Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Shaping Program Repair Space With Existing Patches and Similar Code

作者:Jiajun Jiang, Yingfei Xiong, Hongyu Zhang, Qing Gao, Xiangqun Chen

单位:Peking University, The University of Newcastle

出处:The ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) 2018

原文:https://xgdsmileboy.github.io/files/paper/simfix-issta18.pdf


Abstract

本文提出了一种新的自动化程序修复(automatic program repair,APR)技术,该技术同时基于已有的补丁(existing patches)和相似的代码(similar code)来缩小程序修复的搜索空间。一方面,该技术通过分析已有的补丁,得到一组出现频率较高的对于目标代码的抽象修正操作(abstract modifications),形成一个程序修复的抽象空间(abstract space)。另一方面,该技术通过分析在同一项目中相似的代码片段,得到一组对于目标代码的具体修正操作(concrete modifications),形成一个程序修复的具体空间(concrete space)。最后,该技术通过将抽象空间与具体空间求交集,并执行细粒度代码自适应以生成补丁。作者基于上述方案实现了SimFix工具原型,并且在Defects4J数据集上对其进行了评估。结果表明,SimFix成功修复了数据集中的34个bug,其中13个还未曾被现有的技术修复过。 本文的主要贡献如下:

  1. 基于两个搜索空间交集的APR方法:已有补丁的搜索空间和相似代码的搜索空间;
  2. 基于AST类型的抽象空间定义,从已有补丁获取抽象搜索空间的方法;
  3. 基于代码差分从相似代码获取具体搜索空间的方法;
  4. 在Defects4J数据集上进行评估,证明SimFix工具的有效性 。

1 Introduction

通常来说,APR技术以一个存在故障的程序和一组测试用例作为输入(至少存在一个失败的测试用例),生成一个补丁来修复故障(补丁程序至少通过所有的测试用例)。APR技术寻找正常补丁的过程通常被视为一个搜索过程,其中搜索空间由所有可能的补丁组成,而目标则是从整个搜索空间中识别出正确的补丁。而该方法的问题在于,搜索空间通常十分巨大,并且包含许多可用(通过所有测试用例)但不正确的补丁(plausible but incorrect patch),而测试用例并不能区分正确的补丁与这些可用但不正确的补丁。因此,APR技术不仅需要从一个巨大的搜索空间中找到正确的补丁,还需要尽量避免那些可用但不正确的补丁。

为了解决这个问题,许多APR技术采用数据驱动(data-driven)的方法来评估生成补丁的正确性,并且由此缩小搜索空间或者区分搜索空间中补丁的优先级,以便首先搜索最有可能正确的补丁。其数据源通常有两种:

  1. 已有的补丁(existing patches);
  2. 同项目中相似的代码(similar code)。

2 Motivating Example

3 Approach

3.1 Search Space

Concrete Space

首先介绍对目标代码的两种修改:

  1. $Insert(n, t^\prime, i)$:将AST(Abstract Syntax Trees) $t^\prime$插入到目标AST的节点$n$的第$i$个索引的位置;
  2. $Replace(n, t^\prime)$:用AST(Abstract Syntax Trees)$t^\prime$ 替换以$n$为根节点的子树。

注意到,对目标代码的修改不包括删除。这是根据已有的研究做出的选择。

concrete space即上述两种修改所组成的集合。这些修改是通过差分算法得到的。假设上述的修改共有$M$中,则concrete space的大小为$2^M$

Abstract Space

从对concrete space的解释可以看出,其依赖于一个相似的AST (差分算法的要求),即该空间只能通过同项目中源代码相似的部分得到。为使用已有的补丁得到搜索空间,提出了抽象修改和抽象空间(abstract space)。

抽象修改如下:

  1. $INSERT(T)$:插入根类型为$T$的AST;
  2. $REPLACE(T1, T2)$:将根类型为$T1$的子树替换为根类型为$T2$的另一个AST。

可以看出,抽象修改是抽象出了类型,以抹去具体项目的细节。同理,假设上述的修改共有$M^A$中,则concrete space的大小为$2^{M^A}$。

最后得到的Search Space为上述两种空间的交集。

3.2 Modification Extraction

方法中需要在两个空间内提取修改,已有的补丁和相似的代码。

首先,在分析已有的补丁时,得到每个补丁执行的修改。其次,在分析相似的代码时,我们需要得到将错误代码片段转换为捐助代码片段(donor snippet,无错的且和错误代码片段具有较近syntactic distance的代码片段,syntactic distance是描述两个单词语法上关系的标量,文中没有给出工具计算该参数的指标和方法)的修改。两个空间中修改的获得使用了相同的差分算法。该算法以两个AST A和B作为输入,并产生一组从A到B的具体修改。

Differencing Algorithm

算法首先匹配两个AST之间的节点,然后在匹配的过程中提取修改。

两个节点匹配的条件:

  1. 它们具有相同的节点类型
  2. 它们的所有祖先节点都匹配
  3. 或者,可以通过将目标AST中的一些节点插入源AST来满足前两个条件。

匹配过程采取自顶向下的方式。具体地说,算法从两个AST的根节点开始匹配。如果两个节点可以匹配,递归地检查它们的子节点。否则,通过将引用的AST中的一些父节点插入到有故障的AST来检查节点是否可以匹配(条件3)。两个节点匹配后,再检查它们的子节点是否匹配。

在匹配节点之后,获取修改。在匹配的AST中检查以下四个条件,每个条件都会生成一个修改。

  1. 当两个叶节点匹配但值不同时,我们用目标节点替换源节点。
  2. 当两个元组节点(该节点的子节点个数固定)匹配,但对应位置的一对子节点不匹配时,我们将源子节点替换为目标子节点。
  3. 当两个序列节点(该节点的子节点个数不固定)匹配时,我们至少识别出一对匹配的子节点,并根据匹配子节点的相对位置将目标中所有不匹配的子节点插入到源中。
  4. 当源节点与较低层级的目标节点匹配时,生成一个替换,插入匹配目标节点上方的节点。

3.3 Mining Stage

该阶段的输入是一个补丁库,其中每个补丁包含一对未补丁版本和补丁版本。对于每个补丁,我们使用差分算法获得具体的修改,并将其转换为抽象的修改。然后计算每个抽象修改的发生频率。最后,选择出现频率大于阈值$k$的抽象修改,形成搜索空间$S_1$。在evaluation中,我们根据Pareto原理(二八定律,20%的原因导致80%的结果)将$k$设置为搜索空间可以覆盖80%的补丁的值。

3.4 Repair Stage

该阶段包括五个子阶段。

3.4.1 Fault Localization

使用标准故障定位方法确定可能的故障语句的有序列表。理论上,任何可以生成该列表的故障定位方法都可以。在实验中,作者选择了Ochiai算法。此外,我们使用测试净化(test purification)对测试用例进行预处理,以提高故障定位的准确性。

3.4.2 Donor Snippet Identification

对于每个错误位置,将定位与同一项目中的错误代码类似的供体片段。给定一个可能的故障位置,我们将其扩展为一个代码片段,然后找到一组类似的代码片段作为donor进行比较和调整。代码片段指的是,在源文件中的两个行x和y,[x,y]之间的代码片段是包含在x和y行之间的最长语句(statement)序列。

为获取donor代码片段,需要比较两个代码片段之间的相似性。文章定义了三个相似性度量,最后的相似性是三个相似性的总和。

Structure Similarity

通过AST的结构衡量相似度。具体做法是,从每个代码片段中提取一个向量,其中向量中的每个元素表示AST节点的一个特性。例如,一个元素可以是代码段中for语句的数目,另一个元素可以是代码段中算术运算符的数目(+、-、*、/、%)。然后我们计算两个向量之间的余弦相似度(cosine similarity)。

Variable Name Similarity

通过变量的名字衡量相似度。将使用驼峰命名法的变量拆分,得到若干单词,然后对两个得到的不同单词集合做相似性比较。

Method Name Similarity

通过方法的名字衡量相似度。和变量名相似度的计算方法相同。

3.4.3 Variable Mapping

对于每个供体代码片段,将供体代码片段的变量映射到错误代码片段,构建一个用于代码适应的变量映射表,并用相应的变量替换供体代码段中的所有变量。为获取变量映射表,采用三种相似性度量。

Usage similarity

通过如何在代码段中使用变量来衡量相似度。具体来说,首先使用一个使用序列(usage sequence)来表示变量的使用方式。给定一个变量,我们执行AST树的后序遍历,并为变量的每次出现打印父节点类型。得到的序列表示变量所使用的表达式。之后,根据最长公共子序列计算两个使用序列的相似性获取变量的相似性。

Type similarity

该阶段保证变量映射前后的类型兼容性。类型兼容性,即当一个变量在供体代码片段中用作左值时,我们需要确保目标变量的类型是原始变量的父类,变量在供体代码段中被用作右值时,我们需要确保目标变量的类型是原始变量的子类。理想情况变量映射时,应该强制满足上述两个条件。但是,由于在当前阶段不知道哪些代码将从代码片段中被重用,因此本阶段只使用类型相似性来度量它们类型的兼容性程度。具体地说,我们将类型相似性定义为一个二进制值。当一个变量是另一个变量的子/超类型时,它们的相似性为1,否则为0。

Name similarity

和STEP 2中衡量变量相似性使用相同的方法,只不过这里的考虑范围是两个单独的变量。在计算了每对变量之间的相似性之后,使用贪心的策略选择具有最高相似性的变量对做映射,直到没有剩余为止。

3.4.4 Modification Extraction and Intersection

本阶段将给定的供体代码片段与错误的代码片段按相似性的降序逐一进行比较,并使用代码差分算法提取具体修改。这组修改构成修改集合$S2$。然后,对$S1$和$S_2$取交集,得到了一组具体的修改集合。

3.4.5 Patch Generation and Validation

在前一阶段中获得的修改集定义了一个数量已经被减少的搜索空间。通过对空间中的补丁进行排序,并逐个验证它们,在通过所有测试的补丁集合中得到一个补丁。排序的规则如下(更靠前的规则代表更高的重要级别):

  1. 包含一致修改的补丁优先级较高。一致修改是指要求同时在不同位置对变量进行相同更改的修改。这是由于,当一个变量被替换为另一个变量时,在其他情况下也应该被替换为同一个变量。

  2. 修改较少的补丁优先级较高。

  3. 替换次数多的补丁的优先级高于插入次数多的补丁。

第2、3两个规则是由前人的工作启发得到的。

4 Evaluation

4.1 Experiment Setup

64位Linux服务器,配备2个Intel(R) Xeon CPU以及128GB的内存。对于每一个漏洞分配 2个 CPU core 和 8GB RAM,超时时间设置为5小时。对于生成的漏洞补丁,手工验证其正确性,和Defects4J中提供的标准补丁作对比。

Defects4J中包含的漏洞等相关信息如下:

已有补丁的来源如下:

4.2 Research Questions and Results

RQ.1:各种抽象修改的频率如何?

从表中可以看到,前三个最常见的修改是插入一个if语句、替换一个方法调用以及插入一个方法调用。这一结果与已有的研究的结果一致。

为了进一步了解已有的补丁集是否足够大,能够覆盖一组具有代表性的修改,作者分析了不同项目数下的修改分布:

不同的折线代表所采用的补丁集的组合。从图中可以看出,不同补丁集的百分比非常接近。这些结果表明数据集足够大。此外也能说明抽象空间可以从一小组补丁中挖掘出来,并在项目之间很好地进行共用。

RQ.2:SimFix在Defects4J上的的修复效果如何?

括号外的数字表示被补丁集合中第一优先级补丁修复的错误数,括号内的数字表示补丁集合中所有补丁修复的错误数。缺失的数字用-或直接省略。

Simfix总共生成了22个不正确的补丁和34个正确的补丁,精度达到60.7%。

RQ.3:通过结合已有的补丁,SimFix对搜索空间的精简效果如何?

RQ.4:不考虑删除操作对于自动化程序修复的影响如何?

假如不和抽象搜索空间取交集(SimFix-A版本),那么所有的候选修改将为2.3倍,所花费的时间也变为2倍。

假如对程序的修改将删除包括如搜索空间,并且也采用相同的差分算法计算出删除的修改,则记为SimFix-D版本。

以下是三个版本的修复效果对比:

可以看到,另外两个版本修复的精度和数量都有所下降。其原因是相同的,被扩大的搜索空间包含更多能通过测试(但不正确)的补丁。

RQ.4:在分析代码相似度的时候采用了更细粒度的比较,即采用AST子树的级别的效果如何?

作者手动分析了用细粒度方法生成的补丁,以了解如果只允许statement级别的代码重用,那么还有多少bug可以修复。在检查了所有补丁之后,我们发现修复的bug少了17个。结果表明,细粒度代码的差异化和重用对方法的有效性有显著的贡献。