本文主要介绍由Martinez等人2014年提出并不断完善的开源Java程序自动修复框架ASTOR，全称为“Automatic Software Transformations fOr program Repair”。首先会简要介绍自动程序修复技术，然后介绍ASTOR修复过程，然后介绍内置的各种程序修复技术。

自动程序修复技术

对于程序猿来说，bug可以说是家常便饭一样的存在。每天不是在调bug，就是在生产bug的路上，2333333。当你绞尽脑汁费劲心力，却发现一切的一切都是因为手滑将“==”写成了“=”，或者是不小心敲错一个变量名，循环里少敲了一个“break”......这时候不由得会想，这么简单的bug，调试起来怎么这么费劲，要是有程序可以帮我自动修复这些bug就好了。OK，有需求就要被满足，自动程序修复（APR，automatic program repair）应运而生。
自动程序修复技术已经是软件工程领域中比较热门的一个研究方向，其中有一大类叫做“generate and validate”，即生成验证式的自动程序修复技术，这类技术的算法思想很简单粗暴，就是先通过缺陷定位技术定位到一个或者多个可疑的语句，然后对这些语句进行不同的增删改操作，生成候选的补丁，最后通过配套的测试用例集对其进行验证，通过所有测试用例集的补丁被认为是成功修复得到的正确补丁。

可以看到，这其实是一个在原缺陷程序的修改空间内搜索正确补丁的过程，所以，根据不同的搜索算法（遗传规划、随机搜索等），不同的修改粒度（语句、表达式、操作符），可以有不同的生成验证式的自动程序修复技术。

除此之外，也有自动程序修复技术根据程序运行时信息提取出补丁需要满足的约束，利用约束求解和程序合成，直接求解出正确的补丁。
需要说明的是，自动程序修复技术得到的“正确补丁”实际上是plausible patch,虽然通过了测试用例集，但不能保证语义层面上的修复，还需要人工检查才能确定是否为correct patch。

ASTOR修复过程

ASTOR是为生成验证式的自动程序修复技术提供的开源框架。 ASTOR用Java语言实现并且是针对Java程序的修复技术，它的修复流程主要有以下几步：
0. 输入缺陷程序以及配套的测试用例集。测试用例集中至少要包含一个可以触发相应缺陷的测试用例。
1. 缺陷定位。这一步可以极大地缩减搜索空间。ASTOR使用现有的第三方缺陷定位库，包括GZoltar、CoCoSpoon。找到一个或者多个可疑的出错位置，并且根据计算得到的可疑度进行排序，优先处理最可疑的代码位置。

2. 确定修改点。修改点实际上指的是缺陷程序中的代码元素。根据修改粒度的不同，修改点可以是语句，或者是语句中出现的所有表达式。
3. 创建修复算子。修复算子即对修改点采取的动作。主要分为两种：需要ingredient的和不需要ingredient的。所谓ingredient其实就是源代码中包含的代码元素。举个例子，如果要将一个变量改成另一个变量，肯定要改成程序中已有的变量，不然编译会失败，所以是需要ingredient的。而对于操作符的修改，如“==”改成“=”，是不需要ingredient的。
4. 搜索正确补丁。即基于原缺陷程序的修改点和修复算子，在所有可能得到的修改后代码版本中，找到一个或者多个可以通过所有测试用例的正确补丁。搜索的过程是生成验证式的，不断循环执行“修改生成程序变体，验证是否通过测试用例”的过程。直到满足下面某一条件时循环结束：找到了正确补丁、到达指定循环次数或者时间。
5. 后续操作。这一步的前提是找到多个正确补丁，对结果进行一些优化处理。比如，删除掉补丁中一些与修复无关的修改，根据补丁质量对输出结果进行排序。

ASTOR中实现了多种不同的修复技术，包括jGenProg、jKali等，下面我将逐一介绍。

jGenProg

jGenProg是GenProg的Java实现，GenProg是Weimer等人在2009年提出的，它的主要思想是先将缺陷程序转化为抽象语法树，对节点进行添加、删除、替换的操作，然后基于遗传规划的方法指导整个搜索过程。

// Bug Math-70 repaired by jGenProg

jKali

jKali是Kali的Java实现，它只通过删除某些语句、将if语句中的条件改为true或false、添加return语句来对缺陷程序试图进行修复，它的修复算子很简单，但是会删除功能性代码，改变原程序的语义。

// Bug Math-50 repaired by jKali

jMutRepair

jMutRepair是一种基于变异的修复方法，将来自于变异测试的算子应用到缺陷程序if条件语句中的关系运算符（>, >=, <, <=, ==, !=）、逻辑运算符（||, &&）和一元运算符(负号)，通过修改这些运算符来修复程序。

// Bug Math-85 repaired by jMutRepair

DeepRepair

DeepRepair是jGenProg的扩展，由于jGenProg在对抽象语法树节点进行添加和替换操作时需要ingredient，所以合适的ingredient是成功修复的保障。相比于jGenProg使用随机的ingredient而言，DeepRepair通过深度学习的方式，得到代码结构和语义的特征，计算得到待修改代码块和其他地方代码块的相似度，选择更相似代码块中的ingredient。

另外，如果ingredient中存在变量的作用域不包括修改点，DeepRepair还可以基于变量之间语义的相似度，将这类变量改为修改点处已知的变量。

Cardumen

Cardumen是基于模板的修复方法，针对更小的粒度——表达式，它从原代码中挖掘出可用的修复模板，将语句中的表达式改为占位符作为模板，构造程序中变量名的概率模型，选择修改点处频率最高的变量替代模板中的占位符生成ingredient实例，以此合成补丁。

ASTOR运行实例

运行环境：Ubuntu16.04 64位，jdk1.8.0，maven3.6.0

首先将ASTOR克隆到本地：

git clone https://github.com/SpoonLabs/astor.git

编译ASTOR：

cd astor
mvn clean compile

编译并测试待修复项目（以astor/examples/Math-issue-280为例）：

cd examples/Math-issue-280
mvn clean compile test

获取运行时的classpath并保存到本地：

cd ../../
mvn dependency:build-classpath -B | egrep -v "(^[INFO]|^[WARNING])" | tee /tmp/astor-classpath.txt

执行ASTOR（ASTOR的命令行运行参数详见这里。）：

$(cat /tmp/astor-classpath.txt

打开astor/output_astor/AstorMain-Math-issue-280/src/可以看到得到的所有补丁，patch.diff文件对补丁进行说明：

结语

ASTOR不仅是程序自动修复技术，还是可供研究人员扩展的程序自动修复框架，可以在ASTOR上根据自己的实际需要实现自己的修复算法。

参考资料

[1] https://github.com/SpoonLabs/astor

[2] ASTOR: Exploring the Design Space of Generate-and-Validate Program Repair beyond GenProg (Matias Martinez, Martin Monperrus), Journal of Systems and Software, 2019.

[3] 自动程序修复方法研究述评[J]. 计算机学报, 2018, 41(3):588-610.