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

doi:10.19665/j.issn1001-2400.2020.04.016

西安电子科技大学学报 ›› 2020, Vol. 47 ›› Issue (4): 117-123.doi: 10.19665/j.issn1001-2400.2020.04.016

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

黄昱铭¹(),马建峰^1,²,刘志全¹(),冯丙文^1,^3,^4,⁵,魏凯敏¹

1.暨南大学信息科学技术学院,广东广州 510632
2.西安电子科技大学网络与信息安全学院,陕西西安 710071
3.中国科学院信息工程研究所信息安全国家重点实验室,北京 100093
4.广东省信息安全技术重点实验室,广东广州 520006
5.广东省智能信息处理重点实验室/深圳市媒体信息内容安全重点实验室,广东深圳 518060

收稿日期:2019-12-08 出版日期:2020-08-20 发布日期:2020-08-14
通讯作者: 刘志全
作者简介:黄昱铭(1995—),男,暨南大学硕士研究生,E-mail:406744068@qq.com.
基金资助:
国家自然科学基金(61802146);国家自然科学基金(61972178);国家自然科学基金(61802145);广东省重点领域研发计划(2019B010136003);广东省数据安全与隐私保护重点实验室(2017B03031004);广东省基础与应用基础研究基金(2019A1515011017);广东省自然科学基金(2019B010137005);广东省自然科学基金(2018A030313813);广东省自然科学基金(2018A03031387);广东省自然科学基金(2017A030313390);广东省自然科学基金(2017A030313334);广州市科技计划(201804010428);广州市科技计划(201802010061);中央高校基本科研业务费专项资金(11618332);中央高校基本科研业务费专项资金(11617343);信息安全国家重点实验室开放课题;广东省信息安全技术重点实验室开放基金(2017B030314131);广东省智能信息处理重点实验室/深圳市媒体信息内容安全重点实验室开放基金

Rule-based automatic program repair method

HUANG Yuming¹(),MA Jianfeng^1,²,LIU Zhiquan¹(),FENG Bingwen^1,^3,^4,⁵,WEI Kaimin¹

1. College of Information Science and Technology, Jinan Univ., Guangzhou 510632, China
2. School of Cyber Engineering, Xidian Univ., Xi’an 710071, China
3. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
4. Guangdong Provincial Key Laboratory of Information Security Technology, Guangzhou 520006, China
5. Guangdong Key Laboratory of Intelligent Information Processing and Shenzhen Key Laboratory of Media Security, Shenzhen 518060, China

Received:2019-12-08 Online:2020-08-20 Published:2020-08-14
Contact: Zhiquan LIU

摘要/Abstract

摘要：

为解决基于测试集自动程序修复方法修复缺陷正确率低的问题,提出一种基于规则的自动程序修复方法——RuleFix。该方法首先通过挖掘代码中的隐式编程规则定位缺陷位置,然后根据隐式编程规则选取合适的补丁,最后采用程序合成工具对补丁进行校验以保证修复结果的正确性。此外,为解决现有规则挖掘算法无法有效挖掘低频规则的问题,提出一种低频规则挖掘算法,根据已有规则推演生成新的规则,以提升规则挖掘的能力。基于所提方法实现了原型工具,并与现有的自动程序修复方法进行对比。实验结果表明,与现有的GenProg和PAR方法相比,所提方法有明显更高的修复率和正确率。

关键词: 自动程序修复, 基于规则, 静态分析, 测试集

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

中图分类号:

TP309

黄昱铭,马建峰,刘志全,冯丙文,魏凯敏. 一种基于规则的自动程序修复方法[J]. 西安电子科技大学学报, 2020, 47(4): 117-123.

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.

图/表 10

图1

图2

图3

图4

图5

图6

表1

表2

图7

图8

参考文献 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)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 15

相关文章 4

Metrics

本文评价

推荐阅读 10

[1]	黄昱铭,马建峰,刘志全,魏凯敏,冯丙文. 自动程序修复中的安全隐患场景及解决方案[J]. 西安电子科技大学学报, 2019, 46(6): 147-154.
[2]	苏子剑;梁昌洪;李龙;翟会清. EBG高阻表面的准静态等效媒质模型[J]. J4, 2015, 42(5): 92-97.
[3]	张立勇；王献青；陈平；邓凡；孔德兰. 一种基于逆向迭代搜索的快速隐通道检测方法[J]. J4, 2011, 38(3): 128-135.
[4]	刘晓建;刘西洋;陈平. 一种在面向对象语言中嵌入规则的预编译器的实现[J]. J4, 2003, 30(1): 97-102.