修复系统漏洞的软件（基于演变的多补丁程序修复技术）

修复系统漏洞的软件（基于演变的多补丁程序修复技术）挑战 2：测试用例生成的频谱可能不会暴露甚至覆盖所有同类实例，缺少一些同类最多只能产生部分修复。挑战 1：演化同类不只是代码克隆。 因此，需要进一步的分析以揭示所需的同类关系。在这项工作中，我们提出了针对特定但重要的一类多块修复问题的 APR 技术。我们的解决方案在很大程度上得益于两个研究机构的见解。首先是关于检测和使用代码克隆的研究。这项研究表明，代码克隆在程序中非常丰富。通常，主题系统的 5-25％和多达 50％可以由克隆的代码组成。此外，通过克隆代码复制错误是一种普遍现象。多达 10％的克隆代码中包含错误，其中在代码克隆中发现的错误的 55％是复制的错误[9]。第二项工作是 APR 技术本身，其中绝大部分技术都直接或间接地利用了“整形外科假说” –可以从现有代码中获得修复成分。这可以采取从现有补丁集中派生的程序转换模式（定义修复空间）的形式。或者，可以从现有代码中提取诸如程序元素，表

摘要：尽管在过去的十年中，自动程序修复（APR）技术取得了显着进步，但实际应用仍然是个遥不可及的目标。当前的 APR 技术不能产生编辑多个位置的补丁，即多块补丁。在这项工作中，我们提出了一种新颖的 APR 技术，该技术总结归纳了单块修复技术，以包括一类重要的多块缺陷。多块缺陷是指即可能需要在多个位置应用大致相似的补丁的缺陷。我们将这些维修位置集称为“演化同类”——相似外观的代码，例如在相似的上下文中预计将发生相似的变化。我们提出的方法的核心是针对给定的 bug 进行准确识别出一组演化同类的分析。这种分析利用了三种不同的信息源，即测试套件，新颖的代码相似分析和项目的修订历史。然后以相似的方式同时修复发现的同类。我们在名为 Hercules 的工具中实现了这一技术，并演示了它能够正确修复 Defects4J 数据集中的 49 个错误，这是迄今为止任何 APR 技术中最高的。其中包括 15 个多块的 bug，以及总共 13 个到目前为止尚无其他技术修复的 bug。

关键词：自动程序修复，机器学习，OOP，多块补丁，代码相似度

1、引言

在过去的十年中，人们对自动程序修复（APR）技术进行了大量的研究。这些技术有望帮助将繁琐的调试和修补错误的过程自动化。然而，就 APR 技术的实际应用而言，这一希望尚未实现。可能的原因之一是目前最先进的 APR 技术可以正确修复的错误类别相对有限。特别是，大多数 APR 技术旨在针对单个大块的 bug，即带有补丁的 bug 限制在单个位置的单个连续代码块中。但是，绝大多数错误修复程序跨越了多个块。例如，Defects4J 数据集中有 64％的错误和 Bugs.jar 数据集中有 76％的错误需要多块补丁。先前的几项工作已经意识到进行多块修复的挑战。为了探索通用的多块补丁程序，对搜索空间的任何简单扩展都显然会使修复搜索空间爆炸。

给定一个有问题的程序 P，它在测试套件 T 中至少有一项测试失败，APR 工具（隐式或显式地）搜索由 P 的变异程序组成的空间 P，以允许变异程序通过 T 中的所有测试。

在这项工作中，我们提出了针对特定但重要的一类多块修复问题的 APR 技术。我们的解决方案在很大程度上得益于两个研究机构的见解。首先是关于检测和使用代码克隆的研究。这项研究表明，代码克隆在程序中非常丰富。通常，主题系统的 5-25％和多达 50％可以由克隆的代码组成。此外，通过克隆代码复制错误是一种普遍现象。多达 10％的克隆代码中包含错误，其中在代码克隆中发现的错误的 55％是复制的错误[9]。第二项工作是 APR 技术本身，其中绝大部分技术都直接或间接地利用了“整形外科假说” –可以从现有代码中获得修复成分。这可以采取从现有补丁集中派生的程序转换模式（定义修复空间）的形式。或者，可以从现有代码中提取诸如程序元素，表达式，语句或整个代码片段之类的修复成分，并重新用于创建补丁。这两个工作主体都指出，在整个项目中找到“外观相似”的代码段，并带有类似的错误并需要类似的补丁程序是合理的，我们的工作也利用了这种见解。

我们提出的方法总结了单块修复技术，以包括可能需要在多个位置应用基本相似的补丁（即多块补丁）的错误。我们将修复位置的底层集合称为演化 1 的同类–在相似的上下文中实例化的相似外观代码，预计在代码库的整个生命周期内都会经历相似的变化。重要的是要注意，如 RQ1 所述，从传统意义上讲，这些演化同类不只是代码克隆。此外，我们的方法与整形外科假说的使用是独立的，该假想涉及挖掘现有代码以获取抽象构造或具体成分，以构成当前的修复。相比之下，我们提出的分析试图找到当前漏洞暴露的演化同类，可以同时以类似的方式对其进行修复。原则上，这与用于执行修复的实际技术无关。

我们的方法的关键是能够准确地识别给定错误的演化同类，这提出了以下技术挑战：

挑战 1：演化同类不只是代码克隆。 因此，需要进一步的分析以揭示所需的同类关系。

挑战 2：测试用例生成的频谱可能不会暴露甚至覆盖所有同类实例，缺少一些同类最多只能产生部分修复。

挑战 3：识别这些同类的任何不精确性都可能对识别成功的修复。同样，过近似最多只能产生部分修复。而且，搜索潜在的过近似集合的集合在计算上根本不可行。

我们提出的方法的核心是一种使用三个不同的信息源来准确确定适合于当前错误的进化同类的分析。首先，它使用测试频谱来隐含一个或多个兄弟姐妹，以提供兄弟姐妹识别的起始参考。其次，它使用代码相似性分析标识具有语法的相似性和上下文的语义相似性的同类，通过将语法相似性与有限范围的数据流分析相结合，以对已标识的同级实施语义上下文的相似性。原则上，这种代码相似性分析可以识别出超出测试频谱范围的潜在同类，可以弥补典型测试套件的不足。第三，我们的方法使用修订历史记录信息来进一步确定具有相似更改历史记录的。一旦确定了演化同类，就可以将它们交给任何修复算法，同时为所有同类生成实质上相似的修复（只有名称空间变化）。原则上，可以对任何传统的修复工具进行适当的改造以执行此部分。

我们已经在工具 Hercules 2 中实现了介绍的技术，并在广泛使用的 Defects4J 数据集中对其进行了评估。 在我们的实验中，Hercules 能够正确修复 49 个错误，这是迄今为止任何一种 APR 技术中最高的。 这包括 15 个多块的 bug，以及总共 13 个到目前为止尚无其他技术修复的 bug。

2、HERCULES

图中展示了 Hercules 的基本工作流程。考虑到程序（P）中存在错误，Hercules 会使用 P 的源代码及其版本历史记录，带有至少一个失败测试用例的测试套件（T）以及可选的错误报告，并生成正确的修复 P 的单块或多块大补丁。

第一，识别演化同类：Hercules 首先在修复位置级别应用树相似性算法。然后仅针对相似的修复位置，Hercules 提取相关上下文，然后再次将树相似性算法应用于上下文。最后，Hercules 利用版本历史来高置信地找到进化同类。准备：Hercules 将程序表示和操纵为抽象语法树，以分析程序并实例化修复方案。

步骤 1：确定相似的修复位置。为了找到相对于 R1 的演化同类（ER1），首先我们计算 R1 与程序频谱 S 中每个位置（Ri）之间的相似度。如果修复位置不匹配，则无需分析其上下文和版本历史记录。为此，我们应用树距离算法来计算两个候选修复位置 R1 和 Ri 之间的相似度。

步骤 2：确定修复位置的相关性。步骤 1 可以删除大部分不相关的维修地点。但是，由于任意两个随机语句在语句级别（尤其是小型语句）可能相似，因此仍然存在很多误报。因此，Hercules 通过程序上下文来增强分析，以确保修复位置确实相似并且在相似的上下文中使用。

步骤 3：利用版本历史记录修订演化同类。由于识别演化同类的准确性直接影响修复，因此我们进一步利用版本历史对其进行修订。可能有两种可能的情况。 第一，在步骤 2 中确定的候选中的某些修复位置彼此独立。 第二，由于测试规范较弱，一些真正的同类不在列表中。我们的看法是，真正的同类可能具有相似的进化历史，即他们过去曾经历过类似的 AST 操作。

第二，生成候选补丁：在此步骤中，Hercules 会根据上一步的结果生成单个或多块补丁。对于单个修复位置，Hercules 遵循传统的补丁生成方法。它使用范围内的修复表达式实例化选择修复方案。但是，对于涉及演化同类的多个修复位置，Hercules 在抽象级别实例化选定的修复方案。更具体地说，Hercules 提取所有修复位置以消除由于各种标识符名称而引起的差异。一旦应用了变换，Hercules 可以还原原始变量来生成具体的候选补丁。因此，Hercules 生成的修复空间可能同时具有单个或多块补丁。

第三，候选补丁的排序和验证：生成候选补丁后，Hercules 可以使用现有修复工具中提出的任何排名模型（基于启发式或基于机器学习）对候选补丁进行排名，并一次选择前 N 个候选补丁进行验证。 在每个候选（单块或多块）补丁的验证阶段，Hercules 首先运行失败的测试，如果通过，则 Hercules 运行回归测试。如果回归测试套件通过，则 Hercules 停止并将该补丁报告为最终补丁。

3、实验设置与结果

RQ1：与传统的克隆检测相比，Hercules 通过演化同类检测进行修复定位的效果如何？

许多目标修复位置不是传统意义上的克隆，并且超出了 Deckard 的语法固定的上下文克隆检测范围。相比之下，Hercules 的专门的演化同类分析结合了多种独立信息源，对于当前的应用（即多块程序修复）而言，它要准确得多，因此必不可少。

RQ2：Hercules 如何有效地推广 APR 工具的传统单块修复策略，以执行单块修复和多块修复？

通过将结果与 Hercules-SH 进行比较，我们发现 Hercules 不会由于错误的同时修复而丢失单块错误。此外，由于同时进行多块修复，Hercules 仅额外生成两个不正确的补丁。原因是在多块修复中，由于程序更改发生在两个或多个修复位置，因此通过测试套件检测到回归错误的可能性大大增加。即使测试用例在 n 个修复位置中检测到回归，也将丢弃整个候选补丁。根据块数量对多块错误和补丁的分布进行分析，可以发现 Hercules 修复了各种多块的 bug，大小从 2 个块到最大的 7 个块不等。

RQ3：与最新的程序修复工具相比，Hercules 在修复程序方面的效果如何？

Hercules 修复了 SimFix 和 ACS 无法修复的 9 个独特的大块错误。此外，如果考虑所有错误，Hercules 修复了 13 种独特的错误，这些错误是现有方法无法修复的。总体而言，结果表明，Hercules 提高了修复水平。

RQ4：Hercules 的各个组件对其总体错误修复功能有何贡献？

当我们使用固定大小的上下文时，Hercules 丢失了 11 个错误。同样，版本历史对于正确修复六个错误至关重要。最后，结果进一步表明，当 Hercules 以增量方式工作时，它无法修复 9 个错误。 总而言之，结果表明 Hercules 的所有功能都有助于修复多块的错误。

4、局限

块修复的范围。我们当前的技术仅处理特定类别的多块修复，即每个块的补丁基本相似。尽管与基准工具相比，这确实将成功修复的几率提高了近 50％，但未来的研究仍需要解决其他类别的多块错误。

版本历史分析的准确性。我们的版本历史记录分析可能会受到版本库中主要结构更改（例如目录或包结构或其他系统重构更改）引入的修订历史记录中噪声的影响。我们使用几种启发式方法来弥补这种破坏，并手动检查了一些采样错误实例的历史记录，以验证启发式方法的准确性。但是，我们不能保证分析的正确性。

结果的普遍性。我们的评估仅在 Defects4J 数据集上进行，该数据集是程序修复研究中广泛使用的基准。但是，数据集的 5 个主题系统无法捕获各种 Java 应用程序及其错误。将来必须在其他主题上对该技术进行进一步的验证。我们的技术已实例化用于 Java 程序修复，但原则上也可以应用于 C / C 程序修复。但是其在这种情况下的功效仍有待研究。

5、结论

自动程序修复技术在过去十年中取得了长足的进步。但是，实际应用仍然是一个难以实现的目标。实现此目标的重大障碍之一是当前的 APR 技术无法生成多块补丁。在这项工作中，我们提出了一种新颖的 APR 技术，该技术将单块修复归纳为一个特定但重要的多块修复问题类别，即需要在多个位置应用大致相似的补丁的问题。我们将这类维修位置集称为“演化同类”——外观相似的代码，在相似的上下文中实例化，并且预计会随着时间而发生类似的变化。我们提出了一种新颖的分析方法，可以针对给定的错误准确地识别出一组进化兄弟姐妹。这种分析结合了三个独立的信息源，即测试套件频谱，一种新颖的代码相似性分析，将语法和语义特征进行了比较，以及项目的修订历史。我们在工具 Hercules 中实现了该技术，并证明了它能够正确修复 Defects4J 数据集中的 49 个错误，这是迄今为止任何单个 APR 技术中最高的。其中包括 15 个多块的 bug，以及 13 个到目前为止尚未通过其他任何技术修复的 bug。我们认为，这一贡献是实现 APR 工具实际部署的一个微小而重要的步骤。

致谢

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