面向高级别代码克隆检测方法的设计与实现*

邹 悦，吴 鸣，徐 云

(1.中国科学技术大学计算机学院，安徽 合肥 230027;2.安徽省高性能计算重点实验室，安徽 合肥 230026)

1 引言

在实际软件项目中，代码克隆是指复制粘贴式的代码复用或者模式化思维所造成的相同或相似代码重复出现的现象[1]。

由于开发风格因人而异，对同一功能的不同实现方式导致文本差异较大的高级别克隆在软件中广泛存在(如表1所示)，不利于后续开发人员对代码的解读和维护，也增加了对软件进行二次开发的难度。因此，高级别代码克隆的检测可以帮助程序开发人员定位这些克隆代码，然后进行代码重构和系统维护，在软件开发过程中十分重要。

Table 1 Number of different typecode clones in BigCloneBench

目前在学术界，相关研究者按照源码文本之间的相似程度将代码克隆划分为4个级别[2,3]：Type-1的代码克隆是指除了空白、注释和布局之外完全相同的代码。Type-2的代码克隆是指在Type-1的基础上，除了标识名、变量名、变量类型和函数名以外完全相同的代码。Type-3的代码克隆是指在Type-2的基础上存在着一定的插入、删除和修改语句的相似的代码。Type-4的代码克隆是指功能相似但是通过不同的语法方式实现的代码。对于Type-3和Type-4的高级别代码克隆检测，目前已经有一些国内外的学者进行了相关研究，其中基于程序依赖图PDG(Program Dependency Graph)的方法是一类重要的检测方法[4]。

然而，现有的基于PDG的代码克隆检测方法首先使用静态分析工具来构建包含源码语法结构及调用关系，数据流等的程序依赖图，再采用子图同构检测等精确图匹配算法找出2个相同或相似的PDG，以此发现克隆代码。但是，子图同构检测算法是经典的NP难问题[5]，算法的高复杂度会导致时间消耗巨大，无法用于检测大型的软件系统，而且这种精确的图匹配算法容错率低，也会导致克隆代码的检出率低。

为此，本文提出了一种基于Weisfeiler-Lehman图核算法的代码克隆检测方法。本方法首先对PDG的结构进行了简化；然后使用特征向量相似度的计算进行候选代码对的过滤；最后采用Weisfeiler-Lehman图核这种非精确图匹配的算法进行PDG的相似度计算，能够更高效地检测出更多的高级别克隆。

2 相关研究

本节主要介绍了一些学术界的代码克隆相关的研究，例如不同类型的代码克隆检测方法，现有的图匹配算法分类。

2.1 代码克隆检测方法

基于度量的代码克隆检测方法主要是收集代码块的若干度量值，如函数长度等，构成向量，通过比较向量的相似度来进行克隆的检测。例如，Mayrand等[6]的方法就是收集函数单元的行数、函数调用的数目等进行相似度比较，这种方法虽然能够更快速地进行代码相似度比较，但是无法保留源代码中的一些语法结构信息，会带来假阳性过高的问题。

基于文本的克隆检测方法将代码行作为长字符串，使用字符串匹配算法来检测克隆。例如，Baker[7]将每一行的代码文本哈希后做行粒度的字符串匹配，这种方法比较适用于低级别的克隆检测，对文本相似度高的克隆代码，仍存在召回率低、检测级别低等问题。

基于token的克隆检测方法通过解析工具将源代码程序解析成token序列后再进行比较。例如，CCAligner[8]、SourcererCC[9]和NICAD[10]等方法，对代码的token序列进行相似子序列的查找，这种方法速度快、精度高，可以检测出克隆代码的格式变换以及重命名，但是不适用于语法结构相似的高级别克隆。

基于抽象语法树AST(Abstract Syntax Tree)的克隆检测方法是将代码转化为抽象语法树(AST),然后通过树的匹配算法来检测相似的子树。DECKARD[11]就是通过AST的相似子树的匹配来检测克隆的，但是这种方法仍然丢失了一部分代码语法信息，并且子树的定位和匹配复杂度过高，存在检测不全的问题。

基于PDG的克隆检测方法通过比较源代码的PDG之间的图相似性来检测代码克隆。例如，CCSharp[12]使用VF2子图同构检测算法[13]来发现代码克隆，但是这种精确图匹配的算法存在时间复杂度高、召回率低等问题。

此外，近年来随着深度学习的发展，也有一些方法通过使用深度学习模型在一些大型的代码集上进行训练然后检测克隆代码，例如，Oreo[14]方法在单一的数据集上精确率和召回率表现都较好，但是存在过拟合和可解释性差等问题。

2.2 图匹配算法

图匹配算法可分为精确匹配和非精确匹配算法。精确图匹配算法主要是通过子图同构匹配来判断图相似度，例如Ullmann[15]提出的同构检测算法、VF2同构检测算法[13]等。但是，精确图匹配大都是NP难问题，检测算法时间消耗过大，且还会降低对图结构误差的容忍性。

非精确图匹配算法主要是通过将图结构识别转为统计识别问题，找到精确图匹配最好的近似解[16]，主要包括图嵌入和图核2种算法。图嵌入是指提取图的一些特征值进行相似度比较。这种降维处理损失了图中包含的大量结构信息，会降低图匹配精度，可以用于过滤操作。图核算法[17]，是把图映射到向量特征空间，使得2个图的相似性等于它们在向量特征空间中的内积。图核算法具体的流程如下所示：

(1) 给定2个图G1(V1,E1)、G2(V2,E2),以及一种图分解方式F，分解后的子结构为：

F(G1)={S1,1,S1,2,…,S1,N1}

F(G2)={S2,1,S2,2,…,S2,N2}

(2) 基于上述子结构，G1和G2的图核值可以表示为:

其中,σ(S1,n1,S2,n2)在S1,n1和S2,n2同构时为1，不同构时为0。因此,任何一种图分解方式和子结构同构判断方式的组合都可以定义出一个新的图核。这种算法既保留了核函数计算效率高的优点，也包含了图数据的结构化信息。

Figure 2 Example of PDG of codes图2 代码程序依赖图示例

3 方法设计

本文首先生成了源代码中函数级别的程序依赖图，并对生成的图结构设计了约简的策略，随后对候选的代码对集合进行特征向量的提取和过滤，最后应用Weisfeiler-Lehman图核算法[17]进行图相似性的比较，找出代码克隆，其总体流程图如图1所示。

Figure 1 Flow chart of the proposed code clone detection method图1 本文代码克隆检测方法流程图

3.1 PDG的生成和简化

为了进行程序依赖图相似度的计算，本文需要选取一个合适的程序依赖图生成工具，目前开源的工具有Frama-C[18]和TinyPDG[19]。Frama-C工具只针对C语言程序，TinyPDG是针对Java语言程序的PDG生成工具。由于代码克隆检测方法的评估框架BigCloneBench是基于Java语言的，本文选取TinyPDG工具进行改进，用于PDG的生成。

TinyPDG将源代码程序生成对应的PDG后通过dot文件类型存储，通过节点编号、形状等属性来表示语句的不同类型，例如声明语句、控制语句和赋值语句，通过边的形状来表示语句间的控制依赖、数据依赖以及地址依赖关系。本文首先对PDG按照函数级别进行了切分，剔除了工具自动生成的与语法无关的节点，例如函数进入和退出节点，最后对函数中一些冗余子图，例如第三方函数调用子图进行了合并，这样可以缩小PDG的规模，从而减少后续图匹配算法的时间消耗，示例如图2所示。

3.2 PDG集合的过滤

针对候选的代码对集合，本文首先进行规模比过滤，如果2个图的节点数相差过大，则过滤掉该候选对。然后，本文统计了PDG中不同依赖关系的边的条数和不同类型的节点数目组成特征向量，进行余弦相似度的计算，小于给定阈值的候选对会被直接过滤掉。这样可以大大缩小后续需要进行图匹配的PDG对规模，提升速度。

3.3 基于Weisfeiler-Lehman图核的克隆检测

3.3.1 克隆检测方法流程

针对程序依赖图的结构特征，本文使用并改进了Weisfeiler-Lehman图核算法来进行有向有标签图的相似度匹配。Weisfeiler-Lehman图核算法的基本思想是，对每个节点的所有邻接节点的集合的标签进行排序，然后把这些标签根据某一映射压缩成新的更短的标签值，如图3所示。

Figure 3 Computation of the Weisfeiler-Lehman graph kernel for one iteration图3 Weisfeiler-Lehman图核一次迭代过程

因此,基于Weisfeiler-Lehman图核的图匹配算法及改进步骤如下所示：

(1) 对PDG图中每个节点的标签按照语法类别进行Hash处理,将其结果作为图的初始标记。

(2) 在设定的h次迭代过程中，每次迭代都将当前节点的邻居节点的标签汇集在当前节点中，再对该标签序列使用局部敏感哈希算法进行压缩更新，得到新的节点标签。

(3) 迭代过程完成后，若更新后2个节点的标签相同，则认为以这2个节点为根节点，高度为h的子树存在同构。

(4) 计算出2个图结构间节点标签集合中相同的节点标签对数，即为图核的值，若2个图的图核值满足设定的阈值范围，则认为2段代码为克隆代码。

(5) 动态设定迭代次数(较小图直径/2),每次迭代完成后统计图中相同标签的节点数目。

(6) 在第n(n≤h)次迭代过程加入权重因子(h-n+1)/h，对低次的迭代赋予更高的权重。

在基于Weisfeiler-Lehman图核算法的图匹配之后，即可计算代码对的图核值，代表着2个图中相似点的总数量。本文使用图核值与较小的程序依赖图的比例作为2个图的相似度，如果相似度大于设定的阈值，则认为该代码对为代码克隆。

3.3.2 基于Weisfeiler-Lehman图核检测算法的优劣势分析

使用基于Weisfeiler-Lehman图核算法的非精确图匹配方法可以有效地将每个节点的邻居节点信息进行归总，2个节点的标签序列Hash值的比较，对应的就是以这2个节点为根的一个子树结构的相似度比较。这样可以有效地避免子图同构这种精确图匹配算法中每个节点比较的复杂性，更加快速地计算出2个图的相似度，同时也考虑到了2个图中只存在部分相似性的情况，提升克隆代码的检出率。但是,Weisfeiler-Lehman图核算法对PDG的规范要求较高，所以需要提前对PDG做好预处理工作。同时，虽然本文方法已经大大缩短了图匹配时间，但是与token方法相比，仍然存在很大差距，因此仍然需要设计好的过滤算法加以辅助。

4 实验结果与分析

4.1 数据集介绍与实验配置

在评估方法的有效性时，本文选择了学术界代码克隆检测方法的统一评估框架BigCloneEval[20]。框架中使用的BigCloneBench数据集是由加拿大的Jeffery和Roy团队建立的人造Java数据集，从25 000个软件中提取了包含了43种功能共约59万个Java文件，总代码行数约350×106行，包含了800多万对的真实克隆对。所有的实验都在单机Ubuntu14.04LTS四核8 GB内存的操作系统下进行。

4.2 评估标准与结果分析

由于本文提出的基于Weisfeiler-Lehman图核的方法基于非精确图匹配算法，能够更加快速、全面地检测出高级别克隆。因此，在实验评估标准的选择上，本文选择了代码集合中检测出克隆代码对的精确率、召回率和时间性能3个评估标准。同时，在对比方法的选取上，本文选择了代表性较强的克隆检测方法，包括基于token的检测方法CCAligner、SourcererCC、NICAD,基于AST的方法DECKARD，由于基于PDG的克隆检测方法CCSharp只针对C语言程序，本文选取了包含PDG信息的Oreo工具进行对比实验。

4.2.1 召回率

BigCloneBench评估框架会自动评估代码克隆检测方法每个级别的克隆检测召回率。如表2所示的实验结果表明，在文本相似度比较大的低级别克隆检测上，由于在过滤阶段过滤掉了一些较短的函数，本文方法的召回率都略低于其他克隆检测方法的。但是，在Moderately Type-3、Weakly Type-3和Type-4的高级别克隆检测的召回率上，本文方法明显好于Oreo、CCAligner等其他克隆检测方法。对克隆对详细分析后发现，本文方法能够检测出更多的小结构克隆，即2个图之间存在局部相似性，但是不存在子图同构的情况，因为检测方法对每个节点的子结构都进行了比较，能够发现这种局部相似性。

4.2.2 精确率

由于BigCloneBench只报告方法的召回率，而检测结果规模又较大，因此本文按照学术界通用的方法对克隆结果进行了抽样检测，随机选取了400对克隆代码进行人工确认，结果如表2所示(其他工具的精度结果取自之前的工作[8])。实验结果表明，本文方法的精确率略低于Oreo及CCAligner这些基于token的检测工具，但是仍然比NICAD提升了近25%，比DECKARD提升了近50%。因为一些变量名或者代码语句的插入或删除会导致PDG图结构的变化，以及预处理过程中对PDG进行了简化和节点标签化的处理，这些都会导致检测结果中假阳性的存在，降低检测结果的精确率，但是可以根据用户需求通过调整相似度阈值来平衡召回率和精确率。

Table 2 Clone detection results comparison of different methods on BigCloneBench

4.2.3 时间性能

在时间性能的对比实验中，本文在不同规模的代码数据集合上对不同的代码克隆检测方法进行了实验。由于基于PDG的克隆检测方法CCSharp只针对于C语言程序，因此本文加入了将Weisfeiler-Lehman图核算法换成CCSharp采用的精确图匹配算法(VF2子图同构算法)的时间对比实验。如表3所示的实验结果表明，由于图的生成和预处理过程的时间消耗较大，非精确图匹配算法虽然快于精确图匹配算法，但是仍然比不上token方法，本文方法的时间略慢于基于token的CCAligner和SourcererCC，但是相比NICAD和DECKARD算法以及CCSharp采用的VF2算法的速度有了很大的提升，能够运行在更大规模的代码集合上。

Table 3 Time cost comparison of different methodson different scale codesets

5 结束语

本文针对文本差异较大的高级别克隆检测问题,提出了一种基于PDG的非精确图匹配方法。

该方法首先对根据代码文本生成的程序依赖图进行了简化处理，再通过特征提取和特征向量的相似度计算对候选的代码对集合进行了过滤，减小了后续图匹配的集合规模，最后使用基于Weisfeiler-Lehman图核的非精确图匹配算法进行了PDG的相似度计算，并输出了检测的克隆结果。实验表明，在高级别克隆检测的召回率上，本文方法相对于已有的克隆检测方法有了很大的提高，并且运行速度也比已有的PDG检测方法更快。下一步工作的重点是提高低级别克隆检测的召回率，解决小图克隆检测不全的问题，并加快方法运行速度，提高方法的可扩展性。