精细化的BPEL程序数据竞争动态检测方法

鲁伟娜，鲁法明+，包云霞，曾庆田，段 华

(1.山东科技大学 计算机科学与工程学院，山东 青岛 266590;2.山东科技大学 数学与系统科学学院，山东 青岛 266590)

0 引言

随着Web服务技术的日益成熟和复杂业务需求场景的不断涌现，Web服务组合在面向服务的架构(Service-Oriented Architecture, SOA)领域得到广泛应用，作为服务组合主要技术手段的业务流程执行语言(Business Process Execution Language, BPEL)成为研究与应用的热点之一。与很多传统的并行编程技术类似，BPEL程序容易出现数据竞争、死锁、原子性违背等并发缺陷和漏洞[1-4]，这些漏洞通常难以检测、调试和修复，导致程序不能正常运行甚至崩溃而引发严重事故，例如2003年美国东北部大停电事故就与程序并发漏洞相关[5]。程序并发漏洞的检测和排除是并发系统设计的一大挑战，而数据竞争在并发漏洞中占有较大比例[6]，且通常为引起原子性违背和顺序违背等其他并发缺陷的根本原因[2,6]，因此本文围绕BPEL程序的数据竞争检测问题展开研究。

数据竞争指对同一块存储空间存在并发访问，而且至少有一个访问为写操作。数据竞争会严重影响系统性能，甚至导致系统崩溃而造成经济损失[7-12]，例如Therac-25放射治疗设备事故[7]、纳斯达克的Facebook故障[8]等。由于程序调度的不确定性以及共享存储空间访问控制的复杂性，数据竞争检测存在一定难度。目前，常见的数据竞争检测方法总体上分为静态检测和动态检测两类[13]。静态检测方法针对程序源代码进行分析，能够覆盖程序可能出现竞争的所有源码路径，查全率较高，然而由于缺少程序运行时的信息，导致数据竞争的误报率较高；动态检测方法监视程序执行过程中的内存访问和同步操作，通过运行轨迹收集必要的程序行为信息来判断构成数据竞争的操作，能充分利用某次执行过程中的运行信息，误报率较低，然而受限于并发分支执行交错不确定及所收集信息不完整，该方法存在较多漏报。由于具有高效、低误报率等特性，数据动态竞争检测受到研究界的广泛关注[14-15]，本文在保证低误报率的前提下提出一种新的降低漏报率的BPEL程序数据竞争动态检测方法。

数据竞争的前提是针对同一块存储空间的两个访问操作能够并发执行，且至少有一个访问操作为写操作。数据竞争检测方法一般通过排除操作间的互斥和因果关系来判定它们之间是否能够并发从而导致数据竞争。例如，基于LOCKSET[16-18]的数据竞争检测方法维护程序执行过程中并发分支的当前持有锁信息，当共享变量不受锁保护、不能保证互斥访问时报告数据竞争错误。该方法速度快、开销低，但未考虑读写操作之间可能存在的因果关系，因此报告的潜在竞争可能存在大量误报。FLANAGAN等[19]和KRALL等[20]提出基于HB(happens-before)关系进行数据竞争动态检测的方法。HB关系是并发程序执行时所有事件间的一种偏序关系，其借助逻辑时钟识别操作间的各种因果依赖关系，并将锁对象导致的操作间互斥关系处理为因果约束(约定轨迹中先执行的锁释放操作与其后执行的该锁的获取操作存在因果依赖)。然而，上述对互斥关系的处理并不恰当，由于调度顺序不同，多个并发分支对同一锁对象的访问操作可能存在不同的执行顺序。HB关系仅根据某一条轨迹中的执行顺序就固化不同分支间锁操作的因果关系，丢失了许多潜在的程序行为，带来了数据竞争漏报。针对上述问题，很多工作弱化HB关系对程序行为的约束以减少漏报，例如，SMARAGDAKIS等[21]提出的基于CP(causally-precedes)关系的数据竞争检测方法、KINI等[22]提出的基于WCP(weak-causally-precedes)关系的数据竞争检测方法等，能在一定程度上减少漏报。

然而，上述各类数据竞争检测方法均将操作间的互斥关系处理为因果约束，仅根据轨迹中的操作顺序就限定一些原本可能并不存在的因果约束，导致程序行为信息丢失，引起数据竞争的漏报。针对该问题，数据竞争预测[23-26]的概念被提出。数据竞争预测也是从分析程序运行轨迹出发，但允许对不同并发分支的操作进行重排，可分析更多潜在的程序运行轨迹，从而减小数据竞争的漏报率。例如，DONALDSON等[27]提出基于WDC(weak-doesn’t-commute)关系的数据竞争预测方法，该方法删除了之前一些方法中存在的的过强的因果约束，同时借助向量时钟检测数据竞争，但会添加一些程序语义中原本并不存在的因果约束，仍会导致数据竞争漏报。

前述各类数据竞争检测和预测方法广泛应用于C，C++，Java多线程程序分析，随着Web服务技术的产生和普及，学者们开始将其用于分析BPEL程序的数据竞争。由于BPEL独有的一些语法和语义特性(如flow、link机制和死路径消除等)，需要对前述各类检测方法进行部分调整。例如，CHEN等[28]提出一种基于图理论的检测方法，将BPEL流程转化为BPEL分段图，借助BPEL分段图中节点的可达性确定因果依赖关系，排除因果关系之后认定节点间的并发性，以此进行数据竞争检测。YANG等[29]提出一种静态分析和动态监控相结合的数据竞争检测方法，通过一个修改后的ActiveBPEL引擎监控变量访问事件，并将变量访问事件及其他各种BPEL活动关联到一个并发分支中，然后将BPEL程序转换为一种PPEL分段图，再通过图中节点间的可达性和所属分支情况判定对应活动间是否存在并发关系。这两种方法在检测数据竞争时未考虑BPEL中isolated scope对共享变量访问所起的类似锁机制的访问控制作用，也没有考虑死路径消除等BPEL语义对程序行为的影响。LI等[30]将flow对应到多线程程序的fork和join操作，将flow中子活动对应的并发分支视作一个线程，将link对应到多线程程序的wait和post操作，利用锁的互斥性质建模isolated scope代码片段，将BPEL程序转换为一种粗粒度的BPEL控制流图，并提出一种结合发生序和锁集的BPEL数据竞争检测方法。然而该方法为静态检测方法，流程中link的真实状态和死路消除信息只有在运行中才会获得，因此在检测过程中可能会发生误报。HU[31]提出一种预测性的BPEL数据竞争动态分析方法，较完整地提出了BPEL程序中与并发相关的各种约束模型,包括HB序关系约束、link约束、锁约束和读写约束等，取得了较好的检测效果。然而，类似于多线程程序持有锁的前提下启动新并发分支会导致一些复杂的因果依赖，BPEL程序中存在一些isolated scope与flow，link耦合情境下导致的活动间因果关系(见第2章实例)，前述方法均不能正确处理。

无论多线程程序的数据竞争检测方法，还是BPEL数据竞争的检测和预测方法，产生漏报或误报的根源均为对活动间各种依赖关系的识别不够准确，对互斥关系的处理不够合理。为解决这一问题，本文一方面将BPEL活动间可能存在的因果关系细分为并发块内因果依赖、并发块间因果依赖、LINK因果依赖和IS-LINK耦合因果依赖关系，针对每种因果依赖关系给出相应的识别方法；另一方面，对BPEL锁机制引起的互斥关系进行更为准确地建模，以分析更多潜在的执行轨迹。在此基础上，给出一种更加完整而精细的BPEL程序数据竞争动态检测和预测方法，在一定程度上既保证了较低的误报率，又降低了数据竞争的漏报率。

1 实例与动机分析

本章结合一个BPEL程序的运行轨迹实例，结合前文提到的数据竞争动态检测方法和HU[31]提出的BPEL数据竞争预测性分析方法对其进行分析，指出现有方法的不足，给出本文的研究动机和思路。BPEL程序可以看作一个活动的序列，活动类型包括基本的赋值活动assign、请求活动invoke、消息接收活动receive、应答活动reply等，也包括结构化活动flow，sequence和特殊活动scope，correlations等。sequence用于定义顺序结构，其内嵌的活动必须按顺序执行；flow用于定义并行结构，其内嵌的活动具有并发关系，可并发执行，执行顺序也不确定。可以在flow内部嵌入多个sequence结构，每个sequence结构或每个独立的并发活动都相当于一个线程，将其称为一个并发块，也可以在flow内部通过link声明link源活动和目标活动的因果关系。scope一方面用于为嵌套在其中的活动提供统一的故障处理功能和补偿处理功能；另一方面，当scope活动的isolated属性被设置为yes时，提供并发情况下对共享变量等资源的互斥访问控制，以保证共享数据的一致性。实际上，可认为存在一个全局的互斥锁MUTEX，一旦进入isolated scope便可认为该锁对象被相应的并发块持有，退出isolated scope时认为MUTEX被释放。

通过对BPEL引擎的插桩操作[31]可得类似图1所示的BEPL程序运行轨迹。其中，ISLock表示进入一个isolated scope事件,ISUnlock表示退出一个isolated scope事件，两者分别对应全局锁对象MUTEX的获取和释放操作；有向弧link两端的活动LinkSrc和LinkTarget分别对应link的源活动与目标活动；AssignTo表示对某个BPEL变量的写操作,AssignFrom表示对某个BPEL变量的读操作；轨迹中各事件所对应的并发块ID以及各事件的生成规则在2.1节给出。

根据图1所示的BPEL程序运行轨迹，两个并发块关于变量x的赋值操作不会发生数据竞争，因为link约束要求并发块CB1必须先进入isolated Scope执行link源活动后CB2的link目标活动才能执行。又因isolated scope的互斥关系，在不发生死锁的前提下，必须在CB1退出isolated scope区域后CB2才能进入并执行后续x的赋值操作，而CB1对x的赋值操作在退出isolated scope之前已经完成，因此两者不可能并发。然而，基于WDC关系的数据竞争检测方法仅能识别link活动导致的LinkSrc(CB1,AtoB)与LinkTarget(CB2,AtoB)之间的因果关系，从而错误地判定AssignTo(CB1,x)与AssignTo(CB2,x)会并发，由此给出一个数据竞争误报。另外，即便文献[31]考虑isolated scope引起的互斥关系，也会因AssignTo(CB2,x)执行时未持有锁而无法排除并发，故仍然存在上述的数据竞争误报。

上述各类数据竞争漏报和误报的根源在于已有检测方法对操作间因果和互斥关系的识别不够准确，为此，本文在综合分析上述实例的基础上，对BPEL程序执行轨迹中操作之间的关系进行精细划分。具体的关系分类和定义如下：

定义1给定一个BPEL程序的运行轨迹σ=e1e2e3…en,事件e对应的并发块ID记作#CB(e),事件之间的依赖关系定义如下：

块内相继、块间相继、LINK相继和IS-LINK耦合相继关系统称为相继关系，记作ei→ej。

(5)设ei为位于某isolated scope中的一个事件，ej为位于另一个isolated scope中的事件，且#CB(ei)≠#CB(ej)，则称两者之间具有隔离区互斥关系，记作ei◇ej。

以图1中的BPEL运行轨迹为例，根据定义1检测到事件ISUnlock(CB1, MUTEX)与LinkTarget(CB2, AtoB)存在IS-LINK耦合相继关系，考虑到AssignTo(CB1,x)需要先于前者执行(两者具有块内相继关系)，而AssignTo(CB2,x)需要在LinkTarget(CB2,AtoB)之后执行(通过多次块内相继关系传递可得两者之间的因果依赖)，AssignTo(CB1,x)需先于AssignTo(CB2,x)执行，由此可排除这两个事件并发的可能性，进而排除其构成数据竞争的可能。

下面给出由程序运行轨迹分析挖掘上述各种关系的方法。

2 BPEL运行轨迹与因果关系挖掘

本章首先给出BPEL程序运行轨迹的生成方法，然后给出由运行轨迹挖掘和识别BPEL程序操作间各类因果关系的判定方法。

2.1 BPEL基本概念及其运行轨迹

BPEL是一种用来描述业务流程的编程语言，其中的活动分为基本活动和结构性活动。基本活动用于执行一定的操作，如赋值活动assign、调用伙伴服务活动invoke、消息接受活动receive和应答活动reply等。结构化活动用于嵌套各种基本活动或结构性活动，如活动sequence，flow等，其中sequence用于定义顺序结构，其内嵌的活动须按顺序执行；flow用于定义并行结构，其内嵌的活动可并发执行，执行顺序不确定。flow内部可以嵌入多个sequence结构或者独立的并发活动，还可以通过link声明link源活动和目标活动之间的因果关系。每个flow内部的sequence结构或并发活动都相当于一个线程，称为一个并发块。

图2所示为一个简化的网上购物支付金额计算的BPEL流程实例，各活动右上角数字为该活动所属并发块的ID。其中，main为一个sequence活动，对应流程的开始；receiveInput为一个receive活动，等待订单消息的到来；收到订单消息后启动一个flow活动并创建两个sequence结构的并发块。图中左侧的并发块首先执行活动AssignDiscount，将折扣率初始化为1；然后进入一个isolated scope，先调用活动InvokeCostSum计算订单总额，之再根据总额大小调用InvokeDiscount更新折扣率。图中右侧的并发块首先为消费者提供VIP注册服务AssignVIP，然后调用InvokeVipDiscount活动进一步将折扣率更新为原折扣率的80%。因为仅当用户订单总额超过阈值1 000后才提供VIP注册服务，所以在活动InvokeCostSum与AssignVIP之间存在一个link连接。完成上述各活动后flow活动结束，AssignFinalResult根据最终的折扣信息计算最终支付金额，replyOutput返回最后的计算结果。

下面结合图2中的BPEL流程实例，给出各活动所属并发块ID的设定方法以及BPEL程序运行轨迹的生成规则。

根据BPEL流程可扩展标记语言(Extensible Markup Language, XML)文档定义中活动节点所属层级结构逐个设置其所属并发块的ID，规则如下：

(1)约定流程内所有一级节点同属于一个并发块，并设该并发块的ID为0。

以图2中的BPEL程序为例，第一级活动节点为sequence结构化活动main，置其并发块ID为0，即#CB(main)=0。

(2)设置一个全局的并发块个数计数器CBCount，并初始化为0。然后，按XML流程定义文档中节点的层级顺序(按层级顺序遍历XML文档的过程反映到流程图上时需忽略 link活动对应的有向弧)遍历各个活动，一旦遇到一个flow活动，就将该flow活动的并发块ID设为其父节点的并发块ID；另外，设其内嵌的一级子活动有n个，将这些子活动的并发块ID分别设置为CBCount+1,CBCount+2,…,CBCount+n，然后令CBCount:=CBCount+n。其他情况下，将当前遍历节点的并发块ID设置为其父节点的并发块ID。

仍以图2中的BPEL程序为例，结构化活动main的一级子活动包括receiveInput，AssignFinalResult，replyOutput，它们均非flow活动，故其并发块ID设置为父节点main的并发块ID，即将其并发块ID均设置为0。至于main包含的flow活动，因为其含有两个一级子活动(均为sequence活动)，所以将两个sequence的并发块ID分别设置为1和2。遍历到AssignDiscount活动时，将其并发块ID设置为其父节点sequence的并发块ID，其余各个节点所属并发块的ID类似可得，最终各活动所属并发块ID的计算结果见图2中各活动节点右上角的数字。

借助BPEL流程引擎的日志系统接口对BPEL源程序进行插桩处理[31]，捕获程序执行过程中与数据竞争相关的操作生成相应的事件日志，具体规则如表1所示。以图2中的BPEL程序为例，其一个可能的运行轨迹如表2所示。

表1 BPEL程序操作对应的事件信息

表2 计算网上购物支付金额的BPEL程序运行轨迹实例

续表2

根据上述BPEL程序的并发块识别规则和事件日志生成规则，可得如下BPEL程序运行轨迹的形式化定义：

定义2事件序列σ称为一个BPEL程序的运行轨迹：

σ::=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为并发块的集合；BPEL_Var为BPEL变量的集合；MUTEX为一个全局的互斥锁。各个事件的含义如表1所示。

2.2 基于逻辑时钟的因果关系挖掘

本文借助逻辑时钟识别BPEL程序运行轨迹中各事件之间的因果依赖关系，下面给出逻辑时钟相关的定义和符号。

定义3在BPEL程序执行的任意时刻，为每一个并发块CB绑定一个整数形式的逻辑时钟c∈N，称CB@c为一个并发块的纪元，并约定其初始最小纪元为CB@0，记作⊥CB；称某时刻下所有并发块的纪元构成的向量为BPEL程序的向量时钟，记作V。初始状态下BPEL程序的最小向量时钟满足∀CB∈ConcurrentBlock:V(CB)=CB@0，记为⊥V。并发块纪元和向量时钟的相关运算规则如下：

(1)并发块纪元比较CB@c1

(2)并发块纪元求最大值 max(CB@c1,CB@c2)=CB@max(c1,c2)。

(3)并发块纪元递增CB@c+1=CB@(c+1)。

(4)并发块纪元投影getID(CB@c)=CB。

(5)向量时钟求最大值V1∪V2=λCB∈ConcurrentBlock:max(V1(CB),V2(CB))。

(6)向量时钟递增incCB(V)=λCB′∈ConcurrentBlock:ifCB′=CBthenV(CB′)+1 elseV(CB)。

(7)并发块纪元与向量时钟比较CB@cViffCB@c

以表2中的运行轨迹为例，初始情况下BPEL程序的向量时钟为〈B1@0,B2@0,B3@0〉(在不引起歧义的情况下，可省略向量时钟中各并发块的ID和@符号，如〈B1@0,B2@0,B3@0〉简记为〈0,0,0〉)。随着运行轨迹中各操作的顺序执行，每发生一个事件，就根据事件的种类和属性更新各个并发块的纪元以及程序的向量时钟信息，并根据其进行数据竞争检测。为此，首先给出由BPEL程序运行轨迹挖掘操作间因果关系的方法，本质上是通过识别事件之间的块内相继、块间相继、LINK相继和IS-LINK耦合相继关系，借助向量时钟运算推导事件间的因果依赖关系。

为完成上述任务，一方面，为每个事件设置一个属性isISLocked，标注其是否在一个isolated scope中(可理解为是否持有锁MUTEX，初值为FALSE)；另一方面，对任意一个并发块B，为其设置如下3个向量时钟相关的数据对象：

(1)并发块局部向量时钟 记作Vself，BPEL每执行一个操作后都针对其所属并发块更新向量时钟，记录该操作执行完毕后并发块所能处于的最小全局时间向量；在未执行任何操作的初始状态下，初始化其值为⊥V。

(2)并发块的link源活动向量时钟元组集 记作VLinkSrc，是一个二元组集合，每个元组形如(linkName,Vself)，表示当前并发块执行了linkName的源活动，且该源活动执行后并发块的局部向量时钟为Vself，初始状态下VLinkSrc为一个空集。

(3)并发块的“IS-link目标活动”向量时钟元组集 记作VIS-LinkTarget，集合中的每个元组形如(linkName,Vself)，表示曾经有并发块在某个isolated scope中执行了linkName的源活动，而且该并发块退出isolated scope时的向量时钟值为Vself，初始状态下VLinkSrc与VIS-LinkTarget均为一个空集(当并发块尚未退出isolated scope时约定Vself中各个分量均为-1)。

对BPEL运行轨迹中的每个事件，根据事件类型及相关属性信息，若其有可能导致并发块之间存在时序依赖，则按一定规则更新其所属并发块的局部向量时钟、LINK源活动向量时钟元组集、“IS-link目标活动”向量时钟元组集；至于AssignTo，AssignFrom以及InvokeInput，InvokeOutput等BPEL变量的读写操作，它们不会引起跨并发块的时序依赖，从而不会更新向量时钟。设一个事件执行前各个并发块向量时钟相关数据对象处于状态S,事件执行后的状态记作S′，并记状态S下并发块B的局部向量时钟为SB.Vself,link源活动向量时钟元组集、“IS-link目标活动”向量时钟元组集分别为SB.VLinkSrc和SB.VIS-LinkTarget。表3所示为针对表2中的BPEL程序运行轨迹逐步更新相关向量时钟信息的一个实例，下面结合该实例说明向量时钟的更新规则及其含义。

表3 并发块局部向量时钟、LINK源活动/IS-link目标活动向量时钟元组集更新实例

以表3中的事件e13:FlowJoin(0;1,2)为例，该操作执行前并发块0，1，2的局部向量时钟分别为1,0,0，1,3,0，1,3,3，故后继状态中并发块0的局部向量时钟更新为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)为例，操作执行前并发块1的局部向量时钟值均为1,0,0，执行e3后并发块1的局部向量时钟递增为

(5)ISUNLOCK规则 当并发块B0执行操作ISUnlock(B0,MUTEX)时,若该并发块的link目标活动向量时钟元组集B0.VIS-LinkTarget为空，或者其中所有元素的向量时钟均不为-1,…,-1(意味着当前isolated scope中不存在link源活动)，则该操作不与其他并发块的活动产生依赖关系，只需将当前并发块的局部向量时钟递增为其他并发块的向量时钟保持不变。另外，需将全局变量isISLocked更新为FALSE。记该规则为

以表3中的事件e10:ISUnlock(2,MUTEX)为例，该操作执行前并发块2的IS-link目标活动向量时钟元组集为空，当前隔离区中不存在源活动，只需将并发块2的局部向量时钟1,4,2更新为1,4,3。

(6)ISUNLOCK～LINK规则 当并发块B0执行操作ISUnlock(B0,MUTEX)时,若并发块的IS-link目标活动向量时钟元组集中包括形如(linkName,-1,…,-1)的元素(意味着当前isolated scope中存在link源活动)，则该操作可能会与linkName的目标活动产生时序依赖。为此，除了将B0的局部向量时钟递增为并保持其他并发块的局部向量时钟保持不变外，应将B0的IS-link目标活动向量时钟集中形如(linkName,-1,…,-1)的元素更新为(linkName,incB0(SB0.Vself)),未来执行linkName目标活动时，若处于一个isolated scope中，则linkName目标活动执行后的局部向量时钟值需要与(linkName,incB0,(SB0.Vself))取最大值。另外，需将全局变量isISLocked更新为FALSE。记该规则为

以表3中的事件e7:ISUnlock(1,MUTEX)为例，并发块1的局部向量时钟从〈1,2,0〉递增为〈1,3,0〉。另外，因该并发块的IS-link目标活动向量时钟集中存在元素(AtoB,-1,-1,-1)，当前isolated scope中存在link源活动，需将(AtoB,-1,-1,-1)更新为(AtoB,-1,-1,-1∪1,3,0)=(AtoB,1,3,0)，未来AtoB的目标活动若位于一个isolated scope，则必须在该时刻之后才能执行。

以表3中的事件e9:LinkTarget(2,AtoB)为例，该操作执行时并发块处于isolated scope中(isISLocked=TURE)，且B1.VIS-LinkTarget中存在元组(AtoB,1,3,0)，由此可知存在IS-LINK耦合相继关系，故将该事件执行后的局部向量时钟更新为incB2(SB2.Vself)∪1,3,0=incB2(1,0,1)∪1,3,0=1,3,2。另外，该IS-LINK耦合相继关系处理完毕，故将(AtoB,1,3,0)从IS-link目标活动向量时钟元组集中删除，并将(AtoB,1,2,0)从B1.VLinkSrc中删除。

以表3中的事件e9:LinkTarget(2,AtoB)为例，若e10的发生顺序调整到其前，则该操作执行时不持有锁MUTEX，这种情况下不存在IS-LINK耦合关系，又易见link源活动向量时钟元组集中存在二元组(AtoB,1,2,0)，故在e9结束后将向量时钟更新为incB2(SB2.Vself)∪1,2,0，同时从B1.VLinkSrc中将(AtoB,1,2,0)删除。

根据上述规则，可得表1中各并发块局部向量时钟、link源活动向量时钟元组集和IS-link目标活动向量时钟元组集的计算与更新过程。其中，同一并发块内操作间的实线有向弧表示块内相继关系，不同并发块间的虚线有向弧表示其之间的块间相继、LINK相继和IS-LINK耦合相继关系。

对于同一并发块内的两个事件，为刻画块内因果依赖关系，每执行一次FlowFork，FlowJoin，ISLock，ISUnlock，LinkSrc，LinkSrc这些会导致并发块间时序依赖的事件，就将局部向量时钟内该并发块所对应维度的分量递增1，从而通过比较这两个事件局部向量时钟中其所属并发块分量的大小得到块内因果关系。例如，事件e3:ISLock(1,MUTEX)与e5:LinkSrc(1, AtoB)具有块内相继关系，相应地，e3执行前局部向量时钟1,0,0对应并发块B1的分量为0，其严格小于事件e5执行后局部向量时钟1,2,0所对应B1的分量2。需要注意的是，由于AssignTo，AssignFrom以及InvokeInput，InvokeOutput等变量读写操作不会引起跨并发块的时序依赖，约定共享变量的读写不造成线程局部向量时钟递增。例如，表1中，事件e4:AssignFrom(1,cost)在执行前后的局部向量时钟均为1,1,0。

基于上述分析，任意两个事件ei和ej均可基于对应的向量时钟分析其因果依赖关系。然而，即使能判定不存在因果关系，它们仍可能是并发的，因为也可能存在互斥关系。例如，事件e3:ISLock(1,MUTEX)执行前局部向量时钟1,0,0对应B1的分量0，不小于事件e8:ISLock(2,MUTEX)执行后局部向量时钟1,0,1对应B1的分量0，故两者之间不存在因果依赖关系，但其之间因isolated scope的隔离区互斥关系导致无法并发。对同一BPEL变量的两个读写/写写操作，仅当其既不具备因果关系，也不具备隔离区互斥关系时，才可认定其并发而导致数据竞争，下面给出具体的数据竞争检测过程和更多检测实例。

3 BPEL数据竞争检测

第2章给出了两个事件间因果关系的挖掘方法，针对同一个BPEL变量的两个读写/写写事件，若其属于不同并发块、不具备所挖掘到的各类因果关系，而且这两个事件执行前的isISLocked属性取值不同时为TRUE(不同时位于isolated scope中，意味着不具备隔离区互斥关系)，则可认定两者构成数据竞争。以表3为例，事件e6:AssignTo(1,disc)是对disc的写操作，e11:InvokeInput(2,disc)是针对BPEL变量disc的读操作，两者属于不同的并发块，且两者执行前的isISLocked属性不同时为TRUE，然而e6执行前局部向量时钟1,2,0对应并发块B1的分量为2，小于e11执行后局部向量时钟1,3,3对应B1的分量3，因此两者具有因果关系，不构成数据竞争。

为提高数据竞争检测的效率，本文并非对每一个共享变量的两个读写/写写操作逐一进行数据竞争检测，而是为每一个BPEL共享变量分别维护读事件、写事件信息表。表4以变量disc为例给出读写事件信息表示例，表中每个元素为一个形如(B,isISLocked,V)的三元组，B为当前读/写事件所属的并发块，isISLocked为描述当前事件是否处于isolated scope的布尔值，V为读/写事件执行后的局部向量时钟。初始情况下，各个变量的读写事件信息表均为空；然后，每遇到一个针对变量x的AssignTo或InvokeOutput操作，均向Sx.W中添加一个三元组(B,isISLocked,V)，每当遇到一个针对变量x的AssignFrom或InvokeInput操作，就向Sx.R中添加一个三元组(B,isISLocked,V)，其中B，isISLocked，V的含义如前所述；另外，每添加一个新的三元组，都按如下两种规则进行数据竞争检测：

(1)RACE-W规则 当遇到一个针对变量x的写操作时，假设其对应的三元组为t，则检查x当前对应的读/写事件列表中是否存在三元组t′满足如下条件，若存在，则t与t′对应的操作构成一对数据竞争。

∃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表示两个操作分属于不同的并发块(排除块内因果)；t.isISLocked=FALSE∨t′.isISLocked=FALSE表示两个操作不能都位于isolated scope中(排除互斥关系)；t′.V(t′.B)≥t.V(t.B)表示两个操作不具备块间相继、LINK相继或IS-LINK耦合相继导致的块间因果关系。

(2)RACE-R规则 当遇到一个针对变量x的读操作时，假设其对应的三元组为t，则检查x当前对应的写事件列表中是否存在三元组t′满足如下条件，若存在，则t与t′对应的操作构成一对数据竞争。与RACE-W规则相比，唯一的不同是，本规则要求三元组t′对应变量x的一个写操作。

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

(t.isISLocked=FALSE∨t′.isISLocked

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

表4 共享变量读/写操作信息表与数据竞争检测实例

续表4

以表4中的事件e12为例，该事件是针对变量disc的一个写操作，对应的写事件信息三元组为(2,FALSE,1,3,3)。在disc的写事件信息表中，所有其他两个三元组均对应并发块B1，其向量时钟中对应B1的分量均小于e12向量时钟中对应B1的分量3；而且，disc的读事件信息表只有一个三元组(2,FALSE,1,3,3)，其与e12同属一个并发块。由此可见，RACE-W规则不满足，故该操作不与之前的操作构成数据竞争。类似地，表3中所有的变量读写操作都不存在数据竞争。

表4中运行轨迹的分析过程与第2章对图1中运行轨迹的分析过程类似，基于WDC的数据竞争检测方法仅能识别link源活动e5:LinkSrc(1,AtoB)与目标活动e9:LinkTarget(2,AtoB)之间的因果关系，从而错误地判定e6:AssignTo(1,disc)与e12:AssignTo(2,disc)能并发，导致误报数据竞争。相比而言，如上述检测过程所述，本文方法能识别出两者之间真实存在的因果关系，从而避免误报。

再以表5中的BPEL程序运行轨迹为例，基于WDC的数据竞争检测方法会认为e5与e7之间存在因果关系，而e4要先于e5执行，e5要先于e9执行，由此判定e4与e9之间存在因果关系，从而漏报e4与e9间的数据竞争。类似地，基于HB的数据竞争检测方法会认为e5与e6之间存在因果关系，由此也错误地认定e4与e9之间存在因果关系，导致漏报数据竞争。本文方法则不会出现这种漏报现象，它能检测到事件e9:AssignTo(2,y)与e4:AssignTo(1,y)之间存在数据竞争，原因是：①两者分属于不同并发块；②两者之一e9没有位于isolated scope中；③e4执行前局部向量时钟对应并发块2的分量为1，不小于e9执行后局部向量时钟对应并发块2的分量0。由此可知满足RACE-W规则，e4与e9构成数据竞争。

表5 数据竞争检测实例

续表5

由表3与表5所示的两个BPEL程序数据竞争动态分析实例可见，相比以往基于HB，WDC等关系的数据竞争动态分析方法，本文方法能排除更多误报，而且部分情况下会减少漏报。究其原因，本文对IS-LINK耦合相继关系导致的因果依赖进行了准确界定和识别，而且借助分析isISLocked属性规避了已有动态分析方法将互斥关系建模为因果约束的不足。

4 相关工作对比

结合文献[28,30-32]给出的BPEL程序实例，对比了本文方法和相应参考文献方法的检测结果。对比结果显示，对文献[30]给出的购书订单流程、文献[32]的订单处理流程、文献[28]的客户订单处理流程和文献[31]的订单金额处理流程，本文方法均能准确检测出流程中存在的数据竞争，不存在误报或漏报现象。而对于本文给出的网上购物支付金额计算的BPEL流程，当以表4中的运行轨迹为输入进行数据竞争检测时，文献[32]中基于XML节点树分析的方法会有2处误报，文献[28]基于可达性分析的方法有1处误报，文献[31]的动态检测方法有1处误报；当以其表6中的运行轨迹为输入进行数据竞争检测时，文献[30]的方法有1处漏报，文献[28，32]的方法各有1处误报。另外，用基于HB关系的数据竞争检测方法对表6中的运行轨迹进行分析时会存在1处漏报，用基于WDC关系的数据竞争检测方法对表4中的运行轨迹进行分析时会有有2处误报。相比之下，本文方法能在保证准确率的同时降低误报率。究其原因，上述文献中的数据竞争动态检测方法对因果关系的建模不够精确，且将互斥关系处理为因果约束，会导致多种数据竞争误报或漏报。而本文对BPEL活动间的因果关系进行更加精确地划分，基于逻辑时钟给出了细分后各种因果关系的识别方法，并联合向量时钟和全局互斥锁对BPEL程序中活动间的互斥关系进行准确建模，在一定程度上降低了数据竞争的误报率和漏报率。

然而，本文方法相比已有方法也有一定不足，link源活动向量时钟元组集、IS-link目标活动向量时钟元组集和BPEL变量读/写操作信息表的引入使本文所提数据竞争检测方法会消耗更多的时间和空间，但是额外时间和空间复杂度比WDC等方法增加有限，增加的规模与并发块数量、BPEL变量读写操作的数量以及轨迹长度为线性关系。具体而言，WDC和DC有相同的时间复杂度O(N×(L×T+T2))(N，L，T分别表示事件、锁和线程的数量)，最坏情况下的空间复杂度为Ω(N)。本文所提方法的时间复杂度为O((N+l)×n)，空间复杂度为Ω((T2+l+N)×n)(N，l，T分别表示读写操作变量、link操作和线程数量)。

5 结束语

为更准确地对BPEL程序的数据竞争进行动态检测，本文将BPEL活动间可能存在的因果关系细分为并发块的块内依赖、块间依赖、LINK依赖和IS-LINK耦合依赖，针对每种因果依赖关系给出了基于向量时钟的相应识别方法，以减少基于HB，WDC关系的传统数据竞争检测方法存在的部分误报现象；另外，抛弃以往动态分析将锁集互斥关系建模为因果依赖的常规作法，通过联合向量时钟和全局互斥锁对BPEL锁机制引起的隔离区互斥关系进行了更加准确地建模，为分析更多潜在执行轨迹和数据竞争预测提供了可能，同时减少了对数据竞争的漏报。

相比传统的数据竞争动态检测方法，本文给出一种更加准确的BPEL程序数据竞争动态检测和预测方法，虽然在一定程度上降低了数据竞争的误报率和漏报率，但是以牺牲更多空间和时间维护处理link源活动向量时钟元组集、IS-link目标活动向量时钟元组集和BPEL变量读/写操作信息表等数据对象为代价。另外，本文工作仍存在一些不足。首先，本文仅从单一BPEL程序运行轨迹出发分析潜在的数据竞争，未能充分利用程序代码或其他更多轨迹信息，难以避免地出现漏报数据竞争的情况；其次，本文未考虑BPEL中存在的wait等活动对数据竞争检测的影响。后续工作将对这些问题展开进一步研究，期望将该方法拓展到多线程程序等更一般化的并行程序数据竞争检测领域。