Page 80 - 《软件学报》2021年第9期

2704 Journal of Software 软件学报 Vol.32, No.9, September 2021

的影响.引入相似程序已经生成的测试用例集,在种群进化的交叉部分,仍用轮盘赌法选择的个体与该
用例集中的个体交叉,生成两个新的个体.其他操作与传统方法相同.
3.3.1 实验对象
第 2 节表明:冒泡排序和快速排序两个程序的相似度为 80%,判定为相似程序.实验对象仍选取此相似程序
来探究相似程序间测试用例的重用问题.
实验假设快速排序的适应度较高的测试用例已知.研究测试用例的重用就是将已知的测试用例共享于与
其相似的程序,故测试冒泡排序程序时,将引入快速排序已有的测试用例.测试用例有 32 个二进制的字符,其中,
4 个二进制字符代表一个十进制的阿拉伯数字,意味着每个测试用例代表着长度为 8 的整数数组,整数大小在 0
到 15 之间.测试用例的生成采用遗传算法,种群的个数为 40.具体参数设置见表 5.

Table 5 Parameters setting in genetic algorithms
表 5 遗传算法中的参数设置
遗传操作 取值
选择策略 轮盘赌法选择
交叉策略 多点交叉
交叉概率 0.9
变异策略 单点变异
变异概率 0.1
最大进化代数 1 000
种群大小 40

3.3.2 评价标准
为了检验程序相似性检测方法的有效性及相似程序间测试用例重用的效果,并便于与丁蕊等人 [28] 提出的
关键点路径法进行比较,同时也为了将遗传算法中随机因素对实验结果造成的影响降低到最小,我们将实验结
果的 4 个评价标准(即覆盖率、平均进化代数、执行时间和方差分析)的定义如下.
1) 覆盖率:对程序运行 100 次,记录在最大进化代数 T=1000 内目标路径被覆盖的总次数,覆盖率为这 100
次中被覆盖次数的平均值,以百分比的形式表示;
2) 平均进化代数:目标路径被覆盖的每个程序运行 100 次,若该程序在最大进化代数 T=1000 内覆盖到了
目标路径,记录此时程序的进化代数;若在最大进化代数内目标路径没有被覆盖,记录最大进化代数,
平均进化代数即为这些记录值的平均值;
3) 执行时间:该评价指标记录两种方法(即传统方法与本文方法)的时间开销.传统方法生成测试用例的
执行时间是测试数据或路径的选择与测试数据生成所消耗的时间总和;本文方法生成测试用例的时
间除了测试数据或路径的选择与测试数据生成的时间以外,还包括判定程序相似性和测试用例重用
花费的时间;
4) F 值:在方差分析中,每个被测程序运行 100 次,记录目标个体首次出现的进化代数,将传统方法与本文
方法下获得的该数据作为两组样本来计算 F 统计量,即组间均方与组内均方的比值(见定义 6 和定义
7),该值能验证随机因素对实验结果造成的影响程度.
传统方法和本文方法均采用遗传算法测试同一程序,上面 4 种评价标准作为衡量两种方法测试效率优劣
的指标,检验本文方法是否能够有效地提高测试用例的生成效率,完成测试用例的重用.
3.3.3 实验结果分析
测试冒泡排序来验证相似程序间测试用例重用的有效性,传统方法中的测试种群通过轮盘赌法选择个体
进行交叉变异产生下一代,而作为对比实验的本文方法在种群进化中将引入相似程序快速排序适应度较高的
测试用例.为了减少随机因素的影响,两种实验均独立运行 100 次,本文方法采用的初始种群为冒泡排序随机生
成的初始种群.种群进化达到最大进化代数时算法终止,并记录 100 次实验共有的总时间.
表 6 表明:将快速排序适应度较高的测试用例运用到冒泡排序的测试中,测试用例的生成效率明显提高.其