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

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

问题,却增加了算法的复杂度,计算效率不高.Rong 等人 [15] 为了解决程序需要从两个给定集合中找到所有类似
的字符串对的问题,提出一种在单个操作符中支持不同相似阈值的字符串相似性连接的方法,就判定程序相似
性阈值的设定,设计了新的索引技术,针对不同的程序设计了不同判定程序相似的阈值,使得判定程序相似性更
加准确,但复杂度较高.
Mc.Cabe [16] 提出了圈复杂度的结构度量技术,该技术在流图基础上计算它的圈度,很多时候需要与其他特
征结合进行程序结构的度量.陈浩与王广南等人 [10] 提出了基于程序依赖图的动态胎记技术来检测程序的相似
性,该方法首先对流图的公共子图进行胎记标记,通过比较最大公共子图距离来判断程序相似性.这兼顾了局部
特征和整体特征,但公共子图同构判定的局限性比较大.
分析程序相似性的目的是为了探究相似程序间测试用例重用的有效性,而测试用例的生成是用例重用的
前提,只有保存足够的已生成的测试用例,才能完成它们的重用.近年来,国内外开展了许多关于重用测试用例
和测试用例的生成等方面的研究工作.
Mayrhauser 等人 [17] 通过领域建模来构造可重用的测试用例,其构造包括脚本化、命令模版和参数值选择这
3 个部分,并开发出基于领域建模的测试用例生成工具 Sleuth.Vouffo-Feudjio 等人 [18] 提出了基于 TTCN 的测试
模式,并探讨了该模式的重用规则,包括怎样在不同产品之间的水平重用和不同版本之间的纵向重用.
巩敦卫等人 [19] 就提高回归测试中测试数据的生成效率,提出一种新的回归测试数据进化生成方法.该方法
利用已有的测试数据穿越路径与目标路径的相似程度,选择相似程度较高的测试数据作为初始化种群的部分
个体.进一步,根据已有测试数据穿越路径与目标路径的对比,确定个体实施遗传操作的位置.姜淑娟等人 [20] 提
出了基于模式组合的粒子群优化测试用例生成方法,通过新设定的交叉算子,将个体中的含有模式的部分组合
成新个体,利用遗传算法生成测试用例的过程中,种群中其他个体均可向该适应度较高的新个体进行学习,加快
种群进化速度,提高测试用例生成效率.
将程序的相似性应用在计算机教学和恶性程序检测等领域的研究比较多:最长公共子串算法 [14] 比较字符
串的相似性,字符串的相似性完全取决于最长字符串的长度,具有片面性;Levenshtein 距离算法 [13] 比较适用于规
模较小的程序相似性的比较;基于程序依赖图的动态胎记技术 [10] 来检测程序的相似性,需要公共子图的同构作
为前提条件,局限性比较大.
在前人研究的基础上,本文提出面向关键字流图程序相似度的方法.该方法兼顾了源代码序列和程序功能
结构相似度的比较两个方面.另外,借鉴巩敦卫和姜淑娟等人 [19,20] 的思想,提出了相似程序间测试数据的重用方
法,通过相似程序间测试用例的共享实现用例重用.即:待测程序利用遗传算法生成测试用例,在种群进化阶段
引入相似程序中已经生成的测试数据;在迭代过程,以一定概率向这些个体学习.与传统遗传算法种群个体之间
相互学习的进化方式作对比,测试用例生成效率较高,证明了测试用例重用的有效性,而相似程序间测试用例重
用的效果证明了判断相似程序方法的可行性.

2 程序相似性的判定

本文对程序相似性的判定结果应用到相似程序间的测试用例重用中,故程序相似度的判定不仅注重语义
上的相似性,更加注重程序功能结构上的异同.本节提出关键字流图的构建方法,通过构建的关键字流图查找待
测程序的关键字流图最大公共子图.最后,通过最大公共子图距离算法求得程序的相似度,程序相似性的比较如
图 1 所示.本节给出判定程序相似性的步骤以及与程序相似性判定相关的定义.程序相似性判定的流程如下.
1) 判断待测程序能否实现测试用例的重用:首先观察测试程序所输入的参数是否受到个数限制,如果测
试待测程序时输入的参数数量都是一定的,而且它们所限定的数量是不同的,意味着它们的测试用例
无法直接共享,本文不作比较;
2) 关键字流图最大公共子图的构建:若待测程序之间能够实现测试用例的重用,则构建关键字流图,利
用动态规划算法比较关键字流图中关键字的异同.若关键字相同,则该关键字所属的节点即属于公共
流图子图,并对此节点进行标记,以此构建待测程序的关键字流图最大公共子图;