WS－CDL测试路径的生成与排序

刘翠翠 邱 栋 李必信

(东南大学计算机科学与工程学院，南京211189)

Web 服务编舞描述语言(Web service choreography description language，WS－CDL)［1－2］是一种应用广泛的服务编舞语言.在使用WS－CDL 描述组合服务时，为尽早发现设计中的错误，减少维护开销，需要对WS－CDL 进行测试.WS－CDL 规约指出，WS－CDL 不是一种可执行的业务过程描述语言，也不是一种实现语言，因此目前没有业界统一的执行引擎，这也导致对WS－CDL 的测试工作研究甚少.文献［3］将服务编舞行为建模成带标签的转换系统，将XPath 和XML schema 与服务编舞的具体行为联系起来，识别数据流，生成数据流测试准则.文献［4］提出一种测试WS－CDL 的方法，该方法对当前路径中的最后一个谓词取反，得到下一条路径再执行;重复该过程直至所有路径均被执行则终止.该方法对WS－CDL 规约进行扩展，加入assertion 语句，用以描述WS－CDL 程序的设计者对程序的预期，便于在测试过程中与实际结果相比较.因此，若测试人员采用该方法对WS－CDL 程序进行测试，就需要以侵入方式修改内部代码，从而改变了源程序.

对WS－CDL 组合流程进行测试时，如果运行所有的测试用例会导致测试开销过高，因此研究者提出各种约简测试集的方案［5－6］，以减小测试开销，但这也可能会对错误定位有所影响.测试集排序技术［7－11］根据测试需求定义某种重要性准则，并对测试用例按重要性由高到低排序，即重要性高的测试用例优先测试，这样可以尽早地发现错误.

本文首先提出一种基于控制流图的WS－CDL测试路径生成方法，该方法对WS－CDL 程序进行解析，提取有用的元素信息，将程序转换成WSCDL 控制流图，并据此生成所有可能的测试路径;然后提出2 种测试集排序策略对测试路径进行排序，以提高发现错误的效率;最后通过实例分析，比较未排序和排序后的执行效果.

1 WS－CDL 概述

WS－CDL 是基于XML 的描述语言，旨在从全局观念出发，组合多个任意形式的参与者，通过点对点的交互方式进行协作，从而共同完成某个公共的目标.其中合作参与者的编程模型或平台是任意的，点对点交互通过信道传递消息实现.WS－CDL规约［2］中主要元素层次关系如图1所示.

图1 WS-CDL 主要元素的层次关系

2 WS－CDL 控制流图CCFG

2.1 CCFG 定义

文献［12］根据业务流程执行语言(business process execution language，BPEL)的特点，提出适合BPEL 文档结构的BPEL 流图(BPEL flow graph，BFG)，用于对BPEL 测试.文献［13］在BFG 基础上扩充节点信息，形成扩展BPEL 流图(eXtensive BPEL flow graph)，用于BPEL 的回归测试.本文将此方法应用到WS－CDL 中，根据WSCDL 中元素特征，构造WS－CDL 文档的WS－CDL控制流图CCFG(choreography control flow graph).CCFG 的形式化定义如下:

定义1(WS－CDL 控制流图CCFG)CCFG 是一个四元组〈N，E，s，f〉，其中N 为节点集，N =NN∪EBN ∪EMN ∪PBN ∪PMN ∪CBN ∪CMN ∪RBN∪RMN，且NN，EBN，EMN，PBN，PMN，CBN，CMN，RBN，RMN 分别为普通节点、单选分支节点、单选归并节点、并发分支节点、并发归并节点、选择分支节点、选择归并节点、循环分支节点和循环归并节点;E 为有向边集;s 为开始节点;f 为终止节点;节点和有向边统称为CCFG 的元素.

进入节点的有向边的数目称为该节点的入度;从节点出去的边的数目称为该节点的出度.CCFG具有如下属性:

1)普通节点的入度不大于1，出度大于等于1，如〈package〉，〈assign〉，〈interaction〉等.终止节点出度为0，入度大于等于1.普通节点和终止节点的所有入边和出边均会被触发.

2)分支节点和归并节点是成对出现的，且分支节点的入度均为1，出度均大于1;归并节点的入度均大于1，出度均为1.

3)EBN 和EMN 是一对单选节点(exclusive node)，对应WS－CDL 文档中的〈choice〉，〈choice〉中描述2 个或多个活动，但每次执行有且仅有一个活动被选择，被选择的活动对应的边被触发.EBN的出度和EMN 的入度为〈choice〉中的活动数目.

4)PBN 和PMN 是一对并发节点(parallel node)，对应文档中的〈parallel〉，〈parallel〉中包含多个并行执行的活动，因此PBN 的出度和PMN 的入度为〈parallel〉中的活动数目，且所有的边均被触发.

5)CBN 和 CMN 是一对选择节点，由〈workunit〉的属性guard 映射而来，guard 定义一个条件表达式，当〈workunit〉包含可选属性guard 且该表达式为真时执行〈workunit〉，否则跳过，因此CBN 的出度和CMN 的入度均为2.

6)RBN 和 RMN 是 一 对 循 环 节 点，由〈workunit〉的另一个可选属性repeat 映射而来，repeat 类似于结构化程序中的while 结构，workunit 中的活动会重复执行当且仅当repeat 对应的条件表达式为真，因此RBN 的出度和RMN 的入度均为2.

2.2 CCFG 构造

设N 是CCFG 的一个节点，则在WS－CDL 执行过程中先于N 被执行的第一个节点称为节点N 的源节点;在N 被执行后第一个执行的节点称为节点N 的目标节点.容易看出:

1)CCFG 的开始节点没有源，终止节点没有目标.

2)若N1的目标节点是N2，则N2的源节点是N1.

WS－CDL 中与活动流程密切相关的是〈choreography〉，而用于角色定义和信道类型定义的元素，如〈role〉，〈channelType〉等不影响控制流图的结构，所以在构造CCFG 时忽略这些元素.又由上述性质2)可知源和目标是相互的，因此只要计算出所有节点的目标节点，根据相互性，所有节点的源节点也均被计算出.

构造CCFG 的流程如图2所示.由于WS－CDL是基于XML 的描述语言，所以选择XML 解析器DOM Parser 将WS－CDL 文档解析成DOM 树，然后根据DOM 树提取有用的节点形成CCFG 节点，并确定各节点的源节点和目标节点，最后添加由源节点指向目标节点的有向边，形成完整的CCFG.

图2 CCFG 的构造流程

从DOM 树提取CCFG 节点并确定该节点的源节点和目标节点的规则如下:

1)〈package〉是WS－CDL 的根元素，因此将〈package〉作为CCFG 的开始节点，其源节点为空，目标节点是在初始节点之后第一个被映射的节点.

2)〈assign〉映射为普通节点N，N 的源节点是先于N 被映射的第一个节点，目标节点是N 之后第一个被映射的节点.

3)〈workunit〉包含2 个可选属性guard 和repeat，根据属性的不同确定〈workunit〉的节点类型.

①若〈workunit〉包含的属性是guard，生成选择分支节点CBN、选择归并节点CMN 和普通节点NN 3 个节点.CBN 的目标节点有2 个，一是〈workunit〉子元素中第一个被映射成的节点(guard 中条件表达式为真时〈workunit〉体被触发)，二是CMN(guard为假时，程序跳过〈workunit〉直接到CMN).若〈workunit〉的子元素均不需要被映射成CCFG 节点，则CBN 的2 个分支均会直接连接到CMN，此时可能会发生无法区分这2 条路径的情况.为避免此情况发生，在guard 为真的分支上增加一个NN，即将CBN 的一个目标节点改为由guard 生成的NN，该NN 的目标节点是〈workunit〉子元素中第一个被映射成的节点或者CMN.〈workunit〉子元素中最后一个被映射成的节点或者NN(当〈workunit〉中没有需要映射成CCFG 节点时是NN)的目标节点是CMN.CMN 的目标节点是下一个需要映射成CCFG节点的节点.

②若〈workunit〉包含的属性是repeat，类似于guard 的情况，也生成循环分支节点RBN、循环归并节点RMN 和普通节点NN.RBN 的目标节点包括新生成的NN 和RMN.〈workunit〉子元素中最后一个被映射成的节点或者NN 的目标节点是RBN，RMN 的目标节点是下一个需要映射成CCFG 节点的节点.

4)〈parallel〉映射为一对并发节点.并发分支节点 PBN 的目标是〈parallel〉所有子元素〈workunit〉对应的分支节点，并发归并节点PMN的源是所有〈workunit〉对应的归并节点.

5)〈choice〉映射为一对单选节点.为〈choice〉的每一个子活动生成一个普通节点，这些普通节点就是单选分支节点的目标节点.单选归并节点的源是〈choice〉所有子活动对应的最后一个节点.

6)互为源和目标的2 个节点通过一条由源节点指向目标节点的有向边连接.

3 基于CCFG 生成测试路径

3.1 测试路径的表示方法

对源代码而言，程序的一次执行经过的部分构成一条路径;对于CCFG 而言，一条路径就是由相邻的节点和边按顺序连接而成的，它始于初始节点s，止于终止节点f.在CCFG 中，2 个节点间最多只存在一条边，因此，路径pf可用节点序列表示，即pf={s，n1，…，nk，nk+1，…，nn，f}，其中n1为s的目标节点，nk+1为nk的目标节点(1≤k ＜n)，f为nn的目标节点.

3.2 测试路径集的构造

从s 出发遍历CCFG，每一个分支都对应有新路径产生，遍历结束时所有可能的路径均生成，即完成了测试路径集的构造.对于并发结构，由于特定的输入数据所产生的路径具有相同的执行条件和期望输出，因此本文将它们视为同一条路径.对于循环结构，为了避免环带来的路径的无限循环，仅构造2 条路径以覆盖循环分支上的所有节点.具体构造过程如下.

算法1 构造测试路径集

4 测试路径的排序

测试用例排序技术［7－11］按照某种准则对测试用例排序，使得高优先级的测试用例可以先于低优先级的测试用例进行测试.文献［7］给出了其形式化定义.

定义2(测试用例排序问题)给定测试集T，PT 为T 的全排列，函数f 将PT 中的元素映射成实数，求解T′∈PT，使得

每个测试用例均与一条测试路径一一对应，因而本文测试用例的排序问题即为对测试路径的排序.本文给出2 种排序算法，并在下文给出案例分析，对比排序效果.

WS－CDL 是基于XML 的语言，其文档由XML结构的元素组成，且WS－CDL 元素被映射成CCFG中的节点，而测试路径是由节点构成的，因此可以认为测试路径对应着WS－CDL 文档中的部分元素，本文提出的2 种排序策略均是基于路径中的元素数量的.

4.1 基于路径中元素总数的排序策略

该排序策略基于以下假设:如果测试用例中覆盖的代码越多，则发现错误的可能性越大，因此为尽早地发现错误，应优先选择覆盖代码较多的测试用例.路径中的节点对应WS－CDL 文档中的元素，路径中节点数越多说明该路径对应的测试用例覆盖的WS－CDL 元素也越多.因此本文提出的第1 个排序策略(简称T1)是以路径中节点对应的元素数为排序准则，即计算每条路径中的元素数，按照元素数由多到少对测试路径排序，具体算法如下.

算法2 按路径中元素总数递减的排序算法

4.2 基于路径中未覆盖元素总数的排序策略

对于第1 种排序策略，可能存在以下情况:设有路径p1，p2，p3，且3 条路径中节点数依次减少，因此3 条路径的排序序列是p1，p2，p3.p2优先于p3，但p2中的部分节点可能在p1中已被覆盖，此时p3中未被覆盖的节点数比p2多，因此应优先选择p3，这是本文提出的对T1 的改进排序策略T2，具体算法如下.

算法3 按路径中未覆盖元素总数递减的排序算法

5 实例分析

本节通过解析一个WS－CDL 实例程序构造出对应的CCFG，遍历CCFG 后生成所有可能的测试用例，形成测试用例集，然后用2 种排序算法对测试路径集排序，最后利用APFD(average percentage of faults detected)准则［7］比较初始路径集和排序后路径集的查错效果.

图3给出了一个简单WS－CDL 程序的CCFG，该文档由2 个〈choreography〉组成，包含3 个分支结构，其中第1 个〈choice〉嵌套了1 个〈workunit〉.存在错误的节点用黑色底纹标注.

为了便于生成测试路径，在构造CCFG 时有些元素需要映射为一对节点.根元素〈package〉标志流程的开始，与其对应的〈/package〉标志流程的结束，因 此 解 析 WS－CDL 时，将〈package〉和〈/package〉分别映射为开始节点s 和终止节点f;表示分支结构的元素如〈workunit〉，〈parallel〉和〈choice〉，在CCFG 中也需要用一对节点表示，例如图3中节点10 和节点11 表示同一个元素〈workunit〉.排序算法中是以元素数量作为准则的，因此从路径中计算元素数量时应去除重复的节点，图中重复元素用虚线表示.可看出，根据算法1图3中共存在8 条测试路径，按照生成的路径顺序(A-B-C-D-E-F-G-H)构成初始测试路径集，如表1所示.

图3 CCFG 实例

表1 路径集和错误分布

根据算法2，即将路径按元素总数递减排序，则排序后的路径序列为G-H-C-A-D-B-E-F;根据算法3，即将路径按未覆盖元素总数递减排序，排序后的路径序列为G-D-A-B-C-E-F-H.

按照未排序的测试路径序列(A-B-C-D-E-FG-H)进行测试，执行第1 条测试路径A 发现错误f1;执行第2 条测试路径B 发现错误f1和f6，即多发现了一个错误，此时共发现2 个错误;执行路径C 后新发现错误f2和f3，此时共发现4 个错误;执行路径D 后发现错误f2，f3和f6，这些错误均已在前面的路径中发现，因此此时发现的错误总数仍是4;执行路径E 后新发现错误f4，此时共发现5 个错误;执行路径F 后没有发现新错误;执行路径G后，最后一个错误f5被发现，即经过7 条测试路径才找到所有的错误.

按照算法2 的测试路径序列进行测试，路径G，H，C，A 分别发现新错误2，1，2，1 个，即在执行第4 条路径后发现所有的错误.

按照算法3 的测试路径序列进行测试，执行第1 条测试路径G 后发现2 个错误;第2 条测试路径D 新发现3 个错误，第3 条测试路径A 发现最后一个错误，即在执行第3 条路径后发现所有的错误.

图4 3 种路径序列的APFD

APFD 是一种常用的衡量排序技术的准则.图4给出了3 种路径序列APFD 值的比较.图中8 条测试路径将横坐标8 等分，纵坐标表示已找到的错误占所有错误的百分数，图中阴影部分的面积就表示APFD 值，其取值范围为0～1，APFD 值越大，说明错误发现得越快.文献［11］给出了APFD 的计算公式:

式中，m 表示程序中包含的错误数;n 表示测试用例数;Tm(1≤i≤m)表示第一次发现错误fi的测试用例在测试集中的位置.根据式(1)计算3 种情况下的APFD，分别为58.3%，77.1%和83.3%.可见，排序后可以更快地发现所有错误，并且基于未覆盖元素总数的排序策略由于在选择下一条最优路径时忽略已覆盖的元素，避免覆盖重复的错误，其找错效率更高.

6 结语

本文提出一种用于生成服务编舞描述语言WS－CDL 测试路径的控制流图CCFG.根据WSCDL 元素特点，定义了普通节点、单选节点、并发节点、选择节点和循环节点，并通过由源节点指向目标节点的有向边连接成CCFG，基于CCFG 构造所有可能的路径.为提高发现错误的效率，提出2种基于路径中元素总数的排序算法，对路径的执行顺序进行排序.通过实验比较可知，按照排序后的序列测试WS－CDL，能够更快地发现错误.基于路径中未覆盖元素总数的排序策略在选择下一条最优路径时，忽略已覆盖的元素，避免覆盖重复的错误，可以更快地定位错误.

本文根据WS－CDL 的结构特点生成测试路径，忽略了WS－CDL 中的数据信息，下一步将考虑在CCFG 中扩展数据信息，获取更全面的WSCDL 信息.

向为本文提供宝贵意见的孙小兵、朱敏、吴晓娜、李加凯、齐珊珊等同学表示感谢.

References)

［1］Papazoglou M P，Traverso P，Dustdar S，et al.Service oriented computing:state of the art and research challenges［J］.Computer，2007，40(11):38－45.

［2］Kavantzas N，Burdett D，Ritzinger G，et al.Web services choreography description language version 1.0［EB/OL］.(2005－11－09)［2010－06－19］.http://www.w3.org/TR/ws－cdl－10/.

［3］Mei L，Chan W K，Tse T H.Data flow testing of service choreography［C］//Proceedings of the Joint 12th European Software Engineering Conference and 17th ACM SIGSOFT Symposium on the Foundations of Software Engineering.Amsterdam， The Netherlands，2009:151－160.

［4］Zhou L，Ping J，Xiao H，et al.Automatically testing web services choreography with assertions ［C］//Proceedings of the 12th International Conference on Formal Engineering Methods and Software Engineering.Shanghai，China，2010:138－154.

［5］Michael R，Sehun T.Towards automating regression test selection for Web services［C］//Proceedings of the 16th International Conference on World Wide Web.New York，2007:1265－1266.

［6］Rohtermel G，Harrold M J，Ostrin J，et al.An empirical study of the effects of minimization on the fault detection capabilities of test suites ［C］//Proceedings of the International Conference on Software Maintenance.Bethesda，MD，USA，1998:34－43.

［7］Rothermel G，Untch R，Chu H C，et al.Prioritizing test cases for regression testing［J］.IEEE Transactions on Software Engineering，2001，27(10):929－948.

［8］Rothermel G，Untch R H，Chu C，et al.Test case prioritization:an empirical study［C］//Proceedings of the International Conference on Software Maintenance.Oxford，UK，1999:179－188.

［9］Mei L，Chan W K，Tse T H，et al.XML－manipulating test case prioritization for XML－manipulating services［J］.Journal of Systems and Software，2011，84(4):603－619.

［10］Mei L，Zhang Z，Chan W K，et al.Test case prioritization for regression testing of service－oriented business applications［C］//Proceedings of the 9th International Conference on Quality Software.New York，2009:901－910.

［11］Elbaum S，Malishevsky A G，Rothermel G.Test case prioritization:a family of empirical studies［J］.IEEE Transactions on Software Engineering，2002，28(2):159－182.

［12］Yuan Y，Li Z J，Sun W.A graph－search based approach to BPEL4WS test generation ［C］//Proceedings of the International Conference on Software Engineering Advances.Tahiti，Polynesia，2006:4031799.

［13］Wang D，Li B，Cai J.Regression testing of composite service:an XBFG－based approach［C］//Proceedings of Congress on Services Part Ⅱ.Beijing，China，2008:112－119.