Automatic Repair of C Program Memory Error Guided by Tracking Mechanism

doi:10.3778/j.issn.1002-8331.2202-0254

Abstract

Abstract: C is a highly efficient and widely used language, but its widespread use has been accompanied by growing security issues. The memory error is a common error in C programs, which will cause the system to collapse in severe cases. Manually fixing memory error requires considerable efforts, and potentially introduces new errors in the repair process. To address this problem, an automatic program repair method based on tracking mechanism is proposed. Firstly, it constructs the scope-tree containing the distribution of variables in the program file. Then, a global pointer-based tracking mechanism is proposed to track the state of allocated memory with errors in the program. Finally, a patch is automatically generated based on a global pointer, and a scope-tree is used to locate where the defect is fixed so that the memory error can be safely repaired. Based on the above process, the prototype tool DTSFix has implemented, in addition evaluated it with open-source programs. The experimental results show that DTSFix can effectively detect and repair the real defects in open-source programs without side effects.

Key words: tracing mechanism, automatic program repair, memory errors, scope tree

摘要： C语言执行效率高，使用范围广泛，然而存在的安全问题也日益突出。内存错误是C程序中常见的缺陷，严重时将导致系统崩溃。传统的人工修复内存错误耗费大量人力物力，并可能在修复过程中引入新的错误。针对这个问题，提出了一种基于跟踪机制的程序自动修复方法。构建包含程序文件中变量作用分布的作用域树；提出基于全局指针的跟踪机制，通过插入全局指针跟踪发生错误的分配内存在程序中的状态；基于全局指针自动生成补丁，利用作用域树定位缺陷修复位置从而来安全地修复内存错误。基于上述过程，实现了原型工具DTSFix，并在开源程序中对其进行了评估。实验结果表明，DTSFix能够有效检测并修复程序中的真实缺陷而且不产生副作用。

关键词: 跟踪机制, 程序自动修复, 内存错误, 作用域树

DONG Yukun, WEI Xinxin, SUN Yuxue, TANG Daolong. Automatic Repair of C Program Memory Error Guided by Tracking Mechanism[J]. Computer Engineering and Applications, 2022, 58(19): 76-87.

董玉坤, 位欣欣, 孙玉雪, 唐道龙. 跟踪机制引导的C程序内存错误自动修复[J]. 计算机工程与应用, 2022, 58(19): 76-87.

References

[1] 姜佳君，陈俊洁，熊英飞.软件缺陷自动修复技术综述[J].软件学报2021，32（9）：2665-2690.
JIANG J J，CHEN J J，XIONG Y F.Survey of automatic program repair techniques[J].Journal of Software，2021，32（9）：2665-2690.
[2] PEARSON S，CAMPOS J，JUST R，et al.Evaluating and improving fault localization[C]//Proceedings of the 2017 IEEE/ACM 39th International Conference on Software Engineering（ICSE），2017：609-620.
[3] BIAN P，LIANG B，SHI W，et al.Nar-miner：Discovering negative association rules from code for bug detection[C]//Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering，2018：411-422.
[4] LIANG B，BIAN P，ZHANG Y，et al.AntMiner：Mining more bugs by reducing noise interference[C]//Proceedings of the 38th International Conference on Software Engineering，2016：333-344.
[5] WONG W E，GAO R，LI Y，et al.A survey on software fault localization[J].IEEE Transactions on Software Engineering，2016，42（8）：707-740.
[6] 许健，陈平华，熊建斌.基于抽象内存模型的内存相关漏洞检测方法[J].计算机工程与应用，2022，58（8）：96-108.
XU J，CHEN P H，XIONG J B.Memory-related vulnerability detection method based on abstract memory model[J].Computer Engineering and Applications，2022，58（8）：96-108.
[7] ZHANG Y，JIN D，XING Y，et al.Automated defect identification via path analysis-based features with transfer learning[J].Journal of Systems and Software，2020，166：110585.
[8] JUST R，PARNIN C，DROSOS I，et al.Comparing developer-provided to user-provided tests for fault localization and automated program repair[C]//Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis，2018：287-297.
[9] GOUES C L，PRADEL M，ROYCHOUDHURY A.Automated program repair[J].Communications of the ACM，2019，62（12）：56-65.
[10] WEN M，CHEN J，WU R，et al.Context-aware patch generation for better automated program repair[C]//Proceedings of the 2018 IEEE/ACM 40th International Conference on Software Engineering（ICSE），2018：1-11.
[11] LIU K，KOYUNCU A，KIM D，et al.TBar：Revisiting template-based automated program repair[C]//Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis，2019：31-42.
[12] KOYUNCU A，LIU K，BISSYANDé T F，et al.Fixminer：Mining relevant fix patterns for automated program repair[J].Empirical Software Engineering，2020，25（3）：1980-2024.
[13] LIN H，WANG Z，LIU S，et al.Pfix：Fixing concurrency bugs based on memory access patterns[C]//Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering，2018：589-600.
[14] YU B，TIAN C，ZHANG N，et al.A dynamic approach to detecting，eliminating and fixing memory leaks[J].Journal of Combinatorial Optimization，2021，42（3）：409-426.
[15] GHANAVATI M，COSTA D，SEBOEK J，et al.Memory and resource leak defects and their repairs in Java projects[J].Empirical Software Engineering，2020，25（1）：678-718.
[16] MONPERRUS M.Automatic software repair：A bibliography[J].ACM Computing Surveys（CSUR），2018，51（1）：1-24.
[17] 王淑栋，尹文静，董玉坤，等.面向顺序存储结构的数据流分析[J].软件学报，2020，31（5）：18.
WANG S D，YIN W J，DONG Y K，et al.Data flow analysis for sequential storage structures[J].Journal of Software，2020，31（5）：18.
[18] KOYUNCU A，LIU K，BISSYANDé T F，et al.iFixR：Bug report driven program repair[C]//Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering，2019：314-325.
[19] JEON M，JEONG S，CHA S，et al.A machine-learning algorithm with disjunctive model for data-driven program analysis[J].ACM Transactions on Programming Languages and Systems，2019，41（2）：1-41.
[20] WHITE M，TUFANO M，MARTINEZ M，et al.Sorting and transforming program repair ingredients via deep learning code similarities[C]//Proceedings of the 2019 IEEE 26th International Conference on Software Analysis，Evolution and Reengineering（SANER），2019：479-490.
[21] JIANG J，XIONG Y，ZHANG H，et al.Shaping program repair space with existing patches and similar code[C]//Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis，2018：298-309.
[22] VILLANUEVA O M，TRUJILLO L，HERNANDEZ D E.Novelty search for automatic bug repair[C]//Proceedings of the 2020 Genetic and Evolutionary Computation Conference，2020：1021-1028.
[23] KIM J，KIM S.Automatic patch generation with context-based change application[J].Empirical Software Engineering，2019，24（6）：4071-4106.
[24] YUAN Y，BANZHAF W.Toward better evolutionary program repair：An integrated approach[J].ACM Transactions on Software Engineering and Methodology（TOSEM），2020，29（1）：1-53.
[25] MECHTAEV S，YI J，ROYCHOUDHURY A.Angelix：Scalable multiline program patch synthesis via symbolic analysis[C]//Proceedings of the 38th International Conference on Software Engineering，2016：691-701.
[26] MECHTAEV S，NGUYEN M D，NOLLER Y，et al.Semantic program repair using a reference implementation[C]//Proceedings of the 40th International Conference on Software Engineering，2018：129-139.
[27] AFZAL A，MOTWANI M，STOLEE K T，et al.SOSRepair：Expressive semantic search for real-world program repair[J].IEEE Transactions on Software Engineering，2019，47（10）：2162-2181.
[28] NODA K，YOKOYAMA H，KIKUCHI S.Sirius：Static program repair with dependence graph-based systematic edit patterns[C]//Proceedings of the 2021 IEEE International Conference on Software Maintenance and Evolution（ICSME），2021：437-447.
[29] HUA J，ZHANG M，WANG K，et al.Towards practical program repair with on-demand candidate generation[C]//Proceedings of the 40th International Conference on software Engineering，2018：12-23.
[30] HU Y，AHMED U Z，MECHTAEV S，et al.Re-factoring based program repair applied to programming assignments[C]//Proceedings of the 2019 34th IEEE/ACM International Conference on Automated Software Engineering（ASE），2019：388-398.
[31] SAHA S.Harnessing evolution for multi-hunk program repair[C]//Proceedings of the 2019 IEEE/ACM 41st International Conference on Software Engineering（ICSE），2019：13-24.
[32] SIDIROGLOU-DOUSKOS S，LAHITNEN E，LONG F，et al.Automatic error elimination by horizontal code transfer across multiple applications[C]//Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation，2015：43?54.
[33] BADER J，SCOTT A，PRADEL M，et al.Getafix：Learning to fix bugs automatically[J].Proceedings of the ACM on Programming Languages，2019，3：1-27.
[34] GUPTA R，PAL S，KANADE A，et al.Deepfix：Fixing common C language errors by deep learning[C]//Proceedings of the 33rd AAAI Conference on Artificial Intelligence，2017.
[35] CHEN Z，KOMMRUSCH S，TUFANO M，et al.Sequencer：Sequence-to-sequence learning for end-to-end program repair[J].IEEE Transactions on Software Engineering，2019，47（9）：1943-1959.
[36] VASIC M，KANADE A，MANIATIS P，et al.Neural program repair by jointly learning to localize and repair[J].arXiv：1904.01720，2019.
[37] LEE J，HONG S，OH H.MemFix：Static analysis-based repair of memory deallocation errors for C[C]//Proceedings of the 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering，2018：95-106.
[38] GAO Q，XIONG Y，MI Y，et al.Safe memory-leak fixing for C programs[C]//Proceedings of the 37th IEEE International Conference on Software Engineering，2015：459-470.
[39] VAN TONDER R，LE GOUES C.Static automated program repair for heap properties[C]//Proceedings of the 40th International Conference on Software Engineering，2018：151-162.
[40] HONG S，LEE J，LEE J，et al.Saver：Scalable，precise，and safe memory-error repair[C]//Proceedings of the 42nd International Conference on Software Engineering，2020：271-283.
[41] HUA Y，SUI Y，CHEN S，et al.Automated memory leak fixing on value-flow slices for C programs[C]//Proceedings of the ACM Symposium on Applied Computing，2016.
[42] FAN G，WU R，SHI Q，et al.Smoke：Scalable path-sensitive memory leak detection for millions of lines of code[C]//Proceedings of the 41st International Conference on Software Engineering，2019：72-82.
[43] KOH Y，KANG S，LEE S.Bug report summarization using believability score and text ranking[C]//Proceedings of the 3rd International Conference on Artificial Intelligence in Information and Communication，2021：117-120.
[44] CALCAGNO C，DISTEFANO D，DUBREIL J，et al.Moving fast with software verification[C]//Proceedings of the NASA Formal Methods Symposium.Cham：Springer，2015：3-11.