开放科学（资源服务）标志码（OSID）：

0 概述

回归测试是指测试人员对演化后的新版本程序重新进行测试，确认修改部分没有影响未修改部分的功能^[1]。测试用例集扩增强调利用原测试数据信息和程序演化信息辅助生成新的测试数据，以期提高生成效率并获得更具针对性的测试用例^[2]。

测试数据扩增概念由HARDER等^[3]提出，之后国内外研究人员对其进行大量研究并取得一定的研究成果。吴川等^[4]提出基于分析路径相关性来建立回归测试数据生成模型，虽然目标路径的覆盖率较高，但对于不同的被测程序，需要根据程序的特征设置不同的控制参数。YOO等^[5]将测试数据分为失效和未失效两类，且仅修改程序中的简单运算符。XU等^[6]研究表明使用已有测试数据可以提高测试数据集扩增效率。QI等^[7]利用符号执行技术和状态传递树CEPT^[8]确保测试数据可以覆盖修改后程序的变化节点，JIANG等^[9]通过分析软件信息图扩增测试数据，但QI和JIANG等的研究均未利用原测试数据集。巩敦卫等^[10]根据与目标路径的相似度选取初始种群，采用遗传算法生成测试数据，虽然合理地利用了原测试用例，但是并未将程序的演化信息与交叉算子相结合。殷鹏川等^[11]利用原测试用例跳过重叠初始子路径，对后续目标子路径进行concolic测试，但该方法受限于约数求解器。王曙燕等^[12]利用路径相似度识别新增路径并选取初始种群，采用自适应粒子群算法生成测试用例，但该方法不适用于大规模软件测试。吴川等^[13]基于路径与测试数据之间的关系，决定需要扩增的测试数据，但该方法未利用原测试用例。XU等^[14]研究表明已有测试用例的使用方式对回归测试的效率有较大的影响。王曙燕等^[15]从方法级别和语句级别提取覆盖目标，将原测试用例和正交种群作为初始种群，虽然利用了原测试数据，但并没有对其进行选择，数据冗余性较大。对于上述研究存在的问题，需要一种与程序演化信息密切结合、能充分利用原测试用例且适用于较多程序的测试用例扩增算法，以在降低回归测试成本的同时提高扩增效率。

基于符号执行的软件测试方法受限于本身的高复杂度，难以适用于大规模软件测试，同时由于影响回归测试效果的主要因素是测试用例生成算法，而元启发式算法能有效提高测试用例扩增效率^[16-17]。天牛须搜索（Beetle Antennae Search，BAS）算法是一种新型的元启发式算法^[18-19]，具有参数少且鲁棒性强等优点，自提出以来受到了学术界的广泛应用并取得了一系列的成果，但在测试用例扩增应用中鲜有公开的文献。本文在文献[15]研究的基础上，提出基于天牛须搜索算法的软件测试数据扩增方法MBAS。结合软件演化信息，基于原测试用例集的覆盖信息选取部分测试用例作为初始的进化种群，根据分支距离和分支嵌套深度设计适应度函数，采用改进的天牛须搜索算法对有序目标方法集进行测试数据的扩增，以期提高原测试用例的利用率和程序扩增的效率。

1 有序目标方法集获取

利用已有的测试数据执行新旧程序，根据程序覆盖与执行信息得到需测试的目标方法集合。获取程序的方法调用图并将其用邻接矩阵存储，计算方法执行概率和权值，得到方法包含错误的影响度，获取优先覆盖的目标方法。

1.1 程序覆盖与执行信息获取

一个程序包括m个方法$ M=\{{f}_{1}, {f}_{2}, \cdots , {f}_{m}\} $，对程序执行测试用例后，得到的方法覆盖信息与执行信息用矩阵A表示如下：

$ \boldsymbol{A}=\left[\begin{array}{ccc}{t}_{11}{u}_{11}& \cdots & {t}_{1n}{u}_{1n}\\ ⋮& {t}_{ij}{u}_{ij}& ⋮\\ {t}_{m1}{u}_{m1}& \cdots & {t}_{mn}{u}_{mn}\end{array}\right] $

在矩阵A中，测试数据为$ {t}_{1}, {t}_{2}, \cdots , {t}_{n} $，$ {t}_{ij}(1\le i\le m, 1\le j\le n) $表示测试用例$ {t}_{j} $对于$ {f}_{i} $方法的覆盖情况，如果$ {t}_{j} $覆盖了$ {f}_{i} $，则$ {t}_{ij}=1 $，否则$ {t}_{ij}=0 $。$ {t}_{j} $的执行结果为$ \boldsymbol{u}=[{u}_{1j}, {u}_{2j}, \cdots , {u}_{ij}, \cdots , {u}_{mj}] $ ^-1，$ {u}_{ij} $表示$ {t}_{j} $对$ {f}_{i} $的执行结果，如果成功，则$ {u}_{ij}=1 $，否则$ {u}_{ij}=0 $。

测试用例在新旧版本程序中的方法覆盖与执行情况表示为$ \boldsymbol{A} $和$ \boldsymbol{A}\text{'} $，通过对同一测试用例的覆盖信息和执行信息做异或运算，得到目标方法集$ C=\left\{{f}_{i}\in M\left|\right({t}_{ij} \oplus {t}_{ij}^{'}=1)\bigcup (({t}_{ij} \oplus {t}_{ij}^{'}=0)\wedge ({u}_{ij} \oplus {u}_{ij}^{'}=1))\right\} $。

1.2 目标方法集排序

获取程序的方法调用图，方法调用图是一个有向图，其中每个节点都附加一个权值。建立方法调用图的邻接矩阵，若存在调用关系，则矩阵元素为1，否则为0。对矩阵进行遍历，统计每个方法可调用的方法个数。

1.2.1 目标方法包含错误的概率

通过目标方法在新旧版本程序上的执行概率得到其包含错误的概率。假定方法集相互独立，初始方法$ {f}_{1} $的执行概率$ P\left({f}_{1}\right) $=1，若$ {f}_{i} $调用$ {f}_{a}\cdots {f}_{b} $等$ {w}_{i} $个方法，则$ {f}_{a}\mathrm{的} $执行概率$ P\left({f}_{a}\right) $表示如下：

$ P\left({f}_{a}\right)=\left\{\begin{array}{l}\frac{P\left({f}_{i}\right)}{{w}_{i}}, a\ne 1\mathrm{且}P\left({f}_{a}\right)=0\\ 1.00, a=1\\ P\left({f}_{a}\right)+\frac{P\left({f}_{i}\right)}{{w}_{i}}, a\ne 1\mathrm{且}P\left({f}_{a}\right)\ne 0\end{array}\right. $

若被调用方法的执行概率不为0时，则叠加概率值，直至计算至最后一个节点。计算新旧程序中目标方法$ {c}_{k}\left(1\le k\le m\right) $的执行概率$ P\left({c}_{k}\right) $和$ P\text{'}\left({c}_{k}\right) $，目标方法$ {c}_{k} $包含错误的概率$ P″\left({c}_{k}\right) $表示如下：

$ P″\left({c}_{k}\right)=\left|P\right({c}_{k})-P\text{'}({c}_{k}\left)\right| $

1.2.2 目标方法包含错误的影响度

将方法调用图中所有非叶子节点的权值$ N\left({f}_{i}\right) $初始化为0，所有叶子节点的权值为1。若$ {f}_{i} $调用$ {f}_{a}\cdots {f}_{b} $等$ {w}_{i} $个方法，则$ {f}_{i}\mathrm{的} $方法权值$ N\left({f}_{i}\right) $表示如下：

$ N\left({f}_{i}\right)=\left\{\begin{array}{l}1, {f}_{k}\mathrm{为}\mathrm{叶}\mathrm{子}\mathrm{节}\mathrm{点}\\ \sum\limits _{i=a}^{b}N\left({f}_{i}\right), \mathrm{其}\mathrm{他}\end{array}\right. $

计算新程序中目标方法$ {c}_{k} $的权值$ N\left({c}_{k}\right) $，将权值和包含错误的概率进行乘积得到目标方法包含错误的影响度$ S\left({c}_{k}\right) $：

$ S\left({c}_{k}\right)=P"\left({c}_{k}\right)\cdot N\left({c}_{k}\right) $

将$ S\left({c}_{k}\right) $值按递减的顺序进行排列，得到有序目标方法集$ C\text{'} $，并对其依次生成测试数据。

2 测试数据集扩增

基于天牛须搜索算法的软件测试数据扩增方法可分为预处理和测试用例扩增两个模块，如图 1所示。

预处理模块主要包括程序静态分析和获取目标方法集，抽取方法调用图，使用原测试用例执行新旧程序，得到程序执行信息，获得目标方法集并对目标方法进行排序。测试用例扩增模块首先根据方法覆盖信息从原测试用例集中选取部分用例作为初始种群，再通过改进的天牛须搜索算法的位置更新公式引导天牛向最优解进化，最终生成覆盖目标路径的测试数据。

2.1 初始种群选择

将原测试用例集在新程序中执行，得到程序执行信息矩阵，对于目标方法$ {c}_{k} $，将所有覆盖该方法的测试用例作为扩增的初始测试数据，若无测试数据覆盖该方法，则将在旧程序中覆盖该方法的用例添加至初始种群。

2.2 适应度函数

使用代码分析工具Soot得到$ C\text{'} $中每个方法的控制流程图，根据路径的分支节点数获得需要覆盖的路径集，在目标路径的每个分支节点前插入分支距离函数$ {H}_{p} $，表示第$ p $个分支的分支距离。分支距离是一种常见的启发式方法，用于指导输入数据进行搜索，以解决分支的逻辑谓词中的约束问题^[20]。通过分支嵌套深度调整不同分支节点权重：

$ {G}_{p}=\frac{{D}_{p}}{\sum\limits _{p=1}^{q}{D}_{p}} $

其中：$ {D}_{p} $为通过程序流程图静态分析得到分支节点$ p $的嵌套深度；$ q $为被测程序针对给定目标路径的分支判定数目。通过上式计算出$ {G}_{p} $为分支节点$ p $的权重。

根据分支距离函数和分支嵌套深度设计适应度函数：

$ F\left(x\right)=\frac{1}{\epsilon +\sum\limits _{p=1}^{q}{G}_{p}\cdot {(1-1.001)}^{-{H}_{p}}} $

其中：$ \epsilon $是一个极小的常量以保证分母不为0，在此处设置$ \epsilon =0.01 $。若$ F\left(x\right) $的值越小，则表示越接近目标，因此目标路径覆盖问题可转换为适应度函数最小化问题。

2.3 改进的天牛须搜索算法

在D维解空间中，天牛位置$ x=({x}_{1}, {x}_{2}, \cdots , {x}_{D}) $，其左右两触须的位置为：

$ \left\{\begin{array}{c}{x}_{\mathrm{l}}=x+l\cdot d\\ {x}_{\mathrm{r}}=x-l\cdot d\end{array}\right. $

$ d = \left\lceil {\mathit{\boldsymbol{r}} \times \frac{2}{{{\mathop{\rm norm}\nolimits} (\mathit{\boldsymbol{r}})}}} \right\rceil $

其中：$ x $为当前位置；$ l $为天牛质心与触须间的距离；$ {x}_{\mathrm{l}} $为左须的位置；$ {x}_{\mathrm{r}} $为右须的位置；$ d $为天牛的随机朝向；$ \boldsymbol{r}=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{s}(n, 5) $是一个随机向量。在本文中，天牛的朝向为右须指向左须。天牛通过不断对比$ {x}_{\mathrm{r}} $与$ {x}_{\mathrm{l}} $附近位置的适应度，向适应度低的方向进行移动。

当前位置天牛根据规则移动到下一个位置：

$ x\text{'}=x+s\cdot d\cdot \mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}\left(F\right({x}_{\mathrm{l}})-F({x}_{\mathrm{r}}\left)\right) $

其中：$ s $为可变步长；$ F\left({x}_{\mathrm{l}}\right) $为左须的气味强度，气味强度即适应度函数；$ F\left({x}_{\mathrm{r}}\right) $为右须的气味强度，若$ F（{x}_{\mathrm{l}}） > F\left({x}_{\mathrm{r}}\right) $，$ \mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(·) $取1，天牛在$ d $的方向上以步长$ s $移动，反之，则向$ d $的反方向移动。

在本文中，使用Metropolis准则更新天牛的下一步位置，若新位置$ x\text{'} $的适应值小于$ x $的适应值，则接受$ x\text{'} $为当前位置，反之，则以随机概率接受$ x\text{'} $。步长遵循：

$ s = \left\{ {\begin{array}{*{20}{l}} {1 + s - \left\lfloor {s \times \frac{{{F_{{\rm{ave}}}} - F}}{{\frac{{{F_{\max }} - {F_{\min }}}}{2}}}} \right\rfloor , F \le {F_{{\rm{ave}}}}}\\ {s, F > {F_{{\rm{ave}}}}} \end{array}} \right. $

其中：$ F $为当前个体的适应值；$ {F}_{\mathrm{a}\mathrm{v}\mathrm{e}} $为去掉最大最小适应值后剩余个体适应值的平均数，称为假平均适应值；$ {F}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为最大适应值；$ {F}_{\mathrm{m}\mathrm{i}\mathrm{n}} $为最小适应值。若$ F\le {F}_{\mathrm{a}\mathrm{v}\mathrm{e}} $，则此时个体的性能良好，减小步长，反之，增大步长。

若达到最大迭代次数或测试数据覆盖目标路径，则输出测试数据，选取$ C\text{'} $中下一个目标方法，将已测试目标方法成功的测试用例和根据程序执行信息选取的测试用例作为初始测试数据，继续进行扩增，直至所有目标方法都被测试。

2.4 算法步骤

基于天牛须搜索的测试数据扩增算法的具体步骤如下：

输入  旧版本程序P的测试用例集T，新版本程序P′

输出  覆盖P′的测试用例集T′

步骤1   抽取方法调用图，使用原测试用例集运行新旧程序，获得程序的执行信息，得到需覆盖的目标方法集。

步骤2   对目标方法集进行排序，逐个选取目标路径，进行分支函数的插桩。

步骤3   根据程序执行信息选取部分测试用例。

步骤4   判断是否满足终止条件（测试用例覆盖目标路径或达到最大迭代次数），若满足，则转步骤9。

步骤5   计算测试用例的适应值，确定全局最大适应值、最小适应值和假平均适应值。

步骤6   利用位置更新方程预测天牛的位置。

步骤7   根据Metropolis准则更新天牛下一步位置。

步骤8   更新步长，转步骤4。

步骤9   算法结束，输出测试数据集。

3 实验与结果分析 3.1 实验设置

为验证MBAS方法的数据扩增效果，选用西门子工业程序集中的Schedule和Tcas、三角形判定程序Triangle以及基准程序NextDay作为实验中的测试程序，这些程序被广泛应用于验证不同测试方法的有效性^[21]。被测程序的基本信息如表 1所示。

在实验中应用Eclipse IDE for Eclipse Committers（Mars.2）编程实现天牛须算法和测试程序。针对不同程序运行算法30次，取实验结果的均值进行比较。实验对比方法为基于遗传算法（Genetic Algorithm，GA）的测试数据扩增方法（下文简称为GA方法）和基于粒子群优化（Particle Swarm Optimization，PSO）算法的测试数据扩增方法（下文简称为PSO方法），具体参数设置如表 2所示。

3.2 实验结果

实验选择GA和PSO方法与本文MBAS方法进行比较，在相同的环境下记录每种方法的迭代次数和运行时间，并计算实验数据的均值和标准差，实验结果如表 3和表 4所示。

以程序NextDay为例，在表 3中，GA方法需迭代39.0次，PSO方法需迭代27.1次，MBAS方法仅需迭代17.8次即可生成覆盖目标路径的测试数据。在表 4中，GA方法的运行时间为1.033 s，PSO方法的运行时间为0.481 s，而MBAS方法的运行时间仅为0.261 s。在迭代次数和运行时间上MBAS方法明显优于其他方法。

对实验结果中的迭代次数进行计算：

$ v\left(A\right|B)=\frac{e\left(B\right)-e\left(A\right)}{e\left(B\right)} $

其中：$ v\left(A\right|B) $为方法A相对于方法B提高的效率；$ e $表示方法的迭代次数。MBAS方法相对GA和PSO方法的扩增效率提升结果如图 2所示。

在图 2中，MBAS方法的扩增效率均高于GA和PSO方法。对于输入实参个数少的被测程序Triangle和NextDay，提升的平均扩增效率分别为48.11%和44.33%，而对于Schedule和Tcas，提升的平均扩增效率仅为28.48%和28.42%，即测试数据处于低维空间时扩增效率提升的更明显。对于测试数据扩增效率，MBAS方法比GA方法约平均提升了49.91%，比PSO方法约平均提升了24.76%。

根据表 3和表 4中的标准差，对于被测程序，MBAS方法迭代次数的平均标准差为4.15，均小于GA方法的平均标准差25.62和PSO方法的平均标准差7.85；MBAS方法运行时间的平均标准差为0.163，均小于GA方法的平均标准差0.511和PSO方法的平均标准差0.197，即MBAS方法具有更好的稳定性。

通过测试数据的迭代次数和目标路径覆盖率来评价不同回归测试数据扩增方法的能力，以程序Triangle为例，3种方法的目标路径覆盖率如图 3所示。

由图 3可知，MBAS方法的折线位置位于GA和PSO方法的上方，当迭代次数相同时，MBAS方法对目标路径的覆盖率最大；当目标路径覆盖率相同时，以100%为例，MBAS方法所需的迭代次数最少，优先完成路径覆盖，即MBAS方法在迭代次数和目标路径覆盖率方面均具有一定的性能优势。

通过上述分析可知，对于被测程序，MBAS方法可以有效利用原测试集，快速演化生成覆盖目标路径的测试集。

4 结束语

本文提出一种基于天牛须搜索的软件测试数据扩增方法MBAS，采用目标方法覆盖信息分析需要测试的方法，通过计算目标方法包含错误的影响度，对包含错误影响度大的目标方法进行优先分析生成测试数据集，并利用原测试数据集的目标方法覆盖信息来衡量测试数据的优劣，最终使用天牛须搜索算法演化测试用例使其覆盖目标路径。通过对多个程序进行测试，并将该方法与基于GA和PSO的测试数据扩增方法进行比较，实验结果表明，MBAS方法在测试数据的扩增效率和稳定性上均具有明显的性能优势。但由于天牛须搜索算法未能较好解决高维空间中解的收敛速度较慢的问题，因此后续将对此做进一步改进，提升MBAS方法在高维空间中的扩增效率。