孙昌爱 王 真 潘 琳

1(北京科技大学计算机与通信工程学院 北京 100083)2 (宇航智能控制技术重点实验室 北京 100854)

面向服务的架构(service-oriented architecture, SOA)已经成为分布式应用程序的主要开发范式[1].由于单一的Web服务提供的功能有限，无法满足复杂需求，因此需要将多个服务组装以实现复杂的业务流程.WS-BPEL(business process execution language for Web service)是一种基于XML的服务组装语言[2]，可以将多个不同的Web服务编制起来实现复杂的业务流程.由于被组装的Web服务的动态性、松耦合性、不确定性以及互联网环境的开放性，如何保证WS-BPEL程序的可靠性成为一个挑战性问题[3].

变异测试是一种基于故障的软件测试技术[4]，具有较强的故障检测能力，广泛用于评估测试用例集的完备性和测试技术的有效性[5].然而，由于变异测试产生的变异体数量庞大、等价变异体识别困难、缺乏相应自动化支持工具等原因，变异测试难以在实际中广泛应用.在WS-BPEL变异测试方面，人们提出面向WS-BPEL程序的变异算子[6]，为WS-BPEL程序的变异测试提供基础[7].在课题组前期研究工作中[8-10]，我们提出了一种面向WS-BPEL程序的变异测试框架和支持工具，评估了变异算子的有效性和不同变异算子模拟的故障被检测的难易程度，发现了部分变异算子之间的包含关系.

在前期工作基础上，本文进一步研究如何降低面向WS-BPEL程序的变异测试的开销问题，从二阶变异测试和变异算子优先级2个方面探索面向WS-BPEL程序的变异测试优化技术.本文的主要贡献有3个方面：

1) 提出了2种面向WS-BPEL程序的变异测试优化技术，即面向WS-BPEL程序的二阶变异优化技术和基于变异算子优先级的优化技术.

2) 开发了面向WS-BPEL程序的变异测试集成化支持工具μBPEL，支持WS-BPEL程序变异测试的全过程，同时支持本文提出的变异测试优化技术.

3) 使用6个WS-BPEL程序实例验证并评估提出的优化技术的有效性.

1 相关工作

介绍变异测试优化和WS-BPEL测试相关的研究工作.

1.1 变异测试优化技术

变异测试是一种基于故障的软件测试技术[4].对待测程序P植入符合语法规则的错误，将错误版本的程序称为变异体，植入的故障类型称为变异算子.对于给定的变异体M,如果存在某个测试用例，使得P和M展现出不同的执行行为(通常为不同输出结果)，则称这个变异体M被“杀死”.如果对于任意的测试用例，P和M的执行结果均相同，则称该变异体M为等价变异体.

变异测试具有较强的故障检测能力[5]，可以产生较好的测试效果[11].然而，变异测试存在的主要不足有3个方面：1)变异体数量庞大导致的计算开销；2)等价变异体识别困难；3)缺乏自动化支持工具.人们主要从变异体选择和变异体执行2个角度研究变异测试的优化技术[5].

变异体选择优化关注如何从生成的大量变异体中选择出典型的变异体.Mathur和Wong[12]提出一种变异体随机选择方法，对Mothra系统中的22种变异算子产生的变异体，采用不同的比例随机选择变异体.该方法可以大幅度减少测试开销，同时变异评分并没有明显降低.King和Offutt[13-14]提出了一种变异算子选择方法，根据FORTRAN语言变异算子的测试有效性对其进行选择，采用选择后的变异算子能产生数目较少且更难被杀死的变异体.Hussain[15]根据测试用例的检测能力对所有变异体进行聚类分析，选择出变异体.Langdon等人[16]应用多目标方法指导生成高阶变异体，该方法可以有效地产生比一阶变异体更难检测的高阶变异体，同时产生等价变异体的概率更小，减少了测试开销.在前期工作中，我们提出一种路径感知的变异体精简方法，利用程序的结构信息设计变异体精简策略，有效地减少了变异测试的开销[17].在WS-BPEL程序的变异测试优化技术方面，我们提出一种基于包含关系的变异算子优化技术[10]，分析WS-BPEL程序的变异算子产生的变异体检测的包含关系，进行变异算子约简.

变异体执行优化关注减少变异体的执行时间，主要包括变异体检测优化、变异体变异优化和并行执行变异体优化方法[5].Krauser等人[18]提出一种基于SIMD(single instruction multiple data)计算机的并发执行变异体方法.此方法对变异体的无变异部分执行1次，变异的部分进行并发执行，有效地减少变异体执行时间.

1.2 WS-BPEL测试技术

与传统程序相比，WS-BPEL程序具有4个新特点[19]：1)WS-BPEL提供一种显式的集成机制组装Web服务，而这样的集成在传统程序中是隐式；2)WS-BPEL程序的服务可以采用不同语言实现，而传统程序中的模块通常由同一种语言实现；3)WS-BPEL程序表示为XML文件，不同于传统应用程序；4)WS-BPEL通过流(flow)活动支持并发机制、通过连接(link)支持同步机制.WS-BPEL程序的新特性，导致了WS-BPEL程序的故障类型不同于传统应用程序.

人们提出了多种面向WS-BPEL程序的测试技术.文献[20]将基于WS-BPEL描述的Web服务组装转化为扩展的着色Petri网(extended colored Petri net， ECPN)，提出了一种基于ECPN控制流和数据流结合的测试方法.针对WS-BPEL程序的并发特点，我们提出了一种面向场景的WS-BPEL测试用例生成方法[21]，并开发了相应的支持工具[22].Lee和Offutt[23]探索了将变异测试应用到Web服务测试中.Boonyakulsrirung等人[24]提出一种面向WS-BPEL的弱变异测试框架，通过牺牲变异得分来提高变异测试的效率.Estero-Botaro等人[7]使用遗传算法来获得变异体集合的子集，选择出高质量的变异体.

目前，人们已经开发了多个面向WS-BPEL程序的变异测试支持工具.Domínguez-Jiménez等人[25]开发了WS-BPEL程序变异测试支持工具GAmera，支持变异体生成、测试用例执行和测试结果统计.Boonyakulsrirung和Suwannasart[26]开发了WeMuTe，支持WS-BPEL程序的弱变异测试.在前期研究工作中，我们开发了一个面向WS-BPEL程序的变异测试框架，并开发相应支持工具[8-9]，支持变异体生成、变异测试的执行及结果分析.

2 WS-BPEL程序变异测试优化技术

从二阶变异测试和变异算子优先级2个方面，分别提出了变异测试的优化技术MuSOM和MuPri.

2.1 基于二阶变异的优化技术MuSOM

一种减少变异测试中变异体数量的方法是高阶变异体优化技术，由高阶变异体替代一阶变异体进行测试.一阶变异体指对原始程序应用一个变异算子且植入一处错误生成的变异体；高阶变异体指对原始程序植入多处错误生成的变异体.一个高阶变异体可以看成由多个一阶变异体复合而成.高阶变异体优化技术的提出基于2个推测[5]：1)执行一次M阶变异体等同于执行M个一阶变异体；2)高阶变异体比一阶变异体产生等价变异体的概率小.基于这2个推测可以看出，高阶变异体优化技术主要是通过减少待执行变异体数目和等价变异体识别开销来降低变异测试的开销.

本文提出一种面向WS-BPEL程序的二阶变异优化技术(简称为MuSOM).二阶变异体生成算法主要有3种，分别为LastToFirst，DifferentOperators，RandomMix算法[27].其中LastToFirst算法通过首尾组合2个一阶变异体的方式生成二阶变异体，生成的二阶变异体数量为一阶变异体数量的一半；DifferentOperators算法通过组合不同变异算子生成的一阶变异体生成二阶变异体，生成的二阶变异体数量不小于生成变异体最多的变异算子产生的一阶变异体的数量；RandomMix算法随机组合2个一阶变异体生成二阶变异体，生成的二阶变异体数量为一阶变异体数量的一半.3种算法的基本思想都是通过一阶变异体组合生成二阶变异体，但限制生成的二阶变异体数量的策略不同.其中，LastToFirst算法和RandomMix算法生成的二阶变异体数量相对确定(约为一阶变异体数量的50%)，而Different-Operators算法生成二阶变异体数量不确定.本文研究的WS-BPEL程序可应用的变异算子的种类较少、不同变异算子生成的一阶变异体数量不均衡，DifferentOperators算法不适用.RandomMix算法与LastToFirst算法相似，主要区别在于一阶变异体的选择次序.因此，本文采用LastToFirst算法生成二阶变异体集合.

LastToFirst算法[27]按照首尾依次组合2个一阶变异体的方式生成二阶变异体，过程如图1所示.其中，P指待测程序，M1至Mn代表待测程序P的一阶变异体，M1,n及M2,n-1等代表通过首尾依次组合2个一阶变异体生成的二阶变异体.

Fig. 1 Procedure of LastToFirst algorithm图1 LastToFirst 算法生成二阶变异体过程

MuSOM描述的二阶变异体生成步骤如下：

1) 根据给定WS-BPEL程序P生成一阶变异体，得到的变异体集合表示为M1o={M1,M2,…,Mn}.我们按照一阶变异体产生的顺序对变异体命名并编号为1～n(n为一阶变异体的总数).

2) 将M1o中的一阶变异体首尾依次组合生成二阶变异体，得到二阶变异体集合为M2o={M1,n,M2,n-1,M3,n-2,…}.具体说来，将编号为1与编号为n的一阶变异体组合得到二阶变异体M1,n，编号为2与编号为n-1的一阶变异体组合得到二阶变异体M2,n-1，将编号为3与编号为n-2的一阶变异体组合得到二阶变异体M3,n-2,以此类推，生成二阶变异体集合.当n为奇数时，将一阶变异体M(n+1)2与M(n+1)2+1组合生成二阶变异体.

2.2 基于变异算子优先级的优化技术MuPri

在变异测试中，有些变异算子生成的变异体可以被绝大多数测试用例检测(“杀死”)，有些算子生成的变异体只能被特殊的测试用例检测.若一些较难检测的变异体都能被给定的测试用例集检测，那么该测试用例集也能检测那些容易被测杀的变异体.基于以上猜想，我们从变异体执行顺序的角度，提出一种基于变异算子优先级的变异测试优化技术，首先使用可以产生较难检测变异体的变异算子，然后再使用产生较易检测变异体的变异算子.

为了评价变异算子产生的变异体检测的难易程度，引入变异算子质量度量指标.这里约定P为待测的WS-BPEL程序；TS为测试用例集，TS={t1,t2,…,tn}，其中ti为测试用例集中第i个测试用例，n为测试用例集的用例总数；MO表示WS-BPEL的变异算子集合，MO={O1,O2,…,Ok}，其中Oi表示第i个变异算子，k为变异算子总数.

将变异算子质量定义为

(1)

其中，NOi表示Oi变异算子产生的非等价变异体总数.不难看出，上述定义可从故障检测率(fault detection rate,FDR)推导而来.故障检测率FDR定义为测试用例检测变异体的比例，广泛用来衡量测试用例的故障检测能力:

(2)

基于变异算子质量定义，我们提出一种基于变异算子优先级的优化技术(简称为MuPri)，通过衡量变异算子质量，为变异算子分配测试优先级.具体过程为：首先，对大量的WS-BPEL程序进行变异测试；然后，根据测试结果计算变异算子的质量，按照质量由高到低的顺序为其排序，质量好的变异算子在变异测试中分配较高的优先级，质量差的变异算子分配较低的优先级，即按照变异算子优先级顺序指导生成变异体集合.

算法1. 测试用例排序算法.

输入：实例程序P、变异算子集合O、有序的测试用例集TS={t1,t2,…,tm};

输出：排序后的测试用例集TS′.

① 从O中选择适用于P的变异算子集合OP；

② 对OP中变异算子按算子质量由高到低排序，得到变异算子序列OP：OP1,OP2,…,OPn；

③ 令i=1,TS′=∅；

④ WHILEi≤nDO

⑤ 生成OPi的一阶变异体集合MOi(P)={m1,m2,…,mk}；

⑥ WHILEMOi(P)≠∅ DO

⑦ 添加一个测试用例t到TS′;

⑧ FOR ALLmj∈MOi(P) DO

⑨ 以t测试用例执行mj;

⑩ IFmj被“杀死” THEN

MuPri技术不仅可以依据变异算子的优先级，优先使用质量好的变异算子生成变异体，提高变异体集质量，还可以为测试用例集合排序，得到故障检测效率更高的测试用例集，解决测试用例优先级问题.MuPri实现的测试用例排序的过程如算法1所示.

3 支持工具μBPEL

Fig. 2 Architecture of μBPEL图2 μBPEL工具系统结构图

在前期工作中[8-9]，我们开发了一个面向WS-BPEL程序的变异测试支持工具μBPEL，支持变异体的生成、测试用例的执行和测试结果验证.本文通过扩展μBPEL进一步支持本文提出的变异测试优化技术.图2描述了μBPEL工具的系统结构.各个组件的功能描述如下：

1) 变异体生成.负责为待测WS-BPEL程序生成一阶或二阶变异体.

① WS-BPEL解析.解析WS-BPEL程序.

② 算子管理器.针对各种变异算子的匹配与操作，实现对相应节点的变异处理.

③ XML文件读/写.负责WS-BPEL程序文件的读入和变异体输出.

④ 变异体生成.生成一阶或二阶变异体.

2) 变异体优化.支持变异体随机选择优化.

① 参数配置.接收用户输入的待优化的变异体集合路径和变异体精简比例.

② 变异体获取.根据变异体精简比例，从变异体集合中随机获取相应数目的变异体.

3) 测试用例生成.根据WS-BPEL原始文件，输出期望的测试用例.课题组前期研发了2种测试用例生成工具[22]，场景用例生成将WS-BPEL程序转换为图模型，基于给定的覆盖准则生成测试场景和数据；随机用例生成根据用户输入的约束条件，随机生成满足条件的测试用例.

4) 变异测试执行.执行测试用例并获取输出结果.

① 执行环境配置.根据WS-BPEL的配置信息，获取WS-BPEL服务的端口号和操作名称配置执行环境.

② 程序选取.通过用户输入的文件路径，依次获取原始程序和变异体程序文件.

③ 用例读取.读入并解析相应的测试用例文件，获取用例输入变量的类型、数目、值及用例个数等信息.

④ 待测程序执行.调用WS-BPEL引擎依次对原始程序和变异体执行测试用例集并输出结果.

5) 测试结果评估.负责对输出结果进行统计分析，由结果统计和报告获取2个模块组成.

① 结果统计.对执行相同测试用例的原始程序和变异体的输出结果逐一进行对比.若二者结果不同，表明该测试用例将变异体“杀死”，标记为“T”；否则，记为“F”.依次记录变异体被测杀的状态，并统计出针对变异体的每个测试用例集合的故障检测率信息.

② 报告获取.根据结果统计的输出结果，计算

① http://www.activevos.com/developers/sample-apps

变异得分并生成报告，包括变异体数目、被杀死变异体数目和变异得分信息.

4 实验评估

采用经验研究验证与评估本文提出的面向WS-BPEL程序的变异测试优化技术的有效性.

4.1 实验对象

实验对象包括6个WS-BPEL程序实例：SupplyChain实例[19](P1)、SmartShelf实例(P2)[19]、SupplyCustomer实例(P3)[2]、LoanApproval实例(P4)[2]、CarEstimate实例(P5)①和TravelAgency[28]实例(P6).表1总结这些程序实例的具体信息.

Table 1 WS-BPEL Programs表1 WS-BPEL程序实例的基本信息

4.2 实验指标

本文使用变异得分(mutation score,MS)、故障检测率FDR(见式(2))、测试用例序列检测故障的平均百分比(average of the percentage of faults detected,APFD)这3个指标度量变异测试优化方法的有效性.

1) 变异得分MS.对于给定的测试用例集TS，杀死变异体数量与非等价变异体数量的比例[4]，用来衡量测试用例集的充分程度.变异得分计算为

(3)

其中，P代表被测程序，Nk表示被杀死的变异体数量，Nm表示变异体总数量，Ne代表等价变异体的数量.变异得分越高，说明测试用例集“杀死”的变异体越多，测试用例集越有效.

2) 测试用例序列检测故障的平均百分比APFD.用于评价测试用例集的故障检测效率，常用于衡量不同测试用例优先级技术的排序效果[29].APFD的计算公式为

(4)

其中，TS表示具有特定序列的测试用例集，P表示待测程序，n表示测试用例的个数，m表示被检测故障的总数，reveal(i,TS)表示最早检测出第i个故障所执行的测试用例的位置.APFD量化了测试用例序列的效率和效能，即APFD的数值越大，测试用例集故障检测效率越高.本文采用APFD来度量序列化的测试用例的故障检测效率.

4.3 实验设置

讨论与2种变异测试优化技术评估相关的变异体生成和测试用例集.

1) 一阶和二阶变异体生成.针对表1中的WS-BPEL程序实例，采用本文开发的μBPEL工具生成一阶变异体集合(记为M1o)和二阶变异体集合(记为M2o).表2总结了生成的一阶变异体和二阶变异体情况.

Table 2 First-Order and Second-Order Mutants ofWS-BPEL Programs

2) 测试用例生成.在前期工作中[10]，我们采用等价类划分[30]、边界值分析[30]、面向场景测试技术[22]和随机测试技术[30]这4种技术生成测试用例.为了减少不同测试用例生成技术对变异测试结果的影响，最终生成5组测试用例集，分别记为Tx，Ty，Tz，Tu，Tw，如表3所示.|Tx|，|Ty|，|Tz|，|Tu|，|Tw|表示WS-BPEL程序实例对应的每组测试用例集的大小.需要指出的是，测试用例集的数量依赖于程序的规模和所使用的测试用例生成技术.为了保证实验的公平性，本文采用这些测试用例集评估优化技术的有效性.

Table 3 Test Suits of WS-BPEL Programs表3 WS-BPEL实例的测试用例集合

4.4 优化技术评估结果与分析

4.4.1 MuSOM技术评估结果

MuSOM技术有效性的评估过程描述如下：首先，采用测试用例集Tx对一阶变异体集合M1o和二阶变异体集合M2o进行变异测试，得到能够杀死所有变异体的测试用例集TC；然后，采用测试用例集TC对一阶变异体集合M1o进行变异测试，统计变异得分.

表4总结了生成的二阶变异体集合中的等价变异体情况；图3统计了一阶变异体集合和二阶变异体集合的变异得分情况.

Table 4 Equivalent Mutant of WS-BPEL Programs表4 WS-BPEL程序实例的等价变异体情况

Fig. 3 Mutation score of WS-BPEL programs图3 WS-BPEL程序的一阶与二阶变异体的变异得分

上述实验结果表明：

1) 在使用同样数目和种类的变异算子情况下，M2o集合数量约为M1o的一半，相对于一阶变异测试，减少了约50%的待测变异体(如表2所示)；M2o中的等价变异体数目(NE)总和为0，而M1o中存在48个等价变异体(如表4所示)，主要原因是，与一阶变异体相比，二阶变异体中植入了多处错误，降低了等价变异体的生成概率.由此可见，MuSOM技术极大地减少了等价变异体的出现概率(一阶变异测试中等价变异体约为28%)，大幅度降低等价变异体识别带来的计算开销.

2) 在采用相同的测试用例集情况下，二阶变异测试的变异得分均为100%，而一阶变异测试的变异得分有所不同.其中，P3和P5实例中的变异得分为100%；P1和P6实例中的变异得分分别是97.1%和97.5%，接近于100%；P2和P4实例的变异得分分别是72.6%和73.1%.主要原因是，二阶变异体中存在多处错误，更容易被检测出来.相应地，在相同测试用例集情况下，二阶变异测试的变异得分高于一阶变异测试.

综上所述，相对于传统的(一阶)变异测试而言，二阶变异测试技术可以减少约50%的变异体和减少约28%的等价变异体识别开销，同时并没有大幅度降低衡量测试用例集充分性的能力.

4.4.2 MuPri技术评估结果

MuPri技术依据变异算子质量对测试用例集进行排序.通过对比排序前后的测试用例集的APFD评估MuPri技术的有效性.具体步骤有3个：

1) 变异算子优先级排序.首先采用测试用例集Tx，Ty，Tz，Tu，Tw分别执行实例程序和其一阶变异体集合M1o，计算变异得分(MS)和故障检测率(FDR).需要说明的是，如下变异算子在实例程序中不适用：EAA，EEU，ELL，EMD，EMF，AFP，AIS，AWR，AJC，APM，APA，XMC，XMT，XTF，XER，XEE；变异算子ECC和EAP产生的均为等价变异体.限于篇幅，我们不列出每个变异算子的变异得分和故障检测率(参考文献[9]).

表5列出了可适用的变异算子优先级排序结果.依据变异算子质量Qo的平均值，对变异算子排序并分配优先级.优先级的数值越小，表示该变异算子的优先级越高.

Table 5 Priority of Mutation Operators表5 变异算子优先级

2) 测试用例集排序.针对每个WS-BPEL程序P，首先得到变异得分100%的测试用例集TS，使用变异算子优先级得到排序的测试用例集TS′，分别计算测试用例集TS和TS′的APFD值.以SupplyChain程序为例，表5列出了适用的变异算子优先级序列为：CDE→CCO→CDC→ERR→AIE→ASF→AEL→CFA→EIN→ASI→ACI.采用测试用例排序过程(算法1)对SupplyChain实例的测试用例集进行排序，结果如表6所示.表6中，“√”表示测试用例集TS中第1个将该变异体“杀死”的用例.最终得到测试用例集TS的顺序是“T1→T2→T3”.

Table 6 Results of Executing Test Suite (TS) on SupplyChain表6 SupplyChain程序执行测试用例TS结果

Note:“√” means the first test case that kills the mutant.

使用排序后的测试用例集TS执行没有排序的变异体集合，结果如表7所示.其中“√”表示第1个将变异体“杀死”的测试用例，Location表示该用例在TS中的位置，“×”表示测试用例不能“杀死”变异体，“～”表示测试用例没有执行.最终计算得到APFD的值是74.5%.类似地，我们可以得到其他WS-BPEL程序优化前后的APFD值.

Table 7 Results of Mutation Testing表7 变异体测试结果

Notes:“√” means that the test case kills the mutant; “×” means that the test case cannot kill the mutant; “～” means that the test case is not executed to kill the mutant.

3) 比较排序前后测试用例集的有效性.表8列出了每个WS-BPEL程序的变异算子优化前后的测试用例集的APFD.

Table 8 Comparison Between APFD of Original Test Suiteand that of Prioritized Test Suite Using MuPri

上述实验结果表明：使用MuPri优化技术后得到的测试用例序列的APFD值都大于或等于优化前的APFD值.MuPri优化技术优先使用较难被检测的变异算子生成变异体，采用这样的变异体集合为测试用例集排序，可以得到故障检测效率更高的测试用例集.因此，MuPri技术通过对变异算子进行优先级排序提高了测试用例集的故障检测效率.

5 总 结

本文针对WS-BPEL程序的变异测试开销大的问题，提出了2种面向WS-BPEL程序的变异测试优化技术MuSOM和MuPri.其中，MuSOM从变异体数量精简角度，将二阶变异应用WS-BPEL测试；MuPri提出了变异算子质量的概念，通过度量变异算子优先级指导变异体的使用顺序.开发了面向WS-BPEL程序的变异测试支持工具μBPEL，该工具实现了本文提出的优化技术，有助于对WS-BPEL程序进行高效的变异测试.最后，采用6个WS-BPEL程序实例验证并评估了提出的变异测试优化技术的有效性.实验结果表明:本文提出的变异测试优化技术极大地降低了WS-BPEL程序的变异测试开销，提高了变异测试的效率.

未来将在2个方面进一步开展研究工作：1)与其他相关的优化技术进行比较，评估所提出的优化技术的效率；2)扩展验证的WS-BPEL程序集，特别地，目前的程序集适用的变异算子种类较少，需要采用更大规模的实例程序对优化技术进行更全面的评估.