基于遗传算法和代码相似性自动修复程序错误

石建树 王宪勇

摘要：由于软件产品的复杂性，软件开发过程中开发人员无法避免bug的产生。为了提高软件开发的效率，提出了一种基于遗传算法和代码相似性的bug自动修复方法。首先，搜索与源程序相似的bug代码，并找到与其相关的修复代码。然后，将修复代码转换为抽象语法树，生成候选补丁。接下来，使用基于给定测试用例的适应度函数来验证候选补丁是否有效。最后，生成输出补丁修复源错误代码。

关键词：遗传算法;代码相似性;自动程序修复;软件维护

中图分类号：TP311.5 文献标识码：A

文章编号：1009-3044（2019）31-0209-03

1概述

由于现代软件产品的复杂性，软件开发过程中开发人员无法避免bug的产生。由于有大量的bug报告，开发人员必须花费更多的时间和精力来修复bug。由于每天都有大量的bug，开发人员需要花费更多的时间来跟踪这些bug。开发人员手工生成的补丁的正确率也难以保证。因此，一种速度快，准确率高的自动修复技术可以显著地节省软件开发的时间和成本，提高软件质量。

如果开发人员能够获得有用的信息描述，开发人员就可以轻松地跟踪并修复bug。但是，如果错误报告包含的信息不够，开发人员可能很难进行调试。因此，利用相似的bug代码的修复信息进行自动修复，可以在缺少描述信息的情况下有效地修复bug。

针对上述问题，本文提出一种基于遗传算法和代码相似性的程序自动修复方法。搜索与源bug代码相关的类似bug代码，以及其修复代码。然后，将其转换为抽象语法树（AST）。最后应用遗传规划为源bug代码生成补丁。此方法支持自动修复，可以减少修复bug的时间和工作量，并且可以提高bug修复的质量和补丁的可读性。

2相关工作

许多研究人员提出了程序自动修复方法。如表1所示，我们对与本文相关的自动修复技术进行了比较。

Le Goues等人提出了GenProg，其使用基于AST的遗传规划。GenProg将错误的源代码转换为AST，然后使用选择、交叉、变异等操作生成新的AST。齐玉华等人为了验证GenProg中遗传编程对补丁生成过程是否有效，提出了基于随机搜索的RSRepair方法。Simfix通过分析现有补丁形成抽象的过程修复空间，并且通过分析相同程序中相似的代码片段形成具体的修复空间。文明等人提出了CapGen，CapGen以细粒度的方式在AST节点级别工作，这种设计使其能够找到更精确的修复组件。为了解决细粒度所带来的搜索空间巨大的问题，其使用三种上下文模型使正确的补丁能够排在更靠前的位置。DeepRepair使用基于深度学习的代码相似性对修复成分进行优先级排序和转换。它计算代码元素之间的距离来度量相似性。其通过智能选择和调整修复成分来生成补丁。

3错误修复

3.1数据集

本文使用Defects4i数据集。高质量的数据集对于评估自动修复方法的有效性是必不可少的。Defects4i缺陷数据集共包含6个Java项目（Commons Lang、JFreeChart、CommonsMath、Joda-Time、Mockito和Closure Compiler），总bug数为438个，近年来关于自动修复的研究也广泛采用了该基准。Defects4i数据集中的错误程序都来自实际项目，并且其自带的测试用例集能够较好的覆盖程序的预期行为。

3.2错误定位

识别错误代码行是修复的先决条件。为了找到错误代码的位置，应该执行错误定位技术。错误定位技术的精确度对后续的修复效果起到关键的影响。目前研究人员已经提出了大量的程序错误定位方法。其中基于程序频谱的定位方法是目前的主流方法。其根据测试用例的覆盖率来判断语句的可疑度。最终向修复过程输出一组按可疑度大小排列的语句。本文使用错误定位工具Gzoltar，此工具使用Ochiai算法检索故障空间和可疑值。

3.3遗传规划

在本节中，我们将使用相似的bug修复信息描述遗传规划的应用。算法概览如图1所示。

3.3.1种群初始化

利用克隆检测技术㈣搜索与源bug代码相似的bug代码，并得到相似错误代码的修复代码。为了找到最相似的修复代码，将修复代码中的每一行代码转换为令牌序列。使用最长公共子序列（LCS）对这些行和源错误行的令牌序列进行比较。从这些行中获取具有最高LCS值的令牌序列。保留关键词、变量名和常数，使用随机操作符生成新的代码行，并将该行与错误行交换。重复这个步骤，直到初始补丁的数量等于种群的大小。

3.3.2遗传操作

当前种群中没有合格的个体时，将执行选择操作符。我们用适应度函数将个体按降序排序，使一半的个体都为父代。为了便于初始种群的构建，将适应度函数做规范化处理。以下为个体i的适应度函数规范化处理过程，这个规范化的适应度值仅用于初始种群选择。

其中，i为种群中第i个个体;fitc（i）表示i个体适应度值;fits表示种群中最小适应度值;fit1表示种群中最大适应度值。

交叉的目的是交换两个AST中的子树节点。在每个母树中选择可更改的目标节点。选择目标节点后，通过跟踪父节点来验证两个节点是否可以交换。在变异中，选用删除、插入和交换三种操作。

3.3.3适应度函数

迭代遗传规划算法，直到某些值达到限定条件。设置了三个限定条件;运行时间、代数和适应度值。如果达到限定时间和迭代次数还没有生成正确的补丁，则修复失败。个体适应度值如果是1，则停止迭代输出补丁。在每个迭代步骤中，并必须计算每个个体的适应度值。

其中，a为通过正测试用例的系数;β为未通过反测试用例的系数;y为通过反测试用例的系数;Pp代表通过的正测试用例;Ⅳ。代表通过的反测试用例;P为正测试用例集，N为反测试用例集。

方程结果的取值范围为0～1。值越接近1，个体越接近正确解。由于此模型包含了基本的功能，并且没有引发意外的行为，所以适应度更接近于1。a的值應大于β和y，因为此系数表示个体是否包含基本功能。

4结论

本文提出了一种自动修复程序缺陷的方法。首先，我们通过手工检查发现了可疑的错误代码行。然后，我们使用具有类似bug修复信息的GP生成候选补丁。接下来，我们验证候选补丁是否可采用。最后，我们生成补丁来修复程序错误。使用我们的方法，我们期望花费在修复bug上的时间和精力可以减少。在未来，计划创建一个自动故障修复工具并且利用大规模的bug修复信息修复和测试用例排序技术更有效地完成自动修复过程。