写点什么

Facebook 智能 bug 修复神器:让程序员少掉几根头发

2018 年 11 月 07 日

Facebook智能bug修复神器:让程序员少掉几根头发

Facebook 开发了一款名为 Getafix 的工具,可以自动查找出 bug 的修复方案,并提供给工程师审批,这极大提高了工程师的工作效率和整体代码质量。Getafix 不仅能够为工程师提供直观的修复方案,还能利用更强大的聚类算法,分析问题代码的上下文找到更合适的修复方案。Getafix 是第一款被大规模部署到 Facebook 生产环境中的自动修复工具,它进一步提升了 Facebook 拥有数十亿用户的应用程序的稳定性和性能。

现代的生产环境代码库非常复杂,并且一直持续不断地更新。为了创建一个可以自动查找 bug 修复方案的系统——在没有工程师帮助的情况下——我们构建了一个工具,可以从工程师之前对代码库的更改中学习如何修复 bug。它找到了一些隐藏的模式,并用这些模式来识别最有可能修复新 bug 的补救措施。

image

这个工具叫作 Getafix,已经被部署到 Facebook 的生产环境中,进一步提升数十亿人使用的应用程序的稳定性。Getafix 一般与 Facebook 其他两个工具结合使用,不过这项技术也可以用于其他地方。它目前能够为 Infer 发现的 bug 提供修复建议,Infer 是我们的静态分析工具,可识别 Android 和 Java 代码中的 null 指针异常等问题。它还通过 SapFix 提供修复建议——针对我们的智能自动化测试系统 Sapienz 检测到的 bug。现在,我们将深入了解 Getafix 是如何学习修复 bug(指任意代码问题,而不仅仅是导致应用程序崩溃的问题)的。

Getafix 的目标是让计算机处理日常工作,不过是在人类的监督之下,因为一个 bug 是否需要复杂的修复仍然需要由人类做出决定。这个工具将一种新的层次聚类方法应用于之前的数千个代码变更上,同时检查代码变更本身及其上下文。它可以检测 bug 的基础模式,并提供之前的自动修复工具无法检测到的修复方案。

Getafix 还能够在 bug 修复过程当中,显著缩小程序当中可能需要更改的具体空间,从而更快地选择适当的修复手段 ; 此外,其不再像以往暴力破解及基于逻辑型技术那样对计算时间提出极高的要求。这种更为高效的方法使得 Getafix 被成功部署至生产环境当中。与此同时,由于 Getafix 能够以以往代码变化为基础进行学习,因此足以产生让人类工程师更容易理解的修复结论。

Getafix 目前已经在 Facebook 生产环境中部署完成,负责自动对 Infer 报告提供 null 解引用 bug 进行修复,同时亦可为 Sapienz 标记的与 null 解引用相关的崩溃错误提供修复建议。此外,Getafix 还被用于解决在较新版本 Infer 重新访问现有代码时所发现的代码质量问题。

Getafix 与传统简单自动修复工具有何不同

在目前的行业实践当中,自动修复功能主要用于各类基础性问题,而代码修复则更为简单。举例来说,分析器可能会提出“致命异常”警告,强调开发人员可能忘记在新的 Exception(…) 之前添加一个 throw。自动修复工具能够直接完成调整,而具体调整方式则可通过 lint 规则进行定义——换言之,其并不需要了解操作应用的特定情景。

Getafix 则完全不同,它提供更多通用性功能,并可结合上下文相关因素来解决问题。在以下代码示例当中,对应第 22 行中的 Infer 错误,Getafix 给出了下列修复结论:

image

需要注意的是,此修复方法不仅取决于变量 ctx,同时也与方法的返回类型相关。与简单的 lint 修复方法不同,此类修复程序无法被纳入 Infer 本身。

下图所示为 Getafix 为 Infer bug 提供的修复方法 ; 尽管来自 Infer 的 bug 总是相同的(null 方法调用,有可能引发 NullPointerException 风险),但每一项具体修复操作仍然独一无二。另外需要强调一点,Getafix 的修复方法与人类开发者的常见操作完全一致。

image

深入了解 Getafix 关键技术细节

Getafix 的组织形式如下图内工具链所示。在本节中,我们将描述 Getafix 的三大主要组件及其各自的功能与挑战。

image

Tree Differencer 标识树级别的更改

基于抽象语法树的 Differencer 首先负责在两个源文件之间识别实际的编辑痕迹,例如针对同一文件的连续修订。举例来说,它会检测以下粒度的编辑:使用 if 打包语句、添加的 @Nullableannotation 或者 import,以及将条件提前返回至某一现有方法之内等等。在以下示例中,插入条件判断语句 if dog is null 并提前返回、将 public 重新命名为 private、方法的移动都会被检测为实际编辑。而基于行的 diffing 工具只会将方法标记为完全移除与插入,Tree Differencer 则能够检测到这一移动并将移动方法之内的插入操作视为实际编辑。

Tree Differencer 的主要挑战在于如何有效且精确地对树级别中的“之前”与“之后”部分进行对齐,从而识别出正确的实际编辑及其映射关系。

image

新的修复模式挖掘方法

Getafix 通过利用新的层次聚类技术以及反合一方法(即一种能够在不同符号表达式之间实现泛化的现有方法)进行模式挖掘。在此之后,它会建立可能相关的树差异集合,进而选择该集合中最为常见的程序并转换为修复模式。这些模式可能是抽象的,且包含程序转换所面向的不同“漏洞”。

以下示例图像展示了一组层次结构,即树状图,其通过一组编辑生成。(在本示例中,我们直接采用上个示例中的编辑结果。)每一行皆展示出一种编辑模式——其中紫色代表“之前”,蓝色代表“之后”——以及一些元数据。每个垂直黑条对应于层次结构中的具体层级,其中黑条顶部的编辑模式代表着通过对该结构中所有同一层级的其它编辑进行反合一所获得的模式。其它编辑由较细的黑色线条连接。反合一将来自上一示例中的“如果 dog 为 null 则提前返回”条件与另一条编辑相结合——后者的唯一区别在于“dog 正在饮水”。结果是,其将生成一个代表共性的抽象修复模式。由反合一引入的符号 h0 代表着可以基于上下文实现实例化的“漏洞”。

image

接下来,该编辑模式可以与其它变量名称更为多样但仍然具有相同整体结构的编辑模式相结合。在根据梳理树状脉络时,整个流程将产生越来越抽象的编辑模式。举例来说,其能够将此编辑与同猫相关的编辑组合在一起,从而获得位于图表上方位置的抽象编辑。

更值得强调的是,这种分层匹配流程为 Getafix 提供一套强大的框架,足以在代码变更中发现各类可复用模式。以下图片所示,将总计 2288 项用于修复我们代码库内 Infer 报告 null 指针错误的编辑汇总为一套树状图(横向布局,小型化)。我们希望挖掘的修复模式,无疑正隐藏在这份树状图内。

image

基于反合一方法的模式挖掘并非什么新鲜事物,但要想以尽可能少的修复操作解决新 bug,我们还需要对挖掘得出的模式结果做进一步强化。

其中的变化之一就是引入一部分周边代码,即编辑结果当中没有变更的部分。如此一来,我们不仅能够发现人们在变更中采取的模式,同时也能发现应用变更时上下文中存在的某些模式。举例来说,在上面的第一份树状图中,我们注意到有两项不同的编辑会在 dog.drink(…); 之前添加 if(dog==null)return。尽管 dog.drink(…); 没有变更,但其应被作为模式“之前”与“之后”部分的上下文信息进行考量,从而帮助我们理解这项修复的应用情景。从更高的编辑层级上考虑,dog.drink() 这一上下文与其它上下文合并成为了抽象的上下文 h0.h1(),用以限制模式的适用位置。在下一节中,我们将介绍另一个更具现实意义的示例。

根据以往的自动修复工具文献所述,贪婪聚类算法往往不太可能学习到上述情况。这是因为贪婪聚类算法倾向于维持各个聚类的单一表示,因此如果上下文不存在于训练数据的全部编辑当中,则该算法将不会引入该上下文。例如,如果某项编辑会在 do(list.get()); 与以上示例中提到的 dog.drink() 合并时插入 if (list != null) return,那么贪婪聚类算法会丢弃全部关于提前返回具体插入位置的上下文。与此相反,Getafix 的分层聚类方法则尽可能在各层级上保留上下文,从而确保整体结构的通用性水平。在某种程度上讲,虽然我们希望学习的某些常规上下文可能丢失,但其仍将存在于结构当中的某些底层位置。

除了周边代码之外,我们还将编辑与提示这些编辑的 Infer bug 报告关联起来,从而了解编辑模式与对应的 bug 报告之间的映射关系。在前文第一份树状图中,可以看到 Infer 在 bug 报告中将“errorVar”视为 bug 来源变量,并在进行反合一之后给出漏洞 h0。以此为基础,我们接下来即可在发布新的 Infer bug 报告时将需要关注的变量修改为 h0,从而使得整个修复模式更为具体。

Getafix 如何创建补丁

最后一步,我们需要考虑如何获取存在 bug 的源代码并从挖掘到的结论中生成修复模式,从而针对源代码生成修复补丁。在这方面,我们往往拥有多种修复模式可以选择(如前文树状图所示)。因此,接下来的挑战就是如何选择正确的模式以修复特定 bug。如果该模式适用于多个位置,Getafix 还需要选择出正确的匹配项目。以下示例说明了我们采用的常规方法以及如何在 Getafix 当中切实解决这项挑战。

示例 1:考虑我们之前挖掘到的模式: h0.h1(); → if (h0 == null) return; h0.h1();

下面,我们将简要介绍如何为完全陌生的代码生成以下补丁。

image

Getafix 通过以下步骤创建补丁:

1. 找到与“之前”部分匹配的 sub-AST: mListView.clearListeners();

2. 对漏洞 h0 与 h1 进行实例化

3. 利用实例化之后的部分替换 sub-AST

请注意,之后部分中的 h0 是绑定的,因为其中包含了未修改的上下文 h0.h1();,这将有助于限制模式适用的位置数量。如果不修改上下文,则该模式将为 → if (h0 == null) return;。很明显,这种模式将适用于众多与预期无关的位置,例如 mListView.clearListeners(); 之后、甚至是 mListView = null; 之后。

实际上,仅插入模式也有可能出现在树状图中的某些较高位置,其中具有 h0.h1(); 这一上下文的模式已经通过负责向另一不同语句之前插入 return 的模式完成了反合一。以下示例说明了 Getafix 如何处理这类模式适用范围过广的情况。

示例 2:请考虑以下模式: h0.h1() → h0!=null && h0.h1()

通常情况下,此补丁应该来自对 if 条件或者 return 表达式的修复模式,因此我们当然希望其适用于这类上下文。但其同时也适用于其它一些情况,例如以上示例当中提到的调用语句:mListView.clearListeners();。Getafix 的排名策略会尝试对模式的修复效能做出估算,并为其分配最可能实现修复效果的上下文。这项策略使得该系统能够在之后的运行当中不再依赖于验证步骤,从而显著降低计算时间。

以上模式将与其它模式竞争,例如更为具体的 if (h0.h1()) { … } → if (h0!=null && h0.h1()) { … }或者示例 1 中仅适用于调用语句而非表达式的模式。由于具体程度更高的模式往往拥有更少的匹配位置数量,因此 Getafix 会将其视为更适合当前情况的解决方案并为其分配更高的排名。

Getafix 实际应用与表现

Getafix 现已部署在 Facebook 的生产环境中,负责为 Infer 报告的 null 解引用 bug 提供自动修复建议。顺带一提,Infer 是我们的一款统计分析工具,负责为 Sapienz 发现的、与 null 解引用相关的崩溃 bug 提供修复建议。此外,Getafix 还负责解决 Infer 以往提出的某些重要 bug。

在一次实验当中,我们将 Getafix 计算出的修复建议与以往人工编写的修复方法进行了比较,我们发现,在对大约包含 200 项小型编辑的数据集内各种 Infer null 方法调用 bug 进行修复时,需要修改的内容不足 5 行。此外,在大约四分之一的案例当中,Getafix 提出的排名最高修复补丁与人工创建的补丁完全匹配。

在另一项实验中,我们着眼于 Instagram 代码库中的一套子集,并尝试批量修复其中存在的约 2000 个 null 方法调用问题。Getafix 能够在大约六成 bug 中尝试使用某个补丁,且其中 90% 的尝试都通过了自动验证——这意味着其可编译且 Infer 将不再发出警告。总体来讲,Getafix 成功以自动方式修复了 1077 条(占比约 53%)的 null 方法调用错误。

除了针对新 Infer bug 提供修复建议之外,我们还利用相同的方式清理在原先代码审查中积压的旧有 Infer bug。我们已经清理了数百个返回不可为空的 Infer bug 以及字段不可为空的 Infer bug。有趣的是,在这项工作完成之后,Getafix 在自动修复建议中开始越来越擅长处理返回不可为空以及字段不可为空类问题,二者的成功修复占比分别由 56% 与 51% 增长至 62% 与 59%。总体而言,在过去三个月中,Getafix 提供的一系列建议帮助我们成功修复了数百项额外 bug。

Getafix 还为 SapFix 生成了修复建议,用以处理 Sapienz 检测到的崩溃问题。过去几个月以来,SapFix 所采用的修复方法中有约半数来自 Getafix 且实际有效(通过全部测试)。而在 Getafix 提供给 SapFix 的全部修复建议中,约 80% 通过了全部测试。

提升 Getafix 影响力

Getafix 帮助我们实现了让计算机处理常规 bug 修复工作这一重大目标。随着我们对自身测试及验证工具的不断完善,预计 Getafix 将能够在未来更好地防止各类部署后故障问题。

我们还注意到,Getafix 所挖掘出的修复模式不仅仅是在响应 Infer 报告的 bug; 实际上,其同时也能够针对手动代码检查结果给出修复建议。这种额外的修复模式源将给自动重复代码审查带来令人兴奋的可能性。换句话说,未来我们有可能会将代码库中曾被多次标记及修复的 bug 直接交给自动化工具处理,而不再需要任何人工筛查

Getafix 是我们构建大型代码语料库以及相关元数据统计分析智能化工具这一整体性举措中的组成部分。此类工具的出现,有望改善软件开发生命周期中的各个层面,包括代码发现、代码质量与执行效率等等。我们从 Getafix 当中获得的宝贵见解,也将帮助我们在这一领域构建并部署更多其它与之类似的重要工具。

原文链接:

https://code.fb.com/developer-tools/getafix-how-facebook-tools-learn-to-fix-bugs-automatically/

2018 年 11 月 07 日 17:013057

评论 8 条评论

发布
用户头像
结果就是加了一万行 if (xx == null)
2018 年 11 月 08 日 18:34
回复
用户头像
问题是能找到bug,通常就知道为啥会出现bug了,也就知道怎么改了
2018 年 11 月 08 日 17:34
回复
用户头像
修bug简答,找bug难。找bug有很多商业工具来帮忙,比如 coverity。
2018 年 11 月 08 日 14:29
回复
用户头像
搞起来
2018 年 11 月 08 日 14:09
回复
用户头像
听起来不错哦
2018 年 11 月 08 日 12:54
回复
没有更多了
发现更多内容

萌新不看会后悔的C++基本类型总结(二)

花狗Fdog

【金三银四】这才是打开Java面试的正确方式,吃透这份【Java面试手册】offer稳了

云流

Java 编程 面试

Elasticsearch Index Types and Mappings

escray

elastic 七日更 28天写作 死磕Elasticsearch 60天通过Elastic认证考试 3月日更

mock 请求分发

blueju

JavaScript React Mock umi umijs

恋物志(二):独居者的智能生活指南

脑极体

程序员必须知道的数据结构:HashMap 与 LinkedHashMap

老王说编程

Java 数据结构 hashmap

Oracle table()函数的合理运用,提高工作效率

xiezhr

oracle table() Oracle函数 3月日更

硬件设计必备,电子元器件高清矢量图

不脱发的程序猿

硬件产品 28天写作 硬件设计 电子元器件矢量图 3月日更

2021普通Java程序员如何在行业中脱颖而出?阿里进阶架构师不传之秘终于开源!

程序员小毕

Java 程序员 架构 面试 分布式

开源镜像仓库Harbor的镜像安全

运维研习社

Docker Harbor 漏洞扫描 镜像安全 私有仓库

Redis 与 I/O 多路复用模型

学个球

redis

世界互联网大会,VoneTracer“遇见”溯源未来

茜茜公主

七日更 3月日更

简单工厂模式、工厂模式、抽象工厂模式比较

良知犹存

设计模式

程序员必须知道的数据结构:线性表与链表

老王说编程

Java 链表 线性表

简易项目搭建 Models层封装

happlyfox

学习 28天写作 3月日更

饿了么刚给我确认了p7的职位,对自己的经历,做一个面试总结。

Java架构之路

Java 程序员 架构 面试 编程语言

会员中心小程序的主要模块

Kylin

微信小程序 会员中心 小程序运营 3月日更

正则表达式.01 - 元字符

insight

正则表达式 3月日更

LeetCode题解:714. 买卖股票的最佳时机含手续费,动态规划,JavaScript,详细注释

Lee Chen

算法 LeetCode 前端进阶训练营

力扣(LeetCode)刷题,简单题(第21期)

不脱发的程序猿

LeetCode 面试刷题 28天写作 算法面经 3月日更

总结近期腾讯+阿里+百度Java岗高频面试题,提问率高达98%,看到这篇文章基本offer稳了

Java架构之路

Java 程序员 架构 面试 编程语言

Wireshark数据包分析学习笔记Day3

穿过生命散发芬芳

Wireshark 数据包分析 3月日更

程序员必须知道的数据结构:队列与栈

老王说编程

数据结构 队列

金三银四程序员面试必备:2021最新 最全面Java复习路线!已收录GitHub

比伯

Java 编程 程序员 架构 面试

虚拟化存储

lenka

产品经理 3月日更

阿里面经最新分享:Java面试指南/成长笔记(金三银四程序员必备)

比伯

Java 编程 程序员 架构 面试

微信团队分享:微信直播聊天室单房间1500万在线的消息架构演进之路

JackJiang

微信 架构设计 即时通讯

用c++创作一个简单小游戏

张鹤羽粑粑

28天写作 3月日更

两会热词“区块链”,打开传统溯源的一扇大门!

源中瑞-龙先生

区块链 两会

话题讨论 | 又一家大厂进入汽车领域,"百车大战"即将来临?

程序员架构进阶

话题讨论 七日更 28天写作 话题王者 3月日更

连肝26天,熬夜拜读349页阿里面试通关手册,成功闯进字节跳动

互联网架构师小马

Java 编程 面试 求职 找工作

演讲经验交流会|ArchSummit 上海站

演讲经验交流会|ArchSummit 上海站

Facebook智能bug修复神器:让程序员少掉几根头发-InfoQ