基于深度学习的代码克隆检测技术研究

刘复星　魏金津　任女尔

摘要：在实际软件项目中，复制粘贴式的代码复用或者解决相似问题的模式化思维会造成软件源代码重复出现相同或相似的代码片段。代码克隆检测分析作为衡量代码复用的一种有效方式，在软件开发、维护以及质量保证中发挥着重要作用。提出以深度学习为基础的代码克隆检测技术能够很好地补充常用检测办法无法检测到的场景，如相同含义不同写法的代码段；基于sonar做插件式研发，具有重要的工程意义与实践指导作用。

关键词：代码克隆；深度学习；代码质量管控

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）18-0178-02

1 引言

代码克隆是指在程序设计中表示一段源代码在一个程序，或者一个团体所维护的不同程序中重复出现，是不希望出现的现象【5】。在实际项目中，复制粘贴式的代码复用或者解决相似问题的模式化思维会造成软件源代码重复出现相同或相似的代码片段。为避免巧合，只有超过一定数量的代码相似才能判定为代码克隆。不好的代码复用方式会对整个软件系统的开发和维护带来很多不利因素，因此对于代码复用的分析显得越来越重要。代码克隆分析作为衡量代码复用的一种有效方式，在软件开发、维护以及质量保证中发挥着重要作用。

软件行业内常将Sonar作为技术债务管控的主流工具，Sonar插件式模式，方便自身被其他平台所引入，且有利于扩展第三方插件。通过不同的插件对检测结果进行再加工处理，量化代码质量，方便对不同规模和种类的项目进行代码质量管理[1]。

自动检测代码重复的过程叫作克隆检测，实现基于Sonar的代码克隆自动检测技术，从根源上解决软件代码质量问题带来的风险并提供解决方案，指导软件项目研发质量改进。

基于深度学习算法研发代码克隆检测技术，并以插件形式集成进Sonar，用来检测项目代码中高相似部分从而对代码进行重构，减少代码量和重复功能点，达到节约成本的目的。

2 代码克隆分类

一型克隆：如果排除程序代码在换行、空白、制表符等格式上的区别，以及注释语句等的区别以后，两段代码完全相同。

二型克隆：在一型克隆的基础上， 如果在两段代码之间的常数值以及变量名、函数名等标识符不同， 其余部分相同，那么这就是参变克隆。

三型克隆：在二型克隆基础之上，如果两段代码之间存在个别行不同，比如在一段代码中间新增两条语句，或是删除两条语句， 那么它们是断层克隆。

四型克隆：如果两段代码在结构，形式上不同，但是在逻辑功能上完全相同，即给定相同的输入，总是能得到相同的输出，那么它们就形成了一对功能克隆。【3】

3 代码克隆检测技术

基于纯文本：基于 Text 的克隆检测方法是通过直接比较源代码文本，使用字符串匹配等算法来检测克隆代码。因为没有考虑到代码的形式和结构等信息，因此主要检测Type1型克隆，而对其余类型克隆的支持较弱。

基于Token：基于Token的克隆检测方法是通过对源代码进行词法分析生成源代码的Token序列，然后通过寻找Token序列中相似的子序列来检测克隆代码。因其对源代码进行了词法分析，所以可以较好地支持Type 2克隆的检测。但由于缺乏语法和语义分析，更高级的Type3，Type4型克隆无法較好地支持。

基于语法（AST）：AST，即Abstract Syntax Tree（抽象语法树）【6】，这种克隆检测方法是将源代码表示为如抽象语法树、代码解析树等树的形式，然后通过树匹配算法从中寻找相似的子树来检测克隆代码。因其对源代码进行了语法分析，所以提高了克隆代码检测的准确率，可以较好地支持Type3克隆的检测。但是由于树匹配算法的时间复杂度较高，这类算法的检测速度会低于基于纯文本和Token的方法。

基于深度学习（deep learning）：（1）使用深度学习中递归神经网络，通过训练语言模型，将token表示成向量，构造一棵树型结构（橄榄树），自定义规则列表，对树结构压缩到根结点， 最后生成一个向量， 比较向量研究克隆。（2）从已知的克隆和非克隆方法级代码中提取token，用来训练分类器，然后使用分类器检测给定代码库中的克隆。通过深度学习，可以有效地克隆代码中相似的token的使用模式，从而训练数据以检测测试数据中的克隆。【2】

4 基于深度学习的代码克隆检测技术

检测粒度到方法级别，认为方法是功能实现的主体，检测两个方法之间是否存在克隆，总体实现过程如下：

4.1 生成抽象语法树

1）代码预处理：使用ANTLR，将源代码转换为AST，过程中需要对一部分结点（如与克隆检测无关的编译类型的结点）做过滤。

2）遍历AST并过滤无关节点，进行优化：生成的AST中存在一部分内部结点与编译工作关系比较大而对克隆的检测工作却可能造成误差影响。通过多次实验和观察AST结构，发现这种对克隆检测工作无用的节点共有37种。在这一步将这些节点进行了过滤。

3）生成语料库：由AST深度遍历得到的内部节点序列，把每一个方法对应的节点序列， 类比为一句话或是一段文字， 用于后续skip-gram模型的语料库输入，这个语料库需要足够大，能够涵盖所有的方法节点。实验中， 使用的是jdk作为生出语料库的输入， 生出的语料库总共90MB， 涵盖了53000个方法（c_corpus.txt）. 这个过程只需要进行一次。

4.2 获取词向量

上一个过程中生成的语料库（c_corpus.txt）， 用于作为skip-gram模型的输入。

在实验中发现，将隐藏层神经元个数设置为128， 迭代次数设置在100，000次时效果最好。这样通过使用skip-gram模型， 将147种与方法相关的节点， 一一对应成为多维向量， 并最终生成一个字典. 然后将上一步得到的检测对象的规则节点序列， 依据这个字典中规则节点和向量的一一映射关系， 转换为词向量序列。

由于这些向量携带语义信息，因此还可以为type4型克隆的检测提供新思路。比如代码中的int， double， float等表示数值类型的token，它们在ANTLR转为对应的规则节点，这些节点最终转换成的词向量，向量之间的距离相近。另外类似的还有for， while等。

经过此步骤，将检测对象中的每一个方法都转换为对应的词向量序列，这样就将代码的研究转换为研究向量间关系。

4.3 获取句向量

经过上一个步骤，将检测对象中的每一个方法都转换为对应的词向量序列。但是每个方法的代码行长度都不尽相同， 因此对应的词向量序列长度也不同。为了能够实现比较任意两个方法相似度的功能，使用了scikit-learn中的主成分分析PCA， 目的是将词向量序列压缩为一个向量， 这个向量称之为方法向量， 这样就解决了词向量序列长度不同的问题。

通过使用PCA的数据降维，将每一个方法对应的词向量序列转换为一个方法向量， 且这个方法向量通过解压得到的词向量序列与压缩之前类似，因此能够很好地代表这个词向量序列。

通过研究向量之间的关系与代码之间的克隆关系。

如果两个方法是type1， type2型克隆， 那么这两个方法的AST节点类型和AST结构是一样的， 所以形成的两个词向量序列也是一样的，最终计算出的向量距离是0。

如果两个方法是type3型克隆， 它们的AST节点类型和结构整体相似， 它们最后的词向量序列，也都是类似的。因此在计算它们的距离时， 最终会得到一个数值比较小的向量距离。通过大量研究和实验，把判断type3型克隆的向量距离阈值设置为3e-5，即如果两个方法对应的句向量距离大于0且小于这个阈值，就判断它就是type3型的克隆。

名词解释：

1）抽象语法树（AST）：抽象语法树（缩写为AST），或者语法树（syntax tree），是源代码的抽象语法结构的树状表现形式，这里特指编程语言的源代码。树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。

2）skip-gram：skip-gram模型是word2vec中两个实现word embedding获取词向量的模型之一， 本质上是只有一个隐藏层的神经网络， 这个隐藏层的神经元个数通常会很大，将代码中的每个方法看作是一段文字， 将每一个内部节点看作是一个单词， 这样通过skip-gram模型. 可以将每一个节点转换为一个向量。

3）PCA：使用了scikit-learn中的主成分分析PCA，它是机器学习中常用的数据降维算法之一，本质上是一种数学统计方法。使用PCA可以很好地解决因变量太多而复杂性、计算量增大的弊端。在这里使用PCA的目的是将词向量序列壓缩为一个向量。

5 检测结果

检测对象：jEdit，文件数：597，方法数：8041。

NiCad（当下一款比较流行的克隆检测工具）共检测出447个克隆对， 预处理和检测总共用时64.9秒。

基于深度学习方法：共检测出631个克隆对，预处理和检测总共用时423.9秒。

检测对象：Future30，文件数：427，方法数： 2664。

NiCad共检测出171个克隆对， 预处理和检测总共用时14.7秒。

基于深度学习方法：共检测出331个克隆对，预处理和检测总共用时58.7秒。

结果分析：NiCad是基于文本实现的克隆检测工具，这种方式在检测速度上比较有优势，但是由于没有对代码进行词法和语法分析，因此主要检测Type 1，2型克隆， 对于更高级的3型克隆检测效果很一般。基于深度学习方法首先把源码转换为AST， 这个转换过程相对耗时， 但是能检测出更多类型和数目的克隆对。【1】

6 优势

基于文本或基于token的检测工具主要只能检测出1型和2型克隆，方法可以很好地检测1，2型和3型克隆（1，2型克隆的准确率近似百分之百），并且对4型克隆的发现提供了新的思路。

传统的基于AST的方式除了能检测出1，2型克隆， 也能很好检测出3型克隆， 但是它们往往使用时间复杂度比较大的子树匹配算法，进而判断代码克隆，这种算法时间开销往往比较大。与传统的基于AST的克隆检测方法相比，方法虽然也把源码转换为AST，但是并不直接比较两个AST的相似度，而是通过遍历AST生成结点的序列， 随后通过对向量进行相关数值计算，来研究两段代码的相似度，这样就避免了使用时间开销比较大的子树匹配算法，这种将AST转换为向量的方式， 比传统方法在时间效率上得到了大大提升，检测效果也比较好。

基于机器学习的检测工具，如CCLearner，从已知的克隆和非克隆方法级代码中提取token，用来训练分类器，然后使用分类器检测给定代码库中的克隆。这种方法需要有标注的数据，即数据集需要知道哪些方法是克隆，哪些不是克隆。方法不需要标注数据。而且使用skip-gram模型得到的向量字典只需生成一次，依照这个字典可以将方法转换为一个向量。

7 总结

基于深度学习开发的代码克隆检测技术，可以作为插件集成进Sonar，以比较高的效率扫描项目的克隆代码，开发者根据扫描结果对项目代码重复部分进行优化和重构，可以提高项目质量节约项目成本。

参考文献

[1] 柳萌宇，钟浩，于海波.基于变更相似性的跨语言克隆检测方法[J].计算机与现代化，2016（4）.

[2] 林婵，李俊杰，饶飞，等.基于索引的分布式代码克隆检测[J].信息安全研究，2016（3）.

[3] 甘水滔，秦晓军，陈左宁，等.一种基于特征矩阵的软件脆弱性代码克隆检测方法[J].软件学报，2015（2）.

[4] 郭颖，陈峰宏，周明辉.大规模代码克隆的检测方法[J].计算机科学与探索，2013（12）.

[5] 王国莉，白昊昱.程序设计语言中代码克隆的研究[J].计算机与网络，2013（3）.