【译】用于补丁生成自动推理代码转换

这篇是导师给的论文，因为有随手删文件的习惯，所以把这篇文章发布到掘金社区留作备份，原文地址为：Automatic Inference of Code Transforms for Patch Generation.，本人目前翻译功底较差，如果有小伙伴觉得翻译的有问题，希望在评论区指出，大家共同进步 😊

论文：Fan Long, Peter Amidon, and Martin Rinard. 2017. Automatic Inference of Code Transforms for Patch Generation. In Proceedings of 2017 11th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, Paderborn,Germany, September 4-8, 2017 (ESEC/FSE’17), 13 pages. https://doi.org/10.1145/3106237.3106253

摘要

我们提出了一个新的系统 Genesis，该系统能够处理人工的补丁来自动化推理代码转换，用于自动化补丁生成。我们呈现的结果描述了 Genesis 推理算法和完整的 Genesis 补丁生成系统在来自 372 个真实的 Java 项目的补丁和缺陷上工作的有效性。据我们所知，Genesis 是第一个用于自动推理补丁生成转换或从先前成功的补丁空间中搜索候选补丁的系统。

关键词

补丁生成，代码转换，搜索空间推理

1. 介绍

自动补丁生成系统有望大大减少诊断、调试和修复软件缺陷所需的人工工作。标准的生成和验证方法是从一组测试用例开始的，该测试集中至少有一个测试用例揭示了缺陷。它部署了一组转换以生成候选补丁的搜索空间，然后在测试用例上运行生成的补丁程序，以此找到能够为所有测试用例生成正确输出的合理补丁。之前所有的生成和验证系统都通过一组人工转换来修补这些转换范围内的程序错误。

Genesis

我们介绍了 Genesis，一个新颖的系统，其推理代码转换用于自动化补丁生成系统。给定一组从可修正历史库中提取的人工生成的正确补丁，Genesis 将补丁的子集泛化，并以此推断出可以生成高效搜索空间候选补丁的转换。因此，Genesis 可以结合众多开发人员的补丁并总结出经验并以此生成各种高效的补丁生成策略。在过去没见过的程序中，Genesis 可以很成功地将推断转换应用修复 bug 上。据我们所知，Genesis 是第一个自动推理补丁生成转换或根据先前成功的补丁搜索候选补丁空间的系统。

转换：每个 Genesis 转换都有两个模版抽象语法树（ASTs）。一个模板 AST 匹配原始程序中的代码。另一个模板 AST 指定生成补丁的替换代码。模板 AST 包含模板变量，这些变量与原始代码或补丁代码中的子树或子森林匹配。模板变量使得转换能够抽象掉特定于应用的细节，以捕捉由从不同应用中提取的多个补丁所实现的公共模式。

生成器：许多有用的补丁并不是简单地重新排列现有的代码和逻辑，它们还引入了新的代码和逻辑。因此，Genesis 转换实现了部分模式匹配（partial pattern matching），其中替换的模板 AST 包含原始代码中不匹配的自由模板变量。每个自由模板变量都与一个生成器（generator）相关联，这个生成器可以系统地为自由变量生成新的候选代码组件。这种技术使 Genesis 能够在候选补丁中合成新的代码和逻辑，使其可以为以前不可见的应用程序生成正确的补丁，这点对于 Genesis 来说至关重要。

使用 ILP 搜索空间推断：在设计补丁搜索空间时，关键的地方是在覆盖率和可跟踪性之间进行一个固有的权衡。一方面，搜索空间需要足够大，以包含针对目标缺陷类的正确补丁(覆盖率)；另一方面，搜索空间需要足够小，这样补丁生成系统才能有效地探索空间，找到正确的补丁(可跟踪性)。

Genesis 通过构造和解决整数线性程序(ILP)来解决这个问题，该程序的解决方案最大化了被推断的搜索空间所覆盖的训练补丁的数量，同时又在一定范围内限定了搜索空间可以生成的候选补丁的数量。

2.转换推理

接下来，我们将通过一个例子来概述 Genesis 转换推理算法。Genesis 使用一组训练成功的人工补丁来推断一组补丁生成转换。在我们的示例中，训练集由 963 个人工补丁组成，分别从 356 个 GitHub 仓库中筛选出来。

补丁采样和泛化：Genesis 推理算法使用训练集的样本子集进行训练。对于每个子集，它应用一个泛化算法（generalization algorithm）来推断可以用于生成候选补丁的转换。图一展示了该例中的一个补丁子集：第一个补丁将一个语句 mapperTypeElement==null 分解成一个 if 条件语句。第二个补丁将一个分句 subject!=null 组合成一个返回一个值的语句，第三个补丁将分句 Material.getMaterials(getTypeId())!=null 合并成一个 if 条件语句，这些补丁来自三个不同的应用程序，分别是 mapstruct、modelmappe 和 Bukki。在图 1 中，Genesis 将这些补丁泛化以此来推断转化 P1，在应用时，P1 可以为其他应用程序生成所有采样的三个补丁以及其他补丁。

模版结构：每种转换都有一个模版。在我们的例子中，模版是 V0 ==> ((V3)op2(null))op1(V0)（图 1 以图的形式显示了这个模板）。转换有一个初始模板 AST T0，它匹配未修补程序中的布尔表达式 V0。V0 必须出现在函数体中(如果所有的训练补丁都修改了 if 条件，那么 T0 就会反映出更具体的上下文)。该转换还有一个替换模板 AST T1，它将匹配的布尔表达式 V0 替换为表单((V3)op2(null))op1(V0)的一个补丁。这里 V3、op2 和 op1 是不匹配的模板变量。每个这样的变量都与生成器关联，生成器枚举变量的候选代码组件。

生成器约束：生成器约束控制生成器将枚举的组件。op2 和 op1 的生成器约束 (op2 ∈ {==,! =} and op1 ∈ {&&,||}) 只指定要枚举的操作符集。V3 的生成器约束控制为 V3 枚举的 AST 子树。V3 ∈ Expr 表明 V3 是一个表达式，nodes(V3) ⊆ Call∪Var 表明 V3 只能包含方法调用或变量引用。|V3| ≤ 2 表明 V3 最多可以包含 2 个 AST 节点。

vars(V3) ⊆ M 表明 V3 中出现的任何变量也必须出现在匹配的模板 AST V0 中(这里 M 表示原始匹配代码中的节点集)。|vars(V3)| ≤ 1 表示 V3 中最多只能出现一个变量。 calls(V3) ⊆ M 和 |calls(V3)| ≤ 2 类似，表明约束 V3 中可能出现的方法调用。

正如这些生成器约束所说明的，Genesis 补丁泛化算法推导出生成所有采样训练补丁的最小通用 Genesis 变换。这种策略对于获得在补丁搜索空间中生成可处理数量的补丁的精确目标转换至关重要。

候选转换：Genesis 重复采样训练补丁以获得候选转换(Genesis 将从中选择它用于生成补丁的所选转换)。在我们的例子中，候选转换包括前面的转换P1以及一个转换(P2)，它添加了一个条件(三元)运算符来保护表达式的计算不受 NP 缺陷的影响；一个转换(P3)添加一个 if-return 或 if-continue 语句来跳过触发 NP 缺陷的计算；转换P4通过用一个新的表达式来随便更换一个表达式。新表达式可能包含二进制运算符、条件运算符，以及来自封闭函数的至多六个变量和六个方法调用。

但是并非所有这些变换都同样有用。例如，P4是一个过度通用的转换，它可以生成一个巨大的补丁搜索空间，以至于 Genesis 无法有效搜索。另一方面，P1、P2和P3更有针对性——因为它们是从概念上类似的训练补丁中推断出来的，因此每个都生成一个小得多的搜索空间，但其中包含正确的补丁。P1、P2和P3有效地互补——它们生成的搜索空间具有相对较少的公共补丁。

搜索空间推理：为了得到一组有效的转换，Genesis 必须抛弃例如P4的过度通用的转换，而选择互补的、有效的目标转换，如P1、P2和P3。Genesis 利用从训练补丁中选择的一组验证补丁来驱动转换选择。Genesis 首先计算每个候选转换生成的验证补丁的数量，以及在应用于每个验证补丁的补丁前代码时，每个候选转换生成的搜索空间的大小。

图 2 中的矩阵给出了四个候选转换P1、P2、P3和P4的编号，以及三个验证补丁VP1、VP2和VP3。矩阵中的每个数字都是转换应用于验证补丁的补丁前代码时生成的候选补丁的数量。绿色粗体数字表示，当将转换应用于补丁的预补丁代码时，可以生成验证补丁。这些数字突出了候选补丁提供的覆盖率与可跟踪性之间的权衡。对于易于处理的搜索空间，P1、P2和P3都生成一个验证补丁。相反，P4可以生成两个验证补丁，但代价是难以处理的大搜索空间。

使用矩阵中的信息，Genesis 制定了一个整数线性程序（ILP），它可以最大化所选变换可以生成的验证补丁的数量，但要受到所有选定变换的生成候选补丁总数的约束。覆盖验证案例小于 5×10^4。在我们的示例中，ILP 选择P1、P2和P3作为选定的变换并排除P4。

补丁生成：对于 DataflowJavaSDK 修订版 c06125 中的 NP 缺陷(如图 1 底部所示)，Genesis 首先使用了一种缺陷定位技术来生成一个要修改语句的潜在排序列表。得到的排序列表包括图 1 左下角所示的 if 条件。Genesis 然后将所有选择的转换(包括 P1)应用到 if 条件以生成候选补丁。

图 1 显示了 Genesis 如何将 P1 应用于 if 条件。在这里，补丁将 V3 实例化为变量 union，op2 实例化为==，op3 为||，以此来分解语句 unions == null 使其变成一个最原始的 if 语句。当 union 为 null 时，补丁会导致封闭函数 innerGetOnly()返回预定义的默认值(而不是错误地抛出空指针异常)。这个补丁验证是正确的(为 DataflowJavaSDK JUnit 测试套件中的所有输入生成正确的输出)，并且和为该缺陷开发的人工补丁一致。

3. 实现

我们在 Java 程序中使用 Genesis，在此实验中，我们利用 spoon 库解析 Java 程序，目前我们支持任何使用 maven 项目管理系统和 JUnit 测试框架的 Java 应用程序。

给定一个程序 p，一个测试集，至少一个在 p 中暴露出的缺陷和一个推断搜索空间 P，Genesis 首先会使用一个缺陷定位算法在 p 中标识出与缺陷相关的可疑位置的排序列表(如 AST 片段)。对于每个可疑的 AST 片段 S，Genesis 在 P 中应用每个转换来生成候选补丁。它根据测试用例验证每个候选补丁，如果通过了所有测试用例，则将其附加到生成的补丁列表中。Genesis 旨在使用任意缺陷定位算法。我们目前的实现基于可疑的位置，其由触发 Java 异常的测试集堆栈跟踪得知。Genesis 将其推断的转换应用于排名缺陷定位列表中的每一个可疑语句。对于每个变换，Genesis 计算成本分数，该分数是转换需要生成以覆盖验证案例的候选补丁的平均数量。对于每一个可疑的语句，Genesis 都会优先考虑由成本分数较低的转换生成的候选补丁。

4.实验结果

我们使用 Genesis 来推理补丁的搜索空间，并为 Java 程序中的三类缺陷生成补丁:空指针(null pointer, NP)、超界(out of bounds, OOB)和类强制转换(class cast, CC)。Genesis 使用一个包含 483 个 NP 补丁、199 个 OOB 补丁和 287 个 CC 补丁的训练集，这些补丁来自 356 个开源应用，并推断出一个由 108 个转换生成的搜索空间。

我们的基准缺陷包括来自 41 个开源应用程序的 20 个 NP、13 个 OOB 和 16 个 CC 缺陷。所有的基准测试应用程序都是从 GitHub 收集的，并且多达 235K 行代码。通过 108 个推断的转换，Genesis 为 49 个缺陷(11 个 NP、6 个 OOB 和 4 个 CC 缺陷)中的 21 个生成了正确的补丁。

PAR 是过去的一个使用手工定义补丁模版的 Java 补丁生成系统。我们将 Genesis 和其进行比较。对于相同的基准集，PAR 模板为 10 个缺陷(具体地说，7 个 NP 和 4 个 OOB 缺陷)生成正确的补丁。

我们将这些结果归因于 Genesis 自动化推理算法能够在一定规模下导航导航补丁的变换权衡。Genesis 使用成百上千个候选转换来获得由数十到 100 多个选择转换生成的高效搜索空间——比以前生成和验证系统的转换要多得多。通过部署这么多转换，Genesis 能够捕获范围广泛的补丁模式，并通过选择的转换来确保最终的补丁搜索空间的可追踪性和覆盖率。

5.总结

以前的生成和验证补丁生成系统使用由开发人员定义的固定转换集。通过从成功的人类补丁中自动推断转换，Genesis 使得利用全世界开发人员的专业知识和补丁生成策略来自动修补新应用程序中的漏洞成为可能。

6.本文的主要贡献

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

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

7.参考文献

[1] Fan Long and Martin C. Rinard. 2016. An analysis of the search spaces for generate and validate patch generation systems. In Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, Austin, TX, USA, May 14-22, 2016. 702–713.

[2] Dataflow Java SDK. https://github.com/GoogleCloudPlatform/DataflowJavaSDK.(2017).

[3] JUnit. http://junit.org/. (2017).