回归测试

在软件产品的开发和维护的过程中，因为移除软件内在的缺陷、添加新功能、重构现有代码等操作，需要对代码进行修改，执行软件演化。此外，随着以统一过程和敏捷方法为代表的增量、迭代式开发过程的流行，软件演化频率也随之迅速提高。因此，确保软件演化过程中的质量愈发重要。

回归测试作为一种有效的方法，可有效保证代码修改的正确性并避免代码修改对被测程序其他模块产生副作用。回归测试一般占软件产品测试预算的 $80\mathrm{\%}$ 以上，占软件维护预算的 $50\mathrm{\%}$ 以上。

由于回归测试的应用场景是软件演化，那么就一定有先前的测试用例套件可以用来复用。但是，如果我们直接执行先前的所有测试用例，又会有很多问题。首先就是已有测试用例存在大量冗余，此外还有测试用例失效和缺失等一系列问题。因此，回归测试优化的主要研究方向就是如何从原有用例中提炼出对本次演化有效的用例，并修复失效或缺失的用例。

回归测试优化流程图

回归测试优化

回归测试优化的范畴大概包含以下的五个方向：

• 测试用例修复：识别出因相关模块的外部接口或内在语义发生变更为失效的用例，并其进行修复。
• 测试用例选择：通过分析代码修改，从已有测试用例中选择出所有可检测代码修改的测试用例，并确保未被选择的测试用例在修改前后程序上的执行行为保持一致。
• 测试用例扩充：在代码修改影响分析基础上，对已有测试用例集的充分性进行评估，若不充分则设计新的 测试用例以确保对代码修改的充分测试。
• 测试用例缩减：在满足指定测试需求覆盖前提下，识别并移除冗余测试用例来降低回归测试用例集规模。
• 测试用例优先级：当测试预算不足以执行完所有测试用例时，可以基于特定优先级准则，对测试用例进行优先级排序以优化其执行次 序，旨在最大化优先级目标，例如测试用例集的缺陷检测速率。

测试用例优先级

通过设定特定优先级准则（执行时间，代码覆盖等），对测试用例进行优先级排序以优化其执行次序，旨在提高测试用例集的故障检测率和效率。

测试用例优先级的获取

主要步骤如下：

• 特征提取：选择合适的特征表示测试用例。
• 优先级策略：操纵测试用例的特征进行优先级排序。
• 评估准则：选择恰当指标评估优先级排序的效果。

特征提取

特征提取的方法有很多。根据 $\mathrm{PIE}$ 模型理论我们知道，只有运行的缺陷才能被检测到，那么，我们可以基于源码特征，提取出语句、分支和函数特征，并计算测试用例对这些特征的覆盖率。我们还可以基于文本特征来提取，计算出测试数据文本（如字符串或者量化为向量）之间的差异性（海明距离，曼哈顿距离，编辑距离：即从一个字符串编辑成另一个需要多少步键盘操作等）来表示特征。此外，还可以基于缺陷特征来提取，即在变更代码上进行变异测试，使用变异体杀死能力来度量测试用例的缺陷检测能力。还有一种直接基于模型特征的提取方式，通过对比修改前后模型可别出模型差异，在修改后的模型上执行所有测试用例，并基于测试用例对模型差异的覆盖信息进行优先级排序。

例如，对于以下求最大公约数的缺陷代码：

int gcd(int a, int b){
  	if(!a)	return b;
    while (b) {
      if (a > b) a = a - b;
      else	b = a - b; // should be “b = b - a;”
    }  
  	return b;
}

在第五行存在缺陷。那么，如果某些测试用例有更大的代码覆盖率，那么就能够以更大的概率检测出这一缺陷。所以，在这一代码中，我们可以使用代码覆盖率来作为一个优先级策略。对于优先级策略，一般有贪心、相似性分析、搜索和机器学习几种方法。

基于贪心的 TCP

贪心方法分为全局贪心策略和增量贪心策略。全局贪心策略每次优先选择覆盖最多代码单元的测试用例，而增量贪心策略每轮优先挑选覆盖最多，且未被已选择用例覆盖代码单元的测试用例。在这两种策略下，如果多个用例相同则随机选择。

贪心算法实例

对于贪心方法，我们还可以做如下的改进：

贪心策略的改进1：基于一个共识：错误在每条语句上发生的概率不一样。所以可以为每条语句赋一个权值，在计算覆盖率时算入。对于每个样例 $i$，我们可以定义加权覆盖评估值 $weight(i)$，其计算方式如下：

$$weight(i)=\sum _{j=1}^{u}prob(j)\cdot cover(i,j)$$

其中 $u$ 为代码单元（语句或者分支）个数，$prob(j)$ 为在该代码单元 $j$ 出错的概率，而 $cover(i,j)$ 为样例 $i$ 在 $j$ 处的覆盖度。

贪心策略的改进2：覆盖代码单元次数也应纳入考虑范围。一般来说，某一代码单元被覆盖次数越多，就越容易检测出缺陷。因此，我们在每一轮选择用例时，计算其有覆盖数组，并计算有序覆盖数组（即将有覆盖数组从小到大排序），选择能让有序覆盖数组字典序最大的样例。我们可以看下面的例子：

贪心算法实例

前两轮显然选择 $t_1,t_2$。第三轮，如果选择 $t_3$，那么有覆盖数组为 $[0,1,1,1,3,1,1,1]$，排序后为 $[0,1,1,1,1,1,1,3]$，而如果选择 $t_4$，那么排序后为 $[0,1,1,1,1,1,2,2]$。后者的字典序大，所以选择 $t_4$。因此这些样例的优先级为 $t_1>t_2>t_4>t_3$。

基于相似性的 TCP

一般来说，缺陷的位置是集中的。所以，我们需要考虑测试用例之间的“距离”来作为优先级评估的标准。我们希望让测试用例分布地相对均匀，这样可以增大覆盖率和检测缺陷的能力。

自适应随机策略就是每轮优先选择与已选择测试用例集差异最大的测试用例，这样就可以让测试用例均匀地分布在输入域之中。要达到这一目的，我们需要首先定义测试用例之间的距离：假设 $U(t_1)$ 和 $U(t_2)$ 分别为测试用例 $t_1$ 和 $t_2$ 所覆盖的代码单元集合，那么这两个用例之间的距离定义如下：

$$Jaccard(t_1,t_2)=1-\frac{\mid U(t_1)\cap U(t_2)\mid }{\mid U(t_1)\cup U(t_2)\mid }$$

显然，$Jaccard(t_1,t_2)$ 越大，二者的相似度就越小，“距离”就越大。当我们想要新选择一个测试用例加入我们的测试用例集时，我们可以计算它的与测试用例集中所有用例（当剩余的测试用例集过大时，我们可以从中随机选小批量测试用例作为候选集）的最小距离 $d_{min}$ 作为评估标准。每次都加入 $d_{min}$ 最大的测试用例即可。而对于测试用例集中的第一个测试用例，我们一般选择覆盖率最大的即可。

基于搜索的 TCP

通过探索用例优先级排序的组合空间，借助于基因算法等搜索算法，以此找到检测错误更快的测试用例。它的步骤大概如下：

• 种群构造：生成 $N$ 个优先级测试用例序列，可以按优先级顺序进行编码，如对于六个测试用例，我们可以生成两个序列 $[3,1,4,5,2,6]$ 和 $[6,3,5,4,2,1]$。

• 交叉：多个种群中的个体进行交互。例如，使用单点交叉的方式，首先随机生成分割点，互相交换两个用例序列切割点后部分的片段。如下图，在生成个体 $3$ 时，个体 $1$ 中保持交叉点前面的序列不变，根据个体 $2$ 中的优先级排序方式确定剩余个体的位置，个体 $4$ 同理。

  

  贪心算法实例

• 变异：对种群中的个体进行基因值的改变操作。以一定概率选择测试用例，并随机生成两个测试用例位置，进行互换，产生新的测试用例序列。

• 评估值计算：以语句覆盖为例，给定程序包含 $m$ 个语句 $𝑀=\{{𝑠}_1,{𝑠}_2,\cdots ,{𝑠}_m\}$ 和𝑛个测试用例 $T=\{{𝑡}_1,{𝑡}_2,\cdots ,{𝑡}_n\}$，$T^{\prime }$ 为某一次搜索中 $𝑇$ 的一个优先级序列，$ 𝑇𝑆_i$ 为该测试用例序列 ${𝑇}^{\prime }$ 中第一个覆盖语句 $s_i$ 的测试用例下标，那么其适应度计算为：

  $$APSC=1-\frac{\sum _{i=1}^{m}T{S}_i}{nm}+\frac{1}{2n}$$

评估指标

$\mathrm{APFD}$：平均故障检测百分比。当给定测试用例的执行次序时，该评测指标可以给出测试用例执行过程中检测到缺陷的平均累计比例。其取值范围介于 $0-100\mathrm{\%}$ 之间，取值越高，则缺陷检测速度越快。给定程序包含 $𝑚$ 个故障 $F=\{f_1,f_2,\cdots ,f_m\}$ 和 $n$ 个测试用例 $T=\{t_1,t_2,\cdots ,t_n\}$，$T^{\prime }$ 为 $T$ 的一个优先级序列，$T{F}_i$ 为该测试用例序列 $T^{\prime }$ 第一个检测到故障 $f_i$ 的测试用例下标。那么优先级序列 $T^{\prime }$ 的 $APFD$ 值定义为：

$$APFD=1-\frac{T{F}_1+T{F}_2+\cdots +T{F}_m}{nm}+\frac{1}{2n}$$

此外，$APF{D}_c$ 考虑了测试用例的执行开销和缺陷危害程度；$NAPFD$ 考虑了实际优先级排序场景中无法执行所有测试用例等问题。

测试用例选择

测试用例选择旨在从已有测试用例集中选择出所有可检测代码修改的测试用例。它适用于因测试预算不足以致不能执行完所有测试用例的测试场景。最简单的测试用例选择策略是如果一个测试用例没有执行到变更部分所在的模块，那就不选择这一测试用例。当然，这种方法可能会舍弃掉某些有价值的测试用例。

测试用例集约减

测试用例约减指在满足对指定测试需求的覆盖前提下，通过识别并移除冗余测试用例来降低回归测试成本，在版本迭代时提高测试的效率。这一步可以类比变异体筛选和约减的过程。