代码克隆是软件开发中的常见现象。在软件开发和演化的过程中,程序员通过复制和粘贴代码段,或者使用框架、复用设计模式和自动工具生成代码等方式加速软件开发。以上操作导致代码库中存在2个及以上相同或相似代码段的现象称为代码克隆[1]。开源社区中的代码克隆可以提高开发效率,但是也会导致缺陷传播,降低系统的可靠性。代码克隆检测技术目的在于自动检测软件系统中克隆的代码,可以帮助开发人员和管理者及时发现代码克隆造成的缺陷,更好地保证软件质量。
根据相似程度的不同,Bellon等[2]将代码克隆分为4种类型,从type1到type4,代码相似程度逐渐降低,检测难度也逐渐增加。传统的代码克隆检测方法基于人工定义的规则,对专家经验依赖程度较高。基于深度学习的方法能够自动学习出代码的特征,摆脱“特征工程”的难题,减少人工分析成本。Hindle等[3]认为编程语言和自然语言一样,具有重复性和可预测性,能够被机器理解和分析。受Hindle等[3]工作的启发,许多学者将代码作为自然语言来处理。例如早期的Nicad方法[4]通过对比2个代码行中最长相同序列来检测代码克隆,该方法在文本层面进行分析,不能检测type4类型的克隆。基于词法的克隆检测中,代码被表示为token序列。CClearner[5]将程序的单词分为8种类型,针对每个类型比较2个代码片段的词频序列,得到8维向量送入神经网络中训练。尽管代码和自然语言有很多共性的特征,都是由一系列单词组成,但是代码具有更清晰的逻辑、丰富且复杂的结构,且标识符之间存在长距离依赖,将代码视作自然语言或者token序列进行处理容易丢失信息。
抽象语法树(abstract syntax tree,AST)是基于抽象语法结构将源代码转换为树结构的表示形式。研究表明,基于AST表征的模型明显优于基于序列表征的模型[6-8]。CDLH模型[6]使用基于树的长短期记忆网络(tree-structured long short-term memory,Tree-LSTM)遍历AST,为了提高效率,使用特定的哈希函数对代码向量进行哈希处理,比较散列向量之间的汉明距离来识别代码克隆。为了解决子节点数目可变的问题,将AST转换为全二叉树。Zeng等[9]基于递归自动编码器(recursive autoencoder,RAE)模型提出了加权递归自编码器(weighted recursive autoencoder,WRAE),利用WRAE分析AST,提取程序特征并将函数编码成向量。该方法在输入之前利用二叉树生成规则将AST转换成了完满二叉树。
由于程序的复杂性,AST的结构通常又大又深,尤其是嵌套结构,这样容易产生梯度消失问题,导致AST丢失从远程节点到根节点携带的一些语义信息。为了简化和提高效率,直接将AST视为二叉树或者将AST转换为二叉树,这种做法破坏了源代码的原始语法结构,削弱了神经网络模型捕获真实语义的能力。为了克服上述基于AST的神经网络的局限性,Zhang等[10]提出了ASTNN,将每个大型的AST分割成许多语句树序列,在保留原始代码语义的基础上解决了梯度消失问题。词向量训练器将每一个语句树都编码成向量送入双向门控循环单元(bidirectional gated recurrent unit,BiGRU)中,生成代码片段的向量表示。Meng等[11]在ASTNN模型的基础上进行改进,特征提取阶段用BiLSTM替换原本的BiGRU,新增加一个注意力网络层提取代码特征。
在特征提取阶段,现有的大部分模型都使用基于循环神经网络(recurrent neural network,RNN)的时间序列模型。2017年,谷歌团队[12]提出了完全基于自注意力的深度学习模型——Transformer。相较于RNN,自注意力支持高度的并行化,并且还能轻松地实现长期上下文建模。
1 代码克隆检测方法
本文提出一种基于Transformer和卷积神经网络(convolutional neural network,CNN)的代码克隆检测(Transformer and CNN based code clone detection,TCCCD)方法。TCCCD方法的总体架构如图1所示。基于AST的表征方式能够实现源代码的抽象表示,优于基于token的表征方式。为了解决AST过大带来的梯度消失问题,先将代码解析成AST,同时保留源代码的语法结构。本文借鉴ASTNN切割AST的思想,将一段代码的AST切割为小型语句子树,其中,语句子树由先序遍历得到的语句节点序列构成,蕴含代码结构和层次化信息。每一组语句树通过语句编码器编码成向量,送入神经网络中。在神经网络设计方面,现有的模型大多使用基于RNN的时间序列模型,当2个相关性较大的时刻距离较远时,会产生较大的信息损失。本文使用Transformer的Encoder部分提取代码的全局信息,Transformer能够直接对输入序列之间的更长距离的依赖关系建模。作为补充,使用CNN捕获代码的局部信息,学习出蕴含词法、语法和结构信息的代码向量表示。计算两段代码向量的欧氏距离表征语义关联程度,训练一个二元分类器检测代码克隆。
图1 TCCCD的总体架构
Figure 1 The architecture of TCCCD
1.1 分割AST,编码语句树序列
首先,面向函数粒度,使用现有的语法分析工具,将代码解析为AST。为了防止AST规模过大而导致梯度消失问题,不能直接将AST作为模型的输入,而是按照语句粒度对AST进行切割。
AST经过先序遍历,得到语句节点的集合S,将Method Declaration视为一种特殊的语句节点,故S′=S∪{Method Declaration},集合S′中的每一个节点都对应代码中的一条语句。对于嵌套语句C,C={FuncDef,While,DoWhile,Try,For,If,Switch},定义一系列独立节点P={block,body}。其中,block用于拆分嵌套语句的头和主体部分;body用于方法声明。对于所有的语句节点s,s∈S′,将s的后代定义为D(s)。节点d∈D(s),如果s和d之间存在一条路径通过节点p,p∈P,表明节点d被节点s中的一条语句包含,则称节点d为节点s的子语句节点。那么,以s为根的语句树是由s及其所有后代节点D(s)组成。按照语句树的定义,构造函数递归地创建语句树,并将其依次添加到语句树序列中。语句树序列的顺序蕴含了代码结构的层次化信息。
针对分割得到的语句树序列,将每棵语句树编码成向量。首先,经过Word2Vec训练符号嵌入向量,得到初始输入;其次,遍历语句树,并递归地将当前节点的符号作为新的输入进行计算,同时计算其叶子节点的隐藏状态。对于非叶子节点来说,以节点n为例:
(1)
式中:xn表示节点n的one hot向量;We表示预训练好的词嵌入矩阵。
(2)
式中:Wn∈Rd×k表示权重矩阵;C表示子节点的个数;hi为叶子节点的隐藏状态;bn表示偏置;σ(·)为激活函数;h表示更新后的隐藏状态。
由于每棵语句树子节点的个数不一致,计算叶子节点的隐藏状态时,为了利用矩阵运算进行批处理,使用ST-tree的动态批处理样本的算法[10]。
如式(3)所示,经过最大池化,可以得到每一个语句树最后的向量表示et,其中,N表示语句树的节点个数。
et=[max hi1,max hi2,…,max hik],i=1,2,…,N。
(3)
1.2 Transformer的Encoder捕获全局信息
在RNN中,由于信息是沿着时刻逐层传递的,因此,当2个相关性较大的时刻距离较远时,会产生较大的信息损失。虽然引入了门控机制,如LSTM、GRU等,可以部分解决这种长距离依赖问题,但是它们的记忆窗口也是有限的。CNN善于捕获局部特征,如果想要捕获远距离特征,需要增加网络深度。Transformer完全基于自注意力,能够直接建模输入序列之间更长距离的依赖关系。综合考虑Transformer的性能与参数量,本文使用Transformer的Encoder提取全局的特征。
Transformer的Encoder部分捕获全局信息主要包含以下5个步骤。
步骤1 位置编码。输入为经过词嵌入后的张量,故只需对输入进行位置编码,位置编码的方法为
PE(pos,2i)=sin(pos/10 0002i/d);
(4)
PE(pos,2i+1)=cos(pos/10 0002i/d)。
(5)
X表示经过词嵌入后得到的张量,将词嵌入与位置编码相加,可以得到经过位置编码后的输出Y:
Y=X+PE(X);
(6)
步骤2 将向量Y作为输入,送入多层注意力机制层。注意力函数是基于3个矩阵(Q、K、V)同时计算的。
(7)
步骤3 通过残差连接和层归一化,使矩阵运算维数一致。将网络中的隐藏层归一化为标准正态分布,加快模型的训练速度和收敛速度。
Y′=Y+YAttention;
(8)
Y″=LayerNorm(Y′)。
(9)
步骤4 通过前馈层和2个线性映射层,使用激活函数来生成向量Yhidden。
Yhidden=σ(Linear(Linear(Y″)))。
(10)
步骤5 进行残差连接和层归一化,得到最终向量C1。
Y′hidden=Yhidden+Y″;
(11)
C1=LayerNorm(Y′hidden)。
(12)
1.3 CNN捕获全局信息
根据文献[13-15]的研究,CNN和self-attention在特征信息的提取上存在差异。self-attention焦点在全局上下文中决定在哪里投射更多的注意力,而CNN更多地关注所输入的局部特征信息。不同的模型和结构通常会学习到不同的特征[16],Transformer与CNN可以互补[17]。
借鉴ConvS2S[18],选取其中的卷积块结构,利用级联一维卷积获得代码行局部特征信息。如式(13)所示,每个卷积层包括一个一维卷积、一个门控线性单元(gated linear unit,GLU)和一个残差连接。
F=Y+GLU(Conv(Y))。
(13)
式中:Y表示CNN的输入,为经过词嵌入层和位置编码得到的向量,与Transformer的Encoder共享。Conv表示一维卷积层,其卷积核大小常设置为3。
最后,为了使卷积层输出的特征向量C2与上文中的向量C1具有相同维数,增加一个线性层网络:
C2=Linear(F)。
(14)
1.4 融合Transformer的Encoder和CNN学习到的特征
将Transformer的Encoder学习到的全局上下文特征与CNN学习到的局部代码特征表示相融合,相比以往的方法大多只用到单个模型学习代码特征,本文方法能充分挖掘代码信息。
Z=Concat(C1,C2)。
(15)
如式(15)所示,通过矩阵连接将2个特征向量进行合并,得到代码表示向量Z,相当于将CNN部分嵌入Transformer的Encoder中,通过设置layer的大小,可以实现Transformer的Encoder部分与CNN的堆叠。
考虑到不同语句的重要性直观上是不相等的,例如,ForStatement语句中的API调用可能包含更多的函数信息,因此,使用最大池化来捕获最重要的语义。该模型最终生成一个向量r∈R2m,它被视为代码片段的向量表示。
1.5 计算两段代码向量的相似度
经过以上步骤,两段代码分别转换成固定长度的向量表示r1和r2,根据r=|r1-r2|计算距离,表示两段代码的语义关联程度。经过sigmoid函数得到输出
将输出
作为两段代码的相似性衡量指标。
(16)
式中:Wo∈R2m×M为权值矩阵;bo为偏置。
二元交叉熵被用作损失函数。
(17)
对所有参数进行优化,存储训练后的模型。对于新的代码片段,应将其预处理为语句子树序列,然后输入重新加载的模型进行预测。输出
是[0,1]的单个值,因此,预测值prediction为
(18)
式中:δ为阈值。本文实验将δ设为0.5[10-11]。如果相似度阈值高于0.5,得到预测值为True,将代码对标识为克隆。
2 实验与结果分析
2.1 实验数据与评测指标
代码克隆检测使用的数据集包括OJClone和BigCloneBench,这2个数据集已被许多研究人员用于代码相似性检测和克隆检测[6,10-11]。OJClone数据集的标签分为2类;BigCloneBench数据集的标签分为5类,分别表示类型1至类型4的代码克隆,其中类型3的代码克隆分为强3型和中度3型。
数据集基础信息如表1所示。对于OJClone数据集,7 500个代码段组合可以得到超过2 800万个代码对,随机选取50 000个代码对构成实验数据集。对于BigCloneBench,59 688个代码段组合可以得到超过600万个真代码克隆对和超过26万个假代码克隆对。随机抽取了20 000对假代码克隆对,抽取中度3型和类型4代码克隆对共20 000对,类型1、类型2和强3型数量较少,均小于20 000对,以上全部加入实验数据集中。2个实验数据集中的数据均以3∶1∶1的比例随机划分为训练集、验证集和测试集。
表1 代码克隆检测数据集
Table 1 Code clone detection dataset
数据集代码段数量真代码克隆对占比/ %最长序列长度平均序列长度AST最大深度AST平均深度AST最大节点数AST平均节点数OJClone7 5006.62 2712446013.21 624192BigCloneBench59 68895.716 2532271929.915 217206
代码克隆检测常使用混淆矩阵来评估模型的性能。所有指标的计算方式为
(19)
式中:Precision表示精度;Recall表示召回率;TP表示被分类系统识别为克隆的克隆对数量;FP表示被识别为克隆的非克隆对的数量;TN表示被识别为非克隆的非克隆对的数量;FN表示被识别为非克隆的克隆对的数量。
2.2 实验环境与参数设置
本实验的硬件环境为Inter(R)Core i7-8700K CPU、NVIDIA GeForce GTX 1080 Ti(discrete graphics)、RAM 32.00 GB。软件环境为Anaconda 3.6.0、Pycharm 3.4.0、Pytorch 1.6.0。使用pycparser解析C代码、Javalang解析Java代码得到AST;使用Word2Vec得到词嵌入表示;AdaMax为优化器。
经过反复多次实验,调整模型参数,直至得到性能最优的模型。详细的模型参数如下:Encode dimension为128;Embedding dimension为128;Hidden dimension为256;Epoch为15;Batch size为32;Number of head为8;Kernel size为3;Number of encoder block layer为6;max length为512;δ为0.5。
2.3 实验结果
2.3.1 模型结构分析
为了分析模型结构对代码克隆检测的影响,验证TCCCD中融合2个网络后提取特征的能力更强,设计了3种神经网络结构进行代码克隆检测比较,即TCCCD、CNN及Transformer的Encoder。
在OJClone数据集上进行实验,图2展示了经过每一轮训练之后,3个神经网络结构在OJClone验证集上的损失曲线。图3展示了3个神经网络结构在OJClone数据集上检测代码克隆的精度、召回率和F1值。可以看出,使用Transformer的Encoder和CNN相结合的结构,即TCCCD,相对于其他2个结构收敛速度更快。经过1轮训练之后,TCCCD在验证集上的损失值就降低到了0.126 8。在15轮的训练过程中,TCCCD每一轮验证损失值均低于另外2个网络结构。经过15轮训练之后,TCCCD结构的精度为98.9%,召回率为98.1%,F1值为98.5%。3个评价指标值均高于其他2个网络结构。
图2 不同神经网络结构在OJClone验证集上的损失曲线
Figure 2 Loss curves for different neural network on the validation set of OJClone
图3 不同神经网络结构在OJClone检测代码克隆结果
Figure 3 Performance comparison of different neural network for detecting code clone on OJClone dataset
表2展示了不同神经网络结构在数据集BigCloneBench上对4种不同类型的代码克隆检测结果,其中,BCB-T1、BCB-T2、BCB-T4分别代表数据集BigCloneBench中的类型1、类型2、类型4,BCB-ST3和BCB-MT3分别代表数据集BigCloneBench中的强3型和中度3型。实验表明,在4种类型的代码克隆中,TCCCD方法精度、召回率及F1值均为最高。TCCCD相对于使用Transformer的Encoder部分或者CNN提取代码特征有优势,可以提高检测精度,同时降低误报率和漏报率。且TCCCD在识别BCB-T1和BCB-T2中2个代码片段的相似性方面都非常有效,因为除了不同的标识符名称、注释等,这2个代码片段几乎相同。而在其他代码克隆类型中,TCCCD检测效果稍有下降,尤其在BCB-T4中,检测精度可以达到99.3%,召回率却只有91.2%,F1值也只有93.8%。说明检测的假阳性率较高,有一些语义上相似的代码对并不属于代码克隆对。
表2 不同神经网络结构在BigCloneBench数据集上对4种不同类型的代码克隆检测结果
Table 2 Different neural networks detect of four types code clone on BigCloneBench
神经网络结构类型精度/%召回率/%F1/%CNNBCB-T196.595.796.1BCB-T296.395.695.8BCB-ST395.992.593.9BCB-MT391.187.289.3BCB-T490.382.186.3Transformer的Encoder部分BCB-T199.699.899.7BCB-T299.399.699.4BCB-ST399.094.196.5BCB-MT398.191.294.1BCB-T497.686.391.2TCCCDBCB-T1100.0 100.0 100.0 BCB-T2100.0100.0100.0BCB-ST399.694.996.8BCB-MT399.492.196.1BCB-T499.391.293.8
实验表明,Transformer的Encoder部分和CNN学习到了不同的代码特征,2个网络相结合提取特征的能力更强。
2.3.2 各方法在2个数据集上的检测结果对比
表3展示了各模型在OJClone数据集上检测代码克隆的结果。可以看到,RAE和CDLH方法的精度和F1值都比较小,均低于60%。这是因为RAE基于token序列进行编码,无法有效学习到代码的结构特征。OJClone是由学生提交的编程题构造而来,一般很少引用第三方库,通常会定义i、j、k等没有意义的变量名。因此,CDLH虽然是基于AST,依旧会丢失很多词汇信息,只能捕获一些语法信息。ASTNN、At-BiLSTM、TCCCD检测代码克隆的效果较好,精度、召回率和F1值均高于90%。3种方法都基于语句子树进行编码,说明将大型AST切割成语句子树的方法有助于模型学习代码的结构信息、语句级的词法和语法信息。TCCCD在各项度量指标上均高于其他任何一个模型。在检测精度上,TCCCD与ASTNN均具有最高值98.9%;在召回率上,TCCCD比ASTNN高5.4百分点,比At-BiLSTM高2.8百分点,达到了98.1%;在F1值上,TCCCD比ASTNN高3百分点、比At-BiLSTM高出2.5百分点,达到了98.5%。Transformer的Encoder部分和CNN相辅相成,可以学习出融合代码全局信息和局部信息的稠密向量表示。TCCCD能提取到更多的词法、语法和结构信息来衡量代码的相似性。
表3 各方法在OJClone数据集上的实验结果
Table 3 Results of various methods on OJClone %
方法精度召回率F1RAE48.965.656.0CDLH47.073.057.0ASTNN98.992.795.5At-BiLSTM96.895.396.0TCCCD98.998.198.5
表4展示了各方法在BigCloneBench上的检测结果。
表4 各方法在BigCloneBench数据集上的实验结果
Table 4 Results of various methods on BigCloneBench %
方法精度召回率F1RAE73.560.156.0CDLH92.074.082.0ASTNN97.988.492.9At-BiLSTM95.991.193.4TCCCD99.191.594.2
由于BigCloneBench包含4种代码克隆类型,所以最终的结果是根据4种类型的代码对数量加权计算得来。相较于OJClone数据集,RAE和CDLH方法检测效果均有提升,RAE的检测精度由48.9%提升到了73.5%,CDLH的检测精度由47.0%提升到了92.0%。这是由于BigCloneBench是从真实项目中挖掘到的,实现同一个问题时往往会用到相同的第三方库的类以及Java基础类。而ASTNN、At-BiLSTM、TCCCD检测效果稍有下降,原因是类型4的代码对占代码克隆对总数的一半以上。而类型4为语义相似的代码克隆对,有一些语义上相似的代码对并不属于代码克隆,致使假阳性率升高,使得召回率和F1值均有所降低。虽然上述3个方法在BigCloneBench上检测效果略有下降,但还是优于RAE和CDLH方法。
在检测精度上,TCCCD为99.1%,比ASTNN高出1.2百分点,比At-BiLSTM高出3.2百分点;在召回率值上,TCCCD比ASTNN高出3.1百分点、比At-BiLSTM高出0.4百分点;在F1值上,TCCCD比ASTNN高出1.3百分点,比At-BiLSTM高出0.8百分点,达到了94.2%。相比之下,TCCCD可以实现更高检测精度,同时降低误报率。
3 结论
本文构建了基于Transformer和卷积神经网络的代码克隆检测模型——TCCCD。为了解决AST过大带来的梯度消失问题,同时保留源代码的语法结构,将AST切割为多个语句子树。在神经网络设计方面,本文将注意力模型与CNN相结合来提取代码特征。TCCCD使用Transformer的Encoder来提取代码的全局信息,由于Transformer与卷积神经网络形成互补,再利用CNN模型,捕获代码的局部信息,进而学习出蕴含词法、语法和结构信息的代码向量表示。本文方法在OJClone和BigCloneBench数据集上进行评测,并与代表性代码克隆检测方法进行比较,精度、召回率、F1值均有提升。实验结果表明,该方法能够有效检测代码克隆。
[1] 陈秋远, 李善平, 鄢萌, 等. 代码克隆检测研究进展[J]. 软件学报, 2019, 30(4): 962-980.
CHEN Q Y, LI S P, YAN M, et al. Code clone detection: a literature review[J]. Journal of Software, 2019, 30(4): 962-980.
[2] BELLON S, KOSCHKE R, ANTONIOL G, et al. Comparison and evaluation of clone detection tools[J]. IEEE Transactions on Software Engineering, 2007, 33(9): 577-591.
[3] HINDLE A, BARR E T, SU Z D, et al. On the naturalness of software[C]∥2012 34th International Conference on Software Engineering (ICSE). Piscataway: IEEE, 2012: 837-847.
[4] CORDY J R, ROY C K. The NiCad clone detector[C]∥2011 IEEE 19th International Conference on Program Comprehension. Piscataway: IEEE, 2011: 219-220.
[5] LI L Q, FENG H, ZHUANG W J, et al. CCLearner: a deep learning-based clone detection approach[C]∥2017 IEEE International Conference on Software Maintenance and Evolution (ICSME). Piscataway: IEEE, 2017: 249-260.
[6] WEI H H, LI M. Supervised deep features for software functional clone detection by exploiting lexical and syntactical information in source code[C]∥Proceedings of the 26th International Joint Conference on Artificial Intelligence. New York: ACM, 2017: 3034-3040.
[7] ALON U, LEVY O, YAHAV E. CODE2SEQ: generating sequences from structured representations of code[EB/OL]. (2018-08-04)[2022-09-11].https:∥arxiv.org/abs/1808.01400.
[8] ALON U, ZILBERSTEIN M, LEVY O, et al. CODE2VEC: learning distributed representations of code[J]. Proceedings of the ACM on Programming Languages, 2019, 3: 40.
[9] ZENG J, BEN K R, LI X W, et al. Fast code clone detection based on weighted recursive autoencoders[J]. IEEE Access, 2019, 7: 125062-125078.
[10] ZHANG J, WANG X, ZHANG H Y, et al. A novel neural source code representation based on abstract syntax tree[C]∥2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE). Piscataway: IEEE, 2019: 783-794.
[11] MENG Y, LIU L. A deep learning approach for a source code detection model using self-attention[J]. Complexity, 2020, 2020: 1-15.
[12] VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need[C]∥Advances in Neural Information Processing Systems 30. Long Beach: NIPS, 2017:5998-6008.
[13] CORDONNIER J B, LOUKAS A, JAGGI M. On the relationship between self-attention and convolutional layers[EB/OL]. (2019-11-08)[2022-09-11].https:∥arxiv.org/abs/1911.03584.
[14] GONG J J, QIU X P, CHEN X C, et al. Convolutional interaction network for natural language inference[C]∥Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing. Stroudsburg: Association for Computational Linguistics, 2018: 1576-1585.
[15] YANG G, ZHOU Y L, CHEN X, et al. Fine-grained pseudo-code generation method via code feature extraction and transformer[C]∥2021 28th Asia-Pacific Software Engineering Conference (APSEC). Piscataway: IEEE, 2022: 213-222.
[16] 张安琳, 张启坤, 黄道颖, 等. 基于CNN与BiGRU融合神经网络的入侵检测模型[J]. 郑州大学学报(工学版), 2022, 43(3): 37-43.
ZHANG A L, ZHANG Q K, HUANG D Y, et al. Intrusion detection model based on CNN and BiGRU fused neural network[J]. Journal of Zhengzhou University (Engineering Science), 2022, 43(3): 37-43.
[17] YUAN Y H, HUANG L, GUO J Y, et al. OCNet: object context for semantic segmentation[J]. International Journal of Computer Vision, 2021, 129(8): 2375-2398.
[18] GEHRING J, AULI M, GRANGIER D, et al. Convolutional sequence to sequence learning[C]∥Proceedings of the 34th International Conference on Machine Learning. New York: ACM, 2017: 1243-1252.