南京大学智能软件工程实验室
iselab.cn
引言
一直以来，代码克隆检测在软件维护、安全和质量保证的领域都是一个重要的关注点。尽管目前已经有一些方法结合了语法和语义的特征，但是它们忽略了函数之间的调用关系，这可能会对功能代码克隆检测产生不利的影响。本文提出了一个功能的代码克隆检测工具 FCDetector。FCDetector 首先绘制了函数调用关系图，然后通过分析抽象语法树和程序控制流图来获取代码的语法、语义特征。最后，基于这些特征的结合，FCDetector 使用深度神经网络模型来进行代码克隆检测。我们将 FCDetector 用于一个大型的真实数据集 OJClone 进行实验，实验证明 FCDetector 可以有效检测功能的代码克隆。关于 FCDetector 的视频解说可以在https://youtu.be/woZuOOIZ3Ms进行观看，工具的应用可以在https://github.com/shiyy123/FDetector.获取。
1 介绍
代码克隆也被称为重复的代码。重复代码是源代码片段，该代码片段在一个程序中或在同一实体拥有或维护的不同程序中多次出现。自动识别重复代码的过程就是代码克隆检测。
代码克隆在很多方面都是有害的，可能会对软件维护、安装、质量产生负面影响。如果一段有缺陷的代码被克隆到其他系统中，可能会产生潜在威胁。因此，代码克隆检测在软件工程领域吸引了越来越多研究者的关注，也得到了广泛的应用。
代码克隆检测有四种基本类型：类型一：除了空格、换行和注释，完全相同的代码片段；类型二：除了变量和参数，基本相同的代码片段；类型三：除了有部分新增或删减的代码段，其他部分完全相同的代码片段；类型四：代码片段实现的功能相同，但语义结构不相同。其中针对类型四的代码克隆检测被视为功能的代码克隆检测，它是最为复杂的一种克隆检测类型。
FCDetector 主要针对类型四的代码克隆检测，即功能性的代码克隆检测，此类检测在软件工程领域有着广泛的用户场景。比如，如果发现某个功能的代码段会导致系统出现漏洞缺陷，那么检测出来的克隆代码也很可能存在类似的缺陷，通过代码克隆检测可以快速定位代码缺陷。在代码推荐相关的应用场景下，代码克隆也有着关键性的应用，比如有大量代码需要给专家进行评审，可以根据 FCDetector 挑选出功能类似的代码，推荐同一个专家，这样可以使专家更好的理解代码，提高评审效率。
尽管目前已经有了许多代码克隆检测的技术，但是大部分都不能很好的检测“功能”的代码克隆。因为针对功能的代码克隆较为复杂，通过比较类似标识符的基本特征相似度很难检测出功能代码克隆。除此之外，目前可以检测功能代码克隆的方法，尝试在函数级别上解析语法和语义特征，但是他们没有很好的分析函数之间的调用关系，这可能使得克隆检测的效果不佳。为了解决这一问题，本文提出 FCDetector 这一工具，FCDetector 首先绘制函数调用图（(Function Call Graph，FCG）来分析函数之间的调用关系，然后使用抽象语法树（Abstract Syntax Tree，AST）和控制流图（Control Flow Graph，CFG）来分别抽取语法和语义的特征。最后 FCDetector 使用一个深度神经网络模型来检测代码克隆。基于 OJClone 数据集的实验结果表明，FCDetector 可以有效的检测功能的代码克隆。
2 FCDetector 工具
FCDetector 的整体流程图如图 1 所示。FCDetector 的流程图主要包含 5 个主要部分：（1）解析 FCG，（2）解析 AST 和 CFG，（3）使用嵌入技术生成特征向量，（4）训练 DNN 分类模型，（5）功能代码克隆检测。
为了识别具有功能性克隆的代码片段，FCDetector 首先分析 FCG 来获取函数之间的调用关系，然后将函数级别的 AST 和 CFG 进行结合，分别生成整段代码的 AST 和 CFG。为了将这些特征转换为向量，FCDetector 使用嵌入技术来解析这些特征，在组合了特征向量之后，FCDetector 训练了一个 DNN 模型来检测功能代码克隆。
图 1 系统流程图
2.1 解析 FCG
像 C++这样的高级程序设计语言是灵活多变的。不同的代码结构可以实现同样一个功能，这使得功能的代码克隆检测变得复杂和困难。对于机器而言，理解函数之间的关系是十分困难的。所以非常有必要解析代码结构特征，来映射函数之间的调用关系。
FCG 是一种图结构，它可以很有效的体现出函数之间的调用关系，从而分析出代码段中的函数结构。FCDetector 使用一个 C/C++代码分析工具 Joern 来解析 FCG，函数调用关系使用一个三元组来表示：<调用函数 id,调用语句,被调用函数 id>，其中调用函数 id 是调用函数的标识符，被调用函数 id 是被调用函数的标识符。
我们根据真实的开源代码数据集，总结了 6 种常见的函数调用图，如图 2 所示。关于使用不同函数调用图来实现同一功能的具体例子，将在第三章中展示。使用 FCG 连接函数的 CFG 的相关规则，在 2.2 章节阐述。
图 2 六种函数调用关系图
2.2 解析 AST 和 CFG
FCDetector 首先使用 Joern 工具解析每个函数的 AST 和 CFG。每个函数的 AST 可以被视为一个树的结构。假设我们有一段代码 C，和它的 AST 根节点 Nroot。对于每个树形结构，我们可以使用先序遍历的方法，将 AST 的叶子节点排成一串节点，每个函数的语法特征可以表示为 Tm = {node1,node2,...,noden}，其中 node1 是 Tm 中的每个子节点。
每个函数的 CFG 可以表示为一个图的结构 Gm = (V,E)，其中 V 是节点的集合，E 是边的集合。
根据图 2 展示的函数调用关系，FCDetector 可以将函数的 CFG 链接起来，形成整段代码的 CFG。具体链接规则如下。对于第一种情况，整段代码的 CFG 和函数的 CFG 是一样的；对于第二种情况，调用语句的节点需要增加一条边到入口节点；对于第三种情况，A 函数的父节点要指向 B 函数的入口节点，而且所有的孩子节点都要指向 B 函数的出口节点；第四、五种情况和第三种相似，除了链接另一个函数调用语句的边需要重新调整。第六种情况是两个单独的函数，所以需要分别处理各自的功能对应的 CFG。
根据 2.1 章节种提到的函数连接方法，对于每个代码片段，FCDetector 会将函数的 AST/CFG 连接成整个代码段对应的 AST/CFG。通过使用 FCG 来获取函数之间的调用关系，FCDetector 可以准确地描述每个代码段对应地功能。
2.3 使用嵌入技术生成特征向量
为了将特征转换为特征向量，并用于机器学习模型，FCDetector 使用词嵌入技术来编码 AST 以获取语法特征，使用图嵌入技术来编码 CFG 以获取语义特征。
词嵌入是一种提取有意义的语法语义特征的强大的方法，词嵌入技术可以将一个词转换成一个固定长度的向量，这对于数学处理运算是非常有帮助的。因为函数抽象语法树 Tm 的每个节点 nodei 都可以被视为一个单词，所以 FCDetector 使用词嵌入来编码 Tm，从而获取语法特征。
通过使用词嵌入 Word2vec 方法，Tm 中的每个节点都可以被简化为一个单词，进而计算出它们对应的特征向量 Vnode。然后每个函数的语法特征可以被表示为一个固定长度的向量 Vm=averge(Vnodei),i={1,2,...,Nm}。其中 Nm 是每个函数中所有的节点个数。
图形嵌入旨在在保持尽可能多的图形信息的同时，在低维空间中表示图形。通过使用图嵌入技术，图中的每个节点可以表示为一个向量，FCDetector 用图嵌入 HOPE 技术来转化 CFG 为语义特征向量。通过使用 HOPE，每个节点可以被表示为一个固定长度的向量 Vvertex。
最后，语法和语义特征向量可以被表示为
V1 = average(Vmi),i = {1, 2, ..., Nf}
V2 = average(Vvertexi),i = {1,2,...,Nf}
其中 Nf 是每个代码片段中函数的总数。
2.4 训练 DNN 分类模型
FCDetector 将语法和语义特征向量的结合做为前向神经网络的输入。DNN 模型的结构如图 3 所示。FCDetector 将 V1，V2 用两种不同的顺序进行结合，分别为[V1,V2]和[V2,V1]，这是为了消除输入数据对称性的影响。
图 3 DNN 模型图
DNN 模型将语法语义特征的结合做为输入，每个语法和语义的特征用 16 维度的向量表示。总共的输入向量维度是 33（16+16+1），增加的这 1 维度向量是标签，标签有两个值：0 或 1，代表是否是代码克隆。
为了将输入转换为神经节点，隐藏层使用线性变换，然后压缩非线性。DNN 模型使用反向传播，根据训练集调整权重矩阵 W。 最后有一个 softmax 层，它将功能克隆检测转换为分类问题。
2.5 功能代码克隆检测
假设有两个代码段的特征向量 V1 和 V2，特征之间的关联性可以视为两者之间的距离 d=|V1-V2|，然后我们以此视为他们相似程度的输出。
在训练好所有参数后，训练好的模型会存储下来。下一次，源代码的特征向量可以直接被用于神经网络进行克隆检测，无需再训练神经网络模型。输出的结果是 0 或 1，表示是否有功能的代码克隆。
3 实验评价
FCDetector 的实验评价包含 3 个部分。我们首先介绍实验的环境，然后将 FCDetector 与另外五种现有的克隆检测工具进行比较。最后，我们展示了一个功能的克隆检测例子，来说明 FCDetector 的效果。FCDetector 具体的用法和实验结果在视频中展示。
3.1 实验配置
我们使用了一个开源的 C++数据集 OJClone 来对 FCDetector 进行实验和评估。OJClone 包含 104 个算法任务，每个算法有 500 个不同学生提交的不同版本的代码。对于同一个算法题目，不同版本的代码就可以被视为功能的代码克隆。我们随机选择了 35 个题目，每个题目随机选取 100 个代码片段做为数据。我们使用 Intel i7 4.0GHz 4 核 CPU 和 GTX1060GPU 进行实验。
3.2 与其他代码克隆检测工具的比较结果
我们将 FCDetector 与其他 5 中现有的代码克隆检测工具进行比较，指标为精确率（Precision，P），召回率（Recall，R），和 F1 分数。因为 OJClone 数据集主要属于功能的代码克隆检测，克隆检测的效果可以体现这些工具在功能代码克隆检测的能力。表 1 展示了这 6 种工具的精确率、召回率和 F1 分数。初步的实验结果表明，FCDetector 可以有效的检测功能性的代码克隆。
表 1 不同代码克隆检测工具在 OJClone 上的效果
3.3 使用 FCDetector 进行功能性的代码克隆检测示例
图 4 展示了三个代码片段示例，因为示例 1 和示例 2 的函数调用关系完全不一样，他们可能看起来不像是克隆的代码，但他们实现的功能是完全一样的，因此他们是功能性的代码克隆。示例 1 的函数调用可以与图 2 中的（1）匹配，而示例 2 的函数调用可以与图 2 中（2）匹配。对于示例 1 来说，整个代码段的 CFG 就是函数的 CFG，而对于示例 2，整个代码段的 CFG 就是图 4（d）展示的样子。不同的函数调用关系可能会导致常见的克隆检测工具产生误报。因为 FCDetector 考虑到了函数之间的调用关系，它可以准确的检测出这两段代码之间存在功能性的克隆。
单独依靠 CFG 不足以检测功能性的代码克隆，示例 1（求和方法）和示例 3（求乘积方法）的代码文本基本是一样的，他们的 CFG 在结构层次上也是一样的，但是他们表示完全不同的功能，这两种代码段的区别潜藏在循环体的 AST 中。这两个 AST 的区别在于一个符号的不同，如图 4（e）所示，FCDetector 会判定示例 1 和示例 3 不是功能性的克隆检测，是因为它结合了源代码语法和语义的特征。
图 4 代码克隆检测示例
5 总结
在这篇文章中，我们提出了一个功能性的代码克隆检测工具 FCDetector，它运用 FCG 来结合了函数的 AST/CFG，生成出每个代码段的 AST/CFG。然后我们使用嵌入技术来解析语法和语义特征。最后，我们训练了一个 DNN 模型来进行功能性的代码克隆检测。在 OJClone 数据集上的初步实验结果表明，FCDetector 可以有效地检测功能性的代码克隆。基于 FCDetector，我们可以在代码质量管理、代码重构等领域展开更加长远的研究和探索。
致谢
本文由南京大学软件学院 2020 级硕士刘子夕翻译转述。
感谢国家自然科学基金（61932012，61802171，61772014）支持！
本文来自投稿，不代表本人立场，如若转载，请注明出处：http://www.souzhinan.com/kj/290528.html