魯偉娜，魯法明+，包云霞，曾慶田，段 華

(1.山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590;2.山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590)

0 引言

隨著Web服務(wù)技術(shù)的日益成熟和復(fù)雜業(yè)務(wù)需求場景的不斷涌現(xiàn)，Web服務(wù)組合在面向服務(wù)的架構(gòu)(Service-Oriented Architecture, SOA)領(lǐng)域得到廣泛應(yīng)用，作為服務(wù)組合主要技術(shù)手段的業(yè)務(wù)流程執(zhí)行語言(Business Process Execution Language, BPEL)成為研究與應(yīng)用的熱點(diǎn)之一。與很多傳統(tǒng)的并行編程技術(shù)類似，BPEL程序容易出現(xiàn)數(shù)據(jù)競爭、死鎖、原子性違背等并發(fā)缺陷和漏洞[1-4]，這些漏洞通常難以檢測(cè)、調(diào)試和修復(fù)，導(dǎo)致程序不能正常運(yùn)行甚至崩潰而引發(fā)嚴(yán)重事故，例如2003年美國東北部大停電事故就與程序并發(fā)漏洞相關(guān)[5]。程序并發(fā)漏洞的檢測(cè)和排除是并發(fā)系統(tǒng)設(shè)計(jì)的一大挑戰(zhàn)，而數(shù)據(jù)競爭在并發(fā)漏洞中占有較大比例[6]，且通常為引起原子性違背和順序違背等其他并發(fā)缺陷的根本原因[2,6]，因此本文圍繞BPEL程序的數(shù)據(jù)競爭檢測(cè)問題展開研究。

數(shù)據(jù)競爭指對(duì)同一塊存儲(chǔ)空間存在并發(fā)訪問，而且至少有一個(gè)訪問為寫操作。數(shù)據(jù)競爭會(huì)嚴(yán)重影響系統(tǒng)性能，甚至導(dǎo)致系統(tǒng)崩潰而造成經(jīng)濟(jì)損失[7-12]，例如Therac-25放射治療設(shè)備事故[7]、納斯達(dá)克的Facebook故障[8]等。由于程序調(diào)度的不確定性以及共享存儲(chǔ)空間訪問控制的復(fù)雜性，數(shù)據(jù)競爭檢測(cè)存在一定難度。目前，常見的數(shù)據(jù)競爭檢測(cè)方法總體上分為靜態(tài)檢測(cè)和動(dòng)態(tài)檢測(cè)兩類[13]。靜態(tài)檢測(cè)方法針對(duì)程序源代碼進(jìn)行分析，能夠覆蓋程序可能出現(xiàn)競爭的所有源碼路徑，查全率較高，然而由于缺少程序運(yùn)行時(shí)的信息，導(dǎo)致數(shù)據(jù)競爭的誤報(bào)率較高；動(dòng)態(tài)檢測(cè)方法監(jiān)視程序執(zhí)行過程中的內(nèi)存訪問和同步操作，通過運(yùn)行軌跡收集必要的程序行為信息來判斷構(gòu)成數(shù)據(jù)競爭的操作，能充分利用某次執(zhí)行過程中的運(yùn)行信息，誤報(bào)率較低，然而受限于并發(fā)分支執(zhí)行交錯(cuò)不確定及所收集信息不完整，該方法存在較多漏報(bào)。由于具有高效、低誤報(bào)率等特性，數(shù)據(jù)動(dòng)態(tài)競爭檢測(cè)受到研究界的廣泛關(guān)注[14-15]，本文在保證低誤報(bào)率的前提下提出一種新的降低漏報(bào)率的BPEL程序數(shù)據(jù)競爭動(dòng)態(tài)檢測(cè)方法。

數(shù)據(jù)競爭的前提是針對(duì)同一塊存儲(chǔ)空間的兩個(gè)訪問操作能夠并發(fā)執(zhí)行，且至少有一個(gè)訪問操作為寫操作。數(shù)據(jù)競爭檢測(cè)方法一般通過排除操作間的互斥和因果關(guān)系來判定它們之間是否能夠并發(fā)從而導(dǎo)致數(shù)據(jù)競爭。例如，基于LOCKSET[16-18]的數(shù)據(jù)競爭檢測(cè)方法維護(hù)程序執(zhí)行過程中并發(fā)分支的當(dāng)前持有鎖信息，當(dāng)共享變量不受鎖保護(hù)、不能保證互斥訪問時(shí)報(bào)告數(shù)據(jù)競爭錯(cuò)誤。該方法速度快、開銷低，但未考慮讀寫操作之間可能存在的因果關(guān)系，因此報(bào)告的潛在競爭可能存在大量誤報(bào)。FLANAGAN等[19]和KRALL等[20]提出基于HB(happens-before)關(guān)系進(jìn)行數(shù)據(jù)競爭動(dòng)態(tài)檢測(cè)的方法。HB關(guān)系是并發(fā)程序執(zhí)行時(shí)所有事件間的一種偏序關(guān)系，其借助邏輯時(shí)鐘識(shí)別操作間的各種因果依賴關(guān)系，并將鎖對(duì)象導(dǎo)致的操作間互斥關(guān)系處理為因果約束(約定軌跡中先執(zhí)行的鎖釋放操作與其后執(zhí)行的該鎖的獲取操作存在因果依賴)。然而，上述對(duì)互斥關(guān)系的處理并不恰當(dāng)，由于調(diào)度順序不同，多個(gè)并發(fā)分支對(duì)同一鎖對(duì)象的訪問操作可能存在不同的執(zhí)行順序。HB關(guān)系僅根據(jù)某一條軌跡中的執(zhí)行順序就固化不同分支間鎖操作的因果關(guān)系，丟失了許多潛在的程序行為，帶來了數(shù)據(jù)競爭漏報(bào)。針對(duì)上述問題，很多工作弱化HB關(guān)系對(duì)程序行為的約束以減少漏報(bào)，例如，SMARAGDAKIS等[21]提出的基于CP(causally-precedes)關(guān)系的數(shù)據(jù)競爭檢測(cè)方法、KINI等[22]提出的基于WCP(weak-causally-precedes)關(guān)系的數(shù)據(jù)競爭檢測(cè)方法等，能在一定程度上減少漏報(bào)。

然而，上述各類數(shù)據(jù)競爭檢測(cè)方法均將操作間的互斥關(guān)系處理為因果約束，僅根據(jù)軌跡中的操作順序就限定一些原本可能并不存在的因果約束，導(dǎo)致程序行為信息丟失，引起數(shù)據(jù)競爭的漏報(bào)。針對(duì)該問題，數(shù)據(jù)競爭預(yù)測(cè)[23-26]的概念被提出。數(shù)據(jù)競爭預(yù)測(cè)也是從分析程序運(yùn)行軌跡出發(fā)，但允許對(duì)不同并發(fā)分支的操作進(jìn)行重排，可分析更多潛在的程序運(yùn)行軌跡，從而減小數(shù)據(jù)競爭的漏報(bào)率。例如，DONALDSON等[27]提出基于WDC(weak-doesn’t-commute)關(guān)系的數(shù)據(jù)競爭預(yù)測(cè)方法，該方法刪除了之前一些方法中存在的的過強(qiáng)的因果約束，同時(shí)借助向量時(shí)鐘檢測(cè)數(shù)據(jù)競爭，但會(huì)添加一些程序語義中原本并不存在的因果約束，仍會(huì)導(dǎo)致數(shù)據(jù)競爭漏報(bào)。

前述各類數(shù)據(jù)競爭檢測(cè)和預(yù)測(cè)方法廣泛應(yīng)用于C，C++，Java多線程程序分析，隨著Web服務(wù)技術(shù)的產(chǎn)生和普及，學(xué)者們開始將其用于分析BPEL程序的數(shù)據(jù)競爭。由于BPEL獨(dú)有的一些語法和語義特性(如flow、link機(jī)制和死路徑消除等)，需要對(duì)前述各類檢測(cè)方法進(jìn)行部分調(diào)整。例如，CHEN等[28]提出一種基于圖理論的檢測(cè)方法，將BPEL流程轉(zhuǎn)化為BPEL分段圖，借助BPEL分段圖中節(jié)點(diǎn)的可達(dá)性確定因果依賴關(guān)系，排除因果關(guān)系之后認(rèn)定節(jié)點(diǎn)間的并發(fā)性，以此進(jìn)行數(shù)據(jù)競爭檢測(cè)。YANG等[29]提出一種靜態(tài)分析和動(dòng)態(tài)監(jiān)控相結(jié)合的數(shù)據(jù)競爭檢測(cè)方法，通過一個(gè)修改后的ActiveBPEL引擎監(jiān)控變量訪問事件，并將變量訪問事件及其他各種BPEL活動(dòng)關(guān)聯(lián)到一個(gè)并發(fā)分支中，然后將BPEL程序轉(zhuǎn)換為一種PPEL分段圖，再通過圖中節(jié)點(diǎn)間的可達(dá)性和所屬分支情況判定對(duì)應(yīng)活動(dòng)間是否存在并發(fā)關(guān)系。這兩種方法在檢測(cè)數(shù)據(jù)競爭時(shí)未考慮BPEL中isolated scope對(duì)共享變量訪問所起的類似鎖機(jī)制的訪問控制作用，也沒有考慮死路徑消除等BPEL語義對(duì)程序行為的影響。LI等[30]將flow對(duì)應(yīng)到多線程程序的fork和join操作，將flow中子活動(dòng)對(duì)應(yīng)的并發(fā)分支視作一個(gè)線程，將link對(duì)應(yīng)到多線程程序的wait和post操作，利用鎖的互斥性質(zhì)建模isolated scope代碼片段，將BPEL程序轉(zhuǎn)換為一種粗粒度的BPEL控制流圖，并提出一種結(jié)合發(fā)生序和鎖集的BPEL數(shù)據(jù)競爭檢測(cè)方法。然而該方法為靜態(tài)檢測(cè)方法，流程中l(wèi)ink的真實(shí)狀態(tài)和死路消除信息只有在運(yùn)行中才會(huì)獲得，因此在檢測(cè)過程中可能會(huì)發(fā)生誤報(bào)。HU[31]提出一種預(yù)測(cè)性的BPEL數(shù)據(jù)競爭動(dòng)態(tài)分析方法，較完整地提出了BPEL程序中與并發(fā)相關(guān)的各種約束模型,包括HB序關(guān)系約束、link約束、鎖約束和讀寫約束等，取得了較好的檢測(cè)效果。然而，類似于多線程程序持有鎖的前提下啟動(dòng)新并發(fā)分支會(huì)導(dǎo)致一些復(fù)雜的因果依賴，BPEL程序中存在一些isolated scope與flow，link耦合情境下導(dǎo)致的活動(dòng)間因果關(guān)系(見第2章實(shí)例)，前述方法均不能正確處理。

無論多線程程序的數(shù)據(jù)競爭檢測(cè)方法，還是BPEL數(shù)據(jù)競爭的檢測(cè)和預(yù)測(cè)方法，產(chǎn)生漏報(bào)或誤報(bào)的根源均為對(duì)活動(dòng)間各種依賴關(guān)系的識(shí)別不夠準(zhǔn)確，對(duì)互斥關(guān)系的處理不夠合理。為解決這一問題，本文一方面將BPEL活動(dòng)間可能存在的因果關(guān)系細(xì)分為并發(fā)塊內(nèi)因果依賴、并發(fā)塊間因果依賴、LINK因果依賴和IS-LINK耦合因果依賴關(guān)系，針對(duì)每種因果依賴關(guān)系給出相應(yīng)的識(shí)別方法；另一方面，對(duì)BPEL鎖機(jī)制引起的互斥關(guān)系進(jìn)行更為準(zhǔn)確地建模，以分析更多潛在的執(zhí)行軌跡。在此基礎(chǔ)上，給出一種更加完整而精細(xì)的BPEL程序數(shù)據(jù)競爭動(dòng)態(tài)檢測(cè)和預(yù)測(cè)方法，在一定程度上既保證了較低的誤報(bào)率，又降低了數(shù)據(jù)競爭的漏報(bào)率。

1 實(shí)例與動(dòng)機(jī)分析

本章結(jié)合一個(gè)BPEL程序的運(yùn)行軌跡實(shí)例，結(jié)合前文提到的數(shù)據(jù)競爭動(dòng)態(tài)檢測(cè)方法和HU[31]提出的BPEL數(shù)據(jù)競爭預(yù)測(cè)性分析方法對(duì)其進(jìn)行分析，指出現(xiàn)有方法的不足，給出本文的研究動(dòng)機(jī)和思路。BPEL程序可以看作一個(gè)活動(dòng)的序列，活動(dòng)類型包括基本的賦值活動(dòng)assign、請(qǐng)求活動(dòng)invoke、消息接收活動(dòng)receive、應(yīng)答活動(dòng)reply等，也包括結(jié)構(gòu)化活動(dòng)flow，sequence和特殊活動(dòng)scope，correlations等。sequence用于定義順序結(jié)構(gòu)，其內(nèi)嵌的活動(dòng)必須按順序執(zhí)行；flow用于定義并行結(jié)構(gòu)，其內(nèi)嵌的活動(dòng)具有并發(fā)關(guān)系，可并發(fā)執(zhí)行，執(zhí)行順序也不確定?？梢栽趂low內(nèi)部嵌入多個(gè)sequence結(jié)構(gòu)，每個(gè)sequence結(jié)構(gòu)或每個(gè)獨(dú)立的并發(fā)活動(dòng)都相當(dāng)于一個(gè)線程，將其稱為一個(gè)并發(fā)塊，也可以在flow內(nèi)部通過link聲明link源活動(dòng)和目標(biāo)活動(dòng)的因果關(guān)系。scope一方面用于為嵌套在其中的活動(dòng)提供統(tǒng)一的故障處理功能和補(bǔ)償處理功能；另一方面，當(dāng)scope活動(dòng)的isolated屬性被設(shè)置為yes時(shí)，提供并發(fā)情況下對(duì)共享變量等資源的互斥訪問控制，以保證共享數(shù)據(jù)的一致性。實(shí)際上，可認(rèn)為存在一個(gè)全局的互斥鎖MUTEX，一旦進(jìn)入isolated scope便可認(rèn)為該鎖對(duì)象被相應(yīng)的并發(fā)塊持有，退出isolated scope時(shí)認(rèn)為MUTEX被釋放。

通過對(duì)BPEL引擎的插樁操作[31]可得類似圖1所示的BEPL程序運(yùn)行軌跡。其中，ISLock表示進(jìn)入一個(gè)isolated scope事件,ISUnlock表示退出一個(gè)isolated scope事件，兩者分別對(duì)應(yīng)全局鎖對(duì)象MUTEX的獲取和釋放操作；有向弧link兩端的活動(dòng)LinkSrc和LinkTarget分別對(duì)應(yīng)link的源活動(dòng)與目標(biāo)活動(dòng)；AssignTo表示對(duì)某個(gè)BPEL變量的寫操作,AssignFrom表示對(duì)某個(gè)BPEL變量的讀操作；軌跡中各事件所對(duì)應(yīng)的并發(fā)塊ID以及各事件的生成規(guī)則在2.1節(jié)給出。

根據(jù)圖1所示的BPEL程序運(yùn)行軌跡，兩個(gè)并發(fā)塊關(guān)于變量x的賦值操作不會(huì)發(fā)生數(shù)據(jù)競爭，因?yàn)閘ink約束要求并發(fā)塊CB1必須先進(jìn)入isolated Scope執(zhí)行l(wèi)ink源活動(dòng)后CB2的link目標(biāo)活動(dòng)才能執(zhí)行。又因isolated scope的互斥關(guān)系，在不發(fā)生死鎖的前提下，必須在CB1退出isolated scope區(qū)域后CB2才能進(jìn)入并執(zhí)行后續(xù)x的賦值操作，而CB1對(duì)x的賦值操作在退出isolated scope之前已經(jīng)完成，因此兩者不可能并發(fā)。然而，基于WDC關(guān)系的數(shù)據(jù)競爭檢測(cè)方法僅能識(shí)別link活動(dòng)導(dǎo)致的LinkSrc(CB1,AtoB)與LinkTarget(CB2,AtoB)之間的因果關(guān)系，從而錯(cuò)誤地判定AssignTo(CB1,x)與AssignTo(CB2,x)會(huì)并發(fā)，由此給出一個(gè)數(shù)據(jù)競爭誤報(bào)。另外，即便文獻(xiàn)[31]考慮isolated scope引起的互斥關(guān)系，也會(huì)因AssignTo(CB2,x)執(zhí)行時(shí)未持有鎖而無法排除并發(fā)，故仍然存在上述的數(shù)據(jù)競爭誤報(bào)。

上述各類數(shù)據(jù)競爭漏報(bào)和誤報(bào)的根源在于已有檢測(cè)方法對(duì)操作間因果和互斥關(guān)系的識(shí)別不夠準(zhǔn)確，為此，本文在綜合分析上述實(shí)例的基礎(chǔ)上，對(duì)BPEL程序執(zhí)行軌跡中操作之間的關(guān)系進(jìn)行精細(xì)劃分。具體的關(guān)系分類和定義如下：

定義1給定一個(gè)BPEL程序的運(yùn)行軌跡σ=e1e2e3…en,事件e對(duì)應(yīng)的并發(fā)塊ID記作#CB(e),事件之間的依賴關(guān)系定義如下：

塊內(nèi)相繼、塊間相繼、LINK相繼和IS-LINK耦合相繼關(guān)系統(tǒng)稱為相繼關(guān)系，記作ei→ej。

(5)設(shè)ei為位于某isolated scope中的一個(gè)事件，ej為位于另一個(gè)isolated scope中的事件，且#CB(ei)≠#CB(ej)，則稱兩者之間具有隔離區(qū)互斥關(guān)系，記作ei◇ej。

以圖1中的BPEL運(yùn)行軌跡為例，根據(jù)定義1檢測(cè)到事件ISUnlock(CB1, MUTEX)與LinkTarget(CB2, AtoB)存在IS-LINK耦合相繼關(guān)系，考慮到AssignTo(CB1,x)需要先于前者執(zhí)行(兩者具有塊內(nèi)相繼關(guān)系)，而AssignTo(CB2,x)需要在LinkTarget(CB2,AtoB)之后執(zhí)行(通過多次塊內(nèi)相繼關(guān)系傳遞可得兩者之間的因果依賴)，AssignTo(CB1,x)需先于AssignTo(CB2,x)執(zhí)行，由此可排除這兩個(gè)事件并發(fā)的可能性，進(jìn)而排除其構(gòu)成數(shù)據(jù)競爭的可能。

下面給出由程序運(yùn)行軌跡分析挖掘上述各種關(guān)系的方法。

2 BPEL運(yùn)行軌跡與因果關(guān)系挖掘

本章首先給出BPEL程序運(yùn)行軌跡的生成方法，然后給出由運(yùn)行軌跡挖掘和識(shí)別BPEL程序操作間各類因果關(guān)系的判定方法。

2.1 BPEL基本概念及其運(yùn)行軌跡

BPEL是一種用來描述業(yè)務(wù)流程的編程語言，其中的活動(dòng)分為基本活動(dòng)和結(jié)構(gòu)性活動(dòng)?；净顒?dòng)用于執(zhí)行一定的操作，如賦值活動(dòng)assign、調(diào)用伙伴服務(wù)活動(dòng)invoke、消息接受活動(dòng)receive和應(yīng)答活動(dòng)reply等。結(jié)構(gòu)化活動(dòng)用于嵌套各種基本活動(dòng)或結(jié)構(gòu)性活動(dòng)，如活動(dòng)sequence，flow等，其中sequence用于定義順序結(jié)構(gòu)，其內(nèi)嵌的活動(dòng)須按順序執(zhí)行；flow用于定義并行結(jié)構(gòu)，其內(nèi)嵌的活動(dòng)可并發(fā)執(zhí)行，執(zhí)行順序不確定。flow內(nèi)部可以嵌入多個(gè)sequence結(jié)構(gòu)或者獨(dú)立的并發(fā)活動(dòng)，還可以通過link聲明link源活動(dòng)和目標(biāo)活動(dòng)之間的因果關(guān)系。每個(gè)flow內(nèi)部的sequence結(jié)構(gòu)或并發(fā)活動(dòng)都相當(dāng)于一個(gè)線程，稱為一個(gè)并發(fā)塊。

圖2所示為一個(gè)簡化的網(wǎng)上購物支付金額計(jì)算的BPEL流程實(shí)例，各活動(dòng)右上角數(shù)字為該活動(dòng)所屬并發(fā)塊的ID。其中，main為一個(gè)sequence活動(dòng)，對(duì)應(yīng)流程的開始；receiveInput為一個(gè)receive活動(dòng)，等待訂單消息的到來；收到訂單消息后啟動(dòng)一個(gè)flow活動(dòng)并創(chuàng)建兩個(gè)sequence結(jié)構(gòu)的并發(fā)塊。圖中左側(cè)的并發(fā)塊首先執(zhí)行活動(dòng)AssignDiscount，將折扣率初始化為1；然后進(jìn)入一個(gè)isolated scope，先調(diào)用活動(dòng)InvokeCostSum計(jì)算訂單總額，之再根據(jù)總額大小調(diào)用InvokeDiscount更新折扣率。圖中右側(cè)的并發(fā)塊首先為消費(fèi)者提供VIP注冊(cè)服務(wù)AssignVIP，然后調(diào)用InvokeVipDiscount活動(dòng)進(jìn)一步將折扣率更新為原折扣率的80%。因?yàn)閮H當(dāng)用戶訂單總額超過閾值1 000后才提供VIP注冊(cè)服務(wù)，所以在活動(dòng)InvokeCostSum與AssignVIP之間存在一個(gè)link連接。完成上述各活動(dòng)后flow活動(dòng)結(jié)束，AssignFinalResult根據(jù)最終的折扣信息計(jì)算最終支付金額，replyOutput返回最后的計(jì)算結(jié)果。

下面結(jié)合圖2中的BPEL流程實(shí)例，給出各活動(dòng)所屬并發(fā)塊ID的設(shè)定方法以及BPEL程序運(yùn)行軌跡的生成規(guī)則。

根據(jù)BPEL流程可擴(kuò)展標(biāo)記語言(Extensible Markup Language, XML)文檔定義中活動(dòng)節(jié)點(diǎn)所屬層級(jí)結(jié)構(gòu)逐個(gè)設(shè)置其所屬并發(fā)塊的ID，規(guī)則如下：

(1)約定流程內(nèi)所有一級(jí)節(jié)點(diǎn)同屬于一個(gè)并發(fā)塊，并設(shè)該并發(fā)塊的ID為0。

以圖2中的BPEL程序?yàn)槔?，第一?jí)活動(dòng)節(jié)點(diǎn)為sequence結(jié)構(gòu)化活動(dòng)main，置其并發(fā)塊ID為0，即#CB(main)=0。

(2)設(shè)置一個(gè)全局的并發(fā)塊個(gè)數(shù)計(jì)數(shù)器CBCount，并初始化為0。然后，按XML流程定義文檔中節(jié)點(diǎn)的層級(jí)順序(按層級(jí)順序遍歷XML文檔的過程反映到流程圖上時(shí)需忽略 link活動(dòng)對(duì)應(yīng)的有向弧)遍歷各個(gè)活動(dòng)，一旦遇到一個(gè)flow活動(dòng)，就將該flow活動(dòng)的并發(fā)塊ID設(shè)為其父節(jié)點(diǎn)的并發(fā)塊ID；另外，設(shè)其內(nèi)嵌的一級(jí)子活動(dòng)有n個(gè)，將這些子活動(dòng)的并發(fā)塊ID分別設(shè)置為CBCount+1,CBCount+2,…,CBCount+n，然后令CBCount:=CBCount+n。其他情況下，將當(dāng)前遍歷節(jié)點(diǎn)的并發(fā)塊ID設(shè)置為其父節(jié)點(diǎn)的并發(fā)塊ID。

仍以圖2中的BPEL程序?yàn)槔?，結(jié)構(gòu)化活動(dòng)main的一級(jí)子活動(dòng)包括receiveInput，AssignFinalResult，replyOutput，它們均非flow活動(dòng)，故其并發(fā)塊ID設(shè)置為父節(jié)點(diǎn)main的并發(fā)塊ID，即將其并發(fā)塊ID均設(shè)置為0。至于main包含的flow活動(dòng)，因?yàn)槠浜袃蓚€(gè)一級(jí)子活動(dòng)(均為sequence活動(dòng))，所以將兩個(gè)sequence的并發(fā)塊ID分別設(shè)置為1和2。遍歷到AssignDiscount活動(dòng)時(shí)，將其并發(fā)塊ID設(shè)置為其父節(jié)點(diǎn)sequence的并發(fā)塊ID，其余各個(gè)節(jié)點(diǎn)所屬并發(fā)塊的ID類似可得，最終各活動(dòng)所屬并發(fā)塊ID的計(jì)算結(jié)果見圖2中各活動(dòng)節(jié)點(diǎn)右上角的數(shù)字。

借助BPEL流程引擎的日志系統(tǒng)接口對(duì)BPEL源程序進(jìn)行插樁處理[31]，捕獲程序執(zhí)行過程中與數(shù)據(jù)競爭相關(guān)的操作生成相應(yīng)的事件日志，具體規(guī)則如表1所示。以圖2中的BPEL程序?yàn)槔?，其一個(gè)可能的運(yùn)行軌跡如表2所示。

表1 BPEL程序操作對(duì)應(yīng)的事件信息

表2 計(jì)算網(wǎng)上購物支付金額的BPEL程序運(yùn)行軌跡實(shí)例

續(xù)表2

根據(jù)上述BPEL程序的并發(fā)塊識(shí)別規(guī)則和事件日志生成規(guī)則，可得如下BPEL程序運(yùn)行軌跡的形式化定義：

定義2事件序列σ稱為一個(gè)BPEL程序的運(yùn)行軌跡：

σ::=Operation*;

op∈Operation::=FlowFork(CB0;CB1,…,CBm)|

FlowJoin(CB0;CB1,…,CBm)

|ISLock(MUTEX)|ISUnlock(MUTEX)

|LinkSrc(CB0;linkName)|LinkTarget

(CB0;linkName)

|AssignFrom(CB0,x)|AssignTo(CB0,x)

|InvokeInput(CB0,x)|InvokeOutput(CB0,x);

CB0,…,CBm∈ConcurrentBlock,x∈BPEL_Var。

式中ConcurrentBlock為并發(fā)塊的集合；BPEL_Var為BPEL變量的集合；MUTEX為一個(gè)全局的互斥鎖。各個(gè)事件的含義如表1所示。

2.2 基于邏輯時(shí)鐘的因果關(guān)系挖掘

本文借助邏輯時(shí)鐘識(shí)別BPEL程序運(yùn)行軌跡中各事件之間的因果依賴關(guān)系，下面給出邏輯時(shí)鐘相關(guān)的定義和符號(hào)。

定義3在BPEL程序執(zhí)行的任意時(shí)刻，為每一個(gè)并發(fā)塊CB綁定一個(gè)整數(shù)形式的邏輯時(shí)鐘c∈N，稱CB@c為一個(gè)并發(fā)塊的紀(jì)元，并約定其初始最小紀(jì)元為CB@0，記作⊥CB；稱某時(shí)刻下所有并發(fā)塊的紀(jì)元構(gòu)成的向量為BPEL程序的向量時(shí)鐘，記作V。初始狀態(tài)下BPEL程序的最小向量時(shí)鐘滿足?CB∈ConcurrentBlock:V(CB)=CB@0，記為⊥V。并發(fā)塊紀(jì)元和向量時(shí)鐘的相關(guān)運(yùn)算規(guī)則如下：

(1)并發(fā)塊紀(jì)元比較CB@c1

(2)并發(fā)塊紀(jì)元求最大值 max(CB@c1,CB@c2)=CB@max(c1,c2)。

(3)并發(fā)塊紀(jì)元遞增CB@c+1=CB@(c+1)。

(4)并發(fā)塊紀(jì)元投影getID(CB@c)=CB。

(5)向量時(shí)鐘求最大值V1∪V2=λCB∈ConcurrentBlock:max(V1(CB),V2(CB))。

(6)向量時(shí)鐘遞增incCB(V)=λCB′∈ConcurrentBlock:ifCB′=CBthenV(CB′)+1 elseV(CB)。

(7)并發(fā)塊紀(jì)元與向量時(shí)鐘比較CB@cViffCB@c

以表2中的運(yùn)行軌跡為例，初始情況下BPEL程序的向量時(shí)鐘為〈B1@0,B2@0,B3@0〉(在不引起歧義的情況下，可省略向量時(shí)鐘中各并發(fā)塊的ID和@符號(hào)，如〈B1@0,B2@0,B3@0〉簡記為〈0,0,0〉)。隨著運(yùn)行軌跡中各操作的順序執(zhí)行，每發(fā)生一個(gè)事件，就根據(jù)事件的種類和屬性更新各個(gè)并發(fā)塊的紀(jì)元以及程序的向量時(shí)鐘信息，并根據(jù)其進(jìn)行數(shù)據(jù)競爭檢測(cè)。為此，首先給出由BPEL程序運(yùn)行軌跡挖掘操作間因果關(guān)系的方法，本質(zhì)上是通過識(shí)別事件之間的塊內(nèi)相繼、塊間相繼、LINK相繼和IS-LINK耦合相繼關(guān)系，借助向量時(shí)鐘運(yùn)算推導(dǎo)事件間的因果依賴關(guān)系。

為完成上述任務(wù)，一方面，為每個(gè)事件設(shè)置一個(gè)屬性isISLocked，標(biāo)注其是否在一個(gè)isolated scope中(可理解為是否持有鎖MUTEX，初值為FALSE)；另一方面，對(duì)任意一個(gè)并發(fā)塊B，為其設(shè)置如下3個(gè)向量時(shí)鐘相關(guān)的數(shù)據(jù)對(duì)象：

(1)并發(fā)塊局部向量時(shí)鐘 記作Vself，BPEL每執(zhí)行一個(gè)操作后都針對(duì)其所屬并發(fā)塊更新向量時(shí)鐘，記錄該操作執(zhí)行完畢后并發(fā)塊所能處于的最小全局時(shí)間向量；在未執(zhí)行任何操作的初始狀態(tài)下，初始化其值為⊥V。

(2)并發(fā)塊的link源活動(dòng)向量時(shí)鐘元組集 記作VLinkSrc，是一個(gè)二元組集合，每個(gè)元組形如(linkName,Vself)，表示當(dāng)前并發(fā)塊執(zhí)行了linkName的源活動(dòng)，且該源活動(dòng)執(zhí)行后并發(fā)塊的局部向量時(shí)鐘為Vself，初始狀態(tài)下VLinkSrc為一個(gè)空集。

(3)并發(fā)塊的“IS-link目標(biāo)活動(dòng)”向量時(shí)鐘元組集 記作VIS-LinkTarget，集合中的每個(gè)元組形如(linkName,Vself)，表示曾經(jīng)有并發(fā)塊在某個(gè)isolated scope中執(zhí)行了linkName的源活動(dòng)，而且該并發(fā)塊退出isolated scope時(shí)的向量時(shí)鐘值為Vself，初始狀態(tài)下VLinkSrc與VIS-LinkTarget均為一個(gè)空集(當(dāng)并發(fā)塊尚未退出isolated scope時(shí)約定Vself中各個(gè)分量均為-1)。

對(duì)BPEL運(yùn)行軌跡中的每個(gè)事件，根據(jù)事件類型及相關(guān)屬性信息，若其有可能導(dǎo)致并發(fā)塊之間存在時(shí)序依賴，則按一定規(guī)則更新其所屬并發(fā)塊的局部向量時(shí)鐘、LINK源活動(dòng)向量時(shí)鐘元組集、“IS-link目標(biāo)活動(dòng)”向量時(shí)鐘元組集；至于AssignTo，AssignFrom以及InvokeInput，InvokeOutput等BPEL變量的讀寫操作，它們不會(huì)引起跨并發(fā)塊的時(shí)序依賴，從而不會(huì)更新向量時(shí)鐘。設(shè)一個(gè)事件執(zhí)行前各個(gè)并發(fā)塊向量時(shí)鐘相關(guān)數(shù)據(jù)對(duì)象處于狀態(tài)S,事件執(zhí)行后的狀態(tài)記作S′，并記狀態(tài)S下并發(fā)塊B的局部向量時(shí)鐘為SB.Vself,link源活動(dòng)向量時(shí)鐘元組集、“IS-link目標(biāo)活動(dòng)”向量時(shí)鐘元組集分別為SB.VLinkSrc和SB.VIS-LinkTarget。表3所示為針對(duì)表2中的BPEL程序運(yùn)行軌跡逐步更新相關(guān)向量時(shí)鐘信息的一個(gè)實(shí)例，下面結(jié)合該實(shí)例說明向量時(shí)鐘的更新規(guī)則及其含義。

表3 并發(fā)塊局部向量時(shí)鐘、LINK源活動(dòng)/IS-link目標(biāo)活動(dòng)向量時(shí)鐘元組集更新實(shí)例

以表3中的事件e13:FlowJoin(0;1,2)為例，該操作執(zhí)行前并發(fā)塊0，1，2的局部向量時(shí)鐘分別為1,0,0，1,3,0，1,3,3，故后繼狀態(tài)中并發(fā)塊0的局部向量時(shí)鐘更新為inc0(1,0,0)∪inc1(1,3,4)∪inc2(1,3,3)=2,0,0∪1,4,4∪1,3,4=2,4,4。

以表3中的事件e3:ISLock(1,Mutex)為例，操作執(zhí)行前并發(fā)塊1的局部向量時(shí)鐘值均為1,0,0，執(zhí)行e3后并發(fā)塊1的局部向量時(shí)鐘遞增為

(5)ISUNLOCK規(guī)則 當(dāng)并發(fā)塊B0執(zhí)行操作ISUnlock(B0,MUTEX)時(shí),若該并發(fā)塊的link目標(biāo)活動(dòng)向量時(shí)鐘元組集B0.VIS-LinkTarget為空，或者其中所有元素的向量時(shí)鐘均不為-1,…,-1(意味著當(dāng)前isolated scope中不存在link源活動(dòng))，則該操作不與其他并發(fā)塊的活動(dòng)產(chǎn)生依賴關(guān)系，只需將當(dāng)前并發(fā)塊的局部向量時(shí)鐘遞增為其他并發(fā)塊的向量時(shí)鐘保持不變。另外，需將全局變量isISLocked更新為FALSE。記該規(guī)則為

以表3中的事件e10:ISUnlock(2,MUTEX)為例，該操作執(zhí)行前并發(fā)塊2的IS-link目標(biāo)活動(dòng)向量時(shí)鐘元組集為空，當(dāng)前隔離區(qū)中不存在源活動(dòng)，只需將并發(fā)塊2的局部向量時(shí)鐘1,4,2更新為1,4,3。

(6)ISUNLOCK～LINK規(guī)則 當(dāng)并發(fā)塊B0執(zhí)行操作ISUnlock(B0,MUTEX)時(shí),若并發(fā)塊的IS-link目標(biāo)活動(dòng)向量時(shí)鐘元組集中包括形如(linkName,-1,…,-1)的元素(意味著當(dāng)前isolated scope中存在link源活動(dòng))，則該操作可能會(huì)與linkName的目標(biāo)活動(dòng)產(chǎn)生時(shí)序依賴。為此，除了將B0的局部向量時(shí)鐘遞增為并保持其他并發(fā)塊的局部向量時(shí)鐘保持不變外，應(yīng)將B0的IS-link目標(biāo)活動(dòng)向量時(shí)鐘集中形如(linkName,-1,…,-1)的元素更新為(linkName,incB0(SB0.Vself)),未來執(zhí)行l(wèi)inkName目標(biāo)活動(dòng)時(shí)，若處于一個(gè)isolated scope中，則linkName目標(biāo)活動(dòng)執(zhí)行后的局部向量時(shí)鐘值需要與(linkName,incB0,(SB0.Vself))取最大值。另外，需將全局變量isISLocked更新為FALSE。記該規(guī)則為

以表3中的事件e7:ISUnlock(1,MUTEX)為例，并發(fā)塊1的局部向量時(shí)鐘從〈1,2,0〉遞增為〈1,3,0〉。另外，因該并發(fā)塊的IS-link目標(biāo)活動(dòng)向量時(shí)鐘集中存在元素(AtoB,-1,-1,-1)，當(dāng)前isolated scope中存在link源活動(dòng)，需將(AtoB,-1,-1,-1)更新為(AtoB,-1,-1,-1∪1,3,0)=(AtoB,1,3,0)，未來AtoB的目標(biāo)活動(dòng)若位于一個(gè)isolated scope，則必須在該時(shí)刻之后才能執(zhí)行。

以表3中的事件e9:LinkTarget(2,AtoB)為例，該操作執(zhí)行時(shí)并發(fā)塊處于isolated scope中(isISLocked=TURE)，且B1.VIS-LinkTarget中存在元組(AtoB,1,3,0)，由此可知存在IS-LINK耦合相繼關(guān)系，故將該事件執(zhí)行后的局部向量時(shí)鐘更新為incB2(SB2.Vself)∪1,3,0=incB2(1,0,1)∪1,3,0=1,3,2。另外，該IS-LINK耦合相繼關(guān)系處理完畢，故將(AtoB,1,3,0)從IS-link目標(biāo)活動(dòng)向量時(shí)鐘元組集中刪除，并將(AtoB,1,2,0)從B1.VLinkSrc中刪除。

以表3中的事件e9:LinkTarget(2,AtoB)為例，若e10的發(fā)生順序調(diào)整到其前，則該操作執(zhí)行時(shí)不持有鎖MUTEX，這種情況下不存在IS-LINK耦合關(guān)系，又易見link源活動(dòng)向量時(shí)鐘元組集中存在二元組(AtoB,1,2,0)，故在e9結(jié)束后將向量時(shí)鐘更新為incB2(SB2.Vself)∪1,2,0，同時(shí)從B1.VLinkSrc中將(AtoB,1,2,0)刪除。

根據(jù)上述規(guī)則，可得表1中各并發(fā)塊局部向量時(shí)鐘、link源活動(dòng)向量時(shí)鐘元組集和IS-link目標(biāo)活動(dòng)向量時(shí)鐘元組集的計(jì)算與更新過程。其中，同一并發(fā)塊內(nèi)操作間的實(shí)線有向弧表示塊內(nèi)相繼關(guān)系，不同并發(fā)塊間的虛線有向弧表示其之間的塊間相繼、LINK相繼和IS-LINK耦合相繼關(guān)系。

對(duì)于同一并發(fā)塊內(nèi)的兩個(gè)事件，為刻畫塊內(nèi)因果依賴關(guān)系，每執(zhí)行一次FlowFork，F(xiàn)lowJoin，ISLock，ISUnlock，LinkSrc，LinkSrc這些會(huì)導(dǎo)致并發(fā)塊間時(shí)序依賴的事件，就將局部向量時(shí)鐘內(nèi)該并發(fā)塊所對(duì)應(yīng)維度的分量遞增1，從而通過比較這兩個(gè)事件局部向量時(shí)鐘中其所屬并發(fā)塊分量的大小得到塊內(nèi)因果關(guān)系。例如，事件e3:ISLock(1,MUTEX)與e5:LinkSrc(1, AtoB)具有塊內(nèi)相繼關(guān)系，相應(yīng)地，e3執(zhí)行前局部向量時(shí)鐘1,0,0對(duì)應(yīng)并發(fā)塊B1的分量為0，其嚴(yán)格小于事件e5執(zhí)行后局部向量時(shí)鐘1,2,0所對(duì)應(yīng)B1的分量2。需要注意的是，由于AssignTo，AssignFrom以及InvokeInput，InvokeOutput等變量讀寫操作不會(huì)引起跨并發(fā)塊的時(shí)序依賴，約定共享變量的讀寫不造成線程局部向量時(shí)鐘遞增。例如，表1中，事件e4:AssignFrom(1,cost)在執(zhí)行前后的局部向量時(shí)鐘均為1,1,0。

基于上述分析，任意兩個(gè)事件ei和ej均可基于對(duì)應(yīng)的向量時(shí)鐘分析其因果依賴關(guān)系。然而，即使能判定不存在因果關(guān)系，它們?nèi)钥赡苁遣l(fā)的，因?yàn)橐部赡艽嬖诨コ怅P(guān)系。例如，事件e3:ISLock(1,MUTEX)執(zhí)行前局部向量時(shí)鐘1,0,0對(duì)應(yīng)B1的分量0，不小于事件e8:ISLock(2,MUTEX)執(zhí)行后局部向量時(shí)鐘1,0,1對(duì)應(yīng)B1的分量0，故兩者之間不存在因果依賴關(guān)系，但其之間因isolated scope的隔離區(qū)互斥關(guān)系導(dǎo)致無法并發(fā)。對(duì)同一BPEL變量的兩個(gè)讀寫/寫寫操作，僅當(dāng)其既不具備因果關(guān)系，也不具備隔離區(qū)互斥關(guān)系時(shí)，才可認(rèn)定其并發(fā)而導(dǎo)致數(shù)據(jù)競爭，下面給出具體的數(shù)據(jù)競爭檢測(cè)過程和更多檢測(cè)實(shí)例。

3 BPEL數(shù)據(jù)競爭檢測(cè)

第2章給出了兩個(gè)事件間因果關(guān)系的挖掘方法，針對(duì)同一個(gè)BPEL變量的兩個(gè)讀寫/寫寫事件，若其屬于不同并發(fā)塊、不具備所挖掘到的各類因果關(guān)系，而且這兩個(gè)事件執(zhí)行前的isISLocked屬性取值不同時(shí)為TRUE(不同時(shí)位于isolated scope中，意味著不具備隔離區(qū)互斥關(guān)系)，則可認(rèn)定兩者構(gòu)成數(shù)據(jù)競爭。以表3為例，事件e6:AssignTo(1,disc)是對(duì)disc的寫操作，e11:InvokeInput(2,disc)是針對(duì)BPEL變量disc的讀操作，兩者屬于不同的并發(fā)塊，且兩者執(zhí)行前的isISLocked屬性不同時(shí)為TRUE，然而e6執(zhí)行前局部向量時(shí)鐘1,2,0對(duì)應(yīng)并發(fā)塊B1的分量為2，小于e11執(zhí)行后局部向量時(shí)鐘1,3,3對(duì)應(yīng)B1的分量3，因此兩者具有因果關(guān)系，不構(gòu)成數(shù)據(jù)競爭。

為提高數(shù)據(jù)競爭檢測(cè)的效率，本文并非對(duì)每一個(gè)共享變量的兩個(gè)讀寫/寫寫操作逐一進(jìn)行數(shù)據(jù)競爭檢測(cè)，而是為每一個(gè)BPEL共享變量分別維護(hù)讀事件、寫事件信息表。表4以變量disc為例給出讀寫事件信息表示例，表中每個(gè)元素為一個(gè)形如(B,isISLocked,V)的三元組，B為當(dāng)前讀/寫事件所屬的并發(fā)塊，isISLocked為描述當(dāng)前事件是否處于isolated scope的布爾值，V為讀/寫事件執(zhí)行后的局部向量時(shí)鐘。初始情況下，各個(gè)變量的讀寫事件信息表均為空；然后，每遇到一個(gè)針對(duì)變量x的AssignTo或InvokeOutput操作，均向Sx.W中添加一個(gè)三元組(B,isISLocked,V)，每當(dāng)遇到一個(gè)針對(duì)變量x的AssignFrom或InvokeInput操作，就向Sx.R中添加一個(gè)三元組(B,isISLocked,V)，其中B，isISLocked，V的含義如前所述；另外，每添加一個(gè)新的三元組，都按如下兩種規(guī)則進(jìn)行數(shù)據(jù)競爭檢測(cè)：

(1)RACE-W規(guī)則 當(dāng)遇到一個(gè)針對(duì)變量x的寫操作時(shí)，假設(shè)其對(duì)應(yīng)的三元組為t，則檢查x當(dāng)前對(duì)應(yīng)的讀/寫事件列表中是否存在三元組t′滿足如下條件，若存在，則t與t′對(duì)應(yīng)的操作構(gòu)成一對(duì)數(shù)據(jù)競爭。

?t′∈(Sx.W∪Sx.R):(t.B!=t′.B)∧

(t.isISLocked=FALSE∨t′.isISLocked=

FALSE)∧(t′.V(t′.B)≥t.V(t.B))。

式中：t.B!=t′.B表示兩個(gè)操作分屬于不同的并發(fā)塊(排除塊內(nèi)因果)；t.isISLocked=FALSE∨t′.isISLocked=FALSE表示兩個(gè)操作不能都位于isolated scope中(排除互斥關(guān)系)；t′.V(t′.B)≥t.V(t.B)表示兩個(gè)操作不具備塊間相繼、LINK相繼或IS-LINK耦合相繼導(dǎo)致的塊間因果關(guān)系。

(2)RACE-R規(guī)則 當(dāng)遇到一個(gè)針對(duì)變量x的讀操作時(shí)，假設(shè)其對(duì)應(yīng)的三元組為t，則檢查x當(dāng)前對(duì)應(yīng)的寫事件列表中是否存在三元組t′滿足如下條件，若存在，則t與t′對(duì)應(yīng)的操作構(gòu)成一對(duì)數(shù)據(jù)競爭。與RACE-W規(guī)則相比，唯一的不同是，本規(guī)則要求三元組t′對(duì)應(yīng)變量x的一個(gè)寫操作。

?t′∈Sx.W:(t.B!=t′.B)∧

(t.isISLocked=FALSE∨t′.isISLocked

=FALSE)∧(t′.V(t′.B)≥t.V(t.B))。

表4 共享變量讀/寫操作信息表與數(shù)據(jù)競爭檢測(cè)實(shí)例

續(xù)表4

以表4中的事件e12為例，該事件是針對(duì)變量disc的一個(gè)寫操作，對(duì)應(yīng)的寫事件信息三元組為(2,FALSE,1,3,3)。在disc的寫事件信息表中，所有其他兩個(gè)三元組均對(duì)應(yīng)并發(fā)塊B1，其向量時(shí)鐘中對(duì)應(yīng)B1的分量均小于e12向量時(shí)鐘中對(duì)應(yīng)B1的分量3；而且，disc的讀事件信息表只有一個(gè)三元組(2,FALSE,1,3,3)，其與e12同屬一個(gè)并發(fā)塊。由此可見，RACE-W規(guī)則不滿足，故該操作不與之前的操作構(gòu)成數(shù)據(jù)競爭。類似地，表3中所有的變量讀寫操作都不存在數(shù)據(jù)競爭。

表4中運(yùn)行軌跡的分析過程與第2章對(duì)圖1中運(yùn)行軌跡的分析過程類似，基于WDC的數(shù)據(jù)競爭檢測(cè)方法僅能識(shí)別link源活動(dòng)e5:LinkSrc(1,AtoB)與目標(biāo)活動(dòng)e9:LinkTarget(2,AtoB)之間的因果關(guān)系，從而錯(cuò)誤地判定e6:AssignTo(1,disc)與e12:AssignTo(2,disc)能并發(fā)，導(dǎo)致誤報(bào)數(shù)據(jù)競爭。相比而言，如上述檢測(cè)過程所述，本文方法能識(shí)別出兩者之間真實(shí)存在的因果關(guān)系，從而避免誤報(bào)。

再以表5中的BPEL程序運(yùn)行軌跡為例，基于WDC的數(shù)據(jù)競爭檢測(cè)方法會(huì)認(rèn)為e5與e7之間存在因果關(guān)系，而e4要先于e5執(zhí)行，e5要先于e9執(zhí)行，由此判定e4與e9之間存在因果關(guān)系，從而漏報(bào)e4與e9間的數(shù)據(jù)競爭。類似地，基于HB的數(shù)據(jù)競爭檢測(cè)方法會(huì)認(rèn)為e5與e6之間存在因果關(guān)系，由此也錯(cuò)誤地認(rèn)定e4與e9之間存在因果關(guān)系，導(dǎo)致漏報(bào)數(shù)據(jù)競爭。本文方法則不會(huì)出現(xiàn)這種漏報(bào)現(xiàn)象，它能檢測(cè)到事件e9:AssignTo(2,y)與e4:AssignTo(1,y)之間存在數(shù)據(jù)競爭，原因是：①兩者分屬于不同并發(fā)塊；②兩者之一e9沒有位于isolated scope中；③e4執(zhí)行前局部向量時(shí)鐘對(duì)應(yīng)并發(fā)塊2的分量為1，不小于e9執(zhí)行后局部向量時(shí)鐘對(duì)應(yīng)并發(fā)塊2的分量0。由此可知滿足RACE-W規(guī)則，e4與e9構(gòu)成數(shù)據(jù)競爭。

表5 數(shù)據(jù)競爭檢測(cè)實(shí)例

續(xù)表5

由表3與表5所示的兩個(gè)BPEL程序數(shù)據(jù)競爭動(dòng)態(tài)分析實(shí)例可見，相比以往基于HB，WDC等關(guān)系的數(shù)據(jù)競爭動(dòng)態(tài)分析方法，本文方法能排除更多誤報(bào)，而且部分情況下會(huì)減少漏報(bào)。究其原因，本文對(duì)IS-LINK耦合相繼關(guān)系導(dǎo)致的因果依賴進(jìn)行了準(zhǔn)確界定和識(shí)別，而且借助分析isISLocked屬性規(guī)避了已有動(dòng)態(tài)分析方法將互斥關(guān)系建模為因果約束的不足。

4 相關(guān)工作對(duì)比

結(jié)合文獻(xiàn)[28,30-32]給出的BPEL程序?qū)嵗?，?duì)比了本文方法和相應(yīng)參考文獻(xiàn)方法的檢測(cè)結(jié)果。對(duì)比結(jié)果顯示，對(duì)文獻(xiàn)[30]給出的購書訂單流程、文獻(xiàn)[32]的訂單處理流程、文獻(xiàn)[28]的客戶訂單處理流程和文獻(xiàn)[31]的訂單金額處理流程，本文方法均能準(zhǔn)確檢測(cè)出流程中存在的數(shù)據(jù)競爭，不存在誤報(bào)或漏報(bào)現(xiàn)象。而對(duì)于本文給出的網(wǎng)上購物支付金額計(jì)算的BPEL流程，當(dāng)以表4中的運(yùn)行軌跡為輸入進(jìn)行數(shù)據(jù)競爭檢測(cè)時(shí)，文獻(xiàn)[32]中基于XML節(jié)點(diǎn)樹分析的方法會(huì)有2處誤報(bào)，文獻(xiàn)[28]基于可達(dá)性分析的方法有1處誤報(bào)，文獻(xiàn)[31]的動(dòng)態(tài)檢測(cè)方法有1處誤報(bào)；當(dāng)以其表6中的運(yùn)行軌跡為輸入進(jìn)行數(shù)據(jù)競爭檢測(cè)時(shí)，文獻(xiàn)[30]的方法有1處漏報(bào)，文獻(xiàn)[28，32]的方法各有1處誤報(bào)。另外，用基于HB關(guān)系的數(shù)據(jù)競爭檢測(cè)方法對(duì)表6中的運(yùn)行軌跡進(jìn)行分析時(shí)會(huì)存在1處漏報(bào)，用基于WDC關(guān)系的數(shù)據(jù)競爭檢測(cè)方法對(duì)表4中的運(yùn)行軌跡進(jìn)行分析時(shí)會(huì)有有2處誤報(bào)。相比之下，本文方法能在保證準(zhǔn)確率的同時(shí)降低誤報(bào)率。究其原因，上述文獻(xiàn)中的數(shù)據(jù)競爭動(dòng)態(tài)檢測(cè)方法對(duì)因果關(guān)系的建模不夠精確，且將互斥關(guān)系處理為因果約束，會(huì)導(dǎo)致多種數(shù)據(jù)競爭誤報(bào)或漏報(bào)。而本文對(duì)BPEL活動(dòng)間的因果關(guān)系進(jìn)行更加精確地劃分，基于邏輯時(shí)鐘給出了細(xì)分后各種因果關(guān)系的識(shí)別方法，并聯(lián)合向量時(shí)鐘和全局互斥鎖對(duì)BPEL程序中活動(dòng)間的互斥關(guān)系進(jìn)行準(zhǔn)確建模，在一定程度上降低了數(shù)據(jù)競爭的誤報(bào)率和漏報(bào)率。

然而，本文方法相比已有方法也有一定不足，link源活動(dòng)向量時(shí)鐘元組集、IS-link目標(biāo)活動(dòng)向量時(shí)鐘元組集和BPEL變量讀/寫操作信息表的引入使本文所提數(shù)據(jù)競爭檢測(cè)方法會(huì)消耗更多的時(shí)間和空間，但是額外時(shí)間和空間復(fù)雜度比WDC等方法增加有限，增加的規(guī)模與并發(fā)塊數(shù)量、BPEL變量讀寫操作的數(shù)量以及軌跡長度為線性關(guān)系。具體而言，WDC和DC有相同的時(shí)間復(fù)雜度O(N×(L×T+T2))(N，L，T分別表示事件、鎖和線程的數(shù)量)，最壞情況下的空間復(fù)雜度為Ω(N)。本文所提方法的時(shí)間復(fù)雜度為O((N+l)×n)，空間復(fù)雜度為Ω((T2+l+N)×n)(N，l，T分別表示讀寫操作變量、link操作和線程數(shù)量)。

5 結(jié)束語

為更準(zhǔn)確地對(duì)BPEL程序的數(shù)據(jù)競爭進(jìn)行動(dòng)態(tài)檢測(cè)，本文將BPEL活動(dòng)間可能存在的因果關(guān)系細(xì)分為并發(fā)塊的塊內(nèi)依賴、塊間依賴、LINK依賴和IS-LINK耦合依賴，針對(duì)每種因果依賴關(guān)系給出了基于向量時(shí)鐘的相應(yīng)識(shí)別方法，以減少基于HB，WDC關(guān)系的傳統(tǒng)數(shù)據(jù)競爭檢測(cè)方法存在的部分誤報(bào)現(xiàn)象；另外，拋棄以往動(dòng)態(tài)分析將鎖集互斥關(guān)系建模為因果依賴的常規(guī)作法，通過聯(lián)合向量時(shí)鐘和全局互斥鎖對(duì)BPEL鎖機(jī)制引起的隔離區(qū)互斥關(guān)系進(jìn)行了更加準(zhǔn)確地建模，為分析更多潛在執(zhí)行軌跡和數(shù)據(jù)競爭預(yù)測(cè)提供了可能，同時(shí)減少了對(duì)數(shù)據(jù)競爭的漏報(bào)。

相比傳統(tǒng)的數(shù)據(jù)競爭動(dòng)態(tài)檢測(cè)方法，本文給出一種更加準(zhǔn)確的BPEL程序數(shù)據(jù)競爭動(dòng)態(tài)檢測(cè)和預(yù)測(cè)方法，雖然在一定程度上降低了數(shù)據(jù)競爭的誤報(bào)率和漏報(bào)率，但是以犧牲更多空間和時(shí)間維護(hù)處理link源活動(dòng)向量時(shí)鐘元組集、IS-link目標(biāo)活動(dòng)向量時(shí)鐘元組集和BPEL變量讀/寫操作信息表等數(shù)據(jù)對(duì)象為代價(jià)。另外，本文工作仍存在一些不足。首先，本文僅從單一BPEL程序運(yùn)行軌跡出發(fā)分析潛在的數(shù)據(jù)競爭，未能充分利用程序代碼或其他更多軌跡信息，難以避免地出現(xiàn)漏報(bào)數(shù)據(jù)競爭的情況；其次，本文未考慮BPEL中存在的wait等活動(dòng)對(duì)數(shù)據(jù)競爭檢測(cè)的影響。后續(xù)工作將對(duì)這些問題展開進(jìn)一步研究，期望將該方法拓展到多線程程序等更一般化的并行程序數(shù)據(jù)競爭檢測(cè)領(lǐng)域。