摘要：程序自动修复（APR）是一种很有前景的自动修复软件错误的方法。大多数 APR 技术使用测试驱动修复过程。这使得它们能够立即被应用于真实的代码库，但是也带来了产生过拟合的错误修复的风险。一些技术通过使用契约（例如前置条件和后置条件）定位代码来解决过拟合问题，这些技术提供了有助于描述正确和错误计算状态的信息。不幸的是，主流编程语言通常不包含契约注释，这严重限制了此类基于契约的技术的适用性。本文介绍了一种新颖的 Java 程序 APR 技术——JAID。它能够构造详细的状态抽象（类似于基于契约的技术所采用的抽象）。这些抽象是从常规 Java 代码派生而来的，没有任何特殊注释。置于丰富的状态抽象之上的修复程序的生成和验证过程可以减轻过拟合的问题，并有助于扩展 APR 方法的适用性。在 DEFECTS4J 基准测试中，JAID 的原型实现产生了与程序员编写的程序同样正确的修复程序，改进了正确的修补程序的数量和种类，从而改善了 Java APR 技术的水平。

0. 引言

每一种基于有限测试集的通用软件分析技术都很容易发生过拟合的情况，自动程序修复技术（APR）也不例外。过度拟合很可能会削弱验证 GenProg 率先提出的先生成后验证范式的 APR 工具的性能。在这一范式中，每个试探性生成的候选修复方法（源代码补丁）都要进行测试，并且将能通过所有可行测试的修复方法分类为有效，并作为修复建议返回。由于验证是针对有限的（通常为少量）测试进行的，因此无法保证经过验证的方法对于完整、隐藏的方法都是正确的。实验已经反复确认，自动程序修复技术倾向于产生很大一部分有效但不正确的修复，这些修复只是碰巧通过了所有可用的测试，但显然不适合程序员。

用于 APR 的 AutoFix 技术通过使用由诸如前置条件和后置条件之类的断言构成的契约作为额外信息来减轻过拟合的问题，从而提高了修复程序生成和验证的精度。即使 AutoFix 所使用的契约远远不够详尽，更不用说完整的方法规范了，它们还是有助于增加可以生成的正确修复程序的比例。不幸的是，即使是最简单的契约，也几乎无法在最广泛使用的编程语言中获得。我们是否仍可以概括一些基于契约的程序修复的技术，以便在没有用户编写的契约的情况下有效地工作？

在本文中，我们描述了 JAID：一种用于 Java 程序自动程序修复的技术和工具，它基于详细的基于状态的动态程序分析，类似于基于契约的技术（例如 AutoFix）所采用的技术，但可用于常规 Java 代码（没有任何契约）。对状态的抽象驱动 JAID 的生成和验证过程，并帮助构建高质量的修复程序：在针对 DEFECTS4J 策展的集合中的错误的实验中，JAID 进行了修复，通过了 31 个错误的所有可用测试，并进行了正确的修复（等同于由程序员编写的代码）解决了 25 个错误。就正确修复的总数和精度而言，这些结果接近或优于其他用于 Java 程序自动程序修复的工具，并且包括针对 14 个先前无法实现的 DEFECTS4J 错误自动生成的正确修复。JAID 还是第一种 APR 技术，它无需测试和错误代码以外的其他输入就可以达到很高的精度。相反，其他最新的高精度 APR 技术分析了大量的项目存储库，以收集指导修复的其他信息。

本文的主要贡献是提高 JAID 的性能，其中包括建立丰富的对象状态抽象的技术。反过来，状态抽象依赖于函数的纯度分析，只有纯函数（没有副作用的函数）才能安全地表示状态。尽管使用程序员编写的契约技术（例如 AutoFix）可以轻松地依赖契约中用作谓词的功能，但是 JAID 必须无需注释从常规代码中提取相似信息。JAID 依赖于故障定位和排名启发法抑制生成和验证的候选修订程序的数量。这有助于识别可能与错误行为相关的程序状态。借助这些技术，JAID 可以基于对如何修改对象状态以避免失败的更“语义”分析生成正确的修复程序，而不仅仅是像其他大多数 APR 工具那样通过语法修改现有实现来解决该问题。

在本文中，我们使用名词“ defect”，“ bug”，“ fault”和“ error”作为同义词来表示程序源代码中的错误。名词“ fix”，“ patch”和“ repair”作为同义词，表示应纠正错误的源代码修改。为简单起见，JAID 表示 APR 技术和实现它的工具。JAID 和本文中描述的所有实验材料都可以从以下网址以开源形式获得：https://bitbucket.org/maxpei/jaid

1. JAID 的工作原理

JAID 遵循流行的“生成-验证”方法，也就是先生成大量候选的修补方法，然后使用可用的测试用例对其进行验证。 图 1 概述了整个过程。

JAID 的输入是一个 Java 程序，由一系列类和测试用例组成，这些用例执行该程序并暴露一些缺陷。 JAID 的一项主要功能是它如何根据程序表达式抽象和监视程序状态。 JAID 工作流程的所有阶段都依赖于 A 小节中所述的抽象。故障定位（B 小节）标识可能与维修中的故障有关的状态和位置（快照）。修补程序生成（C 小节和 D 小节）构建了代码片段，这些代码片段通过修改程序状态，控制流或其他简单的启发式方法来避免到达可疑的状态和位置。生成的修复程序将根据可用的测试进行验证（E 小节），通过验证的修复程序将呈现给用户，并根据其正确性的高低进行启发式排名（F 小节）。本节的其余部分描述 JAID 如何使用测试 T 修复类 FC 的泛型方法 fixMe，以至少在 T 中的一个测试失败的方式执行 fixMe 来测试 T。

A. 程序状态抽象

JAID 的程序分析和修订生成过程基于对 fixMe 方法行为的详细基于状态的抽象。 对于 fixMe 中的每个位置（在源代码中唯一标识一条语句），JAID 会在每次测试执行期间记录一组 M 表达式的值：1）数字和布尔类型的表达式的确切值； 2）引用类型表达式的对象标识符（或 null），以便它可以检测引用是别名还是 null。

B. 错误定位

故障定位的目的是识别可疑快照，这些快照指示可能与故障有关的位置和状态。 快照是三元组<l,b,?>其中 l 是 fixMe 方法中正在修复的位置，b 是布尔表达式，?是 b 在 l 处的值（True 或 False）。

这种方法与 AutoFix 类似，但在缺陷方法的控制流程图上明显地排除了关于 l 和故障位置之间的距离的信息。 AutoFix 将缺陷识别为违反契约的情况，这种情况往往发生在程序状态损坏的地方。相比之下，在 JAID 的设置中（使用 Java 中没有契约的测试），在评估测试方法中的断言语句时通常会发生缺陷，因此到方法中缺陷位置的距离无关紧要，并且几乎没有可靠的可疑迹象。

C. 修复程序生成：修复动作

一个高度可疑的快照 s = <l,b,?>表明当某个执行中的程序状态为 b 在 l 处等于?时，程序容易触发缺陷。相应地，JAID 创建了许多候选的修补程序，这些修补程序试图避开可疑状态，以避免缺陷发生。为此，JAID 列举了四种修复措施：

?

通过赋值直接修改状态

?

影响表达式中使用的状态

?

改变语句

?

重定向控制流

每个修复操作都是一个（可能是复合的）语句

D. 修复程序生成：候选修复

每个由上一节中所述的 JAID 构建的修复动作是一条语句，该语句修改了位置 l 处的程序行为，从而避免了某些可疑快照 s = <l,b,?>相关的状态。 在大多数情况下，不应将修复动作无条件地注入正在修复的程序中，而应仅在计算过程中实际上达到状态 b 时才将修复动作注入。条件执行将使程序行为在多数情况下保持不变，当且仅当在即将发生错误时执行。

另一方面，不同的修复动作能带来语义上等效的修复。 JAID 可以根据简单的语法规则执行轻量级冗余消除，例如 x == y 等于!(x != y)。在未来的工作中，我们计划引入更加积极的冗余消除措施。

E. 修复程序验证

即使 JAID 根据通过的和失败的测试期间对程序状态的语义分析来构建候选的修复程序，候选的修复程序也无法保证满足测试要求。为了确定合适的候选，紧跟修复程序生成过程之后的验证过程将运行所有测试 T，也就是每个生成的候选修复程序都要执行包含错误的方法 fixMe。 通过所有测试 T 的候选修复程序被分类为有效（也称为“合适的测试套件”）并保留； 其他未通过某些测试的候选者将被丢弃，因为它们无法修复故障。

F. 修复程序排序

像大多数的 APR 技术一样，JAID 的过程基于启发式方法，并由有限的测试集合驱动，最终达到最好的效果。一个有效的修复程序仍然可能是不正确的，仅仅是因为测试的不完整，才通过所有可用的测试。为了 解决这一问题， JAID 使用相同的用作故障定位基础的启发式方法。每个修复程序都包含一个修复操作，该操作是从快照 s 派生的； s 的可疑度越高，该修复程序的排名就越高；从同一快照生成的修复程序按生成顺序进行排序，这意味着“语义”修复（修改状态或表达式）出现在“语法”修复（变异语句或修改控制流）之前。相同类型的修复程序从简单的语法开始被枚举。当排序启发式方法起作用时，用户仅检查少数排名靠前的修复程序以评估其正确性，判断是否可以将其部署到代码库中。

2. 实验评估

我们评估了 JAID 在 DEFECTS4J 上的有效性，DEFECTS4J 包含大量的缺陷和来自现实世界 Java 项目的程序员编写的修补程序。这种选择还使我们能够定量地将 JAID 评估的结果与大多数 Java 程序 APR 的最新工具进行比较。

有效性。JAID 能够对 Tab 中列出的 DEFECTS4J 的 31 个错误产生有效的修复。更重要的是，它为其中的 25 个错误提供了与程序员编写的错误相当的正确修正。 这表明 JAID 适用于实际代码，并且在成功运行时通常会产生高质量的修复程序。

正如我们在下面更详细地讨论的那样，正确修复的错误的数量与 Java APR 技术的最新水平相当或更高。JAID 生成的修补程序的大小往往较小：每个有效的修补程序平均进行 1.7 行代码更改。这是其修复程序生成过程的结果，该过程基于基于状态的信息，以简单的修复操作为目标，然后通过使用条件模式将其注入代码中来提高其精度。

JAID 甚至可以正确修复仅包含一个失败测试（而没有通过测试）的 4 个错误，在两种情况下，将正确的修复排名第一。 这些结果展示了 JAID 如何成功地缓解过大的有害问题。

性能。JAID 每个错误的运行时间中位数为 119.5 分钟（平均运行时间为 355.1 分钟）。毫无疑问，JAID 比基于约束解决方案和其他符号技术的工具要慢得多。例如，在我们认为是可比较的硬件上，Nopol 平均每个错误花费大约 22 分钟。但是，它们与主要基于动态分析的其他 APR 技术保持一致，例如 jGenProg，每个错误大约需要一个小时。

如果研究一下 JAID 的每个阶段需要花费多少时间，我们发现验证是最耗时的：故障定位花费每个 bug 中值时间的 2.77％，修复程序生成花费 0.5％，修复程序验证花费 92.8％。 。验证时间往往与可用测试的数量和修补程序候选的数量成正比，而后者又与实际分析的快照数量成正比。本节概述的方法仍然有助于节省大量编译时间；作为未来的工作，我们计划通过在同一 JVM 上运行多个并发实例来进一步提高验证性能。

设计。用于修改状态或表达式的动作：基于 JAID 丰富的基于状态的抽象构建的“语义”动作；用于改变陈述的动作-纠正常见错误并在 APR 系统中常用的“句法”动作；用于修改控制流的动作，即“终止”动作仍然会对程序行为产生重大影响。JAID 在正确的解决方案中使用了三种频率相似的动作，这表明它们在很大程度上是互补的，并且都有助于提高 JAID 的有效性。这表明有条件的应用程序和无条件的应用程序都需要针对大量错误。

对比。Java 的其他六个 APR 工具。就用正确的修补程序解决的错误数量而言，JAID 的性能优于所有其他工具。HDA 和 ACS 都严重依赖于从其他来源挖掘其他信息：HDA 挖掘来自 800 个受欢迎的 GitHub 项目的 3000 个错误修复的频率信息，而 ACS 在 GitHub 的所有开源项目中搜索。HDA 的实现还需要将故障定位信息作为输入的一部分。因此，这两种工具都使用了比错误程序及其附带的单元测试更丰富的输入，这表明 JAID 的性能具有很高的竞争力。JAID 在精度（具有正确修复的有效修复的错误百分比）和召回率（DEFECTS4J 中具有正确修复的所有错误的百分比）方面也非常出色。由于不同的方法和不同的实验评估对接受多个有效修复程序的错误的处理方式不同，因此我们测量了三种精度和召回率：1）相对于任何有效修复程序正确修复的错误数量，无论正确的修复等级； 2）相对于由工具输出中排名前 10 位的修复程序正确修复的错误数量； 3）相对于由工具输出中排名第一的正确修复的错误数量。 如果我们不考虑排序，JAID 达到了最高的精确度和召回率。而在其他两种情况下，达到了次优的查全率和次优的查全率。唯一胜过 JAID 的工具都依赖于其他输入信息来提高精度和召回率。

致谢

本文由南京大学软件学院 2020 级研究生钱美缘翻译。