代码实现对象的克隆，哪个代码块能让克隆体消失

概括：

代码克隆检测是软件维护和演化中的一个重要问题。 尽管许多方法考虑结构和标识符，但现有的检测技术还没有对这两种信息源进行建模。 这些技术还依赖于通用的、手工制作的函数来表示代码片段。 我们引入了一种基于学习的检测技术，其中表示源代码中的项目和片段的所有内容都是从存储库中挖掘的。 我们的代码分析支持依赖深度学习来自动连接在词汇级别挖掘的模式和在句法级别挖掘的模式的框架。 我们从软件维护人员的角度评估基于学习的代码克隆检测方法的可行性。 我们在八个真实的Java 系统上采样并手动评估了398 个文件级对和480 个方法级对。 93% 的文件级和方法级样本被评为真阳性。 在真正的阳性结果中，我们发现了映射到所有四种克隆型的对。 我们将我们的方法与传统的面向结构的方法进行比较，发现基于学习的方法检测到的克隆要么未被著名工具Deccard 检测到，要么报告得不理想。 我们的结果证实，我们基于学习的方法适合克隆检测，并且对于研究人员来说是一种可行的技术。

关键词：代码克隆检测、机器学习、深度学习、神经网络、语言模型、抽象语法树

1.首先：

抽象是软件工程（SE）中最重要的词。因此，软件仓库充满了抽象，这些抽象允许软件工程师通过分离关注点并在不同级别处理不同细节来管理复杂性。每个精细的抽象级别都由实现来补充。 这些实现可以从头开始开发或从现有代码片段克隆。如果现有代码是实施的良好起点，软件工程师可以通过复制和粘贴片段来克隆代码。将克隆引入软件系统的另一种方式是工程师可能会无意中开发出与现有实现类似的另一种实现。复制并粘贴代码，然后修改复制的代码片段可能会产生文本上相似的代码片段，并且可以用语法来解释相似之处。 另一方面，如果工程师无意中开发了与现有实现类似的实现，他们最终可能会得到功能相似但语法不同的克隆。

克隆检测是软件维护和演化中的一个重要问题。尽管之前的研究已经证明了代码克隆的一些负面影响，但克隆并不一定有害。克隆并不一定意味着重构。然而，自动检测两个片段之间相似性的能力可以帮助检测候选库、帮助程序理解、检测恶意软件、检测抄袭和版权侵权、检测基于上下文的不匹配以及识别重复，这在许多应用程序中都很重要，例如机会。检测。在本文中，我们的新颖方法用于使用新的基于学习的范例来挖掘内部源代码表示。

克隆检测过程首先将源代码转换为适合相似性评估的表示形式。例如，为了表示代码片段，传统的基于树的克隆检测工具依赖于与通用编程结构紧密耦合的人工特征。在这方面，基于标识符的领域信息被丢弃，并且可以在词汇和句法级别学习的信息之间的链接被切断。 此外，诸如编程结构出现次数之类的声明性特征将大量先验知识应用于如何自动表示片段。然而，可以合理地预期，不同的应用领域和软件系统在不同的开发阶段会产生独特的源代码模式，从而暴露出代码克隆检测等问题。然而，这些模式不一定是使用通用特征空间技术获得的，描述这些有用的潜在特征的唯一方法是创建学习代码的表示，即学习的表示本身。自动学习的表示或“表示学习”不需要先验知识即可将原始数据（例如源代码）转换为合适的表示，而是自动执行发现过程中的手动步骤。源代码特征的有效挖掘、源代码中标识符的语言分析、句法模式分析以及能够适应存储库变化的工程方法是SE研究的基本问题。考虑所有这些问题设计克隆检测方法是我们工作的动力。 我们的主要成果是集成和使用了一套新技术。 自动融合代码中有关结构和标识符的信息并使用软件存储库中的数据指定转换的过程。

关于代码克隆检测的代码片段的表示有两个重要的见解。首先，我们的方法将片段中的项目映射到连续值的向量，以便在源代码存储库中以类似方式使用的项目被映射到相似的向量。 这种从术语到向量的转换与基于令牌的技术(SEC) 中使用的令牌抽象有根本的不同。 其次，我们基于表示学习的方法不依赖于围绕语言的结构元素设计的直观（但有限）特征，例如基于树的技术，而是使用各种粒度的目的是学习片段的判别特征。在水平上。

我们方法的本质可以追溯到SE 中不同级别细节的抽象和处理。 我们建议在构建软件时利用这一基本原则。因此，我们的源代码建模技术利用代码中项目结构中基于经验的模式，就像语言建模利用项目序列中的模式一样。为了实现这一目标，我们将循环神经网络（SEC）与词法分析以及循环神经网络与句法分析相结合。将编译器前端与深度神经网络和深度学习(SEC) 耦合的目的是提供一个框架，将词汇级别挖掘的模式与句法级别挖掘的模式连接起来。 克隆检测是该框架的一个重要应用。

2.深度学习代码片段

我们分两部分描述基于学习的方法（见图1）。 第一部分描述如何使用特定类型的语言模型Rt NN 将每个项目嵌入片段中。第二部分描述了如何使用语言语法对任意长的嵌入序列进行编码来描述片段，以及如何使用Rv NN 实现的递归学习过程。使用深度学习的目的是自动化这个手动步骤。

2.1 深度学习代码：词汇级别

RTN 是一种深度学习模型，适用于对具有词汇V (|V|=m) 的源代码语料库中的术语序列进行建模。

环境

n 是用户指定的超参数，是隐藏单元的数量。 RtN包括输入层xRm+n、隐藏层zRn和输出层yRm。 RTN的深度是由于重复，因为隐藏状态被复制回输入层，因此RTN的输入层压缩了当前项t(I)和先前状态z(I1)。

该输入向量乘以矩阵[, ]Rn(mn) 并传递给非线性向量函数f（即（2））。

该状态向量乘以另一个矩阵Rmn 并标准化以计算后验项。式(1)-(3)展示了Rt NN的表达，式(4)强调了它的深度。所以它的配置看起来像这样：现在可以更清楚地显示输出如何将先前的输入转换为高度非线性函数。

={, , } 的模型使用交叉熵准则进行训练，但这里省略了技术细节。在软件语言建模中，您可以使用模型的输出y(i) 来预测代码行中的下一项：argmaxkyk(i)。然而，深度学习模型不仅对其输出有用，而且对其内部组件也有用。在本研究中，基于RtNN 的软件语言模型最重要的组成部分是等式2 中的嵌入矩阵Rnm。每列 对应一个项。 的列空间包含V 中每个术语的语义表示，以便模型赋予与语料库中以类似方式使用的术语相似的向量。每个给定项在呈现给模型时都会进行one-hot 编码。方程1 中的矩阵向量乘积t。 (2) 相当于将V 中的任意项映射到 的列，它将片段中的项序列映射到嵌入序列。因此，我们编码任意长的嵌入序列来表示代码片段。

2.2 深度学习代码：语法级别

我们基于学习的原型不同于传统技术。给定一个片段，信息从终端节点通过非终端节点流向层次结构的根（见图3-4）。这种自下而上的信息流类似于传统的面向结构的方法中计算特征向量或基于度量的方法中的度量的过程。然而，它挖掘终端节点（SEC）的向量表示和不基于度量出现的非终端节点的特征（SEC 2.1）。特征空间是通过学习片段识别（SEC）获得的。此外，在自下而上的遍历合成信息并计算特征向量或度量之后，传统技术终止并将源代码表示传递给相似片段的匹配检测算法。在某种程度上，我们认为自下而上的信息流是必要的，但不足以充分表示代码片段。因此，我们的终止条款根本不同。在我们的方法中，当模型收敛到一个解决方案时，挖掘表示的过程就结束了，该解决方案允许在不同粒度级别（表达式）上很好地表示编程结构。这一标准是我们方法的核心，其中词汇级信息从终端发送到代码结构的根，并且监控信号通过结构广播从根发回。

2.2.1 从AST到完全二叉树

编译器前端将程序分解为多个组件，并根据语言的语法生成中间代码。这些组件称为编程构造，上下文无关语法指定编程构造的语法。 AST 是表示程序的层次语法结构的中间代码。最终目标是指定一种基于学习的方法来编码任意长度的词汇元素序列。由于AST 中的非终端节点包含一组词汇元素，因此每个AST 节点都有一个表示该节点的代码的向量表示和一个用于存储该节点中包含的词汇元素集的特殊属性repr。有。挖掘代码，使相似的序列包含相似的代码。一种基于学习的方法基于AST，它是一种树表示，可以具有任意数量的级别，其中包含具有任意数量子节点的节点，但这里存在一个问题。由于我们的学习模型只接受固定大小的输入，因此我们将AST 转换为完全二叉树来固定输入大小，并将学习模型递归地应用于不同级别的结构建模。

AST 节点的度可以是0、1、2 或大于2。根据定义，度数为0 或2 的AST 节点满足完全二叉树节点的属性，但任何以度数为2 或更高的节点为根的子树必须转换为完全二叉树。转换的第一步是扫描AST 中的元数据（例如，Java 片段的AST 中的Javadoc 节点）以及空匿名类声明、空数组初始值设定项、空块、空类、空删除节点（例如编译）单位。和空语句。当扫描AST 中的空节点时，它还会查找具有相同父节点的相同文字类型的序列。 学习器对AST 节点的成对组合进行编码。因此，我们通过访问非终端节点、检查其子节点并将相邻的相同文本类型分组到单个实例中来避免对相同文本类型进行编码。真实、真实真实等等。确实如此，这些序列还有助于控制二叉树的深度，这可能会导致分辨率的一些损失。

然后，为了获得二叉树，必须重新组织以度大于2的节点为根的子树，以确保子树正确对齐。

的

放置。 我们为每个非终端系统定义了基于语法的方法。

土地

重新组合度数为2 的节点的子节点。例如，一个语句实例可以有两个或三个子节点。对于这种非终结类型，每个主体都有一个或两个组件，因此我们定义了一种仅生成二叉树子树的新语法（假设表达式和语句节点的语法）。为了实现这一目标，我们通过引入新的人工非终结符类型（例如分支）来增强该语言的语法。

:=

:=[]

对于具有任意最大度数的非终结类型（例如块节点），将其子节点组织成二进制列表。由于块节点的子节点由语句序列表示，因此我们使用一种新产品，允许块节点具有语句递归列表的形式。

:={}

:=[]

它将被替换为正品。

:={}

使用新语法转换每个2 度实例后，从原始AST 获取二叉树。然而，一个节点可能只有一个子树，因此二叉树可能是也可能不是完全二叉树。也就是说，我们需要处理度数为1的节点。 我们以自上而下的方式遍历二叉树，当到达度为1 的节点时，我们将该节点及其子节点合并为单个节点。然后它递归地继续转发重新合并的节点。在自上而下的访问中，只有一个子节点的父节点的实例最终会合并为一个节点。合并过程由优先级列表控制，该优先级列表为每个非终结类型分配一个值。合并两个节点时，优先级值用于确定是否将当前节点类型或子类型分配给新节点。

选项卡1 显示您定义的优先级列表。列表中较高的类型具有较高的优先级。如果两个节点具有相同的优先级值（对于其他两种类型的节点也类似），则合并将保留父节点。这一设计决策来自于对父节点往往比子节点更具表现力和表现力的观察。我们根据一些经验观察决定了该清单。特别是，该表格保证了以下结论：

1.

某些粒度级别受到保护，不能被其他节点覆盖。

2.

合并两个节点时，更多的表达式类型优先于更通用的类型（例如父表达式和块）。

3.

上一步中创建的用于处理2 度节点的人工非终结节点不会替换原始语法中的非终结类型。

在SE 应用程序中，保护一定程度的粒度（例如克隆检测）的影响是显而易见的，我们的方法旨在通过创建明确定义的抽象边界来更好地支持软件维护人员，您可以使用.

2.2.2 从完全二叉树到橄榄树

本文介绍如何将完全二叉树转换为非正式的橄榄树。这是将中间代码转换为完整二叉树并用挖掘的表示来注释该树的结果。考虑int 语句foo=42。该语句的AST 是完整的二叉树，如图3 1-5 所示。再次假设每个AST 节点都有一个特殊的属性repr。例如，repr 在图中存储SimpleName 的表示。使用每个终端的词汇元素初始化此属性，以选择嵌入 矩阵的相应列。例如，如果词法元素int 映射到 的第JTH H 列，则该图的PrimitiveType 被初始化为1.repr=。对于非终端节点，例如图中的变量声明片段和变量声明语句，该属性被初始化为NULL。该节点使用在词汇级别挖掘的模式来初始化嵌入序列。然后使用自动编码器组合嵌入。自动编码器的典型形式是具有输入层x、隐藏层z 和输出层y 的神经网络。这里=[, r]Rn2n 是 编码器。 R2nn 是delta 编码器，zRn 和yR2n 是iases。在词汇级别挖掘的模式和在句法级别挖掘的模式之间的关系与等式1的大小相同。隐藏层z。 g 是非线性向量函数，h 通常是恒等函数。我们声称我们的学习模型只接受固定大小的输入，这有助于从AST 到完整二叉树的转换。具体来说，自动编码器的输入是两个兄弟节点的代码向量，即x=[x;xr]R2n。例如，计算图中变量声明片段的表示。表示模型x=[2.repr; 3.repr]。限制隐藏层的大小（即|z|=n2n）迫使模型学习输入的压缩表示。该压缩z 如方程式所示。将其存储在非终端节点的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 有很大影响。这种效果比原来的效果要大。在计算前向传递中每个非终端节点的代码后，通过结构算法的反向传播来计算（全局）误差函数相对于模型组件的偏导数。一旦深度学习模型在几个阶段收敛，它的表示就被用来构建一个完整的二叉树，产生一棵橄榄树。

为什么深度学习是克隆检测的好方法？分析标识符的技术通常使用潜在语义分析（LSA）。与LSA 相比，深度学习具有三个明显的优势。首先，自动编码器是非线性降维工具。其次，自动编码器递归地应用于输入的多个非线性变换，而不是使用输入的单个线性分解。第三，我们递归地考虑项目的顺序。另一方面，解析结构的方法会丢弃用作先验知识的标识符。我们的学习框架不使用常见的结构元素，而是将其表示基于标识符和文字类型的区分能力，因此深度学习可以识别术语之间的相似性。

Socher 等人将递归自动编码器应用于自然语言句子以进行情感分析。 Socher 工作的新颖之处在于一种半监督扩展，旨在使用句子级标签来训练对句子情感进行分类的模型。使用递归自动编码器来学习实例化为语法级属性的任意大小的代码片段的表示。关于我们使用的属性的性质的一个评论：在编译器术语中，属性（即与编程构造相关的数量）被认为是“组合”或“继承”，但我们在这项工作中挖掘的是，从技术上讲，两者都不是。节点的复合属性是根据该节点及其子节点的属性值计算的，而继承属性是根据该节点、其父属性及其兄弟节点计算的。 然而，在我们的工作中，属性以自下而上的遍历方式合成，而训练算法以自上而下的方式调整属性，因为常见编程结构中的错误在组件之间划分。

2.2.3 用于克隆检测的橄榄树

一旦模型经过训练，推理就变得很容易。识别克隆对相当于比较两个片段在不同粒度级别的表示。具体来说，给定一个片段，我们构造一个AST 并将该AST 转换为完整二叉树。如果完全二叉树有k 个终端节点，则有k 个非终端节点。因此，为了对序列进行编码，我们需要将k1 矩阵乘以向量，然后应用向量函数来导出片段的表示。当然，完全二叉树的拓扑控制着节点表示组合的顺序。对于代码克隆检测的特定应用，所需要的只是一个阈值，该阈值比较两个表示以确定将它们分类为克隆对的倾向，并且该阈值完成了克隆检测规范。

2.2.4 克隆检测的贪婪组合

在这里，我们利用Socher 等人提出的方法。 以贪婪的方式组合表达式对。 1. 概述您的训练步骤。我们为每个片段构建一个AST，并对每对相邻终端节点进行编码，而不是像以前那样转换AST。 然后选择具有最低重构误差的等式7首先进行编码。第四，第一次迭代得出两个代码。该模型比变量声明片段执行更好的重构[2.repr; 3.repr]。 在下一次迭代中，我们用新的父对替换所选对，再次计算成对重建误差，并选择误差最小的对。 如果有k 个终端节点覆盖该段，则重复此过程，直到计算出k1 个非终端节点表示。 一旦自组织树完成，模型就会像以前一样通过结构算法和标准优化技术的反向传播进行训练。

一旦模型经过训练，推理就会再次变得容易。给定一个片段，它构造一个AST 并对节点进行贪婪编码，直到导出包含该片段的节点的代码。使用阈值将该代码与其他贪婪编码片段进行比较，以检测代码克隆。贪婪编码节点的训练和推理过程的重要之处在于不需要构建AST。事实上，语言模型存储了语料库中所有术语的嵌入，因此您可以直接操作特定片段。构建AST 的原因是过滤标点符号等词汇元素，以控制用于训练和推理的树的深度。

这两种组合方法之间存在一些重大差异。 首先，对于基于AST 的方法，克隆粒度通常是“固定的”。也就是说，片段在句法边界内组合。另一方面，对于贪婪方法，克隆粒度通常是“自由的”。也就是说，它组合了没有句法边界的片段。其次，与基于AST 的方法相比，训练需要更多的计算资源。基于AST 的方法需要计算k1 个矩阵-向量乘积，而贪婪方法则计算k1 个（一般）密集矩阵-矩阵乘积。 第三，贪婪方法是在没有显式语法知识的情况下进行训练的，因此不需要构造AST，并且该模型可以更好地处理语法无效的片段。 尽管存在差异，这些方法共同体现了一种新的基于学习的代码克隆检测范例。

3. 工作的未来

关于用于克隆检测的增强深度学习：在这里，我们借鉴了机器学习社区在语义哈希方面的工作，并探索深度学习器中看似无害的机器学习细节如何在SE 中产生重要的实际结果。我们将g（方程5）描述为非线性向量函数。 g被称为“激活”函数，实际中使用了许多激活函数，例如g=tanh。该模型使用小的随机权重进行初始化。这意味着tanh 的（几乎）线性部分“预激活”，例如公式5 中的xz。随着模型的训练，权重增加并引入非线性。使用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] 呈现给图中的模型，则它需要一个^=变量声明片段。标准的唯一变化是添加一个公式来计算（交叉熵）错误分类成本。

4。结论

引入一种检测代码克隆的新方法。我们基于学习的范式至少在两个重要方面不同于传统的面向结构的技术。首先，术语（包括标识符）影响不同粒度级别的片段的表示方式。其次，传统的面向结构和基于度量的技术使用固定转换，而我们的技术旨在自动检测源代码中的判别性特征。我们的结果表明，学习如何用克隆表示检测到的片段是可能的。我们的技术检测映射到所有四种克隆类型的文件方法级别对，并包括排序的数据独立声明和语句、数据相关语句以及被取代的控制语句。我们表明，学习足够强大，可以检测包含.片。在线附录是公开的。

致谢

本文由南京大学软件学院2023级硕士生曹振飞翻译整理。