在自动程序修复中使用基于图差分的代码移植

分享一篇来自AST' 22的文章，题目为"TransplantFix: Graph Differencing-based Code Transplantation for Automated Program Repair"。

在APR社区中，修复材料（Fix Ingredien）是一个常用的概念，它最初表示合成补丁所需的代码片段，也称为供体代码（上篇阅读笔记中出现的词，答疑了）。近年来，在抽象层上对修改源代码的指令进行编码的修复动作也作为一种修复成分被包括在内。虽然越来越多现实世界中的bug被现有的APR技术修复，但APR技术在修复材料层面仍然面临3个挑战：

**（1）定位修复材料，即：在哪里可以找到用于补丁合成的复杂修复材料？**现有的APR技术探索了一系列情况，包括在bug文件、bug项目和外部项目中搜索供体代码。就修复问题而言，现有的APR技术通常假定修复操作驻留在外部项目的真实世界人工编写的bug修复中，可以手动挖掘或自动学习。虽然修复材料可以修复许多单行或单一块错误，但是在哪些地方可以找到更大的bug修复材料，仍然没有答案。

**（2）提取修复行为，即：如何提取复杂的修复动作？**现有的APR技术通过多种方法，如：手工摘要、统计分析、或学习模型，提取修复动作。这些方法的关键思想是识别最频繁的修复操作。但是，随着代码更改大小的增长，修复更改的重复性呈指数级下降，复杂修复更改的排序会下降，因此被选择为修复操作的可能性很低。因此，这些复杂的更改很难手工构建或学习，如图2所示的修复动作。

**（3）供体代码的适配，即：如何适配复杂的供体代码？**GenProg[1]直接将代码从bug程序中的一个位置转移到错误位置，但没有解决潜在的命名空间冲突。Subse-Quent APR技术（例如SimFix[2]，SOSRepair[3]，Fix[4]）通过提出变量重命名方法来调整供体代码片段，但当供体代码加入更多实体（例如，用户定义的数据类型）其他变量时，就需要更全面的供体代码转移方法。如图2所示，修复这种错误需要一组新的代码片段。除了多个变量外，Chart-6修补程序还包含原始数据类型和用户定义的数据类型，甚至还包含不同类的方法调用；此外，这些供体代码的组合在一个块上最多包含8行插入。

在本文中，作者提出了一种新的基于图差分的代码移植方法来帮助解决这三个挑战。

Motivation

对于挑战1，一个供体方法可能为Chart-6提供两个来源的修复材料，即：修复动作和供体代码。如图4所示，PaintList类中的供体方法equals()与Chart-6的错误方法共享相同的方法名。与buggy方法调用super.equals(obj)不同（图3中的第111行），供体方法有自己的"比较行为"实现（图4中的第98-107行）。供体方法中的这种实现在功能上类似于图2所示Chart-6人工编写的补丁。值得注意的是，buggy类（ShapeList）和供体类（PaintList）都继承了同一个父类（AbstractObjectList）。这指出了一条新的途径，通过在buggy项目中适当地搜索供体方法来获得复杂的fix材料。

针对这一问题，本文设计了一种继承层次化感知的method搜索方法。考虑到Chart-6的buggy方法和供体方法在标识符、控制结构和补丁大小方面有很大的不同，作者选择使用方法签名来度量这两种方法之间的相似性。然而，当方法签名在项目中非常常见时（例如，equals()），候选供体方法可能具有相同的相似性得分(即，"being tied")，这对于供体方法排名是不被期望的结果。为了打破这种联系，作者通过区分位于错误方法的相同继承图中的供体方法的优先级来进一步利用继承关系。通过这种方式能够准确地将供体方法排在第一位。

对于挑战2，作者建议执行图差分来提取buggy和供体方法之间的语义差异。首先将该方法表示为控制流图，然后设计一个基于精确图距离算法[5]的图差分算法来推断所有可能的修复动作。在这个例子中，本文提出的算法通过对由buggy和供体方法构造的控制流图进行差分来获得编辑图。如图5所示，编辑图指定了bug和供体方法之间的语义修复动作，包括修复动作的搜索空间。该搜索空间包括修复Chart-6所需的修复动作，即：用供体方法中第98-107行的语句更新buggy方法中第111行的语句。

对于挑战3，即：图4中的数据类型（PathList）和方法调用（PaintUtilities.equal()）与buggy方法不兼容，作者设计了一种命名空间转移方法，不仅可以处理变量，还可以处理类型和方法。这使本文所提模型能够成功地推断出ShapeUtilities.equal()在错误文件中不存在，但实际上与错误文件兼容。在正确地转移供体代码之后，可以将提取的语义修复动作和转移的提供者代码应用于错误方法，以产生对Chart-6的正确修复。

其实感觉这篇文章的Motivation部分的描述不是特别易懂。

Approach

本文所提模型的框架如图6所示。图6描述了TransplantFix的整体工作流程。TransplantFix建立在由三个阶段组成的自动程序修复的典型pipline之上：（1）错误定位，（2）补丁生成，（3）补丁验证。对于错误定位，TransplantFix将有问题的程序及其相关的测试套件作为输入，并按照可疑性值的降序排列可疑方法。然后将该列表输入到补丁生成阶段，以生成候选补丁。作为TransplantFix的核心阶段，补丁生成阶段包括三个阶段：（1）供体代码搜索，（2）供体代码转移和（3）修复行为提取。对于每个可疑的方法，供体代码搜索阶段测量它与项目中所有方法的相似性，然后根据相似性进行排序。对于每个供体方法，供体代码转移阶段将供体方法中的实体转换成与可疑方法兼容的实体。之后，修复行为提取阶段用属性化的控制流图表示方法，并通过对转移的供体图和可疑图进行差分来产生编辑图。基于编辑图，提取语义修复行为来构造搜索空间。将搜索空间中的修复动作和具体的提供者代码应用于可疑方法，以产生候选补丁的列表。在最后一个阶段，补丁生成用错误程序的原始测试套件来验证候选补丁。如果没有找到通过测试套件的有效补丁，TransplantFix将返回到下一个可疑方法的补丁生成阶段。否则，TransplantFix退出并输出有效的补丁。

• 修复材料（供体代码）搜索

旨在将包含用于bug修复的修复材料的供体方法与其他方法区分开来。为此，它利用局部特征（即：方法签名）和全局特征（即：继承关系）来度量可疑方法和每个候选供体方法之间的功能相似性。

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

• 定义2，继承DAG：继承DAG 是用于表示类间继承关系的有向非循环图（DAG），其中每一个顶点表示一个类，边表示继承关系。继承是面向对象编程的一个重要特性，作为一种机制，它使一个类能够继承另一个类的字段和方法。有报道表明，在至少一半被调查的真实世界Java应用程序中，大约74%的用户定义类使用继承。由于Java中一个类最多可以扩展一个超类，但实现多个接口，所以本文采用图结构而不是树结构来表示继承关系。

• 定义3，相关类：如果使得，则与相关。其中，指继承的集合，是and的意思。本文提出“相关类”的概念来描述同一继承DAG中两个类之间的关系。相关类捕获了方法的全局特性，因此可以帮助进一步区分供体方法的优先级。例如，供体PaintList是Chart-6中buggy类ShapeList的相关类，在度量相似度时会给供体方法更高的分数。

给定两个方法，来自bug代码，来自供体代码，它们之间的局部相似性用如下公式进行计算，

全局相似性（继承相似性）采用如下公式计算：

其中jacc()是指Jaccard相似性计算函数，和为权重系数。对于公式(2)，如果bug类没有相关类，则进一步考虑二者元素间的相似性。

最终的相似性由和的平均值决定。

•  供体方法转换

旨在将供体命名空间与可疑命名空间对齐。首先通过在每个方法中收集三种类型的程序实体来构造可疑方法和候选供体方法的名称空间。然后创建实体映射，这些映射对候选供体方法中的实体应该如何适应于可疑方法进行编码。

**命名空间构造。**对于一个方法，命名空间构造包括以下三种程序实体：

（1）Types：考虑两种类型，第一个是方法中使用的所有类型，作为"局部类型"；第二个是方法所属可疑类类型（例如，如图3所示可疑方法的equal的ShapeList类型），充当"全局类型"。

（2）Method Calls：收集方法中调用的所有method call。为了便于两个方法调用之间的比较，本文识别并收集其局部特征以及全局特征。

（3）Variables：除了收集方法中定义或使用的每个变量，还通过跟踪它的声明来收集它的类型。

**命名空间对齐。**由于名称空间中的变量和方法调用都与类型信息相关，所以优先构造类型映射，以便于其他实体的映射。

1. 类型映射，和：

首先对"全局类型"进行映射。给定一个可以可疑方法的"全局类型"和供体方法的"全局类型"，根据驼峰命名切分类型为一组子token，即：。同理，对于，也有对应的。计算两个list之间的最长公共子序列（LCS），然后使用如下方法将中的子token或子token的连接映射到中：

其中，，（）表示（）的子集。

设和是CLS中的两个邻居元素，当时，定义；当时，定义，。

以图4中Chart-6为例，PaintList和ShapeList之间的LCS为[List]，PaintList中唯一的子tokenPaint被映射到ShapeList中唯一的子tokenShape。因此，，其中用于局部类型映射。

在局部类型映射中，对于候选供体方法中的每一个类型，如果其包含（这个是啥？）中的，使用替换该类型中的，否则保持不变。例如，Chart-6的供体方法的局部映射为：，。

2. 方法调用映射，：

方法调用映射如下所示：

其中，，，分别表示在可疑方法和候选供体方法中的方法调用集合。

首先通过测量方法调用的相似性，将候选供体方法中的方法调用映射到可疑方法中的方法调用。这里使用3.2节中描述的方式来度量两个方法调用之间的相似性。当相似性大于阈值分数时，将这两个方法调用添加到映射中。对于仍然没有映射的方法调用，基于全局类型映射进一步创建方法调用映射。类似于局部类型映射的构造，只有当方法调用包含中的时，才把方法调用中的替换成。例如，Chart-6的供体方法的方法调用映射是。

3. 变量映射，：

建立在类型映射之上。具体来说，对于供体方法中的每一个变量，在可疑方法中包含一个符合如下约束条件的变量集合：

其中，指变量的类型。进一步根据中的变量到的Levenshtein距离就行升序排序。例如，Chart-6供体方法中的变量映射为：。

• 修复行为提取

旨在基于3.3节中候选供体方法的已转移命名空间，提取3.2节中获得的候选供体方法和可疑方法之间的语义修复动作。具体来说，包括以下步骤:

1. 图构建

由于修复动作涉及复杂的控制结构，因此作者使用Soot生成CFG来表示方法，有助于对方法中语句间的控制依赖关系进行建模。

2. 图差分

图形编辑距离是一种图差分方法，旨在以最低成本找到来自的最佳编辑路径。

本文将修复变更提取转换成图编辑距离计算问题，相关定义如下：

• 定义4，有属性的CFG：由四元组表示，表示AST节点，表示控制流传递，是一个将属性关联到顶点的函数，是一个将属性关联到边的函数。

如定义4所示，在有属性的CFG中，用顶点表示AST节点，用边表示控制流转换。在属性方面，使用CFG中每个AST节点的格式化字符串作为顶点属性，并将流转换标签(即，对于分支流转换为“真”和“假”，对于其他转换为空字符串)与边属性相关联。

• 定义5，图编辑距离：给定两个有属性的CFG，和，从到的图编辑距离计算如下：

其中，表示在两个节点或两条边之间的编辑操作，表示编辑操作的成本，表示一条编辑路径 （即：编辑操作序列），表示从到的所有可能的编辑路径。

本文考虑了4种编辑操作：（1）update：，使用更新；（2）delete：，删除；（3）insertion：，插入；（4）match：match操作是update操作的特例，但其成本为零（即：），表明和完全匹配。

边的编辑操作与顶点的编辑操作具有相同的类型。

本文使用的GED算法为DF-GED，成本函数如下：

其中，是中节点的属性值，表示的起始节点的特征，表示的结束节点的特征。

如等式（3）所示，如果两个顶点都是表达式或者语句(即：typeMatched())，计算的字符串以及在3.3节中获得的的每一个映射的字符串的Levenshtein距离（即：levensh()）。将每个Levenshtein距离归一化到范围[01]中，并选择最小成本作为最终成本。否则，认为这两个顶点是不匹配的，并因此分配。请注意，应该大于匹配节点的成本。

两条边的成本计算建立在顶点的成本计算之上。如等式(4)所示，计算和的标签之间的Levenshtein距离的平均成本、两条边的起始顶点之间的成本以及两条边的终止顶点之间的成本。

3. 搜索空间构建

上一部分能够获得最佳编辑路径，它包含将转换为所需的所有编辑操作。然而，在自动程序修复的上下文中，错误方法可能只需要编辑操作的子集来修复；引入所有编辑操作可能会导致副作用或错误。另一方面，如果考虑最佳编辑路径中涉及的编辑操作集合的所有子集，搜索空间可能会爆炸。例如：对于图5所示的案例，有12次编辑操作（9次insert，2次update和1次delete），搜索空间的大小为。因此，搜索空间的大小随编辑操作的增加而呈现指数级增长。

为了有效地形成搜索空间，本文提出了"切割点"的概念，使用切割点对来进行分组修复动作。分组后，每个组可以被视为一个"大"编辑操作。

○ 定义6，切割点：切割点是一个对于两个顶点的编辑操作，，其中，，是update或match操作。

如定义6所示，切割点被定义为更新或编辑操作，其中两个顶点存在于两个图中。切割点表明可疑方法中的一个顶点和候选供体方法中的一个顶点之间的映射，并且可以进一步用于组相关编辑操作。

算法1描述了本文如何分组编辑操作和生成修复行为的。

首先，使用深度优先遍历获取的所有切割点（第5行）。然后使用一对切割点（即：，其中，）来对整个编辑路径进行切分（第6-14行）。这样一来就可以描述位于和之间的连续编辑操作序列的特征。这些连续的操作可以组合成一个"大的"依赖的修复动作（第13行）。当识别切割点对时，进一步引入编码句法规则的行顺序约束：

其中表示相应顶点的行号。这要求可疑方法中的和的两个顶点应该具有与候选供体方法中的顶点相同的行号顺序（第8-11行）。对于生成修复动作（第13行），除了考虑编辑操作的完整序列来获得"大的"修复动作之外，还通过生成应用序列的单次编辑的修复动作来进一步丰富搜索空间。一旦从切割点对生成了所有的修复动作，进一步考虑组合位于相同If或循环控制结构中的"大的"修复动作，以形成依赖于分支的修复动作（第16行）。有了这些动作，就可以将它们一个接一个地应用到有问题的项目中，生成一个候选补丁列表。

这篇文章的方法论部分就到此结束了，实验部分感兴趣的小伙伴可以看原文，这里就不再赘述了。

总的来说，这篇阅读笔记属于深度阅读了吧。

简单总结下这段时间读的两篇程序修复相关的文章吧：

首先是供体代码。正如本文提到的，供体代码表示合成补丁所需的代码片段；个人理解就是与缺陷代码相似的代码。在确定一组供体代码后，需要进行命名空间对齐，保证缺陷代码和供体代码之间的一致性。接着需要确定搜索空间，常用的方式多基于图编辑距离。简单来说，可以把搜索空间看作是编辑操作间的不同组合形成的集合。由于搜索空间很大，因此大部分研究都涉及对搜索空间的精简。然后基于搜索空间生成补丁，将搜索空间中的每一个元素（修改动作）接入缺陷代码，生成补丁，最后测试补丁能否通过测试套件。

参考文献

[1] W. Weimer, T. Nguyen, C. Le Goues and S. Forrest, "Automatically finding patches using genetic programming," 2009 IEEE 31st International Conference on Software Engineering, Vancouver, BC, Canada, 2009, pp. 364-374, doi: 10.1109/ICSE.2009.5070536.

[2] Jiang J, Xiong Y, Zhang H, et al. Shaping program repair space with existing patches and similar code[C]//Proceedings of the 27th ACM SIGSOFT international symposium on software testing and analysis. 2018: 298-309.

[3] Afzal A, Motwani M, Stolee K T, et al. SOSRepair: Expressive semantic search for real-world program repair[J]. IEEE Transactions on Software Engineering, 2019, 47(10): 2162-2181.

[4] Xin Q, Reiss S P. Leveraging syntax-related code for automated program repair[C]//2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2017: 660-670.

[5] Abu-Aisheh Z, Raveaux R, Ramel J Y, et al. An exact graph edit distance algorithm for solving pattern recognition problems[C]//4th International Conference on Pattern Recognition Applications and Methods 2015. 2015.