策划编辑 | Natalie
作者 | JOHANNES BADER 等
译者 | 核子可乐
编辑 | Vincent

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

更多干货内容请关注微信公众号“AI 前线”，（ID：ai-front）

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

这个工具叫作 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 重新访问现有代码时所发现的代码质量问题。

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

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

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

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

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

Tree Differencer 标识树级别的更改

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

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

新的修复模式挖掘方法

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

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

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

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

基于反合一方法的模式挖掘并非什么新鲜事物，但要想以尽可能少的修复操作解决新 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();