自动化测试 - 变异测试

背景

两个测试人员关心的问题

如何编写能够暴露缺陷的测试用例 $\rightarrow$ 如何引导测试
如何评估测试套件的质量（提升测试可信度） $\rightarrow$ 如何评估测试

变异测试的产生

模拟缺陷，量化缺陷检测能力，扮演测试有效性的指示器
模拟：变异产生错误版本，模拟探测 Bug 的过程
量化：变异得分（变异杀死率）

变异分析与变异测试

变异分析（Mutation Analysis） $\rightarrow$ $\to$ Research
- 自动化 “变异” 源程序以得到源程序语义变体，并对其进行优化和分析的过程 $\rightarrow$ 自动化生成人工缺陷
- 语义变体：语法上、语义上与源程序都不相同 $\rightarrow$ 变异体
- “变异”：程序变换规则 $\rightarrow$ 变异算子
变异测试（Mutation Testing） $\rightarrow$ $\to$ Practice
- 将变异体视作测试目标（Test Goal）
- 利用变异分析的结果来支持、评估、引导软件测试的过程

变异体

Mutant

变异体是基于一定的语法（Syntax）变换规则，通过对源程序进行程序变换（Program Transformation）得到的一系列变体

假设：

源程序不包含缺陷 $\rightarrow$ 现有的测试套件没有发现缺陷
变异体表达了某种缺陷 $\rightarrow$ 人工缺陷（Artificial Defect）

/**
 * 源程序
 */
public void foo(int x, int y) {
  if (x > y) {
    return x;
  } else {
    return y;
  }
}

/**
 * 变异体 Replace Return
 */
public void foo(int x, int y) {
  if (x > y) {
    return x;
  } else {
    return y;
  }
}

变异得分

Mutation Score

变异测试对测试套件错误检测能力的量化
杀死与存活：变异体是否导致某个测试用例运行失败；测试用例是否“检测”到某个变异体
- 检测到：变异体被杀死（Killed）
- 未检测到：变异体存活（Survived）
计算公式： $score = \frac{mut_k}{mut_s + mut_k} \times 100 \%$

变异杀死的条件

缺陷传播模型

变异杀死条件, Mutant Killing Condition

受程序行为（Program Behavior）的定义影响
程序行为
- （一般定义）可观测的程序输出：待测程序输出到标准输出的内容，或者被测试用例添加断言（Assert）的部分 $\rightarrow$ Propagation
- 程序的中间状态：程序执行某些操作后处在的状态（Program State） $\rightarrow$ Infection

变异分类

根据杀死条件的不同，变异可以分为三种
- Weak Mutation：变异导致紧随变化位置的程序状态发生了变化（R & E）
- Firm Mutation：变异导致原理变化位置的程序状态发送了变化（I）
- Strong Mutation：变异导致程序的输出发生了变化（P & PR）
Weak Mutation $\rightarrow$ Firm Mutation $\rightarrow$ Strong Mutation：变异的要求变高，变异体质量提升

分类：

有效变异体
夭折变异体（Stillborn Mutant）
冗余变异体（Redundant Mutant）
1. 等价变异体（Equivalent Mutant）
2. 重复变异体（Duplicated Mutant）
3. 蕴含变异体（Subsumed Mutant）

等价变异体

对于待测程序 $P$ 的变体 $mut$ ，如果 $mut$ 和 $P$ 的语法不同、语义相同，则称 $mut$ 是 $P$ 的等价变异体

语义相同：对于给定的输入，两个程序总能够给出相同的输出

例子：

源程序：

public void foo(int a) {
  int abs = 0;
  if (a > 0) {
    abs = a;
  } else {
    abs = -a;
  }

  return abs;
}

等价变异体：

public void foo(int a) {
  int abs = 0;
  if (a >= 1) {
    abs = a;
  } else {
    abs = -a;
  }

  return abs;
}

上述的两段代码对于相同的输入都有相同的输出，即这两个代码语义相同，是等价变异体。（注意这里的语义相同指的是待测程序和变体的语义相同）

重复变异体

对于待测程序的两个变体 $mut_1$ 和 $mut_2$ ，如果 $mut_1$ 和 $mut_2$ 语义相同，则 $mut_1$ 和 $mut_2$ 互为重复

注意这里的语义相同指的是两个变体之间的语义相同。

例子：

源程序：

public void foo(int a) {
  int abs = 0;
  if (a > 0) {
    abs = a;
  } else {
    abs = -a;
  }

  return abs;
}

变异体：

public void foo(int a) {
  int abs = 0;
  if (a > 1) {
    abs = a;
  } else {
    abs = -a;
  }

  return abs;
}

重复变异体

public void foo(int a) {
  int abs = 0;
  if (a >= 2) {
    abs = a;
  } else {
    abs = -a;
  }

  return abs;
}

两个变体的关系是重复变异体，因为对于相同的输入有相同的输出，即语义相同。（变体间的语义相同叫做重复变异体）

蕴含变异体

对于两个变体 $mut_1$ 和 $mut_2$ ，如果 $\forall$ 杀死 $mut_1$ 的测试用例 $t$ 都可以杀死 $mut_2$ ，则称 $mut_1$ 蕴含 $mut_2$

例子：

源程序

public void foo(int a) {
  int abs = 0;
  if (a > 0) {
    abs = a;
  } else {
    abs = -a;
  }

  return abs;
}

变异体 $mut_1$ ：

public void foo(int a) {
  int abs = 0;
  if (a >= 3) {
    abs = a;
  } else {
    abs = -a;
  }

  return abs;
}

变异体 $mut_2$

public void foo(int a) {
  int abs = 0;
  if (a >= 4) {
    abs = a;
  } else {
    abs = -a;
  }

  return abs;
}

上述的例子中，杀死 $mut_1$ 的为 1，2 两个输入，杀死 $mut_2$ 的为 1，2，3 三个输入，杀死 $mut_1$ 的任意一个输入都可以杀死 $mut_2$ ，所以 $mut_1$ 蕴含 $mut_2$

变异算子

Mutation Operator

一系列语法变换规则（Syntactic Transformation Rule）
变异（Mutate）的依据，反映了测试人员关注的缺陷种类
基本形式：
- 对程序的源代码进行变换（Source Code Level）
- 对程序的编译结果（中间表示）进行变换，例如：针对 Java Bytecode 的程序变换算子
- 元变异（Meta-mutation）

五种经典变异算子

基础假设

缺陷是简单的，可模拟的
1. 变异体能够模拟测试人员关注的缺陷类型，即：最常出现的缺陷类型；
2. 能够在变异测试中暴露这些人工缺陷的测试套件一定能检测出待测程序中潜在的同类缺陷
3. 老练程序员假设：一个老练程序员编写的错误程序与正确程序相差不大
缺陷可叠加：
1. 复杂变异体可以通过耦合简单变异体得到
2. 能够杀死简单变异体的测试用例可以杀死复杂变异体
3. 结合RIPR/PIE模型思考：该假设是否总是正确？
缺陷检测有效性
1. 缺陷检测能力是测试用例最重要的属性
2. 变异得分能够有效地反映测试用例/套件的错误检测能力
3. 传递性假设：能够杀死变异体（暴露人工缺陷）的测试用例也能有效发现真实世界的缺陷

过程

变异体筛选

对变异体进行筛选（Mutant Selection）：从生成的变体集合中选出一个子集
通过变异算子筛选（Selective Mutation）：定义一系列变异算子，选取其中的一部分构成子集
研究内容
- 变异算子的定义
- 变异算子的选取/约减策略

变异算子定义

算子是一组语法转换规则；算子反映了特定的缺陷类型
研究的核心：如何设计有效的变异算子？
设计原则
- 根据编程语言：Java，C#，C/C++，JS，AspectJ
- 根据语言设计原则：OO，AOP
- 根据应用场景：Web，Android，Ajax
- 根据Bug类型：安全漏洞、内存缺陷、交互错误

变异体约减策略

变异体约减旨在从变异体全集中选出具有代表性变异体子集
目的：减少变异测试所需的资源，提高可拓展性
约减策略
- 随机选取1：选取总量的 10% ~ 60%，缺陷丢失率为 6% ~ 26%
- 基于类型2：某些类型的变异体可能要更加重要
- 基于分布3：利用AST选取更加分散的变异体

变异体生成

将选中的变异体（算子）实例化
基本方式：为每个变体构建一个单独的源文件（Source File）
缺陷：运行时间较长，会产生较大的额操作开销
研究内容：变异体生成技术
- 元变异（Meta-mutation）
- 基于字节码操作（Bytecode Manipulation）
- 热替换（Hot-Swap, Just-In-Time）

元变异

Meta-mutation / Mutation Schemata
核心：程序模式（Program Schema）
- 程序模板（Template）& 部分编译（Partially Interpreted）
- 形式上类似于一般程序，但是包含自由标识符（Free Identifier），i.e. 用一些符号替换程序中的结构（变量、语句）
目的：减少生成变异体时所需的编译次数；集中存储变异体

基于字节码操作

避免编译，从而减少时间开销
操作目标：中间表示（Intermedia Interpretation），如：Java字节码、.NET和LLVM的通用中间表示
代表工作：PIT（Java）、Mull （LLVM for C）

变异体优化

内容：去除有等价和无效变异体
目的
- 减少后续执行变异体阶段的开销
- 提高变异得分的可信度
基本形式：通过静态分析的方式，识别并移除有问题的变异体

识别等价变异体

特征：不可确定问题（Undecidable problem），无法建立识别所有对等变异体的算法，只能设计相应的启发式策略
常用技术
- 代码优化（Code optimization）。对源代码和变异体进行优化，移除优化后与源代码相同的变异体
- 静态数据流分析，如值分析（Value Analysis）。等价变异体汇总存在特定的数据流模板，可以由此识别等价变异体

识别冗余变异体

操作符的角度：如>, ==, <之间的有机组合
缺陷层级（Fault Hierarchy）角度：变异体之间的从属关系
程序分析角度：代码优化、符号执行

变异体执行

特征：变异测试过程中最昂贵的阶段
基本形式：假设一个待测程序 P 有 $n$ 个变异体和一个包含 $m$ 个测试用例的测试套件，则执行变异体的最大次数为 $n \times m$

针对执行优化的量大场景优化执行过程

场景A：计算变异得分

场景B：计算变异体矩阵（Mutant Matrix）

优化策略

改变测试用例的顺序
匹配测试用例与变异体
避免执行必定存活的变异体
限定变异体的执行时间

变异得分计算

变异得分计算：计算被杀死的变异体数量，进而得到变异得分、量化测试的充分性
研究内容：
- 变异杀死的条件：确定一个变异体是否被杀死
- 测试预言的生成：如何生成更多、更好的测试预言来杀死更多的变异体、提高变异得分

变异杀死的条件

核心：定义程序行为（Program behavior）
Weak，Firm，Strong Mutation
代表性工作
1. 针对确定性系统：定义新的系统级行为
2. 针对非确定性系统：定义、模拟程序规格

应用

应用总览

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

变异辅助 Debug

利用变异自动为有缺陷程序推荐补丁

Debug 的两个阶段
- 定位：判断缺陷所在位置，分析可疑的缺陷特征
- 修复：着手修复缺陷本身
自动Debug挑战
- 缺少缺陷版本作为试验评估的数据集
- 变异分析的自身特性为自动 Debug 提供了数据支持

Reference

南京大学软件学院本科三年级课程《自动化测试》
变异测试领域相关论文