1 背　景

代码克隆指的是在代码语句构成上或者语义上相似的代码片段, 其普遍存在于软件项目之中, 尤其在有众多参与者的大规模项目中存在的更多. 代码克隆产生的原因有很多, 主要是开发者在开发的过程中为了提高效率, 包括复制粘贴已有的代码片段并进行适当的增减语句或调换语句顺序, 或使用开发框架、设计模式等^[1]. 代码克隆会导致bug传播^[2], 增加代码维护成本. 现有研究表明, 20%–50%的大型软件系统都包含代码克隆^[3,4]. 因此, 准确地检测代码克隆对于软件开发和维护是至关重要的.

代码克隆检测问题一直在被广泛研究^[5-11]. 其中较为流行的方法是从源代码和抽象语法树(AST)中提取特征, 通过计算特征的相似度判断是否为克隆对^[9,12-16]. 近年来, 特征表示学习方法已经引起了学者们广泛的兴趣^{[10,11,15,17-19]}. 这些方法通过获得词嵌入和复杂的神经网络结构来编码源代码或者AST, 可以获得较好的检测效果.

代码克隆没有形式化定义, 较为公认的标准是将代码克隆分为4种类型^[6,7]. Ⅰ型克隆表示两段代码在除了注释、布局和空格以外完全相同. Ⅱ型克隆指的是替换用户定义的标识符, 在注释、类型和布局上有变化, 但语法或结构相似的代码段. Ⅲ型克隆涉及代码片段的插入和删除, 经过进一步修改(如添加或删除语句)的复制片段, 以及对空格、标识符、布局、注释和类型的更改. 之前的工作已经较好地研究了这3种类型的克隆^{[12,14-16,19]}. 本文主要研究Ⅳ型克隆, 即具有相似语义但语法结构有所差异的代码片段. Ⅳ型克隆的识别在本质上与Ⅰ–Ⅲ型克隆不同, IV型克隆更偏向语义, 即代码片段看上去不相似, 但是都实现了相同或者相似的功能. 图1列出了一个Ⅳ型克隆的例子, 图1(a)和图1(b)展示了复制文件功能的两种不同实现方式, 这对代码片段在语法上差异较大, 但实现了相同功能, 故而是IV型代码克隆.

关于Ⅳ型克隆的检测问题已经有相关研究工作^[9,10,20,21], 这些工作都采用了有监督学习的方法, 使用了经过标注的克隆对和非克隆对作为训练集. 例如, TBCCD^[10]和CDLH^[9]方法利用BCB中标注的几百万个克隆对, 并将这些数据按照8:1:1的比例分成了训练集, 验证集和测试集以训练深度学习模型. 这些方法取得了较好的效果. 但是人工标注一个大规模的训练数据集代价较大, 通常需要对不同代码较为熟悉的有经验的程序员进行高质量的代码标注工作.

本文旨在减少克隆检测模型所需要的标注训练样本的数量. 为此, 我们提出了两种新颖的预训练方法, 即针对token级别的词嵌入以及函数名预测, 以提升深度学习模型的代码表征能力. 首先, 程序标识符, 例如图1中的“buf”“dest”等, 是由开发人员根据自己的习惯和理解定义的, 具有较高的多样性和差异性, 可以导致较为严重的OOV (out-of-vocabulary) 问题: 即给出一个通过标准的Word2Vec预训练的词嵌入矩阵, 有较大比例的单词无法在矩阵中查询到. 针对该问题, 本文首次提出通过解决OOV问题来提升代码克隆检测准确性的研究. 我们提出采用基于子词组合嵌入的预训练方法^[22]. 对于不在词表中的token, 我们仍然可以通过子词组合获得其向量表示. 其次, 针对现有代码克隆检测方法需要大规模标注数据进行训练的问题, 我们提出利用无监督任务来辅助实现这个目标. 本文选择函数名预测任务对神经网络的模型参数进行预训练. Ⅳ型代码克隆检测和函数名预测都是面向语义的, 编写良好的函数代码的语义可以通过函数名体现出来. 因此, 通过函数名预测任务预训练神经网络的参数, 使神经网络的参数学到函数体的语义信息表示. 而后在该参数的基础上进行代码克隆检测任务的训练, 利用函数名预测任务学到的语义表示提高代码克隆检测任务的准确率. 由于函数名预测任务的训练数据集无需人工标注, 因此该策略可以极大减少人工标注代价.

为了验证该想法, 我们将代码克隆检测任务定义为一个二分类问题, 采用一种被广泛应用的, 包含自注意力机制的双向长短时记忆神经网络(AttBiLSTM)^[23]作为代码片段表征模型. 我们用AttBiLSTM神经网络对输入代码进行编码, 比较编码向量, 然后对克隆和非克隆做出最终的预测. 为提高代码表征能力, 本文采用上述两种预训练策略对AttBiLSTM的参数进行预训练, 然后使用少量的代码克隆以及非克隆训练样本 在代码克隆检测任务上对模型进行微调.

我们分别在BigCloneBench (BCB)数据集^[7]和OJClone^[20]上进行了实验来评估提出方法的有效性. BCB数据集中包含超过800万个Ⅳ型克隆对, 同时也有标签不平衡问题^[19]. OJClone数据集由相同问题的答案代码片段集合构成, 同一个问题的不同答案代码片段互为克隆对, 不同问题的答案代码片段互为非克隆对. 同时, 我们采用F-measure和AUC分数来衡量模型性能. 实验结果表明, 本文提出的两种预训练策略都是有效的, 两者的结合可以进一步提高模型的性能. 最后, 我们在BCB中选取了100个克隆对和100个非克隆对训练模型, 与现有的有监督学习方法在数百万个训练样本上训练的结果相比, 可以达到相似甚至更好的克隆检测效果( F-measure值大于96%). 在OJClone中选择了200个克隆对和200个非克隆对进行训练, 同样也可以达到较好的效果(F-measure值大于96%).

2 相关工作

代码克隆检测是软件工程中的一个重要课题, 大量研究者对该问题进行了研究^{[5-8, 11, 12, 17-19]}. 代码克隆检测任务可以分成两个阶段进行, 即对待检测代码片段的表示, 以及在该表示上进行代码相似度度量. 因此代码表示是代码克隆检测的关键, 代码预处理的粒度也决定了检测方法的适用范围和准确度. 基于对代码表示的不同将克隆检测方法分为4类: 基于度量^[16,18] , 基于token^{[12,14,15,24]}, 基于树或图的表示^{[9,13,17,25,26]}.

在基于度量的方法中, 用度量值来衡量以源代码作为输入的代码克隆. 对于函数或类等语法单元, 计算语句度量值, 然后比较这些度量值, 如果两个语法单元具有相同或相似的度量值, 则可以认为它们是克隆对. Svajlenko等^[27]介绍了CloneWorks, 在进行克隆检测之前为用户提供了完整的源代码表示形式, 之后的克隆检测通过经过修改的Jaccard相似度进行, 如果一对代码片段满足给定的最小的阈值, 则判断为克隆对. Sudhamani等人^[28]提出了一种检测克隆的方法. 将源代码作为输入, 同时自定义公式, 根据公式度量相似性, 对K=2的相似值采用K均值聚类进行分组, 该方法对部分类型的克隆检测效果较好. Haque等人^[29]提出将代码划分为多个函数或模块来检测来自不同输入源代码的代码克隆. Ragkhitwetsagul等人^[30]提出了一种基于图像的克隆检测方法, 将Java源文件作为数据集, 以PNG图像为中间状态, 然后利用Jaccard相似性进行克隆检测. 结果表明, 该方法可以较好的识别出Ⅰ型、Ⅱ型和Ⅲ型克隆. Sudhamani等人^[31]使用结构控制语句解决结构相似性检测. 为此, 相似性检测使用C/ C++, Java文件为数据集和自定义公式. 这种方法可以有效地检测出结构相似的克隆. 基于度量的方法一般以源代码作为输入, 或者在源代码的基础上进行一些预处理, 根据预处理之后的代码之间的距离与设定的阈值比较判断是否为代码克隆, 虽然这种方法并不复杂, 但受限于在源代码上提取的度量信息, 只能检测Ⅰ型和Ⅱ型代码克隆; 另一方面, 只提取源代码的文本特征, 忽略了代码之间的结构和语义信息, 检测准确度较低, 且检测复杂度随源代码的长度增加而增大^[1].

程序也可以被表示成token序列或词的集合进行代码克隆检测^[12,24], 基于token的方法是在词法的基础上进行检测, 这些方法包括词法分析和克隆检测两个步骤. 它们在词法分析器的解析之后将目标源代码转换为一系列tokens. 扫描token序列以找到token的重复子序列, 最后, 表示重复子序列的原始代码片段将作为克隆返回. Wang等^[15]开发了基于token的克隆检测器CCAligner. 它使用C、Java文件作为数据集, 识别Ⅰ型、Ⅱ型和Ⅲ型克隆. Yuki等人^[32]提出了一种检测多粒度代码克隆的技术, 并使用Smith-Waterman算法来识别相同的哈希序列. 该方法可以检测Ⅰ型、Ⅱ型和Ⅲ型克隆. Semura等人^[33]开发了另一种克隆检测工具CCFinderSW. 不同于只能检测特定语言的代码克隆检测工具, 它还提供了按需添加语言的扩展机制, 并在其中发现了Ⅰ型和Ⅱ型克隆. Li等人^[18]提出了一种基于深度学习的克隆检测方法CCLearner. 这种方法将IJaDataset转换为token, 并基于深度学习模型进行克隆检测. 基于token的检测方法将源代码拆分为token序列, 根据序列进行代码克隆检测. 这种方法不需要提取复杂的特征, 可以在词汇层面获取到代码片段的信息, 但是将源代码表示成token序列, 也丧失了代码在整体结构层面的信息, 同时, 如果对代码片段进行调换语句顺序、增加或删除操作, 将会在很大程度上改变token序列, 从而使得检测方法无效.

近年来, 基于树的克隆检测方法受到广泛关注, 并取得了较好的检测效果. 在基于树的克隆检测技术中, 程序首先被转换成抽象语法树(AST), 然后在AST上进行编码表示、或通过子树匹配等方法衡量相似性. Gao等人^[19]遍历AST的中间节点, 并利用LSTM学习AST表示, 进行代码克隆检测. TBCCD^[10]提出了一种基于树的卷积神经网络检测语义克隆的新方法, 充分利用了代码片段的结构信息, 通过从AST中获得代码片段的结构信息和从token中获得词汇信息, 同时充分发挥了神经网络检测代码克隆的能力, 该方法可以有效检测出Ⅳ型代码克隆. TBCAA^[34]将API调用序列融合到AST中以弥补由于方法调用提取而导致的语义缺失, 用API增强的AST, 使用基于树的卷积方法作为代码表示学习的基本模块, 可以有效识别语义克隆. Yang等人^[35]提出了一种基于函数的代码克隆检测技术. 首先从函数中创建AST, 将其转换为新的树状结构, 然后利用Smith-Waterman算法获得函数之间的相似度评分. CDLH^[9]使用Word2Vec模型^[36]来学习token嵌入来捕获词法信息, 基于LSTM模型^[37]来训练语法树(AST), 将token组合成二进制向量来表示一个代码片段, 但是此方法没有充分利用AST中的结构信息. 只使用token信息的SourcererCC^[24]和只使用结构信息的Deckard^[13]都无法准确检测到Ⅳ型克隆. ASTNN^[38]将每个大型AST拆分为子语法树, 并通过捕获语句的词汇和语法知识将子语法树编码为向量. Wang等人^[39]构建了一种称为流增强抽象语法树(FA-AST)的程序图表示, 用显式控制和数据流边扩充原始AST构成FA-AST, 然后在FA-AST上应用两种不同类型的图神经网络(GNN)来表征并度量代码对的相似性. 曾杰等人^[40]首先抽取词法单元的特征表示, 然后分析不同单词的语义相似性, 抽取AST, 为叶子节点赋予对应单词的特征表示, 将抽象语法树转化为特征向量树, 并将其编码为定长向量, 根据向量的相似与否判断是否为代码克隆.

基于图的克隆检测首先将代码片段转化为程序依赖图(PDG)等, 然后对PDG的结构是否相似做出判断. Zou等人^[41]提出了一种基于PDG的采用图核的编码克隆检测器CCGraph, 首先对PDG的结构进行规范化, 设计了两阶段的过滤方法来度量代码的特征向量, 然后采用基于改进的Weisfeiler-Lehman图核的近似图匹配算法检测代码克隆. Feng等人^[42]提出了一个连接两个递归自动编码器和一个比较网络的孪生网络进行代码克隆检测, 设计无权值递归自动编码器学习代码表示, 然后利用比较网络进行相似性评估, 充分利用了词汇、语义和结构信息, 可以达到很高的精度. Yuan等人^[43]提出了一种新的语义克隆检测方法, 使用控制流图(CFG)作为程序方法的中间表示. 将语音识别领域的动态时间规整(DTW)算法与两种深度神经网络模型(双向RNN自编码器和图卷积网络(GCN))相结合, 从局部到全局检测语义层克隆. 基于树或图的比较方法需要生成抽象语法树、或者程序依赖图等, 这种方法可以捕获到代码的结构信息和语义, 但是基于树或图的比较时间复杂度和效率复杂度相比较基于度量和基于token的方法要高得多.

现有基于监督学习的方法使用人工标注的数据集例如BigCloneBench^[7]和OJClone^[20]进行监督学习. 这些模型实现了很高的性能, 但需要大规模的人工标注训练数据集, 人工标注代码克隆数据集, 特别是Ⅳ型克隆的代价较高. 近期, 大规模语料预训练模型在自然语言处理领域取得了良好进展. 在程序语言的表征学习上, 大规模预训练模型也受到了关注. 如CodeBERT^[44]等基于大规模代码库的预训练模型的发布, 使得代码表征能力得到了极大提升. 在代码克隆相关领域, 也有通过预训练模型提升代码表征的方法被提出. InferCode^[45]将自然语言处理中的自监督学习思想引入到代码的抽象语法树的表示中, 通过预测从AST上下文中自动识别的子树来训练代码表示, AST的子树被视为训练代码的标签, 无需人工标记工作, 该方法可以用于代码克隆检测. code2vec^[46]首先提取出代码片段的抽象语法树, 从其中提取不同的路径, 用路径中每个节点的词向量连接成该路径的向量, 对于每个路径按照权重加权组成最终向量, 该向量就是对应方法名字的向量. 然而这些预训练模型通常参数规模庞大, 训练及使用代价高.

基于对现有方法的总结比较, 我们需要改进基于度量和基于token方法获得信息不全面, 基于图和树的方法复杂度高, 以及基于大规模预训练语料的方法标注、训练代价大的问题. 克隆检测不仅需要提取出词汇级别的信息, 更需要结构和语义级别的信息来提高检测准确度, 同时对计算效率的要求高, 这导致目前最先进的句子匹配模型(包括输入句子对之间)大多不适用. 通过密切相关的任务进行预训练的想法已经广泛应用于自然语言处理^[47-49]. 在本工作中, 我们应用该思想进行轻量级的语义预训练, 以提升代码表征能力.

3 预训练增强的代码克隆检测方法

本节将详细介绍本文提出的方法. 首先, 概括模型整体结构, 并详细介绍模型的3个主要组成部分, 即嵌入层、代码表示层及分类层. 然后着重介绍两种提升代码表征的增强方式, 即子词丰富和函数名预测.

本文主要关注IV型代码克隆检测问题, 将其定义为一个二分类任务. 给定一对代码片段C^A和C^B, 如果(C^A, C^B)是一个IV型克隆对, 则标注1, 如果它们不是IV型克隆对, 则标注0.

3.1 方法整体结构

本文提出的方法整体结构如图2所示, 首先, 在嵌入层对获得的数据集进行分词处理. token是代码理解的基本单位, 类似于NLP领域句子理解中的单词. 因此, 在神经网络中, token在代码表示中的作用与单词在句子编码中的作用相同. token嵌入通过Word2Vec模型进行预训练, 用从开源代码库(如Github)中收集的代码片段语料库替换输入语料库, 将语料中的每个函数分割成token序列( $ {w}_{1}^{A} $ ,… $ {, w}_{m}^{A} $ 和 $ {w}_{1}^{B} $ ,… $ {, w}_{n}^{B} $ ), 然后使用token序列对Word2Vec模型进行训练, 以获得每个token的向量, 表示为( $ {x}_{1}^{A} $ ,… $ {, x}_{m}^{A} $ 和 $ {x}_{1}^{B} $ ,…, $ {x}_{n}^{B} $ ). 在代码表示层将向量表示的token序列作为输入, 使用BiLSTM进行编码, 得到 ${h}_{1}^{A{\rm {BiLSTM}}}$ ,…, ${h}_{m}^{A{\rm {BiLSTM}}}$ 和 ${h}_{1}^{B{\rm {BiLSTM}}}$ ,…, ${h}_{n}^{B{\rm {BiLSTM}}}$ , 通过self-attention层对用向量序列表示的函数进行总结, 得到 ${h}^{A{\rm {CODE}}}$ 和 ${h}^{B{\rm {CODE}}}$ . 在分类层, 计算 ${h}^{A{\rm {CODE}}}$ 和 ${h}^{B{\rm {CODE}}}$ 的距离, 判定两个函数是否为克隆函数. 因为在检测一对代码片段时, 对两个代码片段的编码方式完全相同, 因此我们使用Siamese模型结构, 即对两个代码片段的嵌入层预训练过程以及代码表示层的BiLSTM网络参数都完全相同. 为了方便阅读, 以下描述以一个代码片段的处理过程为例.

3.1.1 嵌入层

首先, 将每一个代码片段都分割成token序列. 对于片段 $ {C}^{A} $ , 经分割后得到 $ {w}_{1}^{A} $ … $ {w}_{m}^{A} $ , (m为代码片段A的长度), 然后在矩阵 $ {\boldsymbol{E}}_{{w}} $ 中查找每个token对应的向量, 将所有的tokens $ {w}_{i}^{A} $ (i∈[1, m])转化为密集向量. 该查找矩阵已经用代码语料库进行预训练, 查找矩阵 $ {\boldsymbol{E}}_{{w}} $ 在模型中是固定的. 查找过程可表示为:

$ x_i^A = lookup(w_i^A, {{\boldsymbol{E}}_{{w}}}) $

(1)

经过嵌入层的预训练后, $ {C}^{A} $ 生成了序列 $ {x}_{1}^{A} $ … $ {x}_{m}^{A} $ . 对于代码片段 $ {C}^{B} $ , 可以用同样的嵌入方式得到对token序列 $ {w}_{1}^{B} $ … $ {w}_{n}^{B} $ (n为代码片段B的长度)的向量表示 $ {x}_{1}^{B} $ … $ {x}_{n}^{B} $ .

3.1.2 代码表示层

AttBiLSTM神经网络整合token嵌入形式的输入, 它由两部分组成: 双向长短时记忆部分(BiLSTM)和自注意部分. 前者的目的是获得一个高级上下文token表示序列, 后者的目的是总结序列级的输入特征, 并将每个代码片段缩减为一个单一的密集向量. 处理过程分为如下两个步骤:

$ \begin{aligned} h_1^{A{\rm{BiLSTM}}}, \ldots, h_m^{A{\rm{BiLSTM}}} = {\rm{BiLSTM}}(x_1^A, \ldots, x_m^A), \\ {h^{A{\rm {CODE}}}} = {\textit{Self-Attention}}(h_1^{A{\rm{BiLSTM}}}, \ldots, h_m^{A{\rm{BiLSTM}}}) \end{aligned} $

(2)

经过嵌入层的预训练后, 每一个token $ {w}_{i}^{A} $ 都被转化为了一个密集向量 $ {x}_{i}^{A} $ , 它们经过BiLSTM的编码后, 生成了 ${h}_{i}^{A{\rm {BiLSTM}}}$ , 然后经过self-attention层的总结后, 生成了 ${h}^{A{\rm {CODE}}}$ , ${h}^{A{\rm {CODE}}}$ 是 $ {C}^{A} $ 的最终表示.

同样, 我们可以用相同的计算流以 $ {x}_{1}^{B} $ … $ {x}_{n}^{B} $ 作为输入为 $ {C}^{B} $ 计算 ${h}^{B{\rm {CODE}}}$ . 在Siamese BiLSTM中, 神经网络BiLSTM(·)和Self-Attention(·)中有许多模型参数, $ {C}^{A} $ 和 $ {C}^{B} $ 共享BiLSTM和self-attention的模型参数.

3.1.3 分类层

当 ${h}^{A{\rm {CODE}}}$ 和 ${h}^{B{\rm {CODE}}}$ 被训练好后, 我们就可以通过以下过程计算克隆和非克隆的得分:

$ \begin{aligned}[b] {h^{{\rm {DIFF}}}} = ||{h^{A{\rm{CODE}}}} - {h^{B{\rm{CODE}}}}||, \hfill \;\;O = [{O_0}, {O_1}] = {W_{{\rm {CLONE}}}}{h^{{\rm {DIFF}}}} \end{aligned} $

(3)

其中, ${h}^{A{\rm {CODE}}}$ 与 ${h}^{B{\rm {CODE}}}$ 的向量维度相同, ${h}^{\rm {DIFF}}$ 是由它们对应位置相减得到的向量, 也是分类的最终特征, 反映了两个代码片段之间的语义差别, $ {O}_{0} $ 和 $ {O}_{1} $ 分别表示这两段代码为克隆与非克隆的概率, ${W}_{\rm {CLONE}}$ 是分类参数. 本工作采用有监督模型的交叉熵损失训练或微调模型参数:

$ loss = - \log {p_y} = \log \frac{{{{\rm e}^{{O_y}}}}}{{{{\rm e}^{{O_0}}} + {{\rm e}^{{O_1}}}}} $

(4)

其中, y代表输入为克隆或非克隆的真实标签. 训练的目标是最小化所有训练样例的累计损失, 通过不断地缩小累计损失来更新 $ {O}_{0} $ 和 $ {O}_{1} $ 的值, 最后不断更新 ${W}_{\rm{CLONE}}$ , 使模型达到最好的分类效果.

3.2 子词丰富

与自然语言中的单词相比, 编程语言中的token可以以更灵活和多样化的方式命名. 除程序语言关键字外, 标识符可以被命名为任何符合词法规则的字符串. 例如, 几乎所有合法的英语单词(如“read”和“length”), 子词(如“buf”和“dest”), 以及单词组合(如“sourceChannel”)都是合法的程序语言tokens. 因此, 编程语言tokens的数量可能是无限大的. 另一方面, 编程语言预训练语料库的规模比自然语言小得多, 因为我们只能在少数的开源代码库中获得语料. 上述两个问题可能导致token表示中严重的OOV问题. 表示学习中的OOV问题已经在自然语言处理领域得到了广泛的研究. 典型的方法包括纯字符级模型, 如Elmo^[50], ngram子词模型^[22]和基于字节对编码的子词模型^[51,52]. 我们针对代码表示中的OOV问题进行了检测, 发现在BCB数据集中OOV比率高达62.68%, 在OJClone数据集中OOV比率达到了16.82%.

为了解决上面提到的两个问题, 我们引入了ngram子词来丰富词语表示, 采用基于ngram的子词组合的token嵌入来解决token表示中的OOV问题. 对于在词表中预先训练过的单词, 直接利用预先训练的嵌入, 在矩阵 $ {\mathit{E}}_{\mathit{w}} $ 中查找向量作为token表示. 而对于OOV单词, 通过其ngram来组成单词表示. 该预处理方法是由Bojanowski等人^[22]首次提出的对标准Word2Vec模型的简单扩展. 本文基于子词丰富的思想解决OOV问题, 以提升代码克隆检测模型的准确率.

为了方便, 本文不区分单词和token, 因为token可以被视为编程语言中的单词. Word2Vec的基本思想是利用语言建模来学习词(tokens)嵌入. Skip-Gram模型通过预测给定单词的上下文单词来学习单词表示. 给定一个单词序列 $ {w}_{1} $ ,…, $ {w}_{i} $ ,…, $ {w}_{n} $ , 和一个源单词 $ {w}_{i} $ , 上下文窗口大小c, 模型预测它周围的单词 $ {w}_{i-c} $ ,…, $ {w}_{i-1} $ ,…, $ {w}_{i+1} $ ,…, $ {w}_{i+c} $ . 这个过程是一个典型的分类问题, 标签数量与词表大小相同. 尽管分类标签数量很大, 我们可以通过负采样来控制. 模型的目标交叉熵损失函数定义为:

$ loss = - \sum\limits_C {\log p({w_j}|{w_i})} $

(5)

在上述公式中, $ C=2c $ , $ {w}_{j} $ 是 $ {w}_{i} $ 周围单词中的一个. Skip-Gram模型使用一个简单的网络来计算公式(5). 网络有两个查找矩阵 $ {E}_{w} $ 和 $ {E}_{f} $ , 它们都是随机初始化的模型参数, 然后在训练过程中根据目标函数进行微调. 在大规模原始语料上进行训练后, 最终的嵌入矩阵 $ {\mathit{E}}_{\mathit{w}} $ 被输入到等式(1)中的克隆检测模型中.

给出一对源词和上下文单词( $ {w}_{i} $ , $ {w}_{j} $ ), 可以从 $ {\mathit{E}}_{\mathit{w}} $ 中得到源词嵌入 $ {v}_{j} $ , 从 $ {\mathit{E}}_{\mathit{f}} $ 中得到上下文词嵌入 $ {u}_{i} $ . 接下来, ( $ {w}_{i} $ , $ {w}_{j} $ )的相关分数由 $ {u}_{i} $ 和 $ {v}_{j} $ 的数积得到 (T代表转置).

$ s({w_i}, {w_j}) = u_i^{\rm T}{v_j} $

(6)

分类概率的计算公式为:

$ p({w_i}|{w_j}) = \frac{{{{\rm e}^{s({w_i}, {w_j})}}}}{{\displaystyle\sum\nolimits_* {{{\rm e}^{s({w_i}, *)}}} }} $

(7)

其中, *代表任何其他的被随机负采样的词, 分母可以看作是概率计算的归一化因子.

对于子词组合, 唯一的区别是源词 $ {w}_{i} $ 的表示. 除了 $ {w}_{i} $ 的全词嵌入外, 我们还利用了一种由 $ {w}_{i} $ 的ngram合成表示. 例如, 对于单词“source”, 它的4个字符组合包括“sour”“ourc”和“urce”. 我们学习这些单词的嵌入, 然后由它们来组成OOV单词嵌入.

在预训练过程中, 源词 $ {w}_{i} $ 以如下方式被计算:

$ {v_i} = {v_{{w_i}}} + \frac{1}{Q}\sum\nolimits_{i = 1}^Q {{v_{ngram({w_i})}}} $

(8)

$ ngram(.) $ 包括所有可能的限于固定长度(本文中为3到6)范围的ngram子词, $ Q $ 是在 $ {w}_{i} $ 中ngram的总数. 在整合之后, 全词和ngram子词的嵌入可以共同学习.

在探索过程中, 对于完整的单词, 我们通过查阅 $ {\mathit{E}}_{\mathit{w}} $ 直接获得它们的嵌入. 而对于OOV单词, 我们使用公式(8)中被包含的ngram子词获得它们的嵌入. 例如, 对于OOV单词“sourceChannel”, 它的嵌入可以通过平均单词中包含的所有ngram嵌入来计算.

3.3 函数名预测

在进行Ⅳ型代码克隆检测时, 最直观的方法是使用经过标注的代码克隆对来训练神经网络, 在给出大量的代码片段对以及标签(1和0分别代表克隆和非克隆)后, 通过训练深度学习模型来区分克隆与非克隆代码片段. 然而训练深度神经网络需要大量经过高质量标注的数据, 标注工作不仅费时而且需要很多专业人员. 为了解决标注的高成本问题, 我们设计了合理的预训练任务, 使用函数名预测辅助模型学习程序语义信息. 函数名预测任务与面向语义的IV型克隆检测任务高度相关. IV型代码克隆检测判断两个代码片段是否语义相似. 对于没有任何拼写错误, 变量以及函数名符合命名规范的代码, 其函数名通常是对函数体语义的描述总结, 可以反映函数编写者的编程意图, 也可以反映函数体的语义信息, 因此本工作中我们选取函数名预测任务作为辅助预训练任务使深度学习模型的特征表示层学习到代码片段的语义, 进而通过少量有标注的代码克隆、非克隆数据微调模型参数, 达到较好的克隆检测效果.

函数名预测形式上类似于Skip-Gram模型. 给定一对代码片段 $ {C}^{A} $ 和它的函数名 $ {N}^{B} $ , 我们首先计算它们的向量表示. 如图2所示, 对于函数体表示 $ {C}^{A} $ , 利用与代码克隆检测模型相同的网络结构表示代码, 可以得到 ${h}^{A{\rm {CODE}}}$ . 对于函数名表示, 我们首先用几个简单的规则将函数名分割成一系列有意义的单词, 例如“copyFileUsingStream”被分割成“copy File Using Stream”, 然后在单词序列上使用一个简单的平均池化网络来获得其表示. 假设 $ {N}^{B} $ = $ {w}_{1} $ , …, $ { w}_{l} $ , 它的向量表示以如下方式计算:

$ h_i^{\rm {NAME}} = \frac{{\displaystyle\sum\nolimits_{k = 1}^l {lookup({w_k}, {{\boldsymbol{E}}_{{\text{natural}}}})} }}{l} $

(9)

查找矩阵 ${\boldsymbol{E}}_{\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{l}}$ 是自然语言词嵌入的集合. 这里我们直接使用一种已公开发布的Glove词嵌入^[53]. 在本文中, 词嵌入是固定的, 所以这部分没有任何模型参数需要训练.

接下来, 我们可以通过它们的表示计算 $ {C}^{A} $ 和 $ {N}^{B} $ 的相关分数:

$ s({C^A}, {N^B}) = {({h^{A{\rm {CODE}}}})^{\rm T}}h_i^{\rm{NAME}} $

(10)

在给定 $ {C}^{A} $ 条件下, $ {N}^{B} $ 的概率以如下方式计算:

$ p({N^B}|{C^A}) = \frac{{{{\rm e}^{s({C^A}, {N^B})}}}}{{\displaystyle\sum\nolimits_* {{{\rm e}^{s({C^A}, {N^*})}}} }} $

(11)

相关分数和概率公式分别与Skip-Gram模型的公式(6)和公式(7)高度相似. 因为分类标签的数量巨大(与合法的函数名总数相同), 在这里, 同样应用负采样方法进行有效的概率计算. 例如, 我们可以抽样5个函数名来近似分母, 这个方法大大降低了计算成本.

最后, 我们使用下面的损失函数(还有交叉熵损失)作为训练目标:

$ loss = - p({N^B}|{C^A}) $

(12)

克隆检测模型中的参数与函数名预测模型中的参数完全相同. 模型预训练的效果来源于大规模的函数名预测任务, 因为构建这样的语料库不需要人工标注. 我们最终目标是预训练AttBiLSTM参数, 将预训练得到的参数应用在克隆检测模型中. 我们简单地使用预训练的网络参数来初始化神经克隆检测模型的AttBiLSTM部分, 然后根据克隆检测目标对这些参数进行调整. 该过程类似于CodeBERT, 但区别于CodeBERT, 本文采用相似任务进行预训练, 在训练数据集以及模型参数上, 较CodeBERT都更为轻量级.

4 实　验 4.1 实验设置

本工作所有实验采用的服务器的配置为2 Intel Xeon Platinum 8260 CPU @2.30 GHz, 8 NVIDIA GeForce RTX2080 Ti GPU (每块显卡内存为11 GB), 512 GB RAM, PyTorch版本为1.8.0.

4.1.1 克隆数据集

本实验采用BigCloneBench数据集^[7]来评估本文提出方法的有效性. 该数据集是一个被广泛使用的Java代码克隆检测的基准^[9,18], 它包含8 654 345个标注好的真实代码克隆对, 其中8 219 320个为Ⅳ型克隆对(占比95.00%), 279 032个为非克隆对. 训练集为随机采样的100个IV型克隆对和100个非克隆对, 其他的IV型克隆对和非克隆对用于测试. 为了减少单一数据集对实验结果造成的影响, 我们还使用OJClone数据集^[20]对我们的方法进行评估. 该数据集是由OnlineJudge^[20]上的编程问题的正确答案组成, 由于每个问题有多种正确答案, 同一问题两种不同的答案可以看作一对克隆对, 不同问题的答案可以作为非克隆对.

4.1.2 预训练语料构造

对于BigCloneBench, 为了预训练token嵌入和代码表示, 我们从GitHub收集了329个高质量的Java项目(按照获得Star的数量排序). 总共有296 300个文件和2 097 213个方法. 经过处理, 语料中包含超过1.9亿个tokens, 其中有2 489 036个不同的tokens, 构成了词表. 在BCB数据集中, 仅有928 908个token可以在该预训练得到的词表中搜到, 这导致了BigCloneBench上的OOV比率为62.68%.

对于OJClone数据集, 我们用同样的思路选取Github上Star数量较高的C语言项目, 提取项目中所有C语言函数的函数名以及函数体, 使用这些语料信息进行预训练. 但排名较高的C语言项目多数为底层功能开发, 如操作系统的部分实现, 其代码实现逻辑及命名方式等与OJClone数据集中的代码片段(变量名多为单个字符)有较大区别, 这导致无法得到OJClone数据集中token的准确向量表示. 为了验证函数名预测预训练任务的有效性, 我们尝试使用OJClone数据集中的部分数据进行预训练, 我们在15个问题的每个问题中随机抽取400个答案, 将其作为预训练任务中的函数体. 因为OJClone数据集中并没有每个问题的描述, 且答案代码片段中的函数名全部为main, 无法提供准确的语义信息. 为了得到对应这些函数体的函数名, 两位志愿者通过阅读代码, 根据代码语义为每个问题标注函数命名. 对每一个问题, 随机抽取100个答案, 两人阅读这些答案代码片段以后, 分别根据代码片段解决的问题给出函数名, 并通过讨论确定每个代码片段对应的函数名. 这15个问题的函数名包括BubbleSort, getDays等, 该标注方法最大程度地保证了函数名的准确性, 最终得到了6 000个正样本以及6000×5个负样本. 在OJClone数据集中我们所使用的预训练语料共有59 311个不同的tokens, 而在整个数据集中有71 306个不同的tokens, OOV比率为16.82%.

4.1.3 参数设置

参数设置包括token嵌入预训练, 函数名预测训练和代码克隆检测等几个训练任务的超参数. 对于token嵌入预训练, 我们直接使用作者发布的fastText工具^[22], 其中向量维度设置为100, 其他的超参数为该工具默认值. 对于代码表示的BiLSTM网络结构, 所有隐藏层的维度大小设置为300. 在函数名预测和代码克隆检测中, 输入嵌入层采用dropout^[43], LSTM隐藏层采用Adam算法^[46]进行参数优化, 初始学习率为5×10⁻⁴, 梯度剪切阈值为5, mini-batch大小为32. 我们将训练周期和负采样的大小分别设置为20和5, 对于代码克隆检测模型训练epoch设置为100.

对于本文采用给的对比方法, 我们采用原文中报告的参数设置. 对于TBCCD, 我们采用其网站上开源的数据集划分方式, 即将BCB数据集按照4:1:1的比例划分为训练集、测试集和验证集. 卷积核大小为600, 滑动窗口大小为2, 全连接层的维度为50, 使用随机梯度下降进行优化. 训练一共进行10轮, batch size设置为1. 对于ASTNN, 将BCB数据集按照4:1:1的比例划分为训练集、测试集和验证集, 嵌入大小为128, ST-tree和双向GRU的维度为100, 使用AdaMax方法进行优化. 训练过程一共进行了2轮, batch size为64, 克隆检测的阈值设置为0.5, 学习率为0.002.

4.1.4 评估指标

在我们的测试中, 克隆和非克隆的比例是极不平衡的, 我们对于克隆和非克隆独立报告了精度(P), 召回率(R)和相应的F-measure值, 并且在两种类型上使用平均F-measure值( ${F}_{\rm {avg}}$ )作为主要度量依据. 与总体精度相比 ${F}_{\rm {avg}}$ 更合适. 以克隆对的计算为例, P, R, F-measure分别以如下方式计算:

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

(13)

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

(14)

$ {\textit{F-measure}} = \frac{{2PR}}{{(P + R)}} $

(15)

其中, TP, FP, FN分别为检测出的克隆对中为真实克隆对的数量, 检测出的克隆对中并不是克隆对的数量以及真实克隆对中未被检测出来的数量. 除此之外, 我们也报告了AUC值, 因为克隆与非克隆的边界可以根据实际需要手动重置. 为尽量消除使用随机种子初始化模型参数对克隆检测模型的影响, 我们在每个配置上运行了5次实验, 并计算其平均值.

4.2 实验结果

为了找到可以平衡准确率以及时间成本的训练集大小, 我们比较了不同训练数据集大小的实验效果. 为了探究预训练数据集大小对实验结果的影响, 我们在C语言预训练数据集上进行了实验, 比较了不同数据集大小对实验结果的影响. 为了比较两种预训练方法对代码克隆任务的提升效果, 实验设计在基准模型的基础上分别增加了子词丰富、函数名预测任务, 以及同时增加两个预训练任务. 为了与现有的主流方法进行比较, 我们选择了两个当前克隆检测效果最好的模型, 即TBCCD和ASTNN进行比较. 同时我们也对模型的效率进行了测试.

4.2.1 训练集大小对实验结果的影响

首先, 我们在克隆检测模型中检查训练规模的影响, 因为我们的主要目的是使用增强的代码表示来减少人工标注的需求. 我们在实验中使用的克隆对和非克隆对的比例均为1:1, 在比较过程中使用的克隆对的数量分别是20, 50, 100, 200, 500, 1 000. 表1展示了随着训练数据的增加, F值的具体数据和增加的趋势. 可以看到, 训练规模越大, F值表现越好. 当训练量达到100时, 增加训练样本数所得到的效果提升非常不明显. 在后续实验中, 我们选择了数据集中克隆对大小为100的设置.

我们同样在OJClone数据集上进行了训练数据大小对实验结果影响的比较实验, 结果如表2所示: 逐渐将训练数据增加到1 000个时, F_clone值逐渐增加到97.58%, 但是从表中可以观察到, 到训练数据增加到200条时, F_clone值已经达到了96.47%, 并且当逐渐增加数据时, 效果提升地较为缓慢, 因此以下关于OJClone的实验我们均采用200对作为训练集的大小(200对克隆代码对和200对非克隆代码对).

4.2.2 预训练数据集大小对实验结果的影响

为了探究预训练语料的构造规模和训练情况对BCB数据集结果的影响, 我们随机选取了20万、50万、100万、200万对克隆代码片段对模型进行预训练, 实验结果如表3所示.

表3表明随着预训练数据大小的增加, 最终结果也呈上升趋势, 为了平衡训练时间与训练效果, 最终选择数据集大小为200万对的设置.

我们同样在OJClone上进行了预训练数据集大小对实验结果影响的实验. 我们分别在15个问题中选择100, 200, 300个答案, 按照正负样本1:5的比例构造预训练数据集对模型进行函数名预测的预训练, 实验结果如表4所示.

从表4可以看出, 随着预训练数据集的增大, 克隆检测任务的F值和AUC值都会呈现上升趋势, 即对代码克隆的检测效果会不断增强. 考虑到需要预留出足够的答案样本用来构造训练集和测试集, 我们选择400作为C语言实验中的预训练数据集大小.

4.2.3 不同增强效果比较

对于BigCloneBench数据集, 我们从训练池中选取100个克隆语料和100个非克隆语料作为主要设置, 目的是在最小化训练语料规模的同时达到良好的性能. 表5展示了结果. 我们报告了克隆和非克隆的P, R和F得分, 并报告了F得分的平均值和AUC值. Baseline一行表示使用标准的基于全词嵌入的模型, +子词丰富一行表示使用ngram子词丰富嵌入的方法, +函数名预测表示在函数名预测任务上使用AttBiLSTM预训练参数的方法. 最后的模型整合了子词丰富和函数名预测预训练两种提升方法.

如表5所示, 可以发现两种提升方法都是高度有效的. 对于克隆对的F-score, 两种预训练方法可以分别获得9.72和10.58的改进效果. 对于non-clone的F-score, 提升结果分别为23.67和29.11. +函数名预测的预训练结果好于+子词丰富的结果. 当同时采用两种方法时, 可以获得更好的效果. F_avg和AUC在4个模型上的效果变化也与F_clone和F_non-clone相同.

对于OJClone数据集, 本实验的训练集的构造方式为选择每个问题的100个与预训练数据集不同的答案, 在这些答案中随机选择200对克隆代码对和200对非克隆代码对组成训练集, 之所以选择200作为训练集大小, 是因为经过对上文中关于训练集大小的探究实验后, 我们发现训练集大小为200可以最大程度地兼顾代码克隆检测效果和实验过程的时间成本. 测试集的大小为克隆对与非克隆对各15万对, 构造方式为在上述100个答案组成的集合中去除了训练集的200对克隆与200对非克隆后进行随机挑选. 测试结果如表6.

我们注意到在BCB数据集上所有的4个模型上F_non-clone的值都要显著低于F_clone的值, 而在OJClone数据集上F_non-clone的值与F_clone的值却相差不多, 主要原因是在BCB数据集上的克隆与非克隆之间存在严重的数据不平衡(接近30:1). 非克隆的精确值偏低, 是由于部分克隆分类错误造成的. 虽然百分比值很小, 但它大大增加了预测的非克隆数量. 这也是我们不使用精确度作为度量标准的原因.

在表5和表6中, 可以看到在BCB数据集和OJClone数据集上我们最终模型(Final)的效果要远好于Baseline, 这得益于我们提出的两种预训练策略. 通过对两个数据集上的实验效果以及在实验过程的案例进行分析, 我们初步总结出了两种预训练策略分别对应的适用范围如下所示.

(1)子词丰富

(a)对于变量名由较为完整的英文单词组合构成的情况尤为有效. 例如在测试过程中出现了变量名“cardSlot”, 但在训练过程中并未见过该变量名, 因而其是OOV词汇. 因为字典中有“card”和“slot”两个词的向量, 子词丰富方法可以通过组合这两个单词的向量来表示“cardSlot”.

(b)对于例如由单个字母构成的没有任何语意信息的变量名, 例如图3中的(来自OJClone数据集的一个代码片段)变量名n, f等, 子词丰富的效果较差. 实际上OJClone数据集中有较多这种单个字母作为变量名的用法, 这也是OJClone上子词丰富策略对最终分类结果提升效果没有在BCB上高的原因之一.

(2)函数名预测

对于两个功能相同, 但是在语法上相似度较低的代码片段尤为有效, 例如图4中的两个代码段, 均为拷贝文件功能, 但是在代码实现上差距较大. 函数名预测任务能很好的学习到代码片段的语义, 从而提高代码克隆检测的准确率.

4.2.4 与其他方法的比较

我们也将我们的模型与现有效果最优的方法进行了比较. 表7展示了比较结果. 我们列出了基本方法的结果和我们最终模型(即加子词丰富及预训练提升)的结果. TBCCD^[10]是基于抽象语法树的检测方法, 但是还利用了卷积树. ASTNN^[38]将AST拆分为子树进行检测. 这两个模型使用来自BigCloneBench的800万个实例作为训练语料库. 我们使用原文的设置对TBCCD和ASTNN进行实验, 具体参数设置见第4.1.3节. 对于本文提出的方法, 仍采用100对克隆和100对非克隆进行训练.

在OJClone数据集上的TBCCD和ASTNN的两种方法的结果为原文中给出的结果, 从表7可以看出, 在BCB数据集上, 我们的效果好于上述两种方法, 而在OJClone数据集上, 我们的方法F值要优于ASTNN, 稍差于TBCCD. 但是我们的方法仅仅才用了400对标注克隆数据进行训练, 而TBCCD则采用了超过200万对标注数据, 总体上, 我们的方法对于标注的数据集稀缺的代码克隆检测任务是很有必要的.

4.2.5 效　率

表8展示了本文提出方法与对比方法TBCCD, ASTNN的时间开销对比. 本文提出方法的训练时间为27 min, 测试100对所需时间为0.024 s, 在这个过程中只需要100对克隆对和100对非克隆对的训练. TBCCD训练所需时间为2 640 min, 测试100对所需时间为1.36 s. ASTNN训练时间为9 360 min, 测试100对所需时间为12.62 s. 时间较长的原因为是在训练阶段及测试阶段, 都需要先将源代码表示成抽象语法树, 然而这个过程很耗时. 从结果中我们可以看到, 我们的方法测试时间仅为TBCCD的1.8%, ASTNN的0.19%. 本文函数名预测预训练任务训练时间为8 640 min. 该预训练任务无需人工干预, 且仅需进行一次. 因而对比人工标注大量代码克隆对的代价, 该预训练的代价可以接受.

4.2.6 抄袭检测应用

为了进一步验证本文方法的实际可行性, 我们将其应用于代码作业的抄袭检测. 实验样本为天津大学智算学部编译原理课程作业, 该作业要求学生实现C语言编译器中词法分析以及语法分析的功能. 由于作业编码语言多样, 包括C/C++, Python等, 我们选取10组用C/C++语言编码的作业作为检测目标.

首先将每一份作业代码按照函数进行拆分, 10份作业共得到123个函数, 6 298对代码对(每份作业的每一个函数与其他作业的一个函数形成一个代码对). 我们使用在OJClone数据集上训练好的模型对这些克隆片段进行预测, 并对预测结果为克隆的概率在80%以上的函数片段所在的作业进行全面的人工检查.

经过克隆检测模型的检测, 我们的方法预测出850对克隆, 召回率为96.30%, F1值为74.82%. 我们直接采用OJClone数据集上训练好的模型进行克隆检测, 由于: (1) OJClone数据集中的变量、函数等的命名与待检测代码有差距, OJClone数据集中的代码经常用单个字母, 如i, j, k等命名, 而作业数据集的命名较为规范, 因而子词丰富策略对作业数据集作用不明显; (2)我们未用作业代码片段微调检测模型; 因而检测结果准确率没有在OJClone数据集上测试的结果高. 两份作业之间最多包含4对克隆代码片段, 最少的为不包含克隆代码片段. 人工检查结果发现十组作业中并未有抄袭, 其出现克隆代码对的原因为在词法分析和语法分析的过程中, 部分功能或算法是固定的, 例如词法分析中判断该token是否为关键字和数字等, 语法分析中构建first集和follow集的算法等. 通过代码克隆检测模型的辅助, 我们仅需要人工检查8对作业, 减少了82%的工作量. 该应用案例证实了我们方法的实用性和有效性.

4.3 有效性威胁 4.3.1 内部威胁

本实验代码共由3部分组成: 数据的处理过程, 代码的表示过程以及最终的分类过程. 3部分的代码的主体逻辑都由作者自己实现. 代码实现中存在潜在的bug, 可能会影响方法的准确性. 为了降低该内部威胁, 代码中重要的实现部分逻辑由主要作者仔细检查, 并进行了充分的测试. 另外, 由于OJClone数据集中并没有给出可用的函数名, 为了进行函数名预测任务, 我们人工对函数进行命名, 为了避免命名错误或不准确等问题, 我们对每个问题至少阅读了100个答案并且经过所有作者的讨论之后, 最终确定了该问题所对应的函数名.

4.3.2 外部威胁

本实验调用了一些第三方库, 例如PyTorch等, 这些第三方库潜在的bug可能会对本工作的实验结果构成威胁. 为了降低该部分的威胁, 本工作选取被业界广泛使用的, 经过充分测试的第三方库函数.

4.3.3 构造威胁

数据集构造上, 在阅读了大量的论文之后, 我们决定使用大多数实验所采用的数据集BigCloneBench (BCB), 以保证与其他相关工作尽可能相同的实验设置. 为了尽量避免BCB数据集构建时所采用启发式搜索带来的潜在数据标注错误问题对该实验结果的影响, 我们还使用了OJClone数据集对我们的方法进行准确性评估. 在BCB数据集上的函数名预测部分, 所使用的数据集为从Github上获取的代码, 为了尽可能的提高函数名预测的准确度, 我们将Github中的项目按照其所获得的Star数量进行排序, 并获取前329个项目的代码, 从而确保我们所获得的数据集是高质量的.

5 总结与展望

在本文中, 我们研究了低资源设置下的代码克隆检测. 我们提出了两种预训练策略来增强代码表示, (1)使用token嵌入的子词丰富, (2)对从token组合到代码片段的函数名预测. 使用增强代码表示, 我们可以用最小的训练语料库训练出一个强大的代码克隆检测模型. 在BigCloneBench和OJClone数据集上的实验结果表明, 我们提出的两种策略对Ⅳ型代码克隆的检测是有效的, 同时性能上有所提升. 我们的模型只用极少个训练实例(BCB上100个克隆对和100个非克隆对, OJClone上200个克隆对和200个非克隆对)可以达到, 甚至胜过以前使用数百万个训练实例的监督模型的效果, 使用更少的数据进行训练可以减少人力物力的消耗. 本文采用的是轻量级、针对性的预训练方法, 与大规模预训练模型CodeBERT的对比显示, 我们的方法取得了更优的效果.