0 引言

在软件开发过程中，需要频繁地进行软件测试，测试用例需要不断被设计、修改和执行，构成回归测试的测试用例集合^[1]。在回归测试过程中，会产生大量冗余的测试用例，有效约简测试用例，利用尽可能少的测试用例最大限度满足给定的测试目标，能够有效提高测试效率，降低测试成本^[2-4]。传统的测试用例约简方法主要有贪心(Greedy, G)算法、启发式(Heuristic, H)算法和整数规划等^[5]。G算法和H算法总是在当前测试需求中寻找最优的测试用例，所选择的测试用例是某种意义上的局部最优，不能保证全局最优。整数规划法将最优代表集选择问题转化为整数线性规划问题，但时间复杂度较高，运算开销呈指数级增长。

经过多年研究，测试用例约简方法已有了很大改进^[5-9]。华丽等^[10]利用遗传算法的全局搜索能力获取测试用例优化解集合，再根据蚁群算法的正反馈性得到最小集合的最优解。但该方法的约简效果取决于最初产生的测试用例集，不能从根本上对测试用例进行优化。聂长海等^[11]首先提出依据测试需求约简测试用例的方法，根据测试需求间的关联关系对测试用例进行划分，再利用启发式算法、贪心算法等获取可覆盖所有测试需求的最小测试用例集。而在回归测试中测试需求往往包括关注需求集和无关需求集，该方法在约简测试用例过程中，没有考虑无关需求集的问题。顾庆等^[1]提出一种启发式贪婪搜索方法，减少了对无关测试需求的覆盖，最大限度地降低了测试成本。陈静等^[12]提出一种基于关联模式的测试用例约简模型，根据程序模块、测试需求以及测试用例间的关联关系约简测试用例，但目前该研究仍处于理论研究阶段，并没有实现针对具体测试需求约简测试用例的方法。刘锋等^[13]提出一种向量相似度算法，根据测试用例间的相似度、覆盖度和冗余度约简测试用例，但该方法以矩阵形式存储数据，占用存储空间比较大，且容易陷入局部最优解。

针对上述研究中未考虑测试用例间关联关系以及数据存储、计算消耗大的问题，本文提出一种基于变异分析的测试用例约简方法(Reduction method of Test suites based on the analysis of Mutation, RTM)。一方面，从变异测试能够衡量测试用例充分性^[14-18]这一特性出发约简测试用例；另一方面，创建二进制形式的变异体事务集矩阵，通过位运算获取测试用例间关联关系。RTM首先根据源程序特征设计变异因子并产生变异体，避免无关变异体被覆盖而降低测试效率；然后将原始测试用例集分别在原程序和变异体上执行，以测试用例能否检测到指定变异体为依据，对测试用例进行划分，创建二进制变异体事务集矩阵；再根据改进的关联挖掘算法获取测试用例间的关联关系，最后根据所获取的关联关系有效约简测试用例。

1 基于变异分析的测试用例约简模型

设原始测试用例集T={t₁, t₂, …, t_m}，根据源程序特征设计变异因子并生成大量变异体，识别出等价变异体，将非等价变异体定义为P={p₁, p₂, …, p_n}。描述测试用例约简模型需要以下定义。

定义1  变异评分。变异测试最终通过变异评分(Mutation Score, MS)来评估测试用例集的测试充分性，变异评分MS(P, T)通过式(1) 计算获得：

$MS(P,T) = \frac{{killed(P,T)}}{{\left| P \right| - eqv(P)}}$

(1)

其中：函数killed(P, T)返回测试用例集T能够检测出的变异体数量；|P|为变异体总数；eqv(P)函数返回等价变异体的数量，等价变异体与原有程序在语法上存在差异，但在语义上保持一致。等价变异体的检测是一个不可判定问题，已有的检测方法主要有静态检测方法和动态检测方法。根据式(1) 可以看出，MS的取值范围介于0到1之间，MS的取值越高，代表测试用例充分性越高，实际缺陷检测能力越强^[19]。

定义2  测试需求。将测试用例能够检测到变异体作为测试需求，n个测试需求定义为P={p₁, p₂, …, p_n}，那么, P与T之间的映射关系S={(p, t)∈P×T|t能够检测到变异体p}，R(t)表示测试用例t能够满足的所有测试需求。

定义3  变异体事务项。将不能够检测到变异体p_k的测试用例集合作为一个变异体事务项MList_k(MList_k={t₁, t₂, …, t_γ})，其中，p_k∈P，t_i∈T。

定义4  变异体事务集。所有变异体事务项构成变异体事务集，n个变异体事务项构成的变异体事务集表示为MLists={MList₁, MList₂, …, MList_n}。

定义5  变异体事务集矩阵。变异体集合与测试用例集合存在一一对应的关系，所有关系集合组成一个n×m的二进制矩阵A:

$\mathit{\boldsymbol{A}} = \left[ {\begin{array}{*{20}{c}} {{a_{11}}}&{{a_{12}}}& \cdots &{{a_{1m}}}\\ {{a_{21}}}&{{a_{22}}}& \cdots &{{a_{2m}}}\\ \vdots & \vdots & \ddots & \vdots \\ {{a_{n1}}}&{{a_{n2}}}& \cdots &{{a_{nm}}} \end{array}} \right]$

矩阵的行表示一个变异体事务项，若事务项MList_i中包含测试用例t_j，即测试用例t_j不可以检测到变异体a_i，那么a_ij=1；否则a_ij=0。

测试用例约简旨在用最小的测试用例集尽可能地满足更多的测试需求，本文将变异体集合作为测试需求，变异体集合P与原始测试用例集T存在映射关系S={(p, t)∈P×T|t能够检测到变异体p}，测试用例约简问题等价于求最小集合覆盖问题。

令R(T)与R(T′)分别表示原始测试用例集T与用例集T′所满足测试需求集，其中T′⊆T，若R(T′)=R(T)，并且不存在任何t(t∈T)，使R(T′-{t})=R(T)，即若测试用例集T与T′满足相同的测试需求，并且不存在比T′更小的集合，使其与原始测试用例集满足相同的测试需求，那么T′为最小测试用例集合，即约简后的测试用例集合。

2 测试用例约简方法

本文提出一种基于变异分析的测试用例约简方法(RTM)，RTM的测试用例约简流程如图 1所示。

首先在源程序与变异体上分别执行测试用例，以测试用例能否检测到指定变异体为依据，对测试用例进行划分并获取测试用例频繁1项集，根据频繁1项集创建变异体事务集矩阵A，矩阵元素取值0或1，1表示对应测试用例不能够检测到指定变异体，否则能够检测到。设计实现基于二进制矩阵的关联挖掘算法，获取测试用例间的关联关系，根据所获取的测试用例间的关联关系有效约简测试用例。

2.1 初始化变异体事务集矩阵

分别在原程序O与变异体集合P={p₁, p₂, …, p_n}上执行测试用例集T={t₁, t₂, …, t_m}，以测试用例能否检测到指定变异体为依据，获取测试用例频繁1项集，将不能够检测到指定变异p_i(p_i∈P)的所有测试用例作为一个变异体事务项MList_i，所有变异体事务项组成变异体事务集MLists。

令关联挖掘过程中最小支持度为minSup，将频数大于等于minSup的测试用例降序排列，存储在测试用例列表ErrList中，由变异体事务集MLists与测试用例列表ErrList的映射关系创建变异体事务集矩阵A。矩阵的每一行表示一个变异体事务项，矩阵元素按式(2) 设置。

${a_{ix}}\left\{ {\begin{array}{*{20}{c}} {1,\quad {t_x} \in MLis{t_i}}\\ {0,\quad {t_x} \notin MLis{t_i}} \end{array}{\rm{;}}{t_x} \in ErrList} \right.$

(2)

其中，a_i为矩阵第i行，对应变异体事务集中第i个事务项MList_i。式(2) 表明，若MList_i中包含测试用例t_x，即t_x不能检测到变异体p_i，变异体p_i相对测试用例t_x是可存活变异体，那么t_x对应矩阵第i行第x列的元素赋值为1；否则赋值为0。

2.2 约简变异体事务集矩阵

初始化创建的变异体事务集矩阵规模比较庞大，其中包含许多冗余的事务项，删除其中无意义的事务项，合并重复的事务项，能够有效缩减矩阵的规模，大幅度提高获取测试用例间关联关系的效率。

约简变异体事务集矩阵，首先需要按照事务项中所包含的测试用例数，对事务项进行排序，即对矩阵A按行降序排序，再对排序后的矩阵进行约简。

逐行约简有序矩阵过程中，若当前预处理事务项MList_i(矩阵A第i行)包含测试用例数小于等于1，即 $\mathop \sum \limits_{j = 1}^m {a_{ij}} \le 1$ ，那么矩阵该行无法获取测试用例间关联关系，可直接删除该行事务项及其后所有事务项；否则将MList_i与之前所有事务项比较，判断MList_i与之前事务项是否存在冗余。对MList_j(MList_j是MList_i之前的事务项)与MList_i各项元素作异或操作，若 $\mathop \sum \limits_{k = 1}^m {a_{ik}} \oplus {a_{jk}} = 0$ ，那么，MList_i与MList_j所包含的测试用例完全相同，称MList_i与MList_j具有相似性，即MList_i相对于MList_j是冗余的事务项，删除事务项MList_i，同时增加MList_j频数；否则若不存在任何的MList_j使其与MList_i具有相似性，那么MList_i相对于其前所有事务项为可保留事务项。事务集矩阵A具体约简过程见算法1。

算法1  约简变异体事务集矩阵。

输入  初始化创建的变异体事务集矩阵A_n×m；

输出  约简后的变异体事务集矩阵A_n×m。

步骤1  对矩阵A按行降序排列。

步骤2  若 $\mathop \sum \limits_{j = 1}^m {a_{ij}} \le 1$ ，跳转步骤6；否则执行步骤3。

步骤3  若存在MList_j，满足 $\mathop \sum \limits_{k = 1}^m {a_{ik}} \oplus {a_{jk}} = 0$ ，即MList_i与MList_j具有相似性，执行步骤4；否则跳转步骤5。

步骤4  增加MList_j频数，删除矩阵第i行元素，矩阵预处理行向量下移，重复步骤2。

步骤5  当前预处理事务项MList_i下移，即矩阵预处理行向量下移，重复步骤2。

步骤6  删除矩阵当前行及其后所有元素。

步骤7  改变矩阵当前规模。

2.3 获取变异体事务集频繁模式

获取变异体事务集的频繁模式L(L={L₁, L₂, …, L_i, …, L_a-1})，需逐个获取事务项MList_i(1≤i < n)与其前所有事务项MList_j(1 < j < i)相交的测试用例集合L_i，该集合包含相交集合的所有非空子集。若事务项MList_i与MList_j包含有相同的测试用例，那么MList_i与MList_j存在交集L_ij，对集合L_ij进行按位与操作，获取该集合的所有非空子集，每获取一个子集，计算该子集的频数，并将该子集添加到集合L_i中。具体过程见算法2。

算法2  获取变异体事务集频繁模式。

输入  约简后的变异体事务集矩阵A_n×m；

输出  测试用例间的频繁模式集。

步骤1  若∃k(k∈(1, m))满足a_ik∩a_jk=1，那么MList_i与MList_j交集集合L_ij=L_ij+{k}，添加所有符合该条件的k值到L_ij中。

步骤2  令r=|L_ij|，二进制数start=1， ${\rm{e}}nd = \overbrace {11...1}^r$ ，mark值从start开始，逐次加1，mark的每一个值映射一个子集列表l，按照步骤3计算每一个子集的频数。

步骤3  若l⊆L_i，且集合l在L_i中的频数为count，那么count=count+a_j0；否则count=a_i0+a_j0，同时令L_i=L_i+l。

2.4 约简测试用例

由频繁项集及其对应的置信度产生关联规则相对较为容易和直观，根据已有的方法即可获取所有的关联规则Rules={rule₁, rule₂, …, rule_ρ}，令测试用例约简置信度为minConf，根据所获取的关联规则及其对应的置信度conf可有效约简测试用例。

若测试用例集T′(T′≠∅)与测试用例t_b存在关联规则T′$ \Rightarrow $t_b，且置信度conf≥minConf，即测试用例集T′不能够检测到的变异体，t_b也同样检测不到的可靠程度为conf，该可靠程度达到了测试用例约简的最小置信度值，那么测试用例t_b相对于测试用例集T′是冗余的测试用例，即t_b为可约简的测试用例。

由于每一个被约简的测试用例t_b都存在与其具有极大关联度的测试用例集合T′，即t_b相对于T′是冗余的测试用例，那么约简后测试用例集合T′与原始测试用例集合T，执行变异测试后具有相同的变异评分，即约简后测试用例集与原始测试用例集拥有相同的变异评分。

RTM以测试用例能否检测到指定变异体为依据，创建变异体二进制事务集矩阵，采用改进的关联挖掘算法获取测试用例间的关联关系，进而约简测试用例，RTM仅扫描一次数据集，因此最坏情况下，RTM的时间复杂度为n·(n-1)，即测试用例约简率不受初始测试用例集的影响。

3 实验结果与分析

为验证本文方法(RTM)的有效性，选择经典测试用例约简方法，即贪心算法(G算法)和启发式算法(HGS算法)进行实验验证。G算法在循环迭代过程中每次选择能够覆盖最多测试需求的测试用例，直到所有测试需求均被满足，HGS算法首先根据被覆盖到的测试用例数对测试需求进行划分，再使用贪心算法循环迭代选择能够满足所有测试需求的测试用例集^[18]。

3.1 实验设计及评估准则

本文实验结果以测试用例约简率、变异评分、测试覆盖率和错误检测率四个指标进行对比和分析。其中，错误检测率表示约简后测试用例集和原始测试用例集能够检测到错误数的比值。错误检错率越大，表示约简后测试用例集相比原始测试用例集，对测试用例检测率的影响越低，错误检测能力越强^[19]。

实验程序选择Siemens程序集上(http://sir.unl.edu)上的6个基准实验程序：Mid、Triangle、Cal、NextDate、Tcas与WordUtils程序，表 1为6个程序的相关描述信息。

表 1描述的待测程序信息包括有效代码行数、根据程序特征选择的变异因子、由变异因子产生的变异体数目，以及原始测试用例集的规模。本实验中选择的变异因子的描述信息如表 2所示。

3.2 实验结果分析 3.2.1 测试用例约简率和错误检错率

分别在6个程序上使用RTM、G算法和HGS算法约简测试用例，表 3为分别使用3种算法约简测试用例的约简结果。由表 3分析可知，当测试用例规模比较小时，RTM的测试用例约简率并不明显，但当测试用例规模增大时，RTM能够使约简后测试用例约简率平均可达到37%，如程序NextDate，原始测试用例规模为100，RTM的测试用例约简率可达到45%。另一方面，RTM能够获得更高的错误检测率，从实验结果可看出，RTM相对于G算法和HGS算法，能够对原始测试用例集的错误检测率产生更极小的影响，保证测试用例集的错误检测能力。

3.2.2 测试充分性评估

实验通过变异评分和测试覆盖率综合评估约简后测试用例集的测试充分性，图 2为使用三种算法约简测试用例后的变异评分。由图 2分析可知，RTM能够保证在约简测试用例后变异评分不改变，而H算法和HGS算法在源程序与测试用例规模增大的时候，会极大程度地降低变异评分，影响原始测试用例集的测试充分性。

在相同测试充分性的前提下，单个测试用例的测试覆盖率如表 4所示。由表 4可知，RTM相比G算法和HGS算法，能够使约简后的单个测试用例拥有更高的测试覆盖率。如程序WordUtils，使用RTM约简测试用例后，单个测试用例的测试覆盖率相较于G算法提高了18%，相较于HGS算法提高了16%，约简后单个测试用例的测试覆盖率相比原测试用例提高了一倍。

实验结果表明，RTM相较于传统的G算法和HGS算法，能够获得更小的测试用例集，并使得约简后测试用例集对错误检测率的影响降到最低。RTM能够在保持测试充分性的同时，有效提高单个测试用例的测试覆盖率，提高测试效率，降低测试成本。

4 结语

本文针对回归测试中测试用例约简问题，考虑到测试用例间存在的关联关系，结合变异分析和改进的关联挖掘算法，提出一种基于变异分析的测试用例约简方法。通过测试用例间的关联关系有效约简测试用例，使约简后的测试用例在不改变原始测试用例集测试充分性的前提下，大幅度提高单个测试用例的测试覆盖率。

在本文研究基础上，下一步的研究工作主要有两个方面：一方面，将针对降低变异测试效率展开更深入的研究；另一方面，针对未被原始测试用例集检测到的变异体，设计能够杀死该变异体的测试用例，使得测试用例集具有更高的测试充分性。