Randoop 和Evosuite 生成测试用例的变异检测能力分析

郭丹

（四川大学计算机学院，成都610065）

0 引言

单元测试是软件测试过程的重要一环，编写高质量的单元测试用例可以提高测试的效率，但费时费力。单元测试用例自动生成工具可以自动生成大量测试用例，但这些测试用例质量有待评估。评估测试用例质量的一种常用方法是变异测试。变异测试将人工缺陷（变异体）种植到被测代码中，并评估测试用例是否找到它们。当一个测试用例检测到一个变异体时，说明该变异体被杀死[1]，否则变异体仍然存活。

本文选择Randoop 和Evosuite 这两个积极维护的自动化生成单元测试的工具，muJava 变异工具，以数据结构教材中的基本数据结构项目作为被测项目进行变异测试，通过比较Evosuite、Randoop 生成的测试用例的变异检测能力，以回答下面2 个研究问题：

问题1：两个工具生成的测试用例在变异测试中的整体表现如何？

问题2：每个工具在检测不同变异体方面各自有什么优势？

1 相关工作

为了研究自动生成的单元测试用例是否能找到真正的缺陷，Sina Shamshiri 等人针对defects4j 上的五个项目，利用单元测试生成工具Randoop、Evosuite 以及AgitarOne[2]生成的测试用例，将检测到的缺陷与实际的缺陷报告进行比较。实验结果表明：几种测试生成工具共发现55.7%的缺陷，但没有单独的工具发现超过40.6%的缺陷[3]。

为了研究变异体与真实缺陷的关系，Sina Shamshiri 等人[4]针对数据集Defects4J，利用自动化测试生成工具Randoop、Evosuite、JCrashe[5]生成测试用例，用变异工具Major[6]进行变异测试，发现变异体可以有效替代真实缺陷，即变异分数可以体现测试用例发现真实缺陷的能力。

M.Moein Almasi 等人[7]对自动化测试生成工具的有效性进行了评估。但是使用的数据集是工业界的项目——LifeCalc（由SEB Life＆Pension Holding AB Riga Branch 内部拥有和开发的相对复杂的金融应用程序），他们从该软件项目的版本历史中提取了25个真实缺陷，并应用了Evosuite 和Randoop 这两个单元测试生成工具，分别实现了基于搜索和反馈的随机测试生成。自动生成的测试用例检测到这些缺陷的高达56.40%（Evosuite）和38.00%（Randoop）。

2 实验方法

图1 是实验流程图。对于每一个被测项目，Randoop 和Evosuite 分别对其生成测试用例；变异工具muJava 对每个被测项目生成变异体，之后进行变异测试得到变异分数。

图1 实验流程图

2.1 被测系统

基本数据结构及其算法是程序设计和软件项目开发的基础，是实际项目开发中的基本组成部分。本文选择数据结构教材Data Structures and Algorithm Analy⁃sis[8]中的基本数据结构项目作为被测项目，可以分析自动化单元测试工具在基本数据结构项目上的表现。该数据集包含了常用的数据结构，其中包含了链表、队列、栈、二叉树、图，以及各类查找、排序算法等。原始数据集的类文件分布比较杂乱，个别项目中包含了与实现该种数据结构无关的类文件，经过整理后共有46个项目，共有76 个类、327 个方法。

2.2 自动化单元测试工具选择

实验采用目前最流行的两个单元测试工具Randoop 和Evosuite。Randoop[9]是随机单元测试生成工具，它实现了面向对象程序的反馈随机测试生成。这意味着它迭代地扩展随机选择的方法调用序列，直到生成的序列引发未声明的异常或违反一般代码契约。Randoop 还执行其生成的序列，并创建捕获被测试类行为的断言。但是，Randoop 不能将测试中的特定类作为目标，因为它使用自底向上的方法，该方法要求方法调用的所有依赖项。因此，Randoop 需要在测试生成过程中查看所有类的列表作为输入。本文实验在每次运行中使用默认设置。

Evosuite[10]是基于搜索的单元测试生成工具，它是应用一个遗传算法来发展一组测试用例，使代码覆盖率最大化。Evosuite 是从随机测试用例的测试用例开始，然后迭代地应用搜索操作符（如选择、突变和交叉）来进化它们。由于Evosuite 可以针对特定的测试类，因此可以对每个被测类生成一个测试用例。Randoop在生成测试用例时默认时间时100 秒，为了公平起见，在使用Evosuite 时，也将搜索时间也设置为100 秒，其他参数默认。

2.3 变异测试工具选择

muJava[11]是一种用来对Java 程序产生变体，进行变异测试的一个工具。它自动为方法级别变异测试和类级变异测试生成突变体，同时在源程序和变异程序上执行测试用例（利用Junit 生成的测试用例），区分出可存活和不可存活的变异体。在本次实验中，选择muJava 对自动化单元测试生成工具Evosuite、Randoop生成的测试用例进行变异测试。

2.4 实验过程

为了使用Evosuite 和Randoop，需要对原始代码进行处理。Randoop 对于不确定性的Random（)方法会生成不稳定的测试，因此按照Randoop 手册上的处理方法对该方法进行了填0 操作。main 函数是应用程序的入口，类似于一个测试驱动，可以对其他的方法进行调用，而本身不能被调用，所以生成的测试用例无法完全覆盖main 函数中的代码，就会造成覆盖率降低。因此本实验注释了main 函数。

（1）测试生成

Randoop 使用的技术是随机地为被测类生成方法或构造函数的调用序列，而Evosuite 应用遗传算法来进化一组随机测试用例的测试用例。为了减小这种随机性，对Evosuite、Randoop 都生成3 组测试用例，将不可编译的测试用例丢弃，再生成新的测试用例。

（2）去除不稳定的测试

为了使测试检测到真正的缺陷，要求测试用例在运行时全部通过。但是，工具可能会生成不稳定测试，即在第一次执行时通过但第二次执行时却不通过。因此，将可编译的测试用例在被测项目上运行2-3 次。如果有不稳定的测试用例，那么就会去除这一组测试用例，重新生成，重新编译和执行直到每次都通过测试。

（3）生成变异算子

在生成变异算子时，需要将源程序的Java 文件放在muJava 的src 文件夹下，源程序的class 文件放在muJava 的class 文件夹下，测试用例的class 文件放在muJava 的tests 文件夹下。运行GenMutants.cmd，勾选需要进行变异的Java 文件，muJava 的变异算子有方法级别和类级别的变异算子。在本实验中，为了使自动测试生成工具Evosuite、Randoop 生成的测试用例在每次生成变异算子的过程中尽可能生成多种变异算子，将方法级别和类级别的变异算子全部选择。

（4）变异测试

运行RunTest.cmd。因为在生成变异算子时将方法级别和类级别的变异算子全部选择，所以在进行变异测试时应该选择执行所有的变异算子，即：“Execute all mutants”，从而得到方法级别的变异分数即Traditional Mutants Result 和类级别的变异分数即Class Mutants Result。

3 实验结果

在本节中，将讨论实验结果并回答第一节提出的研究问题。

Evosuite、Randoop 分别为每个测试类生成3 组测试用例并进行变异测试，对这3 组测试用例的方法级别变异分数、类级别变异分数求平均值进行分析。

3.1 两个工具生成的测试用例在变异测试中的整体表现如何？

变异分数是被杀死变异体体与生成的变异体总数的比例[12]，变异分数越高说明测试用例杀死的变异体数量越多。对实验过程中Evosuite、Randoop 测试用例的变异分数进行了统计，并分别绘出Evosuite、Randoop测试用例在杀死方法级别、类级别变异体时变异分数的小提琴图，分别如图2、图3。

在生成方法级别变异体的68 个类：其中9 个类（占总类的8%）的Randoop 测试用例的变异分数达到100%，可以杀死所有的变异体。在图2 方法级别小提琴图中：Evosuite 测试用例的变异分数存在较明显的离散值（下侧须细长），中位数在50%左右，在40%—60%之间变异分数分布最密集；Randoop 测试用例的变异分数虽存在离散值，但明显密度小于Evosuite，中位数在60%，且在40-60%、80-90%之间变异分数分布最密集。

在生成类级别变异体的53 个类中：24 个类（占总类的45%）的Evosuite 生成的测试用例的变异分数达到100%；而在Randoop 生成的测试用例中，28 个类（占总类的53%）的变异分数达到100%。观察其小提琴图发现：Evosuite 测试用例的变异分数中位数在60%，且变异分数密集分布在80-100%以及0-20%这两个区间内；Randoop 测试用例的变异分数中位数在100%，在大部分变异分数密集集中在80-100%。

图2 方法级别变异分数小提琴图

图3 类级别变异分数小提琴图

对于Evosuite、Randoop 生成的测试用例，无论是在杀死方法级别的变异体还是类级别变异体，Randoop生成的测试用例的变异分数高于Evosuite，即Randoop生成的测试用例可以杀死更多的变异体。

3.2 每个工具在检测不同变异体方面各自有什么优势？

在本项目的68 个类中，针对muJava 生成的15 种方法级别的变异体，在进行变异测试后每种变异体分成三种情况：部分变异体存活的（live）类的个数、变异体存活率为100%（live-100%）的类的个数和变异体全部被杀死（killed-100%）的类的个数，这三种情况某种变异体类的总和是生成某种变异体类的总数。并分别统计了所有被测类生成的每种变异体在这三种情况下的数量分布。结果如图4。

图4 变异体检测结果统计图

（1）Randoop 测试用例在检测COR（改变逻辑运算符）、ROR（改变关系运算符）类型变异体的能力与Evosuite 相同，都可以将COR 类型的变异体全部杀死，8个类的ROR 变异体被全部杀死。

（2）在检测VDL（删除某个变量）、CDL（删除某个运算常数）、ODL（删除某个变量或者运算常数）类型的变异体时，图3 中变异体的检测统计结果可以明显看出Randoop 测试用例在检测这些类型变异体的能力优于Evosuite 生成的测试用例。

（3）Randoop 测试用例在检测SDL、COI、AOIU、LOI类型变异体的能力略优于Evosuite 生成的测试用例。

在检测COI（改变真值运算符）、SDL（语句删除）、AOIU（改变变量正负号）、LOI（改变位运算符）类型的变异体时，Randoop 测试用例将这些变异体全部杀死的类的数量多于Evosuite，其中SDL、AOIU、LOI 类型的变异体全部存活的类的个数Evosuite 总是比Randoop 少1 个。

（4）Evosuite、Randoop 测 试 用 例 不 善 于 检 测AORB、AOIS 类型的变异体。

在生成AORB（改变二元运算符）类型变异体的23个类中，Evosuite 测试用例在进行变异测试时，只有一个类中的变异体被全部杀死；Randoop 测试用例仅将3个类中的AORB 变异体全部杀死。

在41 个生成AOIS（插入一元运算符）变异体的类中：Randoop 测试用例仅将一个类的AOIS 变异体全部杀死，而Evosuite 测试用例进行变异测试时，没有一个类的AOIS 变异体被全部杀死。

（5）Evosuite 测试用例在检测ASRS、AODU、AORS类型变异体的能力优于Randoop。

在生成了ASRS（赋值运算符替换）类型的变异体的3 个类中，Evosuite 测试用例可将其中一个类的ASRS 变异体全部杀死，但是在利用Randoop 测试用例进行变异测试时，3 个类中ASRS 变异体的存活率都为100%。

在生成AODU（改变返回值）类型变异体的6 个类中，Evosuite 测试用例可将所有的AODU 变异体全部杀死；Randoop 测试用例只将其中3 个类生成的AODU类型变异体全部杀死。

在生成AORS（算术运算符插入）类型变异体的27个类中，从有AORS 存活的类的个数，还是AORS 被全部杀死的类的个数上看，Evosuite 生成的测试用例优于Randoop 生成的测试用例。

整体来说：在检测ASRS、AODU、AORS 这三种类型的变异体时，Evosuite 测试用例比Randoop 测试用例杀死更多数量的变异体；但在剩余的12 种类型的变异体中，Randoop 测试用例比Evosuite 测试用例杀死更多数量的变异体。

3.3 实验有效性的局限

对于每个选定的工具，Evosuite 和Randoop 使用的都不是最新版本，并且没有对参数进行设置，如果使用最新版本或对对某些参数进行设置，这些工具可能会表现得更好。

另外，Randoop 是为整个项目生成了测试用例，它没有针对特定的测试类，相比之下，测试用例数量较多；而Evosuite 专门针对所选择的单个的类生成测试用例，从而导致测试用例数量较少。在本次实验中，Evosuite 生成的测试用例数量远远少于Randoop，这也有可能是导致Randoop 的变异分数明显高于Evosuite的原因。

为了保证实验数据的可靠性，将三组测试用例的变异分数求平均值用以分析。实验中三组测试用例的变异分数不尽相同，如果采用变异分数中最大值或最小值，都会导致实验结果有偏差。

4 结语

本实验通过对自动生成的单元测试用例杀死变异体的效果、Randoop 和Evosuite 对muJava 生成的15 种方法级别变异体的检测效果以及变异分数分析发现，对于小型项目：①Randoop 生成的测试用例的变异分数整体明显高于Evosuite；②在检测ASRS、AODU、AORS这三种类型的变异体时，Evosuite 测试用例比Randoop测试用例杀死更多数量的变异体；在剩余的12 种类型的变异体中，Randoop 测试用例比Evosuite 测试用例杀死更多数量的变异体。

在未来的工作中可以通过添加手工编写的测试用例或者对Evosuite、Randoop 进行参数设置改进自动生成的测试用例，杀死更多的非等价变异体。

阻碍变异测试广泛应用的主要障碍之一就是等价变异体的检测问题。等价变异体不仅对提高变异分数没有帮助，而且长期滞留在测试过程中将耗费极大的计算开销，可以将基于约束测试技术应用于自动化测试用例生成工具，尽早地将等价变异体检测出来，以提高变异测试的效率。