0 引言

在回归测试的过程中，测试人员通过重新测试新版本软件，以验证新版本软件没有被加入新的错误或引起其他代码产生错误^[1]。为了覆盖软件的修改和新增部分，需要对原有测试数据集进行扩增。与传统的测试数据生成相比，测试数据扩增在对比软件新旧版本、分析软件修改影响的基础上，针对软件变化产生新的测试数据，以提高软件的测试效率。

在现有的测试数据扩增方法中，Santelices等^[2]利用控制流图和数据依赖图，结合符号执行进行分析，提出了测试数据集扩增需要满足链需求和状态需求；Qi等^[3]将PIE (Propagation-Infection-Execution)模型^[4]引入到测试数据扩增方法中，在路径引导过程中通过符号执行和CEPT(Change Effect Propagation Tree)^[5]发现变量在修改后未被执行和执行后是否发生变化，以确保扩增的测试数据能够影响输出结果；Xu等^[6]将Concolic Testing技术引入到测试数据扩增方法中，根据软件的演化信息选择有利于覆盖目标路径的测试数据，利用已有测试用例结合实体测试和符号测试产生新的测试数据。

在上述的方法中，Santelices等^[2]和Qi等^[3]提出的方法没有考虑已有测试数据的利用，而Xu等^[6]的方法仅对测试数据的数量进行了缩减，并不能保证筛选出的测试数据的质量。针对上述问题，巩敦卫等^[7]采用遗传算法(Genetic Algorithm, GA)进行测试数据扩增，合理地利用了已有的测试数据形成初始进化种群，有效提高了测试数据的生成效率；但是并没有将GA中起核心作用的交叉算子与程序演化信息相结合，降低了遗传算法全局搜索的能力。

粒子群优化(Particle Swarm Optimization, PSO)算法作为一种简单高效的智能计算方法，在很多领域取得了成功，但在测试数据扩增中的应用还未见公开文献的报道。本文研究采用自适应粒子群优化(Adaptive Particle Swarm Optimization, APSO)算法结合软件演化信息进行测试数据扩增，利用测试数据的穿越路径与目标路径的相似度矩阵选择原有的测试数据集，避免了GA的交叉和变异操作，自适应地调整了算法的搜索过程，作用于穿越路径与目标路径的偏移分量，以期增强其全局搜索能力，提高其收敛速度。

1 回归测试数据集扩增的数学模型 1.1 基本概念

定义1  测试数据集扩增。设程序P，P′为P的新版本程序，T为P的测试数据集, 通过利用已执行测试数据信息和程序演化信息生成新测试数据集T′，使得T′中的测试数据可以覆盖P′的修改和新增部分，T∪T′满足演化软件的测试需求。

定义2  路径。记新版本程序P′包含的路径为p′₁, p′₂, …, p′_m，m是新版本程序P′包含的路径个数，路径p′_i穿越的节点序列为n′_i1, n′_i2, …, n′_i|p′i|(1≤i≤m)，|p′_i|为路径p′_i的节点个数。

定义3  目标路径。记已有测试数据集T包含的测试数据为t₁, t₂, …, t_n，测试数据集T在新版本程序P′中穿越的路径为p′(t₁), p′(t₂), …, p′(t_n)，则目标路径为：

$ P{'_{{\rm{target}}}} = \left\{ {p{'_1},p{'_2} \cdots p{'_m}} \right\} - \left\{ {p'\left( {{\boldsymbol{t}_1}} \right),p'\left( {{\boldsymbol{t}_2}} \right), \cdots p'\left( {{\boldsymbol{t}_n}} \right)} \right\} $

(1)

定义4  路径相似度。对于程序P′的路径p′_i和p′_j穿越的节点序列分别为n′_i1, n′_i2, …, n′_i|p′i|和n′_j1, n′_j2, …, n′_j|p′j|，记路径p′_i和p′_j穿越的相同节点个数记为N_same，则路径p′_i相对于p′_j的路径相似度记为S(p′_i, p′_j)，可表示为：

$ S\left( {p{'_i},p{'_j}} \right) = {N_{{\rm{same}}}}/\left| {p{'_j}} \right| $

(2)

其中，N_same=|p′_i∪p′_j|。

路径相似度可以从侧面衡量两条路径之间的相关度，反映了两条路径之间的相似程度。在程序中，前面的节点往往对后面的节点存在占优关系^[8]，所以路径p′_i相对于p′_j的路径相似度可以通过计算路径p′_i对p′_j的节点满足程度得到。由式(2)可以看出0≤S(p′_i, p′_j)≤1，S(p′_i, p′_j)越大，这两条路径相同的节点越多，当S(p′_i, p′_j)=1时，路径p′_i和p′_j为相同路径。例如，有3条路径p′₀:n₀, n₁, n₂, n₄, n₅；p′₁:n₀, n₁, n₂, n₃, n₄, n₅；p′₂:n₀, n₂, n₃, n₄, n₅；则，|p′₀∩p′₁|=5，S(p′₀, p′₁)≈0.83；|p′₀∩p′₂|=4，S(p′₀, p′₂)≈0.8。

1.2 测试数据集扩增数学模型

基于以上分析，测为：对于新版本程序P′，以测试数据t作为程序P′的输入，执行的路径记为p′(t)，若存在目标路径p_i^*∈P′_target(0≤i≤|P_target|)，使得p′(t)与p′_i的路径相似度S(p′(t), p_i^*)=1，则路径p′(t)与p′_i为相同路径，那么t即为覆盖目标路径p_i^*的期望测试数据。

这样一来，回归测试的测试数据扩增问题就转化为求取路径相似度S(p′(t), p_i^*)最大值问题。对于所有目标路径P′_target而言，生成覆盖目标路径p₁^*, p₂^*, …, p_|p′target|^*的测试数据问题，就可以转化为求取S(p′(t), p₁^*), S(p′(t), p₂^*), …，S(p′(t), p_|p′target|^*)的最大值问题，其数学模型为：

$ \begin{array}{l} \;\;\;\;\max \left( {{f_1}\left( \boldsymbol{t} \right),{f_2}\left( \boldsymbol{t} \right), \cdots {f_s}\left( \boldsymbol{t} \right)} \right)\\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\boldsymbol{t} \in D \end{array} $

(3)

其中：1≤i≤s，f_i(t)=S(p′(t), p_i^*)，s=|P_target|，D为程序P′的输入域。

2 回归测试数据集扩增方法 2.1 初始种群选择

如何利用已有的测试数据生成新的测试数据，是回归测试数据扩增的关键问题。Bueno等^[9]提出具有相似穿越路径的两个测试数据也有一定的相似性，采用相似的已有测试数据作为初始种群进行测试数据扩增，可以大幅度减少测试数据的生成个数，所以，利用已有测试数据进行测试数据扩增是非常必要的。

在程序中，以已有测试数据集t₁, t₂, …, t_m作为输入在新版本程序P′运行后，产生的执行路径为p′(t₁), p′(t₂), …, p′(t_m)，根据式(2)计算已有测试数据的执行路径与目标路径P′_target的相似度s_ij=S(p′(t_i), p_j^*)，可以得到如下的相似度矩阵M:

$ \boldsymbol{M} = \left[ {\begin{array}{*{20}{c}} {{s_{11}}}&{{s_{12}}}& \cdots &{{s_{1n}}}\\ {{s_{21}}}&{{s_{22}}}& \cdots &{{s_{2n}}}\\ \vdots & \vdots &{}& \vdots \\ {{s_{m1}}}&{{s_{m2}}}& \cdots &{{s_{mn}}} \end{array}} \right] $

(4)

其中，m为测试数据集T在程序P′上的穿越路径的个数，n=|P′_target|，s_ij为测试数据t_i的穿越路径p(t_i)与目标路径p_j^*(p_j^*∈P_target)的相似度S(p(t_i), p_j^*)，若存在k∈{1, 2, …, m}，使得${s_{kj}} \ge \frac{1}{m}\sum\limits_{i = 1}^m {{s_{ij}}} $，则选择第k行对应的测试数据t_k作为测试数据扩增的初始测试数据，会非常有利于生成覆盖目标路径p_j^*的测试数据。

2.2 自适应粒子群算法

目前，关于粒子群算法与其改进算法在进化方程中都包含了位置矢量x和速度矢量v, 而在回归测试数据扩增的过程中，往往很难依靠经验来设定粒子的速度阈值。利用胡旺等^[10]提出的算法，只需要考虑x的直接变化，使粒子的位置x逼近当前问题的最优解x^*，其进化方程为：

$ \boldsymbol{x}_i^{t + 1} = w\boldsymbol{x}_i^t + {c_1}{r_1}\left( {{\boldsymbol{x}_{id}} - \boldsymbol{x}_i^t} \right) + {c_2}{r_2}\left( {{\boldsymbol{x}_{{\rm{gd}}}} - \boldsymbol{x}_i^t} \right) $

(5)

其中：x_i^t和x_i^t+1为第t和t+1代种群中第i个粒子的位置；p_id为个体最优，p_gd为全局最优；w为惯性权重；c₁、c₂为学习因子；r₁、r₂为服从U(0, 1)分布的独立随机变量。

改进后的进化方程去掉了粒子速度概念，惯性权重w直接作用于粒子位置，因此惯性权重w对算法的收敛速度和精度起到决定性的作用。实验表明，当w较大时，有利于跳出局部的最优值，这时便于全局搜索；当w较小时，则有利于算法局部搜索。

因此，在粒子群算法的迭代过程中，本文利用文献[11]提出的方法，利用粒子聚集度自适应地调整惯性权重w，建立APSO。其中，粒子聚集度δ的计算公式为：

$ \delta = \left| {{f_{\rm{g}}} - f{'_{{\rm{avg}}}}} \right| $

(6)

其中：f_g为种群的全局最优解；f_avg为种群粒子的平均适应值；f′_avg通过种群中适应值不小于f_avg的粒子适应值再次平均得到。

根据上述提出的自适应调整方案，结合本文的适应度函数，惯性权重w随着粒子的适应值和聚集度进行自适应调整的方法如下：

1) 若f(x_i)>f′_avg，则认为x_i比较接近最优解，惯性权重w应越小：

$ w = {w_{\max }} - \frac{{\left( {{w_{\max }} - {w_{\min }}} \right)\left| {f\left( {{\boldsymbol{x}_i}} \right) - f{'_{{\rm{avg}}}}} \right|}}{{\left| {f\left( {{\boldsymbol{x}_i}} \right) - f{'_{{\rm{avg}}}}} \right|}} $

(7)

2) 若f_avg≤f(x_i)≤f′_avg，则认为该粒子的状况相对普通，w会随着迭代次数的增加，在搜索解的过程中非线性地逐渐减小，利用余弦定理可以很好地描述：

$ w = {w_{\min }} + \left( {{w_{\max }} - {w_{\min }}} \right)\frac{1}{2}\left( {1 + \cos \frac{t}{T}\pi } \right) $

(8)

其中:t为当前进化代数，T为最大进化代数。

3) 若f(x_i) < f_avg，则认为新生成的粒子状况较差，当种群过早收敛时，需要增大w打破当前的稳定；而当种群过于发散时，需要减小w使种群趋于收敛。利用指数函数可以很好地描述：

$ w = c - \frac{1}{{1 + \exp \left( { - \delta } \right)}} $

(9)

其中c为常数。

利用上述的进化方程(5)作用于程序的输入分量，即可在测试数据进化的过程中生成新的测试数据。输入分量是造成测试数据的执行路径偏离目标路径p_i^*的主要原因，它可以通过已有测试数据集T在新版本程序P′上的穿越路径p′(t₁), p′(t₂), …, p′(t_m)与目标路径p_i^*的不同子路径P_dif，结合文献[12]所提方法，确定造成测试数据穿越路径与目标路径差异的输入分量t_i1, t_i2, …, t_in。其中P_dif可表示为：

$ \begin{array}{l} {P_{{\rm{dif}}}}{\rm{ = }}p_i^* - p'\left( {{\boldsymbol{t}_1}} \right) \cap p_i^*,p_i^* - p'\left( {{\boldsymbol{t}_2}} \right) \cap p_i^*, \cdots ,\\ \;\;\;\;\;\;\;\;p_i^* - p'\left( {{\boldsymbol{t}_m}} \right) \cap p_i^* \end{array} $

(10)

2.3 基于APSO算法的测试数据集扩增模型

基于APSO算法的测试数据集扩增模型可分为程序解析、APSO和测试运行三个模块，如图 1所示。

其中：程序解析模块是整个模型的基础部分，该部分通过静态分析构建控制流图，将原有测试数据集输入到测试运行模块得到穿越路径，然后选择出新版本程序需要覆盖的目标路径，并计算出穿越路径和目标路径的相似度矩阵，从而选择出APSO模块需要的初始种群；APSO是核心模块，根据粒子的适应值、进化方程和惯性权重调整公式来引导粒子向目标解进化，最终生成覆盖目标路径的测试数据集；测试运行模块在整个模型中起到桥梁的作用，通过接收测试数据，输出测试数据的穿越路径。

2.4 算法步骤

本节以利用原程序P的测试数据集T生成覆盖新版本程序P′的测试数据为例，详细介绍基于APSO算法的测试数据集扩增方法的实现步骤：

输入  原程序P的测试数据集T，新版本程序P′；

输出  覆盖P′的测试数据集。

步骤1  利用式(4)计算相似度矩阵，选取初始种群，设定初始参数。

步骤2  判断是否满足终止条件，即扩增的测试数据覆盖P′的目标路径，或达到最大进化代数。若满足，转步骤6。

步骤3  根据前文提出的适应度函数(3)，计算测试数据的适应值，根据适应值的大小调整个体最优值p_id和全局最优值p_gd，同时利用式(7)~(9)设定惯性权重w。

步骤4  利用式(10)，以步骤1选择的测试数据作为输入，得到穿越路径与目标路径的不同子路径P_dif，确定输入分量t_i1, t_i2, …, t_in。

步骤5  将步骤3计算的参数代入式(5)，更新输入分量t_i1, t_i2, …, t_in，生成新的测试数据，转步骤2。

步骤6  算法结束，输入覆盖P′的测试数据集。

3 实例分析

本章以三角形判断程序为例来说明本文方法的有效性。修改前后的三角形判定程序的控制流如图 2所示。其中，原程序P的分支节点n₁、n₃和n₅分别判断是否是三角形、等边三角形和等腰三角形；修改后程序P′在原程序P的基础上添加了分支节点n₆、n₉、n₇和n₁₁，分别判断是否是锐角三角形、直角三角形、锐角三角形和直角三角形。假设覆盖原程序P中所有路径的测试数据为t₁=(1, 2, 3)，t₂=(2, 2, 2)，t₃=(2, 2, 3)，t₄=(3, 4, 5)。

根据本文方法，原程序的测试数据集在修改后程序P′的穿越路径为p′₁={n₁, n₂}，p′₂={n₁, n₃, n₄}，p′₃={n₁, n₃, n₅, n₆, n₉, n₁₃}，p′₄={n₁, n₃, n₅, n₇, n₁₁, n₁₄}，根据式(1)得到P′_target=P′-P′_execute={{n₁, n₃, n₅, n₆, n₈}，{n₁, n₃, n₅, n₆, n₉, n₁₂}, {n₁, n₃, n₅, n₇, n₁₀}, {n₁, n₃, n₅, n₇, n₁₁, n₁₅}}。

然后，利用上一步得到的穿越路径P′_execute与目标路径P′_target，利用式(4)计算相似度矩阵：

$ \boldsymbol{M} = \left[ {\begin{array}{*{20}{c}} {0.20}&{0.17}&{0.20}&{0.17}\\ {0.40}&{0.33}&{0.40}&{0.33}\\ {0.80}&{0.83}&{0.60}&{0.50}\\ {0.60}&{0.50}&{0.80}&{0.83} \end{array}} \right] $

以目标路径{n₁, n₃, n₅, n₆, n₈}对应的第一列为例，计算第一列的平均值为0.5，根据式(5)，选择执行路径p′₃={n₁, n₃, n₅, n₆, n₉, n₁₃}，p′₄={n₁, n₃, n₅, n₇, n₁₁, n₁₄}所分别对应的测试数据t₃=(2, 2, 3)，t₄=(3, 4, 5)作为初始种群，生成覆盖目标路径{n₁, n₃, n₅, n₆, n₈}的测试数据。

最后，根据3.2节的内容对初始种群进行演化。由初始种群的适应度p′(t₃)=0.8，p′(t₄)=0.6，利用自适应粒子群算法惯性权重w的调整方法，计算出f_g=0.8，f_avg=0.7，f′_avg=0.8，δ=0；以初始粒子t₃为例，由f_avg≤f(t₃)≤f′_avg，可得$w = {w_{\min }} + \left( {{w_{\max }} + {w_{\min }}} \right)\frac{{1 + \cos \frac{t}{T}\pi }}{2}$，由于测试数据t₃为初始种群，所以t=0，w=w_max，将w代入进化式(6)得到粒子的下一代，计算该粒子的适应值，判断是否满足终止条件，若不满足，则根据粒子的适应值大小重新设定该粒子的局部最优、种群的全局最优和惯性权重，使粒子进入下一次的迭代；若满足，则输出覆盖新版本程序P′所有路径的测试数据。

4 实验与分析 4.1 实验设置

为验证本文方法的有效性，测试程序除了选用三角形判定程序Triangle之外，还选择了基准程序NextDay以及西门子工业程序集中的Tcas和Schedule，上述程序广泛应用于验证不同测试方法的有效性^[13]，其基本信息如表 1所示。

在实验过程中，所有程序均采用Java语言编写，在jdk1.6.0 _24环境下运行，计算机主频为3.20 GHz，内存为2 GB。针对自适应粒子群算法的基本参数设定如下：进化最大代数T=1000，学习因子c₁=c₂=2，惯性权重w_max=1.8, w_min=0.4。

4.2 实验结果

为验证本文方法的有效性，选择基于遗传算法(GA)和随机法的测试数据扩增方法与本文方法进行比较，在相同的条件下，对测试程序各定义一个或多个修改点，分别运行20次，生成覆盖目标路径的测试数据，记录每种方法的进化代数和耗时，分别计算它们的平均值和标准差，最终实验结果如表 2所示。

在表 2中，以空中防撞系统Tcas为例，相比遗传算法需要迭代189.2次、运行时间15.432 s，以及随机法未能在规定的最大代数T=1000中完成测试要求，本文方法只需迭代约19.8次、运行时间0.724 s即可生成覆盖目标路径的测试数据。综合各计算各种扩增方法在不同基准程序的扩增效率，本文方法与基于遗传算法和随机法的测试数据扩增方法相比，测试数据扩增效率平均分别提高了约56%和81%。由此可看出本文方法在回归测试中生成覆盖目标路径的测试数据具有较高的效率。而且，通过多次运行结果求得的标准差可以看出，本文方法在稳定性方面也具有较好的优势。

同时，通过比较不同方法在迭代的过程对目标路径的覆盖率，来评价不同回归测试数据扩增方法的性能。以空中防撞系统Tcas为例，不同方法在迭代过程中对目标路径的覆盖率如图 3所示。由图 3可以看出，本文方法与其他两种方法相比，在覆盖目标路径方面具有明显的优势，且有效地避免了在回归测试数据扩增过程中测试数据陷入局部最优解的问题。

通过上述分析，可以得到如下结论：对于基准程序和西门子工业程序，本文提出的基于自适应粒子群算法的回归测试数据集扩增方法在充分利用原有测试数据集的基础上，可以消耗较少的代价，更稳定地生成覆盖目标路径的测试数据集。

5 结语

在面向覆盖的测试数据集扩增方法中，如何充分利用已有测试数据和如何在测试数据的演化过程中利用更多的路径信息是提高测试数据扩增效率的关键问题。本文提出了一种基于自适应粒子群算法的测试数据集扩增方法，该方法通过对多个基准程序和西门子工业程序进行测试，并与利用遗传算法和随机法的回归测试数据扩增方法进行比较，实验结果表明，本文所提方法在生成覆盖目标路径测试数据的效率和稳定性上都具有明显的提高。

在回归测试数据的扩增过程中，利用测试数据的穿越路径和目标路径的相似度来衡量测试数据的优劣，虽然在一定程度上提高了测试数据生成的效率和稳定性，但是在复杂的实际软件中，如何在测试数据的演化过程中利用更多的路径信息，进而提高生成覆盖目标路径测试数据的效率，是下一步需要继续研究的问题。