引用：Sergey Mechtaev, Xiang Gao, Shin Hwei Tan, and Abhik Roychoudhury. 2018. Test-Equivalence Analysis for Automatic Patch Generation. ACM Trans. Softw. Eng. Methodol. 27, 4, Article 15 (October 2018), 37 pages. https://doi.org/10.1145/3241980.

摘要：

程序自动修复是一个问题，即寻找给定错误程序的转换形式（称为补丁），以消除可观察到的故障。它具有重要的应用，例如提供调试帮助，自动为学生作业评分以及修补安全漏洞。现有修复技术面临的一个共同挑战是对大补丁空间的可伸缩性，因为这些技术明确或隐含考虑了许多候选补丁。

程序修复的正确性标准通常是由一组测试套件给出的。由于底层搜索算法执行了大量测试，因此当前的修复技术无法扩展。在这项工作中，我们通过引入基于测试等效关系的补丁生成方法来解决此问题（如果两个程序在给定测试中“测试等效”，则表明它们在该测试中无法产生可分辨的结果）。我们分别基于运行时值和依赖项提出了两种测试等效关系，并提出了一种将补丁实时划分为测试等效类的算法。

我们在真实程序上的实验表明，我们所提出的方法可以大大减少测试执行的次数，因此在不牺牲补丁质量的情况下，与现有修复技术相比，效率提高了一个数量级。

关键词：软件工程，自动编程，软件测试与调试，动态分析，程序修复，程序合成，动态程序分析

1.介绍

每个开发人员都知道，调试非常困难并且非常耗时。由于自动验证和调试技术的进展缓慢，发现和消除缺陷仍然主要通过手动完成。自动补丁生成方法可以潜在地缓解此问题，因为它们能够解决现实程序中的缺陷，并且仅需要最少的开发人员参与。具体来说，它们已成功应用于提供调试提示，自动为作业评分和修补安全漏洞。但是，巨大的搜索空间问题对当前的程序修复技术提出了严峻的挑战。

程序修复的目的是修改给定的错误程序，以消除可观察到的故障。具体来说，测试驱动程序修复的目标是修改错误的程序，使其通过所有给定的测试。 测试通常由开发人员提供，但是当有正式规范时，也可以在反例指导的优化循环中自动生成测试。通过所有给定测试的补丁（程序修改）在程序修复过程中被认为是合理的。由于测试套件的规格不完整，因此可能存在补丁与用户的意图不符而只是过分贴合测试本身。为了解决这个问题，最新的技术在候选补丁的空间上定义了成本函数（优先级），并搜索优化该功能的补丁。例如，可以基于句法距离，语义距离和从人类补丁中学习的信息来确定更改的优先级。

补丁生成系统需要考虑可能的较大空间的修改，以解决多种缺陷。程序修复的主要挑战之一是可扩展到大型搜索空间。当前的技术可能需要大量的时间来生成补丁，但是它们只考虑并生成相对简单的程序转换。这会影响程序修复产生类似于人的修复的能力，因为人的补丁程序通常涉及复杂的源代码修改。 除此之外，最近的一项研究表明，通过增加更多的转换来扩展搜索空间可能会导致修复系统由于搜索时间的增加而发现较少的正确修复。

尽管现有的测试驱动程序修复技术采用了不同的方法（例如，GenProg 使用遗传编程，SemFix 和 Angelix 基于约束解决，Prophet 基于机器学习），但它们都通过重复执行测试来搜索补丁。由于大型现实程序中测试执行的成本很高，因此执行的测试执行次数是许多现有程序修复算法的主要瓶颈。

现有的搜索方法可以分为两类：基于语法的和基于语义的。基于语法的技术（例如 GenProg）显式生成并测试语法更改。因此，通过这种技术执行的测试执行的数量与探索到的候选补丁的数量成正比的。基于语义的技术通过路径探索并基于此规范合成更改来推断已识别语句的规范。例如，Angelix 使用符号执行（可以视为测试执行的变体）探索给定测试的执行路径偏差，而 Prophet 通过枚举条件值序列探索给定测试的执行路径偏差。因此，通过这样的技术执行的测试执行的数量与探索路径的数量成正比。

这项工作的目的是提高程序修复的可伸缩性，而不牺牲所生成补丁的质量。为了实现这一目标，我们提出了一种基于测试等效关系的方法。如果两个程序在一个测试中等效，则这些程序在该测试中将产生难以区分的结果。

该算法通过在测试执行过程中进行动态分析，将候选补丁的空间划分为测试等效类。 这使我们的方法可以减轻以前技术的局限性。与基于语法的技术相比，它减少了测试执行的次数，因为单个执行足以评估多个补丁候选者（特别是同一测试等效类中的所有补丁）。与基于语义的技术相比，由于两个原因，它减少了测试执行的次数。首先，它避免了探索“不可行”的路径（值的序列），即在给定测试的情况下，任何考虑的候选补丁都无法诱发的路径或值的序列。其次，它重用跨多个测试推断出的信息，以跳过冗余执行，而以前的基于语义的技术则为每个测试独立执行路径探索。

贡献。这项工作的主要贡献如下：

1. 我们建议使用测试等效关系来大幅度缩小为程序修复目的而探索的搜索空间。
2. 通过将其与语法指导的程序综合，我们使用于变异测试的测试等效关系（我们称为基于值的测试等效关系）能够应用在程序修复领域。
3. 我们定义了一个基于动态数据依赖关系的新的测试等效关系，并提出了一种通过组合基于值和基于依赖的测试等效关系来合成分配语句的方法。
4. 我们引入了一种新的补丁程序空间探索算法，该算法可以将补丁程序动态地（在测试执行过程中）划分为测试等效类，从而实现高效的程序修复，从而需要较少的测试执行来生成补丁程序。
5. 我们根据 GenProg ICSE’12 基准测试对真实程序中的算法进行了评估；它表明测试等价性显着减少了所需测试执行的次数，因此提高了测试驱动程序修复的效率，并将其扩展到更大的搜索空间而又不牺牲补丁质量。

2.动机

本节提供了三个示例，这些示例说明了现有技术的局限性：大量重复的测试执行，搜索最佳修复的效率低下以及适用性受到限制。 我们还提出了关键思路，使我们的方法能够解决这些局限性。

2.1 例子：修复条件

考虑 GenProg ICSE’12 基准的 Libtiff1 版本 0661f81 的缺陷。图 1（a）中的代码负责刷新由压缩算法写入的数据，并且缺陷是由错误的突出显示的条件语句引起的。Libtiff 测试套件包含 78 个测试，而这种缺陷通过称为“ tiffcp-split”的失败测试来体现。图 1（b）演示了通过删除条件语句 tif-> tifrawcc！= origrawcc 来修改错误条件的开发人员补丁。

我们将演示现有的自动程序修复算法如何针对这种情况生成补丁。首先，修复算法执行故障定位以识别可疑程序语句。现有工具中本地化语句的数量可能从数十到数千不等，具体取决于算法和配置（它可能包含所有已执行的语句）。在此示例中，我们仅考虑图 1（a）中突出显示的错误表达式的位置。

其次，程序修复算法定义了候选补丁的搜索空间。在这项工作中，我们主要关注两种已被证明可以扩展到大型现实程序的最新方法：Angelix 和 Prophet。具体来说，我们的目标是支持在这些系统中实施的转换组合。因此，针对突出显示的条件语句的搜索空间包括了其子表达式的所有可能替换，这些替换由可见程序变量和 C 运算符构成的表达式细化（例如，追加&& 表达式和|| 表达式），替换运算符和交换参数。总体而言，我们合成器中的搜索空间包含对错误条件的 56,243 项修改。

最后，程序修复算法将探索搜索空间，以尝试找到通过所有给定测试的修改。如果算法确定它通过了所有测试或至少有一项测试失败的话，则将探索搜索空间的元素。现有的搜索空间探索方法可以分为两类：基于语法和基于语义。基于语法的算法显式生成并测试语法更改。在此示例中，基于语法的算法必须执行失败的测试 56,243 次才能评估所有候选者。由于测试套件中有 78 个测试，因此需要 907,457 次测试执行才能探索搜索空间。鉴于成本高昂测试执行方面，这种方法的可伸缩性较差。

基于语义的技术（例如，Semfix，SPR，Angelix 和 Prophet）将探索分为两个阶段。 首先，他们通过路径探索为识别出的表达式推断出一个合成规范。对于此示例，它们枚举并执行条件值的序列（例如，true，true，true，false，...）以查找使程序能够通过测试的那些序列。其次，他们综合了条件的修改以匹配推断的规范。在此示例中，存在 256 个可能的执行路径（在测试执行过程中多次评估条件），因此基于语义的算法对失败的测试执行 256 次测试执行，对整个测试套件执行 1,320 次。尽管基于语义的方法被证明具有更高的可扩展性，但它们仍然受到路径爆炸问题的困扰：执行路径的数量可以无限。为了解决这个问题，当前的系统对探索路径的数量设置了限制。但是，这可能会影响其有效性：如果省略了跟在正确补丁的路径，则无法生成此正确补丁。

在这项工作中提出的算法将程序修改动态地划分为测试等效类。我们证明了第 3.3 节中描述的关系 t~value 的影响。如果在测试执行期间将它们评估为相同的值序列，程序表达式的两个修改是等同的 w.r.t. t~value。令人惊讶的是，对于失败的测试“tiffcp-split” w.r.t t~value，可以将 56,243 个修改的空间划分为五个测试等效类。图 2 中给出了代表不同测试等价性类别的搜索空间的五个元素。由于同一测试等价性类别中的所有补丁对相应的测试都表现出相同的行为，因此失败的测试只能执行五次以评估所有候选补丁。

我们的算法为测试套件中的每个测试计算测试等效类。但是，由于不同测试的测试等效类可能会相交，因此我们的算法会利用这一点跳过不同测试之间的冗余执行。具体而言，对于每个下一个测试，它仅评估未包含在先前执行的测试的失败测试等价性类中的修改子空间。 同时，基于语义的技术针对每个测试独立执行规范推断，而无需在测试之间重用信息。结果，我们的算法只需要执行 103 次测试就可以评估整个测试套件的所有 56,243 个修改。

2.2 示例：最佳修复

考虑图 3（a）中的程序 p，该程序对间隔（0，i]中的奇数计数。表示必须由修复算法修改的错误条件（正确条件为 i mod 2 = 1）。 我们表示一个程序，它用 e 替换为表达式 p [* / e]。修复算法从图 3（b）中的空间 P 搜索合理的补丁（用一个条件语句去替换），使得生成的程序通过了如下定义的测试 t：

t:=({ i -> 4 , c -> 0}, λσ, σ(c) = 2 )

其中 t 是（1）初始程序状态（从变量到值的映射）和（2）使用 lambda 表示法表示的测试断言（程序状态上的布尔函数）的组合。假设使得 p 不等于 t，除此之外，我们考虑在图 3（c）中为考虑的替代空间定义的成本函数 κ，目的是找到成本最低的合理补丁。

为了找到示例程序的补丁，类似 Angelix 和 Prophet 的技术会枚举条件在测试执行期间可能采取的值序列。由于可能存在无限数量的此类序列，因此现有方法为探索序列的数量引入了限制，并使用探索试探法选择要探索的序列。例如，Prophet 枚举了值序列，其中条件语句始终首先执行真分支，直到特定点之后再始终执行假分支。因此，对于所考虑的示例，它将枚举以下序列：

{ true, true, true, true },

{ true, true, true, false },

{ true, true, false, false },

{ true, false, false, false }

对于这些序列中的每个序列，Prophet 都使用测试 t 来执行程序，使得条件在执行过程中采用此序列中的值。只有第三个序列{true，true，false，false}允许程序传递 t，因此它将被选择作为表达式合成的规范。合成器将找到表达式 i> 2，从而获得代价为 0.5 的次优补丁 p [? / i> 2]，因为这是来自搜索空间的唯一满足规范的表达式。但是，由于算法未探索相应的序列{false，true，false，true}，因此无法生成成本为 0.3 的正确表达式 i mod 2 = 1

与类似 Angelix 和 Prophet 的技术相比，我们的算法在搜索空间中进行迭代，以使其在每个步骤中以最低的成本选择和评估未评估的候选补丁。具体来说，首先选择成本为 0.1 的候选补丁 p [? / i≥0]。 它动态地计算该候选补丁的测试等价性等级，2.1 节中描述的值。该类包含程序 p [? / c≥0]，因为条件 i≥0 和 c≥0 对 t 产生相同的值序列{true，true，true，true}。 由于 p [? / i≥0]没有通过测试，因此将整个相应的测试等效类标记为失败。接下来，由于在上一步骤中通过测试等价性间接评估了 p [? / c≥0]，因此它以成本 0.3 选择 p [? / i mod 2 = 1]。 由于该候选者通过了测试，因此算法将其作为找到的修复输出。

2.3 示例：修改赋值

尽管目前的程序修复方法已显示出在修改现有程序表达式方面相对有效，但它们为更复杂的转换提供了有限的支持。在这项工作中，我们考虑一种这样的转换，它将新的赋值语句插入错误程序。 Prophet 和 GenProg 等技术可以通过复制/移动现有程序分配来生成补丁。但是，这种方法有局限性：（1）局部变量的赋值由于其范围而不能从程序的不同部分复制；（2）赋值的每次插入都单独进行验证，这会产生大量所需的测试执行。现有技术并未将规范推导应用于赋值（如第 2.1 节中针对条件语句所述），因为此类规范必须对赋值插入可能引起的所有可能的副作用进行编码（针对每个可能出现在等式左侧的变量），因此对于大型程序而言，推断此类规范是不可行的。

我们从 GenProg ICSE’12 基准测试中展示了测试等价性如何扩展 Gzip5 中缺陷的赋值。考虑图 4 中的三个候选补丁，它们将突出显示的语句插入几个程序位置。首先，我们的算法确定图 4（a）中的程序与图 4（b）中的程序在测试上是等效的（因为关系 t~value 在前面的第 2.1 节中有所描述），因为它们仅在右侧不同在测试执行期间，突出显示的赋值和相应的表达式的值取相同的值。其次，使用简单的动态数据相关性分析，我们的算法确定图 4（a）中的程序与图 4（c）中的程序在测试上等效，因为（1）他们在不同的程序位置插入了相同的赋值，（2）由于在测试执行期间获取了 if 语句的真实分支，因此这两个位置均由测试执行，并且（3）在测试执行期间未在这些位置之间使用/修改变量 ifd 和 part_nb。我们称这种测试等价关系为 t~deps。最后，我们的算法将两个分析的结果合并（作为其并集的传递闭包），并确定图 4（b）中的程序与图 4（c）中的程序在测试上等效。因此，一个测试执行就足以评估所有这些补丁。

3. 测试等效关系

本节正式介绍两个通过程序综合生成的程序修改空间的测试等价关系。在随后的第 4 节中，我们演示如何将这些关系应用于补丁的生成。但是，我们认为这些关系也可以用于不同的领域。其他可能的应用将在第 7 节中讨论。

3.1 初步处理

我们介绍一种命令式编程语言 L 的方法。图 5 中定义了 L 的语法，其中 Z 是整数域，B 是布尔域（是非），Stmt 是一组语句，AExpr 是一组算术表达式，BExpr 是一组布尔表达式，Expr = AExpr∪BExpr，Num 是一组整数，而 Var 是 Z 上的一组变量。L 中的程序是一个语句序列。我们将 L 的子集表示为 P，将表达式的子集表示为 E，将在表达式 e 中遇到的来自 Var 的所有变量表示为 Var（e），该程序是在程序 p 中通过用语句（表达式）s’替换语句（表达式）s 而获得的，表示为为 p [s / s’]。

L 的语义在图 6 中定义，其中程序状态 σ：Var→Z 是从程序变量到值的函数，Σ 是一组程序状态。 我们指出了对程序状态 σ 的修改，其中变量 v 的值被更新为 σ[v→n]。

可以通过派生树表示测试执行，如以下示例所示。

示例 3.2（派生树）。 考虑一个定义为“ x：= y + 1; y：= x”的程序 p 和一个测试 t：=（σin，λσ。σ（y）= 3），其中输入状态 σin：= {x→1， y→2}。 根据图 6 中的语义，以下关系成立：p，σin?σ out，其中 σout：= {x→3，y→3}。 可以通过应用语义规则获得的以下派生树来建立此关系：

输出状态{x→3，y→3}满足测试断言 λσ。 σ（y）= 3，因此 p 通过 t。

3.2 广义综合

针对程序修复技术引入了介绍的测试等价性分析方法，该程序修复技术依赖于语法指导的程序合成来生成补丁。 此类技术基于可见程序变量（程序状态）的值和合成表达式的预期结果，为程序中的“漏洞”生成表达式。 因此，我们将综合规范定义为一组有限的输入输出对集合（输入由 Σ 中的程序状态表示，输出为整数或布尔值）； 我们将所有规格的集合表示为 Spec：= 2 ^（Σ×（Z∪B））。

为了将综合与测试等价性分析集成在一起，我们对程序综合器施加了其他要求：它应在其搜索空间中定义一个值投影算子。

值投影算子生成给定表达式集的最大子集，该子集仅包含在上下文 σ 中被评估为 n 的表达式：

在这项工作中，我们使用枚举合成器在程序合成竞赛中展示了积极的成果。由于它明确地将搜索空间表示为一组表达式，因此在这种合成器中直接实现值投影算子（算法 1）。其他可能的实现将在 A 节中讨论。

3.3 基于值的测试等价关系

本节介绍了仅在表达式上不同的程序空间的检验等价关系 t~value。 从概念上讲，引入的关系概括了已用于突变测试的关系。从算法的角度来看，我们的方法与先前的测试等价性工作不同，在于该关系通过值投影算子与语法指导的程序综合（用于补丁综合）在一起。

直观地，两个程序 p 和 p’使得对于某些表达式 e 和 e’的 p’ = p [e / e’]对于某些测试 t w.r.t t~value 是测试等效的。 如果在用 t 执行 p 和 p’的过程中，将表达式 e 和 e’求值为相同的值，则 t~value。在第 2.1 节中给出了应用此关系的示例。

我们使用 L 的增强语义来建设性地定义关系 t~value。我们选择此表示是因为它同时定义了一种通过程序合成在修改生成空间中计算测试等价类的算法。通过程序工具实现这种语义的方法将在第 5 节中讨论。

图 7 中的语义通过定义 function?value 扩展了图 6 中的语义。 它由谓词 Modified：Expr→B 进行参数化，该谓词标记了已修改的程序表达式，并分析了其替换项的测试等价性。 function ? value 还会维护一组表达式（表示为 c），以使修改后的表达式替换为 c 形成计算出的等效测试类。

增强语义描述了一种识别测试等效类的算法，该算法对于给定的一组表达式（综合搜索空间），通过重复应用该表达式来“过滤”那些不属于当前程序的测试等效类的表达式。值投影算子，在图 7 中突出显示了将值投影运算符应用于当前表达式集 c 的情况。因此，它在此评估步骤中识别出与原始表达式产生相同值的所有表达式 fromc。由于每个表达式可以在测试执行期间进行多次求值，因此值投影运算符也可以多次应用。因此，测试等价类的计算公式为 Πvalueσ1，n1?Πvalueσ2，n2 ... Πvalueσk，nk（E），其中 E 是修改表达式所有替换的集合，ni 是在测试执行期间计算的修改表达式，σi 是相应的程序状态。

在此定义中，如果相应的表达式根据图 6 的语义产生相同的值，则我们将两个仅在表达式上不同的程序称为测试等效程序。具体而言，通过传递程序 p1，测试输入 σin 和一组表达式{e，e’}作为 ?value 的参数，我们得到与结果相同的集合{e，e’}。

上面的命题正式指出：（1）t 值是一个等价关系，（2）如果根据图 7 的语义，两个仅表达式不同的程序是测试等效的，那么这两个程序要么都通过测试，要么都测试失败。C 部分给出了上述命题的证明。

例 3.6（w.r.t t~value 的等效测试程序）考虑一个定义为 if x > 0 then x := y else skip fi, 的程序 p1，一个定义为 if y = 2 then x := y else skip fi, 的程序 programp2，以及一个 testt：=（σin，λσ.σ（y）= 3）其中输入状态 σin：= {x→1，y→2}。 这些程序与 w.r.t. 测试 t 的基于值的测试等价关系，因为它们仅在 if 条件不同，并且以下关系成立：p1，σin，{“ x> 0”，“ y = 2”}? 值 σout，{ “ x> 0”，“ y = 2”}，其中 σout：= {x→2，y→2}。 可以通过以下派生树建立此关系：

3.4 基于依赖的测试等价性

本节介绍了在插入了赋值语句的位置不同的程序空间中的测试等效关系 t?deps。 令程序 p 中的 location 为 p 的语句。程序 p’是通过在位置 l iff p = p [l / v：= e; l]处插入赋值 v：= e 来获得的。设 p 为程序，通过在 p 的位置 l1 和 l2 分别插入赋值 v：= e 获得程序 p1 和 p2。使用 t 执行测试，p1 和 p2 是等价的，（1）对于执行跟踪中的 l1 的每个出现，都有一个 l2 的“匹配”出现（变量 v 在这些出现之间没有被读取或覆盖，变量 Var（e）在这些出现之间没有被覆盖），并且（2）对于执行跟踪中 l2 的每次出现，都存在“匹配”的出现 l1。 在第 2.3 节中给出了应用此关系的示例。

通过 L 的增强语义来正式定义该关系。正如在 3.3 节中一样，我们选择这种表示形式是因为它同时定义了一种识别等价类的算法。 通过程序工具实现这种语义的方法将在第 5 节中讨论。

图 8 中的语义通过定义函数 deps 扩展了图 6 中的语义。 它由一个谓词 Inserted：Stmt→B 来标记所插入的赋值，一个谓词 Left：V→B 来标记所插入赋值的左侧变量，并且一个谓词 Right：V→B 来标记所使用的变量来参数化，在插入的声明的右侧。?deps 仍然保持。

—l—一组代表测试等效插入的位置；

—c—在最后一次读取/写入插入的声明中涉及的变量之后执行的一组位置；

-x-一个布尔值，指示是否在上次读取/写入插入的声明中涉及的变量之后对插入的声明进行了评估。

增强的语义描述了一种分析算法，对于给定的位置集，该算法“过滤”那些不对应于给定分配的测试等效插入的位置。对于插入了赋值 v：= e 的程序，图 8 中的语义计算已执行位置的序列（存储在 setc 中），以使每个序列都包含插入的语句 v：= e（规则 ASSIGN-INS）以及其余所有此序列中的语句不会读取/覆盖变量 v，也不会覆盖 e 中的变量（规则 ASSIGN-NLR）。当找到这样的序列时，在该序列中执行的位置集将与当前的测试等效插入集相交（规则 VAR-LEFT-EXE 和 ASSIGN-LR-EXE 中的 l c）。当未按此顺序执行插入的 v：= e 时，将按此顺序执行的位置集从测试等效的插入集中删除（规则 VAR-LEFT-NEXE 和 ASSIGN-LR- NEXE），因为对于这些位置，这不是 v：= e 的“匹配”出现。

例 3.9（等效测试程序 w.r.t. t?deps） 程序 p1 定义为 x := y; ify > 0 then y := x + 1 else skip fi, 程序 p2 定义为 ify > 0 then x := y; y := x + 1 else skip fi, 一个测试 t：=（σin，λσ。σ（y）= 3）其中输入状态 σin：= {x→1，y→2}。这些程序与测试是等效的，基于依赖的测试等价性关系，仅在分配 x：= y 的位置存在差异，并且以下关系成立：

其中，l1 是 x 的位置：= y inp1，l2 是 x 的位置：= y inp2，σout：= {x→2，y→3}。 可以通过图 9 中的派生树建立这种关系。

上面的定义是非结构化的，因为它没有定义计算具有等价性的测试等价类的算法。 t?。 计算等价类的一种可能方法是使用图 7 和图 8 中的语义和结果分别评估程序。 但是，这需要多个程序执行。 取而代之的是，我们通过结合图 7 和图 8 中 B 部分所示的图 8 中的语义来定义 Lfor t?? 的增强语义，从而使用了一种更有效的方法。这种语义使我们的方法能够计算出测试等价类 w.r.t. t?通过一次执行。

4. 补丁生成

自动化程序修复技术在候选程序修改空间中搜索补丁。 程序修复中的搜索空间如下定义。

定义 4.1（搜索空间）。 搜索空间是通过将给定的变换函数 M：L→2L 应用于错误程序而获得的语法上不同的程序的有限集合。

以前的系统（例如，SPR / Prophet [15，17]和 SemFix / Angelix [22，25]）通过参数化转换模式定义了它们的搜索空间，从而每个模式将给定程序转换为带有“漏洞”和“漏洞程序 ”使用程序合成器填充了表达式。 我们通过图 10 中的函数 M 以类似的方式定义搜索空间（E 表示合成表达式）。

定义 4.2（最佳程序修复）。 设 T 为一个测试套件（一组测试），p∈L 为一个错误程序（?t∈T.?Pass[p，t]），M：L→2L 为一个变换函数，P：= M（p ）是对应的搜索空间，κ：P→R 是成本函数。 最优程序修复的目标是找到一个修复 p∈P，使得 ?t∈T。 在所有此类程序中，Pass [p，t]和 κ（p）最小。

我们的补丁程序生成算法通过（1）从优先级最高的补丁程序开始按优先级（成本函数）定义的顺序评估候选补丁，并（2）通过即时识别测试等效类来跳过冗余执行，从而系统地探索搜索空间 w.r.t 给定的测试等价关系。

为了抽象化各种最佳的合成方法（用成本合成），我们假设有一个函数选择，对于给定的一组程序 P 和一个成本函数 κ，从 P 返回一个具有 κ 最小值的程序。

考虑算法 2 中描述的基准枚举补丁生成方法。该方法将补丁空间（定义 4.1），成本函数和测试套件作为输入，并输出通过所有根据指定顺序进行的给定测试的搜索空间元素序列 成本函数。首先，该算法初始化输出修复列表 R。 其次，通过（1）使用 pick 选择剩余的最佳候选者（2）来评估搜索空间的最佳（2）使用 eval 评估候选补丁，从而在搜索空间中进行迭代。最后，它输出找到的合理补丁 R 的列表。

我们的方法的总体工作流程在算法 3 中进行了描述。我们的算法将补丁空间，成本函数，与测试等价关系作为输入和输出结果的搜索空间元素的顺序，这些元素通过了根据成本函数排序的所有给定测试。与算法 2 相比，我们基于测试等价性的算法还为每个测试保留了 C 和 C 集.C（t）是一组测试等价类（因此，C 是一组程序集），其中所有候选人都通过 t; C（t）是失败的相应集合测试等价性类。首先，我们的算法初始化所有测试 t 的输出修复 R 列表以及通过和失败的测试等效类 C 和 C。第二，在搜索空间中进行迭代，方法是：（1）使用 pick 选择最佳（根据 κ 成本最低）的剩余候选者，以及（2）使用测试评估候选者并计算测试等价性类。

对于给定的候选者，为了识别测试执行的结果和相应的测试等效类，算法使用函数 eval 评估候选者。函数 eval 接受一个 program p，一个 test t，一个搜索空间 P 和一个测试等效关系~t，并返回执行 p 和 t（作为布尔值 isPassing）和一组程序[p]的结果，使得 eval 的具体实现取决于关系 t?，并分别在定义 4.3 和定义 4.4 中正式描述了关系 t~value 和 t~deps。

测试等效类用于搜索空间探索的两个步骤。首先，在选择下一个候选补丁之后，该算法检查该候选者是否属于任何现有的失败类（第 6 行）。 如果该候选补丁至少通过了一次不通过的测试，则该候选补丁的评估将被忽略。其次，在选择下一个测试以评估候选者之后，算法会检查该候选者是否在给定测试的通过类中（第 10 行）。如果某个测试者处于测验的及格类别中，则该算法将忽略该应试者在该测验中的执行。现在，我们专门针对我们研究的两种测试等价性讨论函数评估：基于值的测试等价性和基于依赖项的测试等价性。

定义 4.3（基于值的测试等价性分析）。 设 P 为搜索空间，p∈P 为程序，t =（σin，?）为检验。 令 e 是 p 中的一个表达式，使 ?p∈P?e∈Expr。 p = p [e / e]。 然后，基于值的测试等价性分析评估定义如下：

在此分析中，我们确定了一个程序的测试等价类，在 P 的程序内唯一不相同的程序中，其表达式为 e。通过将所有“替代”表达式 E 的集合作为 ? value 的参数来计算测试等价类。 请注意，在此定义中，我们明确选择了表达式 e，并分析其替换以进行测试等价性。 对于由图 10 中的变换函数 M 产生的搜索空间的每个元素，总是最多有一个这样的 e。 现在，我们讨论基于依赖关系的测试等价性的功能评估。

定义 4.4（基于依赖性的测试等价性分析）。 设 P 为搜索空间，p∈P 为程序，t =（σin，?）为测试。 设 p 为程序，l1 为使得 p = p [l1 / v：= e; l1]且] p∈P 的位置。 ?l2∈p。 p = p [l2 / v：= e; l2]。 然后，基于依赖性的测试等价性分析评估为：

，其中

在此分析中，我们确定了一个程序的测试等价类，该程序的等价性为 v：= e，该程序在 P 中的空间分配方案中仅分配不同的位置。通过将所有“替代”位置 L 的集合作为'deps'的参数来计算该测试等价类。

最后，请注意，算法 3 可以以不同的方式使用。该算法的输出是根据函数 κ 排序的合理补丁 R 的序列。一系列维修可以用于为开发人员提供一些补丁建议。可以通过引入限制并在找到所需数量的合理补丁后从主循环中断开来控制建议的维修次数。某些应用程序可能需要生成所有可能的补丁（例如，以便通过测试生成来缩小候选对象的范围）。 在这种情况下，可以修改算法，以便输出整个测试通过分区而不是单个补丁。

5. 实现

我们已经在 C 语言的称为 f1x 的工具中实现了上述方法。

分析。 我们对提出的测试等价性分析的实现是基于静态（源代码）和动态工具的组合。 具体来说，要在第 3.3 节中为关系 t~value 实现增强的语义，我们将转换模式 M（图 10）应用于错误程序的源代码，并用对实现值投影运算符的过程的调用替换“漏洞”。为了在 t~eps 的关系中实现 3.4 节中的语义增强，我们使用 Pin 实现了一种动态工具，该工具可跟踪分配合成中涉及的变量的读写。

搜索空间。 这项工作的目的是设计和评估用于转换的现有程序修复系统的测试等价关系。我们的系统结合了 SPR / Prophet 和 Angelix 的转换方案（我们研究了这些系统的实现，以便紧密地再现它们的搜索空间），如下所述。

表达式：修改现有的无副作用的整数表达式或条件（从 Angelix 采纳）。 图 10 是 C 程序的 MEXPRESSION 的变体。 根据表达式值，使用 t~value 将其分为等价类。

补充：在现有条件上附加分词/合词（取自 Prophet）。图 10 中 C 语言程序的 MREFINEMENT 的变体。基于条件值，使用 t~value 将其分为检验等价类。

守卫：为现有语句（从 Angelix 和 Prophet 使用）添加一个 if-guard。图 10 中 C 语言程序的 MGUARD 变量。基于条件值，使用 t~value 将其分为检验等价类。

声明：插入声明语句（从 Prophet 中使用）。 图 10 中针对 C 程序的 MASSIGNMENT 的变体。使用 t?划分为测试等价类。

初始化：插入内存初始化（从 Prophet 中使用）。 不分区。

功能：将功能调用替换为另一个功能（从 Prophet 中使用）。 不分区。

由于 Prophet 采用的最后两个转换方案不会生成较小的搜索空间，因此我们的算法未对其进行分区。我们的转换在以下方面与 SPR / Prophetin 的转换不同：（1）Prophet 实现了一种转换方案，用于插入受保护的 return 语句。尽管我们的算法可以使用关系 t~value 对这些变换进行划分，但是这些变换经常会产生过拟合补丁，因此我们将它们排除在搜索空间之外； （2）Prophet 实现了复制现有程序语句的转换。由于此类语句可以任意复杂，并且不能由我们的算法进行分区，因此我们不包括此转换。

成本函数。 已经提出了几种技术来通过优先考虑补丁来增加产生正确修复的可能性。 对于我们的系统，我们实现了一种为较小的更改声明语句的较高优先级的方法：

其中 p 是补丁程序（搜索空间的元素），porig 是原始程序，而 distance 定义为已添加，已修改和已删除 AST 节点的数量。

6. 实验评估

我们根据以下研究问题评估我们的方法：

（RQ1）与最先进的程序修复系统相比，我们的方法的有效性和效率是什么？

（RQ2）与最新系统相比，我们的方法是否可扩展到更大的搜索空间？ 测试等效关系是否可以实现我们的实现方式更高的可扩展性？

（RQ3）每个测试等效关系对我们的算法执行的测试执行数量有何影响？

6.1 评估设置

我们的评估将 f1x 与三种修复方法进行比较：Angelix，Prophet 和 GenProg-AE。 选择这些修复技术是因为它们使用了不同的修复算法，包括符号分析（Angelix），机器学习（Prophet）和遗传算法（GenProg）。我们采用 GenProg ICSE 12 基准评估所有维修方法，以进行评估，因为它包括来自大型现实项目的缺陷，并且旨在对程序维修工具进行系统性评估。此外，该基准测试套件被独立增强，以防止修复工具生成难以置信的补丁。基准测试由八个程序（即 libtiff，lighttpd，PHP，gmp，gzip，python，wireshark 和 fbc）的 105 个缺陷组成，这些缺陷具有开发人员编写的测试套件。表 1 显示了每个评估对象的统计数据。“执行成本”列表示针对给定主题执行测试套件所花费的时间。

我们选择了以下系统及其配置进行评估：

F1X f1x，通过算法 3 中所述的测试等价性划分实现搜索。

F1XE f1xE 是 f1x 的一种变体，它枚举了没有测试等效分区的更改（算法 2）。它被认为是评估分区的实现独立效果。

ANG Angelix 1.1 实现了符号路径探索，并在语法上优先考虑了较小的更改。

PR Prophet 0.1 实现了基于机器学习的条件表达式和补丁优先级的值搜索（路径探索的一种变体）。

PR * Prophet*是 Prophet 的变体，它禁止（1）插入过拟合的返回插入语句的转换和（2）复制除赋值以外的复杂语句。该变体被认为与 F1X / F1XE 中实现的转换匹配，因为 F1X / F1XE 的搜索空间实际上是 PR 和 ANG 的搜索空间的组合。

GP GenProg-AE3.0 实现了一组分析技术，旨在评估功能上相同的补丁（与我们的方法中的测试等效）相反。与使用固有遗传算法的 GenProg 早期版本相比，GenProg-AE 利用了确定性修复算法。

我们以两种模式运行所有配置（F1X，F1XE，ANG，PR，PR ，GP）：

Stop-after-first-found：该算法在找到第一个补丁后终止。此模式代表通常的程序修复使用情况。

Full exploration：算法将在整个搜索空间中搜索后终止。此模式使我们能够获取独立于（1）探索顺序和（2）搜索空间中是否存在合理补丁的数据。

我们重复使用先前研究中的配置来运行 Angelix，Prophet 和 GenProgAE。由于 Prophet 采用正确性模型作为输入变量，在提供的模型中使用了公开可用的替代模型。

我们在运行 Ubuntu 14.04 的 Intel?XeonTM CPU E5-2660 计算机上进行了所有实验，并使用 10 个小时的超时时间来运行每个配置。

6.2 有效性和效率（RQ1）

表 2 总结了以 stop-after-first-found 模式执行的 F1X，F1XE，ANG，PR，PR 和 GP 的有效性结果。第二列至第七列表示每个修复方法生成的可能补丁的数量，而第八至第十三列表示与人类补丁在语法上等效的补丁数量。由于 Angelix 不支持 lighttpd，python 和 fbc，这些对象的相应单元格标记有“-”。 总体结果表明，与所有其他评估的修复方法相比，F1X 生成了最多数量的合理补丁。表 2 中的“与人等效”列显示，F1X 比 F1XE 产生了更多的类似测试人员手工添加的有效补丁，比 ANG 多出了六个，比 PR 多出了 1 个，比 PR 多出了二个，并且比 GP 多出 13 个。

图 11 说明了配置的平均补丁生成时间。 图 11 的 x 轴表示基准测试中的八个对象，而它们的轴表示为给定对象的所有缺陷生成补丁所需的平均时间，其中每个条形图均表示补丁生成方法。总体而言，F1X 的平均补丁生成时间明显短于所有其他修复方法。例如，F1X 平均仅需要 121 秒即可生成 libtiff 补丁，而 ANG 则需要 1,262 秒（F1X 比 ANG 快 1262 121 = 10.5 倍）。 同时，PR *平均需要 1,701 秒才能生成 libtiff 的补丁（F1X 比 PR *快 1701 121 = 14×）;值得注意的是，F1X 比 libtiff 的 GP 快 16×（GP 平均需要 1,940 秒 libtiff 补丁）。 与 PR 相比，PR 的平均补丁生成时间略长，因为它搜索的补丁空间稍大。

结果如图 11 所示，F1X 和 F1XE 的平均出现时间比 F1XE 的平均时间短。 但是，仅考虑 F1X 和 F1XE 两者都发现的补丁时，F1X 始终表现出更好的性能，如图 12 所示。

6.3 探索速度（RQ2）

定义 6.1（探索的候选补丁）。我们说，如果算法识别出补丁是否通过了所有给定的测试或至少通过了一项失败，则将探索候选补丁。注意，我们仅考虑候选补丁程序，其中所有给定的失败测试都在其中执行了源代码修改。

表 3 显示了 F1X，F1XE，PR，PR 和 GP 的探索统计量（由于对 Angelixi 的搜索空间已通过逻辑约束进行搜索，因此排除了 ANG）。第二至第六列描述了 stop-after-first-found 模式的数据，而第七列至第十一列则代表了完整探索模式的数据。第二列至第十一列中的每个单元格的格式为 XY = Z，其中 X 表示通过修复方法“已探究的候选补丁”的平均数量，Y 表示通过修复方法执行的平均测试执行次数，Z 表示探索的速度 （由“已探究的候选补丁”数量与测试执行次数之比计算得出）。 在固定缺陷之间计算先找到后停止的平均值，而在所有缺陷之间计算完全探索模式的平均值。

通常，在 stop-after-first-found 模式和 full exploration 模式下，F1X 的探索速度都比所有其他补丁生成方法高一个数量级。例如，在完全探索模式下，F1X 平均只需要执行 620 次测试来探索 689,925 个 Wireshark 候选对象。对于同一程序，PR 要求进行 13,099 次测试执行以探索 23,043 个候选补丁，PR 要求进行 17,442 次测试执行以探索 18,554 个候选补丁，GP 要求进行 2,213 次测试执行以探寻 2,008 个候选补丁。通过比较 full exploration 模式下发现的平均数量的修补程序，也可以直接显示出探索的效率。为此，我们比较了 F1X 和 PR 的结果，因为这些配置发现了最多的补丁程序。 F1X 平均生成 2265 个合理补丁，而 PR 平均仅生成 9 个合理补丁。

为了生成更多补丁，理想的修复方法应通过在时间预算内探索更多候选者来扩展到更大的空间。 表 3 中的数据表明 F1X 可以扩展到更大的搜索空间，因为它在有限的测试执行次数限制下探索了更多的候选对象。与表 2 和图 11 中所示的其他工具相比，它解释了 F1X 的有效性和效率。回想一下 F1X E 是 F1X 的一种变体，没有测试等价性。 对于相同的搜索空间，由于需要更多的测试执行，因此 F1XE 在限定的时间内搜索的候选对象少于 F1X。 从这个观察中，我们得出结论，测试等效分区是 F1X 更高的可伸缩性的原因。

6.4 等效关系的影响（RQ3）

为了研究每个等效关系对测试执行次数的影响，我们对 Libtiff 的所有 24 个缺陷进行了另一项实验。我们选择了 Libtiff，由于其源代码的结构，Libtiff 主题在搜索空间中的候选补丁总数最大（9,618,864 = 400,786 24），平均每个表有 3 个版本，每个版本有 400 个（可查询的版本为 24）。 我们的目标是确定是否存在单个等价关系占主导地位的数量减少测试执行或这些关系的组合是否会导致更大的减少。

表 4 列出了 F1X 中三个等效关系（t?value，t~value 和 t??）对 Libtiff 的平均测试执行次数的影响。 对于图 10 中的每个转换，该表演示了应用转换的位置数（“位置”列），应用于此转换所产生的搜索空间的测试等效关系（“关系”列） ，生成的不同候选补丁的数量（“候选补丁”列），为失败的测试确定的分区数量（“分区”列），以及使用以下选项探索所有相应候选对象所需的测试数量： 整个测试套件（“测试执行”列）。

这些结果表明，对于 MEXPRESSION，MREFINEMENT 和 MGUARD 转换，我们的算法为失败的测试生成了少量的测试等效类（平均每个分区中有 500- 1,000 个元素），这也导致了少量的执行。整个测试套件对于关系 MASSIGNMENT，减少幅度不大； 但是，关系 t~的组合比单独关系 t?value，t?deps 的效率要高得多（测试执行的次数要少得多）。