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

这篇是导师给的论文，因为有随手删文件的习惯，所以把这篇文章发布到这留作备份，原文地址为： 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).

document.querySelectorAll('.github-emoji') .forEach(el => { if (!el.dataset.src) { return; } const img = document.createElement('img'); img.style = 'display:none !important;'; img.src = el.dataset.src; img.addEventListener('error', () => { img.remove(); el.style.color = 'inherit'; el.style.backgroundImage = 'none'; el.style.background = 'none'; }); img.addEventListener('load', () => { img.remove(); }); document.body.appendChild(img); });