TransplantFix: Graph Differencing-based Code Transplantation for Automated Program Repair

基本信息

博客贡献人

JokerLin

作者

Deheng Yang, Xiaoguang Mao, Liqian Chen, Xuezheng Xu, Yan Lei, David Lo, Jiayu He

标签

Automated program repair, graph differencing, code transplantation

摘要

自动程序修复 (APR) 有望帮助手动调试活动。经过十多年的发展，人们提出了广泛的 APR 技术，并在一组真实的错误数据集上进行了评估。然而，尽管越来越多的错误得到了正确修复，但我们观察到，近年来通过 APR 技术修复的新错误的增长已经遇到了瓶颈。在这项工作中，我们提出 TransplantFix 来探索解决复杂错误的可能性，TransplantFix 是一种新颖的 APR 技术，利用捐赠者方法中基于图差异的移植。 TransplantFix 的主要新颖之处在于三个方面：1）我们建议使用基于图的差分算法从捐赠者方法中提取语义修复动作； 2）我们设计了一种继承层次结构感知的代码搜索方法来识别具有类似功能的捐赠者方法； 3）我们提出了一种命名空间转移方法来有效地适应捐赠者代码。 我们通过广泛比较（涵盖总共 42 种 APR 技术）并针对 Defects4J v1.2 和 v2.0 中的 839 个真实错误评估 TransplantFix，研究了 TransplantFix 的独特贡献。 TransplantFix 在三个方面呈现出优异的效果。首先，与过去三年提出的最先进的 APR 技术相比，它在新修复的错误数量方面取得了最佳性能，达到了 60%-300% 的改进。此外，不依赖于任何修复操作或从大数据中学习的修复操作，它在 Defects4J v1.2 和 v2.0 上评估的所有 APR 技术中达到了最佳的通用性。此外，它还显示了合成复杂补丁的潜力，其中最多包含八行插入。 TransplantFix 为后续研究解决更复杂的错误提供了新的见解和有前途的途径。

简介

自动程序修复（简称APR）旨在无需人工干预即可修复错误，被认为是减轻手动调试活动沉重负担的一项有前途的技术。在 APR 社区中，修复成分是一个常用的概念，它最初表示合成补丁所需的代码片段（又名捐赠者代码）。近年来，修复操作（在抽象级别对修改源代码的指令进行编码）也被列为修复成分的一种类型。在过去的十年中，人们提出了广泛的 APR 技术，以更好地利用修复操作和捐赠者代码。这些技术在现实世界的错误数据集 中取得了有希望的结果，甚至应用于工业管道 。

虽然现有 APR 技术已修复了越来越多的现实世界错误，但我们通过文献综述观察到，通过 APR 技术新修复的错误的增长正在遇到瓶颈。图 1 显示了常用评估数据集（即 Defects4J v1.2 1）上新修复错误的趋势。如图所示，从2016年到2019年，新修复的 Bug 数量经历了快速增长。但是，自2020年以来，增长变得更加缓慢（例如，2022年仅修复了两个新Bug）。正如之前的研究 所报道的那样，APR 技术仍未修复的错误往往在多个方面都“复杂”，例如，涉及多个插入行（即捐赠者代码） 或受更改操作影响的多个语句（即修复操作）。

我们从修复成分的角度总结了阻碍自动程序修复（APR）技术修复更多新错误的三个挑战：1）修复成分的定位；2）修复动作的提取；3）捐赠者代码的适配。第一个挑战是我们在哪里可以找到用于补丁合成的复杂修复成分。对于捐赠者代码，现有的 APR 技术已经探索了一系列设置，包括在 buggy 文件 、 buggy 项目甚至外部项目中搜索捐赠者代码。在修复操作方面，现有的APR技术通常假设用于修复错误的修复操作驻留在现实世界中人工编写的外部项目的错误修复中，可以手动挖掘或自动学习。虽然修复成分被发现可以修复许多单行或单块错误，但在哪里可以找到修复成分以修复更大的错误仍然是一个悬而未决的问题。

第二个挑战是如何提炼复杂的修复操作。 现有的 APR 技术通过多种方法（例如，手动总结 、统计分析 或学习模型 ）提取修复操作。这些方法的关键思想是识别最常见的修复操作。然而，随着代码更改大小的增长，修复更改的重复性呈指数下降，复杂的修复更改的排名会下降，因此被选为修复操作的概率较低。因此，如此复杂的变化很难设计或学习。例如，图 2 显示了 Defects4J 中名为 Chart-6 的典型错误，该错误无法通过现有 APR 技术修复。Chart-6 的修复操作包括多次插入不同的控制结构，包括赋值、分支、循环和返回语句。现有 APR 技术仍然无法实现此类操作。

第三个挑战是如何适应复杂的捐赠者代码。 现有的 APR 技术提出了几种将捐赠者代码转移到有缺陷的位置的方法。 GenProg 直接将代码从有错误的程序中的一个位置传输到有错误的位置，而不解决潜在的命名空间冲突。随后的 APR 技术（例如 SimFix 、SOSRepair 、ssFix ）通过提出变量重命名方法来适应捐赠者代码片段，取得了重大进展。但是，当捐赠者代码包含除变量之外的更多实体（例如，用户定义的数据类型）时，可能需要更全面的捐赠者代码传输方法。例如，如图 2 所示，修复此类错误通常需要一组新的代码片段。除了多个变量之外，Chart-6 补丁还包含原始数据类型和用户定义的数据类型，甚至还包含来自不同类的方法调用。此外，这些捐赠者代码的组合在一个块上跨越多达八行插入。

在本文中，我们提出了一种新颖的基于图差分的代码移植方法来帮助解决这三个挑战。 Barr等人提出了代码移植的概念，旨在将代码从捐赠者位置转移到宿主位置。作为一种有前途的重用代码方法，代码移植开辟了自动程序修复的途径。具体来说，在本文中，我们选择在有缺陷的项目中的方法级别搜索修复成分，并提出一种继承层次感知代码搜索方法，利用继承关系有效地定位修复成分（第一个挑战）。然后通过属性控制流图表示方法，并将修复操作提取重新表述为图形编辑计算问题。 我们进一步建议使用图差分方法来提取语义修复操作（第二个挑战）。由于不同的变量、类型和方法，驻留在捐赠者方法中的捐赠者代码不能直接应用于宿主，我们提出了一种新颖的命名空间传输方法，以有效地将捐赠者代码适应有缺陷的方法（第三个挑战）。

总之，这项工作的主要贡献包括：

(1) 一种继承层次结构感知的方法级捐赠者搜索方法，它捕获方法的局部特征（即方法签名）和全局特征（即继承关系），以有效地在有缺陷的项目中定位捐赠者方法。

(2) 一种基于图差分的方法来提取语义修复操作。我们将修复操作提取重新表述为图编辑距离计算问题，并从 buggy 和捐赠者方法之间的编辑图中提取修复操作。

(3) 一种全面的命名空间构建方法，不仅考虑变量的传输，还考虑数据类型和方法的传输，从而实现更大的捐赠者代码适配。

(4) TransplantFix 通过正确修复之前 APR 技术从未修复过的 8 个新错误，带来了新的动力，帮助突破新修复错误增长的瓶颈。与过去三年提出的最先进的 APR 技术相比，这是最好的性能。 在 Defects4J v1.2 和 v2.0 上评估的所有 APR 技术中，TransplantFix 也显示出了最佳的通用性。此外，TransplantFix 被发现能够合成最多由八行插入组成的正确补丁（例如，Chart-6）。

为了便于后续研究，在 https://github.com/DehengYang/TransplantFix 上公开提供原型和所有相关工件。

动机

在本节中，我们将介绍一个真实世界的错误示例，该示例激发了我们的方法。图 3 列出了 Chart-6 中的错误方法，该方法无法通过现有最先进的 APR 技术修复。 通过仔细研究整个 Chart-6 错误程序，我们获得了解决第一个挑战的见解（即可以在哪里获得此类修复操作和捐赠者代码）。我们观察到一种捐赠者方法可能会为 Chart-6 提供修复成分的两个来源（即修复操作和捐赠者代码）。如图 4 所示，PaintList 类中的捐赠者方法 equals() 与 Chart-6 的有问题的方法共享相同的方法名称。捐赠者方法没有像 buggy 方法那样调用 super.equals(obj)（参见图 3 中的第 111 行），而是有自己的实现用于比较（参见图 4 中的第 98-107 行）。捐赠者方法中的此类实现在功能上类似于 Chart-6 的人工编写补丁中的实现，如图 2 所示。有趣的是，有缺陷的类（即 ShapeList）和捐赠者类（即 PaintList）都继承相同的父类（即 AbstractObjectList）。这指出了通过在有缺陷的项目中正确搜索捐赠者方法来获取复杂修复成分（例如图 Chart-6）的新途径。

针对这个问题，我们设计了一种继承层次感知方法搜索方法。考虑到 Chart-6 的 buggy 方法和捐赠者方法在标识符、控制结构和补丁大小方面存在显着差异，我们选择使用方法签名来衡量两种方法之间的相似性。然而，当方法签名在项目中非常常见时（例如 equals() ），候选捐赠者方法可能具有相同的相似性分数，这对于捐赠者方法排名来说是不希望的。为了打破这种联系，我们通过优先考虑位于有缺陷方法的同一继承图中的捐赠者方法来进一步利用继承关系（第 3.2 节）。 通过这种方式，我们的方法准确地将捐赠者方法排名在 Top-1 位置。

为了解决第二个挑战（即如何获得复杂的修复操作），我们建议执行图差异来提取 buggy 和捐赠者方法之间的语义差异。我们首先将该方法表示为控制流图，然后基于精确图编辑距离算法设计图差分算法来推断所有可能的修复操作。在这个例子中，我们的算法通过区分从 buggy 和捐赠者方法构建的控制流图来获得编辑图。 如图 5 所示，编辑图指定了 buggy 和捐赠者方法之间的语义修复操作，其中包含修复操作的搜索空间。该搜索空间包括修复 Chart-6 所需的修复操作（即用捐赠者方法中第 98-107 行的语句更新有缺陷方法中第 111 行的语句）。

即使获得了修复操作，使捐赠者代码适应有缺陷的方法仍然具有挑战性（第三个挑战）。 如图 4 所示，数据类型（例如 PaintList）和方法调用（例如 PaintUtilities.equal()）与有缺陷的方法不兼容。这种自适应超出了 APR 技术中使用的现有代码自适应方法的范围 。为了解决第三个挑战，我们设计了一种名称空间传输方法，它不仅可以处理变量，还可以处理类型和方法。这使我们能够成功推断出 ShapeUtilities.equal() 不存在于有缺陷的文件中，但实际上与有缺陷的文件兼容。正确传输捐赠者代码后，我们可以将提取的语义修复操作和传输的捐赠者代码应用于有缺陷的方法，以生成针对 Chart-6 的正确修复。

方法

方法概述

图 6 描述了 TransplantFix 的整体工作流程。 TransplantFix 建立在典型的自动化程序修复流程之上，该流程由三个阶段组成：1) 故障定位； 2）补丁生成； 3) 补丁验证。对于故障定位，TransplantFix 将有缺陷的程序及其相关的测试套件作为输入，并按照可疑方法的可疑值降序生成可疑方法的排名列表。然后将该列表输入补丁生成阶段以生成候选补丁。作为TransplantFix的核心阶段，补丁生成阶段由三个阶段组成：1）修复成分搜索； 2）捐赠者代码转移； 3）修复动作提取。对于每个可疑方法，固定成分搜索阶段都会测量其与项目内所有方法的相似性，然后根据相似性进行排名。 对于每个捐赠者方法，捐赠者代码传输阶段将捐赠者方法中的实体转换为与可疑方法兼容的实体。之后修复操作提取阶段表示具有属性控制流图的方法，并通过区分传输的捐赠者图和可疑图来生成编辑图。基于编辑图，它提取语义修复动作来构建搜索空间。它使用具体的捐赠代码在搜索空间中对可疑方法应用修复操作，以生成候选补丁列表。在最后阶段，补丁生成器使用有缺陷程序的原始测试套件对候选补丁进行验证。如果未找到通过测试套件的有效补丁，TransplantFix将返回补丁生成阶段，对下一个可疑方法进行处理。否则，TransplantFix将退出并输出有效补丁。

修复成分搜索

修复成分搜索旨在将包含用于修复错误的修复成分的捐赠者方法与其他方法区分开来。为此，它利用局部特征（即方法签名）和全局特征（即继承关系）来测量可疑方法和每个候选捐赠者方法之间的功能相似性。首先，我们提出与方法的局部和全局特征相关的定义如下。

定义 1（方法签名）。给定一个方法 $m$，方法签名是一对：$⟨MethName,ArgTypeList⟩$。第一个元素是方法名称，第二个元素是方法的参数类型列表，即 $[ArgTyp{e}_1,ArgTyp{e}_2,...,ArgTyp{e}_n]$。

根据 Java 语言规范（简称 JLS）定义方法签名。 JLS 指定如果两个方法具有相同的方法名称和参数类型，则认为它们具有相同的签名，而不管返回类型和参数名称如何。因此，定义 1 通过方法名称和参数类型列表来表征方法签名。

定义 2（继承 DAG）。继承DAG $I$ 是表示类之间的继承关系的有向无环图（简称 DAG）。$I$ 中的每个顶点表示一个类，从 $verte{x}_i$ 到 $verte{x}_j$ 的边表示 $clas{s}_i$ 继承自 $clas{s}_j$ 。

继承是面向对象编程的一个重要特性，它是一种使一个类能够继承另一个类的字段和方法的机制。另据报道，在所调查的现实世界 Java 应用程序中，至少有一半的用户定义类使用了继承 。由于Java中一个类最多可以扩展一个超类，但可以实现多个接口，因此我们采用图结构（即定义2所示的继承DAG）而不是树结构来表示继承关系。这也被之前的遗传相关研究所采用。我们使用 IDAGs 来表示继承 DAGs 的集合。

定义 3（相对类）。$clas{s}_i$ 是 $class$ 的相对类当且仅当 $\exists I\in IDAGs,clas{s}_i\in I.vertices\wedge classj\in I.vertices$。

我们提出”相对类”的概念来描述同一继承 DAG 中两个类的关系。相关类捕获了方法的全局特征，因此可以帮助进一步确定捐赠者方法的优先级。例如，捐赠者类 PaintList 是 Chart-6 中有缺陷的类 ShapeList 的相关类，并且在测量相似度时，捐赠者方法将获得更高的分数。

给定两个方法 $m$（来自有缺陷的代码）和 $m^{\prime }$（来自捐赠者代码），我们根据局部特征（即方法签名）来测量它们的相似性，如下所示：
$$Si{m}_{local}(m,m^{\prime })={\lambda }_1\ast \text{jacc}(\text{MethName}(m),\text{MethName}(m^{\prime }))+{\lambda }_2\ast \text{jacc}(\text{ArgTypeList}(m),\text{ArgTypeList}(m^{\prime }))\text{\hspace{1em}(1)}$$
如式（1）所示，我们包括方法签名的两个元素（即方法名称和参数类型列表），并采用 Jaccard 相似系数分别计算两个局部特征的相似度。由于Java中的命名约定通常遵循 CamelCase，因此我们将方法名称拆分为子标记，然后将两个方法的子标记集输入到 jacc() 中。我们对参数类型执行相同的拆分操作。 ${\lambda }_1$ 和 ${\lambda }_2$ 分别表示分配给方法名称和参数类型列表的相似度得分的权重。

我们测量全局特征（即继承关系）的相似度如下：
$$Si{m}_{global}(m,m^{\prime })=\{\begin{array}{ll}1& \text{if }\text{relative}(\text{cls}(m),\text{cls}(m^{\prime }))\\ {\mu }_1\ast \text{jacc}(\text{PkgName}(m),\text{PkgName}(m^{\prime }))+{\mu }_2\ast \text{jacc}(\text{ClsName}(m),\text{ClsName}(m^{\prime }))& \text{otherwise}\end{array}\text{\hspace{1em}(2)}$$
在等式（2）中，当两个比较方法的类是相对类（即 $relative(cls(m),cls(m^{\prime }))$）时，我们将相似度得分指定为1。对于 buggy 类没有相关类的情况，我们进一步考虑两个元素之间的相似性，即 PkgName 作为包名，ClsName 作为类名。对于这两个元素，我们使用相同的相似性度量（即 Jaccard）和分割操作来获得相似性得分。 同样，${\mu }_1$ 和 ${\mu }_2$ 分别表示分配给包名称和类名称的相似度分数的权重。

最后，我们通过计算它们的平均值来合并 $Si{m}_{local}$ 和 $Si{m}_{global}$，以获得两种方法之间的总体相似度得分。 通过这种方式，我们同时考虑局部特征和全局特征来对候选捐赠者方法进行排名。请注意，相似性度量方程中有四个权重参数。由于目前还没有研究如何分配每个权重的精确值，因此在这项工作中，我们直接将所有参数（即 ${\lambda }_1$ 、${\lambda }_2$、${\mu }_1$ 和 ${\mu }_2$ ）分配为 0.5。我们最终获得了前 50 个候选捐赠者方法的排名列表，按照与可疑方法的整体相似度得分降序排列。

捐赠者方法转移

捐赠者方法转移旨在将捐赠者命名空间与可疑命名空间对齐。它首先通过在每个方法中收集三种类型的程序实体，为可疑方法和候选捐赠者方法构建命名空间。然后创建实体映射，这些映射编码了候选捐赠者方法中的实体应如何调整以适应可疑方法。

命名空间构建

在转移候选捐赠者方法的命名空间之前，必须为可疑方法和候选捐赠者方法构建命名空间。对于一个方法来说，命名空间构造涵盖了以下三种程序实体：

(1) 类型：我们考虑两种类型。第一个是方法中使用的所有类型，用作“本地类型”。第二个是该方法所属的相应可疑类类型（例如，可疑方法 equals() 的 ShapeList，如图 3 所示），充当“全局类型”。

(2)方法调用：我们收集方法中调用的所有方法调用。 为了便于比较两个方法调用，我们识别并收集其局部特征（即方法签名）以及全局特征（即继承关系）。

(3) 变量：除了收集方法中定义或使用的每个变量外，我们还通过跟踪其声明来进一步收集其类型。

命名空间对齐

获得两个命名空间后，我们进一步构建涵盖类型、方法调用和变量的命名空间映射。由于命名空间中的变量和方法调用都与类型信息相关，因此我们优先构建类型映射，以方便其他实体的映射。

类型映射 我们首先为“全局类型”构建映射。 给定可疑方法全局类型的 $type$ 和另一个候选捐赠者方法的 $typ{e}^{\prime }$，我们根据 CamelCase 命名约定将 $type$ 拆分为子标记列表，即 $list=[t{k}_1,t{k}_2,...,t{k}_m]$。同样，我们将 $typ{e}^{\prime }$ 拆分为 $lis{t}^{\prime }=[t{k}_1^{{}^{\prime }},t{k}_2^{{}^{\prime }},...,t{k}_n^{{}^{\prime }}]$。 然后我们计算两个列表之间的最长公共子序列（LCS）。最后，我们构建一个函数 $f_1\subset (S^{{}^{\prime }}\cup concat(S_{sub}^{{}^{\prime }}))\times (S\cup concat(S_{sub}))$，其中 $S=list$，$S^{{}^{\prime }}=lis{t}^{{}^{\prime }}$，$S_{sub}$ （和 $S_{sub}^{{}^{\prime }}$ ）表示 $S$（和 $S^{{}^{\prime }}$）的子集集合，将 $lis{t}^{{}^{\prime }}$ 中的子标记或子标记串联映射到 $list$ 中。设 $t{k}_i^{{}^{\prime }},t{k}_{i+k}^{{}^{\prime }}$ 为两个列表的 LCS 中的两个相邻元素。我们定义 $f_1(t{k}_i^{{}^{\prime }})=t{k}_j$ 其中 $t{k}_j=t{k}_i^{{}^{\prime }}$, $f_1(t{k}_{i+k}^{{}^{\prime }})=t{k}_{j+r}$ 其中 $t{k}_{j+r}=t{k}_{i+k}^{{}^{\prime }}$, $f1(concat(t{k}_i^{{}^{\prime }},...,t{k}_{i+k}^{{}^{\prime }}))=concat(t{k}_j,...,t{k}_{j+r})$。以图 4 中 Chart-6 的捐赠者方法为例，PaintList 和 ShapeList 的 LCS 是 [List] ，PaintList 中的唯一子标记 Paint 映射到 ShapeList 中的唯一子标记 Shape。因此 $f_1(Paint)=Shape$。

基于全局类型映射 $f_1$，我们构建局部类型映射 $f_2$。对于候选捐赠者方法中的每个类型，如果它在 $dom(f_1)$ 中包含 $S$，我们用 $f_1(S)$ 替换该类型中的 $S$。否则，我们保持不变。例如，Chart-6 的捐赠者方法的本地类型映射为 $f_2(PaintList)=ShapeList$、$f_2(PaintUtilities)=ShapeUtilities$。

方法调用映射 我们用函数 $f_3\subseteq M^{\prime }\times M$ 定义方法调用映射，其中 $M^{\prime }=m_1^{\prime },m_2^{\prime },...,m_i^{\prime }$, $M=m_1,m_2,...,m_j$。 $M^{\prime }$ 和 $M$ 分别表示候选捐赠者方法和可疑方法中的方法调用集合。我们首先通过测量方法调用的相似性，将候选捐赠者方法的方法调用映射到可疑方法中的方法调用。我们使用 3.2 节中描述的相同测量来测量两个方法调用之间的相似性。当相似度大于阈值分数时，我们将这两个方法调用添加到映射中。本文将阈值设置为 0.6。 对于仍然没有映射的方法调用，我们根据全局类型映射进一步创建方法调用映射。与局部类型映射的构造类似，只有当方法调用中包含 $dom(f_1)$ 中的一个 $S$ 时，我们才将方法调用中的 S 替换为 $f_1(S)$。例如，Chart-6 的捐赠者方法的方法调用映射为 $f_3(getPaint)=getShape$。

变量映射 变量映射 $f_4$ 构建在类型映射之上。具体来说，对于候选捐赠者方法中的每个变量 $va{r}_i$ ，我们在可疑方法中包含一组符合以下约束的变量 $vars$ ： $\forall va{r}_j\in vars,type(va{r}_j)=type(va{r}_i)\vee type(va{r}_j)=f_2(type(va{r}_i))$，其中 $type(var)$ 表示变量的类型。我们进一步按照与 $va{r}_i$ 的编辑距离的升序对 $vars$ 中的变量进行排序。 例如，Chart-6 供体方法的变量映射为 f 4 ( o b j ) = { o b j } f_4(obj) = \{obj\} f4​(obj)={obj}。

修复动作提取

修复动作提取的目的是根据 3.3 节中候选捐赠者方法的转移命名空间，提取3.2节中获得的候选捐赠者方法与可疑方法之间的语义修复动作。具体来说，它由以下步骤组成：

图构建

正如第 1 节和第 2 节中所讨论的，当修复操作涉及复杂的控制结构时，现有的 APR 技术通常无法实现。因此，我们建议通过控制流图（简称CFG）来表示方法，因为CFG可以对方法中语句之间的控制依赖关系进行建模，并促进语义修复动作的提取。 我们采用 Soot （一种开源且维护良好的工具，已广泛用于各种程序分析）来获取每种方法的 CFG。烟灰也已用于先前的 APR 技术 。请注意，Soot 通过分析类的字节码来生成方法的 CFG，但我们的方法通过在源代码级别修改抽象语法树 (AST) 来生成候选补丁。因此，我们进一步将Soot产生的CFG转换为每个节点对应一个AST节点的CFG。在翻译后的 CFG 中，分支节点（例如 if 表达式）在表达式 AST 级别表示，其他节点在语句 AST 级别表示。然后将这些CFG（控制流图）输入到图差分算法中，以推断语义上的修复变化。

图差分

基于构建的 CFG，我们将修复更改提取重新表述为图编辑距离计算问题。我们给出相关定义如下：

定义 4（属性 CFG）。一个属性控制流图（CFG）是一个由四个元素组成的元组：$⟨V、E、\mu 、\xi ⟩$，其中 V 和 E 分别表示一组顶点（即 AST 节点）和边（即流转换）。 $\mu :V\to A_V$ 是将属性 $a_e$ 关联到顶点的函数，并且 $\xi :E\to A_E$ 是将属性 $a_e$ 关联到边的函数。

如定义 4 所示，在属性化 CFG 中，我们用顶点表示 AST 节点，用边表示控制流转移。就属性而言，我们将 CFG 中每个 AST 节点的格式化字符串作为顶点属性；并将控制流转移的标签（即分支控制流转移的 “true” 和 “false”，以及其他转移对应的空字符串）作为边属性。

定义 5：（图形编辑距离）。给定两个属性 CFG：$g:⟨V,E,\mu ,\xi ⟩,g^{\prime }=⟨V^{\prime },E^{\prime },{\mu }^{\prime },{\xi }^{\prime }⟩$，从 $g$ 到 $g^{\prime }$ 的图形编辑距离为：
$$\text{GED}(g,g^{\prime })=\underset{(e{o}_1,\dots ,e{o}_k)\in \phi (g,g^{\prime })}{\min }\sum _{i=1}^{k}c(e{o}_i)$$
其中 $e{o}_i$ 表示两个顶点或两条边之间的编辑操作，$c(e{o}_i)$ 表示编辑操作 $e{o}_i$ 的成本。 $(e{o}_1,...,e{o}_k)$ 表示编辑路径（即一系列编辑操作），而 $\phi (g,g^{\prime })$ 表示从 $g$ 到 $g^{\prime }$ 的所有可能的编辑路径。

图编辑距离（GED）是一种图差分方法，旨在以最小的成本从 $\phi (g,g^{\prime })$ 找到最佳编辑路径。如定义 5 所示，$e{o}_i$ 是对两个顶点或两条边的编辑操作，编辑操作有四种类型： 1）更新：$v\to v^{\prime }$表示用 $v^{\prime }$ 更新 $v$； 2）删除：$v\to \epsilon$ 表示删除 $v$； 3）插入：$\epsilon \to v^{\prime }$表示插入 $v^{\prime }$； 4）匹配：匹配操作是更新操作的特例，但其成本为零（即 $c(e{o}_i)=0$），表明 $v$ 和 $v^{\prime }$ 完全匹配。 边的编辑操作与顶点的编辑操作类型相同。

根据上述定义，我们将修复动作提取重新表述为图编辑距离计算问题。为了解决这个问题，我们采用了 DF-GED 算法，这是 Abu 等人提出的一种新颖的 GED 方法。 ，我们进一步设计成本函数来计算每对顶点和每对边的成本：
$$\text{Cost}(v,v^{\prime })=\{\begin{array}{ll}{\min }_{A_{v_j^{\prime }}\in A_{v^{\prime }}}\text{levensh}(A_v,A_{v_j^{\prime }})& \text{if }\text{typeMatched}(v,v^{\prime })\\ \text{maxCost}& \text{otherwise}\end{array}\text{\hspace{1em}(3)}$$
其中，$A_v$ 为 $g$ 中顶点 $v$ 的属性，$A_{v^{\prime }}$ 表示 $g^{\prime }$ 中顶点 $v^{\prime }$ 的属性。
$$\text{Cost}(e,e^{\prime })=\left(\text{levensh}(A_e,A_{e^{\prime }})+\text{Cost}(A_{v_e^{in}},A_{v_{e^{\prime }}^{in}})+\text{Cost}(A_{v_e^{out}},A_{v_{e^{\prime }}^{out}})\right)/3\text{\hspace{1em}(4)}$$
其中 $A_e$ 是边 $e$ 的属性。 $A_{v_e^{in}}$ 是 $e$ 的起始顶点的属性，$A_{v_e^{out}}$ 是 $e$ 的结束顶点的属性。

如方程（3）所示，如果两个顶点都是表达式或者都是语句（即 $typeMatched()$ ），我们计算 v 的字符串和 3.3 节中获得的 v ’ 的每个映射字符串的 Levenshtein 距离（即 $levensh()$ ）。我们将每个 Levenshtein 距离归一化到 [0,1] 范围内，并选择最小成本作为最终成本。否则，我们认为两个顶点不匹配，从而分配 maxCost。请注意，maxCost 应大于匹配节点的成本，在本工作中我们将其设置为 10。

两条边的成本计算建立在顶点的成本计算之上。如方程（4）所示，我们计算e和e’的标签之间的编辑距离的平均成本，两条边的起始顶点（即$A_{v_e^{in}},A_{v_{e^{\prime }}^{in}}$）之间的成本，以及两条边的结束顶点（即 $A_{v_e^{out}},A_{v_{e^{\prime }}^{out}}$）之间的成本。

搜索空间构建

请注意，第 3.4.2 节中的图形编辑距离算法最终输出最佳编辑路径（即一系列编辑操作 $(e{o}_1,...,e{o}_k)$），其中包含将 $g$ 转换为 $g^{\prime }$ 所需的所有编辑操作。然而，在自动化程序修复的背景下，有缺陷的方法可能只需要编辑操作的子集来修复错误，并且引入所有编辑操作可能会导致副作用或错误。另一方面，如果考虑最佳编辑路径中涉及的编辑操作集的所有子集，搜索空间可能会爆炸。例如图 5 所示，顶点有 12 次编辑操作（即 9 次插入、2 次更新和 1 次删除），对应于 212 = 4, 096 个候选补丁的搜索空间。当编辑操作超过 20 次时，搜索空间可能会增长到一百万个候选补丁。为了有效地塑造搜索空间，我们提出了 “切点” 的概念，并使用切点对对固定动作进行分组。分组后，每一组都可以视为一次“大”编辑操作。

定义 6（切点）。切点是对两个顶点的编辑操作：$e{o}^c=v\to v^{\prime }$，其中顶点 $v\in g$，顶点 $v^{\prime }\in g^{\prime }$，$e{o}^c$ 为更新或匹配类型。

如定义 6 所示，切点割点被定义为更新或编辑操作，其中两个顶点存在于两个图中。切点指示可疑方法中的一个顶点与候选捐赠者方法中的一个顶点之间的映射，并且可以进一步利用来对相关编辑操作进行分组。

算法 1 描述了我们如何对编辑操作进行分组并生成修复操作。我们首先通过对 $g_s$ 执行深度优先搜索来获取所有切点（第 5 行）。然后，我们利用一对切点，即 $(e{o}_i^c,e{o}_j^c)$，其中 $e{o}_i^c=v_i\to v_i^{\prime }$，$e{o}_j^c=v_j\to v_j^{\prime }$，将整个编辑路径切割成片段（第 6-14 行）。通过这种方式，我们可以描述位于 $e{o}_i^c$ 和 $e{o}_j^c$ 之间的一系列连续编辑操作。这些连续操作可以组合为一个大型相关修复操作（第 13 行）。在识别分割点对时，我们进一步引入一个编码语法规则的线序约束：$v_i.lineNo<v_j.lineNo\wedge v_i^{\prime }.lineNo<v_j^{\prime }.lineNo$，其中 $lineNo$ 表示相应顶点的行号。这要求可疑方法中 $e{o}_i^c$ 和 $e{o}_j^c$ 的两个顶点应该与候选捐赠者方法中的行号顺序相同（第 8-11 行）。为了生成修复操作（第 13 行），除了考虑编辑操作的完整序列而获得“大”修复操作之外，我们通过生成对序列进行单一编辑的修复动作来进一步丰富搜索空间。一旦从切点对中生成了所有修复动作，我们进一步考虑将位于同一 if 或循环控制结构中的“大”修复动作组合起来，形成依赖于分支的修复动作（第16行）。有了这些动作，我们就可以将它们与具体调整过的供体代码逐一应用于有缺陷的项目，以生成候选补丁列表。

评估

介绍

已经用大约 20.4 KLoc 的源代码实现了 Java 编程语言的 TransplantFix。除了第 3 节中描述的核心模块外，TransplantFix 还包括故障定位和补丁验证模块，以形成完整的修复管道。对于故障定位，我们利用现有 APR 工具中常用的 GZoltar API 和 Ochiai 相似系数 来实现方法级故障定位。对于补丁验证，我们首先在候选补丁上运行错误失败测试用例。如果所有失败的测试用例都通过，我们就会通过在补丁上执行所有积极的测试用例来运行回归测试。 对于通过测试套件的合理补丁，我们通过检查它们是否与人类编写的补丁相同或语义等效来手动评估这些补丁的正确性。我们将每次修复试验的时间预算设置为两个小时，遵循 APR 之前的做法。

数据集

我们测量了 TransplantFix 在 Defects4J v1.2 数据集上的有效性 ，并进一步评估了 TransplantFix 在 Defects4J v2.0 数据集上的通用性。 Defects4J v1.2 是一个广泛使用的现实世界 bug 数据集，其中评估了数十种 APR 工具 。它包含来自 6 个开源项目的 395 个 bug，即 jfreechart、commons-lang、commons-math、closurecompiler、joda-time 和 mockito，这些有缺陷的程序的大小从 22 到 96 KLoc 不等。

为了缓解 Durieux 等人报告的基准过度拟合问题。 我们采用Defects4J的扩展版本，即v2.0，来进一步测量TransplantFix，文献中也使用它来评估最先进的APR技术。 Defects4J v2.0 涵盖了 17 个真实世界的软件系统，包含 835 个真实世界的错误 ，其中与 v1.2 相比，包括 444 个新错误。为了避免对同一错误进行重复修复试验，我们对 Defects4J v2.0 中的 444 个新错误进行了 TransplantFix 评估。我们评估中的完整错误列表和修复数据也是公开的 。

TransplantFix 的有效性

在本节中，我们评估 TransplantFix 对 Defects4J v1.2 中的 395 个错误的有效性，并将其与现有的 APR 技术进行比较。

由于观察到补丁过度拟合问题 ，评估 APR 生成的补丁的正确性已成为文献中的共识。因此，正确修复的错误（简称 $N_{correct}$）的数量已被广泛评估，以显示 APR 技术的有效性 。近年来，首次正确修复的错误数量（$N_{unique}$）已成为越来越流行的衡量标准，以强调 APR 技术的独特贡献，并已被文献广泛采用。随着APR技术的数量不断增长，如何在第一时间正确修复更多的 Bug 对于 APR 社区来说是一个具有挑战性的任务。

在本文中，我们重点衡量 TransplantFix 的 $N_{unique}$ 与现有 APR 技术的对比，并通过包含 42 种 APR 技术进行彻底的比较。为了进行这样的比较，我们进行了系统的文献综述，以确定已在 Defects4J 数据集上评估的所有 APR 工具。我们在评审过程中考虑了四个纳入标准：1）论文提出了一种新的 APR 技术并在 Defects4J 上对其进行了评估，例如，排除了针对 C 语言的 APR 工具； 2）论文必须经过同行评审，即我们排除灰色文献，包括技术报告、博士论文等； 3) 论文全文应可公开访问，以便我们检查此 APR 工具修复了哪些错误。例如，DEAR 在我们进行文献综述3时仍然没有公开的全文被排除在外。

基于这样的纳入标准，我们最终确定了 42 个 APR 工具。如表1所示，我们的比较涵盖了七年时间段（即从2016年到2022年），并表征了APR技术之间故障定位配置的差异。我们观察到现有的 APR 技术评估主要采用两种故障定位配置：

（1）故障定位（Fault Localization，简称FL），部署特定的故障定位技术（即基于频谱的或基于信息检索的）并向APR工具输出可疑程序实体的排名列表；

（2）非故障定位（简称Non-FL），直接向APR工具提供故障线路或方法。

由于这两种故障定位场景对 APR 工具的有效性有显着不同的影响，我们分别比较这两种故障定位场景。根据之前的研究 ，我们从文献中收集了 42 种研究工具的修复结果。

图7 展示了FL 场景中每年的最大 $N_{unique}$。对于每个 APR 工具，$N_{unique}$ 是在创建 APR 工具的年份之前提出的先前 APR 工具从未修复过的错误修复数量。例如，Elixir 是在2017年提出的，因此我们通过检查有多少2016年提出但被 Elixir 修复的五个APR工具（即在 FL 场景中，排除 HDRepair，因为它依赖于非 FL 场景）未修复的新错误来计算其 $N_{unique}$。 因此，最大 $N_{unique}$ 是每年达到的最高 $N_{unique}$。 2017 年 Elixir 的$N_{unique}$为19，高于2017年提出的其他三个工具。因此，2017年 $N_{unique}$ 的最大值为19。

如图 7 所示，数据集中新修复的错误的增长近年来已遇到瓶颈。 $N_{unique}$ 的最大值在 2017 年迅速上升至 19，并在接下来的两年（即 2018 年和 2019 年）稳步下降。 $N_{unique}$ 的最大值在 2020 年和 2021 年突然缩小为 5 个和 4 个。此外，在不考虑 TransplantFix 的情况下，这个数字在 2022 年下降为 2 个。这表明，随着多种APR技术的不断提出，修复新的Bug变得越来越困难。

在图 7 中，考虑了在 FL 场景中评估的 36 个 APR 工具，并且 Defects4J v1.2 中总共 146 个错误已被 36 个工具中的至少一个正确修复。为了计算 TransplantFix 的 $N_{unique}$，我们不仅考虑了 2016 年至 2021 年间所有已修复的错误，还包括 RewardRepair 在 2022 年新修复的错误。因此，TransplantFix 正确修复了 36 种 APR 技术中任何一种都没有修复的 8 个新错误。此外，与过去三年提出并在 FL 场景中评估的 7 个 APR 工具新修复的 bug 数量相比，TransplantFix 实现了最佳性能，比 Restore 多 60%（3 个 bug），比 RewardRepair 多 300%（6 个 bug）。

自 2019 年以来，使用非 FL 场景已成为一种常见做法，尤其是在基于深度学习的 APR 工具中（即表 2 中 12 个工具中的 8 个）。表 2 列出了 $N_{unique}$ 的 12 个 APR 工具，其中包括采用非 FL 场景的 TransplantFix。作为最早在非FL场景下进行评估的工具之一，TBar 与 HDRepair 相比首次修复了 64 个 Bug。 2019 年之后，$N_{unique}$ 从未超过 20。2021 年，与 2016 年至 2020 年间提出的所有（即 7 个）工具相比，Recoder 取得了较高的 $N_{unique}$。2022 年修复新 bug 的难度变得更大。一个代表性的事实是，2022 年提出的最先进的 APR 技术，即 RewardRepair，仅修复了 5 个分别是第一次出现错误。我们根据非 FL 场景下评估的 APR 工具正确修复的所有 bug（包括 2022 年提出的两个 APR 工具）来计算 TransplantFix 的 $N_{unique}$。在这种情况下，TransplantFix 仍然成功修复了 10 个新 bug，而这些 bug 从未被所有 10 个 APR 工具正确修复过。

TransplantFix 的通用性

自杜里厄等人以来揭示了基准过度拟合问题，评估新提出的 APR 工具的通用性变得越来越流行。在这项工作中，我们评估了 TransplantFix 对 Defects4J v2.0 中 444 个新错误的普遍性。请注意，在此数据集上评估的现有 APR 工具使用不同的故障定位场景。为了公平比较，我们在 FL 和非 FL 场景中运行 TransplantFix。表 3 列出了每个 APR 工具正确修复的错误数量。

我们观察到，先前对 APR 工具的普遍性的评估主要关注正确修复错误的绝对数量 ，但这可能会对结论的可靠性带来威胁。例如，APR 技术正确修复了 Defects4J v1.2 中 395 个错误中的 20 个错误，以及 Defects4J v2.0 中 444 个错误中的 20 个错误。就绝对数量而言，性能不会下降，但实际上，考虑到数据集大小之间的差异（即 395 与 444），该工具的性能会略有下降。为了捕捉这些差异，我们提出以下指标来计算 APR 技术的通用性：
$$\text{DegradationRatio}=\left|\frac{N_{\text{correct}}}{|\text{usedBugs}|}\right|-\left|\frac{N_{\text{correct}}^{\prime }}{|{\text{usedBugs}}^{\prime }|}\right|\text{\hspace{1em}(5)}$$
其中，$N_{\text{correct}}$ 表示原始数据集中正确修复的错误数量，$N_{\text{correct}}^{\prime }$ 表示新数据集中正确修复的错误数量。 $|\text{usedBugs}|$ 和 $|{\text{usedBugs}}^{\prime }|$ 分别表示原始数据集和新数据集用于评估的已使用错误的数量。$DegradationRatio$ 分数越低，APR 工具的通用性越强。

表 3 显示了在 Defects4J v1.2 和 v2.0 数据集上评估的五种 APR 工具的 DegradationRatio 分数。在 FL 场景中，有五个 APR 工具在两个数据集上进行评估。与其他四种 APR 工具相比，TransplantFix 通过达到最低的 DegradationRatio 实现了最佳性能。请注意，与所有五种 APR 技术相比，RewardRepair 修复了 Defect4J v2.0 中 257 个错误中最多的错误。然而，它修复了 Defects4J v1.2 中 120 个错误中的 29 个错误，但当 Defects4J v2.0 中提供了两倍以上的错误（即 257 个）时，这个数字减少到 24 个。因此，它的 DegradationRatio 是五种 APR 工具中最高的。在非 FL 场景中，与在两个数据集上评估的 RewardRepair 相比，TransplantFix 也以最低的 DegradationRatio 分数（即 3.48%）实现了最佳性能。

TransplantFix 优于其他 APR 工具的一种解释是，TransplantFix 不依赖于任何手动设计或自动学习的修复操作。这种精心设计或学习的修复操作可能会过度适合特定的数据集。相反它从 Buggy 项目中的捐赠者方法中提取语义修复操作，无需任何人为干预或神经模型调整，因此比研究的 APR 工具更具通用性。

案例研究

虽然第 1 节和第 2 节中所示的 Chart-6 显示了 TransplantFix 的独特性，但我们进一步对 Defects4J 中的错误进行了两个案例研究，以展示 TransplantFix 如何利用其命名空间传输（即 Chart-17 的案例研究）和图形差异（即 Chart-1 的案例研究）来为现实世界的错误生成正确的补丁。

图 8(a) 展示了一个名为 Chart-17 的错误。尽管人工编写的补丁的大小相对较小，即由单行删除和两行插入组成，但无论是在 FL 还是非 FL 场景下，该错误都从未被其他 APR 工具修复过。修复这个bug需要APR技术来很好地解决多个方法调用、类型以及变量的插入问题。为了修复这个错误，TransplantFix 首先通过继承层次感知代码搜索找到了图 8(b) 中所示的捐赠者方法，即 XYSeries 类中的 Clone() 方法，该方法与有缺陷的类 TimeSeries 继承自同一父类 Series。然后它利用命名空间传输来构造类型映射 {XYSeries → TimeSeries}，最后应用提取的修复操作（即删除错误语句并插入两个捐赠者语句）以生成正确的修复。

图 9(a) 说明了另一个名为 Chart-1 的错误，它对应于 if 条件开关。与修复错误的现有 APR 技术不同，TransplantFix 以一种有趣的方式修复此错误，而不依赖于任何手动设计或自动学习的修复操作。请注意，图 9(b) 所示的捐赠者方法中没有捐赠者代码（即 “==” 运算符），TransplantFix 通过我们基于图差异的方法识别语义差异。也就是说，在控制流图表示中，有缺陷的方法显示（即当条件 dataset != null 为真时返回结果）与捐赠者方法相反的行为（即当条件数据集 != null为假时返回结果）。因此 TransplantFix 识别此语义修复操作（即切换 if 条件）并通过应用该操作正确修复它。

讨论

TransplantFix 在复杂补丁合成中的潜力 我们观察到，TransplantFix 在 Defects4J v1.2 上生成的 36 个补丁中，大约有 20% 是六行插入补丁或更大的补丁。特别是，TransplantFix 成功地合成了一个 15 行插入的补丁，跨越了 Time-3 bug 的 5 个块。它还为 Math-13 和 Chart-6 在单个块中合成了八行插入的补丁。这三个错误都属于 TransplantFix 新修复的错误集中。这表明 TransplantFix 在针对现实世界的错误合成复杂补丁方面的潜力。在 Defects4J v2.0 上进行评估时，这一比例已降至 8%。一种解释是 Defects4J v2.0 中添加的新项目要小得多，这使得生成复杂的补丁变得困难。例如，Cli项目由4KLoc的源代码组成，其中TransplantFix针对三个Cli bug生成的补丁都是一行插入补丁。在这种情况下，TransplantFix可能需要从外部项目中搜索捐赠者方法。我们将代码搜索的扩展作为未来的工作，以探索 TransplantFix 在合成更复杂补丁方面的全部潜力。

TransplantFix 的可解释性 APR 技术的可解释性（即解释补丁是如何生成的）对于在实际流程中更多地采用 APR 技术非常重要 。最近，诺勒等人。 报道称，APR 技术的副产品（例如，识别出错误或修复位置）可以增强对 APR 生成补丁的信任。在这项工作中，TransplantFix 的整个修复流程是透明且确定的。除了错误或修复位置之外，TransplantFix 还可以提供更多副产品，包括已识别的具有类似功能的供体方法作为修复参考、指示供体和 buggy 方法之间语义差异的编辑图，以及应用于 buggy 方法的确切修复操作。

TransplantFix提供的这些信息可以有利于开发者评估补丁的正确性，从而增强开发者对TransplantFix生成的补丁的信任：

TransplantFix 的后续步骤 在本文中，我们提出了 TransplantFix 并在新修复的错误和通用性方面展示了其有希望的结果。作为未来的工作，我们设想 TransplantFix 可以进一步发挥其潜力的两种场景：1）工业部署，其中 TransplantFix 可以集成到 Repairnator 的实际修复管道中，以帮助现实世界中的手动调试活动。 2) 基于全局搜索的修复，其中 TransplantFix 将修复成分搜索范围扩展到外部项目。因此，出现了一系列新的挑战，因为继承关系在这种情况下可能不起作用，并且命名空间差异可能更加显着。

对有效性的威胁 对内部有效性的一个威胁是我们在第 4.3 节中进行的文献综述可能无法涵盖 Defects4J 中评估的所有现有 APR 技术。为了减轻威胁，我们手动检查了引用 Defects4J 出版物 的所有出版物，并根据第 4.3 节中定义的纳入标准确定了合格的出版物。另一个威胁是，我们按照先前的实践，从文献中提取了 42 个研究的 APR 工具的修复结果 。然而，这样的结果通常是由不同的硬件和超时得出的，这可能会导致比较有偏差。考虑到使用相同的硬件和时间预算重新运行所有 APR 工具所需的巨大工程工作和时间成本（例如 RepairThemAll 实验 ），我们将此类实验留作未来的工作。 对外部有效性的威胁是用于评估 TransplantFix 的错误可能并不代表所有现实世界的错误。为了减轻威胁，我们使用了最常用的数据集 Defects4J 及其扩展版本中的总共 839 个现实错误。作为未来的工作，我们计划在更真实的数据集（例如 Bears 、Bugs.jar ）上评估 TransplantFix。

总结

在本文中，我们提出了一种继承层次结构感知的捐赠者搜索方法来定位修复成分，一种基于图差异的方法来提取语义修复操作，以及一种全面的名称空间转移方法来适应捐赠者代码。我们通过涉及 42 个 APR 工具的广泛比较以及对 Defects4J v1.2 和 v2.0 中 839 个错误的评估来强调 TransplantFix 的独特性。与基线 APR 工具相比，TransplantFix 在新修复的错误数量和通用性方面均实现了最佳性能。此外，它还显示了合成最多由八行插入组成的复杂补丁的能力。在未来的工作中，我们计划将 TransplantFix 扩展为更多场景（例如，集成到 Repairnator 中）和实验（例如，使用更多数据集进行评估），如第 5 节所述。

启发

复杂错误的代码包含多错误的情况，适合学生提交作业的情况，对此可以参考提出的方法，寻找同伴程序、提取语义修复（图编辑距离路径）等步骤，获得语义修复动作后喂给 LLM 进行后续修复及反馈生成，不仅适合学生作业多错误情况，也对控制修复前后意图保持一致有帮助。

相关知识链接

• 论文链接
• BibTex

@inproceedings{10.1145/3551349.3556893,
author = {Yang, Deheng and Mao, Xiaoguang and Chen, Liqian and Xu, Xuezheng and Lei, Yan and Lo, David and He, Jiayu},
title = {TransplantFix: Graph Differencing-based Code Transplantation for Automated Program Repair},
year = {2023},
isbn = {9781450394758},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3551349.3556893},
doi = {10.1145/3551349.3556893},
booktitle = {Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering},
articleno = {107},
numpages = {13},
keywords = {Automated program repair, code transplantation, graph differencing},
location = {Rochester, MI, USA},
series = {ASE '22}
}