基于自适应粒子群优化算法的测试数据扩增方法

王曙燕　温春琰　孙家泽

摘要：

针对在回归测试中原有测试数据集往往难以满足新版本软件测试需求的问题，提出一种基于自适应粒子群算法（APSO）的测试数据扩增方法。首先，根据原有测试数据在新版本程序上的穿越路径与目标路径的相似度，在原有的测试数据集中选择合适的测试数据，作为初始种群的进化个体；然后，利用初始测试数据的穿越路径与目标路径的不同子路径，确定造成两者路径偏离的输入分量；最后，根据路径相似度构建适应度函数，利用APSO操作输入分量，生成新的测试数据。该方法针对四个基准程序与基于遗传算法（GA）和随机法的测试数据扩增方法相比，测试数据扩增效率分别这只是一个实例的结果！平均提高了约56%和81%。实验结果表明，所提方法在回归测试方面有效地提高了测试数据扩增的效率，增强了其稳定性。

关键词：

回归测试；目标路径；测试数据扩增；路径相似度；粒子群优化算法

中图分类号：

TP311.5

文献标志码：A

Abstract：

It is difficult for the original test data to meet the requirements of the new version of software testing in regression testing， thus a new test data augmentation method based on Adaptive Particle Swarm Optimization （APSO） algorithm was proposed to solve the problem. Firstly， according to the similarity between the cross path in the original test data and the target path in the new version of the program，Firstly， according to the similarity between the cross path and the target path of the original test data in the new version of the program， the appropriate test data in the original test data was chosen as evolutionary individual of initial population. Secondly， taking advantage of different subpaths of the cross path of initial test data and target path， the input component which caused deviation between them was confirmed. Finally， the fitness function was created according to the path similarity， and the new data was generated by using the APSO algorithm to operate the input component. Compared with the genetic algorithm based and random algorithm based test data augmentation methods on four benchmark programs， the augmentation efficiency of the proposed method was improved on average by approximately 56% and 81% respectively. The experimental results show that the proposed method can effectively increase the efficiency and improve the stability of test data augmentation in regression testing.

英文關键词Key words：

regression testing； target path； test data augmentation； path similarity； Particle Swarm Optimization （PSO） algorithm

0引言

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

在现有的测试数据扩增方法中，Santelices等[2]利用控制流图和数据依赖图，结合符号执行进行分析，提出了测试数据集扩增需要满足链需求和状态需求；Qi等[3]将PIE （PropagationInfectionExecution）模型[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的交叉和变异操作，自适应地调整了算法的搜索过程，作用于穿越路徑与目标路径的偏移分量，以期增强其全局搜索能力，提高其收敛速度。

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

4.2实验结果

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

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

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

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

5结语

在面向覆盖的测试数据集扩增方法中，如何充分利用已

有测试数据和如何在测试数据的演化过程中利用更多的路径信息是提高测试数据扩增效率的关键问题。本文提出了一种

基于自适应粒子群算法的测试数据集扩增方法，该方法通过对多个基准程序和西门子工业程序进行测试，并与利用遗传算法和随机法的回归测试数据扩增方法进行比较，实验结果表明，本文所提方法在生成覆盖目标路径测试数据的效率和稳定性上都具有明显的提高。

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

参考文献：

[1]

张智轶，陈振宇，徐宝文，等.测试用例演化研究进展[J].软件学报，2013，24（4）：663-674.（ZHANG Z Y， CHEN Z Y， XU B W， et al. Research progress on test case evolution [J]. Journal of Software， 2013， 24（4）： 663-674.）

[2]

SANTELICES R， CHITTIMALLI P K， APIWATTANAPONG T， et al. Testsuite augmentation for evolving software [C]// ASE 08： Proceedings of the 2008 23th IEEE/ACM International Conference on Automated Software Engineering. Washington， DC： IEEE Computer Society， 2008： 218-227.

[3]

QI D， ROYCHOUDHURY A， LIANG Z. Test generation to expose changes in evolving programs [C]// ASE 10： Proceedings of the 25th IEEE/ACM International Conference on Automated Software Engineering. New York： ACM， 2010： 397-406.

[4]

VOAS J M. PIE： a dynamic failurebased technique [J]. IEEE Transactions on Software Engineering， 1992， 18（8）： 717-727.

[5]

PEARL J. Probabilistic Reasoning in Intelligent Systems： Networks of Plausible Inference [M]. San Francisco， CA： Morgan Kaufmann， 1988： 35.

[6]

XU Z， ROTHERMEL G. Directed test suite augmentation [C]// APSEC 2009： Proceedings of the 2009 International Conference on the AsiaPacific Software Engineering. Washington， DC： IEEE Computer Society， 2009： 406-413.

https：//www.computer.org/csdl/proceedings/apsec/2009/3909/00/3909a406-abs.html

XU Z. Directed test suite augmentation [C]// ICSE 11： Proceedings of the 2011 33rd International Conference on Software Engineering. New York： ACM， 2011： 1110-1113.

[7]

巩敦卫，任丽娜.回归测试數据进化生成[J].计算机学报，2014，37（3）：489-499.（GONG D W， REN L N. Evolitionary generation of regression test data [J]. Chinese Journal of Computers， 2014， 37（3）： 489-499.）

[8]

吴川，巩敦卫.基于路径相关性的回归测试数据进化生成[J].

计算机学报，2015，38（11）：2247-2261.（WU C， GONG D W. Evolutionary generation of test data for regression testing based on path correlation [J]. Chinese Journal of Computers， 2015， 38（11）： 2247-2261.）

[9]

BUENO P M S， JINO M. Automatic test data generation for program paths using genetic algorithms [J]. International Journal of Software Engineering and Knowledge Engineering， 2002， 12（6）： 691-709.

[10]

胡旺，李志蜀.一种更简化而高效的粒子群优化算法[J].软件学报，2007，18（4）：861-868.（HU W， LI Z S. A simpler and more effective particle swarm optimization algorithm [J]. Journal of Software， 2007， 18（4）： 861-868.）

[11]

史娇娇.基于遗传粒子群优化算法的测试数据自动生成技术研究[D].徐州：中国矿业大学，2014：34-48.（SHI J J. Study on the automatic test data generation based on genetic algorithm and particle swarm optimization algorithm [D]. Xuzhou： China University of Mining and Technology， 2014： 34-48.）

[12]

张岩，巩敦卫.基于搜索空间自动缩减的路径覆盖测试数据进化生成[J].电子学报，2012，40（5）：1011-1016.（ZHANG Y， GONG D W. Evolutionary generation of test data for path coverage based on automatic reduction of search space [J]. Acta Electronica Sinica， 2012， 40（5）： 1011-1016.）

[13]

DO H， ELBAUM S， ROTHERMEL G. Supporting controlled experimentation with testing techniques： an infrastructure and its potential impact [J]. Empirical Software Engineering， 2005， 10（4）： 405-435.