微软提出程序图方法:从源代码中学习,揪出恼人的Bug

707 阅读7分钟

作者|微软
编译|Debra
编辑 | Emily
AI 前线导读在过去五年中,基于深度学习的方法已经彻底改变了很多应用,例如可以理解图片、语音和自然语言的应用。对于计算机科学家来说,他们自然而然会提出一个疑问:计算机是否学会了理解源代码?乍一看,这似乎是一个微不足道的问题,因为编程语言的确被设计为可以被计算机所理解。但是,许多软件 bug 的出现,实际上反映了开发者的真实心理:他们希望代码按他们想要的方式去执行,而不是按他们写的去执行。换句话说,小的错别字会带来很严重的后果。

更多干货内容请关注微信公众号“AI 前线”,(ID:ai-front)

以下是一个简单的例子:

float getHeight {return this.width; }。

在这个例子中存在的问题对于人类,或一个可以理解术语“高度”和“宽度”含义的系统是显而易见的。它的关键洞见是源代码提供两种功能。首先,它向计算机传达应该准确执行哪些硬件指令。其次,它向其他程序员(或六周后向作者自己)传达程序如何工作的信息。后者是通过选择名称、代码布局和代码注释来实现的。通过识别两个通信渠道出现分歧的情况,自动系统会指出可能存在的软件缺陷。

过去的程序分析主要集中在正式的、机器可解释语义的程序上,或者它把程序视为自然语言的一个(有点奇怪的)例子。前者这个方法来源于数学逻辑(https://www.microsoft.com/en-us/research/research-area/programming-languages-software-engineering/),需要针对每个需要处理的新案例进行大量的工程设计工作。另一方面,自然语言方法则涉及自然语言处理工具(https://www.microsoft.com/en-us/research/research-area/human-language-technologies/)的应用,这些工具在纯粹的句法任务上运作良好,但迄今还不能学习程序的语义。

在 ICLR 2018 年发表的一篇新论文中,来自微软研究院和温哥华西蒙弗雷泽大学的研究人员提出了一种将这两者结合起来的新方法,并展示了如何用这种方法找出已发布软件中的错误。

程序图

为了能够从丰富的源代码结构中学习,首先需要将它转化为程序图。图的节点包括程序的标记(即变量、运算符、方法名称等)及其抽象语法树的结点(定义语言语法的元素,如条件语句)。程序图包含两种不同类型的边缘:句法边缘只表示应该如何解析代码,比如 while 循环和 if 块;以及作为简单程序分析结果的语义边缘。


句法边缘包括简单的“NextToken”边,用于表示抽象语法树的“Child”边,和用于将源代码与源代码文本中最后一次发生连接的“LastLexicalUse”边。图 1 以语句 Assert.NotNull(clazz)为例展示了这种边,其中与 token 对应的节点是灰色框,与程序语法的非终端对应的节点是蓝色椭圆。子边缘显示为蓝色实心边缘,而 NextToken 边缘为黑色双边缘。

语义边缘包括将变量连接到上一次可能在程序执行中使用过的“LastUse”边缘,“LastWrite”边缘则连接到上一次写入的变量,“ComputedFrom”边将变量连接到计算值。利用程序分析工具箱中的其他工具(例如别名和点对点分析)以及路径条件,可以获得更多的语义边缘。图 2 展示了一小段代码中的一些语义边缘(黑色)。


LastUse 关系以绿色边缘显示。因此,例如,y 与循环之前的 y 的最后一次使用以及自身相关联。同样,LastWrite 关系显示为红色边,因此在 while 条件中使用 x 与循环前的 x 赋值,以及循环内 x 的赋值相关联。最后,ComputedFrom 关系由蓝色边缘表示,将变量连接到从中计算出来的变量。

句法边缘大致对应程序员在阅读源代码时看到的内容。另一方面,语义边缘则与程序如何执行相对应。通过将这些概念结合在一张图中,系统可以同时从更多的信息源中学习。

从图形中学习

最近,从图形结构数据中学习引起了一些关注,因为图形是表示数据及其关系的标准方式,例如我们可以用一张图包含一个组织或药物成分的信息。近期图形深度学习比较成功的两种方法有图形卷积网络(graph convolutional networks,卷积网络的扩展,是图像理解的关键)和门控图形神经网络(gated graph neural networks ,广泛用于自然语言处理的递归神经网络的扩展)。

这两种方法首先均对每个节点进行独立处理,以获得节点本身的内部表示(即低维空间中的向量)。随后,重复地将每个节点的表示与它所连接的节点的表示相结合(两种方法的组合方式有所不同)。因此,在第一个步骤之后,每个节点都包含其自身及其直接邻居的信息;在第二步之后,它获得两步之外的节点的信息,以此类推。由于该方法的所有步骤都在(小)神经网络上进行,因此可以训练它们从数据中提取与整体任务相关的信息。

寻找错误

学习程序图可用于查找错误,例如本文开头的示例中所示的错误。为了这个目的,该模型被赋予一个程序,该程序中的一个位置以及可以在该位置使用的变量列表,之后要求模型预测应该使用哪个变量。为了处理这个任务,程序被转换成一个图形,其中一个特殊节点对应要选择的位置。通过权衡该特殊节点的计算表示以及与可用变量相对应的节点表示,网络可以计算每个变量可能性的大小。为这样的模型提供数百万行现有的代码,以及不需要特别注释的数据集,就可以轻松进行训练。

当在新代码上运行这个模型,并以很高的概率预测 var1,但程序员选择了 var2 时,这可能表示这是一个错误。通过标记这些问题让人类专家审查,我们就可以发现实际的错误。以 Microsoft C#编译器 Roslyn 获取的代码为例:


请注意突出显示的参数文件路径和字段 _filePath 的用法,它们很容易被混淆。_filePath 是一个错字,开发人员在研究人员报告了这个问题和类似问题后将之修复。在其他一些 C#项目中也发现了类似的 bug,被报告之后得到修复。

在量更大的定量评估中,这种新方法比传统的机器学习技术要好得多。作为基准测试方法,它考虑到了直接在源代码上工作的双向递归神经网络(BiRNN)以及访问数据流信息的 BiRNN 的简单扩展。为了评估不同的模型,他们分析了总共包含 290 万行源代码的开源 C#项目。在不同的机器学习模型中使用其中单个变量被删除并被要求预测最初使用的变量(假设代码经过充分测试且总是正确的)的源代码进行测试。在第一个实验中,他们用已保存的文件对这些模型进行训练。在第二个实验中,使用全新项目的数据测试这些模型。结果如下表所示,使用新的程序图测试结果更好。image

未来的应用

程序图是一种将深度学习方法应用于程序的多功能工具。微软将在明年的 AI Residency Program(https://www.microsoft.com/en-us/research/academic-program/microsoft-ai-residency-program/)中继续研究其未来的应用。


相关链接


  • 开源代码实现:https://github.com/Microsoft/gated-graph-neural-network-samples

  • Deep Program Understanding projecthttps://www.microsoft.com/en-us/research/project/program/

  • 门控图神经网络论文https://arxiv.org/abs/1511.05493

  • 门控图神经网络代码库https://github.com/Microsoft/gated-graph-neural-network-samples

  • 学习用图表来表示程序 - ICLR'18 论文https://arxiv.org/abs/1711.00740

原文链接:

https://www.microsoft.com/en-us/research/blog/learning-source-code/