【解放程序员】MIT“创世纪”机器学习新系统,自动生成补丁修复Bug

【新智元导读】当您辛辛苦苦写了大半年程序,终于要享受一下国庆长假的时候,别让 bug 把您的假期毁了。MIT 研究团队开发了一个称为“创世纪”的系统,能够对以前的补丁进行自动学习,生成补丁模板,并对候选补丁进行评估。它修复的 bug 几乎是最好的手编模板系统的两倍,大大减少了程序员修复bug的工作量。

长假来了,你放假了,但你辛辛苦苦编程的软件没有放假。它还在产生着 bug......

关于程序员大哥发现 bug 以后的心态,我们也略知一二:

别人写的代码有 bug——谁写了这么个烂代码,幸亏有哥这样神一样的存在才发现,哥真是救世主

自己写的代码有bug——

(1)运行很久

<1>别人发现 这个程序运行很久了是不是真有bug啊,是不是你弄错了啊,可以重现么,什么?可以重现,那问题也不大,要不用户早投诉了,瞧你那惊慌失措的样子,至于么?

<2>自己发现 这个bug隐藏的很深啊,还好哥犀利犀利,没有被领导发现,今晚加个菜 (2)新上线程序 <1>别人发现 这个程序刚上线还处于调试阶段,有bug很正常,谁的程序没bug,连操作系统都有bug <2>自己发现 哥就是犀利,自己开发自己测试,看测试那帮人什么也不会干,这么明显的bug都测不出来

不管怎么说,不能让 bug 把你的长假毁了!让我们关注一下 MIT 研究团队的新研究,他们开发了一个称为“创世纪”的系统,能够对以前的补丁进行自动学习,生成补丁模板,并对候选补丁进行评估。据研究者说,“创世纪是第一个自动推理补丁生成转换或根据先前成功的补丁搜索候选补丁空间的系统”,它修复的 bug 几乎是最好的手编模板系统的两倍。如果有更多的训练数据和更强的算力,也许会得到更好的结果,而现在它已经可以让程序员只花费以前一半的时间来修复 bug 了。

“创世纪”修复的 bug 几乎是最好的手编模板系统的两倍

几乎所有软件都会有 bug 和安全漏洞,需要时不时的“打补丁”。这些 bug 常常只是一些疏忽引发的。比如说,程序努力在读取已经删掉的数据。这些补丁往往也很简单,比如一行确定数据仍然还存在的代码。

这种简单性鼓励计算机科学家开始探索自动补丁生成的可能性。一些研究团队,比如MIT 电气工程与计算机科学教授Martin Rinard 领导的小组,开发了一些模板,这些模板涵盖了补丁常采用的一般形式。然后,算法可以使用模板来生成一些候选补丁,并对它们进行评估。

最近,在 ACM 的专题研讨会上,Rinard和他的学生Fan Long,以及加州大学圣地亚哥分校的 Peter Amidon 介绍了一个新的系统,该系统能够通过分析在实际软件中应用成功的补丁,自己学习构建模板。

手工编码的补丁生成系统可能有 5 个或 10 个模板,新系统则创建了85 个,这使得它更加多样化,同时也更精确。这些模板是根据真实补丁的特定类型“订制”而成,因此不会产生尽可能多的无用备选。在测试中,这个被称为“创世纪”(Genesis)的新系统修复的错误几乎是最好的手编模板系统的两倍。

研究报告的第一作者、MIT 电气工程与计算机科学研究生Long 表示:“你需要进行权衡。一方面,你想产生足够的备选,好让这个集里包括有用的补丁。另一方面,你不希望这个集里面包含太多备选,以致于无法搜索。“

研究者自述:四大贡献造就第一个自动推理补丁生成转换系统

论文摘要:

我们提出了一个新的系统,称为“创世纪”(Genesis),它能够处理手工编码的补丁,自动推理代码转换,以实现补丁自动生成。我们展示的结果表明了创世纪推理算法的有效性和完整的创世纪补丁生成系统,它处理了从 372 个Java项目收集的真实补丁和缺陷。据我们所知,创世纪是第一个自动推理补丁生成转换或根据先前成功的补丁搜索候选补丁空间的系统。

图1

图1:创世纪转换的示例推理和应用。顶部是训练补丁(初始代码和补丁代码),中间是推理转换(inferred transform),底部是创世记生成的新补丁。

本研究的贡献主要有以下四点:

  • 使用模板AST和生成器进行转换:我们用模板AST 和发生器,为自由模板变量提出了新的变量。这些转换使创世纪能够抽象出补丁和应用程序特定的细节,以捕获由不同应用程序绘制的多个补丁中存在的常见模式和策略。生成器使创世纪能够合成所需的新代码和逻辑,以获得在大规模实际应用中出现的bug 的正确补丁。
  • 补丁泛化:我们提出一种新的补丁泛化算法,给定一组补丁,自动生成捕获了补丁中常见补丁生成模式的转换。该转换可以生成所有给定的补丁以及在相同或其他应用程序中具有相同模式的其他补丁。
  • 搜索空间推理:我们提出了一种新颖的搜索空间推理算法。从一组训练补丁开始,该算法推理出一组转换,它们一起生成具有良好覆盖和易处理性的候选补丁的搜索空间。推理算法包括一个新的采样算法,它可以识别训练补丁中“有前景”的子集来进行泛化,以及针对最终搜索空间选择问题的基于ILP的解决方案。
  • 完整的系统和实验结果:我们提供了一个完整的补丁生成系统,包括bug 定位和候选补丁评估算法,它们使用推理搜索空间自动修补大规模现实应用中的缺陷。我们还介绍了这个完整系统的实验结果。

图2

图2:使用整数线性规划来选择一组有效的转换组。

据我们所知,创世纪是第一个自动推理补丁生成转换或根据先前成功的补丁搜索候选补丁空间的系统。所有实验数据(包括创世纪源代码、推理模板和生成的补丁)可从http://groups.csail.mit.edu/pac/patchgen/ 获得。

选择模板:在可以更正的 bug 数量和生成的无用候选补丁数量中做 tradeoff

创世纪训练的数据集中的每个项目包括两个代码块:原始的、错误的代码和修复它的补丁。创世纪从构建训练样本对开始,数据集中的每个项目都与其他项目配对。

接下来,创世纪对每一对进行分析,并创建一个通用的 representation——一个草案模板——这将使它能够合成两个原始代码的补丁。它或许也合成了其他无用的备选。但 representation 必须足够通用,是备选中成功的补丁。

然后,创世纪会在训练集中的所有样本上对每个草案模板进行测试。每个模板仅基于两个样本,但它可能适用于其他几个。对每个模板,都根据两个标准进行评分:可以更正的错误数量和它生成的无用备选数量。例如,生成 10 个备选补丁的模板,其中4 个能够纠正训练数据中的错误,它就可能会比生成1,000个备选但只有 5 个正确补丁的得分高。

根据这些分数,创世纪选出了500 个最有前景的模板。对于它们中的每一个,它再次用其他样本中增强初始的两个训练样本集,创造出一个巨大的含有三个样本的训练集。对于每一个样本,它调整其草案模板,以产生更通用的模板。然后执行相同的评估程序,提取 500 个最有前景的模板。

经过四轮这样的过程,500 个顶级模板中的每一个模板都已经在五个样本集上进行了训练。最终的筛选使用了略微不同的评估标准,以确保训练集中的每个错误都可以被纠正。也就是说,在最后的 500 个模板中,可能有一个模板,它的补丁可能只能纠正一个错误,在前一轮的评估中得分相对较低。但是,如果它是修补该 bug 的唯一模板,那么它就是最终胜者。

在研究人员的实验中,最终的筛选将模板的数量从 500 个减少到85 个。创世纪使用Java 编写的程序,MIT 的研究者将其性能与最好的手写Java 补丁生成器进行了对比。创世纪正确修补了 41 个开放源代码编程项目中的49 个测试用例中的21 个 bug,而旧有的系统则修补了 11 个。

如果有更多的训练数据和更强的计算能力——以评估更多的候选模板——有可能得到更好的结果。不管怎么说,一个使得程序员只花费以前一半的时间来修复代码中错误的系统,肯定是有用的。

原文链接:http://www.csail.mit.edu/bug_repair_system_learns_from_example

原文发布于微信公众号 - 新智元(AI_era)

原文发表时间:2017-10-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

谷歌、亚马逊和百度的深度学习野心:TensorFlow、MXNet、PaddlePaddle 三大框架对比

【新智元导读】本文作者陈汝丹从定位、框架使用、分布式构成三个方面比较了 TensorFlow、MXNet、PaddlePaddle三个常用开源框架。 本文转载自...

37460
来自专栏机器之心

教程 | 从预处理到部署:如何使用Lore快速构建机器学习模型

选自Medium 作者:Montana Low 机器之心编译 参与:李诗萌、思源 机器学习的构建和部署通常需要非常多的工作与努力,这对于软件开发者和入门者造成了...

41350
来自专栏新智元

Kaggle放大招:简单几步实现海量数据分析及可视化

【新智元导读】近期,Kaggle发布了新的数据分析及可视化工具——Kaggle Kerneler bot,用户只需上传数据集,便可用Python为用户自动获取相...

15530
来自专栏程序员的知识天地

5个方法对于重量级网站的图片优化

图像是每个网站的关键组成部分。 根据 HTTP Archive ,图像占网页上需要加载总数据的比例达60%以上。 几乎成为所有网站上重要的组成部分,无论是电子商...

39420
来自专栏企鹅号快讯

你的深度学习应用可能存在安全风险

360安全实验室(肖奇学 、Deyue Zhang)、佐治亚大学(李康)和弗吉尼亚大学(Weilin Xu)的研究者,他们在论文《Security Risks ...

24250
来自专栏CSDN技术头条

基于OpenGL ES的深度学习框架编写

背景与工程定位 背景 项目组基于深度学习实现了视频风格化和人像抠图的功能,但这是在PC/服务端上跑的,现在需要移植到移动端,因此需要一个移动端的深度学习的计算框...

46180
来自专栏郭耀华‘s Blog

SmileyFace——基于OpenCV的人脸人眼检测、面部识别程序

项目地址 https://github.com/guoyaohua/SmileyFace 开发环境 Visual Studio 2010 MFC + OpenC...

40450
来自专栏CDA数据分析师

工具 | Python 和 R 数据分析/挖掘工具互查

在此总结一些在数据分析/挖掘中可能用到的功能,方便大家索引或者从一种语言迁移到另一种。如果大家已经熟悉python和R的模块/包载入方式,那下面的表查找起来相对...

25670
来自专栏安全领域

在物联网中应用机器学习:使用 Android Things 与 TensorFlow

在本教程中,我们将探索如何使用 Android Things 和 TensorFlow 将机器学习应用到物联网中。

1K160
来自专栏AI科技评论

开发 | 谷歌发布TensorFlow 1.4版本:支持分布式训练,迎来三大新变化

e Developers blog正式撰文发布TensorFlow 1.4版本,此次的更新迎来三个重大变化:Keras位于TensorFlow core中,Da...

31130

扫码关注云+社区

领取腾讯云代金券