Detecting Code Clones with Graph Neural Network and Flow-Augmented Abstract Syntax Tree 笔记（一）
摘要部分
语义克隆检测是重点。利用抽象语法树（AST）的思路在各种编程语言的测试中都有明显的进展，但现有缺陷是无法充分利用代码片段的结构信息（语义信息的控制流和数据流）。
本文使用流增强抽象语法树（FA-AST，FA：flow-augmented），而图神经网络又采用了两种不同的类型。
引言部分
包含过往项目缺陷与本项目优势。
过往项目
为了研究语法差异很大但语义相近的这一类代码，研究者采用了深度神经网络，一般的方法分成了两步：
- 利用神经网络计算出代码块的一种向量表示；
- 计算向量相似度。
一个典型方法就是CDLH，引导树型长短时记忆模型（Tree-LSTM）对二进制化的AST进行编码，重构代码块。这种方法的缺陷就在于仅发掘了AST携带的语法结构化信息，而不含有一些语义信息（控制流、数据流）。
CFG（Control Flow Graphs）的应用目的就是发掘控制流信息，应用案例如DeepSim，利用CFG构建语义矩阵。但CFG仍旧存在缺陷，一是缺乏数据流信息；二是多数CFG仅包含代码块间的控制流，忽略了块内的语法结构；三是对于部分编程语言而言，构建CFG的难度远大于构建AST。
本项目
本项目的目的在于构建一种图的表示形式，能够利用AST反映语法、语义信息，使用图神经网络（GNN）进行检测。本项目的思路包含三步：
- 构建程序的图表示方式；
- 利用图神经网络计算代码块的向量表示；
- 以向量相似度表征代码相似度。
本项目需要构建基于AST的图表示方式，其中的AST被称作FA-AST（flow-augmented AST）。FA-AST的构建方法是向原始AST添加不同类型的边，边表示着不同类型的控制流和数据流。
本项目采用了两种不同的图神经网络模型：
| Gated Graph Neural Network(GGNN) | Graph Matching Network(GMN) |
|---|---|
| 对所有不同代码块分别计算向量 | 对成对的代码块一并计算向量 |
背景部分
包含代码克隆检测背景与图神经网络。
代码克隆检测
| 代码克隆级别区分 | |
|---|---|
| Type-1(T1) | 语法完全相同的代码块，但不包括空格和注释 |
| Type-2(T2) | 包含T1，且标识符名称和文本值的部分可能不同 |
| Type-3(T3) | 包含T1、T2，且可能存在增加、修改、删除语句 |
| Type-4(T4) | 语法不同但实现功能相同（如冒泡排序与快速排序两个代码块会被认定为成对的T4代码块） |
T3和T4的界定比较模糊，研究者用BigCloneBench等作为进一步界定的基准，T3和T4又因此被划分为强T3、普通T3、弱T3（或T4），每个级别都比其前者更加难以检测。本项目主攻弱T3（或T4）类型。
图神经网络
传统的深度神经网络，如卷积神经网络（CNN）和递归神经网络（RNN）对图像和自然语言处理都卓有成效。
但是图数据更加复杂。图像可以被视作一组像素，文本可以被视作一系列单词的序列，而就图而言，至少需要关注两类信息：结点以及结点间的关系（边）。图神经网络即为此而产生。图神经网络的目的是学习每个结点中含有其临近结点信息的嵌入状态，有时则需要学习整个图的嵌入信息。多数现有的图神经网络模型适用于一般框架的信息传递神经网络（MPNN，Message Passing Neural Networks）。在MPNN框架中，神经网络模型包含两个阶段：传递信息和读出信息。
现假设图信息表示为\(G=(V,E)\)，\(V\)表示结点，\(E\)表示边，\(G\)中的每个结点拥有状态\(h\)，每条边被赋予嵌入值\(e\)。信息传递阶段会更新结点内的状态：
\[\begin{align} m_{j{\rightarrow}i}&=f_{message}(h_i^{(t)},h_j^{(t)},e_{ij}),{\forall}(i, j){\in}E\tag{1}\\ m_i&=f_{aggregate}(\{m_{j{\rightarrow}i}|{\forall}(i, j){\in}E\})\tag{2}\\ h_i^{(t+1)}&=f_{update}(h_i^{(t)},m_i)\tag{3} \end{align} \]其中，\(m_{j{\rightarrow}i}\)表示由结点\(j\)传递到结点\(i\)的信息，\(f_{message}\)为信息函数；\(m_i\)表示结点\(i\)的信息聚合，\(f_{aggregate}\)为聚合函数，通常内容为直接求和；\(f_{update}\)为结点更新函数。等式\((1)\)和等式\((2)\)可以被认为是聚合器，表示每个结点从邻接结点收集信息。等式\((3)\)为更新器，为每个结点更新内部状态。在整个信息传递阶段，上述执行过程会重复\(T\)次。在读出信息阶段，该模型会使用函数\(f_R\)为整个图计算出一个向量表示：
\[h_G=f_R(\{h_i^T|i{\in}V\})\tag{4} \]问题定义部分
假设有两个代码片段\(C_i\)和\(C_j\)，并设定一个常量标签\(y_{ij}\)，用于判定两个片段\((C_i,C_j)\)是否为克隆代码对。基于一系列拥有已知克隆标签的克隆代码对，就可以建立训练集\(D=\{(C_i,C_j,y_{ij})\}\)。项目的目的是训练出一个深度学习模型为函数\(\phi\)服务。\(\phi\)的功能是将代码片段\(C\)映射为特征向量\(v\)，以使得对于任意代码片段对\((C_i,C_j)\)，它们的相似程度\(s_{ij}=\phi(C_i,C_j)\)都尽可能接近相应的标签\(y_{ij}\)。
在推断阶段，项目在真伪克隆代码对之间设置了一个阈值\(\sigma\)用以判定。当相似程度\(s_{ij}\geq\sigma\)时判定为真，否则为假。
提出方案部分
方法概览
首先将代码片段处理为AST，其次建立图表示方式（FA-AST，对AST加边以表示控制流、数据流），然后FA-AST结点和边的嵌入状态，再将成对的向量化FA-AST输入图神经网络。图神经网络会为所有结点计算向量表示。为发掘代码克隆，项目采用一个读出函数对每个FA-AST分别汇集结点向量，成为图级别的向量。至此，产出结果即为两个图级别的向量表示。之后再使用余弦相似性表征这两个向量的相似程度。如果相似程度大于阈值\(\sigma\)，则认为两个代码片段成克隆代码对。项目的代价函数是均方差，即：
\[\begin{align} {{1}\over{d}}{\sum^{d}_{i=1}}(y_i-\hat{y_i})^2\tag{5} \end{align} \]其中\(d\)表示\(y_i\)和\(\hat{y_i}\)的维度。本项目中，预测的关于两个代码片段相似性的真值，所以此处\(d=1\)。
使用AST建立图
原始AST仅能表示代码的语法结构，所以需要对其添加不同类型的边。尽管对于某些语言而言，程序可以被转换为汇编语言控制流图或者中介表示（IR：Intermediate Representation），项目并没有直接采用这样的控制流图，原因如下：
- 对于单程序，控制流图中的边数通常远少于其AST中的，而对于图神经网络而言，更少的边意味着结点间更少的信息传递，即结点将以更低的频次更新状态。
- 控制流图中的多数结点都是语句表达式，而不是单个的标记。如果使用简单的方法嵌入节点信息（比如打包单词嵌入），将会失去这些结点中的语义信息。当然控制流图并不是不能采用，如果为每个语句表达式建立子图，也能解决丢失语义的问题。但是这将显著提高运算成本。
本项目使用javalang（python库）取得Java应用程序的AST。
为建立程序的图表示方式，规定了如下类型的边：
| Child | 根据AST规则，将非终端结点连接至其所有子结点 |
| Parent | 将根结点以外的结点连接至其父系结点 |
| NextSib | 将结点连接至其兄弟结点（根据AST规则从左至右），因为图神经网络不考虑结点顺序，有必要向神经网络模型提供一份所有子结点的顺序 |
| NextToken | 将终端结点连接至下一个终端节点（AST中，终端结点指的是程序源代码中的标识符标记token，故NextToken边连接了一个标识符token和下一个相关联源码的标记token） |
| NextUse | 连接一个变量使用的结点及其下一次出现的结点，NextUse边可以发掘出有效的数据流信息 |
- If判断语句：在AST中，一个IfStatement结点包含两个或三个子结点。第一个子结点为If条件Condition，第二个（和第三个）子结点为当条件判断为真（为假）时的主体语句，分别是ThenStatement和ElseStatement。这里定义了CondTrue边连接Condition和ThenStatement，同样定义CongFalse边和ElseStatement。
- While循环语句：一个While结点有两个子结点，分别为条件Condition和主体语句Body。定义WhileExec边连接Condition至Body，定义WhileNext连接Body至Condition，这模拟了循环的执行过程。
- For循环语句：一个For结点有两个子结点，分别为循环控制ForControl和主体语句Body。与While循环类似，定义ForExec边连接ForControl至Body，定义ForNext边连接Body至ForControl。
- 顺序执行语句：Java中，语句顺序执行存在于方法体和循环体的代码时钟之中。BlockStatement结点是按顺序执行的语句对应AST子树的根结点。与之前提出的控制流结点不同，BlockStatement结点可以拥有任意个数的子结点，故对于其每个子结点而言，都需要定义一个NextStmt边连接自身至下一个结点（兄弟结点）。
最后，为提升信息传递频次，对每种没有对应反向边的边（即不能回到原始出发的结点，如CondTrue和NextStmt），再为其添加额外的反向边。
模型化代码对的神经网络模型
本项目采用两种不同的图神经网络：为图嵌入信息设计的传统GNN、能够同步模型化两个图的图匹配网络。
图嵌入模型
在这个模型中，项目使用GGNN（Gated Graph Neural Network）学习图的嵌入信息。GGNN采用传统GNN框架（公式见背景部分-图神经网络）。这里的\(f_{message}\)函数具体为多层感知器（MLP，Multilayer Perception），\(f_{update}\)函数具体为门控循环单元（GRU），则GGNN的扩展流程如下：
\[\begin{align} m_{j{\rightarrow}i}&=MLP(h_i^{(t)},h_j^{(t)},e_{ij}),{\forall}(i,j){\in}E_1{\cup}E_2\\ m_i&={\sum_j}m_{j{\rightarrow}i}\tag{6}\\ h_i^{(t+1)}&=GRU(h_i^{(t)},m_i) \end{align} \]读出函数\(f_G\)采用：
\[\begin{align} h_G={MLP}_G({\sum_{i{\in}V}}\sigma(MLP_{gate}(h_i^{T})){\odot}MLP(h_i^{(T)})) \end{align}\tag{7} \]图匹配网络
GMN（Graph Matching Networks）框架学习一对图的嵌入信息。包含传统GNN的扩展过程，并另外计算来自两个图的结点间交叉图的注意力机制。尽管GMN每次需要一对图的输入，其仍旧可以为每个图产生各自的嵌入信息，完整的扩展过程如下：
\[\begin{align} m_{j{\rightarrow}i}&=f_{message}(h_i^{(t)},h_j^{(t)},e_{ij}),{\forall}(i,j){\in}E_1{\cup}E_2\tag{8}\\ \mu_{j{\rightarrow}i}&=f_{match}(h_i^{(t)},h_j^{(t)}),{\forall}i{\in}V_1,j{\in}V_2{\ }or{\ }i{\in}V_2,j{\in}V_1\tag{9}\\ h_i^{(t+1)}&=f_{node}(h_i^{(t)},{\sum_j}m_{j{\rightarrow}i},{\sum_{j^{\prime}}}{\mu_{j^{\prime}{\rightarrow}i}})\tag{10}\\ h_{G_1}&=f_G(\{h_i^{(T)}\}_{i{\in}V_1})\tag{11}\\ h_{G_2}&=f_G(\{h_i^{(T)}\}_{i{\in}V_2})\tag{12} \end{align} \]其中的\(f_{message}\)是MLP。\(f_{match}\)是注意力机制：
\[\begin{align} a_{j{\rightarrow}i}&={\frac{exp(s_h(h_i^{(t)},h_j^{(t)}))}{{\sum_{j^{\prime}}}exp(s_h(h_i^{(t)},h_{j^{\prime}}^{(t)}))}}\tag{13}\\ \mu_{j{\rightarrow}i}&=a_{j{\rightarrow}i}(h_i^{(t)}-h_j^{(t)})\tag{14} \end{align} \]其中\(s_h\)表示一个向量相似度函数（本项目中就是点积）。\(f_{node}\)是门控循环单元（GRU），\(h_i^{(t)}\)表示其位于时间点\(t\)的现态，输入为\({\sum_j}m_{j{\rightarrow}i}\)和\({\sum_{j^{\prime}}\mu_{j^{\prime}{\rightarrow}i}}\)。GMN采用与GGNN相似的读出函数（等式\((7)\)）。总体来看GMN模型和GGNN模型是相似的，唯一主要区别在于GMN增加了GRU的输入项（交叉图匹配向量）。