MIT“创世纪”机器学习新系统，自动生成补丁修复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

摘编自：新智元