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.