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

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

begin
1 keywords←findKeywords(program1,program2); //查找待测程序源代码基本块中关键字
2 KFGs←buildKFGs(keywords); //分别构建待测程序的关键字流图
3 subgraphs←findSubgraphs(KFGs); //利用动态规划算法寻找关键字流图的最大公共子图
4 Knum,Snum←nodeNumber(KFGs,Subgraphs); //计算每个关键字流图的节点数,最大公共子图节点数
5 similarity←calculateSimilarity(Knum,Snum); //计算待测程序相似度
6 return similarity;
end
本节采用自适应的方法进行实验来选取程序是否相似的阈值 [23] ,实验对象为已知功能相近的程序或者不
相近的程序,实验方法为本节所提的程序相似性检测方法.表 3 和表 4 分别给出了本文方法验证部分基础程序
及系统中常用功能程序的相似性实验结果.
Table 3 Testing of the similarity between basic programs (%)
表 3 基础程序间相似性的检测 (%)
插值查找 二分查找 折半查找 顺序查找 基数排序 简单选择 冒泡排序 希尔排序
插值查找 100 71 75 71 56 50 50 43
二分查找 71 100 75 62 43 37 37 43
折半查找 75 75 100 100 43 37 37 43
顺序查找 71 62 100 100 43 37 37 43
基数排序 56 43 43 43 100 71 71 86
简单选择 50 37 37 37 71 100 100 67
冒泡排序 50 37 37 37 71 100 100 67
希尔排序 43 43 43 43 86 67 67 100
Table 4 Testing of similarity between commonly-used programs in the system (%)
表 4 系统常用功能程序间相似性的检测 (%)
用户登录 b 登录验证 信息下载 身份验证 b
用户登录 a 84 44 42 38
身份验证 a 37 55 43 92
数据处理 32 36 38 47
表 3 考察了多个查找算法和排序算法两种不同功能的程序.从表中实验的数据可以看出:功能相近程序的
相似性皆超过 70%;而不同功能的程序即使程序规模相近,其相似度也在 70%以下.本文将 70%设定为程序是否
相似的阈值.
表 4 中选用系统中常用的功能程序考察其相似度.用户登录 a 与用户登录 b 是两种不同脚本的登录算法,
登录验证为用户登录时后台的验证算法.用户登录、身份验证、数据处理和信息下载为同一系统下不同功能的
算法.表 4 中的实验结果再次验证了功能相同的程序间相似性较高,而功能不同的不相似程序的相似度均在
70%以下,证明本文将判定程序是否相似的阈值设定在 70%的合理性(在判定规模较小的程序时存在一定的偶
然性,应将特例排除).
2.5 用关键字流图比较程序相似性的优势
公共关键字流图子图比较程序相似性具有以下优势.
1) 将程序转化成关键字流图,关键字是代码的核心标识符,关键字相同的节点意味着生成该节点的代码
语句结构相同.通过比较关键字流图来判定程序的相似性,解决了两个程序功能相同但源代码差异较
大的问题;
2) 本文是在关键字流图最大公共子图的基础上比较程序的相似度.相对于最长公共子串比较相似性,公
共关键字流图子图更大程度比较了两个程序,避免了最长公共子串比较程序只取决于最长公共子串
大小片面性的问题;