《软件学报》：自动程序修复方法研究进展（玄跻峰、任志磊、王子元、谢晓园、江贺）

软件学报ISSN1000-9825, CODEN RUXUEW Journal of so/nare,201627(4):771-784ldoi:10.13328/ s004972] c中国科学院软件研究所版权所有 -62562563 自动程序修复方法研究进展 玄跻峰,任志磊),王子元4,谢晓园12,江贺 软件工程国家重点实验室(武汉大学,湖北武汉430072) (武汉大学计算机学院湖北武汉430072) (大连理工大学软件学院辽宁大连116621) 南京邮电大学计算机学院江苏南京210006) 通讯作者:玄跻峰,E-mail:xuan(@whu.edu.cn 摘要:自动程序修复帮助开发者降低人工修复bg的成本基于测试集的修复方法旨在生成能够通过测试集的 代码补丁,以使程序正常运行回顾了基于测试集的程序修复的现有文献按照自动修复方法和实证基础两个方面陈 述了研究进展首先将已有的自动修复方法划分为3类,分别是基于搜索的、基于代码穷举的和基于约束求解的补 丁生成方法;其次,细致地描述了程序修复的实证研究基础以及该研究领域中的争议;然后,简要介绍了程序修复的 相关技术作为修复方法的补充;最后做出总结,描述了面临的机遇和挑战. 关键词:自动修复;遗传规划基于搜索的软件工程;测试集;实证基础 中图法分类号:TP31 中文引用格式:玄跻峰任志磊,王子元谢晓园江贺.自动程序修复方法研究进展软件学报2016,27(4771-784.htt/ww Jos.org.cn/1000-9825/4972.htm 英文引用格式: Xuan JF, Ren ZL, Wang ZY, Xie XY, Jiang H., Progress on approaches to automatic program repa. Ruan Jian XueBao/journalofSoftware2016,27(4):771-784(inChinese).http://www.jos.orgcn/1000-9825/4972.htm Progress on Approaches to Automatic Program Repair XUAN Ji-Feng, 2 REN Zhi-Lei'. WANG Zi-Yuan xIE Xiao-Yuan,2 JIANG He State Key Laboratory of Software Engineering(Wuhan University ) Wuhan 430072, China) Computer School, Wuhan University, Wuhan 430072, China) ty 21, China) (School of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing 210006, China) Abstract: Automatic program repair helps developers reduce the cost of manual bug fixing. Approaches to test-suite based repair aim to generate code patches to pass the test suite as well as maintain the program execution. This paper available literature on test-suite based repair and report the progress in two directions: Approaches to automatic repair and empirical foundations. First, existing approaches to automatic repair are described in three categories: Search based, exhaustion based, and constraint-solving based patch th on in the research field. Related techniques then briefly introduced as the supplementation of program repair. Finally, opportunities and challenges are presented to summarize this review Key words: automatic repair; genetic programming; search based software engineering, test suite; empirical foundation 程序bug是软件开发中不可避免的产物,其产生原因可以追溯到软件开发的各个阶段历史数据表明超过 基金项目:国家自然科学基金(61502345,61403057,6137014,61202032) Foundation item: National Natural Science Foundation of China(61502345, 61403057, 61370144, 612020321 收稿时间:2015-09-02,修改时间:2015-10-15;采用时间:2015-11-20,jos在线出版时间:2016-01-13 CNKI网络优先出版:2016-01-1413:15:55,htp:/www.cnki.net/kems/detail/2560.TP201601141315001html ◎中国科学院软件研究所http://www.jos.org.cn

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software,2016,27(4):771−784 [doi: 10.13328/j.cnki.jos.004972] http://www.jos.org.cn ©中国科学院软件研究所版权所有. Tel: +86-10-62562563 自动程序修复方法研究进展∗ 玄跻峰 1,2, 任志磊 3 , 王子元 4 , 谢晓园 1,2, 江 贺 3 1 (软件工程国家重点实验室(武汉大学),湖北 武汉 430072) 2 (武汉大学 计算机学院,湖北 武汉 430072) 3 (大连理工大学 软件学院,辽宁 大连 116621) 4 (南京邮电大学 计算机学院,江苏 南京 210006) 通讯作者: 玄跻峰, E-mail: jxuan@whu.edu.cn 摘 要: 自动程序修复帮助开发者降低人工修复 bug 的成本.基于测试集的修复方法旨在生成能够通过测试集的 代码补丁,以使程序正常运行.回顾了基于测试集的程序修复的现有文献,按照自动修复方法和实证基础两个方面陈 述了研究进展.首先,将已有的自动修复方法划分为 3 类,分别是基于搜索的、基于代码穷举的和基于约束求解的补 丁生成方法;其次,细致地描述了程序修复的实证研究基础以及该研究领域中的争议;然后,简要介绍了程序修复的 相关技术作为修复方法的补充;最后做出总结,描述了面临的机遇和挑战. 关键词: 自动修复;遗传规划;基于搜索的软件工程;测试集;实证基础 中图法分类号: TP311 中文引用格式: 玄跻峰,任志磊,王子元,谢晓园,江贺.自动程序修复方法研究进展.软件学报,2016,27(4):771−784. http://www. jos.org.cn/1000-9825/4972.htm 英文引用格式: Xuan JF, Ren ZL, Wang ZY, Xie XY, Jiang H. Progress on approaches to automatic program repair. Ruan Jian Xue Bao/Journal of Software, 2016,27(4):771−784 (in Chinese). http://www.jos.org.cn/1000-9825/4972.htm Progress on Approaches to Automatic Program Repair XUAN Ji-Feng1,2, REN Zhi-Lei3 , WANG Zi-Yuan4 , XIE Xiao-Yuan1,2, JIANG He3 1 (State Key Laboratory of Software Engineering (Wuhan University), Wuhan 430072, China) 2 (Computer School, Wuhan University, Wuhan 430072, China) 3 (School of Software, Dalian University of Technology, Dalian 116621, China) 4 (School of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing 210006, China) Abstract: Automatic program repair helps developers reduce the cost of manual bug fixing. Approaches to test-suite based repair aim to generate code patches to pass the test suite as well as maintain the program execution. This paper reviews available literature on test-suite based repair and report the progress in two directions: Approaches to automatic repair and empirical foundations. First, existing approaches to automatic repair are described in three categories: Search based, exhaustion based, and constraint-solving based patch generation. Second, empirical foundations on repair are detailed, including the argumentation in the research field. Related techniques are then briefly introduced as the supplementation of program repair. Finally, opportunities and challenges are presented to summarize this review. Key words: automatic repair; genetic programming; search based software engineering; test suite; empirical foundation 程序 bug 是软件开发中不可避免的产物,其产生原因可以追溯到软件开发的各个阶段.历史数据表明,超过 ∗ 基金项目: 国家自然科学基金(61502345, 61403057, 61370144, 61202032) Foundation item: National Natural Science Foundation of China (61502345, 61403057, 61370144, 61202032) 收稿时间: 2015-09-02; 修改时间: 2015-10-15; 采用时间: 2015-11-20; jos 在线出版时间: 2016-01-13 CNKI 网络优先出版: 2016-01-14 13:15:55, http://www.cnki.net/kcms/detail/11.2560.TP.20160114.1315.001.html

Journal of sofware软件学报Vol.27,No4, April2016 45%的现代软件开发成本消耗于定位和修复bug过程中山无论工业生产还是学术研究领域,定位和修复程序 bug都是软件工程的核心问题随着软件测试和调试技术的提高,自动化的程序bug定位技术已经得到了一定的 研究和发展,然而自动化的程序bug修复方法仍处在初级阶段随着程序bug数量的日益积累自动修复技术 的深入研究及应用已迫在眉睫据已有数据显示在2001年~2010年这10年间,开源软件项目 Eclipse共接受 了33331个提交的bug,平均每天新增76个bug为了提高软件质量并改进软件产品,开发者不得不耗费大量 的人力和资源修复软件中的问题 为了降低修复过程中的时间和人力成本,自动程序修复( automatic program repair)方法应运而生该方法依 据给定的程序问题,自动生成程序补丁( patch,进而修复程序中的错误修复中产生的程序补丁既可以自动添加 到程序中,也可以用于指导开发者继续改进代码与现代软件工业中广泛出现的敏捷开发( agile developmen)和 持续集成( continuous integration)相结合,自动程序修复方法将有效地降低程序修复的成本从技术角度来看,研 究者将程序修复看作从潜在的搜索空间( search space)中搜索补丁的过程而优秀的修复技术可以大幅度提高补 丁搜索的准确率并减少用于搜索的时间消耗56该研究思路与基于搜索的软件工程契合例如,自动程序修 复中的先驱方法 Gen Prog就是一种基于遗传规划 genetic programming的C程序修复算法图 由于程序自身的复杂性自动程序修复的研究面临着一系列的挑战 方面研究者尝试设计算法为程序自动生成补丁,而所生成的补丁与真实人工添加的补丁尚存较大 差别; ·另一方面,研究者正在探索自动修复的实证基础( empirical foundation,然而该研究并非一帆风顺曾在 2014年和2015年掀起了两次领域内的学术争论 为避免歧义,若无特别说明,本文的研究主题(即自动程序修复)专指基于测试集的修复test- suite based repair)方法在基于测试集的修复中,测试集 test suite)用于描述并限定程序的正确行为( program behavior)任 何自动生成的补丁应至少保障测试集正确运行 passing the test suite,以确认未违反程序的需求说明.自动程序 修复研究中的绝大多数成果都属于基于测试集的修复领域 。发至本文成文之际2015年8月31日)自动程序修复方法尚未有工业应用本文回顾了该领域的研究历史 从修复方法和实证研究基础两个主要方面详述程序修复的现有研究进展以及所面临的机遇和挑战本文选取 的文献试图覆盖自动程序修复领域自2008年以来累计8年的主流工作需要提及的是:虽然该领域的国内研究 相对于国际同行较为滞后但来自国防科学技术大学12-1和上海交通大学的研究者们已发表了不少优秀成 果将在后文加以介绍 本文首先概述自动程序修复的研究背景;其次,通过检索和筛选相关文献简要地回顾研究历史;再次,分两 个方面介绍本文的主要部分:自动修复方法的研究进展和程序修复的实证研究基础;然后,作为补充简要介绍 与程序修复直接相关的技术最后,分析自动程序修复研究面临的机遇和挑战 概述 1.1基于测试集的程序修复 基于测试集的程序修复,简称为程序修复,旨在自动生成能够通过测试集中全部测试用例( test case程序 补丁该类方法主要以白盒( white-box)形式呈现,即,被修复程序的源代码和测试用例对自动修复方法完全可见 个程序修复方法的输入通常是带有bug的程序( buggy program)及其当前的测试集,并且至少有一个测试用例 因为bug而无法通过(fai)修复方法的输出为零个或一个程序补丁(有的方法可以输出多个补丁)生成零个补丁 表示该方法无法自动修复程序 处理程序并非易事:程序的需求信息( requirements)通常以自然语言描述,如项目文档或程序接口文档,这些 信息无法被直接翻译为程序输入另一方面程序形式化的规格说明( specifications)也难以充分获取因此,源代 码结构和测试集中的测试用例成为修复程序的主要输入来源获得可修复bug的代码补丁,实际上就是生成在 程序特定位置的代码段而这个特定位置和代码段的内容都是未知的直观来说,程序修复包含两个部分,即如 ◎中国科学院软件研究所http://www.jos.org.cn

772 Journal of Software 软件学报 Vol.27, No.4, April 2016 45%的现代软件开发成本消耗于定位和修复 bug 过程中[1].无论工业生产还是学术研究领域,定位和修复程序 bug 都是软件工程的核心问题.随着软件测试和调试技术的提高,自动化的程序 bug 定位技术已经得到了一定的 研究和发展[2,3],然而自动化的程序 bug 修复方法仍处在初级阶段.随着程序 bug 数量的日益积累,自动修复技术 的深入研究及应用已迫在眉睫.据已有数据显示:在 2001 年~2010 年这 10 年间,开源软件项目 Eclipse 共接受 了 333 371 个提交的 bug,平均每天新增 76 个 bug[4].为了提高软件质量并改进软件产品,开发者不得不耗费大量 的人力和资源修复软件中的问题. 为了降低修复过程中的时间和人力成本,自动程序修复(automatic program repair)方法应运而生.该方法依 据给定的程序问题,自动生成程序补丁(patch),进而修复程序中的错误.修复中产生的程序补丁既可以自动添加 到程序中,也可以用于指导开发者继续改进代码.与现代软件工业中广泛出现的敏捷开发(agile development)和 持续集成(continuous integration)相结合,自动程序修复方法将有效地降低程序修复的成本.从技术角度来看,研 究者将程序修复看作从潜在的搜索空间(search space)中搜索补丁的过程,而优秀的修复技术可以大幅度提高补 丁搜索的准确率,并减少用于搜索的时间消耗[5,6].该研究思路与基于搜索的软件工程契合[7].例如,自动程序修 复中的先驱方法 GenProg 就是一种基于遗传规划(genetic programming)的 C 程序修复算法[8]. 由于程序自身的复杂性,自动程序修复的研究面临着一系列的挑战. • 一方面,研究者尝试设计算法为程序自动生成补丁,而所生成的补丁与真实人工添加的补丁尚存较大 差别; • 另一方面,研究者正在探索自动修复的实证基础(empirical foundation),然而该研究并非一帆风顺,曾在 2014 年[9]和 2015 年[10,11]掀起了两次领域内的学术争论. 为避免歧义,若无特别说明,本文的研究主题(即自动程序修复)专指基于测试集的修复(test-suite based repair)方法[9].在基于测试集的修复中,测试集(test suite)用于描述并限定程序的正确行为(program behavior).任 何自动生成的补丁应至少保障测试集正确运行(passing the test suite),以确认未违反程序的需求说明.自动程序 修复研究中的绝大多数成果都属于基于测试集的修复领域. 截至本文成文之际(2015 年 8 月 31 日),自动程序修复方法尚未有工业应用.本文回顾了该领域的研究历史, 从修复方法和实证研究基础两个主要方面详述程序修复的现有研究进展以及所面临的机遇和挑战.本文选取 的文献试图覆盖自动程序修复领域自 2008 年以来累计 8 年的主流工作.需要提及的是:虽然该领域的国内研究 相对于国际同行较为滞后,但来自国防科学技术大学[12−16]和上海交通大学[17]的研究者们已发表了不少优秀成 果,将在后文加以介绍. 本文首先概述自动程序修复的研究背景;其次,通过检索和筛选相关文献简要地回顾研究历史;再次,分两 个方面介绍本文的主要部分:自动修复方法的研究进展和程序修复的实证研究基础;然后,作为补充,简要介绍 与程序修复直接相关的技术;最后,分析自动程序修复研究面临的机遇和挑战. 1 概 述 1.1 基于测试集的程序修复 基于测试集的程序修复,简称为程序修复,旨在自动生成能够通过测试集中全部测试用例(test case)的程序 补丁.该类方法主要以白盒(white-box)形式呈现,即,被修复程序的源代码和测试用例对自动修复方法完全可见. 一个程序修复方法的输入通常是带有 bug 的程序(buggy program)及其当前的测试集,并且至少有一个测试用例 因为 bug 而无法通过(fail).修复方法的输出为零个或一个程序补丁(有的方法可以输出多个补丁).生成零个补丁 表示该方法无法自动修复程序. 处理程序并非易事:程序的需求信息(requirements)通常以自然语言描述,如项目文档或程序接口文档,这些 信息无法被直接翻译为程序输入.另一方面,程序形式化的规格说明(specifications)也难以充分获取.因此,源代 码结构和测试集中的测试用例成为修复程序的主要输入来源.获得可修复 bug 的代码补丁,实际上就是生成在 程序特定位置的代码段.而这个特定位置和代码段的内容都是未知的.直观来说,程序修复包含两个部分,即如

玄跻峰等:自动程序修复方法研究进展 773 何找到bug的位置和如何为bug生成代码段为了解决程序修复问题,研究者们将这个带有bug的程序及其某 个潜在位置的代码变动(例如代码的添加、删除或修改)看作一个个体并将所有这样的个体看作一个巨大的搜 索空间因此程序修复的过程可以看作如何从搜索空间中找寻可以修复bug的个体的过程 1.2修复算法的流程 图1展示了基于测试集的程序修复方法的流程程序修复方法首先通过故障定位( fault localization)方法将 给定带有bug的程序的所有语句按某种规则排序,得到可疑语句的排列;然后将这些语句作为疑似bug的位置 逐个传输给补丁生成算法( patch generation),补丁生成算法会检测当前bug的位置,决定是否能够输出补丁:如果 能够,则输出补丁给测试集进行验证,通过验证(即是否能够通过测试集)的补丁将作为结果输出;若该疑似bug 置无法输出补丁,则从语句排列中获取下一个可疑语句,重新运行补丁生成算法以继续寻找潜在的补丁 故障定位 补丁生成 语句排列 逐语句分析基于搜索的 基于代码 基于 「第1条语句 穷举的方法 的法 求解的 「第2条语句 匚投末语句 solving based generation patch generation patch generation 全部语句分析完毕 下一条语句 错误验证补了 无补丁输出 输出最终补丁 Fig 1 Overview of test-suite based repair 图1基于测试集的程序修复方法的流程概览 如图1所示,本文将所有的相关补丁生成方法粗略地划分为3类即基于搜索( search based patch generation) 的方法、基于代码穷举( exhaustion based patch generation)的方法和基于约束求解( constraint- solving based patc generation)的方法基于搜索的方法使用源自基于搜索的软件工程8中“搜索”的定义,即,采用元启发式 ( meta-heuristics)方法、演化算法( evolutionary computation)等优化方法进行补丁的搜索基于搜索的方法是程序 修复中的主要部分,尤其在领域创始之初更占有重要地位,代表算法包括基于遗传规划的抽象语法树修复算法 genProgl、基于程序等价性的遗传修复算法AE0、基于随机搜索的修复算法 RSRepai1等基于代码穷举 的方法无差别地变异全部可疑语句,同时,有策略地穷举可能出现的代码修改,追求补丁的有效性而忽略算法效 率这类算法不多代表算法包括程序变异算法凹、代码消除算法Kai,基于约束求解的方法,顾名思义将补 丁生成转换为约束求解问题,应用求解器直接计算可行解( feasible solution),进而转换为最终补丁,代表算法包 括程序语义修复SmFx2、补丁简化算法 Directrix2)、条件bug修复 topol24等 需要注意的是其一,基于代码穷举的方法和基于约束求解的方法也可以看作某种程度的搜索,但本文遵从 基于搜索的软件工程领域的约定,只将第1类方法称为基于搜索的补丁生成方法其二,图1的流程是经过总结 已有方法而得到的大概流程2426在一些修复算法中,某些步骤可能被简化例如在基于代码穷举的方法 Kal10中,所有的程序语句没有经过故障定位而按照自然顺序直接排列而在基于约束求解的方法 SemFix2 中,在补丁生成后无需进行补丁的验证第3节详细介绍修复方法 ◎中国科学院软件研究所htp:/ww.jos.org.cn

玄跻峰 等:自动程序修复方法研究进展 773 何找到 bug 的位置和如何为 bug 生成代码段.为了解决程序修复问题,研究者们将这个带有 bug 的程序及其某 个潜在位置的代码变动(例如代码的添加、删除或修改)看作一个个体,并将所有这样的个体看作一个巨大的搜 索空间[5].因此,程序修复的过程可以看作如何从搜索空间中找寻可以修复 bug 的个体的过程. 1.2 修复算法的流程 图 1 展示了基于测试集的程序修复方法的流程.程序修复方法首先通过故障定位(fault localization)方法将 给定带有 bug 的程序的所有语句按某种规则排序,得到可疑语句的排列;然后将这些语句作为疑似 bug 的位置, 逐个传输给补丁生成算法(patch generation);补丁生成算法会检测当前 bug 的位置,决定是否能够输出补丁:如果 能够,则输出补丁给测试集进行验证,通过验证(即是否能够通过测试集)的补丁将作为结果输出;若该疑似 bug 的位置无法输出补丁,则从语句排列中获取下一个可疑语句,重新运行补丁生成算法以继续寻找潜在的补丁. Fig.1 Overview of test-suite based repair 图 1 基于测试集的程序修复方法的流程概览 如图 1 所示,本文将所有的相关补丁生成方法粗略地划分为 3 类,即基于搜索(search based patch generation) 的方法、基于代码穷举(exhaustion based patch generation)的方法和基于约束求解(constraint-solving based patch generation)的方法.基于搜索的方法使用源自基于搜索的软件工程[7,18,19]中“搜索”的定义,即,采用元启发式 (meta-heuristics)方法、演化算法(evolutionary computation)等优化方法进行补丁的搜索.基于搜索的方法是程序 修复中的主要部分,尤其在领域创始之初更占有重要地位,代表算法包括基于遗传规划的抽象语法树修复算法 GenProg[5]、基于程序等价性的遗传修复算法 AE[20]、基于随机搜索的修复算法 RSRepair[16]等.基于代码穷举 的方法无差别地变异全部可疑语句,同时,有策略地穷举可能出现的代码修改,追求补丁的有效性而忽略算法效 率.这类算法不多,代表算法包括程序变异算法[21]、代码消除算法 Kali[10].基于约束求解的方法,顾名思义,将补 丁生成转换为约束求解问题,应用求解器直接计算可行解(feasible solution),进而转换为最终补丁,代表算法包 括程序语义修复 SemFix[22]、补丁简化算法 DirectFix[23]、条件 bug 修复 Nopol[24,25]等. 需要注意的是:其一,基于代码穷举的方法和基于约束求解的方法也可以看作某种程度的搜索,但本文遵从 基于搜索的软件工程领域的约定,只将第 1 类方法称为基于搜索的补丁生成方法;其二,图 1 的流程是经过总结 已有方法而得到的大概流程[24,26].在一些修复算法中,某些步骤可能被简化.例如:在基于代码穷举的方法 Kali[10]中,所有的程序语句没有经过故障定位,而按照自然顺序直接排列;而在基于约束求解的方法 SemFix[22] 中,在补丁生成后无需进行补丁的验证.第 3 节详细介绍修复方法. 带有 bug 的程序 测试集 故障定位 验证补丁 输出最终补丁 语句排列 第 1 条语句 第 2 条语句 最末语句 ... 正确 下一条语句 逐语句分析 错误 无补丁输出 全部语句分析完毕 补丁生成 基于搜索的 方法 Search based patch generation Exhaustion based patch generation 基于约束 求解的方法 solving based patch generation 或 或 基于代码 穷举的方法 Constraint-

774 Journal of sofware软件学报Vol.27,No4, April2016 3测试集在程序修复中的作用 测试集是自动修复算法的重要输入事实上,测试集是在实践上程序需求说明的代码表达由于需求说明往 往不可见,测试集中的测试用例可以制约程序的实际行为在自动修复算法中,测试集指导补丁生成同时验证 生成后的补丁是否通过测试集 度量基于测试集的修复算法,其基本要求是添加补丁的程序能够通过测试集中的全部测试用例该度量标 准被称为可修复性( fixability)现代软件开发中,测试集可以通过测试框架(如Java语言的 JUnit)自动运行因此, 可修复性能否达到是可以自动完成的 能够通过测试集的补丁并不一定正确正确性( correctness)指的是修复后的程序达到了预期的行为,即,程序 的输出能够满足潜在的测试预言( (test oracle)例如,一个修复划分三角形类别程序的补丁正确,指的是程序可以 无误地划分任何潜在的三角形类别,而不是仅仅满足有限数量的测试用例的通过正确性目前还不能通过自动 技术完成只能手动验证近期的一些工作采用了正确性作为评价标准1003261 2研究历史回顾 2.1文献检索与筛选 本文的文献囊括了基于测试集的程序修复领域8年来的研究进展,同时包含了其他程序修复相关技术的 主要文献以下是本文检索和筛选文献的步骤 (1)文献检索的主要途径是谷歌学术搜索引擎 Google scholar)以及ACM( ACM digital library)、IEE ( IEEE xplore digital library)和 Springer(Springer link)的论文数据库检索过程中倾向于软件工程的主 流会议期刊(如ICSE,FSE等)并包括系统和程序语言相关会议期刊(如 PLDLOOPSLA等) (2)检索关键词包括自动程序修复的关键词的组合,可简要概括如下(⊥表示空字符串) (repairvfix)A(softwarevprogramvcode )A(failurevbugvtest casevtest suitev1) 3)检索时间为2001年至今的全部文献由于基于测试集的修复领域始于2008年,因此,该检索将覆盖基 于测试集的程序修复方法相关的全部文献,同时我们也列出了其他程序修复方法的主要相关文献 (4)收入本文的文献类型包括期刊的长文和短文、会议的 research track, experience track, industry track, ew idea and emerging result track和 short paper track以及技术报告 technical report)技术报告是该领 域文献的重要组成部分,由于该领域发展活跃,部分论文尚未进入发表阶段常以技术报告的形式呈 现但文献不包含会议的 poster track, doctoral symposium, student competition,原因是这些部分的正文 较短不足以了解文章内容同时也不包括博士论文(PhD. dissertation,因为所涉及的博士论文的内容 大部分己经以会议或期刊论文的形式发表 (5)基于上面检索到的论文,我们进行了人工筛选最后获得第22节列出的文献 2.2历史文献回顾 经过文献检索与筛选获得了基于测试集的程序修复领域自2008年~2015年的学术论文37篇,其中会议长 文25篇、会议短文2篇、期刊6篇、技术报告4篇需要指出的是这里仅包含本文主题,即,基于测试集的程 序修复,这37篇论文将在第3节和第4节进行详细介绍,而与程序修复相关的其他论文将在第5节介绍 表1列出了基于测试集的程序修复的相关文献的出处,其中包括软件工程顶级会议ICSE论文8篇、FSE 论文4篇、顶级期刊 IEEE Trans. on Software Engineering(TSE)论文2篇 图2展示了自2008年创始以来该领域相关文献的分布,可以看到文献数量缓步上升,而最近两年的文献数 量最多,2014年8篇,而2015年已有11篇这一趋势说明,该领域正日趋活跃.另外,2011年没有任何文献出现 时没有发现特殊原因 ◎中国科学院软件研究所http://www.jos.org.cn

774 Journal of Software 软件学报 Vol.27, No.4, April 2016 1.3 测试集在程序修复中的作用 测试集是自动修复算法的重要输入.事实上,测试集是在实践上程序需求说明的代码表达.由于需求说明往 往不可见,测试集中的测试用例可以制约程序的实际行为.在自动修复算法中,测试集指导补丁生成,同时验证 生成后的补丁是否通过测试集. 度量基于测试集的修复算法,其基本要求是添加补丁的程序能够通过测试集中的全部测试用例.该度量标 准被称为可修复性(fixability).现代软件开发中,测试集可以通过测试框架(如 Java 语言的 JUnit)自动运行.因此, 可修复性能否达到是可以自动完成的. 能够通过测试集的补丁并不一定正确.正确性(correctness)指的是修复后的程序达到了预期的行为,即,程序 的输出能够满足潜在的测试预言(test oracle).例如,一个修复划分三角形类别程序的补丁正确,指的是程序可以 无误地划分任何潜在的三角形类别,而不是仅仅满足有限数量的测试用例的通过.正确性目前还不能通过自动 技术完成,只能手动验证.近期的一些工作采用了正确性作为评价标准[10,25,26]. 2 研究历史回顾 2.1 文献检索与筛选 本文的文献囊括了基于测试集的程序修复领域 8 年来的研究进展,同时包含了其他程序修复相关技术的 主要文献.以下是本文检索和筛选文献的步骤. (1) 文献检索的主要途径是谷歌学术搜索引擎(Google scholar)以及 ACM(ACM digital library)、IEEE (IEEE xplore digital library)和 Springer(Springer link)的论文数据库.检索过程中倾向于软件工程的主 流会议期刊(如 ICSE,FSE 等),并包括系统和程序语言相关会议期刊(如 PLDI,OOPSLA 等); (2) 检索关键词包括自动程序修复的关键词的组合,可简要概括如下(⊥表示空字符串): (repair∨fix)∧(software∨program∨code)∧(failure∨bug∨test case∨test suite∨⊥); (3) 检索时间为 2001 年至今的全部文献.由于基于测试集的修复领域始于 2008 年,因此,该检索将覆盖基 于测试集的程序修复方法相关的全部文献;同时,我们也列出了其他程序修复方法的主要相关文献; (4) 收入本文的文献类型包括期刊的长文和短文、会议的 research track,experience track,industry track, new idea and emerging result track 和 short paper track 以及技术报告(technical report).技术报告是该领 域文献的重要组成部分,由于该领域发展活跃,部分论文尚未进入发表阶段,常以技术报告的形式呈 现.但文献不包含会议的 poster track,doctoral symposium,student competition,原因是这些部分的正文 较短,不足以了解文章内容;同时也不包括博士论文(Ph.D. dissertation),因为所涉及的博士论文的内容 大部分已经以会议或期刊论文的形式发表; (5) 基于上面检索到的论文,我们进行了人工筛选,最后获得第 2.2 节列出的文献. 2.2 历史文献回顾 经过文献检索与筛选,获得了基于测试集的程序修复领域自 2008 年~2015 年的学术论文 37 篇,其中会议长 文 25 篇、会议短文 2 篇、期刊 6 篇、技术报告 4 篇.需要指出的是:这里仅包含本文主题,即,基于测试集的程 序修复,这 37 篇论文将在第 3 节和第 4 节进行详细介绍,而与程序修复相关的其他论文将在第 5 节介绍. 表 1 列出了基于测试集的程序修复的相关文献的出处,其中包括软件工程顶级会议 ICSE 论文 8 篇、FSE 论文 4 篇、顶级期刊 IEEE Trans. on Software Engineering(TSE)论文 2 篇. 图 2 展示了自 2008 年创始以来该领域相关文献的分布,可以看到:文献数量缓步上升,而最近两年的文献数 量最多,2014 年 8 篇,而 2015 年已有 11 篇.这一趋势说明,该领域正日趋活跃.另外,2011 年没有任何文献出现, 暂时没有发现特殊原因

玄跻峰等:自动程序修复方法研究进展 775 Table 1 List of related literature on test-suite based repair 表1基于测试集的程序修复的相关文献的列表 出版物名称 缩写文章数 ACM SIGSOFT Int'l Symp. on the Foundations of Software Engineering Fs王868143 ISSTA 3 10,15,43 120,32,41 国际会议 IEEE Int'l Conf on Software Maintenance(and Evolution ICSM 3 12,1446 Int'l Conference on Software Testing Verification and Validation ICST I'l Workshop on Constraints in Software Testing, Verification, and Analysis CSTVA I IEEE Congress on Evolutionary computation 国际期刊 Empirical Software Quality Journal Science China Information Scier 技术报告 2526,34,50 技术报告 口期刊论文 20082009201020112012201320142015 年份 Fig 2 Illustration of literature by year 图2相关文献的年代分布 3基于测试集的自动程序修复方法 正如第1.2节所说,本文按照获得补丁的过程将基于测试集的程序修复方法分为3类,即,基于搜索的方法 基于代码穷举的方法和基于约束求解的方法其中,多数已有的修复算法可以认为是基于搜索的方法 3.1基于搜索的方法 在基于搜索的方法中生成程序补丁的过程被看作是从补丁的搜索空间中寻找最优可行解的过程对于被 修复程序来说,潜在补丁的搜索空间是未知的研究者将更改被测程序而产生的新程序看作潜在的补丁进而获 得补丁空间基于搜索方法的核心之一,是使用基于搜索的软件工程中的启发式方法、演化算法等方法寻找 补丁 2008年 Arcuri和Yao12最早提出了基于测试集的程序修复思路完成了该领域开创性的工作他们将被修 复程序的补丁看作算法的解,应用协同演化(co- evolutionary)算法自动生成代码补丁 2009年 Weimer和 Le goues等人8389作为该领域的先驱,设计了 Gen Prog算法 Gen Prog将C程序看作 抽象语法树( abstract syntax tree),将代码段看作子树;基于遗传规划算法 Gen Prog将被测程序的抽象语法树通过 插入、删除或替换生成新的程序,并应用测试用例集验证是否被修复.在该方法中,补丁的位置由一种内嵌的故 障定位算法决定遗传规划在 GenProg中的作用是通过变换语法树获得新的语法树 2010年, Weimer和 Le goues等人的后续工作,如2010年的Fast等人和2012年的 Le goues等人,进 步从遗传规划的优化角度提升获得补丁的效率;而2010年, Schulte等人2则应用了同样的方法修复汇编语 ◎中国科学院软件研究所http://www.jos.org.cn

玄跻峰 等:自动程序修复方法研究进展 775 Table 1 List of related literature on test-suite based repair 表 1 基于测试集的程序修复的相关文献的列表 类型 出版物名称 缩写 文章数 文章列表 国际会议 Int’l Conf. on Software Engineering ICSE 8 [6,8,9,16,17,23,42,47] ACM SIGSOFT Int’l Symp. on the Foundations of Software Engineering FSE 4 [11,40,45,48] Int’l Symp. on Software Testing and Analysis ISSTA 3 [10,15,43] IEEE/ACM Int’l Conf. on Automated Software Engineering ASE 3 [20,32,41] IEEE Int’l Conf. on Software Maintenance (and Evolution) ICSM 3 [12,14,46] Int’l Conference on Software Testing, Verification and Validation ICST 1 [21] Genetic and Evolutionary Computation Conf. GECCO 3 [28,30,31] Int’l Workshop on Constraints in Software Testing, Verification, and Analysis CSTVA 1 [24] IEEE Congress on Evolutionary Computation CEC 1 [27] 国际期刊 IEEE Trans. on Software Engineering TSE 2 [5,49] Communications of the ACM CACM 1 [29] Empirical Software Engineering ESE 1 [33] Software Quality Journal SQJ 1 [44] Science China Information Sciences SCIS 1 [13] 技术报告 Technical Report TR 4 [25,26,34,50] 合计 37 Fig.2 Illustration of literature by year 图 2 相关文献的年代分布 3 基于测试集的自动程序修复方法 正如第 1.2 节所说,本文按照获得补丁的过程将基于测试集的程序修复方法分为 3 类,即,基于搜索的方法、 基于代码穷举的方法和基于约束求解的方法.其中,多数已有的修复算法可以认为是基于搜索的方法. 3.1 基于搜索的方法 在基于搜索的方法中,生成程序补丁的过程被看作是从补丁的搜索空间中寻找最优可行解的过程.对于被 修复程序来说,潜在补丁的搜索空间是未知的,研究者将更改被测程序而产生的新程序看作潜在的补丁,进而获 得补丁空间.基于搜索方法的核心之一,是使用基于搜索的软件工程中的启发式方法、演化算法等方法寻找 补丁. 2008 年,Arcuri 和 Yao[27]最早提出了基于测试集的程序修复思路,完成了该领域开创性的工作.他们将被修 复程序的补丁看作算法的解,应用协同演化(co-evolutionary)算法自动生成代码补丁. 2009 年,Weimer 和 Le Goues 等人[5,8,28,29]作为该领域的先驱,设计了 GenProg 算法.GenProg 将 C 程序看作 抽象语法树(abstract syntax tree),将代码段看作子树;基于遗传规划算法,GenProg 将被测程序的抽象语法树通过 插入、删除或替换生成新的程序,并应用测试用例集验证是否被修复.在该方法中,补丁的位置由一种内嵌的故 障定位算法决定.遗传规划在 GenProg 中的作用是通过变换语法树获得新的语法树. 2010 年,Weimer 和 Le Goues 等人的后续工作,如 2010 年的 Fast 等人[30]和 2012 年的 Le Goues 等人[31],进 一步从遗传规划的优化角度提升获得补丁的效率;而 2010 年,Schulte 等人[32]则应用了同样的方法修复汇编语 2015 论文数量 年份 会议短文 技术报告 期刊论文 会议长文 会议短文 技术报告 期刊论文 会议长文 12 10 8 6 4 2 0 20092008 2010 20122011 2013 2014