微软研究院：基于图模型表示程序，通过深度学习自动找出bug

来源：微软研究院

编译：weakish

最近有一些研究将深度学习应用到源代码这样的形式语言上，不过大部分的工作只是尝试将自然语言方法迁移到形式化语言上，而没有很好地利用代码语法的特性。比如，大部分的工作都没有考虑变量和函数引入的长距离依赖关系。最近的ICLR 2018上，微软研究院的研究人员提交的论文Learning to Represent Programs with Graphs（地址：https://www.microsoft.com/en-us/research/wp-content/uploads/2017/11/programGraphs.pdf）用图模型表示代码的语法语义结构，并使用基于图的深度学习方法学习理解程序结构，成功找到了知名开源项目中的bug。在ICLR 2018的评审中，本论文名列十佳。

图模型背后的直觉

如前所述，当前应用于源代码的深度学习模型，绝大部分仅仅刻画了代码肤浅的文本结构，包括：

token序列

解析树

变量的扁平依赖网络

这些模型忽略了代码明确定义的、丰富语义，仅仅迁移了自然语言处理方法。

当然，也有研究注意到了这些模型的缺陷，尝试利用代码的语义改善模型的表现。

比如，当前大部分模型基于变量的扁平依赖网络，这样的模型显然没有充分利用代码中变量的特性。代码中的变量有哪些特性呢？

首先，变量是有作用域的。只有在相应的作用域中，才能使用变量。在作用域之外，变量是不可见的。因此，在理解作用域的基础上，统计变量的所有用例，可以更精确地建模。

其次，在静态类型语言中，变量的类型经常是显式声明的，有时则是由编译器自动推断得出。无论哪种情况，变量的类型都是确定的，否则编译器会报编译错误。那么这个类型信息，也是可以供模型利用的。

Allamanis等在2015年提出了学习变量的分布式表示的方法，就利用了变量的所有用例来预测变量的名称。而Raychev等在2015年和Bichsel等在2016年的研究，建模了变量、AST元素和类型之间的关系来预测变量名和类型，就利用了变量的类型信息。

最后，变量不是孤立的，而是处于flow（流）之中。实际上，一些现代程序语言的类型系统，已经利用flow提供的信息来推断变量的类型。这一技术被称为flow-sensitive typing或flow typing。

比如，在支持flow-sensitive typing的Whiley语言中，编译器可以成功推断x的类型：

real f(int y):

if y > 1:

x = y

else:

x = 2.0

return x

如果y大于1，则x的类型为int，否则为real。

Whiley于2009年引入flow-sensitive typing，是最早使用此特性的语言。之后，Ceylon、Kotlin和TypeScript等语言也引入了此特性。

同理，深度学习也可以利用flow，来改善模型的表现。微软研究院的本项工作，就在建模时利用了flow信息。

最终得到的模型效果不错。比如，模型能发现下面的代码中第4行Assert.NotNull(clazz);中的clazz应该是first。目前的IDE难以发现这样的错误，因为first在之后的语句中使用了。

GGNN

本工作的模型基于GGNN（Gated Graph Neural Networks）。这里简单介绍一下GGNN。

GGNN可以用下式表示：

上式中，V表示节点。

E表示由离散的边的集合组成的列表：

k表示边的类型数。

其中，X表示节点的特征，我们用一个实数组成的向量x(v)表示节点x的特征。我们给每个节点分配了一个状态向量h(v)，该向量基于x(v)初始化。

然后，为了在图中传播信息，我们使用m(v)k表示节点v传递给相邻节点的类型为k的“消息”。“消息”的内容，基于当前状态向量计算，即m(v)k = fk(hv)，这里，fk可以是任意的函数。通过同时计算所有边的消息，可以同时更新所有的状态。具体来说，聚合所有收到的信息可以计算出节点v的新状态。

消息集合的条件是节点u和节点v之间存在类型为k的边

上式中，g是聚合函数。基于聚合消息和当前的状态向量h(v)，下一时刻的状态h'(v)可以通过下式计算：

程序图

我们将程序的源代码表示为图，骨架为程序的AST。

想一想，在AST层面，模型需要包含哪些与语义相关的信息。

首先，顺序是重要的。显然x / y和y / x的语义完全不同。因此，图模型使用NextToken类型的边表示这一语义。

其次，AST既然是抽象语法树，顾名思义，存在层次关系。因此，图模型使用Child类型的边表示这一语义。

比如，以下语句

表示为

上图中，黑色的方框表示语法token，而蓝色的圆角框表示语法节点。黑色的NextToken边将语法token与它的后继节点连接起来，蓝色的Child边表示语法node间的关系。

如前所述，模型需要利用flow信息。那么flow能提供哪些语义相关的信息呢？

最容易想到的就是变量的读和写。变量在什么时候使用了，变量的值在什么时候发生了改变，显然，这是非常重要的信息。模型分别使用LastUse和LastWrite两种类型的边来表示这两类信息。

其次，在像x = y + z这样的语句中，x的值由y和z决定，因此x和y、z之间事实上存在依赖关系。因此，模型使用ComputedFrom类型的边来表示这一信息。

比如，以下代码段：

可以表示为：

为了清晰性，上图给变量标上了序号。由下往上看，x4 = x5 + y6语句中，x4的值由x5和y6计算得到，因此，x4节点与x5、y6两个节点间有ComputedFrom边相连（图中紫色的点划线）。类似的，图中红色的点线表示LastUse边，绿色的划线表示LastWrite边。

还有一些和flow无关的信息，也值得考虑。比如，在以下代码结构中：

基于flow模型，两个变量v之间并不存在LastUse关系，但它们仍属于同一变量，为了建模这一关系，模型使用LastLexicalUse边将同一变量的所有用例连接起来。

此外，方法名和return语句中的变量常常存在一定的联系。比如，考虑下面一段代码：

显然，IsDisposed和_isDisposed之间存在某种联系。

因此，模型使用ReturnsTo类型的边连接两者。

类似地，方法声明时使用的参数名和方法调用时使用的变量名之间也常常存在联系。因此，模型使用FormalArgName类型的边连接两者。这一做法受到了Rice等《Detecting argument selection defects》的启发。

最后，为了加快GGNN的传播速率，使模型更具表达力，所有类型的边都引入了相应的反向边，使边的数量和类型翻倍了。

变量的类型信息

模型假定面向的是静态类型语言，且源代码可以编译。因此，每个变量都有一个（已知的）类型T(v)。我们定义了一个可学习嵌入函数r(T)来表示已知类型，用UnkType表示未知或未表示的类型。为了利用很多面向对象语言的类型层次，我们将一个变量的类型T(v)映射到它的超类：

通过计算元素最大值得出类型表示r*(v)。

节点表示初始化

将节点名称切分为子token（例如，camelCase切分为camel和case，pascal_case切分为pascal和case），对所有子token的词嵌入取平均，得到节点名称的嵌入，与r*(v)连接，所得用0补齐，以便和GNNN的隐藏层尺寸保持一致。

VarNaming的程序图

给定一个程序和一个现有的变量v，按照前述方法构建一个图模型，然后将变量名替换为一个特殊的 token。使用上一节介绍的方法初始化节点表示，接着运行GGNN共8时步（经过测试发现，更少的次数不够用，更多的次数表现并不更好），然后通过对所有 token的表示取平均以计算变量用例的表示。该表示进一步作为单层GRU的初始状态，用于预测目标名称（以子token序列表示，例如，inputStreamBuffer表示为[input, stream, buffer]）。我们以最大似然为目标，训练graph2seq架构。

VarMisuse的程序图

为了建模VarMisuse，需要修改图。

首先，对于给定的slot t，插入一个新节点vSLOT，然后使用所有不依赖于选定的变量的边（也就是LastUse、LastWrite、LastLexicalUse之外所有的边）将其与图的剩余部分连接起来。通过这样的方法，我们计算出t的上下文表示c(t)。

类似地，对于目标slot而言，插入一个候选节点vt,v，使用LastUse、LastWrite、LastLexicalUse三种类型的边将其与图的剩余部分连接起来。拖过这样的方法，我们计算出t处的候选变量v的用例表示u(t, v)。对所有的候选变量都进行类似的操作。

同样，运行GGNN共8时步。将上下文表示和用例表示作为节点的这种状态。正确的变量用例通过arg maxvc(t)Tu(t, v)计算得出。和VarNaming一样，基于最大似然进行训练。

实现

由于实际项目的源代码规模较大，结构比较复杂。因此转换成的图模型也很大，也比较多样化。在这样的图上应用GGNN是一个挑战，一方面是规模大，另一方面是多样化的形状很难进行高效的batching。一个重要的洞见是，巨大的图通常而言比较稀疏，因此将边表示为邻接表通常有助于降低内存使用。研究人员基于稀疏张量表示实现了这一点，从而使batch尺寸较大，可以高效地利用现代GPU的并行特性。另一个关键的洞见是，将图batch表示为由许多孤立的部分组成的大型图。这只需要进行适当的预处理，保证节点标识唯一。由于这会让batch构建给CPU更多的压力，因此研究人员使用独立的线程预备minibatch。在单张Nvidia GeForce GTX Titan X上，对于平均有2228（中位数 936）个节点、8350（中位数3274）条边、8 GGNN展开迭代、16个边类型（原本有8类，加上反向版本后共16类）、隐藏层尺寸为8的图，研究人员基于TensorFlow的实现可以在训练和测试时分别达到每秒55图和每秒219图的速率。

评估

评估的数据取自GitHub上的开源C#项目。选择了GitHub上收藏数最多的一些项目，然后剔除难以使用Roslyn编译的项目。Roslyn是微软开发的.Net编译器，提供了丰富的代码分析API。由于模型需要编译器能提取代码的准确类型信息（包括由外部库提供的类型），因此剔除了难以使用Roslyn编译的项目。最终得到的数据集包括29个项目，290万行代码，覆盖编译器、数据库等多个领域。

最终的测试结果表明，无论是在类型和结构已知的项目（SeenProject）还是在类型和结构未知的项目（UnseenProject）上，GGNN的表现都比基准模型要好。

为了验证模型的设计上的一些选择，研究人员也进行了消融研究。

同时，基于这个模型，研究人员在一个收藏数1500以上、测试齐全的GitHub项目中找到了3个bug。文章开头的例子就是其中一例bug。