变异测试

变异测试背景

变异意味着不同、变化和产生新知识。
正向变异：修复错误的程序、产生新的测试用例；
反向变异：产生错误的程序片段、生成恶意测试用例。

测试人员一般比较关注这两个问题：如何产生好的测试用例？这一测试用例应当尽可能地反映出系统的缺陷。如何评估测试套件的质量？这一评估方式应当提高测试的置信度。变异测试在生成测试用例和评估软件测试的过程中显示出了优越性。

变异测试的产生，主要通过模拟缺陷与量化缺陷监测能力两个部分。模拟时变异产生错误版本，模拟探测 $\mathrm{Bug}$ 的过程；量化时来评估变异得分。

变异测试的一些基本概念

变异体：基于一定的语法（$\mathrm{Syntax}$）变换规则，通过对源程序进行程序变换）（$\mathrm{Program}\mathrm{Transformation}$）得到的一系列变体。

变异得分：变异测试对测试套件错误检测能力的量化。定义杀死为变异体导致某个测试用例运行失败，即测试用例检测到变异体，其数量为 $mu{t}_k$；存活反之，其数量为 $mu{t}_s$​。那么变异得分的公式为

$$score=\frac{mu{t}_k}{mu{t}_k+mu{t}_s}\times 100\mathrm{\%}$$

缺陷传播的三种过程

• $R\mathrm{\&}E$：缺陷所在的位置可以被执行到（$\mathrm{Weak}\mathrm{Mutation}$）
• $I$：缺陷的执行影响了程序的状态（$\mathrm{Firm}\mathrm{Mutation}$）
• $P\mathrm{\&}PR$：程序状态的影响传播到了输出（$\mathrm{Strong}\mathrm{Mutation}$）

杀死条件：可观测的程序输出（$P\mathrm{\&}PR$）；程序的中间态（$I$​）；

变异体的分类

• 等价变异体：变异体与待测程序语法不同，语义相同；
• 重复变异体：变异体之间语法不同，语义相同；
• 蕴含变异体：若能杀死变异体 $A$ 的测试用例都能杀死变异体 $B$，则 $A$ 蕴含 $B$。这种蕴含是基于语义的，而不是基于测试用例的。

变异算子：一系列语法变化规则，是变异的依据，反映出测试人员关注的缺陷种类。它的基本形式有：对程序的源代码进行变换；对程序的编译结果或中间表示进行变换，如更改字节码；元变异。

变异测试为什么是有效的？

变异测试的有效性基于三个假设：

• 缺陷是简单的，且是可模拟的：一个老练程序员编写的错误程序与正确程序相差不大。
• 缺陷是可以叠加的：复杂变异体可以通过耦合简单变异体得到。
• 缺陷的检测是有效的：测试用例具备缺陷检测能力。

变异测试过程

变异测试的在实际应用中的主要流程分为变异分析（变异体筛选、变异体生成、变异体优化、变异体执行、变异得分计算）和变异应用，如下图。

变异测试和变异应用的主要流程

变异体筛选和约减

变异体筛选是变异测试的第一步，目的是减少变异体的数量，提高变异测试的效率。主要的方法在于仔细地选取有效的变异算子集。

变异算子是一组语法转换规则，它反映了特定的缺陷类型。变异算子可以根据不同的编程语言、不同的应用场景以及不同的 bug 类型来进行设计。变异算子的设计是提升变异体质量的关键。

变异算子的具体例子

以下是来自 PITest 的一些基础的变异算子的例子：

Name	Transformation	Example
Cond. Bound.	Replaces one relational operator instance with another one (single replacement).	$<$ ↦ $\le$
Negate Cond.	Negates one relational operator (single negation).	$==$ ↦ $\ne$
Remove Cond.	Replaces a cond. branch with true or false.	if (...) ↦ if (true)
Math	Replaces a numerical operator by another one (single replacement).	$+$ ↦ $-$
Increments	Replace incr. with decr. and vice versa (single replacement).	$++$ ↦ $--$
Invert Neg.	Removes the negative from a variable.	$-a$ ↦ $a$
Inline Const.	Replaces a constant by another one or increments it.	$1$ ↦ $0$, $a$ ↦ $a+1$
Return Values	Transforms the return value of a function (single replacement).	return 0 ↦ return 1
Void Meth. Call	Deletes a call to a void method.	void m() ↦ $\mathrm{\varnothing }$
Meth. Call	Deletes a call to a non-void method.	int m() ↦ $\mathrm{\varnothing }$
Constructor Call	Replaces a call to a constructor by null.	new C() ↦ null
Member Variable	Replaces an assignment to a variable with the Java default values.	a = 5 ↦ a
Switch	Replaces switch statement labels by the Java default ones.

变异体约减旨在从变异体全集中选出具有代表性变异体子集。约减的目的是减少变异体的数量，提高变异测试的效率。主要的约减策略有：随机选取、基于类型的约减（某种类型的变异体可能更加重要）、基于分布（可以利用 $\mathrm{AST}$ 的分布信息来选取更分散全面的变异体）。

变异体生成

变异体生成的过程即将各个变异算子实例化为变体的过程。由于变体的数量可能会非常庞大，所以如果将所有的变体都生成为源文件，那么会导致很大的时间和空间开销。因此，变异体生成技术包括元变异、基于中间表示的变异和热替换等。

元变异由程序模板和部分编译组成。它的形式上类似于一般程序，但是包含自由标识符，使得在完全编译时可以用一些符号替换程序中的结构。利用元变异，可以减少生成变异体时所需的编译次数并集中存储变异体。

基于中间表示操作的变异体生成直接产生中间代码，避免了编译，从而减少时间开销。常见的中间表示有 $.\mathrm{Net}$、$\mathrm{Java}\mathrm{Bytecode}$、$\mathrm{LLVM}\mathrm{IR}$ 等。

变异体优化

变异体优化的目的是去除有等价和无效变异体，减少后续执行变异体阶段的开销并提高变异得分的可信度。目前主要的变异体优化方法有代码优化（比较代码优化后的代码是否相同）和静态数据流分析法。

变异体执行

变异体执行是变异测试中开销最大的环节。我们假设程序有 $m$ 个变异体和一个含有 $n$ 个测试用例的测试套件。那么，变异体执行的所有次数为 $m\times n$。

变异体执行的优化策略主要是去优化变异得分和变异体矩阵的计算过程：

• 改变测试用例的顺序（$\mathrm{TCP}$），先执行能杀死更多变异体的测试用例；
• 匹配测试用例与变异体；
• 避免执行必定存活的变异体；
• 严格限定变异体的执行时间。

变异得分计算

计算被杀死的变异体数量，进而得到变异得分、量化测试的充分性。在这一阶段，还需要研究变异杀死的条件，设计出更好的预言。

变异测试应用

• 评估作用：利用变异得分度量测试的充分性
• 引导作用：利用变异测试/分析的结果来引导测试过程
• 传统应用：应用于确定性系统
  • 用例和预言生成
  • 测试优化（排序 & 选择）
  • Debug引导（缺陷定位 & 自动修复）
• 变异 & $\mathrm{AI}$：应用于非确定性系统（$\mathrm{DNN}$）

用例和预言生成

用例和预言的生成主要采用 $\mu \mathrm{Test}$ 方法，即遗传算法 + 变异分析，在用例生成时采用神经网络建模（包括杂交、突变和适应性方程）的方法，通过对程序行为的分析来生成预言。

杂交指交换两个体（测试用例）的部分语句，突变指对测试用例进行删除、插入、修改。而适应性方程为 $f(t)=\frac{1}{D_f(t)+D_m(t)}+I_m(t)$，其中 $D_f(t)$ 为测试用例 $t$ 执行（某些）变异体所需要生成方法调用和参数的数量，$D_m(t)$ 为测试用例 $t$ 的执行变异语句的距离，$I_m(t)$ 为变异体本身造成的影响。适应性方程的值越大越好。通过这三种方法，可以搭建起神经网络，来生成更优质的测试用例。

预言生成的主要思路是生成断言以杀死变异体。通过添加能够杀死变异体的断言语句来检测到变异体与源程序之间的不同行为。添加的断言一般分为以下种类：

• 初级类型断言
• 对象类型断言
• 检查器断言
• 域（成员变量）断言
• 字符串断言

变异辅助 Debug

利用变异自动为有缺陷程序推荐补丁。主要分为定位和修复两个步骤。定位过程时利用变异测试结果抽象测试轨迹，并利用这些轨迹计算程序组件的可疑度，再以可疑度作为指标，挑选出最有可能的缺陷组件。修复过程时根据一定的语法规则转换缺陷程序为正确版本，类似变异的逆向过程。

总结 重点

变异测试总结