自动化程序修复（APR）在减少错误修正的工作量方面具有巨大潜力，并且近年来提出了许多方法。 APR 通常被视为一种搜索问题，它的搜索空间包含所有可能的补丁，它的目标是在该空间中识别正确的补丁。许多技术采用数据驱动的方法，分析数据源（例如现有补丁和相似的源代码）以帮助识别正确的补丁。但是，尽管现有的补丁和相似的代码提供了补充信息，现有技术也仅能分析单个数据来源，无法轻松地扩展以同时对两者进行分析。在本文中，我们提出了一种新颖的利用现有的补丁和相似的代码的自动程序修复方法。我们的方法从现有补丁中挖掘出抽象的搜索空间，并通过与相似的代码片段进行区分来获得具体的搜索空间。然后，我们在两个搜索空间的交集内搜索。我们已将我们的方法实现为名为 SimFix 的工具，并在 Defects4J 基准测试中对其进行了评估。我们的工具成功修复了 34 个错误。据我们所知，这是 Defects4J 基准上由单一技术修复的最多错误。此外，据我们所知，我们的方法修复的 13 个错误从未被先前的方法修复。

关键词：自动程序修复，代码差异，代码适配

1、引言

自动化程序修复（APR）旨在通过自动生成满足规范的补丁来减少错误修复的工作量，这是迈向软件自动化的一步。近年来，已经提出了许多自动程序修复技术。典型的 APR 方法将有错误的程序和一组测试用例作为输入（程序至少使其中一个测试用例失败），并生成修复程序以修复故障（已修补的程序能通过所有测试）。

APR 通常被视为一种搜索程序，其搜索空间由所有可能的补丁组成，搜索目标是从空间中识别出正确的补丁。这个问题非常具有挑战性，因为搜索空间通常很大，并且包含很多合理但错误的补丁。测试用例无法区分正确的补丁和合理但不正确的补丁。APR 方法不仅需要在巨大的空间中找到正确的补丁，而且还需要避免看似合理但不正确的补丁。

为了解决此问题，许多 APR 技术采用数据驱动的方法来估计补丁的可能性，将搜索限制在更优先的搜索空间，以便首先尝试更有可能正确的补丁。常用的数据源之一是现有的补丁。分析现有补丁可以使我们得到错误修复的分布，因此我们可以选择进行修改可能性最大的补丁。典型的方法包括基于修复模式限制搜索空间的 PAR，Genesis，QAFix 和 SOFix，以及根据学习模型对补丁进行排序的 Prophet 和 HDRepair。另一个常用的数据源是源代码。分析源代码有助于我们了解要修复的程序的内部结构（包括公共代码和特定于上下文的代码），因此我们可以选择适合当前代码上下文的补丁。典型的方法包括 GenProg 及其变体，它们结合来自同一项目中类似代码片段的语句。此外还有 SearchRepai，在代码库和 ACS 中执行语义搜索，根据 GitHub 的统计结果对补丁成分进行排名。

为了实现跨项目挖掘，我们在 AST 节点类型上定义了一个抽象搜索空间，其中抽象搜索空间中的每个抽象补丁都是对修改 AST 节点类型的具体补丁的抽象。 然后抽象空间定义将项目特定的细节抽象出来，因此很可能会从一小部分补丁中概括出来。

为了从源代码中获取搜索空间，我们遵循了现有的方法，复用相似代码中的修复成分：首先定位到与错误代码片段相似的代码片段，然后与相似的代码片段中的这些成分合并以形成候选补丁。但是，很难为修补成分找到合适的粒度。如果我们使用粗粒度（例如语句），则许多错误无法被修复。如果我们使用细粒度，例如 AST 节点，则它们的组合可能会形成无法有效搜索的大空间。为了克服这个问题，我们提出了一种新颖的基于差异的方法来减少细粒度的搜索空间。更具体地说，我们首先定义一组功能，以计算错误代码段与其他代码段之间的句法距离。对于具有较短距离的相似代码段（称为给予者），我们将两个代码段进行比较，并获得从错误代码段到施主代码段的修改。最后，通过修改的组合形成实际的搜索空间。由于不同代码段中的变量名称通常是不同的，因此我们还建立了变量名称之间的映射，并在提取和应用修改时将其考虑在内。

我们已将我们的方法实现为一种名为 SimFix 的自动程序修复工具，并在 Defects4J 基准测试中对其进行了评估。我们的工具成功修复了 34 个缺陷。据我们所知，这是 Defects4J 基准上由单一技术修复的最多错误。此外，据我们所知，用我们的方法修复的 13 个缺陷从未被相关技术正确修复。

总而言之，本文做出了以下贡献：（1）一种基于两个搜索空间的交集的自动程序修复方法：现有补丁的搜索空间和相似代码的搜索空间。（2）一种基于现有补丁的 AST 类型的抽象空间定义获取搜索空间的方法。（3）一种基于代码差异从相似代码获取搜索空间的方法。（4）在 Defects4J 上进行的实验表明了我们方法的有效性。

2、方法

2.1 搜索空间：

在 AST 上的具体的修改操作包括：

（1）Insert(n,t’,i)：在节点 n 下索引 i 的位置插入抽象语法树 t’

（2）Replace(n,t’)：用抽象语法树 t’替换以 n 为根的子树

删除代码通常会产生错误的补丁程序，因此我们不考虑在搜索空间中进行删除操作。基于此定义，由差异算法产生的修改自然会形成搜索空间。但是，此定义取决于 AST，不适合分析不同 AST 上的补丁。为了支持补丁分析，我们定义了抽象修改和抽象搜索空间：

（1） INSERT(T): 插入一个根节点类型为 T 的 AST

（2） REPLACE(T1,T2): 使用另一个根节点类型为 T2 的 AST 替换根节点类型为 T1 的。

显而易见，每个具体修改都对应于一个抽象修改，并且我们使用一个函数来执行此转换。最后，在从补丁获得抽象空间并从类似代码获得具体空间之后，我们就可以获取到它们的交集。

2.2 修改提取

首先，在分析补丁时，我们需要获取每个补丁执行的修改。其次，在分析相似代码时，我们需要从错误代码段到供体代码段进行修改。我们对两个地方使用相同的差异算法。该算法将两个 AST a 和 b 作为输入，并产生一组从 a 到 b 的具体修改。我们的算法与 GumTree [10]共享相同的骨架，但专门针对我们的搜索空间而定制。我们首先在两个 AST 之间匹配节点，然后在匹配过程中提取修改。确定两个节点是匹配的条件为：它们具有相同的节点类型；它们的所有祖先都匹配；可以通过从目标 AST 到源 AST 插入一些节点来满足前两个条件。

2.3 挖掘阶段

挖掘阶段的输入是补丁集，其中每个补丁都包括一对未补丁版本和补丁版本。 对于每个补丁，我们使用差异算法来获取具体修改，然后使用函数（如 3.1 节中所述）将其转换为抽象修改。 然后，我们计算每种抽象修改的出现频率。 最后，我们选择出现频率大于阈值 k 的抽象修饰来形成搜索空间 S1。 在我们的实验中，我们根据帕累托原理将 k 设置为一个值，其中搜索空间可以覆盖 80％的补丁。

2.4 修补阶段

故障定位：理论上，任何产生可疑语句的有序列表的故障定位方法都可以与我们的方法一起使用。在 Java 上进行的实验中，我们选择了 Person 等人实现的 Ochiai 算法。此外，我们使用纯净的测试预处理测试用例，以提高故障定位的准确性。

代码段提供者识别：给定一个潜在的错误位置，我们将其扩展为错误的代码段，然后找到一组相似的代码段作为供体进行比较和修改。 我们首先定义代码段是指在给定源文件中的两个行号 x 和 y，[x，y]之间的代码段是包含在 x 和 y 行之间的最长语句序列。 这里的“语句”指的是用 Java 语法定义的 Statement 节点。为了识别用于提供的代码段，我们需要测量两个代码段之间的相似性。在这里，我们定义了三个相似度度量，最终相似度是这三个相似度的总和。这三个相似度度量分别为：结构相似度、变量名相似度和方法名相似度。根据代码段的定义，我们可以识别出错误的代码段和用于修复的代码段。给定潜在的故障行，我们将其扩展为大小为 N 的代码段。接下来，我们在源文件上滑动一个大小为 N 的窗口，提取该窗口中的代码段作为提供的代码，然后删除重复的代码段。这样，我们可以在 N 行代码中提取所有可能的代码段。 然后我们计算故障片段与每个供体片段之间的相似度，然后选择前 100 个供体片段。在后续实验中，我们根据经验将 N 设置为 10。

变量映射：在此阶段，我们将故障代码片段和代码片段提供者中的变量进行匹配，并为代码自适应构建变量映射表。我们利用三种相似性信息，即用法相似性，类型相似性和名称相似性。最终相似度得分是上述三个得分的加权总和。计算完每对变量之间的相似度后，我们会贪婪地选择相似度最高的对，直到没有为止。然后，我们将提供的代码段中的所有变量替换为对应的映射后的变量，以获得相应的修复代码段。

修改提取和取交集：给定提供的代码段，我们将它们与故障代码段按相似性降序进行逐一比较，并使用第 2.2 节中介绍的代码差异算法提取具体修改。 然后，我们确定这组修改与通过分析现有补丁提取的修改之间的交集。之后，我们获得了一组用于补丁生成的具体修改方案。

补丁生成和验证。 在上一阶段中获得的一组修改定义了缩小的搜索空间。 此阶段的目标是在通过所有测试的空间中确定一个补丁，所以我们在空间中对补丁进行排序并逐一验证它们。我们按照以下规则对补丁进行多级排序，较早的规则表示级别更高：（1）包含一致修改的补丁排名更高；（2）修改较少的补丁排名较高；（3）具有更多替换操作的补丁的排名高于具有更多插入操作的补丁。获取候选补丁的有序列表后，我们将通过测试逐个验证补丁，然后返回能通过所有测试的第一个补丁。

3、评估

RQ1：频繁的抽象修改是什么？

我们在补丁集上进行挖掘阶段以获得抽象搜索空间，然后检查结果。表 3 显示了定义抽象搜索空间的频繁抽象修改。从表中可以看出，最常见的 3 种修改是插入 if 语句，替换方法调用和插入方法调用。该结果与现有研究的结果一致。例如，Martinez 和 Monperrus 确定的前 5 个最频繁的插入/更新也包括在我们的空间中，例如插入方法调用和 if 语句。这些修改形成了一个小的抽象空间。

RQ2：SimFix 在 Defects4J 上的有效性

评估结果显示在表 4 中，其中每个单元格表示每个项目上通过相应的修复技术修复的错误的数量。有些论文仅报告由第一个补丁修复的错误，而有些论文则报告由任何补丁修复的错误，而与排名无关。括号外的数字表示第一个补丁修复的错误，而括号内的数字表示任何补丁修复的错误。 缺少的数字用“-”标记或直接省略。 从表中我们可以看到，SimFix 使用第一个补丁成功修复了 Defects4J 基准测试中的 34 个错误，与所有其他比较方法相比，可以获得最多数量的正确补丁。 此外，对于四个项目，SimFix 会通过第一个可行的补丁程序修复最多数量的错误。

RQ3：基于现有补丁缩小搜索空间的效果如何

在我们的方法中，我们首先从相似的代码中获得一个具体的空间，然后通过使用现有补丁中的抽象空间来减少它。为了了解此步骤的有效性，我们实现了 SimFix 的一种变体，称为 SimFix-A。它使用从相似代码差异中提取的所有候选修改来修复程序，即使它们不在现有补丁的抽象空间中。实验结果如表 5 所示。从表中可以看到，如果不从现有补丁中提取抽象空间，就可以减少 12 个错误。两个主要因素促成了这一减少。 （1）该空间包含更多可能的补丁，这些补丁可能在正确的补丁之前生成。（2）如果空间较大，则需要花费更多时间来生成和验证补丁，并且可能无法在规定的时间内生成正确的补丁。

RQ4：删除操作如何影响程序自动修复？

如第 3.1 节所述，我们从空间中排除了删除。 在这个研究问题中，我们探索了该设计决策的效果。我们实现了 SimFix 的另一个变体，称为 SimFix-D，其中，我们在搜索空间中包含了删除操作，并修改了差异算法，从而生成了删除操作。性能下降的原因与 SimFix-A 相似：扩大的搜索空间包含更多的补丁程序和更合理（但不正确）的补丁程序。

RQ5：使用细粒度的效果如何？

与大多数在语句粒度上重用相似代码的现有方法一样，我们的方法利用细粒度的差异算法在 AST 子树粒度上重用相似代码。为了研究这种细粒度的重要性，我们手动分析了我们的方法产生的补丁，以查看如果仅允许像现有方法一样重用语句级别代码，仍然可以修复多少个错误。 检查了所有补丁之后，我们发现将少修复 17 个错误。 结果表明，细粒度的代码区分和重用大大提高了我们方法的有效性。

4、结论

在本文中，我们提出了一种新颖的自动程序修复方法，该方法基于精确获取的代码差异并利用现有补丁和类似代码。 更具体地说，通过分析现有补丁，我们获得了一组常见的抽象修改，从而形成了程序修复的抽象空间。 通过分析同一程序中的相似代码段，我们提取了具体的修改，从而形成了具体的空间。 最后，我们使用两个空间之间的交集并执行细粒度的代码自适应以生成补丁。 我们已经实现了该方法的原型，即 SimFix，并在 Defects4J 上对其进行了评估。 SimFix 总共成功修复了 34 个错误，而现有技术从未修复过 13 个错误。

此论文由南京大学软件学院 2020 级研究生钱美缘转述。