原文标题：Shaping program repair space with existing patches and similar code
原文作者：Jiang J, Xiong Y, Zhang H, et al.
发表会议：ISSTA 18
原文链接：https://dl.acm.org/doi/abs/10.1145/3213846.3213871
笔记作者：[email protected]安全学术圈
笔记小编：[email protected]安全学术圈

APR（自动化程序修复）通常被视为搜索问题，其搜索空间由所有可能的补丁组成，目标是在搜索空间中识别正确的补丁。这个问题很有挑战性，因为搜索空间通常很大，并且包含许多看似合理的（通过所有测试的补丁）但不正确的补丁；而测试用例并不能区分正确的和看似合理但不正确的补丁。APR方法不仅需要从巨大的搜索空间中定位正确的补丁，还需要避免看似合理但不正确的补丁。

为此，许多APR技术采用数据驱动的方法来估计补丁的可能性，并限制/优先化搜索空间，以使得首先尝试的补丁是更有可能正确的。目前两种常用的数据是：

1. 现有补丁：分析现有的补丁能够提供bug-fixing修改的分布，使得可以挑选出最有可能进行修改的补丁。

2. 源代码：分析源代码有助于理解要修复的程序的内部结构（包括公共代码和特定于上下文的代码），从而可以选择适合本地编程上下文的补丁。

然而，这两种数据源都有其局限性。一方面，虽然现有的补丁提供了bug-fixing修改的全面特征，但它们通常不足以覆盖不同的情况。特别是，对当前项目中的局部元素的bug-fixing修改，例如：为用户定义的方法添加边界检查或删除用户定义的对象的冗余初始化；这通常在现有补丁中找不到，因为通常只存在来自当前项目历史的有限数量的补丁。另一方面，源代码没有描述bug-fixing修改的可能性，即：开发人员犯错误的可能性有多大。例如，通常更有可能将">"改为">="而不是插入一个循环语句，但是源代码本身并不能告诉我们这些信息。

在本文中，作者建议将这两个数据源结合起来，以更好地指导自动化程序修复。本文的基本思想是：使用每个源来表征搜索空间，并取两个空间的交集。

Motivation

listing 1是Defects4J中的一个缺陷（Closure-57）。在这个例子中，if条件是不完整的。在访问targert对象的getString()方法之前，需要检查其类型是否为Token.STRING。在典型的程序修复过程中，首先使用错误定位算法来定位该代码段，然后在搜索空间中找到一组对该代码段的修改（即：补丁），这些修改可以使所有测试通过。

如果允许所有可能的修改，搜索空间是无限的，不容易在空间内快速识别正确的补丁。为了实现有效的搜索，需要缩小搜索空间，以便只包含最可能的补丁。

首先考虑如何使用相似的代码来缩小空间。根据现有的研究[1,2,3]，与有缺陷的代码片段相似的代码片段更有可能包含补丁的成分。因此，我们可以将搜索空间限制为只包含来自相似代码片段的成分。在本文给出的示例中，给定一个错误的代码片段，能够找到一个供体（donor）代码片段（listing 2），它与listing 1中显示的错误代码相似。它们在抽象语法树方面有相似的代码结构——都有一个IfStatement围绕着相同的MethodInvocation （getString()）。

如果直接结合供体代码片段中的成分，很难找到合适的粒度。例如，一些现有的研究使用语句粒度，即：在供体代码片段中插入或替换语句。在上述例子中，整个代码片段是一个if语句，直接用供体语句替换有问题的语句不会修复错误，因为供体代码片段使用不同的变量名并包含不同的主体。另一方面，如果使用细粒度级别，例如AST节点级别，则有许多可能的方法来组合AST节点，并且搜索空间仍然很大。

为解决这个问题，作者结合变量匹配和代码差分来产生搜索空间。首先，引入一个算法，该算法基于变量的用法、类型和名称来映射两个代码片段中的变量。基于映射，用错误代码片段中的映射变量替换供体代码片段中的变量。在上述例子中，last将被target替换，因为它们共享相同的类型，并且都在!=比较和在对getString()的方法调用中。类似地，propName将被className替换。接着，利用细粒度的代码差异算法来比较两个代码片段，并提取从错误代码到供体代码的修改。本文涉及的差分算法基于GumTree [4]，可以在AST子树级别提取修改。在上述例子中，本文的差分算法提取了以下两个修改：

1. 使用target!=null && target.getType()==Token.STRING替换target!=null。

2. 在If块的最后插入return (className.equals(methodName))。

搜索空间包含所有修改的组合。在上述例子中，搜索空间包括三个补丁：[修改1]、[修改2]和[修改1, 修改2]。

虽然使用相似的代码大大减少了搜索空间，但搜索空间可能仍然包含许多看似合理但不正确的补丁。 例如，listing 3中的例子（来自Defects4J中的Time-24 bug），在本文的评估比较实验中，这个bug被错误地修复了。在这个例子中，错误定位算法错误地将正确的片段识别为错误的。从这个代码片段中，可以找到一个供体代码片段（第2-4行）,它导致了一个用强制转换表达式替换方法调用的补丁（第7-8行）,这个补丁恰好通过了所有的测试。然而，事实上，开发人员很少会将强制转换表达式与方法调用混淆在一起，因此这个补丁并不常见，也不太可能是正确的。换句话说，如果我们从现有的修补程序中得到一个搜索空间，只覆盖常见的修复模式，我们可以从搜索空间中排除这个修补程序。

为了从补丁语料库中获得搜索空间，作者定义了只包含AST节点类型的抽象修改。例如，其中一个抽象修改可能是"用强制转换表达式替换方法调用"，它包含上面提到的补丁。然后统计抽象修改在语料库中的出现频率，将搜索空间定义为出现频率高于阈值的抽象修改的组合。在本例中，上述抽象修改的频率低于阈值，因此在两个搜索空间（补丁空间和源代码空间？）之间取交集之后，不正确的补丁将被排除。本文在离线挖掘阶段从现有补丁中获取空间，这个空间用于在线修复阶段修复许多不同的bug。

在获得最终的搜索空间后，根据三个排序规则对空间中的补丁进行排序。例如，首先对具有较简单修改的补丁进行排序。在上述例子（listing 1）中，首先尝试[修改1]和[修改2]，然后再考虑两者的组合。每当一个补丁通过了所有的测试，就输出结果。这样，将为第一个示例（listing 1）生成正确的补丁，而不会为第二个示例（listing 3）生成不正确的补丁。

Approach

图1是本文所提方法的框架，包含离线挖掘和在线修复两个阶段。

• 在离线挖掘阶段，分析一组补丁以获得搜索空间。

• 在线修复阶段包括五个阶段：（1）给定一个错误程序，使用标准的错误定位方法识别可疑错误语句的有序列表。（2）对于每个错误位置，定位与同一项目中的错误代码相似的供体代码片段。（3）对于每个供体代码片段，在供体代码片段和错误代码片段之间映射变量，并用相应的变量替换供体代码片段中的所有变量。（4）区分两个片段，获得搜索空间，并计算。（4）生成交集内的补丁列表，并使用测试套件验证它们。

两个阶段共享相同的搜索空间定义和相同的代码差分算法。

• 一些定义

在上述框架中，涉及到搜索空间这一概念。在定义搜索空间之前，需要更为形式化的AST。本文将AST定义为顺序树，即节点的子节点按顺序排列，并将所有AST的集合表示为。为避免混淆，直接使用来指代AST中的节点位置；使用来表示节点的父节点，来表示节点的子节点，来表示AST的根节点。假设存在一个函数用于对每一个节点赋予两类节点类型。第一类是tuple，有固定数量的子节点。例如，一个MethodInvocation类型的节点必须有3个子节点，分别是：一个reviever表达式，方法名和参数。第二类是sequence，无固定数量的子节点。例如，Block类型的节点可以用一系列的语句，语句的数量无法预先确定。使用或表明或是否为tuple类型。对于一些有相关值的叶子节点，如：SimpleName有对应的name值，使用表示对应的值，其中表示没有关联的值。

离散数学警告！

修改空间是修改操作的组合。

需要注意的是，本文定义的搜索空间不包括删除，因为现有研究认为[5,6]，删除代码通常会导致不正确的补丁。

基于上述定义，由差分算法产生的修改自然形成了搜索空间。但是，此定义依赖于AST，不适合分析不同AST上的补丁。为了支持补丁的分析，本文将抽象修改和抽象搜索空间定义如下：

很容易看出，每个具体的修改对应一个抽象的修改，本文使用函数abs来执行这种转换。

最后，在从补丁获得抽象空间和从相似代码获得具体空间之后，需要获得它们的交集。设是具体空间，是抽象空间，它们的交集定义如下。

• 修改提取

首先，当分析补丁时，需要得到每个补丁执行的修改。第二，当分析相似的代码时，需要从错误的代码片段得到对供体代码片段的修改。我们对两个地方使用相同的差分算法。该算法将两个AST a和b作为输入，并产生一组从a到b的具体修改。

具体来说，首先匹配两个AST之间的节点，并提取匹配过程中的修改。直观上，两个节点是匹配的，如果（1）它们具有相同的节点类型，并且（2）它们的所有祖先都匹配，或者（3）通过从目标AST向源AST插入一些节点可以满足前面的两个条件。算法1显示了两个AST之间的匹配过程的细节，通过执行自顶向下的搜索来定位满足上述条件的匹配节点。该算法从函数与两个AST的根开始。如果两个节点可以匹配（第2-3行），递归地检查它们的子节点；否则，通过将引用的AST中的一些父节点插入到出错的AST来检查这些节点是否匹配（第4- 6行）。两个节点匹配后，检查它们的子节点。这里区分两种类型的节点：对于tuple节点，只匹配相应位置的子节点（第13-14行）；对于sequence节点，它们的子节点可以自由匹配（第15-24行）。

在匹配的AST中检查以下四个条件，每个条件产生一个修改。其中，表示a和b匹配，a来自源AST，b来自目标代码片段，使用表示以a为根节点的子树：

当两个叶节点匹配但具有不同的值时，用目标节点替换源节点。

当两个tuple节点匹配但相应位置的一对子节点不匹配时，用目标子节点替换源子节点。

当两个sequence节点匹配时，确定至少一对匹配的子节点，并根据匹配子节点的相对位置将目标中所有不匹配的子节点插入到源中。

当一个源节点匹配一个较低层次的目标节点时，生成一个替换有效地将节点插入到匹配的目标节点之上。

• 挖掘阶段

挖掘阶段的输入是补丁语料库，其中每个补丁包括一对未打补丁的版本和打补丁的版本。对于每个补丁，使用差分算法来获得具体的修改，并使用函数将它们转换成抽象的修改。然后统计每一个抽象修改的出现频率。最后，选择出现频率大于阈值k的抽象修改构成搜索空间。

• 修复阶段

首先需要进行错误定位。理论上，任何产生可疑语句有序列表的错误定位方法都可以与本文的方法一起使用。本文选择了Person等人[7]实现的Ochiai[8]算法。此外，本文还使用test purification[9]来预处理测试用例，以提高故障定位的准确性。

供体片段识别。给定一个潜在的错误位置，将其扩展为一个错误的代码片段，然后定位一组相似的代码片段作为供体进行比较和调整。

代码片段：给定行号x和y，在源文件中处于[x, y]之间的代码段是包含在第x行和第y行之间的最长的语句序列。这里的语句是指AST中的Statement类型节点。例如：对于listing 2，在第1行和第4行之间包含了一个完整的If语句，而在第1行和第2行之间仅包含了用于初始化propName的语句，因为前两行没有完整地包含If语句。为识别供体代码片段，需要度量两个代码片段之间的相似性。这里定义了三个相似性度量，最终的相似性是这三个相似性的总和：

1. 结构相似性：结构相似性涉及AST的结构。遵循DECKARD [10]，从每个代码片段中提取一个向量，其中向量中的每个元素代表AST节点的一个特征。例如，一个元素可以是代码段中For语句的数量，另一个元素可以是代码段中算术运算符（+、-、*、/、%）的数量。然后计算两个向量之间的余弦相似度。

2. 变量名相似性：变量名相似性是指两个代码片段中的变量名的相似程度。首先对变量名进行token化，即根据CamelCase将变量名拆分成一组token。例如，变量className被分成两个单词class和Name。从这两个代码片段中，可以获得两组token化的变量名。然后，使用Dice的系数计算两个集合的相似性。

3. 方法名相似性：方法名相似性是指两个代码片段中使用的方法名的相似程度。方法名相似性的计算方式与变量名相似性的计算方式相同。

基于代码片段的定义，可以识别出错误代码段和供体的代码段。给定一条可能有错误的代码行，将其扩展为大小为N的代码片段，假设故障代码行为N，提取[n-N/2，n+N/2-1]之间的代码片段作为错误片段。

接下来确定供体片段。在所有源文件上滑动一个大小为N的窗口，提取窗口中的代码片段，并删除重复的代码。这样就提取了N行代码中所有可能的代码片段。接下来，计算错误片段和每个供体片段之间的相似性，并选择前100个供体片段。在本文的实验中，根据经验将N设置为10。

变量映射。在这个阶段，需要匹配错误代码片段和供体代码片段中的变量，并构建一个变量映射表用于代码调整。为此，利用三种相似性信息，即用法相似性、类型相似性和名称相似性：

1. 用法相似性：用法相似性捕获变量在代码片段中的使用方式。首先用一个使用序列来表示一个变量是如何被使用的。给定一个变量，执行AST的后序遍历，并打印变量每次出现的父节点类型。结果是一个序列，表示使用该变量的表达式。对于在listing 1和listing 2中给出的示例，变量target和last有以下使用顺序:

然后，基于最长公共子序列（LCS）计算两个使用序列的相似性。

2. 类型相似性：当重用来自供体代码片段的代码片段时，需要用目标变量进行变量替换。因此，确保映射的变量具有兼容的类型非常重要。（1）当一个变量在供体代码片段中用作左值时，需要确保目标变量的类型是原始变量的超类型。（2）当一个变量在供体代码片段中用作右值时，需要确保目标变量的类型是原始变量的子类型。理想情况下，当构建变量映射时，应该强制执行以上两个条件。然而，由于在当前阶段并不知道代码片段中的哪个代码片段将被重用，本文简单地使用类型相似性来度量它们类型的兼容程度。具体地说，将类型相似性定义为：当一个变量是另一个变量的子/超类型时，它们的相似度为1，否则为0。

在Java中，基本类型没有显式的子类型关系。给定两个基本类型和，认为是的一个子类型，如果中的任何值都可以无损地转换成中的值。

3. 名称相似性：两个变量的名称相似性的计算方式与用于识别供体代码片段的变量名称相似性的计算方式相同，只是这里只考虑两个变量，而不是代码片段中的所有变量。

最终的相似度得分是上述三个得分的加权和。在计算了每对变量之间的相似性之后，贪婪地选择相似性最高的对，直到没有对剩下。例如，listing 1和listing 2中的匹配变量是last和target，以及target和className。然后，用相应的映射变量替换供体代码片段中的所有变量，以使用与错误变量共享的变量来获得适配的供体代码片段。

后续本文把供体代码片段称为修改后的代码片段。

修改提取和插入。给定供体代码片段，按照相似性的降序将它们与有缺陷的代码片段逐一进行比较，并使用代码差分算法提取具体的修改。然后确定这组修改与通过分析现有补丁提取的修改之间的交集。在此之后，获得了一组用于生成补丁的具体修改。

补丁生成和验证。在前一阶段获得的修改集合定义了缩小的搜索空间。这一阶段的目标是在空间中找到一个能够通过所有测试的补丁。如前所述，对空间中的补丁进行排序，并逐个进行验证。根据以下规则，按照它们在序列中出现的顺序，对补丁执行多级排序：更早的规则表示更高的级别。

1. 包含一致修改的补丁排名更高。一致的修改（变更）是指在同一时间不同位置对变量进行相同的变更。

2. 修改较少的补丁排名较高。

3. 具有更多替换的补丁比具有更多插入的补丁排名更高。

第一条规则处理一种特殊情况：当一个变量被另一个变量替换时，它应该在其他情况下被相同的变量替换。第二个和第三个规则受句法距离的启发：具有更少、更简单的修改的补丁排名更高。

获得候选补丁的有序列表后，用测试套件逐个验证补丁，并返回通过所有测试的第一个补丁。

实验部分简单过了一下，看不动了。其实这篇文章思路挺有意思的，但是有些点不太好理解，有一定的上手难度。

参考文献

[1] Ji T, Chen L, Mao X, et al. Automated program repair by using similar code containing fix ingredients[C]//2016 IEEE 40th Annual Computer Software and Applications Conference (COMPSAC). IEEE, 2016, 1: 197-202.

[2] Ke Y, Stolee K T, Le Goues C, et al. Repairing programs with semantic code search (t)[C]//2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2015: 295-306.

[3] Yokoyama H, Higo Y, Hotta K, et al. Toward improving ability to repair bugs automatically: a patch candidate location mechanism using code similarity[C]//Proceedings of the 31st Annual ACM Symposium on Applied Computing. 2016: 1364-1370.

[4] Falleri J R, Morandat F, Blanc X, et al. Fine-grained and accurate source code differencing [C]//Proceedings of the 29th ACM/IEEE international conference on Automated software engineering. 2014: 313-324.

[5] Qi Z, Long F, Achour S, et al. An analysis of patch plausibility and correctness for generate-and-validate patch generation systems[C]//Proceedings of the 2015 International Symposium on Software Testing and Analysis. 2015: 24-36.

[6] Tan S H, Yoshida H, Prasad M R, et al. Anti-patterns in search-based program repair[C]//Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. 2016: 727-738.

[7] Pearson S, Campos J, Just R, et al. Evaluating and improving fault localization[C]//2017 IEEE/ACM 39th International Conference on Software Engineering (ICSE). IEEE, 2017: 609-620.

[8] Abreu R, Zoeteweij P, Van Gemund A J C. An evaluation of similarity coefficients for software fault localization[C]//2006 12th Pacific Rim International Symposium on Dependable Computing (PRDC'06). IEEE, 2006: 39-46.

[9] Xuan J, Monperrus M. Test case purification for improving fault localization[C]//Proceedings of the 22nd ACM SIGSOFT international symposium on foundations of software engineering. 2014: 52-63.

[10] Jiang L, Misherghi G, Su Z, et al. Deckard: Scalable and accurate tree-based detection of code clones[C]//29th International Conference on Software Engineering (ICSE'07). IEEE, 2007: 96-105.

安全学术圈招募队友-ing 
有兴趣加入学术圈的请联系 secdr#qq.com