党向盈，李金凤

(徐州工程学院信息工程学院，江苏 徐州 221018)

dangpaper@163.com;41407770@qq.com

1 引言(Introduction)

软件测试是保障软件产品质量的一种有效方式。随着科学技术的飞速发展，软件产品的复杂性越来越高，规模也越来越大，这也导致软件缺陷越来越隐蔽，采用传统的检测方法很难检测出软件的顽固缺陷[1]。实施自动化软件测试技术时，需要测试数据执行程序，同时测试数据是检验程序缺陷的重要手段，因此测试数据的质量尤为重要[2]。

变异测试是一种面向缺陷的软件测试技术，它通过对程序语句合乎语法的改变，模拟真实的缺陷[3]。通过这种方式，对模拟的缺陷生成测试数据，保障测试数据集的充分度。在结构覆盖测试技术中，覆盖率最高的是路径覆盖测试技术。路径中包含的节点是程序的语句，所以覆盖一条路径的测试数据能覆盖很多程序语句，那么路径覆盖所得的测试集规模也比较小，冗余测试数据少。

本文借鉴变异测试和路径覆盖技术生成能检测缺陷的测试数据。变异测试模拟缺陷，融合原程序路径，覆盖路径生成的测试数据，也能覆盖缺陷，而且生成的测试数据集规模比较小。

2 测试数据生成方法(The proposed method of test data generation)

结构化的路径覆盖测试所生成的用例是为了覆盖目标路径，即使路径覆盖率高，也不能代表检测缺陷率高。此外，传统的方法生成测试数据效率比较低，考虑到进化算法已经广泛应用[4]，本文采用遗传生成测试数据覆盖融合缺陷的路径。

变异测试和路径覆盖测试技术结合的测试数据生成方法的基本框架如图1所示。首先基于变异测试技术生成变异体，并转化为变异分支，用于模拟程序的缺陷，再将这些变异分支(缺陷)融入程序；同时，在原程序路径集中选择多条目标路径。然后，将变异分支融入原程序生成新被测程序；通过分析变异分支与原语句之前的相关性，将变异分支融入目标路径。最后，基于遗传算法生成覆盖路径的测试数据。

图1 变异测试和路径覆盖测试技术结合的测试数据 生成方法的基本框架Fig.1 Basic framework of test data generation method based on mutation testing and path coverage testing

2.1 基于变异测试技术模拟程序缺陷

变异测试技术不仅可以根据程序或语句的特征模拟真实软件中的各种类型的缺陷，也可以基于程序的复杂情况，针对性地选择缺陷发生位置和注入缺陷的数目[5]。因此，变异测试被认为是一种方便、灵活、个性化的技术。

在实施变异测试时，通过变异算子对原程序语句实施变异操作，比如原语句为“a>b”,实施变异之后，生成变异语句“a==b”。将变异语句替换原来的语句，得到新的被测程序定义为变异体。每一个模拟的缺陷对应一个变异体。在实施变异测试时，一个程序通常会产生大量的变异体。某一测试数据同时执行原程序和变异体，如果两者的输出结果不一致，那么该用例以强变异测试准则杀死变异体。而且，为了杀死这些变异体，需要大量的测试数据执行变异体和原程序，导致变异测试代价非常高昂[6]。

为了克服以上不足，文献[6]提出弱变异测试思想，将变异体转化为变异分支。具体方法是根据变异测试的必要条件，将原语句和变异语句构建if条件语句的分支，形成变异分支。如果某一测试数据覆盖了变异分支，那么基于弱变异测试准则杀死变异体。图2(a)为三角形类型判断程序的部分源代码，如果对语句实施变异，得到变异语句。然后，基于文献[6]提出的方法进行弱变异测试转化，构建变异分支；采用同样的弱变异测试方法，对语句实施变异，得到图2(b)中的16 个变异分支，分别表示为。将这些变异分支插入原语句的前面，得到新的被测程序。

图2 示例程序Fig.2 Sample program

插入原程序的变异分支，代表一些模拟缺陷。如果某一测试数据覆盖某一变异分支，说明基于弱变异测试准则杀死了对应的变异体，也就是说，生成的测试数据可以用于检测这个模拟的缺陷。

2.2 基于相关性变异分支融入路径

变异分支插入原程序后，生成新的程序。考虑到原程序中可以通过路径覆盖生成测试数据，对于新程序，为了生成覆盖变异分支的测试数据，可以将这些变异分支融入已有原程序路径，这样，生成的测试数据不仅满足路径覆盖准则，也满足变异测试准则。

为了将变异分支融入原程序路径，首先，在原程序路径集中选出若干目标路径；然后，在新程序中判断原语句与变异分支的相关性，生成相关子路径；最后，基于原语句所在目标路径将变异分支插入目标路径，形成新的目标路径。以图2为例阐述基于相关性变异分支融入路径的方法。在原程序路径集中选择目标路径，可以得到：

需要说明的是，路径集中可能包含很多路径，针对挑选目标路径的原则：(1)尽量选择包含路径节点比较少的路径。(2)挑选的目标只是初选，如果所有变异分支都无法融入，该路径将被删除。(3)目标路径中，还有未融入的变异分支，将从路径集中重新挑选路径。

2.3 基于遗传算法生成测试数据

遗传算法是由自然界的遗传和进化理论启发而来，是一种被广泛使用的全局搜索的优化技术。近年来，遗传算法已经广泛应用于软件测试中[9]。

本文采用遗传算法时，遗传操作包括轮盘赌选择方法，即单点交叉和单点变异。交叉概率和变异概率分别为0.9和0.3。考虑到目标路径有多条，本文采用单种群遗传算法(Single Population Genetic Algorithm，SGA)和多种群遗传算法(Multi-population Genetic Algorithm，MGA)生成覆盖路径测试数据。单种群遗传算法生成测试数据时，一次运行算法只能针对一条路径生成测试数据。多种群遗传算法生成测试数据时，一次运行算法，多个种群针对多条路径生成测试数据，多种群个数设置为目标路径个数。

3 实验 (Experiments)

图3 三条目标路径采用单种群遗传算法的时间消耗 和迭代次数对比Fig.3 Comparison of time consumption and iteration number of three target paths using SGA

图4 三条目标路径采用多种群遗传算法的时间消耗 和迭代次数对比Fig.4 Comparison of time consumption and iteration number of three target paths using MGA

下面比较采用单种群和多种群生成测试数据的性能。由图5所知，对于路径，在时间消耗和迭代次数方面，因为实验具有一定的偶然性，所以单种群遗传算法偶尔优于多种群遗传算法，但从总体来看，多种群遗传算法生成测试数据方法明显优于单种群遗传算法。同理，由图6可知，对于路径，多种群遗传算法在时间消耗和迭代次数方面的性能也高于单种群遗传算法。由图7可知，对于路径，多种群遗传算法的性能也高于单种群遗传算法。

图5 采用单种群和多种群覆盖p1的时间消耗和迭代次数对比Fig.5 Comparison of time consumption and iteration number of covering p1 using SGA and MGA

图6 采用单种群和多种群覆盖p2时间消耗和迭代次数对比Fig.6 Comparison of time consumption and iteration number of covering p2 using SGA and MGA

图7 采用单种群和多种群覆盖p3时间消耗和迭代次数对比Fig.7 Comparison of time consumption and iteration number of covering p3 using SGA and MGA

对于单种群遗传算法和多种群遗传算法，执行30 次的时间消耗和迭代次数平均值如表1所示。从表1中可以看出，覆盖所有路径时，单种群比多种群遗传算法消耗的时间更长，迭代次数更多。多种群遗传算法在时间消耗方面比单种群遗传算法少用7.02 s，时间节约幅度为41.15%。多种群遗传算法在迭代次数方面比单种群遗传算法少1,276.2 次，迭代次数降低24.33%。此外，对比覆盖三条目标路径的平均时间消耗和迭代次数可知，消耗时间最多，迭代次数也最多，说明路径最难覆盖；消耗时间最少，迭代次数也最少，说明路径最容易覆盖。

表1 单种群和多种群遗传算法时间消耗和迭代次数的平均值Tab.1 Average of time consumption and iteration numbers using SGA and MGA

4 结论(Conclusion)

本文所提出的基于变异测试的路径覆盖测试数据进化生成方法，创新性地将变异测试技术和路径覆盖测试技术结合，转化后的变异分支模仿缺陷，融入原程序路径，生成的测试数据不仅规模小且能够用于检测缺陷。考虑到遗传算法有利于提高测试数据生成效率，针对多条路径，采用多种群遗传算法，每个子种群负责一条路径测试数据的生成。实验结果也验证多种群遗传算法明显优于单种群遗传算法。