php怎么表现奇数技巧_​自动生成补丁的测试等价性分析

引用：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.

程序自动修复是一个问题，即探求给定缺点程序的转换形式（称为补丁），以肃清可不雅观察到的故障。
它具有主要的运用，例如供应调试帮助，自动为学生作业评分以及修补安全漏洞。
现有修复技能面临的一个共同寻衅是对大补丁空间的可伸缩性，由于这些技能明确或隐含考虑了许多候选补丁。

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

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

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

每个开拓职员都知道，调试非常困难并且非常耗时。
由于自动验证和调试技能的进展缓慢，创造和肃清毛病仍旧紧张通过手动完成。
自动补丁天生方法可以潜在地缓解此问题，由于它们能够办理现实程序中的毛病，并且仅须要最少的开拓职员参与。
详细来说，它们已成功运用于供应调试提示，自动为作业评分和修补安全漏洞。
但是，巨大的搜索空间问题对当前的程序修复技能提出了严厉的寻衅。

程序修复的目的是修正给定的缺点程序，以肃清可不雅观察到的故障。
详细来说，测试驱动程序修复的目标是修正缺点的程序，使其通过所有给定的测试。
测试常日由开拓职员供应，但是当有正式规范时，也可以在反例辅导的优化循环中自动天生测试。
通过所有给定测试的补丁（程序修正）在程序修复过程中被认为是合理的。
由于测试套件的规格不完全，因此可能存在补丁与用户的意图不符而只是过分贴合测试本身。
为理解决这个问题，最新的技能在候选补丁的空间上定义了本钱函数（优先级），并搜索优化该功能的补丁。
例如，可以基于句法间隔，语义间隔和从人类补丁中学习的信息来确定变动的优先级。

补丁天生系统须要考虑可能的较大空间的修正，以办理多种毛病。
程序修复的紧张寻衅之一是可扩展到大型搜索空间。
当前的技能可能须要大量的韶光来天生补丁，但是它们只考虑并天生相对大略的程序转换。
这会影响程序修复产生类似于人的修复的能力，由于人的补丁程序常日涉及繁芜的源代码修正。
除此之外，最近的一项研究表明，通过增加更多的转换来扩展搜索空间可能会导致修复系统由于搜索韶光的增加而创造较少的精确修复。

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

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

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

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

贡献。
这项事情的紧张贡献如下：

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

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.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 的序列。
一系列维修可以用于为开拓职员供应一些补丁建议。
可以通过引入限定并在找到所需数量的合理补丁后从主循环中断开来掌握建议的维修次数。
某些运用程序可能须要天生所有可能的补丁（例如，以便通过测试天生来缩小候选工具的范围）。
在这种情形下，可以修正算法，以便输出全体测试通过分区而不是单个补丁。

我们已经在 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 节点的数量。

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

（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 的效率要高得多（测试实行的次数要少得多）。