引用
Ji C , Chen Z , Xu B , et al. A Novel Method of Mutation Clustering Based on Domain Analysis.[C] Software Engineering & Knowledge Engineering. 2009.
1. 摘要
突变测试主要目的是减少突变体和要执行的测试用例的数量而保证简化后的突变集仍然足够有效。其中之一的技术突变聚类整合了数据聚类和突变分析，使得突变集和测试集可以大大减少。本文修改了现存的突变聚类，目的是提供一种可以在测试用例之前静态指导聚类突变体的方法，然后使用简化的突变集生成测试集，我们假设生成的测试集可以杀死大部分的原始突变集。因为只需要生成并执行一个较小的测试集，所以突变测试的成本将会大大降低。实验得出了支撑我们假设的令人振奋的结果。
2. 介绍
突变测试是有效的错误侦探方法，很有可能能够发现程序中的大多数故障，但突变测试的计算成本很高昂，会耗费过多的人力和时间成本。人们引入了许多策略以减少计算开销。被称为“do smarter”的突变技术主要关注在突变过程中何时对状态进行比较；被称为“do faster”的做法降低了在相同的环境中运行突变体的成本。显然，“do fewer”方法很容易，该种方法意味着在更少的突变体上执行较少的测试用例。关键思想是执行重要的突变体以节省资源，突变体的数量由突变算子决定，最小化突变算子将可以起到很好效果。
本文的组织如下：第 3 节介绍了突变聚类的相关工作；第 4 节提出了一些减少域的策略，因为相关变量的域可以帮助区分突变体；第 5 节展示了实验结果和分析；第 6 节提出了未来的一些改进方向。
3.突变聚类
在突变体被聚合之前，将执行所有测试用例和突变体，结果用于评估突变体。我们应用静态方法来度量所有突变体，静态方法不需要执行突变体且可以对突变聚类起到改进作用。对于每个突变体，我们使用一些符号执行规则减少所有变量的域，可以让域减少的变量集被视为突变体代表，应用了具有实践成本的静态控制流分析。
可选模块和路径条件
如果一个突变体起作用，则执行必须满足基本条件：程序不会在突变点之前退出。
下图描绘了一个简单的程序，该程序在三种不同条件下具有三个可能的终点。我们将包含 return 语句的子句作为一个程序模块，将那些常规子句作为一些可选模块。这四个模块被视为入口节点的四个控制相关性节点。
程序的状态包括输入域、路径条件和指示要执行的下一个模块的路径计数器。以图中的示例为例，我们根据软件规范初始化所有输入域。通过执行路径时，路径条件会集成来自不同模块的条件。
突变体的减少条件
有三种类型的条件应组合在一起。
1.
退出避免条件：选择突变路径应避免程序退出。
2.
嵌套条件：在一个模块中，可能存在一些嵌套条件，所有达到突变点的相关条件应被满足。
3.
突变条件：突变算子在条件上产生句法差异，我们考虑了突变的条件，影响同一条语句的突变体具有相等的退出避免条件和嵌套条件。突变语句被视为突变条件，我们可以据此分辨出差异。
聚类的突变距离和中心
需要定义一种距离计算方法以应用聚类规则。汉明距离提供了一种解决方案。表 1 显示了汉明距离在我们的分析中的工作方式。A，B，C 和返回值代表 M1 和 M2 的可变度量。如果域不同，则引入 1。否则，距离为 0。然后将 1 的总和计为不同突变体的距离。在表 1 中，M1 和 M2 之间的距离为 3。
通过距离值，我们将类似 K-means 算法的过程应用于聚集突变体。首先，我们随机选择 k 个聚类，k 通常是总数的一半。然后，我们评估了从其余突变体到这 k 个类簇的距离，每个突变体将加入了距离小于特定值的聚类，然后 k 减半，重复该过程。由于域值的特殊性，很难直接计算两个或几个域的均值，我们任意选举代表突变体。k 个突变体参与下一轮聚类，突变体总数将减少到 k / 2。
4. 实验结果和分析
本节的目的是评估以下假设：域值也可以像测试用例的执行结果一样起到区分突变体的作用。从聚类生成的测试集可以显示出与原始测试集几乎相同的杀死突变体的能力。
实验步骤
1.首先，我们使用 muJava1 为程序 P 生成突变体 MF。根据案例程序的功能，丢弃类中的某些变异算子。
2.然后为 MF 设计测试集 TF，并用 MSF 突变评分进行评估。
3.我们在包括返回值的 P 中找到所有变量。
4.根据每个突变体的特征记录变量的域，我们将域作为每个突变体的度量。 5.现在，我们计算每两个突变体之间的距离。
6.选择为全部突变体总数一半的 k 和为最大距离值的一半的阈值。聚类随机选择 k 个突变体作为初始聚类。我们将距离小于阈值的突变体进行聚类。随机选择一个突变体代表一个聚类，这些突变体形成新的突变体集合 MN。
7.从 TF 中删除不能杀死任何突变体 MN 的测试用例，其余的测试用例构成了新的测试集 TN。
8.用 MSN 评估 TN 以杀死 MF，TF 和 TN 的效率通过不同的突变评分进行比较。 9.度量了突变体的质量以表明我们的方法可以有效降低突变测试的执行成本。如有必要，可以将 MN 聚类更多次，并且也可以减少 TN。
随着突变体的减少，测试用例被最小化，而测试用例功能仍然像原始测试集一样强大。积极的结果证明了我们的假设，即域值可以像测试案例一样保持突变体的强度。对突变体进行聚类提供了一种最佳解决方案，该方案使突变测试可以执行更少的突变体。
5. 结论与未来工作
我们的方法仅将一个变量作为依赖维度。当我们修改测量距离的策略时，定义将得到提升。如果一个域涉及另一个域，则将距离记录为 1，将完全不同的记录为 2。这样，我们可以扩展距离值的范围，突变体分类将获得更高的准确度。需要解决的第二个问题是如何确定聚类的中心。所有突变体均由变量域表示，缺乏一种方法来定义域的多个值的合理均值。案例研究的前期工作是手动完成的，我们将设想一个全自动系统来模拟突变聚类的整个过程。然后，我们可以将分析应用于更大范围的其他程序。我们希望它可以帮助降低运营成本并使突变测试切实可行。
