一种基于规则的自动程序修复方法

doi:10.19665/j.issn1001-2400.2020.04.016

Abstract

Abstract:

To tackle the problem of a low accuracy of test suite-based automatic program repair methods, this paper proposes a rule-based automatic program repair method named RuleFix. The proposed method first mines implicit programming rules in programs to locate defects, and then selects an appropriate patch according to the implicit programming rules, and lastly verifies the patch by utilizing the program synthesis tool to ensure the correctness of the repair result. Moreover, to tackle the problem that the existing rule mining algorithms cannot effectively mine low-frequency rules, a low-frequency rule mining algorithm is proposed, which can derives new rules based on the existing rules to improve the ability of rule mining. Finally, a prototype tool is implemented based on the proposed method, and then the proposed method is compared with the existing automatic program repair methods. Experimental results demonstrate that the proposed method has a significantly higher repair rate and accuracy rate than the existing GenProg and PAR methods.

Key words: automatic program repair, rule-based, static analysis, test suite

CLC Number:

TP309

HUANG Yuming,MA Jianfeng,LIU Zhiquan,FENG Bingwen,WEI Kaimin. Rule-based automatic program repair method[J].Journal of Xidian University, 2020, 47(4): 117-123.

Figures/Tables 10

References 15

[1]	黄昱铭, 马建峰, 刘志全, 等. 自动程序修复中的安全隐患场景及解决方案[J]. 西安电子科技大学学报, 2019,46(6):150-157.
	HUANG Yuming, MA Jianfeng, LIU Zhiquan, et al. Security Risk Scenarios and Solutions in Automatic Program Repair[J]. Journal of Xidian University, 2019,46(6):150-157.
[2]	李斌, 贺也平, 马恒太. 程序自动修复:关键问题及技术[J]. 软件学报, 2019,30(2):244-265.
	LI Bin, HE Yeping, MA Hengtai. AutomaticProgram Repair: Key Problems and Technologies[J]. Journal of Software, 2019,30(2):244-265.
[3]	王赞, 郜健, 陈翔, 等. 自动程序修复方法研究述评[J]. 计算机学报, 2018,41(3):588-610.
	WANG Zan, GAO Jian, CHEN Xiang, et al. Automatic Program Repair Techniques: a Survey[J]. Chinese Journal of Computers, 2018,41(3):588-610.
[4]	QI Y, MAO X, LEI Y, et al. The Strength of Random Search on Automated Program Repair[C]// Proceedings of the 2014 36th International Conference on Software Engineering. Washington: IEEE Computer Society, 2014: 254-265.
[5]	XIONG Y, WANG J, YAN R, et al. PreciseCondition Synconfproc for Program Repair[C]// Proceedings of the 2017 IEEE/ACM 39th International Conference on Software Engineering. Piscataway: IEEE, 2017: 416-426.
[6]	PERKINS J H, KIM S, LARSEN S, et al. Automatically Patching Errors in Deployed Software[C]// Proceedings of the 2009 22nd ACM SIGOPS Symposium on Operating Systems Principles. New York: ACM, 2009: 87-102.
[7]	LI Z, ZHOU Y. PR-Miner: Automatically Extracting Implicit Programming Rules and Detecting Violations in Large Software Code[C]// Proceedings of the 2005 Joint 10th European Software Engineering Conference (ESEC) and 13th ACM SIGSOFT Symposium on the Foundations of Software Engineering. New York: ACM, 2005: 306-315.
[8]	CUI Z, CHEN X, MU Y, et al. PSP-finder: A Defect Detection Method Based on Mining Correlations from Function Call Paths[J]. Chinese Journal of Electronics, 2018,27(4):776-782. doi: 10.1049/cje.2018.04.001
[9]	MIAO Y, LIN J, XU N. AnImproved Parallel FP-growth Algorithm Based on Spark and Its Application[C]// Proceedings of the 2019 Chinese Control Conference. Washington: IEEE Computer Society, 2019: 3793-3797.
[10]	GRAHNE G, ZHU J. Fast Algorithms for Frequent Itemset Mining Using FP-trees[J]. IEEE Transactions on Knowledge and Data Engineering, 2005,17(10):1347-1362. doi: 10.1109/TKDE.2005.166
[11]	LEUNG C K S, KHAN Q I, LI Z, et al. CanTree: A Canonical-order Tree for Incremental Frequent-pattern Mining[J]. Knowledge and Information Systems, 2007,11(3):287-311. doi: 10.1007/s10115-006-0032-8
[12]	SOLAR-LEZAMA. Program Synthesis by Sketching[D]. Berkeley: University of California, 2008.
[13]	PETKE J, HARALDSSON S O, HARMAN M, et al. Genetic Improvement of Software: A Comprehensive Survey[J]. IEEE Transactions on Evolutionary Computation, 2018,22(3):415-432. doi: 10.1109/TEVC.4235
[14]	KIM D, NAM J, SONG J, et al. Automatic Patch Generation Learned from Human-written Patches[C]// Proceedings of the 2013 International Conference on Software Engineering. Washington: IEEE Computer Society, 2013: 802-811.
[15]	JUST R, JALALI D, ERNST M D. Defects4J: ADatabase of Existing Faults to Enable Controlled Testing Studies for Java Programs[C]// Proceedings of the 2014 International Symposium on Software Testing and Analysis. New York: ACM, 2014: 437-440.

项目名称	缺陷数	测试用例数
Chart	26	2205
Lang	65	2245
Math	105	3602
Time	27	4130

项目名称	缺陷数	RuleFix	GenProg	PAR
Chart	26	4	0	0
Lang	65	4	0	1
Math	105	13	5	3
Time	27	1	0	0
合计	223	22	5	4

Rule-based automatic program repair method

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 15

Related Articles 5

Metrics

Comments

Recommended 10

[1]	HUANG Yuming,MA Jianfeng,LIU Zhiquan,WEI Kaimin,FENG Bingwen. Security risk scenarios and solutions in automatic program repair [J]. Journal of Xidian University, 2019, 46(6): 147-154.
[2]	SU Zijian;LIANG Changhong;LI Long;ZHAI Huiqing. Improved quasi-static effective medium model of the electromagnetic band gap (EBG) high-impedance surface [J]. J4, 2015, 42(5): 92-97.
[3]	FAN Yesen;LI Tuanjie;MA Xiaofei;LI Zhengjun. Form-finding method of equal tension cable networks for space mesh antennas [J]. J4, 2015, 42(1): 49-55.
[4]	ZHANG Liyong；WANG Xianqing；CHEN Ping；DENG Fan；KONG Delan. Fast reverse searching method for covert channels identification [J]. J4, 2011, 38(3): 128-135.
[5]	LIU Xiao-jian;LIU Xi-yang;CHEN Ping. A study of the implementation of the precompiler for embedding the rule-based paradigm into the object-oriented language [J]. J4, 2003, 30(1): 97-102.