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

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

3) 相似度的判定:使用最大公共子图距离算法计算关键字流图子图距离,该距离的大小决定了程序的相
似程度.

1. 判断待测程序能否
实现测试用例的重用
判定程序 否
源程序 是否能实现测试 条件不满足,结束
用例的重用

是
2. 关键字流图子图的构建 输入
输出 输入
关键字流图 公共子图
构建模型 关键字流图 构建模型

输出
3. 相似度的判定 输出 关键字流图 输入 最大公共
程序相似度 公共子图 子图距离

判断程序 得出结论
是否相似

Fig.1 Determining program similarity
图 1 程序相似性的判定
2.1 相关定义
定义 1(关键字). 作为代码核心的标识符,用于表示一种数据类型或程序结构.像 Java 和 C 语言等编辑语言
都有自定义的关键字.本文选择 Java 代码编写的程序作为实验对象,表 1 列出了 Java 语言中的关键字.
Table 1 Keywords of Java language
表 1 Java 语言的关键字
abstract assert boolean break byte
case catch char class const
continue default do double else
enum extends final finally float
for goto if implements import
instanceof int interface long native
new package private protected public
return strictfp short static super
switch synchronized this throw throws
transient try void volatile while
定义 2(关键字流图). 关键字流图(keyword flow graph,简称 KFG)是一个五元组(V,E,keyword,entry,exit),其
中:V 表示节点集,源程序的每个基本语句块都对应流图的相应节点;E 是边集,表示语句的流向;keyword 表示关
键字集,存储着节点中的关键字,若源代码中无关键字,该节点储存字符 null;entry 和 exit 分别表示程序唯一的入
口节点和出口节点.
定义 3(关键字流图公共子图). 节点集 V 中的每个节点均是关键字流图 G 1 中的节点,同样又是关键字流图
G 2 中的节点,那么节点集 V 在流图上构成的图即为流图 G 1 和 G 2 的公共子图.若存在节点集 G,且 G 1 和 G 2 不存
[8]
在其他的子图的节点数大于 G,那么 G 是 G 1 和 G 2 的一个最大公共子图 .