基于天牛须搜索的软件测试数据集扩增方法

摘要

基于天牛须搜索的软件测试数据集扩增方法，所属软件回归测试领域。针对原测试用例难以满足因软件演化引发修改的新程序的测试需求的问题，提出基于程序执行信息和天牛须搜索的测试用例扩增方法。静态分析新旧版本程序，获取方法调用图和程序执行信息，得到需测试的目标方法集，通过计算方法包含错误的影响度，对目标方法进行排序；根据原测试用例集的方法覆盖信息选取部分测试用例作为初始种群，通过分支距离和分支嵌套深度设计适应度函数，采用改进的天牛须搜索算法对有序目标方法集进行测试数据扩增。本发明利用方法调用图、程序执行信息和天牛须搜索算法进行回归测试数据的扩增，提高原测试用例的利用率，降低回归测试的成本。

说明书

技术领域

本发明属于软件测试技术领域，特别是在回归测试技术领域，用于进行扩增测试数据集，充分利用原有测试集满足软件演化过程中的测试需求，是一种软件测试数据集扩增方法。

背景技术

软件产品在开发和维护过程中因代码修改会触发软件演化行为，为了有效保障修改后的软件产品的质量，一般通过执行回归测试来保证代码修改模块的正确性并避免代码修改模块对被测程序其他模块产生的副作用。回归测试是指修改现有软件后，对演化软件重新测试，以确认新引入的修改没有引入新的错误或妨碍现有未修改部分的功能。

软件演化引发程序的修改与增加，回归测试中已有测试用例不能完全测试这些程序。为了满足软件演化的测试需求，保证测试数据集可以覆盖到程序的修改和新增部分，就需要对原测试用例集进行扩增。在进行回归测试数据扩增时，首先需要分析和提取目标，再对其进行测试数据的扩增，测试目标主要是程序中被修改及新增部分。测试用例集扩增需要充分利用已执行测试信息并结合软件演化信息辅助新测试用例生成。

与传统的测试用例生成相比，测试用例扩增覆盖的目标更具有针对性，而且利用已执行测试数据信息和程序演化信息辅助生成新测试数据，可以大大提高回归测试的用例集生成效率。目前，已有的测试用例集的产生方法大体上分为两类：第1类是面向行为的测试用例扩增技术，即期望新测试用例显示演化软件的执行变化；第2类是面向覆盖的测试用例集扩增技术，即期望新测试用例覆盖演化软件的新增和修改部分。

传统的测试数据集扩增技术限制条件多，回归测试中仍缺乏一种有效的用于测试用例自动扩增的方法。为此提出一种基于天牛须搜索的软件测试数据集扩增方法。对新旧版本程序进行静态分析，获取方法调用图和原测试用例在程序中的执行信息，得到需测试的修改的方法集，通过计算其包含错误的影响度进行排序。从原测试用例集中根据原测试用例的执行信息选取部分用例作为初始种群，采用改进的天牛须搜索算法对有序目标方法集进行测试数据的扩增。

发明内容

本发明要解决的问题是：现有的测试数据生成技术中原版本程序的测试用例难以满足新版本软件的测试需求问题，需要一种高效的新的回归测试数据扩增方法，在消耗较少资源的情况下，提高粒度分析程序可能引入的错误方法，提高原测试用例的利用率和回归测试效率。

本发明的技术方案为：前期预处理采用方法调用图、程序执行信息在方法级别分析程序可能引入修改方法部分，获取目标方法集，选择扩增的初始测试数据；后期采用改进的天牛须搜索算法针对目标方法集进行回归测试数据扩增。本发明的特征包括以下步骤：

(1)对于旧新版本程序P

若方法f

(2)对P

测试数据为t

对矩阵A和A′中同一测试用例的覆盖方法信息和执行结果信息做异或运算，得到目标方法集

(3)假定方法集相互独立，初始方法f

计算旧新程序中目标方法的执行概率P(c

P″(c

计算新程序中目标方法的权值N(c

S(c

将S(c

(4)使用Soot代码分析工具和Graph viz得到C′

其中，d

其中，ε是一个极小的常量以保证分母不为0，设ε＝0.01；

(5)根据步骤(2)得到的测试用例在旧新程序中方法的执行信息矩阵，对于目标方法c

(6)对步骤(5)中的初始群体采用改进的天牛须搜索算法，假设天牛个体在解空间中的位置为x.，则其左须坐标为x

x′＝x+s·d·sign(f(x

其中，x为当前位置，s为搜索的可变步长大小，sign(·)是符号函数，用来确定天牛下一步的移动方向，f(x

其中，f为当前个体的适应度，f

若达到最大迭代次数或测试数据覆盖目标路径，则输出满足的测试数据，选取C′

本发明通过白盒测试技术分析程序获取方法调用图，根据原测试数据建立方法执行信息，通过对旧新程序执行信息的对比获取目标方法集；计算旧新程序中方法可能包含错误的概率，与方法权值进行乘积，计算出方法包含错误的影响度，从而对目标方法集进行排序；通过比较旧新程序方法执行信息，选择与目标方法相关联的部分测试用例作为初始测试数据，采用改进的天牛须搜索算法对目标方法对应的测试路径集依次进行扩增。该回归测试数据扩增方法，将分析新版本程序发生改变部分的粒度提到方法级别，针对方法内部进行静态分析，发现可能引入错误的修改的方法，得到需测试的目标路径，最后通过改进的天牛须搜索算法中的天牛的朝向和步长对测试用例进行优化，生成覆盖目标路径的新测试数据。程序的方法调用和方法静态分析，使生成的测试用例更加精准，提高原测试数据的利用率，降低新测试数据的生成代价。

附图说明

图1是本发明方法的流程图

图2是Doxygen分析Java实例程序得到的方法调用图

图3是Soot分析某一方法得到的程序控制流图

图4是本发明方法对三角形分类程序Triangle进行测试用例集扩增与其他三种方法的目标路径覆盖率对比情况

具体实施方式

如图1，本发明结合软件的演化信息与改进的天牛须搜索算法进行回归测试用例集的扩增，前期预处理部分采用程序的方法调用图、方法覆盖执行信息获取有序目标方法集和初始测试用例，后期采用优化算法进行回归测试数据扩增，具体步骤如下：

(1)对Java程序用Doxygen工具生成的方法调用图如图2所示；

(2)利用原测试集t

(3)计算得出目标方法在旧程序中被调用的概率为P(c

(4)以测试方法f

表1不同分支条件距离函数

(5)通过新程序执行信息的矩阵，将覆盖方法f

(6)计算种群中各个个体的适应度，如果存在适应度值为0的用例，则满足条件，输出测试用例，否则，通过改进的天牛须搜索算法计算下一步位置，使用Metropolis准则对种群的下一步位置进行更新，更新步长，继续局部搜索或全局搜索操作，直到达到最大迭代次数或适应度值为0时输出测试用例；继续在测试路径集中选择下一条目标路径，生成覆盖目标路径的测试数据；选取有序目标方法集的下一个方法，直至目标方法全部被覆盖。

通过以上过程可以识别出修改后可能引入错误的方法集并对其进行回归测试数据集的扩增，为了说明本发明的有效性，在相同的条件下，对测试程序各定义一个或多个修改点，分别使用本发明方法(MBAS)、传统遗传算法(GA)和传统粒子群算法(PSO)运行30次，生成覆盖目标路径的测试数据，记录每种方法的进化代数，分别计算它们的平均值和标准差，以此来衡量测试数据扩增方法的效率和稳定性。测试程序选用西门子工业程序集中的Sch edule和Tcas，三角形判定程序Triangle以及基准程序NextDay，在相同条件下分别运行每种方法，记录其测试数据进行扩增时的迭代次数，实验结果如表2所示：

表2不同算法扩增测试数据的迭代次数

以程序NextDay为例，遗传算法需迭代39.0次，粒子群算法需要迭代27.1次，本方法需迭代约17.8次即可生成覆盖目标路径的测试数据。本发明方法与基于遗传算法和粒子群算法的测试数据扩增方法相比，测试数据扩增效率分别提高了约54.35％和34.31％。

以三角形分类程序Triangle为例，不同方法生成的测试数据路径覆盖率如图4，从测试数据的覆盖率评价不同回归测试数据扩增方法，本发明方法与其它两种方法相比，能通过较少的迭代次数覆盖到目标路径，说明本方法在效率方面有较好的效果。

表2中本方法迭代次数的标准差均低于其它两种方法，说明本发明方法在软件测试数据扩增方面具有较高的稳定性。

综合实验数据，在相同条件下，本发明利用方法调用图、程序执行信息、程序的控制流图与改进的天牛须搜索算法相结合，测试数据扩增的效率优于遗传算法(GA)和粒子群算法(PSO)，能够有效的提高测试数据扩增的效率，充分利用原测试用例，提高回归测试效率。