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

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

由表 8 的实验结果可知:变异概率的改变,给实验结果带来了很小的变化.变异概率由 0.1 变化到 0.3 时,冒
泡排序中目标路径的覆盖率提高了 7%,平均进化代数减少 3.7,F 值仍远大于 F 界值 3.04.本文方法测试结果表
明:在 3 种变异概率下,其目标路径的覆盖率皆为 100%.对比两个实验的实验结果可知:3 种变异概率下使用本文
方法的测试效率远远高于传统方法,相似程序检测时用例重用效果较好.
表 9 中的数据为本文方法和业界测试用例生成效率较高方法的各性能指标.为了检测相似程序间测试用
例的重用效果,排除其他因素造成干扰,本实验遗传算法的各种参数和关键点路径法 [20] 中的参数保持一致,并且
选择相同的目标路径.通过比较平均迭代次数可看出,本文方法实验中的种群能更早地覆盖目标路径.
Table 9 Performance comparison between our method and the key-point path method
表 9 本文方法与关键点路径法性能比较
方法 输入分量数 关键点理论路径数 平均迭代次数
关键点路径 [20] 3 8 10.08
本文方法 3 8 5.3
3.4 进一步实验

为了证明面向关键字流图判断程序的相似性,并将测试用例重用到相似程序测试用例的生成中的效果较
好,实验特别设计了基于控制流图、程序流程图及数据流图的方法来判断程序的相似性,并将相似度较高的程
序作为实验对象检验测试用例的重用效果,以便于与我们基于关键字流图的方法作对比.实验按照与关键字流
图相同的方法计算程序的相似性,例如:利用控制流图计算程序相似度时,首先将待测程序生成控制流图,接下
来查找控制流图的最大公共子图.由于控制流图的节点中没有存储关键字等信息,故而查找公共节点时,考察有
向边的数量与方向.若节点边的来向、去向和数量完全相同,则该节点属于公共子图中的节点.最后使用最大公
共子图距离算法计算程序的相似度.详细过程可参考第 2 节.表 10 为待测程序的基本信息以及实验结果.

Table 10 Basic information and experimental results of the program to be tested
表 10 待测程序的基本信息与实验结果
函数个数/ 程序相似度(关键字流图/控制流图/
程序名称 时间(s) 平均进化代数 覆盖率(%)
代码行数 程序流程图/数据流图)(%)
身份验证 13/209 55/80/86/86 33.30 136.20 91
登录验证 8/178
用户登录 10/217 44/74/79/79 34.10 95.60 94
登录验证 8/178
数据处理 8/226 38/75/82/82 47.30 220.55 88
信息下载 5/186
表 10 显示了 3 组待测程序的名称、子函数个数、代码行数以及基于关键字流图、控制流图、程序流程图
与数据流图方法下的程序相似度.从数据中能够看出:在 3 组程序中,关键字流图下的程序相似度都低于 70%,而
其他 3 种流图判定该程序的相似度时皆有较高的相似度(这样就超过了相似度设定的阈值,把本来不相似的程
序也判定成相似了).实验结果显示了待测程序测试用例重用的效果(特别注意:表中的 3 个指标值是根据控制流
图、程序流程图以及数据流图得到的结果,并且它们的测试过程一样,因此数据一致).从表中的 3 个评价指标能
够看出:基于控制流图、程序流程图以及数据流图判定待测程序的相似度得到较高的值,其测试用例的重用在
一定程度上确实降低了目标个体的平均进化代数,并且提高了其覆盖率,但均未达到 100%.结合第 3.3.3 节以及
本文其他实验的结果,基于关键字流图相似程序间测试用例的重用的效果更好,其目标个体的覆盖率皆为
100%,而目标个体的平均进化代数也较为更低.
控制流图、程序流程图和数据流图判定程序相似性时只比较了程序的结构而没有考察图中节点的功能,
而基于关键字流图比较程序相似性时,综合比较了程序的结构与功能.因此,判定程序的相似度更准确,其测试