0 引言

软件测试日渐重要，基于变异的测试用例生成技术(Mutation-based Test Case Generation, MTCG)^[1]得到了学术界的广泛关注。变异测试是一种基于故障植入的软件测试技术，使用变异算子对被测程序语句进行合乎语法的微小改动，被改动的语句称为变异语句，带有变异语句的程序称为变异体^[2]。在变异体上执行测试用例，若执行结果和原程序执行结果不同，则称该变异体被该测试用例杀死，反之则称该变异体未被杀死。MTCG技术旨在生成极少的测试用例杀死尽可能多的变异体，以获得较高质量的测试用例集。然而，变异测试代价昂贵，无法应用于软件实际测试中，因此，如何降低变异执行开销是MTCG技术的重点研究内容^[3]。

变异测试分为弱变异测试和强变异测试，弱变异测试只需检测变异体变异位置的状态和原程序不同，即可以判定该变异体被杀死；强变异测试则需要检测变异体执行结果和原程序输出结果不同，才可判定变异体被杀死。所以，弱变异测试不用运行完整的程序，其测试代价小于强变异测试，是一种降低变异执行开销的有效途径^[4]。因此，目前大部分研究集中在弱变异测试用例自动生成方面。Papadakis等^[5]基于弱变异测试准则，提出用变异前后的语句构建变异分支，将弱变异测试问题转化为变异分支覆盖问题，这在一定程度上降低了变异测试的执行开销，然而其在测试用例生成时，采用的进化算法每次仅以一个变异分支为目标，生成一条测试用例，效率较低。随后，Fraser等^[6-7]以所有变异分支为目标，以测试用例集为个体，利用遗传算法实现测试用例集的自动生成；在此基础上，文献[8]给出了一种基于集合进化算法(Set Evolutionary Algorithm, SEA)的弱变异测试用例集生成方法，将测试用例集作为个体，增设了集合内部的交叉算子，通过种群进化，使其个体能够覆盖更多变异分支，最终生成一个能够覆盖全部变异分支的个体或者达到其最大迭代次数，即测试用例集生成成功或失败。该方法的执行效率高于传统的面向单个变异分支的测试用例生成方法，但也存在下面两个问题：

1) 个体规模(即其包含的测试用例个数)在进化过程中是固定不变的，因此需要设置适当的个体初始规模。然而通常情况下，测试人员无法事先根据拟覆盖变异分支的个数确定所需的测试用例个数：取值过大，容易引起测试用例生成开销的增大和存储空间的浪费；取值过小，又可能导致测试用例集生成失败。

2) 其以目前广泛使用的分支距离作为适应度函数，不适合于以集合为个体的进化评估，且该适应度函数计算开销大。

因此，本文提出了一种基于动态集合进化算法(Dynamic Set Evolutionary Algorithm, DSEA)的弱变异测试用例集生成方法，该方法的个体规模是动态可变的，在进化过程中，寻找合适的个体规模，以生成较小规模的测试用例集，同时避免个体初始规模对于测试用例集生成的影响。本文的主要贡献如下：

1) 提出了一个动态集合进化算法，通过增设集合精简算子，优化种群中的个体规模，使个体规模在进化过程中得以动态调整，以寻找合适的测试用例集规模。

2) 设计了一个适用于集合进化的适应度函数，降低了动态集合进化算法在弱变异测试用例集自动生成中的计算开销。

3) 在5个基准程序上，实现了基于动态集合进化的弱变异测试用例集自动生成，并与使用集合进化的弱变异测试用例集生成方法进行比较，结果表明利用动态集合进化算法的弱变异测试用例集生成其时间开销最多降低了74.58%，生成的测试用例集规模平均减少了50.15%。

1 相关研究 1.1 弱变异测试

对于给定的被测程序P，在其语句s上实施某一变异算子，得到变异语句s′，将被测程序P中s替换成s′，保持其他语句不变，则可以得到P的一个变异体M^[9]。其中变异算子的定义是：在符合语法规则的前提下，从原程序生成差别极小程序(即变异体)的转换规则。

例如，针对图 1所示原程序中的语句c=a+b，实施基本算术运算符替代变异操作，即分别用“-”“*”和“/”代替原始运算符“+”，生成3个变异体m1、m2和m3，如图 1所示。

变异测试通过执行测试用例并检测变异体与原程序的执行结果来判定变异体是否被杀死。当测试用例集足够完备时，未被杀死的变异体，称为等价变异体^[10]。杀死的变异体数量占非等价变异体数量的比值，称为变异得分^[11]，常用来评价测试用例集的质量。变异得分越高，测试用例集质量越好。

一般情况下，测试用例杀死变异体需满足3个条件：1) 可达性条件：变异位置可以被测试用例执行到；2) 必要性条件：原程序与变异体在变异位置的执行状态不同；3) 充分性条件：原程序与变异体的输出结果不同。

满足上述3个条件的变异测试即为强变异测试，由于充分性条件需要执行完整的程序，执行成本高，为降低执行开销，Howden^[12]给出了弱变异测试准则，只需满足上述前两个条件——可达性与必要性，即可判定变异体被杀死。

1.2 弱变异测试用例集生成

弱变异测试用例集生成是指生成满足弱变异测试准则的测试用例集。Papadakis等^[5]认为可以将弱变异测试准则转化为变异分支覆盖准则，其变异分支与变异分支覆盖准则定义如下：

定义1  变异分支。设原语句的主体表达式为e，实施某一变异算子后获得变异语句的主体表达式为e′，构造条件不等式e!= e′，该条件不等式则为一个变异分支。

例如，对于图 1中原程序语句c=a+b，应用基本算术运算符替代变异操作后，对应的三个变异语句分别为c=a-b、c=a*b和c=a/b，其变异分支分别为a+b!= a-b、a+b!= a*b和a+b!= a/b。

定义2   变异分支覆盖准则。在原程序P的相应语句前插入其生成的所有变异分支，形成插桩程序P′，对程序P′执行测试用例集，使得P′中每个变异分支其值为真的情况至少出现一次，则称该测试用例集满足变异分支覆盖准则。

将图 1中原程序语句c=a+b的三个变异分支插入到该语句c=a+b前，形成一个新的程序P′，如下所示。

class ClassA{

int s(int a, int b){

  int c;

  if((a+b)!=(a-b)){printf("m1 is killed"); }

  if((a+b)!=(a*b)){printf("m2 is killed"); }

  if((a+b)!=(a/b)){printf("m3 is killed"); }

  c=a+b;

  return c;

}}

若测试用例集能够覆盖P′所有变异分支的真分支，则可检测出原程序与所有变异体在变异位置的执行状态不同；即测试用例集满足变异分支覆盖准则，等同于满足弱变异测试准则。

因此，基于弱变异测试准则的测试用例生成问题可转换为满足变异分支覆盖准则的测试用例生成问题，通过不断生成测试用例，直到所有变异分支都被覆盖为止。

1.3 基于集合进化的弱变异测试用例集生成

将弱变异测试准则转化为变异分支覆盖准则，将每个变异分支看作一个目标，使得弱变异测试用例集的自动生成可以看作是一个多目标问题，即生成若干测试用例，覆盖所有变异分支。

利用进化算法实现测试用例自动生成是一种常用的方法。传统进化算法，一个个体代表一个解。当一个个体代表多个解的集合时，相应的进化优化算法称为集合进化^[13]，该算法可以一次生成满足多个目标的解集，而不是每次生成满足单个目标的解。将集合进化算法应用于弱变异测试用例集生成，其种群中的个体为测试用例集合，通过交叉、变异操作生成新个体。基于集合进化的弱变异测试用例集生成如算法1所示。

算法1  基于集合进化的弱变异测试用例生成算法SEA。

Initial pop;           //初始化

  evaluate(pop);         //计算适应度值

  repeat

    Inner_crossover(pop);       //个体内部交叉操作

    Inter_crossover(pop);       //个体之间交叉操作

    Mutate(pop);         //个体变异操作

    evaluate(pop);         //计算适应度值

    pop=update(pop);           //种群更新

until(满足终止条件)

1) 集合交叉Crossover()。

集合进化种群中的个体是一个集合，其既可以通过两个集合交叉产生新个体，又可以通过集合内部交叉产生新个体，因此，集合交叉又可分为集合间交叉Inter_crossover()和集合内交叉Inner_crossover()两种，其中集合内交叉是集合进化算法所特有的。常用的集合交叉方式为单点交叉。

2) 集合变异Mutate()。

集合变异是指通过对集合(个体)中的元素进行更改，产生新的个体。常用的集合变异策略是随机变异，即随机选择个体的某个基因进行变异。

3) 种群更新update()。

种群更新策略决定哪些个体可以进入下一代种群。集合进化算法中常用的种群更新策略为(μ+λ)更新策略，即种群规模为μ，其通过交叉变异产生λ个子代个体，在μ个父代个体与λ个子代个体中根据适应度值选择μ个个体进入下一代种群。

将集合进化算法应用于弱变异测试用例集生成，其生成效率高于传统方法，但其个体规模在进化过程中是固定不变的，需要事先设置合适的个体初始规模，这是很困难的。此外，其使用分支距离作为适应度函数，需要计算谓词分支距离，增加了计算开销。因此，本文提出一种动态集合进化算法，用于实现弱变异测试用例集的自动生成。

2 动态集合进化的弱变异测试用例集生成

本文针对弱变异测试用例集自动生成，提出一种动态集合进化算法，通过增设集合精简算子，动态调整个体规模，以寻找合适的测试用例集规模，同时避免个体初始规模对生成测试用例集规模的影响；设计了适用于集合进化的适应度函数，降低弱变异测试用例集生成的计算开销。

2.1 动态集合进化的弱变异测试用例集生成算法

基于动态集合进化的弱变异测试用例集生成的核心思想是以变异分支覆盖为准则，以测试用例集合为个体，在种群进化过程中，动态调整个体规模，以寻找合适的测试用例集规模，生成较小规模的测试用例集，实现弱变异测试用例集的自动生成。基于动态集合进化的弱变异测试用例集生成如算法2所示。

算法2  基于动态集合进化的弱变异测试用例集生成DSEA。

Initial pop;           //初始化

evaluate(pop);         //计算个体的适应度值

repeat

  refine_set =Greedy_Essential(best_Ind);     //精简最优个体

  if(best_Ind.fitness==0){return refine_set; }  //测试用例集生成

  else{

    Nt=estimate(refine_set);   //估算个体(测试用例集)合适规模

    pop=adjust(pop, Nt, refine_set);       //调整个体

    Inner_crossover(pop);       //个体内部交叉操作

    Inter_crossover(pop);       //个体之间交叉操作

    Mutate(pop);         //变异操作

    evaluate(pop);       //计算个体的适应度值

    pop=update(pop);         //种群更新

}

until(满足终止条件)

因此，基于动态集合进化的弱变异测试用例集生成首先初始化种群pop，利用evaluate()函数计算种群中个体的适应度值；通过Greedy_Essential()函数对最优个体进行精简，除去冗余，获得最优个体的精简集refine_set；若最优个体精简集refine_set能够覆盖所有的变异分支，则弱变异测试用例集生成，算法结束；否则，estimate()函数根据最优个体精简集规模和未覆盖的变异分支数量估算个体(测试用例集)的适当规模Nt，adjust()函数依据Nt调整种群的个体规模；对调整后的种群应用集合进化算法，实施交叉、变异操作生成新个体，update()函数根据种群更新策略对种群进行更新。重复上述过程，直到进化次数到达指定值或者生成弱变异测试用例集。

2.2 适应度函数及动态集合进化的设计 2.2.1 适应度函数

适应度函数用来评估个体的优劣，本文动态集合进化算法的个体是测试用例集，目标是覆盖全部变异分支，因此本文将个体未覆盖的变异分支数量作为衡量个体优劣的适应度函数。

假设被测程序的变异分支集为B，当前个体Ind对每个变异分支b_i(b_i∈B)的覆盖情况用f_i(Ind)表示，即f_i(Ind)=0表示变异分支b_i被当前个体Ind覆盖，f_i(Ind)=1表示个体Ind未覆盖变异分支b_i，则适应度函数Fitness(Ind)的计算公式可以表示为：

$ Fitness\left( {Ind} \right) = \sum\limits_{i = 1}^{|B|} {{f_i}\left( {Ind} \right)} $

(1)

Fitness(Ind)值越小，说明Ind没有覆盖的变异分支越少。当Fitness(Ind)为0时，说明当前个体覆盖了全部的变异分支，满足变异分支覆盖准则。

2.2.2 集合精简算子

集合精简算子用以调整种群中个体的规模，以寻找适当的测试用例集规模，生成较小规模的测试用例集，同时可在集合进化过程中节省存储空间。

集合精简算子由3部分组成，即去除最优个体的冗余基因获得其精简集Greedy_Essential()，估算适当的个体(测试用例集)规模estimate()和动态调整个体规模adjust()。

获得最优个体精简集Greedy_Essential()：个体中冗余的基因扩大了自身的规模，通过除去个体中的冗余基因，可以获得较小规模的个体，同时还可以节省存储空间。E贪心算法^[14]是一种常用的精简测试用例集方法，它在贪心算法的基础上加入了essential策略，即由essential策略和greedy策略组成，essential策略的主要思想是选取出必要的元素。本文中的个体是测试用例集，除去测试用例集中的冗余测试用例，即可对该测试用例集进行精简，因此，本文根据E贪心算法，设计Greedy_Essential()函数，对最优个体进行精简。假设被测程序的变异分支集为B，最优个体由m个测试用例组成，即best_Ind={x₁, x₂, …, x_m}，best_Ind覆盖的变异分支集为R_p，未覆盖的变异分支集为R_f，则该最优个体的适应度函数值为|R_f|；若测试用例x_i(x_i∈best_Ind)覆盖的变异分支集记为b_xi，则best_Ind中测试用例对应覆盖的变异分支集记为R={b_x1, b_x2, …, b_xm}, 那么Greedy_Essential()首先应用essential策略，选取出必要的测试用例，即某个变异分支只被best_Ind中的某个测试用例所覆盖，那么这个测试用例就不可能是冗余的测试用例，将该测试用例放入精简集refine_set并从best_Ind中删除，同时从R和R_p中删去其覆盖的变异分支，继续从best_Ind中选取必要的测试用例，放入精简集refine_set，直到R_p中不存在只被best_Ind中一个测试用例覆盖的变异分支为止。然后使用greedy策略，根据R中变异分支集的规模，从best_Ind中选取测试用例，每次选取R中最大规模元素对应的测试用例，放入精简集refine_set，并从R和R_p中删去该测试用例覆盖的变异分支，继续选取直到R_p中不存在变异分支。综上，选取出的所有测试用例组成了最优个体精简集refine_set。

估算个体合适规模estimate()：种群进化过程中，通过在个体中添加额外的测试用例以覆盖其未覆盖的变异分支，可以估算合适的个体规模。由于最优个体未覆盖变异分支数量最少，所以其在理论上需要添加的额外测试用例个数最少。因此，可以通过最优个体精简集规模|refine_set|加上其未覆盖变异分支数|R_f|作为估算的个体合适规模，即个体合适规模为Nt=|refine_set|+|R_f|。

调整个体规模adjust()：在每一轮种群进化过程中，根据估算的个体合适规模Nt=|refine_set|+|R_f|，对种群中的个体规模进行调整。比较当前种群中的个体规模与Nt的大小：若个体规模≥Nt，调整策略为：最优个体通过其精简集refine_set中加入|R_f|条测试用例，将规模调整为Nt，其他个体移除(|best_Ind|-Nt)条测试用例，将规模调整为Nt；若个体规模 < Nt, 调整策略为：在种群中的个体中加入(Nt-|best_Ind|)条测试用例，将规模调整为Nt。

2.2.3 种群更新策略

集合进化的种群更新update()采用(μ+λ)更新策略，即在进化过程中保留父代与子代中的优秀个体，易导致种群失去多样性。结合进化策略中(μ，λ)更新^[15]中只在λ个子代个体中择优选择μ个个体组成下一代种群，本文设计一种新的种群更新策略(μ，λ+1) 更新策略，μ表示当前种群中有μ个父代个体，λ+1表示从λ个子代个体与1个父代最优个体组成的临时种群(要求λ+1>μ)中根据适应度值择优选择出μ个个体组成下一代种群，不仅保证了种群的多样性，同时保证了种群进化的质量不会下降。

3 实验

为验证本文方法能否在不受个体初始规模影响的前提下，生成较小规模的弱变异测试用例集并降低执行开销，设计实验，分析比较文献[8]中的基于集合进化的弱变异测试用例集生成方法和本文提出的基于动态集合进化的弱变异测试用例集生成方法在生成的测试用例集规模和执行时间上的优劣。

3.1 基准程序

实验以5个变异测试常用的Java程序作为基准程序^{[5, 8]}, 其程序的ID、总代码行数、生成的变异分支数以及程序说明如表 1所示。

3.2 研究问题

为验证本文的动态集合进化算法在生成弱变异测试用例集时，是否能不受个体初始规模的影响，生成较小规模的测试用例集并降低执行开销，本文从以下两个方面进行研究：

1) 利用动态集合进化算法实现弱变异测试用例集自动生成时，个体初始规模对其最终生成的测试用例集规模是否有影响？与使用集合进化的弱变异测试用例集生成方法相比，能否生成更小规模的测试用例集？

2) 利用动态集合进化算法生成弱变异测试用例集，相比于基于集合进化的弱变异测试用例集生成，其执行开销是否有所降低？

3.3 实验过程

首先，利用MuClipse工具^[16]对表 1所示的5个基准程序实施15种方法级运算符变异操作，如算术运算符替换操作、逻辑运算符插入替换等操作，形成变异分支，并将所有变异分支插入原程序相应位置，形成插桩后的被测程序，其相应的变异分支数如表 1第4列所示。

然后，利用集合进化算法和本文提出的动态集合进化算法，生成基准程序的弱变异测试用例集。集合进化算法采用分支距离作为其适应度，计算方法如表 2所示，T、F列分别表示条件语句为真(T)、假(F)时分支距离。

为保持实验结果的可比性，两种算法使用相同的参数，即种群规模为100，集合内部的交叉概率P_inner为0.2，集合间交叉概率P_inter为0.7，集合变异的概率P_mutation为0.1。

实验环境为Intel Core i7-4790 CPU 3.60GHz，4.00GB内存，采用Microsoft Windows 7 64位操作系统和Eclipse SDK 4.2.2集成开发环境。

3.4 结果与分析

对于表 1程序，分别以本文提出的动态集合进化算法(DSEA)与集合进化算法(SEA)生成弱变异测试用例集，生成的测试用例集规模如表 3所示。

为探讨基于动态集合进化算法的弱变异测试用例集生成方法最终产生的测试用例集规模是否受个体初始规模的影响，本文对5个基准程序，在5组个体初始规模下，进行弱变异测试用例集生成。每个程序第一组个体初始规模的设置参照文献[8]的个体初始规模值，随后个体规模以5递增，每组实验重复十次，生成的弱变异测试用例集平均规模如表 3所示。

由表 3可知，利用动态集合进化算法实现弱变异测试用例集生成时，其生成的测试用例集规模不受个体初始规模的影响，并且约简率最低为31.98%，平均为50.15%，约简率是指最终生成的测试用例集约简规模与个体初始规模的比值。

此外，实验还讨论了个体初始规模小于所需测试用例集规模的情况，结果如表 4所示。

由表 4可以看出，即使个体初始规模较小，利用动态集合进化算法(DSEA)仍能生成所需的测试用例集，满足弱变异测试准则。而集合进化算法(SEA)在个体初始规模小于所需测试用例集规模时，无法生成覆盖全部变异分支的测试用例集。

集合进化算法应用于弱变异测试用例集生成时，其生成效率受个体初始规模影响，且最终生成的测试用例集规模即为个体初始规模。而动态集合进化算法其最终生成的测试用例集规模不受个体初始规模影响，且生成的测试用例集规模很大程度上接近所需测试用例集的最小规模。

为分析对比动态集合进化算法和集合进化算法在生成弱变异测试用例集的时间开销，本文对5个基准程序，参照表 3最终生成的测试用例集规模设置个体初始规模，重复进行10次弱变异测试用例集生成，其生成的测试用例集规模和执行时间如表 5所示。

由表 5可知，利用动态集合进化算法生成的弱变异测试用例集规模更小，其执行时间也更少。执行时间减少最多的是程序J2，比集合进化算法降低了74.58%，程序J4的执行时间也降低了64.13%。从表 1可以看出，J2和J4的程序规模较大，生成的变异体数量也较多，因此可以认为，被测程序的变异分支数越多，动态集合进化算法越适用，弱变异测试用例集生成效率越高。

为更直观地对比两种算法的弱变异测试用例集生成时间开销，图 2(a)(b)分别给出了J2和J4 10次重复生成弱变异测试用例集的执行时间，并按执行时间升序排列。由图 2可以看出动态集合进化算法应用于弱变异测试用例集生成时，其执行时间明显少于集合进化算法。

为分析比较两种算法在不同个体初始规模下，对弱变异测试用例集生成所需时间的影响，本文设置了5组不同的个体初始规模，图 3(a)(b)分别给出了程序J2和J4在不同个体初始规模下的测试用例集生成时间开销。

由图 3可以看出，不同的个体初始规模下，动态集合进化算法实现弱变异测试用例集生成的执行时间明显低于集合进化算法。所以，利用动态集合进化算法生成弱变异测试用例集，相比于基于集合进化的弱变异测试用例集生成，其执行开销明显降低。

4 结语

测试用例集的自动生成一直是软件工业界关注的重点。本文在弱变异测试准则转化为变异分支覆盖准则的基础上，研究如何高效快速地生成较小规模的弱变异测试用例集。基于此，本文提出一种基于动态集合进化算法的弱变异测试用例集生成方法，以测试用例集为个体，在进化过程中根据执行信息动态调整个体规模，寻找适当的测试用例集规模，生成较小规模的测试用例集，降低执行开销和节省存储空间；同时设计了一个适用于集合进化的适应度函数，以降低计算开销。研究表明基于动态集合进化的弱变异测试用例集生成方法在执行开销和生成的测试用例集规模得到了极大的改善，提高了弱变异测试效率。