一种并行的基于蚁群算法的测试用例序列生成方法

摘要

一种并行的基于蚁群算法的测试用例序列生成方法，首先确定了影响测试用例优先级的因素，然后利用蚁群优化算法分析测试用例的优先级，接着将设计的算法进行多核并行处理，最后对测试用例优先级分析结果进行评价，得到最优测试用例序列。本发明方法将测试用例可以发现的缺陷数量、测试用例的执行时间和测试用例发现的缺陷的严重性作为信息素更新规则和测试用例节点选择规则的参数，与现有技术相比，可以在回归测试过程更快的检测出比较重要的缺陷，而且实现简单，便于操作，适用于回归测试中的大规模测试用例的优先级排序，提高了回归测试过程的有效性和快速性。

说明书

技术领域

本发明涉及算法优化设计与软件测试领域，特别是一种并行的基于蚁群算法的测试用例序列生成方法。

背景技术

当软件修改或升级后，为了保证改进后的软件不引入新的软件缺陷就必须进行回归测试，传统的回归测试是软件开发和维护中的重要活动过程。回归测试过程通常是一个集成测试过程，涉及到大量的测试用例的执行，因此，该过程非常耗时，而测试用例优先级分析方法是软件回归测试中提高效率的一种有效方法。

目前，智能优化算法分析测试用例优先级取得了很好的效果，如遗传算法、蚁群算法、粒子群算法等的应用，这些已有的算法在测试用例优先级分析过程中存在两方面的不足：一方面是在分析过程中没有利用多核并行处理的优势，而智能优化算法本身具有较强的并行性，可以利用多核并行计算来提高效率；另一方面是通常假设测试用例检测出的软件缺陷具有等同性，在算法设计中没有考虑不同软件缺陷对软件质量的影响不同。

发明内容

本发明解决的技术问题是：克服现有技术的不足，提供了一种通过将蚁群优化算法和多核并行计算相结合，提高了测试用例优先级排序有效性与快速性的并行的基于蚁群算法的测试用例序列生成方法。

本发明的技术解决方案是：一种并行的基于蚁群算法的测试用例序列生成方法，包括如下步骤：

(1)基于蚁群算法分别使用n只蚂蚁从初始待选择测试用例列表中选择测试用例，然后分别更新蚂蚁的待选择测试用例列表，继续选择下一测试用例且更新蚂蚁的待选择测试用例列表，重复上述过程直至n只蚂蚁选择的测试用例序列长度均为n，得到第1次迭代n只蚂蚁的测试用例序列，其中n只蚂蚁并行选择测试用例或更新其待选择测试用例列表；所述初始待选择测试用例列表包括测试用例Ti，i＝1,2,3，，，n；所述更新蚂蚁的测试用例列表方法为将该蚂蚁选择过的测试用例从初始待选择测试用例列表中剔除；

(2)对缺陷的严重性进行划分后得到其严重性数值，并记为S(l)，然后计算测试用例Ti可以发现的缺陷数目、测试用例Ti的执行时间得到测试用例Ti的缺陷检出效率Rf_i，并计算测试用例Ti在所有测试用例中的重要程度IS_i，其中

$>{\mathrm{IS}}_i=\frac{{\mathrm{Sf}}_i}{\max \left(\mathrm{Sf}\right)}$>

$>{\mathrm{Sf}}_i={\Sigma }_{l=1}^{r}S\left(l\right)$>

l＝1,2,3，，，q，q为缺陷的数目，max(Sf)为测试用例中缺陷严重性数值的最大值，r是测试用例Ti可以检出的缺陷数量；

(3)对测试用例Ti与测试用例Td构成的路径上的信息素进行更新，

τ_id(t+1)＝(1-ρ)·τ_id(t)+Δτ_id

$>{\mathrm{\Delta \tau }}_{\mathrm{id}}={\Sigma }_{k=1}^n{\mathrm{\Delta \tau }}_{\mathrm{id}}^k$>

$>{\mathrm{\Delta \tau }}_{\mathrm{id}}^k=\left(\begin{array}{c}Q*h\left(k\right)\\ 0\end{array}\right)$>若蚂蚁k选择了测试用例节点Ti到测试用例节点Td间的路径其他情况

$>h\left(k\right)=\frac{{\Sigma }_{i=1}^{M_k}{\mathrm{Rf}}_i^k\left(t\right)}{M_k}$>

其中，d＝1,2,3，，，n，t为迭代次数且初值为1，τ_id(1)为0.5，ρ为信息素的消散速率，τ_id(t+1)是在(t+1)次迭代过程中从测试用例节点Ti到测试用例节点Td之间的路径上的信息素更新量，τ_id(t)为第t次迭代过程中Ti到Td之间的路径上的信息素，(1-ρ)·τ_id(t)为第t次迭代过程中Ti到Td之间的路径上残留的信息素，Δτ_id为第t次迭代过程中Ti到Td之间的路径上总的信息素增量，为第t次迭代过程中蚂蚁k在Ti到Td之间的路径上留下的信息素，Q为常量，表示蚂蚁拥有的信息素总量，h(k)是第t次迭代过程中蚂蚁k在t次迭代中关于缺陷检出效率的函数，M_k是第t次迭代过程中蚂蚁k检出所有缺陷时选择的测试用例数，Rf_i^k(t)为第t次迭代过程中蚂蚁k选择的测试用例Ti的缺陷检出效率Rf_i；

(4)分别使用n只蚂蚁分别从初始待选择测试用例列表中选择测试用例，分别更新蚂蚁的待选择测试用例列表，然后分别从其待选择测试用例列表中选择转移概率最大的测试用例并更新蚂蚁的待选择测试用例列表，重复上述过程直至n只蚂蚁选择的测试用例序列长度均为n，得到第t+1次迭代n只蚂蚁的测试用例序列；所述转移概率为当前测试用例情况下跳转至另一测试用例的概率，其中，测试用例Ti跳转至测试用例Td的转移概率为

其中，η_id(t)＝IS_d(t)，α,β为调节参数，s为正整数，为蚂蚁k在选择测试用例Ti后的待选择测试用例列表，n只蚂蚁并行选择测试用例或更新其待选择测试用例列表；

(5)t＝t+1，并重复步骤(3)至步骤(4)直至第a次迭代得到的n只蚂蚁的测试用例序列与第a-1次迭代得到的n只蚂蚁的测试用例序列相同，其中a不小于2；

(6)使用APFD度量标准计算第1到a次迭代得到的n只蚂蚁的测试用例序列的APFD值，并选择APFD值最大的测试用例序列作为最优化的测试用例序列输出。

所述的步骤(1)中的从初始待选择测试用例列表中选择测试用例，步骤(1)中的继续续择下一测试用例或者步骤(4)从初始待选择测试用例列表中选择测试用例的方法为随机选择。

所述的步骤(2)中对缺陷的严重性进行划分后得到其严重性数值的方法包括如下步骤：

(1)根据软件中缺陷的严重性将缺陷划分为待观察缺陷等级、轻微缺陷等级、一般缺陷等级、重要缺陷等级、严重缺陷等级；

(2)对各个缺陷的严重性等级进行定量化并得到各个缺陷对应的严重性数值S(l)，其中，待观察缺陷等级的严重性数值为2，轻微缺陷等级的严重性数值为4，一般缺陷等级的严重性数值为6，重要缺陷等级的严重性数值为8，严重缺陷等级的严重性数值为10。

本发明与现有技术相比的优点在于：

(1)本发明方法将测试用例可以发现的缺陷数量、测试用例的执行时间和测试用例发现的缺陷的严重性作为信息素更新规则和测试用例节点选择规则的参数，与现有技术相比，可以在回归测试过程更快的检测出比较重要的缺陷；

(2)本发明方法与现有技术相比，将蚁群算法及智能优化算法并行特性加入生成过程当中，最终生成的测试序列不仅具有较好的优先级，而且生成速度快；

(3)本发明方法与现有技术相比，克服了现有技术忽视不同软件缺陷对软件质量影响不同的不足，另外实现简单，便于操作，适用于回归测试中的大规模测试用例的优先级排序，提高了回归测试过程的有效性和快速性。

附图说明

图1为本发明方法原理流程图；

图2为本发明方法中测试用例优先级分析的蚁群算法建模示意图；

图3为不同测试用例执行排序下的APFD；

图4是不同测试用例执行排序下的检出缺陷的严重性；

图5是不同测试用例执行排序下的时间。

具体实施方式

本发明提出在软件回归测试过程中一种并行的基于蚁群算法的测试用例序列生成方法，通过蚁群优化算法和多核并行计算相结合，提高了测试用例优先级排序的有效性和快速性，包括(1)确定影响测试用例优先级的因素；(2)蚁群优化算法分析测试用例的优先级；(3)蚁群优化算法的多核并行处理；(4)测试用例优先级分析结果的评价。下面结合实例对本发明做进一步说明：

步骤一：确定影响测试用例优先级的因素

(1)计算测试用例的缺陷检出效率

测试过程中测试用例的选择和排序受多种因素的影响，针对回归测试而言，考虑的主要影响因素有三个：测试用例可以发现的缺陷数量、测试用例的执行时间和测试用例发现的缺陷的严重性，本发明方法总和考虑该三个因素，其中，测试用例可以发现的缺陷数量反映了该测试用例对软件缺陷检测的覆盖能力，一个测试用例在执行过程中可能发现一个或多个软件缺陷，发现的软件缺陷越多，说明该测试用例对软件缺陷的覆盖能力越强，优先级越高；测试用例的执行时间反映了该测试用例的测试效率，在回归测试中，由于测试过程的时间约束，测试用例集通常不能全部执行，测试用例的执行时间越短，优先级越高；测试用例发现的缺陷的严重性反映了该测试用例检测出缺陷的重要程度，软件对不同程度的软件缺陷的可接受程度不同，为了在测试过程中及早的发现严重的软件缺陷，测试用例发现的缺陷的严重性越高，优先级越高。

测试用例可以发现的缺陷数量和测试用例的执行时间两个因素可以进行综合，形成测试用例的缺陷检出效率，缺陷检出效率是测试用例单位执行时间内发现的缺陷数量，反映了测试用例检测缺陷的快速性，测试用例Ti的缺陷检出效率具体计算方法如下：

(2)计算测试用例检出缺陷的严重性

为了方便分析缺陷的严重性对测试用例优先级的影响，本发明中将缺陷的严重性进行定量化处理，不同等级的缺陷赋予不同的数值(其中，缺陷等级划划分标准可以选用《QUALITY STANDARDS DEFECT MEASUREMENTMANUAL,United Kingdom Software Metrics Association October 2000》中方法)，如下表所示：

表1 缺陷严重性的定量化

缺陷严重性等级严重性数值待观察缺陷(Level_1)2轻微缺陷(Level_2)4一般缺陷(Level_3)6重要缺陷(Level_4)8严重缺陷(Level_5)10

则测试用例Ti检出的缺陷可能包含不同严重等级的缺陷，总的缺陷严重性数值为：

$>{\mathrm{Sf}}_i={\Sigma }_{l=1}^{r}S\left(l\right)$>

其中，S(l)表示缺陷l的严重性数值，r是测试用例Ti可以检出的缺陷数量。在检出缺陷严重性方面，测试用例Ti在所有测试用例中的重要程度可以计算为：

$>{\mathrm{IS}}_i=\frac{{\mathrm{Sf}}_i}{\max \left(\mathrm{Sf}\right)}$>

其中，max(Sf)为所有测试用例中总的缺陷严重性数值的最大值。

步骤二：蚁群优化算法分析测试用例的优先级

(1)测试用例优先级分析的蚁群算法建模

本发明方法利用蚁群算法解决测试用例优先级问题，首先需要构建该问题的蚁群模型。蚁群模型中每个蚂蚁通过搜索规则构建一条路径，这条路径上的一个节点表示一个测试用例，因此，蚂蚁的一条完整路径对应测试用例的一条序列，n个蚂蚁就构建出测试用例的n条序列，这n条序列中存在一条最优的序列，对最优序列(最优路径)的权重进行加强，重复上述操作，经过多次迭代后，即可找到全局最优的测试用例序列。

如图2所示为本发明方法中蚁群算法模型示意图。在回归测试中，假设初始的测试用例集T中包含n个测试用例，T中测试用例的初始序列为{T1，T2，...，Ti，...，Tn}，这些测试用例总共可以检测出m个软件缺陷，在蚁群模型中，蚂蚁的个数为n个。Ti表示测试用例集T中的第i个测试用例，Lj表示蚂蚁选择了(j-1)测试用例后待选择的测试用例列表(由剩余的(n-j+1)个测试用例节点组成)。在初始时刻，n个蚂蚁被随机放置在测试用例列表L1中，然后每个蚂蚁在下一个待选择的测试用例列表L2中随机选择下一个测试用例节点，以此类推，直至每个蚂蚁选择的测试用例覆盖了m个软件缺陷。当一次迭代完成后，一个蚂蚁构建了一个测试用例序列，然后根据信息素更新规则和测试用例节点选择规则重复上述过程，其中，T中测试用例的初始序列为n蚂蚁随机选择n次得到，测试用例序列中的第一个测试用例为随机选择。

蚂蚁在构建测试用例序列过程中彼此相对独立，这是进行多核并行处理的基础。另外，蚂蚁每选择一个测试用例节点后，要对待选择的测试用例列表Lj进行更新操作，而且每个蚂蚁拥有独立的待选择测试用例列表。

(2)信息素更新规则

当一次迭代完成后，要对每条路径上的信息素按下述规则进行更新，

τ_id(t+1)＝(1-ρ)·τ_id(t)+Δτ_id

$>{\mathrm{\Delta \tau }}_{\mathrm{id}}={\Sigma }_{k=1}^n{\mathrm{\Delta \tau }}_{\mathrm{id}}^k$>

$>{\mathrm{\Delta \tau }}_{\mathrm{id}}^k=\left(\begin{array}{c}Q*h\left(k\right)\\ 0\end{array}\right)$>若蚂蚁k选择了测试用例节点Ti到测试用例节点Td间的路径其他情况

$>h\left(k\right)=\frac{{\Sigma }_{i=1}^{M_k}{\mathrm{Rf}}_i^k\left(t\right)}{M_k}$>

其中，τ_id(1)为0.5，ρ为信息素的消散速率，取值范围为[0，1]，可以取0.6，τ_id(t+1)是在(t+1)次迭代过程中从测试用例节点Ti到测试用例节点Td之间的路径上的信息素更新量，τ_id(t)为上一次迭代过程中Ti到Td之间的路径上的信息素，即(1-ρ)·τ_id(t)为残留的信息素，Δτ_id为Ti到Td之间的路径上总的信息素增量，为蚂蚁k在Ti到Td之间的路径上留下的信息素，Q为一个常量，表示一个蚂蚁拥有的信息素总量，可以取100，h(k)是蚂蚁k在t次迭代中关于缺陷检出效率的函数，M_k是在第t次迭代中当蚂蚁k检出所有缺陷时选择的测试用例节点数。由于缺陷检出效率是检出的缺陷数量与执行时间之比，因此，函数h(k)中考虑了影响测试用例优先级的前两个因素，函数h(k)的值越大，说明蚂蚁k构建的测试用例序列越好。

(3)测试用例节点选择规则

测试用例节点选择规则决定了选择下一个测试用例的概率，不失一般性，假设蚂蚁k在第j个待选择的测试用例列表Lj中选择了测试用例节点Ti，则在下一个，即第(j+1)个待选择的测试用例列表L(j+1)中选择测试用例节点Td的概率按下述规则给出：

η_id(t)＝IS_d(t)

其中，η_id(t)为启发函数，表明了从测试用例节点Ti到选择下一个测试用例节点Td的期望值，η_id(t)的值越大，说明在下一个待选择的测试用例列表L(j+1)中越期望选择测试用例Td，为蚂蚁k的第(j+1)个待选择的测试用例列表，测试用例节点选择规则由测试节点形成的路径上的信息素τ_id(t)和启发函数η_id(t)共同决定，α，β为调节参数，α＝1，β＝2，可以调节τ_id(t)和η_id(t)对的影响程度。η_id(t)的值由下一个测试用例Td发现的软件缺陷的严重性程度而决定，因此，η_id(t)考虑了影响测试用例优先级的第三个因素。

步骤三：蚁群优化算法的多核并行处理

步骤二建立的蚁群模型寻找最优测试用例序列过程中，每个蚂蚁独立构建自己的测试用例序列，只有在所有蚂蚁全部构建出自己的测试用例序列后，才共享构建的结果和更新信息素，即存在蚂蚁间的通信。因此可以将每个蚂蚁构建测试用例序列的过程分配到独立的线程，单独运行，然后将运行结果进行共享，通过利用计算机多核并行计算的优势来提高效率。每个蚂蚁构建测试用例序列的过程中，消耗时间最多的是循环迭代和循环赋值，本发明方法利用Intel线程构建模块TBB(Thread Building Block)进行并行化处理循环迭代和循环赋值，处理的部分包括：

(1)初始化的TBB模板设计

在问题初始化时，将n个蚂蚁随机放置在初始测试用例列表L1中，利用TBB中parallel_for并行模板编写初始化各个蚂蚁的模板类，该模板类中包含一个构造函数和operator接口，在构造函数中初始化蚂蚁数据结构，在operator接口中通过优化后的双重循环实现蚂蚁的初始化，外循环中初始化蚂蚁构建的测试用例序列为零，检测出的软件缺陷数为零，并使蚂蚁随机选择L1中的一个测试用例，内循环设置蚂蚁的下一个待选择的测试用例列表。

(2)每个蚂蚁构建测试用例序列过程的TBB模板设计

利用TBB中parallel_reduce并行模板编写每个蚂蚁构建测试用例序列过程的模板类，该模板类中包含两个构造函数、operator接口和join接口，一个构造函数利用对象参数初始化蚂蚁数据结构，另一个构造函数构建子任务，支持join接口中的合并操作，operator接口支持循环体内任务的并行处理、循环体内实现蚂蚁选择下一个测试用例节点、待选择的测试用例列表的更新以及已构建的测试用例序列和检出的软件缺陷数的更新，其中蚂蚁选择下一个测试用例节点的操作是根据测试用例节点选择规则来计算得到，join接口将多个线程中的每个蚂蚁构建测试用例序列的结果进行合并，便于每个蚂蚁求解结果的共享。

(3)更新测试用例节点路径上的信息素的TBB模板设计

利用TBB中的parallel_for并行模板编写更新测试用例节点路径上的信息素的模板类，该模板类中包含一个构造函数和operator接口，构造函数为一个空实现，operator接口计算任意两个测试用例节点路径上残留的信息素。测试用例节点路径上的信息素的计算需要遵循信息素更新规则，包括上一次迭代残留的信息素和信息素增量两部分，信息素增量部分的计算需要各个蚂蚁之间频繁地进行信息共享，并行处理并不高效，该部分串行处理，而残留的信息素的计算相对独立，适应于并行化，因此，operator接口只计算两个测试用例节点路径上残留的信息素。

步骤四：测试用例优先级分析结果的评价

(1)软件缺陷检出效率的度量分析。

为了评价本发明方法对测试用例优先级分析的效果，这里用检测软件缺陷效率来衡量。APFD(Average of the percentage of faults detected)作为度量标准。(参考文献：Rothermel G,Untch R H,Chu C,et al.Test case prioritization:An empirical study[C]//Software Maintenance,1999.(ICSM’99)Proceedings.IEEE International Conference on.IEEE,1999:179-188.)

如果T为包含n个测试用例的集合，m为测试用例集T检测出的软件缺陷数量，T的一个测试用例排序为T′，TF_i为检测到缺陷i的第一个测试用例在测试用例排序T′中的位置，则针对测试用例排序T′的APFD计算如下：

$>\mathrm{APED}=1-\frac{{\mathrm{TF}}_1+{\mathrm{TF}}_2+...+{\mathrm{TF}}_1+...+{\mathrm{TF}}_m}{\mathrm{nm}}+\frac{1}{2n}$>

APFD的取值范围为0％到100％，APFD的值越大，说明对应测试用例排序方法检测到软件缺陷的速率越快，即使用APED度量标准计算迭代得到的所有的n只蚂蚁的测试用例序列的APED值，并选择APED值最大的测试用例序列作为最优化的测试用例序列输出。

下面对本发明提出的技术方法进行了实验验证，回归测试的测试用例集中包含8个测试用例，这8个测试用例的初始排序为{T1,T2,T3,T4,T5,T6,T7,T8}，这些测试用例总共覆盖10个软件缺陷{F1,F2,F3,F4,F5,F6,F7,F8,F9,F10}，10个缺陷的严重性数值分别为{4,2,2,8,10,8,10,4,6,6}，每个测试用例可以发现的缺陷数量，执行时间和检出缺陷的严重性可以通过历史数据计算得到，表2中详细给出了这些参数，这些参数是多核并行蚁群算法的输入参数。我们比较了四种测试用例执行排序的检出缺陷的性能，这四种测试用例执行排序分别为：

初始排序{T1→T2→T3→T4→T5→T6→T7→T8}；

理论最优排序为{T3→T1→T5→T4→T6→T7→T8→T2}；

本发明ACO排序{T1→T3→T5→T7→T6→T2→T4→T8}；

随机排序{T7→T5→T4→T6→T1→T3→T8→T2}。

为了全面比较不同测试用例执行排序的检出缺陷的性能，如图3、图4、图5所示本发明从APFD、检出缺陷数的百分比、检出缺陷的严重性和执行时间这些方面进行了比较，如表3所示，从表中可以看出，ACO排序和理论最优排序的性能相当，APFD均为82.5％，只要执行前3个测试用例就可以把10个软件缺陷全部检出，执行时间为16个时间单位；初始排序的性能其次，APFD为76.25％，检出全部缺陷需要执行前5个测试用例，执行时间为24个时间单位；随机排序的性能最差，APFD为66.25％，检出全部缺陷需要执行前6个测试用例，执行时间为29个时间单位。可见，理论最优排序和ACO排序下的测试用例执行顺序最利于软件缺陷的检测，该理论最优排序在实际应用中难以获得，因此可以用本发明可以获得与理论最优排序性能相当的测试用例执行顺序。

表2 测试用例、检出缺陷和执行时间的关系

表3 不同测试用例执行排序的检出缺陷的性能

按照上述四个步骤，即可实现并行的基于蚁群算法的测试用例序列生成方法，该方法综合考虑了测试用例发现的缺陷数量、测试用例的执行时间和测试用例发现的缺陷严重性三个方面对测试用例执行的优先级进行分析，可以快速求解出最优的测试用例执行排序，使得回归测试在最短时间内检测出软件的缺陷，提高了回归测试过程的有效性和快速性，为软件的回归测试提供了一种高效的实用方法

本发明说明书中未作详细描述的内容属本领域技术人员的公知技术。