Page 44 - 《软件学报》2021年第9期

2668 Journal of Software 软件学报 Vol.32, No.9, September 2021

当给定一个缺陷程序,修复工具:(1) 首先通过静态分析、动态测试等技术手段确定程序中可能的缺陷代码
位置;(2) 然后,每次选择一个候选出错位置,使用补丁生成技术尝试生成修复补丁;(3) 最后验证生成的修复补
丁的正确性.基于静态分析检测的修复方法由分析工具预定义的规则检查补丁是否正确,而基于动态测试的修
复方法要求修复补丁可以通过所有的测试.然而,修复工具可能产生多个补丁修复同一个缺陷,为了提升修复的
效率和补丁的质量,通常在验证补丁之前或之后应用启发式规则或统计分析的方法对候选的补丁进行过滤和
排序.修复工具针对候选出错位置依次迭代上述修复过程,直到找到正确的修复补丁或者达到终止条件,如运行
超时等.
在上述修复过程中,缺陷定位的准确率会影响缺陷自动修复工具的修复结果.Liu 等人 [11] 通过实验表明:相
比于使用自动化缺陷定位方法,提供准确的代码出错位置使得自动修复工具 TBar 多修复了 31 个程序缺陷(提
升了 72.1%).因此,提升缺陷定位的准确率可以有效提升已有修复工具正确修复缺陷的数量.有很多相关的研究
致力于提升定位的准确率,提出了各种不同的缺陷定位技术.目前,在缺陷自动修复领域使用比较多的缺陷定位
技术存在两类:基于动态测试执行 [12−15] 以及静态程序分析的方法 [16−19] .基于动态测试执行的定位技术根据程序
中的未通过测试以及通过测试的动态运行时特征对代码候选出错位置进行排序,比如基于程序频谱的定位技
术.基于静态分析的方法通过预定义的规则描述程序的规约,然后通过程序分析技术判断程序是否满足给定规
约.缺陷定位是一个独立的研究领域,本文对其不进行详细介绍,更多关于定位的相关技术介绍请参考最新的相
关综述论文 [20] .
补丁生成模块负责生成缺陷修复代码,是自动修复方法的核心.根据上文的介绍,定位准确率会影响修复结
果.事实上,缺陷定位对修复的整体影响依然十分有限,即使给定正确的代码出错位置,已有的自动修复方法也
仅能正确修复小部分(<20%)程序缺陷 [11] .因此,目前的自动修复方法所面临的核心挑战依然是如何正确高效地
生成修复补丁.最新的研究也是主要针对该模块进行优化和创新.因此,本文接下来的综述部分将根据修复工具
所使用的补丁生成策略进行分类.如图 3 所示,本文将缺陷修复分为 4 大类,具体内容将在第 2 节进行详细介绍.
补丁过滤排序及验证模块是缺陷修复过程中的最后一步,也是保证补丁质量的关键一步.由于修复中使用
的程序规约通常是不完备的,例如非精确的静态分析结果或不完备的测试集(弱测试集问题 [21] )等.因此,即使不
正确的修复补丁也有可能会通过验证(在第 3 节,我们会更详细地讨论补丁的质量问题),对候选的修复补丁进行
过滤 [22,23] 和排序 [24] ,成为提升补丁质量的一个有效手段.但由于目前修复工具主要面临的挑战是难以生成正确
的修复补丁,所以过滤和排序策略仅是对自动修复方法效果的进一步优化,并不能从根本上解决生成正确补丁
难的问题.
综上,本文主要针对软件缺陷自动修复技术中的补丁生成模块进行详细的综述,对于缺陷定位以及补丁过
滤排序及验证模块不做展开讨论(本文的局限性).读者可以参考相关的综述论文 [1−6,20] 了解更详细的内容.
(2) 修复效果评价指标
对于自动修复工具生成的修复补丁,我们将其分为以下 3 种类型:错误补丁(incorrect patches)、似真补丁
(plausible patches)和正确补丁(incorrect patches).其中:错误补丁指不能通过验证模块验证的补丁;似真补丁可以
通过验证,但由于改变了程序的原始语义而并非正确;正确补丁即语义正确的修复补丁.在度量缺陷自动修复工
具的修复效果时,目前广泛使用的评价指标是召回率(recall)和准确率(precision).其定义如下:
召回率 = | 正确补丁修复的缺陷 | ,准确率 = | 正确补丁修复的缺陷 | .
| 所有缺陷 | | 正确补丁或似真补丁修复的缺陷 |
召回率越高,反映自动修复工具的补丁生成能力越强;准确率越高,反映修复工具生成补丁的质量越好.在
实际应用中,上述两个指标在某种程度上相互制约.修复的数量增加,代表修复工具有能力生成更多种类的补
丁,从而导致生成似真补丁的可能性增大而降低准确率.因此,自动修复技术通常需要在两者中进行权衡.例如,
已有的自动修复方法通过限定修复缺陷的类型 [25] ,降低生成似真补丁的概率,提升修复准确率.这样的修复技术
在原理上就限制了其补丁生成能力.本文在第 2 节中针对具体修复技术进行相关介绍.除上述两个通用评价指
标,一些论文中也会采用上述指标的变体,比如针对语法等价的补丁的召回率和准确率(即要求正确补丁与目标