软件开发过程中, 开发人员通过复制代码片段, 并修改或不修改部分内容来实现新的功能, 这种方式被称为代码克隆^[1]. 虽然复用代码可以加速软件的开发 , 但是也会导致软件维护困难的问题, 对软件质量产生影响^[2]. 代码克隆检测作为一项基础研究, 被应用到代码剽窃检测^{[3, 4]}、演化分析^[5]、Bug检测^[6]、软件质量评估^[7]等领域. 当前研究表明, 克隆代码广泛存在于大型代码仓中, Kamiya等人^[8]报告JDK中存在29%的克隆代码, Baker^[9]在Linux源码中检测到22.3%的代码属于克隆. 从实用性和易用性方面出发, 基于Token的克隆检测方法更适合大型代码仓的检测.

目前在学术界, 根据代码的不同表征形式, 克隆检测方法主要分为基于Token^[10-13]、抽象语法树(AST)^[14]、程序依赖图(PDG)^[15]、深度学习^{[16, 17]}等. 基于AST、PDG、深度学习的方法通过分析程序的语法及语义信息, 建模程序代码的高级别特征, 达到检测文本差异较大的克隆代码的目的, 但是这些方法通常需要消耗大量的时间进行建模及检测, 不适用于大型代码仓, 如主流的AST方法Deckard^[14]、PDG方法CCGraph^[15]分别需要消耗1 h 12 min、15 min 10 s检测1 M行代码仓, 与之相比, Token方法CCAligner^[12]只需1 min 13 s. 然而, 基于Token的克隆检测方法由于缺少使用程序的语法及语义信息, 在检测文本差异较大的代码上效果较差, 如CCAligner方法在公开数据集BigClone-Bench^[18]中的Moderately Type-3的召回率只有10%. 因此, 通过在Token方法中加入程序的语义信息, 以提高Token方法的检测能力, 同时维持其检测快速的特点, 是在大型代码仓中进行克隆检测的关键.

根据检测过程使用的粒度, 基于Token的检测方法可以分为行粒度和词粒度两类. 基于Token的行粒度检测方法将代码行作为检测的基本单元, 通用的流程包括统一程序的代码风格, 归一化变量等标识符, 并匹配代码片段中行之间的相似性以验证是否为克隆. CCFinder^[8]对C和Java语言分别提出6项代码行的转换规则, 并使用后缀树算法检测克隆, 但是CCFinder只支持检测Type-1和Type-2克隆. NiCad^[11]提出一种灵活的代码行切割策略, 将一行代码分为多行, 以增强对于代码行修改行为的容错性, 然后以切割后的行作为基本单元, 计算代码片段的最长公共子序列衡量相似性, 但是切割策略需要人为设定, 会引入误差. CCAligner^[12]通过建立e-误配索引表检测存在连续代码行失配的large-gap克隆, 同时在大型代码仓中达到更短的检测时间. LVMapper^[13]借鉴生物信息学中序列比对的方法, 检测存在分散的失配行的large-variance克隆, 且能够检测250 M行的代码仓. 但是, 这些行粒度的检测方法在面对克隆片段的多个代码行都存在细微修改, 以及行顺序调整而不影响整体功能的情况时, 会出现检出效果不足的问题. 基于Token的词粒度检测方法将单词作为基本检测单元, 如SourcererCC^[10]将代码片段通过词法解析程序转为词袋, 通过判断词袋之间的相似性验证是否为克隆. 但是SourcererCC没有对用户自定义的标识符(如变量名等)归一化, 不能检测出对标识符统一修改的克隆情况.

综上所述, 传统的基于Token的行粒度和词粒度克隆检测方法在大型代码仓中有较好的性能, 但是大都从文本角度出发, 没有考虑代码片段的语法及语义信息, 而限制其检测能力. 为此, 本文提出一种赋予语义信息的Token词粒度检测方法, 从程序的抽象语法树中获取Token的语义信息, 并基于赋予语义信息的Token增强对于文本差异较大克隆的检测能力. 另外, 使用函数名和类型名角色的Token建立高效索引, 达到快速检测克隆的目的. 与主流方法相比(包括NiCad, Deckard, CCAligner等), 本文方法显著提升在Moderately Type-3克隆上的召回率, 同时在大型代码仓中需要更少的检测时间.

1 基于Token语义构建的代码克隆检测

本文的基于Token语义构建的克隆检测方法主要由两个核心步骤组成, 包括赋予Token语义信息和基于语义Token的克隆检测. 检测整体流程如图1所示.

赋予Token语义信息过程主要目的是通过分析程序的抽象语法树, 抽象Token的语法及语义信息, 增强Token的特征描述. 首先, 使用语法分析工具对每个代码块构建抽象语法树; 然后, 根据语法规则分析每个Token对应的角色, 将其标记为变量名、函数名、类型名等角色; 最后, 对代码块的每个Token从其抽象语法树的路径中获取语义信息, 将每个Token编码为一个固定维度的特征向量.

克隆检测过程的主要目的是通过在代码块的函数名和类型名Token上建立的全局索引表加速有效的候选代码块的筛选, 同时利用赋予语义的Token判断代码块之间的相似性. 首先, 利用所有代码块的函数名和类型名角色的Token建立全局索引表; 然后, 对于每个代码块, 通过查询全局索引表快速定位出候选克隆块; 其次, 针对定位得到的候选克隆块, 通过一系列的过滤策略, 去除高度不相似的代码块, 防止后续验证过程不必要的时间开销; 最后, 根据赋予语义的Token计算代码块之间的相似性, 从而得到克隆对.

1.1 构建抽象语法树

基于开源工具Javalang^[19]为代码块生成抽象语法树. 现有的工作^[20]表明了抽象语法树可以有效地表示代码片段的语法及语义信息. 抽象语法树通过树形结构描述源代码的结构特征, 不依赖于源代码语言的具体细节, 而对语法和语义信息进行抽象描述^[21]. 抽象语法树的内部节点描述了源代码的基本语义结构, 叶子节点描述了具体的Token内容. 本文参考Java语法规范^[22], 对Javalang生成的AST的内部节点进行整理, 共汇总得到25种内部节点类型, 如表1所示. 其中, 对for循环、do-while循环和while循环3种结构进行等价处理, 将他们转换为loop condition和loop body两类语法节点; 同时, 将一元及二元表达式抽象为3类语法节点, 分别是逻辑表达式(Logical Expression, 如>, <, ==, !=等), 数值表达式(Numeric Expression, 如+, –, *, >>, &等)和状态表达式(Condition Expression, 如&&, ||等).

图2为BigCloneBench数据集^[10]中的存在克隆情况的代码块示例, 该代码块读取特定编码的文件内容, 然后将文件内容以字符串的形式返回. 图3为代码块生成的抽象语法树, 为简化展示的结果, 只对第2行和第8行绘制树结构. 其中, 内部节点为表1描述的结构信息, 叶子节点为源码具体的Token值.

1.2 分析Token的角色

Token是组成源程序的基本词法单元, 并且Token可以分为很多角色, 包括关键字、标识符、常量、运算符和标点符号等, 其中标识符可以细分为变量名、函数名、类型名等角色. 受Oreo方法^[23]的启发, 如果两个代码块实现相似的功能(或者存在克隆行为), 它们有很大概率调用相同的函数并定义相同的类对象^[23]. 基于这种观察, 本文对Token的角色进行分析, 并将在第1.4节中使用函数名角色和类型名角色的Token建立全局索引表, 基于索引表查询与目标代码块存在相同的函数名和变量名Token的代码块, 将其作为候选代码块, 从而完成克隆对的定位操作.

本文通过分析Javalang中的语法规则标记Token的角色, 以图4中变量定义的语法规则为例, 赋值符号“:=”前的部分为规则名, 符号“:=”后的部分为该规则具体的定义内容. 从该规则中可以分析出, 变量定义(图4第1行)主要分为3个部分, 包括变量修饰符(如final等), 变量类型(如int, 自定类型名等)和变量声明列表. 变量声明列表(图4第6行)由一系列逗号分隔的变量定义体构成. 变量定义体(图4第7行)由两部分构成, 包括变量名(即VariableDeclaratorId)和初始化列表(即VariableInitializer), 位于VariableDeclaratorId部分的标识符即为变量名角色. 如图2第2行, fis的角色为变量名, FileInputStream的角色为类型名.

1.3 获取Token语义信息

本文从代码块的抽象语法树出发, 分析Token的语义信息, 通过Token的高维特征, 而不是仅从文本角度来验证Token之间的相似性, 达到检测结构相似的克隆对的目的. 抽象语法树的内部节点构成了程序的骨架结构, 叶子节点填充了具体的Token信息, 从根节点至叶子节点的路径描述了Token在抽象语法树中的结构特征. 如果两个Token有相似的路径结构特征, 那么这两个Token的功能存在相似性, 进一步地, 如果两个代码块中存在众多路径结构特征相似的Token, 那两个代码块很可能存在克隆行为. 标识符角色的Token表达了程序的功能, 其他角色的Token (如关键字、常量、运算符等)主要用于修饰程序的结构, 所以本文通过衡量两个代码块的标识符Token的相似性, 从而衡量代码块的相似性. 对于函数名和类型名角色的Token, 本文使用其文本字符串的形式, 对于变量名角色的Token, 本文编码其语义信息, 将其抽象为一个特征向量.

为了编码Token在抽象语法树中的结构特征信息, 本文先序遍历抽象语法树, 记录叶子节点Token的路径信息, 路径信息是由表1的节点构成的节点序列. 本文将节点序列构造为一个25维的整型向量, 向量中的每一维代表一种类型的节点, 每一维的值代表节点的频度, 另外, 如果Token在代码块中出现多次, 则将其对应的所有路径向量加和作为其最终的特征向量. 例如, 图2第8行的strBuf在图3的路径序列为N3(Method Definition)-N19 (Throw Body)-N5 (Loop Body)-N11 (Method Invocation), 编码的25维特征向量为[0, 0, 1, 0, 1, …, 1, …, 1, …, 0], 其中第3、5、11、19维的值为1, 其他位置的值为0, 另外strBuf出现在第4和12行, 分析对应位置的特征向量, 将它们与第8行的特征向量加和之后作为strBuf的最终特征向量.

1.4 建立全局索引表

为了防止在代码仓中成对地匹配代码块来验证克隆对的相似性, 本文借鉴CCAligner^[12]和LVMapper^[13]方法, 构造索引表, 通过查询索引表获得指定代码块的候选克隆代码块. 由于CCAligner和LVMapper是行粒度的Token检测方法, 本文对构建过程进行改造, 使用代码块的函数名和类型名角色的Token, 对其建立n-gram序列, 生成索引表.

具体的操作步骤包括: 首先, 对每个代码块的函数名和类型名Token按照字典序进行升序排序; 然后, 对于每个排好序的长度为m的Token序列, 按照窗口大小为k, 步长为1的方式进行滑动, 获得m–k+1个k-gram字符串序列; 最后, 对k-gram字符串序列做哈希操作得到哈希值, 将哈希值作为索引项, 代码块的ID作为值, 插入到全局索引表中. 全局索引表的键的数据结构为k-gram序列的哈希值, 值的数据结构为包含该k-gram序列的代码块ID数组. 例如, 如果代码块B₁的函数名和类型名Token为A, B, C, D, E, 设定窗口k=3, 则索引表的内容为{hash(A, B, C):[B₁], hash(B, C, D):[B₁], hash(C, D, E): [B₁]}.

1.5 定位候选代码块

定位过程主要是尽可能多地找到潜在克隆代码块, 不需要保证克隆代码块的真伪. 如果两个代码块存在克隆行为, 那么它们的函数名和类型名角色的Token存在重叠的情况. 在第1.4节中定义的全局索引表的索引项是对函数名和类型名角色Token信息的聚合, 而互为克隆的代码块之间存在相同的聚合信息. 因此, 可以对指定代码块的函数名和类型名角色的Token构造k-gram序列后, 查找全局哈希表, 得到的代码块ID数组即为候选代码块, 具体的步骤如算法1所示.

算法1. 定位与指定代码块存在克隆的候选代码块法

输入: 全局索引表M, 查询的代码块B.

输出: 候选克隆代码块集合Q.

1 对序列S按照窗口大小为k, 步长为1的方式进行滑动, 生成m–k+1个k-gram列表, 即[T₁, T₂, …, T_|S|–k+1].

2 初始化候选克隆代码块集合Q为空; 获取代码块B的函数名和类型名角色的Token序列, 并按照字典序升序排序, 得到序列S.

3 对于列表[T₁, T₂, …, T_|S|–k+1]的每个k-gram序列, 进行hash操作得到其哈希值H_i=hash(T_i).

4 将哈希值H_i作为关键字查询全局索引表M, 得到对应的值列表V_i=get(M, H_i); 然后合并列表V_i到集合Q中.

5 返回候选克隆代码块集合Q.

1.6 过滤候选代码块

过滤过程主要目的是通过低时间复杂度的计算方式, 删去定位过程中得到的候选代码块中的伪克隆代码块, 避免这些伪克隆在后续验证过程中被再次计算. 本文通过两种策略进行过滤操作, 也就是代码块的规模差距和代码块中相同函数名和类型名角色Token的覆盖率. 如果两个代码块的Token个数差距过大, 那么它们互相之间不太可能存在克隆关系, 其计算公式如式(1)所示, 并限制个数的比例不小于阈值α. 另外, 如果两个代码块的相同函数名和类型名角色的Token的比例太小, 那么它们可能主要是实现不同的功能, 而不存在克隆关系, 其计算公式如式(2)所示, 并限制比例不小于阈值β.

$ SR = \frac{{\min (\left| {B_1} \right|, \left| {B_2} \right|)}}{{\max (\left| {B_1} \right|, \left| {B_2} \right|)}} $

(1)

其中, B₁,B₂分别为指定代码块和候选代码块; |B₁|, |B₂|分别表示代码块B₁,B₂中标识符Token的总数.

$ TR = \frac{{{count} \_same\_token(T_1, T_2)}}{{\min (\left| {T_1} \right|, \left| {T_2} \right|)}} $

(2)

其中, T₁, T₂分别为代码块B₁, B₂的函数名和类型名Token, 函数count_same_token用于计数相同函数名和类型名Token的个数.

1.7 验证克隆对

在过滤阶段完成之后, 候选代码块中包含一些潜在的代码块与指定代码块存在克隆关系. 验证阶段需要计算指定代码块与候选代码块的相似度, 从而得到克隆对. 克隆对的相似性计算包含两个方面, 一方面是函数名和类型名角色在文本上的相似性, 另一方面是赋予语义信息的变量名角色Token的相似性.

本文提出一种多轮匹配的近似算法计算两个代码块变量名角色Token的相似性. 每个变量名角色的Token编码为25维的向量, 则代码块的变量名角色的Token可形成一个向量集合, 两个代码块变量名角色Token相似度的计算转化为两个向量集合相似度的计算, 考虑到精确的向量集合相似度计算的时间复杂度为 ${\rm O}(n!)$ , 本文提出一种近似的计算方式, 将时间复杂度优化到 ${\rm O}(k{n^2})$ , 具体的步骤如算法2所示.

算法2. 计算两个变量名角色Token向量集合的相似度

输入: S₁,S₂ are vector collection of variables for block B₁ and B₂, respectively. η is decreasing ratio.

输出: VR is the the similarity between S₁ and S₂.

1 sim_sum = 0; // sum of matched vectors

2 initialize array M₁ to size |S₁| with default value 0;

3 initialize array M₂to size |S₂| with default value 0;

4 for t=1.0 to 0.0 step η do

5　 for i=0 to |S₁| do

6 　　 if M₁[i]==1 then continue;

7 　　 for j=0 to |S₂| do

8　　　 if M₂[j]==1 then continue;

9　　　 s=cosine(S₁[i], S₂[j]);

10　　　 if s≥t then

11　　　　 sim_sum=sim_sum+s;

12　　　　 M₁[i]=1, M₂[j]=1;

13　　　 end if

15　　 end for

16　 end for

17 end for

18 return sim_sum/max(|S₁|, |S₂|);

在算法2中, 对于给定的两个向量集合和一个预设的下降率η (介于−1.0和0.0之间的小数), 计算向量集合的相似度. 在计算过程中, 每轮逐次减少匹配的阈值t (第4行), 遍历向量集合(第5, 7行), 计算选定的两个向量的余弦相似度(第9行); 将余弦相似度大于等于本轮阈值t的两个向量进行绑定(第12行), 并将这两个向量的余弦相似度计入总和sim_sum中; 另外, 如果选定的向量已经被绑定(第6, 8行), 则跳过向量的匹配; 最后将计算的向量和除以两个向量集合规模的最大值(第18行), 作为向量集合的相似度VR.

最后, 克隆对B₁,B₂的相似度的PR计算方法如式(3)所示, 将相似度大于阈值φ的克隆对输出.

$ PR = \mu \times TR + (1 - \mu ) \times VR $

(3)

其中, TR为克隆对的相同函数名和类型名Token的比例, VR为克隆对的变量名Token的相似度, μ表示代码块中函数名和类型名Token在代码块的全部标识符Token的占比, 不同代码块中的μ大小有所差异, 其计算方式如式(4):

$ \left\{ {\begin{array}{*{20}{c}} {{\mu _1} = \left| {{T_1}} \right|/\left| {{B_1}} \right|} \\ {{\mu _2} = \left| {{T_2}} \right|/\left| {{B_2}} \right|} \\ {\mu = ({\mu _1} + {\mu _2})/2} \end{array}} \right. $

(4)

其中, T₁,T₂分别为代码块B₁,B₂的函数名和类型名Token, 取μ₁, μ₂的平均值作为克隆对的μ值.

2 实验结果与分析 2.1 实验数据与环境

本文采用公开克隆检测数据集BigCloneBench^[18]进行实验. BigCloneBench是由加拿大的Svajlenko团队建立的人造数据集, 它从IJaDataset-2.0中挖掘克隆, 并标记出8 584 153个真克隆对和279 032个假克隆对. 其中包含55 499个Java文件, 根据功能分类保存到43个子文件夹中. 本文在BigCloneBench数据集上进行克隆检测从而验证工具的有效性.

为了对比不同工具可扩展性的差别, 本文从IJaDataset-2.0中分别抽取出1 M、10 M、20 M、30 M、250 M LOC (lines of code)代码构成规模数据集, 在不同的规模数据集上进行实验, 比较不同工具的检测用时从而体现可扩展性的差异.

实验的运行环境为Ubuntu 18.04系统, Intel(R) Xeon(R) Gold 5120 2.20 GHz CPU, 503 GB内存空间.

2.2 实验评价指标

本文采用精确率P(precision)、召回率R(recall)和时间性能3个指标来评估克隆检测工具. 精确率P表示被检测出来的克隆对属于真克隆的概率, 如式(5)所示; 召回率R表示真克隆对被检测出来的概率, 如式(6)所示:

$ P = \frac{{TP}}{{TP + FP}} $

(5)

$ R = \frac{{TP}}{{TP + FN}} $

(6)

其中, TP表示被预测为克隆且为真克隆对的数量; FP表示被预测为克隆但为假克隆对的数量; FN表示没有被检测出来的真克隆对的数量.

在评估工具的召回率时, 采用BigCloneEval^[24]评估框架. BigCloneEval是基于BigCloneBench设计的自动化评估工具, 它将标记出的真克隆对与克隆检测工具报告的克隆对进行比较, 根据被检测出的真克隆对数量报告克隆检测工具的召回率, 并将召回率分为Type-1 (T1)、Type-2 (T2)、Very Strongly Type-3 (VST3, 克隆对相似度介于0.9–1.0)、Strongly Type-3 (ST3, 克隆对相似度介于0.7–0.9)、Moderately Type-3 (MT3, 克隆对相似度介于0.5–0.7)和Weakly Type-3/Type-4 (WT3/T4, 克隆对相似度介于0–0.5)共6类.

在评估克隆检测工具的精确率时, 由于克隆检测结果数量庞大(接近百万个克隆对), 难以逐个验证克隆对的真伪. 本文采用学术界广泛使用的方法^{[10, 12]}, 从克隆检测结果中随机选出400个克隆对, 由3位超过6年编程经验的研究者人工验证克隆对的真伪, 根据验证的结果计算克隆检测工具的精确率.

2.3 检测方法有效性的实验结果及分析

为了对比本文克隆检测方法的有效性, 选取代表性较强的5类方法, 包括基于Token的方法: NiCad^[11]、SourcererCC^[10]、CCAligner^[12]和LVMapper^[13], 以及基于AST的检测方法: Deckard^[14]. 通过对比不同检测工具在BigCloneBench数据集上的精确率和召回率验证方法的有效性, 结果如表2所示.

实验结果表明, 本文提出的克隆检测方法在精确率方面有较好的检测效果, 达到91%, 表明检测出的克隆对基本上都是真克隆. 在召回率方面, 对T1、T2类型的克隆对检测达到接近100%的效果, 略低于NiCad、CCAligner和LVMapper, 在后续分析中发现, 没有达到100%的原因是Javalang工具在解析部分源文件时出现错误, 无法获得程序的抽象语法树, 导致与该程序相关的克隆对无法被报告. 在VST3和ST3类型的克隆上, 本文的方法略低于NiCad方法, 但仍处于领先水平.

另外, 相比于NiCad、SourcererCC、CCAligner、LVMapper和Deckard方法, 本文方法在检测MT3和WT3/T4类型的克隆上有最好的检测效果, 在MT3类型上召回率达到43%, 同时检测到176 712对WT3/T4类型的克隆. 这是由于NiCad、SourcererCC、CCAligner和LVMapper这些传统的基于Token方法单从程序的文本角度出发, 它们可以在T1、T2等不存在语句变异(如插入、删除和修改等)的克隆上呈现较好的效果, 但是对于语句行出现差别的克隆对(也就是MT3和WT3/T4克隆), 这些方法出现检测不足的问题. 而基于AST的方法Deckard, 由于其从AST子树匹配的角度分析, 对AST整体结构的建模能力不足, 在MT3和WT3/T4这样差异较大的克隆上效果不好. 本文方法从AST的路径上分析Token的语义信息, 同时考虑克隆过程中变化不大的函数名和类型名角色的Token, 在检测文本差异较大的克隆对上呈现较好的检测能力.

2.4 时间性能的实验结果及分析

随着软件功能的丰富, 当前的代码仓的体量呈现逐渐增大的趋势, 克隆检测方法在大型代码仓的检测时间是一项需要重点关注的指标. 本实验将与NiCad、SourcererCC、CCAligner和LVMapper方法对比, 统计不同方法在1 M、10 M、20 M、30 M、250 M行规模数据集上的运行时间, 评估不同方法的可扩展性的差异. 由于Deckard方法无法运行在10 M LOC数据集, 所以不对其进行展示, 其他方法的结果如表3所示.

从表3中可以看出, 本文提出的克隆检测方法在1 M、10 M、30 M和250 M LOC的规模数据集上需要最少的检测时间, 达到最好的可扩展性效果, 在20 M LOC数据集上略差于LVMapper方法. 能够快速检测的原因有两方面, 一方面是在定位过程中快速地查询到与指定代码块可能存在克隆的候选代码块, 并且通过低成本的过滤阶段去掉部分伪候选; 另一方面是在验证阶段优化相似性比对方法, 降低了时间复杂度.

3 结论与展望

为增强传统Token克隆检测方法在文本较大差异的克隆上的检测能力, 本文提出一种为Token赋予语义信息且适用于大型代码仓的方法. 该方法从程序的抽象语法树中分析Token的语义信息, 并从语义角度比较Token的相似性. 在检测过程中通过构建索引表、定位、过滤和验证步骤, 达到在大型代码仓中快速检测的目的. 实验结果表明, 相比于其他克隆检测方法(NiCad, Deckard, CCAligner等), 赋予语义的Token可以更好地表征语义信息, 显著提高在MT3克隆上的检测效果; 同时, 本方法在大型代码仓中表现出更加突出的时间性能. 在后续的研究中, 可以进一步优化Javalang生成抽象语法树的过程, 提高T1、T2类型的召回率, 另外可以尝试程序依赖图(PDG)中提取特征, 增强检测的能力.