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

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

定义 4(前缀与后缀) [14] . 前缀 Pref[S,i](1≤i≤L),指从字符串 S 的第 1 个字符开始至字符串的某个位置 i 结
束的特殊子串,可记为 S[1,i];后缀 Suffix[S,i](1≤i≤L),指从字符串 S 的位置 i 开始至整个串末尾的一个特殊子串,
可记为 S[i,L].
根据定义 4,公共前缀(后缀)表示一个字符串既是字符串 S 的前缀(后缀),又是字符串 T 的前缀(后缀),那么
该字符串是字符串 S 和 T 的公共前缀(后缀).
定义 5(最大公共子图距离). 给定两个非空图 G 1 和 G 2 ,以及它们的最大公共子图 mcs(G 1 ,G 2 ),它们之间的距
离 [21,22] 可表示为
| mcs ( ,G G ) |
(,G
DG 1 2 ) 1=− 1 2 (1)
max(| G 1 |,| G 2 |)
其中,|G 1 |和|G 2 |分别表示 G 1 ,G 2 的节点数,mcs(G 1 ,G 2 )表示最大公共子图的节点数.那么图 G 1 与 G 2 的相似度可以
定义为
| mcs ( ,G G ) |
SG ) = (1− D ( ,G G )) 100%× = 1 2 × 100% (2)
( ,G
2
1
1
2
max(| G 1 |,| G 2 |)
定义 6(组间变异和组内变异). 在统计学中,组间变异表示数据的各组平均数 X 与总平均数 X 之间的离均
i
差平方和,记为 SS TR ;而组内变异表示每组数据中的每个测量值 X ij 与该组平均数 X 之间的离均差平方和,记为
i
SS e .它们的公式分别表示为
k k i n
SS = n (X − ∑ X ) ,SS = 2 ∑ n (X − ∑ X ) 2 (3)
TR i i e i ij i
i= 1 i= 1 j= 1
其中,n i 为第 i 组的组内数据个数,k 为组数.
定义 7(方差分析). 在统计学中,方差分析(analysis of variance,简称 ANOVA)是用于两个及两个以上样本均
数差别的显著性检验,又称为“变异数分析”或“F 检验”.F 值为组间均方 MS TR 与组内均方 MS e 的比值,表示为
F=MS TR /MS e (4)
其中,MS TR =SS TR /k−1,MS e =SS e /N−k.这里,N 为各组数据个数的和,k 为组数.
2.2 关键字流图的构建
关键字是代码核心的标识符,能够代表代码的结构或者数据类型.某些代码中的关键字相同,意味着它们的
代码结构相同.源代码中,每行代码或者功能相近的若干行代码为一个基本块,每一个基本块构成一个节点.关
键字流图的节点中存储了形成该节点基本块中的关键字,若基本块中无关键字,此节点存储字符串 null;若该行
代码存在两个及以上的关键字,记录第 1 个关键字即可.构建关键字流图的步骤类似于控制流图的构造过程,已
有很多研究,本节不再做具体说明.下面是冒泡排序的关键字流图构造示例.
图 2 中,图 2(b)是图 2(a)冒泡排序源码所对应的关键字流图.可以看出,关键字流图节点中存储了形成该节
点的关键字.例如:生成第 2 个节点的基本块中含有关键字 int,该基本块在生成关键字流图过程中将该关键字储
存在相应的节点上.待测程序的关键字流图构建完成,接下来比较待测程序关键字流图中关键字的异同,构建待
测程序的关键字流图最大公共子图.图 3~图 5 分别给出了冒泡排序的控制流图、程序流程图和数据流图等几
种比较常用的软件结构图与关键字流图的比较.通过对比发现:
• 关键字流图比较程序相似性,注重程序的结构和功能上的异同,符合功能结构相同的程序,其测试用例
会以更大概率共享的理念;
• 控制流图能表达程序的结构,但不能展示图中每个节点的功能;
• 程序流程图能清晰地表达程序的流程及功能,但存在许多相似节点合并的现象;此外,用自然语言总结
节点功能存在一定的主观性,会因个人用语不同而存在文字上差别较大的情况;
• 数据流图比较详细地阐述了程序主体及功能,也因此使其更加复杂,在比较程序相似性方面存在与程
序流程图相同的缺点.