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

【解放程序员】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)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 危险!一张贴画就能迷惑AI,对抗补丁或让自动驾驶车毁人亡

    来自北京航空航天大学(Beihang University)、悉尼大学(University of Sydney)和剑桥大学(University of Cam...

    新智元
  • 【智驾深谈】撑起自动驾驶半壁江山:剧学铭谈Ibeo激光雷达

    【新智元导读】上图是美国Darpa无人车比赛的参赛车,车上犄角样的设备,全是激光雷达。作为自动驾驶最重要的传感器之一,激光雷达已毫无疑问成为业界关注的重点。大...

    新智元
  • 深度|详解自动驾驶核心部件激光雷达,它凭什么卖70万美元?

    【新智元导读】作为自动驾驶汽车的核心部件之一,激光雷达传感器以昂贵出名,此前的价格高达70万美元,远超普通汽车。自动驾驶研究专家黄武陵在本文中介绍了激光雷达传感...

    新智元
  • 微信Android热补丁实践演进之路

    继插件化后,热补丁技术在2015年开始爆发,目前已经是非常热门的Android开发技术。其中比较著名的有淘宝的Dexposed、支付宝的AndFix以及Qzon...

    张绍文
  • 去噪算法升个级,图片瞬间变清晰 | 论文

    图像上噪点太多了,一大片都是点点的雪花连女神的脸都看不清了,传统去噪方法效果太差,可否有破解方法?

    量子位
  • 补丁管理:不要以持续运行时间为自豪

    在补丁管理方面一些 Linux 系统管理员和 Windows 系统管理员没有差别。实话说,在一些方面甚至做的更差(特别是以持续运行时间为自豪)。 -- Kyle...

    企鹅号小编
  • 如何有效地对Linux系统补丁进行管理 ?

    1. 前 言 本文所所采用的截图,大部分由笔者在红帽的同事马林提供,在此表示感谢。 最近几个月,全球勒索病毒肆虐。如之前的WannaCry,前两...

    魏新宇
  • k8s集群部署高可用完整版

    yuezhimi
  • 网络协议 18 - CDN:家门口的小卖铺

        到现在为止,我们基本上已经了解了网络协议中的大部分常用协议,对于整个 HTTP 请求流程也较为熟悉了。从无到有后,我们就要考虑如何优化“有”这个过程,也...

    北国风光
  • 基于envoy的分布式gateway-contour

    Contour是开源的Kubernetes入口控制器, 为Envoy边缘和服务代理提供控制平面. Contour支持动态配置更新和多团队入口委托,同时保持轻量级...

    有点技术

扫码关注云+社区

领取腾讯云代金券