软件缺陷的自动修复技术之探讨

针对自动化修复软件缺陷，工业界与学术界设计开发了各种软件测试、分析工具来发现和定位软件错误。例如，并行程序由于资源访问和调度设计的不足，可能造成死锁等与并行执行有关的缺陷。为此，研究者设计了专门的方法来检测这种缺陷。又如，软件库提供了成千上万的类和函数，开发人员可能由于使用不当而造成软件缺陷。研究者还研究了如何从软件库中获取应用程序接口（API）使用规约，并据此检测了与软件库使用有关的缺陷。

自动软件缺陷修复是近年来另一个新兴的研究热点。该方法首先通过缺陷定位技术，定位了软件中带有缺陷的代码行。通过执行测试用例集，计算代码行的可疑程度，并将最可疑的代码行认为是缺陷代码行。缺陷定位之后，自动修复软件方法通过预先定义的一系列修复算子和遗传算法经典的交叉变异编辑操作，生成候选修复集合；执行候选修复集合，可以得到每个候选修复的适应值，并根据适应选取下一代候选修复。通过迭代上述过程，指导某个候选项通过所有测试用例，即可被认为是最后的修复。

上述自动缺陷修复过程涉及到的技术有：

1. 缺陷定位技术，基于统计的频谱缺陷定位（Spectrum-Based Fault Localization，SBFL）是一种广为应用的技术。它通过先运行一组测试用例，将每一个语句通过和失败的次数记录下来，然后计算每一个语句的缺陷可疑值。一般来说，一个语句出现在失败测试用例中的次数越多，可疑值就越高，则也更有可能含有错误。最后输出的一组是按照可疑值排序的语句，排名最高的就是最有可能出错的语句。一般认为较好的自动缺陷定位技术并不一定能与好的自动缺陷修复技术实现互补。在传统的缺陷定位场景中，只要定位好缺陷，就可以修复这些缺陷，并不涉及迭代。而自动缺陷修复与缺陷定位则是一个交叉迭代的过程，如何为特定的缺陷修复技术设计相应的缺陷定位技术依然是一个值得探讨的问题。

2. 自动修复算子，现有的自动修复技术算子大致可以分为基于测试的变异修复算子和基于约束的程序合成算子。以自动修复算子为例，它以测试用例为指导，通过不断对缺陷代码进行变异操作，得到新的补丁代码，迭代该过程直到获得可以让所有测试都通过的补丁。一般的修复算子有变异操作和交叉操作两种。变异操作通过将语句整句删除、在语句后插入新的语句和程序中任意语句交换三种方式修改缺陷代码，在每一次变异中随机执行三种方法之一。交叉操作以两个代码段作为输入，互换交叉点之后的代码，形成新的后代。比如有输入[P1，P2，P3，P4]和[Q1，Q2，Q3，Q4]，交叉点为2，则会得到子代[P1，P2，Q3，Q4]和[Q1，Q2，P3，P4]，每个子代码都会得到双亲的信息。修复算子的丰富程度决定了自动修复方法的潜力。为了获取更为丰富的修复算子，金（Sung Kim）等人叫通过分析开源软件的修复历史来获取有效的修复算子，并获得了较好的结果。

3. 修复算法，修复算法决定了是否能在一定时间限制内生成正确的修复，现有修复算法主要建立在遗传算法技术或者随机搜索技术之上。其中，韦默（Weimer）等人提出的方法为典型的基于遗传算法的技术，首先通过错误定位技术找到可能的错误代码，并通过对错误代码进行随机变种生成第一代候选修复集合。在对候选修复集合执行测试用例以计算每个候选修复的适应值，并根据适应值选取双亲进行交叉和变异以得到下一代修复集合。将这个过程持续下去，直到某个修复通过了所有测试用例，则可认为程序修复结束。由于遗传算法的效率较低，基于遗传算法的方法一般花费时间较长。

齐（Qi）等人因提出的使用随机算法也可以找到有效的修复补丁，并且速度比基于遗传算法的方法更快。该算法在搜索阶段则直接使用随机的变异操作修改错误代码，得到候选修复补丁，并通过执行测试用例检查该补丁是否有效。一旦测试用例失败，就判定其为无效补丁，不再执行其余的测试。因为该算法不需要执行所有的测试以计算适应值，所以搜索速度得以大幅提升。此外，该算法还可以通过调整测试用例的执行顺序让可能失败的测试更早地被执行，以提高每一轮的执行速度。

上述两种方法都以测试用例的执行结果作为判断修复补丁是否有效的依据。在实验设置上，两种方法在补丁生成和有效性判定上都采用相同的测试用例集合，存在潜在的过度适应问题。例如，最近的一项研究指出在之前一项代表性研究中，虽然生成的修复能够通过测试用例，但并没有真正修复缺陷。这是后继的研究者应当着力避免的问题。

开源软件对软件缺陷自动修复的价值：

1. 提升缺陷修复方法

开源社区的开发者在地理上非常分散，为了帮助处在不同地理位置的开发者共享开发代码，开源社区一般通过SVN、CⅤS、Git等服务器分享代码这些服务器提供了大量软件的修改记录。通过分析这些记录，可以进一步提升已有的自动软件缺陷修复技术。获取高效修复算子是一个关键的问题，决定了自动软件缺陷修复技术对目标软件的修复能力。大多数情况下，研究者通过经验直接得到修复算子，不足之处在于难以获取全面的修复算子，也很难评估其修复能力。在这一点上，开源社区可以提供大量缺陷修复的实例，通过分析人工修复实例，有可能获取高效的修复算子。例如，金（Kim）等人通过分析上千例人工修复事例，从中得到了十个最为常见的修复算子，实验结果表明比之前方法里的算子更有效。又如，马丁内斯（Martinez）和孟博鲁斯（Monperrus）从人工修复中自动学习修复模型，描述了对各种代码实体（函数名和变量名等）实施各种修复操作的概率。实验结果表明，得到的修复模型可以修复更为复杂的缺陷。除此之外，开源软件里的修复历史对修复算法也有指导作用。例如龙（Long）和李纳德（Rinard）从已知的修复历史里定位与待修复缺陷有关的修复，然后利用这些已知的实例指导缺陷修复。高（Gao）等人则通过分析开源社区论坛上的相关讨论来指导缺陷修复过程。

2. 缺陷修复方法潜力评估

虽然自动软件缺陷修复技术能灵活修复未知缺陷，但由于刚刚起步，现有工具大都是实验原型，修复能力还非常有限。开源软件里积累了大量的缺陷修复实例，通过分析这些缺陷修复的特性，再与已方法的原理比较，就能够估计出有多少缺陷潜在被修复。例如，根据钟（Zhong）等人的工作，大约有20%的缺陷可能被自动修复。通过比对开源软件中的缺陷修复操作和自动缺陷修复方法的框架，他们为该方向的进一步完善提供了较为全面的建议。