DeepSim: Deep Learning Code Functional Similarity

论文阅读 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）：