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

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

是待测程序适应度比较高的测试用例,甚至某些测试用例作为目标个体参与了种群的进化,因此在种
群迭代 1 000 次的情况下,种群进化出目标个体(覆盖率 100%)是大概率事件;
2) 容易陷入局部最优是遗传算法的弊端之一,实验发现:当种群进化到一定代数之后,种群基因种类较
少,许多个体的基因相同或者非常相近,很大程度上阻碍了目标个体的生成;而外部个体的引入能够
丰富种群基因,加速目标个体的进化.
3.5 问题回答
通过分析第 3.3.3 节和第 3.4 节的实验结果,对第 3.3 节开头中提出的两个问题做如下回答.
回答问题 1. 本文设计的关键字流图比较程序相似性,相对于其他方法比较程序相似性有什么优点?如何
来检验方法的有效性?
第 2.5 节已经讨论过关键字流图比较程序相似性的优势,程序的相似程度可以通过最大公共子图距离进行
判定.通过相似程序间测试用例的共享,实现数据用例的重用.可根据测试用例的重用效果证实关键字流图比较
程序相似性方法的有效性.由表 6 传统方法与本文方法测试程序的评判结果,传统方法的覆盖率为 15%,平均进
化代数为 890.9 代;而作为引入相似程序测试用例的本文方法的目标路径覆盖率为 100%,平均进化代数为 3.5.
表 11 增加了两组基准程序和 5 组工业程序,本文方法测试程序的目标路径覆盖率皆为 100%(注意:PG17 除外,
因其为不相似程序的测试),前 3 项评判标准皆优于传统测试方法,第 4 项评价指标能够排除实验的随机影响因
素,从而证明了本文方法的有效性.由此可知:将相似程序(如,快速排序和冒泡排序)的测试用例相互引入到对方
的测试中,测试效率显著提高.由此证实了本文程序相似性判定方法的有效性.
回答问题 2. 相似程序间用例的共享能够减少多少测试的工作量,提高多少测试效率?
从表 7 和表 8 可看出:在不同的种群规模和不同的变异概率下,本文方法目标路径的覆盖率都是 100%,4 项
评价指标充分证明了本文方法优于传统方法.结合表 6 和表 13,在所有程序的测试中,本文方法下的目标路径覆
盖率均为 100%(注意:PG17 除外,因其为不相似程序的测试),平均进化代数最高(即最差情况)也仅为 36.13;而传
统方法目标路径覆盖率最大才达到 91%,平均进化代数除 PG3 以外均超过 130.可见,本文方法的测试效率显著
高于传统方法.因为本文方法在进化遗传操作中引入了相似程序适应度较高的测试用例,种群在进化时随机地
与这些个体进行交叉,其收敛速度明显高于传统方法.
3.6 有效性分析、存在的问题及其初步解决方案
影响实验效果的因素包括内部因素和外部因素.
1) 内部因素主要是遗传算法本身对实验结果造成的影响.种群初始化采用随机生成的方法,轮盘赌法选
择个体进行遗传操作也具有一定的随机性,为了降低算法随机性带来的影响,进行 100 次独立的实验,
实验结果取 100 次重复实验的平均值;
2) 外部因素包括程序本身对实验结果的影响.与实验选取的对象有关,本文方法测试不同组的程序,测
试用例的重用效果略有差别.另外,实验发现:本文方法的实验结果受引入的测试用例的个数和适应
度的影响,一定范围内引入的测试用例个数越多和采用较好适应度的测试用例往往能取到相对较好
的结果,实验中引入的测试用例为传统方法生成的测试用例.
针对用例重用的问题,本文探究了相似程序间测试用例的重用,实验取得了较好的结果,证明了方法的有效
性.然而,本文仍存在以下不足.
1) 本文方法在判定规模较小程序的相似性时会具有一定的偶然性,其准确性有待进一步提高;
2) 存在有些相似程序的用例长度不同的情况,测试数据无法共享,该条件有一定的局限性.
若判定为相似程序的测试用例长度不同,那么在遗传算法生成测试用例的过程中,种群个体不能与相似程
序的测试用例进行交叉进化.若将引入个体的长度与进化种群个体的大小改成一致,则能够完成用例长度不同
的程序间测试用例的重用.
本文就存在的不足设想如下初步解决方案.