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

钱忠胜 等:面向关键字流图的相似程序间测试用例的重用 2703

率进行交叉与变异等操作,生成新的种群;判断新种群中是否有个体满足目标路径被覆盖,若其被覆盖,记录种
群的进化代数;判断是否满足算法的终止条件,即种群是否达到最大进化代数,若满足则终止算法,若不满足则
循环种群进化的过程.
算法 3 将测试用例重用到待测程序的测试数据生成中,并作为对比实验检验测试用例的重用效果.该算法
的初始种群采用算法 2 中的初始种群,以避免初始种群不同对实验结果造成的影响.在种群交叉进化的遗传操
作过程中,算法 3 引入相似程序的测试用例作为个体交叉的对象,其他步骤与算法 2 一致.
算法 3(本文方法).
输入:种群大小 pop_size,个体 individual,染色体长度 chro_size,进化代数 gen_size,交叉概率 pc,变异概率 pm,
引入的新个体 shared_pop;
输出: 新种群.
begin
1 initialize(pop_size,chro_size); //初始化种群
2 for i←:gen_size;
3 individualSign_list←quicksort(pop_size,individual);
4 fitness_list←finess(pop_size,individual,individualSign_list);
//第 3 步和第 4 步这两步种群个体测试冒泡排序,生成能表示节点距离的序列,计算个体适应度
5 individual_list←select¬(pop_size,individual,fitness_list,elitism);
//轮盘赌法选择个体
6 pop2_list←crossover2(pop_size,chro_size,individual_list,shared_pop,pc);
//与引入的个体交叉产生新的个体
7 mutate2(pop_size,chro_size,pop2_list,pm) //变异过程
end for
end
3.3 测试用例生成实验

选取第 3 节讨论的两个相似程序(即冒泡排序和快速排序)为实验对象,提出两个问题探究本文判断程序相
似性方法的合理性以及相似程序间测试用例重用的有效性,收集实验结果加以分析.具体问题如下:
问题 1. 本文设计的关键字流图比较程序相似性,相对于其他方法比较程序相似性有什么优点?如何检验
方法的有效性?
最长公共子串等方法只比较代码的相同程度,而忽略了源代码略有差别、但功能结构却相同的情况.提出
利用关键字流图比较程序的相似性,将比较全部源代码简化为比较代表代码语句功能结构的关键字.
最大公共子图距离能够判断待测程序的相似程度.而通过遗传算法将程序已有的测试用例应用到相似程
序的种群进化的遗传操作中,检验测试用例的生成效率来判断程序相似性判断的有效性.即:通过用例的共享,
待测程序的测试效率明显提高,可证明两个程序相似性判断是正确的.
问题 2. 相似程序之间用例的共享能够减少多少测试工作量,提高多少测试效率?
检测关键字流图判别程序有效性的实验,也能完成用例的重用.我们结合姜淑娟等人 [20] 的思想,在初始化种
群的环节中引入相似程序中已有的测试数据,种群其他的个体通过向这些测试用例的学习加速种群进化,主要
通过 4 个评判标准来检验测试效率.评判标准见第 3.3.2 节.
我们采用对比实验来解答上面两个问题.实验的不同点主要在于种群进化的方式不同.
• 传统方法测试程序,初始种群随机生成,在初始种群中用轮盘赌法选择两个体进行遗传操作,轮盘赌法
选中的两个个体以一定概率进行变异:若满足交叉条件,则两个个体进行交叉,进化成两个新个体.循环
此操作,直到产生的新种群个体数与初始种群相同;
• 而利用本文方法测试程序,初始种群使用传统方法生成的种群,以排除初始种群不同对实验结果造成