电子学报 ›› 2017, Vol. 45 ›› Issue (10): 2498-2505.DOI: 10.3969/j.issn.0372-2112.2017.10.026

• 学术论文 • 上一篇    下一篇

基于变型空间代数的自动程序修复方法

徐勇1, 毋国庆2, 袁梦霆2, 黄勃3   

  1. 1. 广东肇庆学院数学与统计学院, 广东肇庆 526061;
    2. 武汉大学计算机学院, 湖北武汉 430072;
    3. 上海工程技术大学电子电气工程学院计算机系, 上海 201620
  • 收稿日期:2016-11-11 修回日期:2017-02-27 出版日期:2017-10-25 发布日期:2017-10-25
  • 通讯作者: 黄勃
  • 作者简介:徐勇,男,1977年生,博士,主要研究方向为软件工程、软件调试.E-mail:xyus@whu.edu.cn;毋国庆,男,1954年生,教授、博士生导师,主要研究领域为软件需求工程、形式化方法.E-mail:wgq@whu.edu.cn
  • 基金资助:
    国家自然科学基金(No.61640221,No.61603242);上海高校青年教师培养资助计算专项基金(No.ZZGCD15088);肇庆学院科研基金(No.201734);肇庆市科技创新指导类项目(No.201704030409)

Automatic Program Repair Based on Version-Space Algebra

XU Yong1, WU Guo-qing2, YUAN Men-ting2, HUANG Bo3   

  1. 1. School of Mathematics and Statistics, Zhaoqing University, Zhaoqing, Guangdong 526061, China;
    2. Computer School, Wuhan University, Wuhan, Hubei 430072, China;
    3. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
  • Received:2016-11-11 Revised:2017-02-27 Online:2017-10-25 Published:2017-10-25

摘要: 基于代码枚举的自动程序修复方法借助变异算子对程序中错误语句进行变更操作,从而得到程序修复解.由于缺乏文法制导及变异算子数量的有限性,该方法的有效性有待进一步提高.本文提出一种基于变型空间代数的自动程序修复方法,即将回归测试用例集视为训练实例,通过归纳学习得到程序中出错语句的修复解.具体而言,该方法包括以下特征:(1)从文法到变型空间的自动构造生成方法;(2)根据变型空间树中变型空间的不同类别,分别给出一致性定义;(3)结合静态及类型检查的变型空间代数运算.实验结果表明:与基于代码枚举及基于搜索的修复方法相比,本文提出的方法在修复成功率方面更具优势;与此同时,方法中的静态及类型检查机制可以有效地削减假设空间的规模.

关键词: 自动程序修复, 变型空间代数, 归纳学习, 上下文无关文法, 生成树

Abstract: Automatic program repair based on code enumeration exploits mutation operators to fix buggy programs by mutating the faulty statements.Its effectiveness is hindered by lack of grammar-directed mutation and limited number of mutation operators.This paper proposes a new automatic program repair method based on version space algebra,which uses inductive learning techniques to automatically produce repair solution for the faulty statement of buggy program.Specifically,the proposed method has the following features:(1) automatic derivation of version spaces from grammars,(2) defining consistency of version space according to its type,and (3) combining static and type checking with version space algebra.Experimental results show the proposed method outperforms other existing automatic program repair approaches in terms of repair success rate,and static and type-checking mechanism can prune the hypothesis space efficiently.

Key words: automatic program repair, version-space algebra, inductive learning, context-free grammar, derivative tree

中图分类号: