一种用于白盒测试的测试用例优先级排序方法

技术领域

本发明属于软件测试技术领域，尤其是软件测试中白盒测试技术领域，具体涉及一种用于白盒测试的测试用例优先级排序方法。

背景技术

测试用例优先级排序技术是指通过特定的排序准则，对针对某一待测程序的所有测试用例进行排序，目的是以更快的速度覆盖待测程序中的覆盖对象，例如语句，从而加快测试用例的缺陷检测速率。遗传算法是一种通过模拟自然界中生物的遗传进化过程，对最优化问题的最优解进行搜索的方法，它在解决函数优化、离散问题等一些复杂问题时，具有很好的应用价值，同时，遗传算法的使用不依赖问题的具体领域，因此对问题的种类有很强的鲁棒性。

测试用例优先级排序问题是目前软件测试领域中的一个研究热点，对于该问题的研究最早由Wrong等人于1997年开展，他们结合测试用例历史覆盖信息和代码修改信息,提出一种混合方法,该方法首先借助测试用例集缩减技术识别出冗余测试用例,对非冗余测试用例根据其覆盖能力进行排序。2007年，李征等人针对测试用例优先级问题将传统的遗传算法与贪心算法、爬山算法进行了对比验证，实验证实使用遗传算法做测试用例优先级在大多数情况下可以比其它算法取得更好的结果。2015年，张卫祥等人在提出了两种测试用例优先级评价指标的基础上使用遗传算法进行测试用例优先级排序，取得了较好的实验效果。2016年，卢亚峰等人通过对8个大型工业程序不同版本对应的测试用例集使用贪心算法、自适应随机算法和遗传算法进行排序，实验验证了自适应算法和遗传算法可以取得比其它算法更好的排序结果。然而，传统的遗传算法在寻优过程中存在收敛速度慢，稳定性不好的问题，为此，本发明以传统的遗传算法为基础，对其中的选择和交叉操作进行改进，提出了一种新的用于白盒测试的测试用例优先级排序方法，提高测试效率，有助于软件缺陷的尽早发现。

发明内容

在回归测试中，进行白盒测试时要从大量的可用测试用例中选取重要的、揭错能力强的测试用例优先对待测程序进行测试，以提高测试过程中发现缺陷的能力，这时需要对测试用例的执行次序进行重新规划，达到提高测试效率的目的。传统的遗传算法在寻找测试用例的最佳排序的过程中存在收敛速度慢、稳定性差的问题，因此亟需寻求一种用于测试用例优先级排序的新方法。

本发明的技术方案为：一种用于白盒测试的测试用例优先级排序方法，具体包括以下几个步骤：

步骤一：针对一个待测程序，使用已经设计好的测试用例集进行测试，将测试用例对待测程序的语句覆盖情况进行记录，得到测试用例对待测程序的语句覆盖信息矩阵A；假设某待测程序有m条语句，用n个测试用例进行测试，若测试用例集用Φ表示，Φ＝{T₁,T₂,…,T_i,…,T_n}，其中T_i(1≤i≤n)为测试用例集中的第i个测试用例，构造的语句覆盖信息矩阵A的大小为n×m，待测程序中语句编号的范围是1到m，测试用例编号的范围是1到n，若第i个测试用例执行中覆盖了第j个语句,则A_ij＝1，否则A_ij＝0；

步骤二：编码；测试用例优先级排序问题针对给定的待测程序和测试用例集，个体表示一个测试用例优先级排序序列，测试用例优先级排序序列就是由测试用例编号所组成的有序序列，即每一个个体被编码为一个有序测试用例编号串，编码的长度为测试用例的个数n；

步骤三：构造适应度函数；针对任一个体，TS_j为首个可以覆盖到待测程序中第j个语句S_j的测试用例在该测试用例执行序列中所处的次序，假设执行完测试后待测程序中被覆盖的语句的数量为M，那么M个语句对应M个这样的次序，所有次序之和为由此可以构造适应度函数APSC，APSC表示语句覆盖的平均百分比，

即其中TS_j(1≤j≤M)可以用语句覆盖信息矩阵A进行计算，针对被覆盖的语句S_j，在A中查找第一个覆盖到该语句的测试用例在该测试用例序列中所处的次序，那么这个次序就是TS_j的数值；

步骤四：随机初始化种群；设定种群规模为N，即种群中包含N个个体，若用D表示种群，则

D＝{<r₁₁,r₁₂,…,r_1n>,<r₂₁,r₂₂,…,r_2n>,…,<r_i1,r_i2,…,r_in>,…,<r_N1,r_N2,…,r_Nn>}，其中<r_i1,r_i2,…,r_in>代表种群中的第i个个体；设置交叉概率P_c和变异概率P_m以及最大迭代次数MAX；令迭代次数g＝1,开始迭代；

步骤五：执行随机抽样选择策略；

(1)计算种群中所有个体的适应值，得到一个由N个适应值组成的数组，表示为{Fitness₁,Fitness₂,…,Fitness_N}，其中Fitness_individual(1≤individual≤N)表示种群中第individual个个体的适应值，若种群适应值的平均值用averageFitness表示，则随机生成一个实数start(0＜start＜averageFitness)；令index＝1，index表示个体编号，令种群适应值之和sum初值为Fitness₁；

(2)令select为当前已经选择的个体的数量；计算pointer＝start+select×averageFitness，pointer为衡量种群中个体适应值大小的依据，若Fitness_index＜pointer,那么进行如下操作:a.index＝index+1,sum＝sum+Fitness_index；b.重复执行a中的操作，当sum≥pointer时，将index的值保存在individuals数组中的第select+1个位置，并停止b中操作；

(3)select＝select+1,重复执行(2)中的操作，当select＝N时，停止选择操作；

(4)将individuals数组中的数字作为下标，用这些下标对应的每一个个体顺次替换当前种群中的每一个个体，得到与原种群大小相同的新一代种群；

步骤六：执行交叉操作；针对种群中任意两个个体A₁和A₂，设假设交叉操作后产生的子代个体为A₁＇和A₂＇；随机生成一个0到1的实数，当P_c大于这个实数时，执行交叉操作，交叉操作后产生的子代个体取代父代个体进入新种群，没有进行交叉的个体被直接复制进新种群；交叉操作的具体过程如下：

(1)计算A₁和A₂中相同位置上数值不同的位置数量，假设为t,则A₁和A₂中相同位置上数值相同的位置数量为n-t；

(2)产生N个序列，每个序列为一个长度为t的排列，N个序列中第k个序列可以表示为其中

k＝1,2,…,N，1≤u≤t，<r_u×k>表示取r_u×k的小数部分，如果小数部分为负数，那么将负数加1，使该负数变成一个正数，其中r_u＝2cos(2πu/q)，q是满足q≥2t+3的最小素数；

(3)删除A₁和A₂中的n-t个相同位置上的相同数值，将余下的t个相同位置上的不同数值按照由小到大的顺序进行排序，记排序后由t个数值组成的序列为s，s＝<s₁,s₂,…,s_t>，其中s₁≤s₂≤…≤s_t；将按照由小到大的顺序排列为记该序列为P_k＇；记录经过排序后在P_k＇中所处的位置，根据位置的变化情况对s_i在s中所处的位置进行重新调整，得到由s₁,s₂,…,s_t组成的一个新的序列，记为s＇，再使用s＇中的每一个数值分别填充A₁和A₂中相同位置上具有不同数值的t个位置，就得到了一个新的序列，记为S_k，该序列长度为n；当k取1,2，…，N-1，N中的每一个数值时，都执行(3)中上述操作，就可以生成N个长度为n的序列，记为S＝{S₁,S₂,…,S_N}；

(4)计算(3)中生成的N个序列的适应值，A₁＇和A₂＇中各个位置上的数值与适应值最大序列中各个位置上的数值对应相同；

步骤七：执行变异操作；

对于种群中任意一个个体，假设为B，随机生成一个0到1的实数，当P_m大于这个实数时，对B执行变异操作，变异操作的过程为：从B上随机选择两个位置，将这两个位置上的数值进行交换，从而得到一个新的个体B＇；

步骤八：记录本次迭代后的最大适应值及其对应的个体；

步骤九：判断迭代终止条件，本方法中的迭代终止条件是当前迭代次数大于最大迭代次数MAX，如果终止条件成立，那么此时最大适应值个体对应的测试用例优先级排序序列为最优测试用例优先级排序序列，输出该序列并停止迭代；否则，令迭代次数g＝g+1，返回步骤五，继续迭代。

本发明有益效果

发明中用于测试用例优先级排序的选择操作采用了随机抽样的方式选择出满足种群大小的若干个体，这种选择个体的方式增大了选取种群中有较高适应值个体的概率，保证了在选择过程中能够选中种群中较优的个体，增加了算法在寻优过程中的收敛速度；交叉操作考虑了进行交叉的两个个体在哪些位置上有相同数值以及哪些位置上有不同数值，减小了交叉操作的盲目性，增加了算法在寻优过程中的收敛速度和稳定性；实验结果显示(由图2和图3所示)，本方法生成最优测试用例优先级排序结果的收敛速度快、稳定性好，能提高测试效率，节约测试成本，及早发现软件缺陷。

附图说明

附图1为一种用于白盒测试的测试用例优先级排序方法的流程图。

附图2为测试用例优先级排序不同方法的平均适应值变化对比图。

附图3为测试用例优先级排序不同方法的最大适应值箱体图。

具体实施方式

以JavaScript单元测试框架Jasmine的源程序的测试用例优先级排序为例，结合附图1对本发明提出的一种用于白盒测试的测试用例优先级排序方法的具体实施方式进行说明。

步骤一：针对一个待测程序，使用已经设计好的测试用例集进行测试，将测试用例对待测程序的语句覆盖情况进行记录，得到测试用例对待测程序的语句覆盖信息矩阵A；Jasmine的源程序有292条语句，用24个测试用例进行测试，若测试用例集用Φ表示，Φ＝{T₁,T₂,…,T_i,…,T_n}，其中T_i(1≤i≤n)为测试用例集中的第i个测试用例，构造的语句覆盖信息矩阵A的大小为24×292，待测程序中语句编号的范围是1到292，测试用例编号的范围是1到24，若第i个测试用例执行中覆盖了第j个语句,则A_ij＝1，否则A_ij＝0；

步骤二：编码；测试用例排序问题针对给定的待测程序和测试用例集，个体表示一个测试用例优先级排序序列，测试用例优先级排序序列就是测试用例编号所组成的有序序列，即每一个个体被编码为一个有序测试用例编号串，编码的长度为测试用例的个数24；

步骤三：构造适应度函数；针对任一个体，TS_j为首个可以覆盖到待测程序中第j个语句S_j的测试用例在该测试用例执行序列中所处的次序，执行完测试后Jasmine的源程序中被覆盖的语句的数量为292，那么292个语句对应292个这样的次序，所有次序之和为由此可以构造适应度函数APSC，APSC表示语句覆盖的平均百分比，

即其中TS_j(1≤j≤292)可以使用语句覆盖信息矩阵A进行计算，针对被覆盖的语句S_j，在A中查找第一个覆盖到该语句的测试用例在该测试用例序列中所处的次序，那么这个次序就是TS_j的数值；

步骤四：随机初始化种群；设定种群规模为150，即种群中包含150个个体，若用D表示种群，则

D＝{<r₁₁,r₁₂,…,r₁₂₄>,<r₂₁,r₂₂,…,r₂₂₄>,…,<r₁₅₀₁,r₁₅₀₂,…,r₁₅₀₂₄>}，其中<r₁₁,r₁₂,…,r₁₂₄>代表种群中的第1个个体，<r₂₁,r₂₂,…,r₂₂₄>代表种群中的第2个个体，…，<r₁₅₀₁,r₁₅₀₂,…,r₁₅₀₂₄>代表种群中的第150个个体；设置交叉概率P_c＝0.85，变异概率P_m＝0.55，最大迭代次数MAX＝50；令迭代次数g＝1,开始迭代；

步骤五：执行随机抽样选择策略；

(1)计算种群中所有个体的适应值，得到一个由150个适应值组成的数组，表示为{Fitness₁,Fitness₂,…,Fitness₁₅₀}，其中Fitness_individual(1≤individual≤150)表示种群中第individual个个体的适应值，初始种群中所有个体的适应值为

(0.677226,0.68764263,0.68707186,0.6705194,0.6021689,…,

0.75742006,0.7020548,0.70719177,0.7126141,0.63313353,0.7255993)

若种群适应值的平均值用averageFitness表示，则

即

averageFitness＝103.31777662038803/150＝0.6887851774692535；随机生成一个实数start(0＜start＜averageFitness)，其数值为0.36970036874340495；令index＝1，index表示个体编号，令种群适应值之和sum初值为Fitness₁，sum＝Fitness₁＝0.677226；

(2)令select为当前已经选择的个体的数量；计算

pointer＝start+select×averageFitness，即

pointer＝0.36970036874340495+0×0.6887851774692535，pointer为评价种群中个体适应值大小的衡量依据，计算结果为0.36970036874340495，由于sum>pointer，所以将此时index的数值1保存在数组individuals中的第1个位置，表示选择了种群中编号为1的个体；

(3)select＝select+1,此时

pointer＝0.36970036874340495+1×0.6887851774692535，计算结果为1.058485546212658，由于此时sum保存的是select＝0时sum最终的数值0.677226，对sum和pointer进行比较，

0.677226<1.058485546212658，所以index＝index+1＝2，

sum＝sum+Fitness₂＝0.677226+0.68764263＝1.36486863；再次比较sum和pointer,由于1.36486863＞1.058485546212658，所以将此时index的数值2保存在数组individuals中的第2个位置；重复执行(3)中的上述操作，当select＝N时，停止选择操作；例如：某次迭代过程中选择操作完成后individuals数组中的值为：

(1,2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,18,19,20,21,22,22,23,24,26,27,28,28,

31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,52,53,54,55,55,56,57,58,59,60,

61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,

90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,

114,115,116,117,119,120,121,122,122,123,124,125,126,127,128,129,130,131,132,133,134,135,

136,137,138,139,140,141,142,143,144,145,146,147,148,149，150)，

从以上数据中可以看出，编号为8、25、29、30的个体在选择过程中没有被选中，表明这些个体适应值小，因而被选中的概率较小；编号为22、28、55、122的个体在选择过程中均被选中了多次，表明这些个体适应值大，因而被选中的概率大；

(4)将individuals数组中的数字作为下标，用这些下标对应的每一个个体顺次替换当前种群中的每一个个体，得到与原种群大小相同的新一代种群；

步骤六：针对种群中任意两个个体A₁和A₂，设假设交叉操作后产生的子代个体为A₁＇和A₂＇；随机生成一个0到1的实数，这里生成的随机数为0.53896，由于P_c大于这个实数，因此执行交叉操作，交叉操作后产生的子代个体取代父代个体进入新种群，没有进行交叉的个体被直接复制进新种群；交叉操作的具体过程如下：

(1)本例中选择出的两个父代个体为：

A₁＝(17,1,5,15,3,14,20,22,10,23,4,16,2,6,13,18,11,7,9,12,19,21,8,24)；

A₂＝(19,12,7,20,13,9,2,11,1,22,8,6,3,4,23,18,15,10,17,21,14,16,5,24)；

则A₁和A₂中相同位置上数值不同的位置数量t＝22，A₁和A₂中相同位置上数值相同的位置数量n-t＝2；

(2)产生150个序列，每个序列对应一个长度为22的排列，N个序列中第k个序列可以表示为其中

k＝1,2,…,150，1≤u≤22；<r_u×k>表示取r_u×k的小数部分，如果小数部分为负数，那么将负数加1，使该负数变成一个正数，其中r_u＝2cos(2πu/q)，q是满足q≥2t+3的最小素数，这里q≥2t+3＝47，因而q取47，例如，当u＝3，k＝1时，r₃×1＝1.9289383501087531，那么<r₃×1>＝0.9289383501087531；当u＝4,k＝1时，

r₄×1＝-6.482505539488857，<r₄×1>＝-0.482505539488857，那么要将<r₄×1>的数值转变成<r₄×1>＝-0.482505539488857+1，即0.5174944605111431；当k＝2时，通过计算得到的P₂为

(0.9643,0.8579,0.6826,0.4416,0.1392,0.7808,0.3727,0.9223,0.4376,0.9273,0.4004，

0.8663,0.3347,0.8149,0.3163,0.8477,0.4175,0.0334,0.7022,0.4299,0.2213,0.0802)；

(3)删除A₁和A₂中的2个相同位置上的相同数值，这里删除的数值为A₁和A₂中第16个位置上的数值18和第24个位置上的数值24；将余下的22个相同位置上的不同数值按照由小到大的顺序进行排序，记排序后由22个数值组成的序列用s表示,s＝<s₁,s₂,…,s₂₂>，其中s₁≤s₂≤…≤s₂₂，这里s＝<1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,20,21,22,23>；将按照由小到大的顺序排列为记该序列为P_k＇，这里将P₂中的所有数值按照由小到大的顺序进行排序，得到

(0.0334,0.0802,0.1392,0.2213,0.3163,0.3347,0.3727,0.4004,0.4175,0.4299,0.4376,

0.4416,0.6826,0.7022,0.7808,0.8149,0.8477,0.8579,0.8663,0.9223,0.9273,0.9643)；

记录经过排序后在P_k＇中所处的位置，根据位置的变化情况对s_i在s中所处的位置进行重新调整，得到由s₁,s₂,…,s₂₂组成的一个新的序列，记为s＇，例如P₂中第1个位置的数值0.9643经过排序其位置变为了22，那么将s中第1个位置上的数值1存放在长度为22的新序列的第22个位置，P₂中第2个位置的数值0.8579经过排序其位置变为了18，那么将s中第2个位置上的数值2存放在长度为22的新序列的第18个位置，…,P₂中第22个位置的数值0.0802经过排序其位置变为了2，那么将s中第22个位置上的数值23存放在长度为22的新序列的第2个位置，经过该方式对P₂中22个数值在序列中所处的位置进行重新调整后得到(19,23,5,22,15,13,7,11,17,21,9,4,3,20,6,14,16,2,12,8,10,1)，即这是得到由s₁,s₂,…,s_t组成的一个新的序列，再使用该序列中的每一个数值顺次填充A₁和A₂中相同位置上具有不同数值的22个位置，就得到了一个新的序列，记为S₂，该序列长度为24，

S₂＝(19,23,5,22,15,13,7,11,17,21,9,4,3,20,6,18,14,16,2,12,8,10,1,24)；当k取1,2，…，149,150中的每一个数值时，都执行(3)中上述操作，就可以生成150个长度为24的序列，记为

S＝{S₁,S₂,…,S₁₅₀}；

(4)计算(3)中生成的150个序列的适应值，A₁＇和A₂＇中各个位置上的数值与适应值最大序列中各个位置上的数值对应相同；这里计算得到的150个序列中的最大适应值为0.74999994，对应的序列为(9,12,4,19,8,15,5,6,24,10,13,17,21,1,11,18,7,22,16,3,2,14,20,23)，因而A₁＇和A₂＇均为

(9,12,4,19,8,15,5,6,24,10,13,17,21,1,11,18,7,22,16,3,2,14,20,23)；

步骤七：执行变异操作；

对于种群中任意一个个体，假设为B，随机生成一个0到1的实数，当P_m大于这个实数时，对B执行变异操作，变异操作的过程为：从B上随机选择两个位置，将这两个位置上的数值进行交换，从而得到一个新的个体B＇；例如，对于种群中的某个体B，

B＝(4,16,19,24,1,8,20,17,13,5,12,14,18,7,11,10,9,3,22,2,15,6,21,23)，随机生成的一个0到1的实数为0.5114276945945321，满足0.55＞0.5114276945945321，执行变异操作：从B上随机选择的两个位置为7和11，将这两个位置上的数值进行交换得到一个新的个体B＇，

B＇＝(4,16,19,24,1,8,12,17,13,5,20,14,18,7,11,10,9,3,22,2,15,6,21,23)；

步骤八：记录本次迭代后的最大适应值及其对应的个体，本次迭代后的最大适应值为0.78224885，该适应值对应的个体为

(4,19,8,5,15,9,24,12,13,17,3,7,6,16,11,14,10,22,2,20,18,21,1,23)；

步骤九：判断迭代终止条件，本方法中的迭代终止条件是当前迭代次数大于最大迭代次数MAX,MAX＝50，如果终止条件成立，那么此时得到的测试用例优先级排序序列为最优测试用例优先级排序序列，输出该序列并停止迭代；否则，令迭代次数g＝g+1，返回步骤五，继续迭代。例如，第50次迭代后，种群中最大适应值为0.79723173，输出的最优测试用例优先级排序序列为

(13,20,9,15,8,4,1,16,6,10,3,5,24,7,19,2,12,11,22,21,18,17,14,23)。

通过以上过程可以实现用于白盒测试的测试用例优先级排序，针对jasmine程序的语句覆盖信息，分别将传统遗传算法和本发明中的方法各执行20次。

图2是20次实验中，50次迭代的适应值平均值随迭代次数变化图。从图2可以看出，迭代过程中，本方法的适应值要大于传统遗传算法对应的适应值，所以针对白盒测试中的测试用例优先级排序，本方法相比传统遗传算法具有更快的收敛速度。

图3是传统遗传算法和本方法20次实验中最大适应值的箱体图，对比两副箱体图可知，本方法得到的数据分布更集中，即在使用本方法进行针对白盒测试的测试用例优先级排序时生成最优排序结果的稳定性更好。

实例分析表明，本发明提出的用于白盒测试的测试用例优先级排序方法与传统遗传算法做测试用例优先级排序相比，本发明提供的用于白盒测试的测试用例优先级排序方法收敛速度快，生成最优测试用例优先级排序序列的稳定性好，是一种有效的用于白盒测试的测试用例优先级排序方法。