DeepSim: Deep Learning Code Functional Similarity

代码的功能相似性检测

1、现存的大多数方法聚焦于代码的语法相似性，功能相似性还是一个挑战

（现存方法：都一般遵循相同的流程
首先从源代码中提取语法特征，以原始文本、tokens或者AST的形式
然后使用某个距离度量公式，如欧氏距离来检测相似的代码）

本文中提出的方法：将代码的控制流和数据流编码成一个语义矩阵，矩阵的每个元素都是一个高维稀疏的二进制向量

在这种表示下，我们设计一个深度学习模型来衡量代码功能相似性
通过将从“代码对”中学到的“隐藏表示”连接起来，这个DNN模型把检测功能相似性转化为了一个二元分类的问题，从而可以学习到这样的模式：虽然语法差异比较大，但是功能比较相似的代码之间的模式。

2、JAVA数据集

构建程序依赖图（PDG），通过子图同构来判断的变现比AST好，但是子图同构复杂性高（they either do not scale due to the complexity of graph isomorphism图同构具有复杂性，不可伸缩？？;要么使用可扩展性的序列来近似图，而不精确，例如：将PDG中的子图映射到AST深林，比较AST中提取的语法特征向量）

3、DeepSim有两个关键点：

①如果特征表示具有更高的抽象，则它对于度量代码语义更为强大
因为更高的抽象需要捕获更多的代码语义信息
控制流和数据流代表的是比语法特征更高的抽象
所以，DeepSim使用控制流和数据流作为相似性度量的基础
②我们提出了一种新型的编码方法：将代码的控制流和数据流编码成为一个压缩的语义矩阵，矩阵的每个元素都是一个高维稀疏二值特征向量。
通过这种编码，我们将代码相似性度量的问题简化为识别矩阵中的相似模式。这比发现子图更具有收缩性。

包含主要的两部分：

①Code semantic（语义） representation through encoding control flow and data flow into a feature matrix
可以将任意语言的代码片段作为源代码、字节码或二进制代码形式的输入，只要可以构造数据流图和控制流图
②Code similarity measurement through deep learning
该模型包含两个联系紧密的模块：
NN模块：提取高级特征（隐藏表示）
二元分类模块：判断代码对在功能上是否相似
数据集

在JAVA数据集上已经实现

两个数据集：

a dataset of 1,669 Google Code Jam projects（数据集地址） and the popular BigCloneBench（数据集地址），which contains over 6,000,000 tagged clone pairs and 260,000 false clone pairs.

本篇文章关于深度学习反向传播的解释：

The goal is to minimize the error (e.g., squared error) of reconstructing the inputs from its
hidden representation:

模型训练过程：

将控制流和数据流代表的语义信息编码为一个稀疏矩阵的过程：

控制流捕获代码基本块和过程之间的依赖关系（控制流分为顺序、分支、循环结构）
数据流捕获沿着程序路径和操作的数据值流

以上是表示代码行为的基础

我们basic idea是将控制流和数据流编码为变量之间和基本块之间的关系

Our basic idea is to encode code control flow and data flow as relationships between variables and
between basic blocks (e.g., operations, control jumps).

To obtain the control flow and data flow, we may perform the analysis on either source code, binary code, or any intermediate representation (e.g., Java bytecode, LLVM bitcode).
In this paper we focus on Java bytecode using the WALA framework
代码示例和控制流图（CFG）：

在CFG中，每个矩形代表一个基本块，每个块中可能存在多个中间指令
每个基本块可以生成一个数据流图（DFG）变量和基本块的类型信息都包含在图中

Encoding Semantic Matrices：

我们考虑三种用于编码控制流和数据流信息的特征：
变量特征（Variable features）、基本块特征（Basic block features）、变量和基本块之间的关系特征（Relationship features between variables and basic blocks）

变量特征：

①data type ： V (t) (bool, byte, char, double, float, int, long, short, void, other primitive types, JDK classes, user-defined types)
②modifiers（修饰符）：V (m) (final, static, none)
③other information： V (o) (basic, array, pointer, reference)
共19种

我们把他们编码成一个19维的特征向量

V = {V (m),V (o),V (t)}
如： X is a static int variable, so we have V = {0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0}

基本块特征：考虑7种类型：

normal, loop, loop body, if, if body, switch, switch body
7维的one-hot向量，用B表示
如：BB1 is a if basic block and its representation B = {0, 0, 0, 1, 0, 0, 0}

变量和基本块之间的关系特征
我们把数据流和控制流编码为变量之间的操作和基本块之间的控制跳转
共识别了43种不同的操作类型（43维onehot编码， I向量表示）
为了保留DFG中各变量之间的操作信息，T = {Vop1,Vop2, I }，81维（19+19+43），Vop1，Vop2
表示操作数，19维
为了保存控制流，将T扩展为T = {Vop1,Vop2, I ,B}，88维（81+7），这88为特征向量包含数据流和控制流

现在一般定义3个规则来对变量和基本块之前的联系编码信息

分别定义了
①两个变量之间的操作
编码两个变量op1和op2之间的操作，以及两个变量的类型信息和相应的基本块。这里bbop1表示op1所属的基本块

②变量和相关块之间的信息
编码变量与其对应块之间的关系。这里V0，I0表示零特征向量

③两个邻居基本块之间的联系。
编码两个相邻基本块之间的关系。这里bb2是CFG中bb1的继承者

定义3.1（语义特征矩阵A）。给定一个代码片段，我们可以使用上面捕获其控制流和数据流信息的编码规则生成一个矩阵。A中的每一行和每一列都是一个变量或基本块。它们的顺序对应于代码指令和基本块顺序。A（i，j）=T（i，j）是大小为E=88的二进制特征向量
i,j取值：1…n,n=nv+nb,变量数目与基本块数目的总和
Given a code fragment, we can generate a matrix using the encoding rules above that captures its control flow and data flow information. Each row and column in A is a variable or a basic block. Their order corresponds to the code instruction and basic block order. A(i, j) = T (i, j) is a
binary feature vector of size E = 88 that represents the relationship between row i and column j， here i, j = 1, 2, …,n, where n = nv +bb is the summation of variables count and basic blocks count.

考虑图2中的示例。它的CFG有11个变量（9个局部变量和2个静态字段）和6个基本块（包括输入、返回、退出块）。根据上面的编码规则，我们可以导出一个如图3所示的稀疏矩阵。(所以矩阵A的尺寸是17*17，A的每个元素是T向量，88d，表示一个变量或基本块)

与原始的CFG和DFG相比，我们的语义特征矩阵表示有两个优点。

首先，它减少了寻找同构子图以检测矩阵中相似模式的问题。
其次，这种结构（即一个矩阵）使得以后的过程很容易使用。
值得注意的是，对于大多数语法上相似的代码，它们的标识符名称、文本值或代码布局都不同，生成的语义矩阵将相同，因为这些差异是由CFG和DFG规范化的。
克隆类型：
级别1：除了空白区域、整体布局与注释上有差异意外，其他方面完全一致
级别2：在级别1差异的基础上，还在变量名和文字值上具有差异
级别3：在级别2的差异的基础上，还会有语句片段的添加、删除与修改
级别4：两个相似代码片段具有不同的语法结构之外，实现的功能是一样的
这个特性确保我们的方法也可以处理语法相似性。

我们承认，我们的矩阵表示法并不编码PDG中的所有信息。然而，所有依赖都隐式地编码在我们的表示中。例如，code ：y=x；z=x包含一个输入依赖项；它被编码为T（y，x）和T（z，x）。其他类型的依赖以类似的方式编码

有了语义矩阵，可以有效表示代码段，但是我们不能直接在语义矩阵上使用欧氏距离度量两个元素之间的相似程度。

语义矩阵有两大缺陷：

①无法确定哪些元素更重要，所以欧氏距离不可用
②不能检测出哪些元素的功能是相似的

但是功能相似、语义不同的两个语义矩阵不同，所以我们不能使用简单的距离度量（欧氏距离）来度量他们的相似性，因为我们不知道语义矩阵中的某些元素是否比另一个元素更重要。而且，不同的元素可能功能相似（如int和long），但是很难直接在语义矩阵上检测这种相似性。

本文设计出一个可以有效识别语义矩阵之间的相似模式的深度学习模型。

（DNN就是用来识别两个语义矩阵之间的相似性）
使用前馈神经网络从每个代码对的语义矩阵中生成high-level features，然后使用二元分类器将他们分成功能相似或者不相似

输入处理：与RNN类似，要求输入一个大小固定的语义矩阵 k*k，k=128
用0填充或者原始特征矩阵大小is=nv+nb，截断后k=nv′+nb′=128，其中nb′=nb，nv′=128-nb （nv变量数目，nb基本块的数目）
保留所有CFG的信息，丢弃部分超过矩阵大小的DFG信息来截断矩阵
T：88d，是控制流和数据流的编码
将T映射到h0 ，c=6

处理代码语句重新排序。
然后，我们将A的每一行展平为一个长度为c·k的向量，并以展平的行特征向量为输入，添加两个完全连接的层，以提取与每一行所表示的变量或基本块相关的所有信息。最后，加入一个池化层，对所有的行特征向量进行汇总。为了减少代码语句重新排序的影响，我们使用平均池化而不是整平整个矩阵

程序的第4行和第5行的句子顺序导致x和y的值不同
在矩阵的表示中，我们编码这三个变量之间的数据流，句子顺序决定了矩阵的每一行表示那个变量或者基本块
因为，我们生成了2个不一样的矩阵A

两个程序的前三行没有依赖关系，所以如果只考虑前三行的话，两个程序是等价的。
所以为了使我们的程序具有re-order的健壮性，我们忽略独立变量或者基本块之间的顺序，只保留有依赖关系的变量或者基本块的order。这可以通过对表示独立变量或者基本块的A的所有相邻行来执行average pooling，然后flatten剩余的行（句子顺序被保存在这个flatten vector中）。但是这会导致不同方法的向量长度不同，输入到一个静态的NN模型中有问题，所以对矩阵中的所有行采用average pooling处理。池化使得模型在没有任何额外参数的情况下将输入的大小从ckk转化为c*k
(与卷积层的pooling类似)。减小了模型的复杂性，可以提高训练和预测的效率。
以上表示可能会区分两个相似但是并不是完全相同的输入，如int和float array，使用带监督的二分类来解决

如图4所示，我们以不同的顺序连接方法m1和m2的潜在表示向量h13和h23:[h13，h23，[h23，h13]。然后，我们在两个具有共享权重的连接向量上应用一个完全连接的层，对输出状态执行另一个平均池，最后添加分类层。我们现在可以使用交叉熵作为成本函数，并最小化它来优化整个模型。
通过这种方式，我们的模型能够学习具有不同语法的每个代码对之间的相似性

大小为N的代码存储库需要运行N*(N-1)/2，对于N个方法，先运行模型的前向阶段得到各个方法的潜在表示h3，对于每个方法对，只运行分类阶段

实验

在GCJ和BigCloneBench数据集上进行测试

人工证实有12个完全不同的problem。

GCJ数据集的发现
我们发现超过20%的项目包含至少一个明显的语句重新排序。它们大多是由循环中使用的变量定义的不同顺序或函数（如min、max等）的参数的不同顺序引起

BigCloneBench是一个大型代码克隆基准测试，包含超过6000，000个标记克隆对和260，000个从25000个系统收集的错误克隆对

BigCloneBench中的每个pair也是一对方法，并被手动分配一个克隆类型。从下载的数据库中获得的克隆对总数与[53]中报告的略有不同。我们丢弃没有任何标记的真或假克隆对的代码片段，并丢弃LOC小于5的方法。最后我们得到了50K个方法，包括5.5M个标记克隆对和200K个标记假克隆对。大多数真/假克隆对属于克隆类型WT3/T4
级别3：在级别2的差异的基础上，还会有语句片段的添加、删除与修改
级别4：两个相似代码片段具有不同的语法结构之外，实现的功能是一样的
实验

使用DECKARD , RtvNN and CDLH 来做对比
DECKARD是一种典型的基于语法树的技术，它使用预先定义好的规则为每个子树生成特征向量，并对他们进行聚类以检测代码克隆的方法。
RtvNN使用RNN+欧氏距离来度量相似性。与我们的方法不同之处在于：RtvNN对源代码的tokens和AST进行操作，并分别学习每个代码的隐藏层表示（无监督学习），而不是组合代码对来学习他们之间的相似模式。
CDLH使用LSTM+ASTs

实验1

①DECKARD achieved low recall and precision.
原因是：该模型要求两个方法的语法树非常相似，本质上是整个代码的语法相同。
为了检验，我们选取了12个问题之一的所有解决该问题的代码，发现超过一半的解决方案具有不同的语法树结构，他们被错误地预测到不同的簇类中。
②DeepSim的表现远高于DECKARD、SdA-base and SdA-unsup，说明了该方法能够有效地从语义矩阵中学习higher-level的特征。，编码后的语义矩阵也比DECKARD中所用的语法表示更好。
③ RtvNN的查全率最高，查准率最低。我们发现 RtvNN几乎将所有的方法对都报告为相似。
原因是： RtvNN依赖于tokens和AST去生成隐藏层的表示，然后使用一个很简单的距离度量来区分它们。但是，两个功能相似的函数可能具有显著的语法差异，两个功能不同的函数可以共享语法上相似的成分，如IO操作。
通过进一步分析，我们发现大多数方法之间的距离在[2.0,2.8]的范围内，通过降低距离阈值，RtvNN的准确率可以显著提高到90%，但是查全率迅速下降到10%，F1分最高为0.325
④DeepSim的精确度为71.3%，仍然有很大的改进空间。 检查了DeepSim的误报和漏报后，我们发现这主要是由于该工具在处理方法调用方面的局限性。
比如在一个问题中，有些解决方案使用标准的循环和赋值语句，而其他解决方案则使用Map和Replace之类的utility methods（通用方法）。由于我们没有讲被调用方法中的信息明文编码到语义特征矩阵中，DeepSim无法区分这些方法及其相应的语句。
对于大多数静态代码相似性度量技术来说，这是一个常见的限制。

Considering that DeepSim could generate a final hidden representaion for each method after training, incorporating this information to encode method invocation instructions is feasible (re-training may be necessary). In addition, utilizing constraints-solving based approaches [29, 33] as a post-filtering to the reported results may also further improve the precision（DeepSim在训练后为每个方法都生成一个隐藏层表示，所以把这些信息合并到调用指令的编码中是可行的，此外，使用基于约束求解的方法对报告结果进行后滤波也可以进一步提高精度）

实验2

对于这个数据集，DeepSim在查全率和查准率方面都明显优于所有其他方法。
DeepSim本应该保证在T1-ST3上的F1达到1.0，没有达到的原因应该是在该工具从源代码中产生DFG时，丢失了一些数据流，原因是我们在WALA中引入了处理外部依赖项的近似方法。

实验3

使用问题ID为4的真/假克隆对作为训练数据集（因为它包含大约80%个真/假克隆对的整个数据集），其余数据作为测试数据集。（由于来自BigCalBoobe的真/假克隆对来自不同的功能 ）

对于wt3/T4的克隆类型，BigCloneBench上的DeepSim的F1高于GCJ数据集上的F1（这与文献[57]中报道的BigCloneBench和另一个OJ数据集OJClone的比较结果一致）。我们检查了几个WT3/T4克隆对，发现尽管它们在语句级别（这是WT3/T4克隆类型的标准）上的相似性不到50%，但其中许多都遵循相似的代码结构，并且只在调用的api的序列上有所不同。相反，GCJ项目都是由具有不同代码结构的不同程序员从头开始构建的。因此，在GCJ数据集中检测功能克隆更加困难。
Why DeepSim outperforms the other DNN approaches？

原因有三。

首先，DeepSim基于编码DFG/CFG的语义特征矩阵，这是比其他DNN方法（如RTVNN和CDLH）所使用的词汇/语法表示（例如，token或AST）更高级别的抽象。与两个SdAbaseline相比，DeepSim以语义特征矩阵为输入，而对于SdAbaseline，每个88d特征向量T被手动重新编码为8d，整个矩阵被展平为一个向量。手动重新编码可能会丢失信息，因为8d向量中的每个元素实际上都是分类数据，并且在这种情况下，标准神经网络模型受到限制。此外，flatten整个矩阵会加剧语句重新排序的影响，因为整平向量是严格排序的，这会导致报告更多的误报。

第二，DeepSim和两个SdA baseline都包含一个方法对的分类层，而RtvNN只计算两个方法的隐藏表示之间的距离，不比我们之前讨论的那样适用，这应该部分归因于模型中二元分类公式的有效性。

第三，DeepSim模型使用了两个average pooling layers，第一个计算矩阵所有行的平均状态，从而减少了语句重新排序带来的副作用。第二个计算两个不同隐藏状态的表示的拼接的平均状态，保证了代码相似性的对称性，即：

编码方法的有效性。

在DeepSim的第一层，我们将每个88维的特征向量T映射到隐藏空间中的一个6维的向量。为了分析我们的训练模型，我们构造了8个不同的特征向量，每个特征向量都是变量之间特定操作的编码。我们将它们映射到嵌入空间，并使用PCA降维对其进行可视化。

DeepSim生成的8个不同输入特征向量的第一层隐藏表示。
①有四个非常接近的点，代表四种不同的指令。这表明我们的编码确实有效地保留了数据流信息，并且我们的模型成功地学习了这些操作之间的相似性。
②

尽管操作相同，但是来自于不同的基本块在嵌入空间中并不紧密。
这表明，我们的函数代码相似性度量模型能够将代码结构（即控制流）信息有效地分解到特征向量中，并成功地学习到这些信息。

八条指令隐藏状态的可视化显示了对数据流和控制流进行编码的各种特性矩阵的有效性。
更重要的是，我们的DNN模型可以从输入的语义特征矩阵中学习高级特征，以及具有不同语法的功能相似代码之间的模式。这显著地区别了我们的方法和其他方法。

语义特征矩阵的大小被固定为128，对我们的数据集有效，但是这个固定长度针对较短或者较长的数据集可能会降低计算效率或者丢失一些方法的信息，作者提出可以与RNN结合，但是RNN需要固定的输入序列顺序，这很难处理代码语句的重新排序。具有attention机制的LSTM可能会是一个潜在的解决方案。

另外，DeepSim的性能受到数据集大小和质量的限制。