BPEL過程一致性度量

張學偉，邢建春，宋巍，王洪達，韓德帥

（1.解放軍理工大學國防工程學院，江蘇南京210007；2.南京理工大學計算機科學與工程學院，江蘇南京210094）

BPEL過程一致性度量

張學偉1，邢建春1，宋巍2，王洪達1，韓德帥1

（1.解放軍理工大學國防工程學院，江蘇南京210007；2.南京理工大學計算機科學與工程學院，江蘇南京210094）

服務組合和云計算作為面向服務體系結構下資源集成和應用互聯的有效手段，使得描述Web服務的BPEL過程產生了眾多變種。針對變種整合和變種之間差異檢測的問題，研究BPEL過程一致性就很有意義。然而，現有的方法要么僅提供一個“是／否”的定性回答，要么是從控制流層面數量化地度量一致性，導致度量結果不符合用戶的預期評判。因此，采用活動間的行為約束作為度量基礎，以事件日志中活動的發生概率為權重，一種數值化地度量BPEL過程行為一致性的方法被提出，并且實現了計算一致性的軟件工具。通過對6組BPEL過程進行分析，驗證了該方法的可行性和有效性，且度量結果符合用戶的預期。

BPEL過程；活動約束圖；事件日志；一致性度量

BPEL語言［1］作為一種流行的描述Web服務的業界標準，受到了越來越多的業務人員的重視。隨著云計算與服務計算時代的到來用戶需求的不斷變化和公司內部的適時調整，系統原有的BPEL過程可能演化出多個變種。為確保業務人員有效地檢測變種間的差異以及整合變種［2］，研究BPEL過程的一致性就很有意義。在軟件工程領域，一致性被定義為“無差異、標準化和無矛盾的程度”［3］。由于提出的方法以活動間的行為約束作為評判BPEL過程是否一致的基礎，所以BPEL過程一致性被定義為“行為約束不變性和無矛盾”［4］。

雖然已經提出了多種方法度量一致性［5?10］，比如跡等價［5］、互模擬［6］、行為側畫［7?8］、典型行為［9］等，但大多數并不適用于BPEL過程。1）多數方法僅能給出定性的回答，導致無法有效區分過程之間是輕微還是完全地不同；2）由于過程在執行時一些活動可能偶爾被執行，還有一些可能頻繁地在過程實例中出現，使得活動在過程中的重要程度出現差別。但僅個別方法在度量一致性時考慮了此因素；3）現有方法僅從控制流層面刻畫活動間的行為約束，抽象掉了數據信息，導致其不能準確度量BPEL過程一致性。為解決上述問題，提出一種基于事件日志數值化地度量BPEL過程一致性的方法。

1 BPEL過程控制

通過一個啟發案例引出所要研究的問題，并在隨后章節中借助此案例說明提出的方法的可行性和有效性。圖1為旅行代理BPEL過程G1、G2的控制流程圖（BPEL control flow graph，BCFG）［10］，描述的是賓館和機票預定服務。該案例來自Oracle公司的BPEL過程管理庫，由第三方對其進行適當的調整，并在ActiveBPEL工具中分別執行100次，獲得相應的執行路徑集合。對整個過程而言，執行頻率較高的路徑上的活動比執行頻率較低路徑上的活動更為重要，那么它對BPEL過程一致性的影響也就更為明顯。

圖1 旅行代理過程的控制流程圖和事件日志Fig.1 CFGs and event logs of travel agency processes

對于BPEL過程一致性的度量，首要解決過程對齊的問題。在過程模型領域中，由于活動抽象層次的不同，過程對齊可分為2類：水平對齊和垂直對齊。如果2個過程屬于同一抽象層次，那么它們為水平對齊，如果屬于不同的抽象層次，則為垂直對齊。雖然研究的對象都屬于同一抽象層次，但是由于BPEL過程中通信機制的不同也可能導致過程之間垂直對齊的出現。假定每個BPEL過程中的活動都具有唯一的名稱標識，對齊不同過程中的活動，當且僅當它們的名稱一致。圖1中G2的＜invoke＞活動A14與G1中存在異步調用依賴關系的＜invoke＞活動A3和＜receive＞活動A4在名稱和功能上一致，則活動A14與A3、A4為垂直對齊。盡管度量BPEL過程一致性涉及到過程對齊的問題，但它獨立于水平對齊和垂直對齊的區分。

為了能從控制流和數據流2個層面刻畫BPEL過程的行為約束，并將事件日志引入到一致性度量中，圖2為提出的方法的研究框架。1）應用BCFGs描述BPEL過程，并獲得相應的事件日志；2）根據BCFGs，應用BPEL活動約束圖刻畫活動間的行為約束；3）基于BEPL活動約束圖和事件日志，根據2個過程的對齊活動對集合和一致活動對集合，計算它們的一致性程度。

圖2 提出的方法的技術框架Fig.2 The technology framework of proposed approach

2 BPEL活動約束圖

在BPEL過程中的活動之間存在三類本質的行為約束：偏序關系（→）、互斥關系（+）和獨立關系（｜｜）［11］。偏序關系由控制依賴、數據依賴和異步調用依賴組成。在選擇或循環結構中，由于每次只能執行一條分支，導致不同分支上的活動間存在互斥關系。對于以上2種關系都不存在的活動對，則認為是獨立關系。于是，將BPEL過程的活動和行為約束刻畫到一個圖形結構中，得到BPEL活動約束圖。

定義1 BPEL活動約束圖（BPEL activity con?straint graph，BACG）是一個二元組（N，E），

1）N是活動集合，包含基本活動、控制活動以及一個表示BPEL過程開始的入口節點Entry；

2）E＝E1∪E2是邊的集合，其中有向邊＜Ai，Aj＞∈E1表示偏序關系，無向邊＜Ak，Al＞∈E2表示互斥關系。

BACG的控制依賴子圖是一棵以Entry節點為根的樹，其中分支節點表示BPEL中的控制活動，葉子節點表示基本活動。為精確刻畫BPEL的行為，在Entry節點與其所控制的任一活動之間的控制依賴邊上附加一個“T”的標簽，而在選擇或循環活動與其控制的活動之間的控制依賴邊上附加“T”或“F”的標簽，標簽的取值取決于受控活動為“真”（T）時執行還是為“假”（F）時執行。

定理1 BPEL過程包含的行為關系→、+、｜｜互為排斥，→、→-1、+、｜｜分割活動對集合N×N。

由于選擇或循環結構中每次只能執行其中一條分支，導致不同分支上的活動之間不可能存在偏序關系，因此三類關系互為排斥。如果活動對（Ai，Aj）存在偏序關系，且（Aj，Ai）沒有數據依賴關系，那么（Ai，Aj）為反偏序關系（→-1），對于既沒有偏序關系也沒有互斥關系的活動對，都歸于獨立關系，因而三類關系構成一個活動對關系全集。

定理2 BPEL過程中的活動Ai對其自身可能是偏序關系也可能是獨立關系。

由于活動Ai與自身可能存在數據依賴構成閉環，所以（Aj，Ai）存在偏序關系，如果不存在這種數據依賴閉環，則為獨立關系。例如，圖1中A1｜｜A1。

3 一致性的分析和度量

3.1 對應關系

為度量BPEL過程一致性，引入了對齊概念。過程對齊通過2過程活動間的對應關系建立［7］。

定義2 對應關系（correspondences）。設N1、N2分別是BPEL過程P1、P2的活動集合。對應關系～?N1×N2通過對應活動使P1和P2對齊以至于～≠?。

根據對應關系的基數，BPEL過程P1、P2之間的對應關系能夠被分為以下3種：

1）如果?Ai∈N1［?Aj∈N2［Ai～Aj］］，那么從P1到P2的映射為滿射；

2）如果（Ai，Ax），（Aj，Ay）∈～且（Ax＝Ay）?（Ai＝Ay），那么從P1到P2映射為單射；

3）如果P1與P2即滿足滿射也滿足單射，那么它們互為雙射。

例如，圖1中的過程G1、G2，其中A3～A14，A4～A14。在這種情況下，從過程G1到G2的對應關系為滿射。反過來從過程G2到G1的對應關系則為單射。對應關系的基數特性反映了水平對齊和垂直對齊之間的差異。水平對齊的兩過程對應關系都為單射，那么活動之間僅有1∶1的對應。而垂直對齊對于對應關系的基數沒有限制。

對齊BPEL過程的一致性程度反映的是過程之間對應活動的質量。僅那些根據對應關系對齊的活動在度量BPEL過程一致性時才會被考慮。

定義3 對齊活動（aligned activities）。設～表示BPEL過程P1、P2之間的對應關系。P1的對齊活動集合N1～?N1被定義為N1～＝｛Ai∈N1｜?Aj∈N2［Ai～Aj］｝，P2的對齊活動集合N2～的定義與上類似。

3.2 事件日志

一個可執行的BPEL過程在ActiveBPEL工具下經過多次重復執行，可產生多條執行路徑（剔除那些未完全執行的路徑），這些執行路徑的集合即為BPEL過程的事件日志。

定義4 事件日志L是某個集合S中的執行路徑的多重集，L∈B（S?），其中S?表示完全執行路徑集，B（S?）是由多個完全執行路徑集構成。

事件日志是由完全執行路徑構成的多重集，且同一路徑可能被執行多次。為將活動的發生概率引入到BPEL過程一致性度量中，需計算2個過程的每種路徑被執行的頻率。由于度量BPEL過程一致性比較的是兩個對齊的過程，所以計算每種路徑執行概率是以2個過程的所有執行路徑數目作基數。圖3展示了過程G1、G2中每種路徑的執行頻率。由于一致性度量只與那些對齊活動有關，所以僅計算2個過程中對齊活動的發生概率，如圖1中A8的發生概率fA＝0.2+0.125+0.25+0.1＝0.675。

圖3 2個BPEL過程的每種路徑執行頻率Fig.3 Execution frequency of each trace of BPEL processes

3.3 BPEL過程一致性度量

由于提出的方法對活動之間的映射關系是單射（1∶1）還是滿射（1∶n）沒有要求，所以既能應用于水平對齊也能應用于垂直對齊。為了描述對齊過程中行為約束，定義了2個對齊活動對集合，活動對中的活動來自同一BPEL過程。這些集合囊括了2個過程所有對齊的活動對并保存了每個過程的BACG所包含的行為約束。設R1∈｛→，→-1，+，｜｜｝、R2∈｛→，→-1，+，｜｜｝分別為P1、P2中的行為約束。

定義5 一致活動對（consistent activity pairs）。BPEL過程P1、P2根據對應關系“～”對齊。P1的一致活動對集合CA1～?（N1

～×N1

～）所包含的活動對（Ai，Aj）滿足以下2種情形：1）當Ai＝Aj，且?Ak∈N2～有Ai～Ak時，存在AiR1Ai?AkR2Ak；

2）當Ai≠Aj，且?Ak，有Ak≠Al，Ai～ Ak，Aj＝Al時，存在2種情形：

①AiR1Aj?AkR2Al；②Ai～Al，Aj＝Ak。

P2的一致活動對集合的定義與上類似。根據定義可知，一致活動對是對齊活動對的一個子集。由于研究的BPEL過程都是同一層次，所以重疊的對應活動對并不存在。

對齊BPEL過程之間的差異可以分為2種；對齊活動對的控制流相同，但行為約束不同；對齊活動對的行為關系相同，但控制流不同。例如，圖1中一致活動對（A5，A6）的控制流在G1中為并發關系，在G2中卻為順序關系，但行為關系都為獨立關系。提出的方法更注重的是過程之間本質關系的不同，而對于表象的差異并不敏感。只要對齊活動對行為關系不同，該活動對就一定不是一致活動對，若行為關系相同且為獨立關系，即使控制流不同，該活動對依然是一致活動對。

根據3.1中定義的事件日志以及給出的路徑執行頻率和對齊活動發生概率的計算方法，計算2個BPEL過程的對齊活動對的發生概率。由于對齊活動對的發生概率與該活動對中的2個活動的發生概率大小有關，所以取較小的發生概率作為一致活動對的概率fCA（Ai）。例如，圖1中對齊活動對（A1，A2）的fCA（A1）＝［1.0，1.0］＝1.0；（A5，A8）的fCA（A8）＝［1.0，0.675］＝0.675；（A9，A10）的fCA（A10）＝［0.675，0.325］＝0.325。基于對齊活動對和其發生概率，定義對齊BPEL過程一致性度量程度。

定義6 對齊過程一致性程度（consistency de?gree of alignment）。設BPEL過程P1、P2根據對應關系～對齊。一致性程度被定義為

基于定義6和事件日志，能夠計算圖1中的BPEL過程G1、G2之間的一致性程度。圖4為G1、G2的BACGs。根據圖4中的對齊活動獲得2個過程的所有對齊活動對，即｜（N1～×N1～）｜＝13×13＝169，｜（N2～×N2～）｜＝12×12＝144。從圖4中可以發現對齊活動A12的控制依賴不同，G1中A12被Entry節點控制而G2中A12被A15控制，這導致由A12構成的所有對齊活動對都不是一致活動對，G1中不一致活動對｜（A12×Ai）｜+｜（Ai×A12）｜-1＝13+13-1＝25；G2中不一致活動對｜（A12×Ai）｜+｜（Ai×A12）｜-1＝12+ 12-1＝23。根據事件日志，每個過程的所有對齊活動對的發生概率都能夠獲得。因此過程G1、G2的一致性程度：

圖5 一致性度量的原型工具Fig.5 A proof?on?concept tool for consistency measure?ment

圖7 BPEL過程G1、G2的BACGsFig.7 BACGs of BPEL Processes G1and G2

4 評估

首先介紹度量BPEL過程一致性方法原型工具的實現，然后通過6對BPEL過程對驗證提出的方法的可行性和有效性。

4.1 實現

一種計算BPEL過程一致性的原型工具被實現。它以2個BPEL過程和相應的路徑和數目為輸入，以2個過程的一致性程度為輸出。原型工具的具體實現過程：首先是將輸入的2個BPEL過程轉變成BCFGs的數據存儲格式，BCFGs中的活動包含名稱、輸入輸出變量、活動類型等信息；通過活動之間的行為關系的分析獲得BACGs；然后根據2個過程的每種路徑以及相應的數目，計算每個對齊活動的發生概率；最后根據BACGs獲得所有對齊活動對和一致活動對以及它們的發生概率，能夠計算出2個過程的一致性程度。圖5展示的是原型工具的輸出，采用矩陣形式表示BACG有助于用戶發現不一致活動對。此外，應用該工具還能夠獲得3個副產品：控制流程圖、活動約束圖和存儲活動的xml文件。它們能夠幫助用戶更好地理解BPEL過程一致性的度量方法。

4.2 案例分析

為展示提出的方法的可行性和有效性，將其應用于實際BPEL過程中進行驗證。案例中G1、G2描述的是選擇賓館預訂服務，G3、G4從Oracle公司BPEL過程管理庫中選取，描述的是同時預定2家賓館的服務。在ActiveBPEL工具下，多次執行案例中的BPEL過程，建立了相應的事件日志，并經過篩選、統計和分析，獲得了每個過程的每種路徑執行次數，如圖6所示。其中由于G3過程中有并發結構，所以出現了6種執行路徑，而G4是順序結構，則只有一種執行路徑。

基于圖6中的BCFGs，分析活動間的行為約束，建立每個過程的BACG，如圖7所示。由于每個活動都有唯一名稱標識，因此任意一對過程根據對應關系都能獲得各自的對齊活動集合，從而對齊活動對集合也能被建立。例如，G1與G3的對齊活動集合同為（A1，A3，A4，A5，A6，A7），那么它們的對齊活動對數目為｜N1～×N1～｜＝｜N3～×N3～｜＝36。通過比較2個過程的BACGs，獲得它們的一致活動對集合。根據圖6中的執行路徑頻率，計算每對過程的對齊活動的發生概率，然后比較對齊活動對中每個活動的發生概率，獲得該活動對的發生概率，即其中較小的概率。例如G1與G3的對齊活動的發生概率分別為：

fA（A1）＝fA（A7）＝（70+30+40+20+10×4）／200＝1.0；

fA（A3）＝fA（A4）＝（70+40+20+10×4）／200＝0.85；

fA（A5）＝fA（A6）＝（30+40+20+10×4）／200＝0.65。

對齊活動對（A1，A3）的發生概率為0.85。根據每個過程的對齊活動對數目和一致活動數目以及相應的發生概率，計算出2個過程一致性程度。例如，過程G1和G3的一致性程度為

圖6 BPEL過程的4個變種和事件日志Fig.6 Four variants of BPEL processes and their event logs

圖7 4個變種的BACGsFig.7 BACGs of four variants

圖8 展示了案例中任意一對過程之間的一致性程度。從圖中可以看出結構化活動的改變會很大程度地影響2個過程的一致性，因為它導致其所有的子活動的控制依賴關系、互斥關系發生改變。而順序結構與并發結構之間的轉換在不改變數據依賴關系的前提下不會影響一致性。此外，具有獨立關系的活動之間執行順序的調換也不影響一致性。

實驗中的案例沒有隨機地選取樣本，而是將研究對象定位于第三方提供的流程。而這些流程多少在維度和結構上有些簡單比較適合于評估，這就可能影響實驗的典型性。通過實際BPEL過程驗證提出的方法的合適性，案例分析表明該方法是符合用戶期望的。而它能否適用于其他BPEL流程或其它語言描述的業務流程，比如XML流程定義語言XP?DL（XML process definition language）等，需要在下一步工作中將該方法應用到更多的實例中。

圖8 對齊過程之間的一致性程度Fig.8 Consistency degrees of aligned processes

4 結論

提出的BPEL過程一致性度量方法根據事件日志中活動的發生概率，以活動的行為約束為基礎，能夠給出數值化的度量結果。該方法避免了現有方法僅從控制流層面度量一致性的缺陷，而是從控制流和數據流2個層面研究BPEL過程一致性，使得度量結果符合用戶的預期評判。并且實現了自動計算一致性的原型工具。案例分析驗證了提出的方法的可行性和有效性。

為了描述那些不存在偏序和互斥關系的活動對，在BPEL活動約束圖中引入了獨立關系的概念，但并沒有給出這種關系的嚴格定義。由于互斥關系和獨立關系是對稱的，偏序關系卻不對稱，即包含偏序關系的活動對（A1，A2）與（A2，A1）不同。為了使它們對稱，引入了反偏序關系，但這種做法是否合適值得商榷。

雖然提出了一種度量BPEL過程一致性的方法，但并不了解業務過程專家是否認可該方法，以及他們普遍認為哪一種度量BPEL過程一致性的標準更為合適。下一步將進行基于假設檢驗的實驗研究說明提出的方法的合適性。

［1］WS?BPEL 2.0 Specification［EB／OL］.［2007?05?27］.ht?tp：／／docs.oasis?open.org／wsbpel／2.0／wsbpel?v2.0.pdf.

［2］HUANG Y，HE K Q，FENG Z W，et al.Business process consolidation based on E?RSPTs'in SERVICES［C］／／Pro?ceedings of IEEE World Congress on Services.Anchorage.［S.l.］，2014：254?361.

［3］RADATZ J，GERACI A.IEEE standard glossary of software engineering terminology［S］.IEEE Std.USA，1990.

［4］SONG W，ZHANG W J，ZHANG G X，et al.Quantifying consistency between conceptual and executable business processes［C］／／Proceedings of SCC.Santa Clara Marriott，USA，2013：9?16.

［5］van der AALST W M P，BASTEN T.Inheritance of work?flows：an approach to tackling problems related to change［J］.Theoretical Computer Science，2002，270（1／2）：125?203.

［6］van GLABBEEK R J，WEIJLAND W P.Branching time and abstraction in bisimulation semantics［J］.Journal of the ACM，1996，43（3）：555?600.

［7］WEIDLICH M，MENDLING J，WESKE M.Efficient consis?tency measurement based on behavioral prof i les of process models［J］.IEEE Transaction on Software Engineering，2011，37（3）：410?429.

［8］WEIDLICH M，MENDLING J.Perceived consistency be?tween process models［J］.Information Systems，2012，37（2）：80?98.

［9］ALVES DE MEDEIROS A K，van der AALST W M P，WEIJTERS A.Quantifying process equivalence based on ob?served behavior［J］.Data and Knowledge Engineering，2008，64（1）：55?74.

［10］ZHANG X W，SONG W，XING J C，et al.Behavioral con?sistency measurement and analysis of WS?BPEL processes［C］／／Proceedings of the 14th WAIM.Beidaihe，China，2013：619?630.

［11］SONG W，MA X X，CHEUNG S C，et al.Refactoring and publishing WS?BPEL processes to obtain more partners［C］／／Proceedings of ICWS.Washington DC，USA，2011：129?136.

［12］XING J C，ZHANG X W，SONG W，et al.BPEL Similari?ty-a metric based on activity constraint graphs［C］／／Pro?ceedings of the 1st AP?BPM.Beijing，China，2013：39?55.

Consistency measurement of BPEL processes

ZHANG Xuewei1，XING Jianchun1，SONG Wei2，WANG Hongda1，HAN Deshuai1

（1.College of National Defense，PLA University of Science and Technology，Nanjing 210007，China；2.Department of Computer Sci?ence and Engineering，Nanjing University of Science and Technology，Nanjing 210094，China）

Service composition and cloud computing as an effective manner for resource integration and application of interconnection make variants of business process execution language（BPEL）process which describes Web serv?ices increase rapidly.The research on the consistency of BPEL processes is significant to integration of variants and detection of differences between variants.However，existing approaches either only resulted in a binary answer or presented the quantitative results at the level of control flow，which resulted in that the measurement results did not conform to the intuition of users.Therefore，this paper proposes a new approach that quantitatively measures behav?ioral consistency between BPEL processes.It is based on behavioral constraint between activities and the weight of probability of activity occurrence in event logs.A software tool was implemented to automatically calculate consis?tency degree of BPEL processes.By analyzing consistency of six pairs of BPEL processes，the experimental results verify the feasibility and effectiveness of the proposed approach，and conformity to the intuition of users.

BPEL processes；activity constraint graph；event log；consistency measurement

10.3969／j.issn.1006?7043.201402023

：A

：1006?7043（2015）06?0814?07

http：／／www.cnki.net／kcms／detail／23.1390.u.20150520.0851.001.html

2014?02?24.網絡出版時間：2015?05?20.

國家自然科學基金資助項目（61202003）；國家重點基礎研究發展規劃資助項目（2015CB352202）；武漢大學軟件工程國家重點實驗室開放基金資助項目（SKLSE2012?09?05）.

張學偉（1988?），男，博士研究生；邢建春（1964?），男，教授，博士生導師.

張學偉，E?mail：zxwlucky＠163.com.