ACM通信

研究突出了

基于进化计算的程序自动修复

作者:Westley Weimer, Stephanie Forrest, Claire Le Goues, ThanhVu Nguyen
ACM通讯，2010年5月，Vol. 53 No. 5, 109-116页
10.1145/1735223.1735249
评论

有许多检测和减轻软件错误的方法，但很少有通用的方法来自动修复一旦发现的错误。本文重点介绍了近年来将程序分析方法与进化计算相结合来自动修复现成的遗留C程序中的错误的工作。该方法将有bug的C源代码、一个演示bug的失败测试用例，以及少量编码程序所需功能的其他测试用例作为输入。修复程序不依赖于正式规范，使得它适用于广泛的现有软件，这些软件很少有正式规范。

回到顶部

1.简介

修复bug是一个困难、耗时和手工的过程。一些报告将软件维护(传统上定义为在系统交付后对其进行的任何修改)置于典型软件项目总成本的90%之上。²²修改现有的代码，修复缺陷，以及开发软件是这些成本的主要部分。¹⁹突出的软件缺陷的数量通常超过了可用的资源来解决它们。成熟的软件项目被迫同时带有已知和未知的bug¹³因为他们缺乏处理每个缺陷的开发资源。

本文描述了如何将程序分析方法与进化计算相结合来自动修复现成的遗留C程序中的bug。遗传规划(GP)是一种受生物进化启发的计算方法，它演化出针对特定任务的计算机程序。¹²GP维护单个程序的种群，每个程序都是任务的候选解决方案。每个个体的适应性通过任务特定的适应性函数来评估，并选择适应性最高的个体进行继续进化。计算模拟生物突变和交叉产生高适应性程序的变化，这个过程迭代，直到找到一个高适应性程序。GP已经解决了一系列令人印象深刻的问题(例如，Schmidt和Lipson²¹)，但它还没有被用于开发现成的遗留软件。随着2008年遗传编程野外指南注意到，“虽然人们通常将GP描述为不断进化的程序，但GP通常并不用于进化人类通常用于软件开发的图灵完备语言中的程序。相反，更常见的做法是用一种更受约束、通常是特定于领域的语言来发展程序(或表达式或公式)。”(波里et al。¹⁸引用Orlov和Sipper的话¹⁵)．

我们的方法假设我们可以访问C源代码，一个执行要修复的错误的负面测试用例，以及几个编码程序所需行为的正面测试用例。C程序表示为抽象语法树(AST)，其中每个节点对应于程序中的一个可执行语句或控制流结构。有了这些输入，修改后的GP就演变出了一个候选修复，可以避免负面测试用例失败，同时仍然通过正面测试用例。然后我们使用结构差异¹和δ调试²⁵技术来最小化修复的大小，提供一个紧凑的人类可读的补丁。

像GP这样的进化算法的一个重大障碍是，它必须采样无限大小的搜索空间才能找到正确的程序。为了解决这个问题，我们引入了两个关键的创新。首先，我们限制算法，使所有通过突变和交叉引入的变化在程序的其他部分重用结构。从本质上讲，我们假设即使一个程序在一个位置缺少重要的功能(例如，null检查)，它也可能在另一个位置显示正确的行为，可以复制和调整以解决错误。其次，我们限制突变和交叉的遗传操作只在程序中与错误相关的区域进行操作，特别是在执行路径上产生错误行为的AST节点。该算法不是搜索所有ast的空间，而是搜索表示一条执行路径的节点的更小空间。在实践中，错误的执行路径至少比AST的唯一节点少一个数量级，结合这些见解，我们演示了11个C程序的自动修复，总计63,000行代码。

Forrest等人报告的主要贡献。⁸和Weimer等人。²⁴是:

• 基于描述所需功能的测试用例来找到并最小化程序修复的算法。这些算法是通用的，因为它们可以修复许多类的bug。
• 一种将GP应用于程序修复的新颖高效的表示和操作集。这是第一个公开的作品，展示了GP如何修复未注释的遗留程序。
• 实验结果表明，该方法可对11个多域生产程序中的多类缺陷进行修复。
• 实验分析了算法性能如何随问题规模的增长而增长，以及进化算法中不同组件的相对贡献。

在本文的其余部分中，我们首先概述了我们的技术方法(第2节)，并举例说明了微软Zune媒体播放器最近的一个bug(第3节)。在第4节中，我们报告了几个基准程序的修复结果，并研究了算法性能如何随问题的大小而变化。在第5节中，我们将工作放在以前的贡献的背景下，在第6节中讨论我们的经验、注意事项和对未来工作的想法，在第7节中结束。

回到顶部

2.技术方法

我们的方法的核心是一种进化算法，它通过选择性地搜索相关程序变体的空间来修复程序，直到发现一个可以避免已知缺陷并保留关键功能的变体。我们使用一种新的GP表示，并对必要修复的可能性质和位置进行假设，提高了搜索效率。对于一个有缺陷的程序，有几个问题需要解决:

1. 它哪里做错了?我们取一组负面测试用例这是故障的特征。输入程序不通过所有否定的测试用例。
2. 它应该做什么?我们取一组积极的测试用例这就编码了功能需求。输入程序通过所有正测试用例。
3. 我们应该在哪里换呢?我们赞成在执行负面测试用例时改变访问的程序位置，并避免在执行正面测试用例时改变访问的程序位置。
4. 我们应该如何改变它?我们插入、删除和交换程序语句，并使用现有的程序结构控制流。我们倾向于基于现有的程序结构进行插入。
5. 我们什么时候结束?我们将通过所有积极和消极测试用例的第一个变体称为主要修复。我们尽量减少它和原始输入程序之间的差异，以产生最后的修复。

为了展示修复过程，我们首先描述我们的程序表示(第2.1节)和故障定位(第2.2节)选择。然后，我们详细介绍了基于gp的修复策略(章节2.3)，讨论了修改表示的遗传操作(章节2.4)，以及使用测试用例评估修改结果的适应度函数(章节2.5)。最后，使用后处理步骤来最小化所产生的修复(章节2.6)。

2.1.表示

有许多被普遍接受的用于表示程序的结构，例如控制流图(CFGs)和抽象语法树(ast)。我们之所以选择ast，是因为ast可以无损地表示所有的结构化程序，而GP中对树形运算的研究也很深入。ast可以在多个抽象或粒度级别上表示，我们的程序表示反映了表达能力和可伸缩性之间的权衡。例如，C程序包含这两者语句，例如条件句"If (!p) {x = 0;}”,表达式，例如"0”或“p (!)”。对于可伸缩性，我们将语句视为基本单元或基因。因此，我们从不修改“p (!)“成”(p | | error_flag)因为这样做需要改变表情的内部结构。相反，在操作复合语句时，我们操作整个AST子树。例如，我们可以删除整个"如果……语句，包括它的then-branch和else-branch子语句。最后，我们从不直接修改底层控制流指令，例如休息,继续，或转到，尽管它们周围的语句可以修改。

2.2.故障定位

我们假设软件缺陷是局部的，修复一个缺陷不需要改变整个程序。这种假设通过限制对程序中可能包含缺陷的部分的代码更改来缩小搜索空间。我们将修改偏向于在运行负面测试用例时访问过但在运行正面测试用例时没有访问的语句节点。我们为每个语句分配一个惟一的ID，并让程序打印访问的每个语句的ID，从而找到这些信息。¹⁴这使得我们的方法可以扩展到更大的程序大小。例如，当阿特程序总共包含8068个语句节点(表1)时，我们利用该故障定位信息将搜索偏向34个可能有影响的语句节点，减少了两个数量级以上。

形式上，每个程序变体都是一对，包括:

1. 一个抽象语法树包括所有的表述年代在程序中。
2. 一个加权路径通过这个项目。加权路径是一个对列表年代，w_年代，每个都包含程序中访问的否定测试用例的语句以及该语句的相关权重。

默认的路径的权值如果一个语句在否定的测试用例中访问，而在任何肯定的测试用例中没有访问，则该语句的值为1.0。如果在阳性和阴性的测试案例中都访问它，它的权重为0.1。所有其他语句的权值都是0.0。权重表示对语句与bug的相关性的初步猜测。该方法与故障定位的联合/交叉模型有关。^20.的加权路径长度是加权路径上各语句权重的和。这个标量给出了搜索空间复杂度的一个粗略估计，并与算法性能相关(第4节)。我们将在第6节返回到故障定位问题。

2.3.遗传规划

我们使用GP来维护程序变体的种群。每一种变体，有时被称为个人，表示为带有加权路径(故障定位信息)的AST。我们通过两种遗传操作来修改变异，突变和交叉。突变会随机改变加权路径上的节点，而交叉则会在两个ast之间交换子树(详见下文)。每次修改都会产生一个新的AST和加权程序路径。通过编译AST并在测试用例上运行它来评估每个变体的适合度。它的最终适应度是它通过的正测试和负测试用例的加权总和。一旦每个个体的适合度被计算出来，a选择阶段删除人口中排名最低的50%。^一个新种群的形成是通过将剩余的高适应度个体与原程序进行第一次交叉。每个交叉都会产生一个子节点。我们将子元素添加到种群中，并保持父元素不变，保持种群大小不变。最后，所有存活的个体都发生了变异。

修复过程会在找到通过所有正的和负的测试用例的候选解决方案，或者当它超过预设的代数时终止。通过所有测试用例的第一个变体是主要维修。

2.4.遗传算子

如上所述，我们将GP算子应用于给定的变体，从而产生新的程序变体，从而探索可能修复的搜索空间。键操作符是突变，它对个体进行随机改变。由于我们表示的原始单位(基因)是语句，突变比其他进化算法中使用的简单位翻转更复杂。只有加权路径上的语句才受变异算子的影响。考虑加权路径上的每个位置的突变，其概率等于其路径权值乘以a全球突变率。被选为突变的语句随机地服从其中任何一种删除(删除整个语句及其所有子语句:年代{}),插入(在它之后插入另一个语句:年代｛年代；年代”;}),或者交换(年代年代虽然年代＇年代)．注意，在我们的方案中，单个突变步骤可能在加权路径上包含多个语句级的突变操作。

操作变量的第二个操作是交叉，在GP中交换两个个体之间随机选择的子树。虽然我们最初的实验使用了更复杂的交叉形式，但我们已经看到，结果不依赖于使用的特定交叉算子。⁸在每一代中，每一个幸存的变种都要经历交叉。

最后，还有许多其他的C程序组件没有被GP操作符所涉及，比如数据类型定义以及局部和全局变量声明。因为它们永远不会出现在加权路径上，它们永远不会被突变或交叉所改变。这可能会限制修复的表达能力:如果修复漏洞的最佳方法是改变数据结构定义，GP就不会发现这个修复方法。例如，一些程序可以通过重新排序数据结构字段或改变程序控制流来修复;我们的技术找到了第二次修复。另一方面，忽略变量声明会导致格式不良的变量出现问题。由于突变和交叉的限制，GP永远不会生成语法错误的程序(例如，它永远不会生成不平衡的括号)。但是，它可能会将变量的使用移到声明的作用域之外，从而导致不进行类型检查，从而无法编译的语义格式错误的变量。

2.5.适应度函数

在全科医生,健身函数是用于评估变量的目标函数。个人在程序修复任务中的适应性应该评估程序在避免程序错误的同时仍然做“它应该做的所有事情”的情况。我们使用测试用例来度量适应性。对于我们的目的，a测试用例由程序的输入(例如，命令行参数，从磁盘读取的数据文件等)和甲骨文比较器函数，对所需的响应进行编码。一个程序P据说通过一个测试用例T如果oracle对程序的输出满意:T_甲骨文（P（T_输入)) =。测试用例可以检查纯功能正确性之外的其他行为(例如，程序可能需要在给定的时间范围内产生正确的答案，或者避免无限循环)。这类测试的成本高达软件生命周期总成本的45%，¹⁷在软件工程领域，寻找覆盖程序的所有部分和所有需要的行为的测试用例是一个困难但研究充分的问题。

我们将缺陷演示输入和它们的异常输出(即，我们想要修复的bug)称为负面测试用例。我们使用程序现有测试输入和oracle的一个子集来编码程序的核心功能，并将它们称为积极的测试用例。有许多技术可以用于识别程序中的错误，包括静态的(例如Ball和Rajamani)^3.霍夫梅耶和普¹⁰)和动态(如Forrest et al.;⁷和Liblit等人。¹³)．我们假设一个错误已经被识别，并且与至少一个否定的测试用例相关联。

适应度函数接受程序变体(基因型)，将内部表示编译为可执行程序，并针对一组阳性和阴性测试用例运行它。它返回通过的测试用例的加权和。这个总和是加权的，因此通过负面测试用例的价值至少与通过正面测试用例的价值相同。直觉上，这一权重奖励了寻找可能的修复方法。未编译的程序被赋值为适应度0。

2.6.减少维修

因为GP可能会引入不相关的更改，我们使用程序分析方法从初级修复中删除不必要的编辑。例如，除了修复之外，GP可能会产生死代码(x = 3;x = 5,)或者调用不相关的函数。我们在后处理步骤中使用树形结构的差分算法和增量调试技术来生成一个简化的补丁，当应用到原始程序时，会使它通过所有的测试用例。

使用树形结构差分,¹我们将主要修复视为对原始程序的一组更改。每一个改变是一种树形结构的操作，例如“取根在位置4的AST的子树，并移动它，使其成为位置6的节点的第5个子节点”。我们试图找到一小部分变更，以生成仍然通过所有测试用例的程序。

让C_p= {c₁、……c_n}是与主要修复相关的一组更改。让测试（C) = 1，如果程序应用的变化得到C对原程序通过所有正、负测试用例;让测试（C) = 0否则。一个one-minimal C子集我C_p是这样的集合吗测试（C) = 1和c_我C．测试（C\ {c_我}) = 0。也就是说，一个最小子集产生的程序通过了所有的测试用例，但是删除任何额外的元素会导致程序至少失败一个测试用例。检查一个集合是否有效涉及到适合度评估(调用测试)．

我们使用三角洲调试²⁵有效地计算来自主要修复的一个最小子集的更改。增量调试在概念上类似于二进制搜索，但它返回一个集合，而不是单个数字。直观地，从{开始c₁、……c_n}，它可能会检查{c₁、……c_{n/ 2}}:如果这一半的更改足以通过测试, {c_{1 +n/ 2}、……c_n}可以丢弃。当不再有大小子集时n/2可以去掉，子集的大小n/4被考虑移除，直到最终大小为1的子集(即单个更改)被测试。通过蛮力找到整体最小有效集可能涉及到O（2ⁿ)评估;增量调试在中找到一个最小子集O（n²)．^{25, 12号提案}然而，我们通常在实验中观察到线性数量的测试。这个较小的更改集将作为最终的修复以标准程序补丁的形式。在我们的实验中，最终修复通常比初次修复至少小一个数量级。

回到顶部

3.插图

2008年12月31日，微软Zune媒体播放器的一个bug被广泛报道，导致它们冻结。^b错误是以下程序片段中的一个bug:^c

当输入天数的值是闰年的最后一天时(例如10,593，对应于2008年12月31日)，程序将在第3-16行进入无限循环。

现在我们来回顾一下这个程序的修复过程。我们首先生成它的AST并确定加权路径，使用行号表示语句id。阳性测试用例zunebug(1000)访问行1- 8,11 -18。阴性测试用例zunebug(10,593)访问第1-16行，然后无限重复第3、4、8和11行。

对于这个例子，负面测试用例由输入366和10,593组成，它们会导致无限循环(而不是正确的值1980和2008)，而正面测试用例是输入1,000、2,000、3,000、4,000和5,000，它们会产生正确的输出1982、1985、1988、1990和1993。

我们考虑一种变体，V，它被初始化为与原始程序相同。在第1代中，两个操作发生了变化V:条件句。If(天> 366){天-= 366;年+ = 1;}插入到原始程序的第6行和第7行之间;而"天- = 366插入到第10行和第11行之间。注意，第一次插入不仅包括如果而是整个子树。这将产生以下代码片段:

这个修改后的程序通过了阴性测试用例366(1980年)和一个阳性测试用例1000。

变体V在第2、3、4、5代中没有变化，但在第6代中，它通过以下操作进行了突变:删除610行，和"天- = 366插入第13行和第14行之间:

在这一点上,V通过所有测试用例，搜索结束V作为初级修复。调用最小化步骤是为了丢弃不必要的更改。与原始程序相比(并使用原始程序中的行号)，有三个关键变化:c₁= "天- = 366从第6行删除;c₂= "天- = 366“插入第9行和第10行之间;而且c_3.= "天- = 366插入第10行和第11行之间。只有c₁而且c_3.是通过所有测试的必要条件，所以要改变吗c₂删除，产生最后的修复:

平均而言，构建和最小化这里所示的Zune片段修复需要我们的原型总共42秒，包括编译和评估一套5个阳性和2个阴性测试的变体的时间。

回到顶部

4.结果

到目前为止，我们已经从总共2.3MLOC的20个程序中修复了共计186kLOC模块中的20个缺陷(这里没有全部显示)。我们修复了8个类的缺陷:无限循环、分割错误、堆缓冲区溢出、非溢出拒绝服务、整数溢出、无效异常、错误输出和格式字符串漏洞。修复平均需要1428秒，其中大部分时间用于执行平均3903次适合度评估。在表1，我们总结了Forrest等人报告的11个基准测试程序的结果。⁸和Weimer等人。²⁴基准程序、测试用例、GP代码和用于生成和再现这些结果的支持基础设施可以在以下网站获得:http://genprog.adaptive.cs.unm.edu/．

在我们所有的实验中，有一个标准试验使用以下设置。种群大小为40,GP最多运行20代。前10代的全球突变率为0.06。如果没有发现初级修复，当前种群被丢弃，全局突变率减半到0.03，并且，如果可能，加权路径被限制为仅在阴性测试用例期间访问的语句，并且GP被运行10个额外的代。这些结果表明，GP可以自动发现生产C程序中各种记录在案的bug的修复。

如果发现初步修复，试验终止。我们对每个程序进行了100次试验，记住适合度，在一次试验中，两个具有不同ast但源代码相同的人不会被评估两次。类似地，未经更改复制到下一代的个体不会被重新评估。

一旦确定了主要修复，将其最小化到最终修复的过程是非常迅速的，平均需要不到5秒。最后的修理，表示为补丁格式，大小从四行不等(例如:zune:一个插入，一个删除，和一个上下文位置行为每次编辑)到11行(例如，看起来颇具4.3)．

并不是所有的试验都能成功修复;在这里显示的修复中，平均60%的试验产生了初步修复。中的“时间”和“健康评估”两栏表1衡量一次成功的试验所付出的努力。由于所有试验都是独立的，许多试验可以并行进行，当第一次成功试验产生初步修复时终止。此外，对于给定的变量，不同变量的适应性和不同测试用例的结果都可以独立评估，这使得我们的方法很容易在多核架构上并行化。的测量表1是在一个四核3 GHz的机器上制作的。

创建修复所需的总时间中，超过一半花费在通过测试用例运行已编译的变量来评估适应性上。对于具有大型测试套件的程序，这种成本可能相当大。因此，我们的方法的可扩展性的一个主要因素是必须找到修复的这种适应性评估的数量。所需的适应度评估次数与搜索空间的大小和搜索策略的有效性有关:每个适应度评估代表一个探针。我们假设加权路径的大小可以很好地表示搜索空间的大小;回想一下，我们只修改沿着路径的语句(第2.2节和2.4节)。图1显示了对这一关系的实证调查的结果，绘制了产生每18个修复所需的平均适应度评估数相对于其加权路径的长度(注意对数尺度)。虽然在得出强有力的结论之前需要更多的数据点，但该图表明，适合度评估的数量，因此搜索时间，可以按幂律的形式缩放y＝斧头^b在哪里b为最佳拟合线的斜率(0.78)。这表明寻找修复的时间与固定数量的测试用例的加权路径的大小接近线性。

我们的方法也无法修复一些缺陷，包括那些需要同时进行许多编辑或更改的缺陷，而这些修改不能直接在语句级别进行(例如，matmul (b)应该是matmul (a, b))．我们在第6节回到修理质量的问题。

回到顶部

5.相关工作

阿库里²提出了使用GP自动修复软件bug的想法，Orlov和Sipper尝试了进化Java字节码。¹⁵然而，我们的工作是第一次报告了带有真实bug的真实程序的实质性实验结果。基于搜索的软件工程(SBSE)领域⁹为软件测试使用进化的和相关的方法，例如，开发测试套件，改进软件项目管理，并努力评估发现安全违规，在某些情况下重构或重新设计大型软件库。在SBSE中，GP技术中的大多数创新都涉及到新的适应度函数类型，并且很少强调新的表示和操作符，比如这里探讨的那些。

我们的方法自动修复程序而不需要说明。在之前的工作中，我们开发了一种能够很好地修复规范程序的自动算法。²³然而，正式的规范并不总是可用的(例如，这里修复的任何程序都没有正式的规范可用)，所以目前的工作集中在测试用例上，以检查和确保正确性。

跟踪和故障定位，最小化和解释(如琼斯和哈罗德¹¹)项目还旨在阐明错误和简化调试。这些方法通常将错误症状缩小到几行(一个潜在原因)。我们的工作通过提出混凝土修复来扩展这项工作。此外，这些其他算法通常仅限于给定的跟踪或源代码，因此永远不会将错误的“原因”本地化为丢失的语句或建议移动语句。我们的方法可以推断应该添加、删除或交换的新代码:11个修复中的6个表1必需的插入或交换。

Demsky et al。⁵提出了一种数据结构修复技术。给定数据结构一致性的正式规范，他们修改程序，以便如果数据结构不一致，可以在运行时将其修改回一致状态。他们的技术不会以用户可见的方式修改程序源代码。相反，它会插入运行时监控代码，“修补”不一致的状态，以便有bug的程序可以继续执行。因此，修复完成后，它们的程序会继续产生运行时开销。与我们工作的另一个不同之处在于，它们的数据结构修复需要正式的规范。最后，他们的技术局限于数据结构，不能解决所有的逻辑错误。的肾小球囊性肾病例如，第3节中的无限循环就超出了这种技术的范围。然而，这种技术补充了我们的:在运行时数据结构修复没有提供可行的长期解决方案的情况下，它可以使程序在我们的技术搜索长期修复时继续执行。

去年Clearview¹⁶自动检测并修补已部署软件中的程序集级错误。Clearview在运行时监视一个程序，学习描述正常行为的不变量，并随后标记违规进行修复。动态生成并测试使牵连不变量为真的候选补丁。尽管Clearview的性能开销很高，但它已经成功地应用于有bug的Mozilla Firefox版本，并在红队黑客的攻击下进行了评估。然而，Clearview只能修复那些与所选监视器相关的错误。我们的方法更通用，提供了一种修复多类故障的单一方法，而不需要特定的监视器，而且我们不需要持续的运行时监控(以及固有的减速)来创建和部署修复。

这些工作说明了人们对自动软件修复问题以及可能尝试的许多可能的方法中的一些迅速增长的兴趣。最近还有其他一些不太成熟的关于自动查找和修复软件bug的建议，例如，Dallmeier等人，⁴这表明我们可以期望在今后几年内在这一领域取得迅速进展。

回到顶部

6.讨论

这里报告的结果表明，GP可以应用于遗留C程序中的bug修复问题。然而，也有一些注意事项。

基本限制。首先，我们假设缺陷是可重现的，并且程序在测试用例上的行为是确定的。这种限制可以通过多次运行测试用例来缓解，但是最终如果程序行为是随机的，我们的方法将很难找到或评估一个正确的补丁。我们进一步假设积极的测试用例可以编码程序需求。测试用例比正式规范或代码注释更容易获得，但是如果使用的太少，修复可能会牺牲重要的功能。在实践中，我们很可能有太多的测试用例，而不是太少，这减慢了适合度评估并阻碍了搜索。我们还假设沿着负测试用例所走的路径与正测试用例所走的路径不同。如果它们完全重叠，我们的加权表示法就不能有效地指导GP修改。最后，我们假设可以用程序中已经存在的语句构造修复;在未来的工作中，我们计划扩展我们的方法，以包括一个修复模板库。

进化。到目前为止，我们对研究结果的一个担忧是进化的作用。我们的大多数修复都是由于对程序的一两次随机修改，通常在最初几代人中就会发现，或者偶尔也不会。我们使用暴力算法(按预定顺序应用简单的突变操作)和随机搜索(随机应用突变操作，不选择或继承部分解)进行了一些实验。在我们的许多基准测试程序中，这两种更简单的替代方案的性能与GP相同，甚至更好。我们不能完全理解是什么特征，无论是程序还是特定的bug，决定了通过随机试验和错误找到解决方案有多容易。然而，到目前为止，在加权路径较长(即故障难以定位)的情况下，GP优于其他两种搜索策略。我们的GP算法设计存在一些有趣的问题，但最初的整个过程非常成功，我们没有仔细试验参数值、选择策略和操作符设计。这些几乎都可以得到改善。

故障定位。作为图1显示，寻找解的时间随加权路径的长度而变化。由于加权路径是故障定位的一种形式，我们可以使用现成的故障定位技术(如Jones和Harrold¹¹还有雷尼埃尔和赖斯^20.)或动态发现的不变量，¹³以白萝卜的风格⁶进一步缩小搜索空间。在无法仅通过控制流本地化错误的情况下，例如跨站点脚本或SQL注入攻击，数据上的谓词可能有帮助。此外，我们最近的实验表明，错误的位置(即，插入新代码的位置)很少与修复的来源(即，找到要插入的代码的位置)相同。由于我们一半以上的修复都涉及到插入或交换代码，所以找到可行的修复是至关重要的，但我们仍然不太了解。

适应度函数。我们当前的测试套件适应度函数具有概念简单的优势:通过所有测试用例的变体被认为是正确的，未编译或未通过所有测试的变体被拒绝。然而，它在中间区间可能不够准确，或者不够精确，不足以指导更复杂问题的进化搜索。考虑一个具有竞争条件的程序，该程序的修复包括插入独立的组件锁而且解锁调用。带有部分解的变体(例如，只是插入)锁)可能不幸地通过更少的测试用例(例如，通过死锁)，从而“欺骗”进化算法。适合度函数设计可以通过几种方式来增强，例如，通过对单个测试用例进行加权，动态地选择要包含的测试用例子集，或者通过使用其他信息来增加测试用例评估。例如，如果一个简单的谓词像x = = y在所有阳性测试用例的特定点为真，但对于阴性测试为假，使其为真的变体可能会被赋予更高的适应度值。

修复质量。我们感兴趣的是最小化后的维修差异有多大，以及维修质量与人工工程解决方案相比如何。在我们迄今为止的实验中，许多(但不是所有)修复在最小化步骤之后看起来是一样的。例如，我们为null-httpd错误，但有很多重叠存在(例如，两次修复可能会在同一个基本块的不同点插入相同的语句)。修复质量依赖于编码程序需求的高质量的阳性测试用例集的存在。在其他工作中，我们尝试了指示性工作负载、模糊测试和利用漏洞，以证明我们的服务器修复解决了问题的原因，而不是脆弱的负输入记忆，也不会导致常见请求失败(即，由于阳性测试)。不过，在这方面仍有许多工作要做，例如自动记录或证明所产生的修理的性质。

未来的工作。除了这些迫在眉睫的步骤外，未来还有其他更有雄心的工作领域。例如，我们计划开发一套通用的修复模板，以便GP在突变中使用额外的新代码源，而不是那些恰巧在程序中出现的语句。我们的AST程序表示可以以各种方式进行扩展，例如，通过包含数据结构定义和变量声明。类似地，我们目前正在试验汇编级和字节码级的修复。最后，我们有兴趣在更复杂的错误(如竞争条件)上测试该方法，并了解更多需要修复的错误，如它们的大小和分布，以及我们如何识别哪些是适合GP技术的对象。

回到顶部

7.结论

我们把这项技术的成功归功于设计限制搜索空间的决策。将注意力限制在语句上，沿着加权路径聚焦遗传操作，重用现有语句而不是发明新语句，修复现有程序而不是创建新程序，这些都有助于在实践中使用GP自动修复错误。

自动编程的梦想已经与计算机科学家们擦肩而过至少50年了。本文中描述的方法并不能通过从零开始发展新的程序来实现这个梦想。然而，它们确实展示了如何在有限的环境下改进遗留软件，至少为实现这个梦想提供了一小笔首付。我们相信，我们在自动修复方面的成功既说明了我们方法的有效性，也说明了当今软件的状态。在现代环境中，理解整个软件包、充分测试它或定位错误的来源是极其困难的。在这种情况下，人类编程通常有一个很大的试错组件，许多错误可以通过从另一个位置复制代码并将其粘贴到另一个位置来修复，这就不足为奇了。这种调试方法与我们在本文中描述的方法没有太大区别。

回到顶部

致谢

我们感谢David E. Evans、Mark Harman、John C. Knight、Anh Nguyen-Tuong和Martin Rinard的深入讨论。这项工作直接基于约翰·霍兰德和约翰·科扎的开创性思想。

本研究得到了国家科学基金CCF 0621900、CCR-0331580、CNS 0627523、CNS 0716478、空军科学研究办公室拨款fa95007-1 -0532以及微软研究院的捐赠。不应推断官方赞同。作者感谢Cris Moore帮助找到Zune的代码。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2010 ACM有限公司

---

没有发现记录