基于集合覆盖的Wp方法测试集约简方法

崔 玲，张建标，3，公 备，吴丽影1

（1.北京工业大学计算机学院，北京 100124；2.北京工业大学可信计算北京市重点实验室，北京 100124；3.北京工业大学信息安全等级保护关键技术国家工程实验室，北京 100124）

基于集合覆盖的Wp方法测试集约简方法

崔 玲1，2，张建标1，2，3，公 备1，2，吴丽影1

（1.北京工业大学计算机学院，北京 100124；2.北京工业大学可信计算北京市重点实验室，北京 100124；3.北京工业大学信息安全等级保护关键技术国家工程实验室，北京 100124）

为了提高测试效率，提出一种基于集合覆盖的测试集约简方法.该方法对有限状态机（finite state machine，FSM）模型中经典的测试生成算法Wp方法（部分W方法）所生成的测试集进行冗余约简.通过分析Wp方法的特点，找出测试序列之间包含关系的规律，删除冗余的测试用例.理论分析和实验结果表明:该方法能够有效约简测试集，并且不改变故障检测能力.

有限状态机（FSM）；Wp方法；集合覆盖；约简

Wp方法是基于有限状态机（finite state machine，FSM）模型进行软件系统测试的经典方法，它具有较高的错误检测能力，但会产生过多的测试用例，导致测试成本过高，因此需要对其测试集进行约简.

现有的测试集约简方法中，比较经典的是贪心算法、启发式算法［1-3］，这2种算法首先需要确定测试需求和测试用例之间的满足关系，然后从测试用例集中优先选择能满足测试需求最多的测试用例，直到测试需求都被满足，时间复杂度均为O（n3）.还有人提出将粗糙集理论和遗传算法用于约简算法中［4-5］，时间复杂度均为O（n3）或O（n2）.这些方法存在的问题是，没有考虑具体的测试生成算法的特点，因此这些算法应用到Wp方法生成的测试集上，虽然一定程度上可以减小测试集规模，但是前提都会设置一些限制条件，或者以降低故障检测能力为代价，因而难以推广应用［6-8］.文献［9］是将约简问题转化为旅行商问题，采用启发式算法对Wp方法的测试集进行约简，约简效果较好，但降低了故障检测能力.

针对这些问题，本文提出了一种基于集合覆盖的测试集约简方法，该方法仅考虑测试序列之间的包含关系，可在不改变故障检测能力的基础上删除冗余序列，达到约简目的.

1 Wp方法

一个FSM模型M可以定义为一个六元组（Q，X，Y，q0，δ，O）［10］，其中Q是有穷的状态集合，X是有穷的输入集合，Y是有穷的输出集合，q0是FSM模型的初始状态，且q0∈Q，δ:Q×X→Q为状态转换函数，O:Q×X→O为输出函数.

用（qi，qj；x/y）表示一个转换，其中qi∈Q，qj∈Q，x∈X+，y∈Y+，δ（qi，x）=qj，O（qi，x）=y，其含义可描述为当FSM模型处于qi状态时，对其输入序列x，FSM模型将转入状态qj，同时输出序列y.

Wp方法，又称部分W方法，是由Fujiwara等［11］提出的，改进了经典算法W方法，Wp方法保持了W方法原有的故障检测能力.

假设FSM模型M包含n（n＞0）个状态，待测模型Ⅰ最多包含m（m≥n）个状态.下面是Wp算法的总体过程:

1）计算M的转换覆盖集P、状态覆盖集S、特征集W、等价特征集Wi.

2）T1=SX［m-n］W.

3）设ψ是M的所有等价特征集的集合，ψ= ｛W1，W2，…，Wn｝.

4）设R=｛ri1，ri2，…，rik｝是所有属于转换覆盖集P但不属于状态覆盖集S的输入串的集合，R= P-S.另外，如果rij∈R，则δ（q0，rij）=qij.

其中δ（q0，rij）=qij，δ（qij，u）=ql，Wl是状态ql的状态等价集，Wl∈ψ.

6）合并T1和T2得到测试集T，即T=T1∪T2.

Wp方法包括2个阶段:第1阶段，用T1中的测试用例测试待测模型Ⅰ，目的在于检测Ⅰ中的状态是否与M中的相应状态等价，但也许没有检查完Ⅰ中的所有转换；第2阶段，用T2中的测试用例测试Ⅰ，目的在于检测M中定义的其余转换是否在Ⅰ中得到了正确的实现.

2 基于集合覆盖的测试集约简方法

2.1约简理论

定理1 对于任意2条测试序列seq1与seq2，如果seq1为seq2的前缀，则有seq1的错误检测能力不大于seq2的错误检测能力.

证明:假设seq1的检测能力大于seq2的检测能力.由于seq1是seq2的前缀，seq2可以分为seq1和子串（seq2-seq1）两部分.那么对待测模型Ⅰ输入seq2所经过的转换路径必为seq1和（seq2-seq1）所经过的转换路径的并集，所得的输出也必然等于seq1和（seq2-seq1）所得输出的并集，因此seq2的检测能力不小于seq1的检测能力.与假设相矛盾，定理成立.

该定理的意义在于，对于待测模型Ⅰ，用测试用例seq2进行测试之后，则不必再用其前缀seq1进行测试.如果在测试用例集中同时有seq1与seq2，则可以认为seq1为冗余序列.

引理1 若1条转换（qi，qj；xk/yl）在待测模型Ⅰ中被正确实现，则需要经过以下3个步骤:

1）将待测模型Ⅰ设置为状态qi，实现此过程可通过向Ⅰ输入特定的输入序列，此输入序列被称为前导序列，用psi表示.

2）将Ⅰ设置为状态qi后，输入xk，测试其输出是否为预期的输出yl.若是，则说明此转换没有出现操作错误，否则说明出现了操作错误.

3）输入xk后，需要检测Ⅰ的当前状态是否为qj.检测方法为向当前Ⅰ输入可以唯一标识该状态的一个输入序列集，在当前状态输入该输入序列集后将产生与其他状态不同的输出.在Wp方法中，该输入序列集为对应状态的等价特征集，即qj的等价特征集（参见文献［12］）.

该引理说明，在判断M中定义的某条转换是否在待测模型Ⅰ中得到正确的实现，即判断该转换的输出和转向的状态是否与M中的定义相一致时，只要确定步骤2）和3）的正确性即可.步骤1）的作用是将Ⅰ设置为该转换的首状态，也就是说前导序列psi可以不唯一.由此可知，假如有2条测试序列seq1与seq2，二者后缀相同，且前导序列激活后的状态为同一状态时，则表明这2条测试序列具有相同的检测能力，可以删除其中一条序列.

2.2约简算法

根据上述约简理论，将测试集的约简转换为集合覆盖问题［12］，依据Wp方法中2个阶段生成的测试序列的特点，分别进行约简.

集合覆盖问题的一个实例（X，F）由一个有穷集X和一个X的子集族F构成，且X的每个元素属于F中的至少一个子集

式中子集S∈F覆盖了X的若干个元素.集合覆盖问题就是找到一个最小规模的子集C∈F，使其所有元素覆盖X的所有元素

算法1 基于集合覆盖的约简算法

GREEDY_SET_COVER（F，X，isCoverFunc）

输入:测试集F，覆盖需求集X.

输出:约简集C.

选择一个序列S∈F，使得CovedSet最大，

其中

其中，函数SetCovered（S，U，isCover_Func）的作用是，根据谓词函数isCover_Func返回集合U中被序列S覆盖的元素组成的集合.

其中谓词函数有2个，定义如下.

函数1 前缀覆盖谓词函数

该函数判断序列S2是否为序列S1的前缀，若是则返回true，否则返回false.

函数2 子串覆盖谓词函数bool isCover_ Subsep（S1，S2）

该函数判断序列S2是否为序列S1的子串，若是则返回true，否则返回false.

设原测试集F=｛t1，t2，…，tm｝，覆盖需求集X= ｛r1，r2，…，rn｝，一次循环中语句（1）最多执行m次，循环最多执行n次，因此该算法的时间复杂度为O（mn）.

算法2 对测试集T1进行约简

输入:测试集T1.

输出:约简后的测试集T′1.

步骤1 求T1对应的转换标识集Tid1，构造覆盖需求集Req（T1）=Tid1；

步骤2 使用前缀覆盖谓词函数作为参数，用GREEDY_SET_COVER算法进行约简，令约简集为

步骤3 将T1id′转换为对应的输入序列集

经过算法2，T1约简前后拥有相同的错误检测能力.

在下面算法3的描述中，转换覆盖集P、状态覆盖集S、特征集W、等价特征集Wi、测试集T2对应的转换标识集分别用Pid、Sid、Wid、Wiid、T2id表示.其中表示状态qi∈Q的等价特征集在状态v∈Q激活FSM产生的转换标识序列构成的集合，同时引入Rid表示Pid与Sid的差集，即Rid=Pid-Sid.

算法3 对测试集T2进行约简

输入:测试集T2.

输出:约简后的测试集T′2.

步骤1 构造覆盖需求集Req（T2），有

其中

Tail（t）:表示转换t的尾状态.

Last（seq）:表示转换标识序列seq的最后一项转换标识.

Xid［m-n］（q）表示对于所有seq∈X［m-n］，seq在状态q∈Q激活FSM产生的转换标识序列构成的集合.

步骤2 使用子串覆盖谓词函数作为参数，用GREEDY_SET_COVER算法进行约简，令约简集为

步骤3 将Tid′2转换为对应的输入序列集

经过算法3，T2约简前后同样拥有相同的错误检测能力.

证明:由引理1可得知，只要满足引理1中所述的3个步骤就可完成对相应转换的检测.T2用于测试M中定义的部分转换是否在I中得到了正确的实现，即判断所检测转换的输出和转入的状态是否与M中的定义相一致［7］.由算法3可知，在对T2进行约简时，将检测转换与该转换尾状态的等价特征集的连接所构成的集合作为覆盖需求集，约简后的集合与T2的区别仅仅在于T2中的前导序列换成了其他的前导序列.所以T2在约简后，其错误检测能力不受影响.

算法4 用算法1对T′1∪T′2再进行一次约简.

3 约简实例

下面以图1所示FSM模型M1为例，演示基于集合覆盖的测试集约简方法的计算过程.

为图1所示的FSM模型M1中的每条转换设置唯一的标识，其对应关系如表1所示.

表1　M1转换标识Table 1 M1transition identification

首先利用Wp方法处理M1，分别得到:

转换覆盖集P=｛ε，a，aa，ab，b，ba，bb｝；

状态覆盖集S=｛ε，a，ab｝，特征集W=｛a，aa｝；

等价特征集W1=｛a｝，W2=｛a，aa｝，W3=｛a，aa｝；

测试集T1=｛a，aa，aaa，aba，abaa｝；

测试集T2=｛aaa，ba，baa，baaa，bba｝；

测试集T=｛a，aa，aaa，aba，abaa，ba，baa，baaa，bba｝.

将上述所得的每个集合转换成由转换标识构成的对应集合，分别得到:

转换覆盖集P对应的标识序列构成的集合

状态覆盖集S对应的标识序列构成的集合

T1集对应的标识序列组成的集合

T2集对应的标识序列组成的集合

假设待测模型Ⅰ与FSM模型M包含相同数量的状态，即m=n，则Xid［m-n］（q）为空.

然后分别对T1、T2及T′

1∪T′2进行约简.

1）对T1进行约简

①构造集合T1的覆盖需求集Req（T1）=T1id，则Req（T1）=｛l1，l1l3，l1l3l1，l1l4l5，l1l4l5l3｝.

②使用前缀覆盖谓词函数isCover_Prefix，令约简后的T1id为T1id′，则

2）对T2进行约简

①构造集合T2的覆盖需求集

②用GREEDY_SET_COVER算法进行约简，则约简集

3）对T′1∪T′2进行约简

①构造集合T′1∪T′2的覆盖需求集

②用GREEDY_SET_COVER算法进行约简，则约简集

将Tid′转换为为输入序列集T′，即

对T1′∪T2′进行约简的方法与约简T1的方法相同，所以其错误检测能力同样不受影响.

表2所示的是约简前后测试用例数量及总长度的对比.

表2　约简前后对比Table 2 Comparision before reduction and after reduction

该实例分析表明，本文所提出方法对Wp方法生成的测试集进行约简，不仅可以减少计算开销，还可以获得较小的测试集.

4 实验分析

定义1 测试序列数量约简率

式中:No为约简前的测试序列的数量；Nr为约简后的测试序列的数量.

定义2 测试序列总长度约简率

式中:Lo为约简前的测试序列的总长度；Lr为约简后的测试序列的总长度.

使用三元组（s，i，o）表示s个状态、i个输入、o个输出的FSM模型.图1所示的FSM模型可以表示为三元组（3，2，2）.结合表2中约简前后的结果，可以得到

为了进一步验证本文所提方法的有效性，进行了多次实验，结果如图2所示.

根据图2可知，测试序列数量约简率ρn和测试序列总长度约简率ρl均可保持在40％以上.而且随着状态数的增多，约简效率会相应提高.初步分析，在Wp方法生成的测试序列集中，每个测试序列的测试路径都是由初始状态开始，状态数越多，具有前缀包含关系和子串包含关系的测试序列越多，因此约简效果越好.

同时，建立错误检验模型，对存在的操作错误和转换错误进行检验，在m=n的情况下，得出M1存在24 404个错误.实验证明，本文方法可以检测出M1的所有错误.使用文献［9］中提出的方法，M1的测试集为TTSP=｛baaabaaaaabba｝，进行错误检验，有12个错误不能被检测，图3所示的是其中一条不能被检测的错误转换（q3，q1；a/1）.

5 结论

1）本文提出一种基于集合覆盖的约简算法，利用测试序列之间的包含关系，对Wp方法生成的测试用例集进行约简.

2）通过分析Wp方法生成测试序列的特点，理论证明了本文所提方法不会改变Wp方法的错误检测能力.

3）通过实验证明，本文所提方法可以有效地减少测试序列的长度和数量，提高测试效率.

［1］游亮，卢炎生.测试用例集启发式约简算法分析与评价［J］.计算机科学，2011，38（12）:147-150. YOU L，LU Y S.Analysis and evaluation of heuristic algorithms for test suite reduction［J］.Computer Science，2011，38（12）:147-150.（in Chinese）

［2］HARROLD M J，GUPTA R，SOFFA M L.A methodology for controlling the size of a test suite［J］.ACM Trans on Software Engineering and Methodology，1993，2（3）:270-285.

［3］CHEN T Y，LAU M F.A new heuristic for test suite reduction［J］.Information and Software Technology，1998，40（5/6）:347-354.

［4］WEN H S，WEN B Q.An incremental approach to attributereductionfromdynamicincompletedecision systems in rough set theory［J］.Data＆amp;Knowledge Engineering，2015，100:116-132

［5］NEHA S，MS S.Model based test case prioritization for cost redution using genetic algorithm［J］.International Journal of Science and Engineering Applications，2015，3 （4）:105-109.

［6］CHEN T Y，LAU M F.On the divide-and-conquer approach towards test suite reduction［J］.Information Sciences，2003，152（1）:89-119.

［7］XIAO J，LAM C P，LI H，et al.Reformulation of the generationofconformancetestingsequencestothe asymmetric travelling salesman problem［C］∥Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation.New York:ACM，2006:1933-1940.

［8］XIE L，WEI J L，ZHU G X.Improved FSM-based method forprotocolconformancetesting［J］.Journalon Communications，2011，32（6）:172-176.

［9］XIAO J，LAM C P，LI H，et al.Reformulation of the generationofconformancetestingsequencestothe asymmetric travelling salesman problem［C］∥Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation.New York:ACM，2006:1933-1940.

［10］CHEN W H.An optimization technique for protocol conformance testing based on the Wp method［J］. International Journal of Applied Science and Engineering，2003，1（1）:45-54.

［11］FUJIWARA S，BOCHMANN G，KHENDEK F.Test selection basedonfinitestatemodels［J］.IEEE Transactions on Software Engineering，1991，17（6）: 591-603.

［12］CAPRARA A，TOTH P，FISCHETTI M.Algorithms for the set covering problem［J］.Annals of Operations Research，2000，98（1/2/3/4）:353-371.

（责任编辑 吕小红）

Approach for Reduction Test Suite of Wp Method Based on Set Covering Problem

CUI Ling1，2，ZHANG Jianbiao1，2，3，GONG Bei1，2，WU Liying1
（1.College of Computer Science，Beijing University of Technology，Beijing 100124，China；2.Beijing Key Laboratory of Trusted Computing，Beijing University of Technology，Beijing 100124，China；3.National Engineering Laboratory for Critical Technologies of Information Security Classified Protection，Beijing University of Technology，Beijing 100124，China）

To improve the test efficiency，a reduction method of test sets reduction based on set covering was presented.Redundancy reduction on the test set generated by Wp（part of W）method was carried out，which was a classical test generation algorithm in FSM（finite state machine）model.By analyzing the characteristics of Wp method，the regularity of the inclusion relations between test sequences was found，and then redundant test cases were deleted.Theoretical analysis and experimental results show that the method can effectively reduce the original test set and has the same error detection capabilities as the test set before.

finite state machine（FSM）；part of W（Wp）method；set covering；reduce

TP 319

A

0254-0037（2016）09-1332-06

10.11936/bjutxb2015120046

2015-12-18

国家自然科学基金资助项目（61501007）

崔 玲（1979—），女，讲师，主要从事信息安全方面的研究，E-mail:vicky@bjut.edu.cn