摘要：

由于调试是一项耗时的活动，因此自动化诸如 GenProg 之类的程序修复工具大受欢迎。最近的一项研究表明，Gen Prog 的大多数维修都只是通过删除功能来避免错误。我们发现推出于 2015 年的 SPR，仍然删除了许多“合理的”重新配对中的功能。与 Gen Prog 和 SPR 等生成并验证系统不同，尽管基于语义的修复方法在生成的修复质量方面显示出了优势，但到目前为止，它们的可伸缩性一直是人们关注的问题。在本文中，我们介绍 Angelix，一种可扩展的基于语义的新颖修复方法，可达到与基于搜索的内容维修工具，例如 GenProg 和 SPR 能处理的代码规模。这表明，Angelix 比以前提出的基于语义的修复方法更具可扩展性，例如 SemFix 和 DirectFix。此外，我们的修复方法可以修复相互依赖的多个漏洞。这种修复使用 SPR 和 GenProg 是很难实现。在我们的实验中，Angelix 从大型真实世界软件系统诸如 wireshark 和 php 之类的软件生成了修复，这些生成的修复包括多处修复。我们还报告了我们自动修复著名的 Heartbleed 漏洞的经验。

关键字：程序修复，可扩展的基于语义的修复，多行补丁，Angelic forest

1. 背景

自动化程序修复具有光明前途的想法逐渐成为现实。最近已经引入了各种自动修复工具，例如 GenProg，PAR，relifix，SemFix，Nopol，DirectFix 和 SPR 等。这些自动修复方法可以分为以下两种广泛的方法，即基于搜索的方法（例如 GenProg，PAR 和 SPR）和基于语义的方法（例如 SemFix，Nopol 和 DirectFix）。基于搜索的修复方法（也称为“生成并验证”方法）在搜索空间中进行搜索，以生成修复候选者并针对提供的测试套件验证该修复候选者。同时，基于语义的修复方法使用语义信息（通过符号执行和约束求解）来合成修复。

将修复方法分为基于搜索的修复和基于语义的修复，在某种程度上类似于将软件测试分为基于搜索的测试和基于符号执行的测试。尽管这样的分类可能有点粗略，但可以帮助我们了解自动化程序修复的当前趋势。GenProg 是一种基于搜索的著名修复工具，已证实可扩展到大型现实世界软件，例如 php 和 wirehark。同时，在可修复性方面，第一个基于语义的修复工具 SemFix 被证明比 GenProg 更有效（因为可以修复更多有缺陷的程序，所以更高）。尽管 SemFix 仅应用于相对较小的程序。之后，在这两种方法中，都开始考虑了高质量修复的重要性，从而产生了另一种基于搜索的修复工具 PAR 和基于语义的修复工具 DirectFix。

当前，自动程序修复的研究考虑了三个属性：可伸缩性（应扩展到大型现实程序），可修复性（应通过覆盖许多缺陷类别来修复大量缺陷）和修复质量（应产生减少对程序的更改，删除较少的功能并且更可能被开发人员接受的修复）。就基于语义的方法论而言，可伸缩性低是批判的主要来源，尽管它在高可修复性（例如 SemFix）和高质量修复方面取得了可喜的成果。

为了提升自动程序修复的效果，本文提出了 Angelix，一种可扩展的基于语义的新颖修复方法，可达到与基于搜索的内容维修工具处理的代码规模，有效避免了传统基于语义自动化程序修复的局限性。基于语义的修复方法通常通过符号执行来提取修复约束，该修复约束充当指导程序合成的规范，因此可以合成满足修复约束的补丁。Angelix 中可扩展的多行错误修复的关键推动因素是被称为 angelic forest 的新颖轻量级修复约束。该 angelic forest 是通过符号执行自动提取的。与先前工作中使用的修复约束相比，angelic forest 更简单，并且其大小与正在修复的程序的大小无关，从而使我们的修复方法可扩展。尽管 angelic fores 比较简单，包含足够的语义信息以启用多位置错误修复。在现有的基于搜索的修复工具中，SPR 不支持多行修复。尽管 GenProg 可以更改程序的多个位置，但最近对 GenProg 维修的研究表明，GenProg 生成的看似复杂的维修位于 实际上，绝大多数情况下的功能等效于单行修改。因此 Angelix 兼具了基于搜索的修复和基于语义的修复的优势。

2. 实验方案

我们的方法如下所示，为了提升基于语义自动化程序可伸缩性。我们方法中最关键的步骤是提取修复约束。最为关键的因素是被称为 angelic forest 的新颖轻量级修复约束。该 angelic forest 是通过符号执行自动提取的。与先前研究中使用的修复约束相比，angelic forest 更简单，并且其大小与正在修复的程序的大小无关，从而使我们的修复方法可扩展。

（1） 程序转换。执行保留语义的程序转换，以扩展修复算法可以修复的缺陷类别。修复框架对于添加更多保留语义的程序转换方案是透明的。

（2） 故障定位。使用 Jaccard 公式，该公式被认为对自动程序修复最有效。由于修复算法会修改错误的表达式，因此在表达式级别而不是语句级别应用 Jaccard 公式。

（3） 提取修复约束。通过受控的自定义符号执行来提取 angelic forest，不是在使用符号输入来启动符号执行的情况下，而是在一些可疑程序位置（根据统计错误定位结果选择）安装符号，以控制执行符号执行期间要探索的路径。算法 1 显示了如何提取 angelic forest。

（4） 补丁合成。将提取出的 angelic forest 作为合成规格提供给修复合成器。 综合修复在执行时会遵循每个测试的 angelic forest 路径之一，从而所有测试都通过。 在这些 angelic forest 路径中，每个修复的表达式返回其在相应 angelic forest 路径中指定的相应 angelic forest 值。从而根据 angelic forest 合成补丁值。

3. 实验评估

（1）两个维度评估 Angelix

?

修复方法可以从大型的实际软件中产生补丁。

?

修复方法可以修复多位置漏洞。

（2）实验结果一:

可修复性。与最新的修复工具 SPR 相比，我们的工具在 libtiff 中显示出较高的可修复性（在我们的工具中修复了更多缺陷）（10 对 5），而在 php 中显示出较低的可修复性（10 对 18）。 在其余 3 个项目中，两种工具都显示出相同的可修复性。 例如，SPR 的缺陷类包含插入诸如 memset 之类的函数调用，该缺陷类中包含 5 个 php 缺陷;同时，Angelix 可以修复多个错误位置，而我们的工具专门修复了两个 libtiff 多位置缺陷 。表 3 显示了跨对象，每种修复工具专门修复的缺陷数量。 与 SPR，GenProg 和 AE 相比，我们的工具产生了最多数量的独特修复。

修复质量。我们还定性比较了 Angelix 和 SPR 的修复情况。我们使用 SPR 进行实验，并显示了 SPR 生成的修复，原始代码与每个修复之间的差异用阴影表示。SPR 修复看起来有问题，因为它只是通过禁用 then 分支中的代码块来删除功能。实际上，此修补程序在功能上不等于开发人员提供的修补程序。不过，这样的过度拟合的修复对调试很有帮助，因为如果有条件的话，用户至少可以看到（不正确的）修复问题。但是，通过将 SPR 修复与我们的工具 Angelix 在的修复进行比较。我们的维修工作将漏洞的位置更精确地定位为“ td-> td nstrips> 1”。这是因为我们的维修工具会产生通过使用 MaxSMT 求解器修复与原始漏洞表达式接近的问题。结果，可以更精确地确定有问题的漏洞位置。在这种情况下，我们的修复与开发人员提供的修复相同。

仅删除功能的漏洞修复在 SPR 修复中很常见。表 4 比较了我们的工具和 SPR 之间通过删除功能的维修次数。在我们基于五个项目的实验中，SPR 生成的修复中有 42％删除了功能，在 libtiff 主题中，该百分比上升到 80％。 即使省略了三个项目（python，lighttpd， 和 fbc），功能百分比即使在高达 45％的高比率下，删除修复操作也保持不变。 GenProg 和 AE 还经常生成功能删除修复。相比之下，Angelix 生成删除功能的维修次数较少（21％）。

（3）实验结果二:

表 5 显示了 GenProg benchmark 和 coreutils 中多位置漏洞缺陷的实验结果。 “固定表达式”列显示通过我们的工具所修复的表达式数量。Angelix 进行了功能上与开发人员为 coreutils-00743a1fec48bead 提供的修复等效的修复。同时，在 coreutils-1dd8a331-d461bfd2 中，虽然两个条件表达式的功能与开发者补丁的修复方式相似，但在我们的修复中，输出信息未得到纠正。在 coreutilsc5ccf29b-a04ddb8d 中，开发人员提供的修复程序使用的函数调用未在我们的修复程序中使用。至少在两个基准测试中，多位置缺陷类别涵盖的缺陷数量受到限制。我们进行了调查（GenProg benchmark 和 CoREBench）。 开发人员提供的许多针对多行缺陷的修复程序涉及添加新的变量，语句和函数。我们相信自动修补的研究应该进入更复杂的补丁程序，以及我们的多位置缺陷类正朝着这样的方向发展。目前,在大型实际软件中，只有 Angelix 修复工具可以生成（非功能删除）多位置修复补丁。

4. 结论

在本文中，我们描述了基于语义的修复方法如何可以扩展到大规模的实际软件。这种可扩展性的关键推动因素是我们新颖的轻量级修复约束，称为 angelic forest。我们通过实验表明，我们的修复方法可以成功地从各种实际软件（包括 wireshark 和 php）生成修复，这是应用了自动修复工具的最大程序。此外，除了提供可扩展性之外，我们的修复方法还比现有的可扩展修复工具（例如 SPR 和 GenProg）产生更高质量的修复；与这些现有工具相比，我们的修复工具产生的功能-在我们的实验中删除程序的频率降低。我们的修复工具成功修复了现实世界软件中的多位置错误，而现有修复工具无法做到这一点。最后，我们报告并成功修复了著名的 Heartbleed 漏洞。

致谢

本文由南京大学软件学院 2020 级研究生葛宇翻译。