Angelix：通过符号分析的可扩展多行程序补丁合成

由于调试是一项耗时的活动，导致了一些自动程序修复工具（如 GenProg）引起了人们的兴趣。最近的一项研究表明，GenProg 修复大多是通过简单地删除相关功能来避免错误。我们发现，SPR，这一 2015 年提出的最先进的修复工具，仍然在许多合理的补丁中删除某些功能。与 GenProg 和 SPR 等生成并验证系统不同，基于语义分析的修复技术则是基于程序的语义信息来合成修复补丁。尽管这种基于语义的修复方法在生成补丁的质量方面显示出了一定的前景，但到目前为止，它们的扩展性一直是人们关注的问题。

在本文中，我们提出了 Angelix，这是一种新颖的基于语义的修复方法，同时可以扩展到与基于搜索的修复工具（如 GenProg 和 SPR）处理的类似规模的程序。这也表明 Angelix 比以前提出的基于语义的修复方法（例如 SemFix 和 DirectFix）更具可扩展性。此外，我们的修复方法可以修复多个相互依赖错误位置，这也是 SPR 和 GenProg 很难实现的。在我们的实验中，Angelix 从诸如 Wireshark 和 php 的大型现实世界软件生成修复补丁，这些生成的修复包括多位置修复。

3 技术介绍

该修复方法包括以下四个步骤：（1）程序转换，（2）错误定位，（3）修复约束提取，（4）补丁合成。

在第一步，我们执行保留语义的程序转换以扩展我们的修复算法可以修复的缺陷类，一般而言，我们的修复框架对于添加更多保留语义的程序转换方案是透明的；在第二步中，我们进行统计错误定位。根据相关研究，在自动程序修复中该 Jaccard 公式效率最高，因此我们也采用该公式，由于我们的修复算法会修改缺陷的表达式，因此我们在表达式级别而不是语句级别应用 Jaccard 公式。最后两个步骤则将基于语义的修复方法与基于搜索的修复方法（如 GenProg 和 SPR）区分开来，其中基于语义的方法通常通过符号执行从正在修复的程序中提取修复约束，该修复约束充当指导程序合成的规范，因此可以合成满足修复约束的补丁。

本文介绍的修复方法新颖之处在于一个轻量级修复约束，我们称之为天使森林。天使森林的大小与需要修复的程序规模是无关的，这也使得本文提出的修复方法具有不错的扩展性。我们的天使森林，尽管简单但是包含了足够的语义信息来进行多位置缺陷修复。接下来，我们基于天使值（公式 1）和天使路径（公式 2）来公式化定义天使森林（定义 3）。

3.1 天使森林提取

我们通过受控符号执行进行天使森林提取，受控是指我们不是使用符号输入来启动符号执行的情况下，而是在一些可疑的程序位置（根据统计错误定位结果）中安装符号，以控制执行符号执行期间要探索的路径。图 1 算法展示了如何提取天使森林

图 1 天使森林生成算法

3.2 补丁合成

当天使森林获得后，我们将它作为合成说明提供给我们的修复合成器，当修复合成器被执行时，会执行每一个测试用例的天使路径，从而通过所有的测试用例。对于这些天使路径，每一个被修复的表达式都返回其相应的天使值。

我们的修复合成器是在基于组件的修复合成（Component Based Repair Synthesis , CBRS）基础上实现的，CBRS 将程序视为原始组件（例如变量和运算符）的电路。例如，图 2 的电路图显示了程序表达式 x>y 的电路，其中方框和线分别表示组件机器联系。给定原始的缺陷程序，组件以及要合成的程序说明，CBRS 的目标是在组件之间进行搜索以（1）满足给定的说明、（2）与原始缺陷程序的连接关系差异性最小。以一个错误表达式 x>=y 为例，图 2 中的表格则展示了该表达式所需要的规范说明，而由于 x>y CBRS 更改了变量 x 和 y 从组件>=到组件>的联系。

图 2 组件示意图

3.3 优化

为了控制符号执行次数，我们使用以下迭代方法。首先，我们从测试用例集的部分用例开始，该用例集可最大程度地覆盖可疑位置。然后对于约减后的测试用例集，我们得到其天使森林并合成补丁。如果生成的补丁会导致整个用例集回归，则将单独的测试用例添加到测试用例集中，重复上述步骤直到所拥有的测试用例可以通过。关于修复时间，不同于基于搜索的修复方法，由于大量的修复痕迹需要不断地重建程序并重新测试，我们的方法可以在少量的试验中得到修复结果，同时重构和重新测试的开销大大减少。

4 结论

本文中，我们讨论了如何利用我们的轻量级修复约束，使得基于语义的缺陷修复方法扩展到大型真实程序上，同时通过实验表明，我们的修复方法可以成功地从各种真实软件中生成修复，包括 wireshark 和 php，这是现有自动修复工具可以应用到的最大规模的程序。我们的修复工具已成功修复了真实软件中的多位置错误，这也是现有修复工具无法做到的，同时该工具成功修复了著名的 Heartbleed 缺陷。