语义级代码克隆检测数据集的评估与改进

摘要：应用深度学习来检测语义代码克隆受到了研究界的广泛关注。

本文分享自华为云社区《语义级代码克隆检测数据集的评估与改进》，作者：软件分析 Lab。

一、背景介绍

代码克隆检测[1]是软件工程领域一个很重要的研究方向。代码克隆不必要地增加了软件系统的大小。一个系统越大，需要维护的开销就越高。为了检测和管理代码克隆，研究者把代码克隆分为四类[2]：

• 类型一是除了注释、空格、换行之外，完全相同的代码片段；

• 类型二是在类型一的基础上，除了类型名、变量名以及常量名之外，完全相同的代码片段；

• 类型三是在类型二的基础上，有少量语句的增加、删除、修改；

• 类型四是指实现的功能相同，但实现的方法完全不同。

在代码克隆成为一个软件工程的研究方向以来，许多非深度学习的方法都专注在检测类型一、二、三的克隆，但是在检测语义代码克隆（中等类型三、弱类型三以及类型四）上取得的进展很有限。这是因为非深度学习的方法没有识别在词法以及语法级别实现很不相同，但属于语义代码克隆的代码对（例如冒泡排序和快速排序）。

基于一个带标记的数据集（如 BigCloneBench[3]），研究者提出许多基于深度学习的方法来检测语义代码克隆[4][5]。他们的实验结果展示了他们的方法可以有效的检测语义代码克隆。基于深度学习的方法可以有效的检测语义代码克隆是因为这些方法可以从训练集中学习到语义代码克隆的语义信息。

然而目前还尚未有工作研究 BigCloneBench 数据集是否真的能够用来验证语义代码克隆检测方法的有效性。在本篇文章中[6]，我们首先发现 BigCloneBench 数据集的语义代码克隆对使用相似的标识符，而非语义代码克隆对的标识符不相似。接着文章提出了一个不合理（undesirable-by-design）的克隆检测模型（名为 Linear-Model），通过只考虑那些标识符在代码克隆片段中出现来检测代码语义代码克隆。这个不合理的模型可以达到跟其他被验证有效的方法一样的效果。为了减轻这个问题，我们通过抽象 BigCloneBench 数据集中的一部分标识符（类型名、变量名以及方法名）得到 AbsBigCloneBench 数据集。实验结果表明 AbsBigCloneBench 数据集能够更好的验证语义代码克隆检测方法的有效性，同时使用 AbsBigCloneBench 数据集训练的模型在 BigCloneBench 数据集测试依然有效，而使用 BigCloneBench 数据集训练的模型在 AbsBigCloneBench 数据集测试却无效。

二、BigCloneBench 数据集分析

BigCloneBench 数据集由 Svajlenko 等人[3]提出，它是从 IJaDataset[7]中挖掘而来，并且由三个专家手动确认。IJaDataset 包含 25000 个项目，3.65 亿行代码。BigCloneBench 包含 10 类问题以及 600 万克隆对和 26 万非克隆对。BigCloneBench 将类型三的代码克隆分为弱、中、强和非常强四类。表 1 展示了 BigCloneBench 数据集中每个类型的代码克隆对占比，超过 98%的代码克隆对属于语义代码克隆。

表 1：BigCloneBench 数据集中每个克隆类型的占比

1. BigCloneBench 不同问题之间标识符的 Jaccard 相似系数分析

算法 1 展示了我们统计 BigCloneBench 数据集的不同问题之间标识符的 Jaccard 相似系数分析的流程图。我们首先得到每一个问题出现频率最高的 20 个标识符。然后我们计算两两问题之间的标识符的 Jaccard 相似系数，由于 BigCloneBench 数据集中包含 10 个问题，因此我们最终会得到 45 个相似系数。最后我们对这 45 个相似系数取平均作为数据集的不同问题之间的 Jaccard 相似系数。BigCloneBench 数据集不同问题之间的标识符的 Jaccard 相似系数为 0.038，它表明 BigCloneBench 数据集不同问题之间的标识符很不相同。

表 2 详细展示了 BigCloneBench 数据集中每类问题的前 20 个标识符名字。我们用同样的方法分析了 OJClone 数据集[11]（另一个被广泛使用的语义代码克隆检测数据集）的不同问题之间的标识符的 Jaccard 相似系数为 0.469，它表明 OJClone 数据集的不同问题之间的标识符比较相同。导致差异的原因是 BigCloneBench 数据集是从真实项目中挖掘到的，实现同一个问题时，往往会用到相同的第三方库的类以及 Java 基础类。而 OJClone 是通过学生提交的编程题构造而来，这些编程题往往是基础的算法，学生一般很少引用第三方库，在定义变量名时，一般都会定义 i、j、k、n 等。

表 2：BigCloneBench 数据集中每类问题的前 20 个标识符名字

2. BigCloneBench 数据集和现实世界中的语义代码克隆示例

图 1 和图 2 展示了一个 BigCloneBench 数据集中的语义代码克隆包含相似的标识符的例子和 Stack Overflow 中的一个语义代码克隆包含不相似的标识符的例子。这两个例子可以说明现实世界中确实存在不依赖标识符的语义代码克隆，而 BigCloneBench 数据集中的语义代码克隆依赖标识符的问题应该需要被重视和提升。

图 1：BigCloneBench 数据集中具有相似标识符的语义代码克隆示例

图 2：Stack Overflow 具有不相似标识符的语义代码克隆示例

三、不合理的克隆检测模型

本节展示了我们设计的不合理的克隆检测模型（名为 Linear-Model）的整体架构以及具体的技术细节。

1.整体架构

图 3 展示了 Linear-Model 的整体架构图。我们首先使用 javalang[8]将代码片段解析为抽象语法树。然后我们使用 PACE[5]（由 Yu 等人提出）对每个结点进行编码，接着使用编码的结点传给 Linear-Model 和一个最大池化层。

图 4 展示了详细例子（虚线表示 AST 中的终结结点，实线表示 AST 中的非终结结点）。然后我们遍历 AST（抽象语法树）上的所有结点，并且根据 node 的 ID 去重。最后我们得到的 node ID 为“MethodDeclaration”, “copy”, “FormalParameter”, “src”, “ReferenceType”, “String”, “dest”, and “IOException”。State-of-the-art 的方法使用程序的 AST 信息，包括词法和结构信息。Linear-Model 也使用同样的词法信息，但是由于 Linear-Model 不对 AST 做处理，因此 Linear-Model 只使用程序的少量结构信息（比如根据 ForStatement 结点得知程序包含 for 循环结构等），详细的 Linear-Model 的实现在下一节介绍。

图 3：Linear-Model 的整体架构

图 4：一个代码片段及其对应的 AST 以及遍历 AST 得到的 Node IDs 集合的示例

2.线性操作和最大池化

图 5 展示了 Linear-Model 的线性操作和最大池化。Node IDs 集合中有 n 个 token，每个 token 的编码长度为 d。Linear-Model 使用一个 d×m 的矩阵进行线性操作，得到一个 n×m 的矩阵。经过线性操作后，node IDs 集合中的 token 个数不变。然后对每一维度使用一个最大池化的操作，最终得到一个 1×m 的向量。

图 5：线性操作

四、实验设置

我们通过实验回答如下 3 个 Research Question：

RQ1：一个不合理的模型 Linear-Model（通过只考虑哪些标识符出现在代码片段中）能够在 BigCloneBench 数据集中达到好的效果吗？

RQ2：State-of-the-art 的方法和 Linear-Model 在 AbsBigCloneBench 数据集上的效果如何？

RQ3：State-of-the-art 的方法和 Linear-Model 在交叉实验上的效果如何？

1.对比方法

• ASTNN[9]。ASTNN 是一个基于神经网络的程序抽象语法树的表示模型。它对抽象语法树的子树进行编码来更加充分的捕获程序抽象语法树的信息。然后它使用一个双向 RNN 来对每个子树的表示做处理，得到整个 AST 的表示。最后通过比较两个代码片段的 AST 表示的相似性来判断两个代码片段是否属于代码克隆。

• TBCCD[5]。TBCCD 提出使用基于树的卷积神经网络检测语义代码克隆的工作。TBCCD 还提出了一个基于词位置编码的方法来解决测试集中存在不在词表中的未知 token 的问题。

• FA[10]。FA 使用基于图的卷积神经网络进行语义代码克隆检测。FA 首先在程序的抽象语法树上加边，然后 FA 使用两个不同类型的图神经网络来判断两个代码片段的相似性。由于 FA 只支持 Java 语言的代码克隆检测，因此我们只汇报 FA 在 BigCloneBench 数据集以及 AbsBigCloneBench 数据集上的结果。

2.数据集

我们使用两个公开的数据集（剩下两个数据集是基于这两个数据集变化而来）：BigCloneBench[3]和 OJClone[11]。这两个数据集被广泛用来验证语义代码克隆检测方法的有效性。表 3 展示了两个数据集的详细信息。

表 3：BigCloneBench 数据集和 OJClone 数据集的整体统计信息

• BigCloneBench

BigCloneBench 数据集由 Svajlenko 等人提出，它是从 IJaDataset 中挖掘而来，并且由三个专家手动确认。IJaDataset 包含 25000 个项目，3.65 亿行代码。BigCloneBench 包含 10 类问题以及 600 万克隆对和 26 万非克隆对。BigCloneBench 将类型三的代码克隆分为弱、中、强和非常强四类。表 1 展示了 BigCloneBench 数据集中每个类型的代码克隆对占比，超过 98%的代码克隆对属于语义代码克隆。我们使用 OJClone 来回答我们的 RQ1。

• OJClone

OJClone 由 Mou 等人提出，它最初是用来验证代码分类任务有效性的。后来 CDLH、TBCCD、ASTNN 以及 FA 使用 OJClone 来验证语义代码克隆检测任务有效性。学生为了解决同一问题提交的代码片段的实现往往不同，因此 OJClone 的代码克隆对被认为至少属于类型三的克隆。我们使用 OJClone 来回答我们的 RQ1。

• AbsBigCloneBench

AbsBigCloneBench 是从 BigCloneBench 数据集中抽象而来。AbsBigCloneBench 抽象了 BigCloneBench 数据集中的部分标识符，包括类型、变量以及函数名，保留了其他 token，比如操作符、基本类型以及成员变量。根据代码克隆类型的定义，抽象标识符之后的 AbsBigCloneBench 不会改变 BigCloneBench 数据集中语义代码克隆和非语义代码克隆的标记信息。我们使用 AbsBigCloneBench 数据集来回答我们的 RQ2 和 RQ3.

• Over-AbsBigCloneBench

跟 Mou 等人和 Yu 等人一样，我们同样尝试研究如果只使用 AST 中的非终结结点，语义代码克隆检测方法在该数据集的有效性。Over-AbsBigCloneBench 只使用图 4 中实线部分的 token 进行实验。我们使用 Over-AbsBigCloneBench 来展示 state-of-the-art 方法在这样一个过抽象的数据集上同样比 Linear-Model 有效。

3.实验设置

对于所有数据集，我们按照 8：1：1 划分训练集、验证集和测试集。Linear-Model 的参数如下：m 为 100，训练的 epoch 为 10，优化器为 SGD。

五、实验结果

RQ1：一个不合理的模型 Linear-Model（通过只考虑哪些标识符出现在代码片段中）能够在 BigCloneBench 数据集中达到好的效果吗？

表 4 展示了 State-of-the-art 的方法和 Linear-Model 在 BigCloneBench 以及 OJClone 数据集的效果。从表中可以看到，Linear-Model 在 BigCloneBench 数据集上可以达到跟 state-of-the-art 方法几乎一致的效果，而在 OJClone 数据集上的效果要明显比 state-of-the-art 方法差很多。在使用 BigCloneBench 数据集验证基于深度学习的语义代码克隆检测方法的有效性时，研究者应当注意 BigCloneBench 数据集中的标识符的影响。

表 4：State-of-the-art 的方法和 Linear-Model 在 BigCloneBench 以及 OJClone 的效果

发现 1：

一个不合理的模型 Linear-Model 在只考虑哪些标识符出现在代码片段中，能够在 BigCloneBench 数据集上达到很好的效果，但是它在 OJClone 数据集上失效。只使用 BigCloneBench 数据集来验证基于深度学习的语义代码克隆检测方法是有问题的，BigCloneBench 数据集需要被改进。

RQ2：State-of-the-art 的方法和 Linear-Model 在 AbsBigCloneBench 数据集上的效果如何？

为了减轻 BigCloneBench 数据集中标识符的影响，我们通过抽象 BigCloneBench 数据集中的一部分标识符来更好的验证基于深度学习的语义代码克隆检测方法的有效性。我们将抽象后的数据集记为 AbsBigCloneBench。我们首先介绍 state-of-the-art 的方法和 Linear-Model 在 Over-AbsBigCloneBench 数据集（只保留程序 AST 中的非终结结点）上的效果，接着介绍怎样修改 BigCloneBench 来得到 AbsBigCloneBench，最后讨论为什么 AbsBigCloneBench 比 BigCloneBench 在验证基于深度学习的语义代码克隆检测方法有效性时更合理。

1. State-of-the-art 的方法和 Linear-Model 在 Over-AbsBigCloneBench 数据集的效果

跟 Mou 等人和 Yu 等人一样，为了进一步研究代码 token 对代码克隆检测的影响，我们在 Over-AbsBigCloneBench 数据集上测试了 state-of-the-art 的方法和 Linear-Model 的效果。表 5 展示了 state-of-the-art 的方法和 Linear-Model 在 Over-AbsBigCloneBench 数据集的效果。当程序 AST 中的终结结点（即代码 token）被移除后，state-of-the-art 的方法明显比 Linear-Model 的方法有效，因为 state-of-the-art 的方法在学习程序结构信息方面比 Linear-Model 更有效。但是移除所有的代码 token 是不合理的，这样会损失大量的程序语义信息。这也是 state-of-the-art 的方法在 Over-AbsBigCloneBench 数据集上的效果相比 BigCloneBench 差很多的原因。

表 5：state-of-the-art 的方法和 Linear-Model 在 Over-AbsBigCloneBench 数据集的效果

2. 怎样修改 BigCloneBench 来得到 AbsBigCloneBench

考虑到保留代码语义信息不变，抽象所有的代码 token 是不合理的。我们只抽象 BigCloneBench 数据集中的部分标识符，包括类型、变量以及函数名，保留了其他 token，比如操作符、基本类型以及成员变量。图 6 展示了一个 BigCloneBench 数据集中的代码片段以及其抽象后的示例。

图 6：BigCloneBench 数据集中的一个代码片段以及其抽象后的示例

AbsBigCloneBench 数据集不同问题之间的标识符的 Jaccard 相似系数为 0.484，对比 BigCloneBench 数据集的 0.038，表明 AbsBigCloneBench 比 BigCloneBench 数据集更少的依赖于标识符。

3. State-of-the-art 的方法和 Linear-Model 在 AbsBigCloneBench 数据集的效果

跟 RQ1 类似，我们比较了 state-of-the-art 的方法和 Linear-Model 在 AbsBigCloneBench 数据集的效果。实验结果如表 6 所示，∆F1 指标指相对表 4 的 F1 值结果的提升或降低。

表 6：State-of-the-art 的方法和 Linear-Model 在 AbsBigCloneBench 数据集的效果

从表 6 可以看到，state-of-the-art 的方法在 AbsBigCloneBench 数据集上的 F1 值明显比 Linear-Model 高。同时 state-of-the-art 的方法在 AbsBigCloneBench 数据集上的 F1 相比 BigCloneBench 几乎没有变化，而 Linear-Model 却有一个明显的下降。分析原因我们认为在抽象了部分标识符后，Linear-Model 只通过考虑哪些标识符出现来进行语义代码克隆检测是无效的。图 7 进一步展示了 state-of-the-art 的方法和 Linear-Model 在 BigCloneBench 以及 AbsBigCloneBench 数据集的 PR 曲线以及 AUC 值，PR 曲线和 AUC 值同样能说明 AbsBigCloneBench 数据集在检测基于深度学习的语义代码克隆检测方法的有效性时更合理。

发现 2：合理的抽象 BigCloneBench 数据集中的标识符能够帮助其更好的分别 state-of-the-art 的方法和不合理的基于深度学习的代码克隆检测方法。抽象 BigCloneBench 数据集中的标识符名字能更帮助其更好的评估基于深度学习的代码克隆检测方法的有效性。

RQ3：State-of-the-art 的方法和 Linear-Model 在交叉实验上的效果如何？

本节我们通过交叉实验来研究模型在 BigCloneBench（AbsBigCloneBench）数据集上训练，在 AbsBigCloneBench（BigCloneBench）数据集上测试的效果，并且提出三个评估技术来检查用来验证基于深度学习的代码克隆检测方法的数据集是否合理。

1. State-of-the-art 的方法和 Linear-Model 在 BigCloneBench 数据集训练，在 AbsBigCloneBench 数据集测试

表 7 的上半部分展示了 state-of-the-art 的方法和 Linear-Model 在 BigCloneBench 数据集训练，在 AbsBigCloneBench 测试的效果相比在 BigCloneBench 测试的效果有一个明显的下降，它表明在 BigCloneBench 数据集上训练的模型，在其他只是标识符不同的数据集上测试将会失效，而根据代码克隆的定义，标识符不同不应该影响代码语义克隆检测模型的效果。分析原因我们认为模型在 BigCloneBench 数据集上训练时，能够通过标识符信息快速达到收敛，模型不会继续深入学习程序的结构信息。因此一旦测试集中的标识符跟训练集不相似，模型的效果就会有一个明显的下降。

表 7：State-of-the-art 的方法和 Linear-Model 在交叉实验上的效果

发现 3：

在 BigCloneBench 数据集上训练的模型在 AbsBigCloneBench 数据集测试无效

2. State-of-the-art 的方法和 Linear-Model 在 AbsBigCloneBench 数据集训练，在 BigCloneBench 数据集测试

表 7 的下半部分展示了 state-of-the-art 的方法和 Linear-Model 在 AbsBigCloneBench 数据集训练，在 BigCloneBench 测试的效果相比在 AbsBigCloneBench 测试的效果几乎没有变化，它表明在 BigCloneBench 数据集上训练的模型，在其他只是标识符不同的数据集上测试依然有效。分析原因我们认为模型在 AbsBigCloneBench 数据集上训练时，不能够通过标识符信息快速达到收敛，模型会继续深入学习程序的结构信息。因此即使测试集中的标识符跟训练集不相似，模型的效果依然会有效。

发现 4：

在 AbsBigCloneBench 数据集上训练的模型在 BigCloneBench 数据集测试依然有效。AbsBigCloneBench 提供了更全面的方法有效性视图，与在 BigCloneBench 数据集训练的模型相比，在 AbsBigCloneBench 数据集训练的模型对标识符名称的依赖程度更低。

3. 三个检查用来验证基于深度学习的代码克隆检测方法的数据集是否合理的评估技术

• 不同方法在抽象前数据集和抽象后数据集的有效性排序应该一致

• 同一个方法，在抽象前数据集训练，在抽象后数据集测试的效果应该一致

• 不合理的方法在抽象后的数据集应该无效

六、总结

我们首先发现 BigCloneBench 数据集的语义代码克隆对使用相似的标识符，而非语义代码克隆对的标识符不相似。接着文章提出了一个不合理的模型（Linear-Model），通过只考虑那些标识符在代码克隆片段中出现来检测代码语义代码克隆。这个不合理的模型可以达到跟其他被验证有效的方法一样的效果。为了减轻这个问题，我们通过抽象 BigCloneBench 数据集中的一部分标识符（类型名、变量名以及方法名）得到 AbsBigCloneBench 数据集。实验结果表明 AbsBigCloneBench 数据集能够更好的验证语义代码克隆检测方法的有效性。并且使用 AbsBigCloneBench 数据集训练的模型在 BigCloneBench 数据集测试依然有效，而使用 BigCloneBench 数据集训练的模型在 AbsBigCloneBench 数据集测试却无效。

作者：于浩、胡星、李戈、李影、王千祥、谢涛; 来自北京大学、华为云 PaaS 技术创新 Lab

PaaS 技术创新 Lab 隶属于华为云(华为内部当前发展最为迅猛的部门之一，目前国内公有云市场份额第二，全球第五)，致力于综合利用软件分析、数据挖掘、机器学习等技术，为软件研发人员提供下一代智能研发工具服务的核心引擎和智慧大脑。我们将聚焦软件工程领域硬核能力，不断构筑研发利器，持续交付高价值商业特性！加入我们，一起开创研发新“境界”！（招聘接口人：guodongshuo@huawei.com; huwei18@huawei.com）

参考文献

1. Chanchal Kumar Roy and James R Cordy. A Survey on Software Clone Detection Research. Queen’s School of Computing TR 541, 115 (2007), 64–68.

2. Stefan Bellon, Rainer Koschke, Giulio Antoniol, Jens Krinke, and Ettore Merlo. Comparison and Evaluation of Clone Detection Tools. IEEE Transactions on Software Engineering 33, 9 (2007), 577–591.

3. Jeffrey Svajlenko, Judith F. Islam, Iman Keivanloo, Chanchal K. Roy, and Mohammad Mamun Mia. Towards a Big Data Curated Benchmark of Inter-Project Code Clones. In Proceedings of the 30th International Conference on Software Maintenance and Evolution (ICSME), 2017, 476–480.

4. Hui-Hui Wei and Ming Li. Positive and Unlabeled Learning for Detecting Software Functional Clones with Adversarial Training. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018, 2840–2846.

5. Hao Yu, Wing Lam, Long Chen, Ge Li, Tao Xie, and Qianxiang Wang. Neural Detection of Semantic Code Clones Via Tree-Based Convolution. In Proceedings of the 27th IEEE International Conference on Program Comprehension (ICPC), 2019, 70–80.

6. Hao Yu, Xing Hu, Ge Li, Ying Li, Qianxiang Wang, Tao Xie. Assessing and Improving an Evaluation Dataset for Detecting Semantic Code Clones via Deep Learning. TOSEM, 2022, Accepted.

7. IJaDataset2.0. January 2013. Ambient Software Evoluton Group. http://secold.org/projects/seclone.

8. https://github.com/c2nes/javalang.
   

9. Jian Zhang, Xu Wang, Hongyu Zhang, Hailong Sun, Kaixuan Wang, and Xudong Liu. A Novel Neural Source Code Representation Based on Abstract Syntax Tree. In Proceedings of the 41st IEEE/ACM International Conference on Software Engineering (ICSE), 2019, 783–794.

10. Wenhan Wang, Ge Li, Bo Ma, Xin Xia, and Zhi Jin. Detecting Code Clones with Graph Neural Network and Flow-Augmented Abstract Syntax Tree. In Proceedings of the 27th IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER), 2020, 261–271.

11. Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin. Convolutional Neural Networks over Tree Structures for Programming Language Processing. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), 2016, 1287–1293.

​​​​​点击关注，第一时间了解华为云新鲜技术~