https://m.toutiao.com/is/JWhQ522/
代码克隆检测是软件维护和进化的一个重要问题。 许多方法考虑结构或标识符，但现有的检测技术都没有对两种信息来源进行建模。 这些技术还依赖于通用的、手工制作的特性来表示代码片段。 我们介绍了基于学习的检测技术，其中表示源代码中的项和片段的所有内容都是从存储库中挖掘出来的。 我们的代码分析支持一个框架，它依赖于深度学习，用于自动将在词汇层面挖掘的模式与在句法层面挖掘的模式联系起来。 我们从软件维护人员的角度评估了基于学习的代码克隆检测方法的可行性。 我们在 8 个真实世界的 Java 系统中对 398 个文件和 480 个方法级对进行了采样和手动评估；93%的文件和方法级样本被评估为真正的阳性。 在真正的阳性中，我们发现对映射到所有四种克隆类型。 我们将我们的方法与传统的面向结构的技术进行了比较，发现我们基于学习的方法检测到克隆，这些克隆要么是未被检测到的，要么是由突出的工具 Deckard 进行的次优报告。 我们的结果证实了我们基于学习的方法适合克隆检测和研究人员的一种可行的技术。
关键词：代码克隆检测，机器学习，深度学习，神经网络，语言模型，抽象语法树
抽象是软件工程(SE)中最重要的一个词。因此，软件仓库充满了抽象，这给软件工程师提供了通过分离关注点和在不同级别处理不同的细节来管理复杂性的能力。所有粒度级别的抽象都由实现来补充。 这些实现可以从零开始开发，也可以从的现有代码片段中克隆。如果现有代码为实现提供了一个合理的起点，那么软件工程师可以通过复制和粘贴片段来克隆代码。另一种可以在软件系统中引入克隆的方法是，工程师可能会在不知不觉中开发出类似于现有实现的另一种实现。复制和粘贴代码并随后修改复制的片段可能会产生文本上相似的代码片段，其中相似之处可以用它们的语法来描述。 另一方面，当工程师在不知情的情况下开发一个与已经存在的东西相似的实现时，他可能会创建功能相似但在语法上不同的克隆。
检测克隆是软件维护和进化的一个重要问题。虽然先前的工作已经证明了代码克隆的几个不利影响，但克隆并不一定是有害的。克隆也不一定重构。然而，在许多应用程序中，自动检测两个片段相似的能力是至关重要的，例如检测候选库、帮助程序理解、检测恶意软件、检测剽窃或版权侵权、检测基于上下文的不一致性和寻找重构机会。在本文中，我们的新方法使用于一个新的，基于学习的范式挖掘内部源代码表示。
克隆检测过程开始于将源代码转换为适合于评估相似性的表示。例如，要表示代码片段，传统的基于树的克隆检测工具依赖于与泛型编程结构紧密耦合的人工特性。在这方面，植根于标识符的域信息被丢弃，打破了在词汇层面和句法层面上可以学习的信息之间的联系。 此外，声明特性（例如编程构造的发生计数）将大量先验知识应用于如何自动表示片段。然而，可以合理地预期，来自不同应用领域和处于不同开发阶段的软件系统会产生独特的模式源代码，这将揭示问题，如代码克隆检测。然而，这些模式并不一定是使用通用特征空间的方法来获取的，而这些有用的潜在特征可以被描述的唯一方法是使用所学习的代码的表示，即学习表示本身。自动学习表示，或“表示学习”，并不需要将原始数据（如源代码）转换为适当表示的先验知识，而是使检测过程中的人工步骤自动化。挖掘有效的源代码特征，分析源代码中标识符的语言，分析句法模式，以及能够适应不断变化的存储库的工程方法是 SE 研究的基本问题。将克隆检测方法工程化，它考虑了所有这些问题，是我们工作的动力。 我们的关键结果是一套融合和使用的新技术。 我们融合了代码中结构和标识符的信息，并使用软件仓库中的数据来自动化指定转换的步骤。
我们对用于代码克隆检测的表示代码片段的关键洞察力是双重的。首先，我们的方法将片段中的项映射到连续值向量，使得源代码仓库中以类似方式使用的项映射到类似向量。 从项到向量的这种转换与基于 token 的技术(SEC)使用的 token 抽象在根本上是不同的。 其次，我们的基于表示学习的方法旨在学习不同粒度级别的片段的鉴别特征而不是依赖于直观的（但有限的）特征，这些特征是围绕一种语言的结构元素设计的，比如基于树的技术。
我们的方法的本质可以追溯到抽象和处理 SE 中不同级别的不同细节。 我们建议在软件构建中利用这一指导原则。因此我们的源代码建模技术在代码中的项结构中利用基于经验的模式，就像语言建模在项序列中利用模式一样。为此，我们将词汇分析与递归神经网络(SEC)配对和递归神经网络的句法分析。将编译器前端与深度神经网络和深度学习(SEC)耦合的目的是提供一个框架，将用于在词汇层面挖掘的模式与在句法层面挖掘的模式联系起来。 克隆检测是该框架的一个重要应用。
我们分两部分阐述基于学习（如图 1 所示）的方法。 第一部分描述如何使用特定类型的语言模型 Rt NN 将片段中的每个项进行嵌入。第二部分描述了我们如何使用语言的语法和使用 Rv NN 实现的递归学习过程来编码任意长的嵌入序列来描述片段。我们不打算指定在不同粒度级别上建模这些片段的特性；使用深度学习的目的是自动化这个人工步骤。
一个 RTN 是一个深度学习模型，非常适合在源代码语料库中用词汇表 V 建模项序列，其中|V|=m。设 n 为用户指定的超参数，为隐藏单元的个数。一个 RtN 包括输入层 x∈Rm+n、隐藏层 z∈Rn 和输出层 y∈Rm。一个 RTN 的深度归因于重复，其中隐藏状态被复制回输入层，因此 RTN 中的输入层凝集了当前项 t(I)和先前的状态 z(I1)：
该输入向量乘以矩阵[α，β]∈Rn×(mn)，并传递给非线性向量函数 f，即（2）。，
这个状态向量乘以另一个矩阵 γ∈Rm×n，并归一化以计算后验项，等式（1）-（3）说明了 Rt NN 的表示，等式（4）突出其深度，使其组成更加明确，以显示其输出是如何将先前输入转化为高度非线性函数。
θ={α，β，γ}的模型是用交叉熵准则训练的但在这里省略了技术细节。在软件语言建模中，模型的输出 y(i)可用于预测一行代码中的下一个项，即 argmaxkyk(i)。然而，深度学习模型不仅仅是对他们的输出有用，对他们的内部成分也是有用的。在本工作中，基于 RtNN 的软件语言模型最重要的组成部分是在等式 2 中的嵌入矩阵 α∈Rn×m。每列 α 对应一个项。α 的列空间包括对 V 中每个项的语义表示，使得模型将相似向量归因于语料库中以类似方式使用的项。给定的每个项在呈现给模型时都是 one-hot 编码的，矩阵向量乘积 αt 在方程中。 （2）相当于将 V 中的任何项映射到 α 中的一列，从而将片段中的项序列映射到嵌入序列。因此，为了表示代码片段，我们编码任意长的嵌入序列。
我们基于学习的原型不同于传统的技术。给定一个片段，信息将从终端节点通过非终端节点流向分层结构的根(图 3–4 所示)。这种自下而上的信息流就像在传统的面向结构技术中计算特征向量的过程，或者在基于度量的技术中计算度量。然而，我们挖掘终端节点(SEC)的向量表示和非终端节点的特性不是基于指标的发生计数(SEC 2.1)。特征空间是通过学习区分片段(SEC)来得到的。此外，在自下而上的遍历中合成信息以计算特征向量或度量之后，传统技术终止并将源代码表示传递给匹配检测算法以类似的片段。在某种程度上，我们认为自下而上的信息流动是必要的，但不足以充分代表代码片段。因此，我们的终止条件在根本上是不同的。在我们的方法中，当模型收敛到一个解决方案时，挖掘表示的过程就会终止，这样它就可以在不同的粒度级别(Eq)上充分地表示编程构造。这一标准，词汇水平的信息从终端传输到代码结构的根部，监督信号从根通过结构广播传递回来的这一标准是我们方法的核心。
2.2.1 从 AST 到完全二元树
编译器的前端将程序分解为各个组件，并根据语言的语法生成中间代码。这些组件被称为编程结构，而无上下文语法指定编程结构的语法。AST 是一种表示程序的层次句法结构的中间代码。最终，我们的目标是指定基于学习的技术来编码任意长的词汇元素序列。由于 AST 中的非末端节点包含词汇元素的序列，假设每个 AST 节点都有一个特殊的属性 repr 用于存储向量表示，表示节点的 code，以及节点包含的词法元素序列。我们对代码的挖掘方式使相似的序列具有相似的代码。一种基于学习的技术是基于 AST，一种树表示，它可以具有任意数量的级别，包括具有任意数量子节点的节点，但这里存在问题。我们的学习模型只接受固定大小的输入，因此我们将 AST 转换为一个完整的二叉树来固定输入的大小，并将学习模型递归地应用于不同层次的结构建模。
一个 AST 节点的度要么为零，要么为一，要么为二，或者大于二。根据定义，度为零或两个的 AST 节点满足全二叉树中节点的性质，但必须将植根于度为或大于两的节点的子树转换为完全二叉树。我们转换的第一步是扫描 AST 并删除元数据(例如，Java 片段的 AST 中的 Javadoc 节点)以及空匿名类声明、空数组初始化器、空块、空类、空编译单元和空语句的节点。当我们扫描 AST 以寻找空节点时，我们还会寻找具有相同父节点的相同文字类型的序列。 学习者将对 AST 节点的成对组合进行编码；因此，我们通过访问非终端节点、检查它们的子节点和将相邻的、相同的文本类型归纳到一个实例来避免对相同的文本类型进行编码。如 true，truetruetrue 等。所有都变成 true，这些序列也有助于控制二叉树的深度，从而有可能失去一些分辨率。
接下来，为了获得二叉树，需要对植根于度大于两个节点的子树进行重组，以便对子树进行适当的排列。 我们定义了一种基于语法的方法，针对每个非终端类型，系统地重组度为 2 节点的子节点。例如，如果语句实例可以有两个或三个子节点。对于这种非终端类型，我们定义了一个新的语法，它只产生二叉树子树（假设表达式和语句节点的语法），因为每个主体都有一个或两个构造。为此，我们引入了新的人工非终端类型，如分支，从而增强了语言的语法：
:=
:= [ ]
对于具有任意最大度的非终端类型（例如块节点），我们将它们的子节点组织成二进制列表。由于 Block 节点的子节点由一系列语句表示，所以我们使用一个新的乘积，其中块节点可以具有递归语句列表的形式
:= {}
:= []
替换了原来的乘积。
:= {}
在我们使用新语法对每个度为 2 的实例进行转换后，我们从原始 AST 中获得了一棵二叉树，但是二叉树可能是也可能不是完整的二叉树，因为节点可能有一个和唯一一个子树。换句话说，我们需要处理度为 1 的节点。 我们以自顶向下的方式遍历二叉树，当我们到达度为 1 的节点时，我们将节点及其子节点合并为一个节点。然后，我们递归地继续从新合并节点的传输。自上而下的访问确保具有一个和只有一个子节点的父节点的实例最终被合并到一个节点中。我们的合并过程由一个优先列表来控制，该列表为每个非终端类型分配一个值。 合并两个节点时，优先级值用于决定是否将当前节点类型或子类型分配给新节点。
Tab 1 显示了我们定义的优先级列表，其中列表中较高的类型具有较高的优先级。 当两个节点具有相同的优先值-这可能是两个其他类型节点的情况-合并保持父节点。这个设计决策来自于这样的观察，即父节点通常比子节点更具有表现力和代表性。我们根据几个经验观察确定了清单。特别是，有了这个表格，我们确保以下结论：
1.
某些级别的粒度受到保护，并且从不被其他节点覆盖。
2.
当合并两个节点时，更多的表达类型优先于更一般的类型，如父级表达式和块。
3.
人工非终端节点，在前一步中创建，用于处理度为 2 的节点，永远不会取代原始语法中的非终端类型。
在 SE 应用程序中，保护某些级别的粒度的含义是显而易见的，例如克隆检测（例如），我们的方法能够在定义良好的抽象边界上表示并报告克隆，以更好地支持软件维护人员。
2.2.2 从完全二叉树到 Olive 树
现在，我们描述如何将一个完整的二叉树转换为我们非正式地称为 Olive 树的树，这是将中间代码转换为一个完整的二叉树，然后用挖掘的表示来注释这棵树的结果，考虑 int foo=42 的语句。此语句的 AST 已经是图 3 1-5 中描述的完整二叉树。再次假设每个 AST 节点都有一个特殊的属性 repr，例如，repr 在图中存储 SimpleName 的表示。我们使用其词法元素为每个终端初始化此属性，以选择嵌入 α 矩阵中的相应列。例如，如果词法元素 int 映射到 α 的 JT H 列，则在图中为 PrimitiveType 初始化，使 1.repr=α。对于非终端节点，如图中的可变声明片段和可变声明语句，此属性初始化为 NULL。在这个节点，我们使用了在词汇层面挖掘的模式初始化嵌入序列。接下来，我们使用自动编码器组合嵌入。自动编码器的典型形式是具有一个输入层 x、一个隐藏层 z 和一个输出层 y 的神经网络，其中 ε=[εℓ，εr]∈Rn×2n 是 ε 编码器；δ=[δℓ；δr]∈R2n×n 是 δ 编码器；βz∈Rn 和 βy∈R2n 是 βiases. 在词法级别上挖掘的模式与在句法级别上挖掘的模式结合的连接是 n，这是相同的 n，它控制了 Eq 中隐藏层 z 的大小。g 是一个非线性向量函数，h 通常是恒等函数。我们声称我们的学习模型只接受固定大小的输入，这促使 AST 转换为完全二叉树。具体地说，自动编码器的输入是两个兄弟节点代码的向量，即 x=[xℓ；xr]∈R2n。例如，计算图中可变声明片段的表示。我们将向模型展示 x = [2.repr; 3.repr]。限制隐藏层的大小(即|z|=n<2n)迫使模型学习其输入的压缩表示。这个压缩，z 在等式 5 中。作为我们存储在非终端节点 repr 属性中的挖掘表示。本质上，该模型将输入嵌入到低维特征空间中，就像语言模型嵌入一个热项向量(SEC)一样。换句话说，语言模型将词汇元素转换为嵌入，自动编码器将任意两个嵌入压缩到与术语嵌入具有相同维数的向量。 输出 y=[xℓ；xr]∈R2n 被称为模型对输入的重建。训练模型涉及测量原始输入向量与重建之间的距离，如果模型能够有效地学习输入的判别特征，那么它就能够概括地重建从输入域采样的任何输入向量。
我们刚刚演示了传统的自动编码器如何压缩两个词汇元素的适度序列，但为了支持克隆检测，我们学习了更多的代码。由于树中每个节点的代码具有相同的大小，我们可以递归地应用自动编码器 RvN，在不同的级别上对完整的二叉树进行建模。我们用来压缩图中简单名称和数字文字的自动编码器。 只要变量声明片段的代码与原始类型的代码合并，并提交给同一模型以计算变量声明：5.repr = g([εℓ, εr][1.repr; 4.repr] + βz).的代码，就可以递归地应 3。 与以前一样，为了训练模型，我们解码表示(即 y=h([δℓ；δr][5.repr]βy)，并将重建与输入(即 x=[1.repr；4.repr])进行比较，以调整权重。但现在的误差是（加权）和在所有的重建错误中，较大的编程结构将对片段的表示产生更大的影响。例如，可变声明片段对调优 5.repr 的影响大于原始类型。在计算前向传递中的每个非终端节点的代码后，通过结构算法的反向传播计算（全局）误差函数相对于模型组件的偏导数。然后利用标准方法对误差信号进行优化。 一旦深度学习模型在几个阶段之后收敛，我们就用表示来构建完整的二叉树来产生 Olive 树。
为什么深度学习是克隆检测的好方法？分析标识符的技术通常使用潜在语义分析(L SA)。深度学习比 LSA 有三个明显的优势。首先，自动编码器是非线性降维器。第二，递归地应用自动编码器对输入进行几个非线性变换，而不是使用输入的一个线性分解。三，递归考虑项的顺序。另一方面，分析结构的技术会丢弃标识符，我们使用这些标识符作为先验知识。我们的学习框架不是使用通用的结构元素，而是基于标识符和文字类型的鉴别能力来表示它，因此即使语法只有弱相似，深度学习仍然可以识别术语之间的相似性。
Socher 等人将递归自动编码器应用于自然语言句子进行情感分析。Socher 工作的新奇之处在于半监督增强，旨在训练模型，用句子级别的标签来分类句子的情感。我们使用递归自动编码器来学习任意大小的代码片段的表示，实例化为句法层面属性。一个关于我们使用的属性性质的评论：用编译器的说法，一个属性（即与编程构造相关联的数量）被认为是“合成的”或“继承的”，但我们在这项工作中挖掘的属性在技术上也不是。节点的合成属性是从节点和节点子代的属性值计算的，而继承属性是从节点、其父属性和其兄弟姐妹计算的。 然而，在我们的工作中，属性是以自下而上的遍历方式合成的，但是训练算法将以自上而下的方式调整属性，因为一般编程构造的错误在它们的成分之间被划分。
2.2.3 为克隆检测的 Olive 树
一旦模型被训练，推理就很简单。识别克隆对等于比较两个片段的表示，这可以在不同的粒度级别。具体来说，给定一个片段，我们构建 AST，然后将 AST 转换为一个完整的二叉树。如果完全二叉树中有 k 个终端节点，则会有 k 个非终端节点。因此，编码序列需要 k1 矩阵向量乘法，然后应用向量函数导出片段的表示。当然，完全二叉树的拓扑控制节点表示组合的顺序。对于代码克隆检测的具体应用，所有需要的都是一个阈值，用于比较两种表示，以确定它们的倾向是否将它们归类为克隆对；阈值完成克隆检测规范。
2.2.4 克隆检测的贪婪组合
在这里，我们借鉴了 Socher 等人提出的方法。 以贪婪的方式组合成表示对。一，总结了训练程序。对于每个片段，我们构建 AST，而不是像以前一样转换 AST，我们编码每一对相邻的终端节点。 然后选择重建误差最低的对等式 7 先编码。第四，第一次迭代推导出两个代码；该模型在重构[1.repr；2.repr]方面做得更好，而不是可变声明片段[2.repr；3.repr]。 下一次迭代将所选对替换为新的父对，然后再次计算成对重建错误，选择误差最小的对。 如果有 k 个终端节点覆盖片段，则此过程重复，直到计算出 k1 非终端节点的表示为止。 一旦自组织树完成了，模型就像以前一样通过结构算法和标准优化方法进行反向传播训练。
一旦模型被训练，推理再次是直截了当的。给定一个片段，我们构建 AST，然后贪婪地编码节点，直到为包含该片段的节点派生代码。该代码与其他贪婪编码的片段进行比较，使用阈值来检测代码克隆。关于贪婪编码节点的训练和推理过程的一个重要注意是，我们不需要构建 AST。事实上，由于语言模型存储了语料库中每个术语的嵌入，我们可以直接在具体的片段上操作。我们构建 AST 的原因是为了过滤词汇元素，如标点符号，以控制我们用于训练和推理的树的深度。
这两种组合方法有一些显著的差异。 首先，对于基于 AST 的方法，克隆粒度通常是“固定的”，即它结合了句法边界内的片段。另一方面，对于贪婪方法，克隆粒度通常是“自由的”，即它结合了没有句法边界的片段。第二，与基于 AST 的方法相比，训练需要更多的计算资源。 基于 AST 的方法有 k1 矩阵向量乘积来计算，而贪婪方法有 k1（一般）密集矩阵矩阵乘积来计算。 第三，由于贪婪方法是在没有明确语法知识的情况下训练的，因此不需要构建 AST，因此模型可以更好地处理语法无效的片段。 尽管存在差异，但这些方法共同使代码克隆检测的新的基于学习的范式具体化。
关于用于克隆检测的扩展深度学习：在这里，我们借鉴了机器学习社区在语义散列方面的工作，并展示了在深度学习者中看似无害的机器学习细节如何在 SE 中产生重要的实际影响。我们描述了 g（等式 5）作为非线性向量函数。g 被称为“激活”函数，在实践中使用了许多激活函数，例如 g=tanh。模型是用小的随机权重初始化的，这意味着“预激活”，例如，εxβz 在等式 5 中，位于 tanh 的（近似）线性部分。随着模型的训练，权重增加，并引入非线性。当使用 tanh 激活时，权重可以正向或负向远离零。例如，我们通过从（近似）unif（0.08，0.08）中采样并使用 tanh 激活来初始化 RvNN。在对模型进行训练后，我们对每个系统中的每个文件进行编码。图 5 显示特征的相对频率直方图；我们使用权重衰减进行正则化。分布在 16 个圆锥形显示了一个有趣的双峰结构。假设我们选择了一些 λ∈R，所以特征大于 λ 映射到 1，特征小于或等于映射到 0。λ 将连续值特征向量转换为二进制码，允许我们测量不同度量空间中片段的相似性。 因此，给定一个片段，可以通过在片段周围寻找片段中的其他片段来检测克隆，这种计算可以通过现代计算机体系结构上的快速算法来优化。 二进制码不仅能实现快速搜索，因为测量相似性等于找到只相差几位的片段，而且它们还需要更少的内存这是海量软件库的关键问题。在进行实证研究时，我们注意到 JHotDraw 中大量的 I 型和 II 型克隆，因此我们使用 λ=0 对 JHotDraw 的（贪婪）文件级特征向量进行了转换。 30 个样本中有 14 个（47%）被评估为真正阳性(所有 III 型克隆)，这比测量与 ℓ2 的相似性要糟糕得多。为了调整二元特征向量的模型，我们计划用不同的学习启发式进行实验。 Salakhutdinov 和 Hinton 报告说，语义散列（以生成为基础的方法）在对自然语言文档进行散列的实验中比 LSH 快得多。
类型预测：图 6 展示了如何用另一个解码器对原始模型ε、δ、βz、βy进行增强，δτ 训练以预测给定其代码的编程构造或片段的类型 τ。Socher 等人使用类似的设计，以半监督的方式分析情绪与人工生成的多项式分布。我们的增强不需要像情感任务那样人工生成粗粒度标签，因为这里的类型是由编译器自动估算的。例如，在图中如果我们将[2.repr；3.repr]呈现给模型，那么我们期望 ˆτ=变量声明片段。对标准的唯一改变是添加一个表达式来计算(交叉熵）错误分类成本。
我们引入了一种全新的检测代码克隆的方法。我们基于学习的范式在至少两个重要方面与传统的面向结构的技术不同。首先，术语-包括标识符-影响不同粒度级别的片段如何表示。第二，我们的技术旨在自动发现源代码的识别特征，而传统的面向结构和基于度量的技术使用固定的转换。我们的结果表明，学习如何表示克隆检测的片段是可行的。我们发现，我们的技术检测到文件和方法级对映射到所有四种克隆类型，并证明学习足够健壮，足以检测具有重新排序的数据独立声明和语句、数据依赖语句和已被替换控制语句的类似片段。我们的在线附录是公开的。
本文由南京大学软件学院 2020 级硕士研究生曹振飞翻译转述。
联系客服
