A Study of Applying Fault-based Genetic-Like Programming Approaches to Automatic Software Fault Corrections

doi:10.23940/ijpe.18.09.p18.20902104

Abstract

Abstract: Correcting software bugs automatically is challenging because the process poses many uncertainties. As the size and complexity of software increases, manually correcting software bugs becomes very difficult. Hence, automatic software repair has become increasingly essential. Genetic programming (GP) is a method for addressing this problem, as research has applied it to find ways to repair faulty programs in recent years. Nevertheless, most of the variants generated by GP are not precise in detecting repair solutions. In this paper, we propose a fault-based genetic-like programming approach that heuristically searches all possible variants as they increase with the number of modifications. Our method is able to find the best repairs for programs with fewer faults, faster than genetic programming. However, the cost is that heuristically searching for suitable repairs is time-consuming. Hence, we have also optimized our approach to speed up performance. In this study, our approach was used to repair faulty C programs, and the results were compared with those generated by genetic programming. The results show that our approach better detected faulty programs in up to 18000 lines of code when the number of program faults was less than two.

Key words: component, automatic software repair, genetic programming, fault localization

Chia-Hao Lee, Chin-Yu Huang, and Tzu-Yang Lin. A Study of Applying Fault-based Genetic-Like Programming Approaches to Automatic Software Fault Corrections [J]. Int J Performability Eng, 2018, 14(9): 2090-2104.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

[1] A. Arcuri, “On the Automation of Fixing Software Bugs,” inProceedings of the 30th International Conference Software Engineering (ICSE), pp. 1003-1006, Leipzig, Germany, May 2008
[2] B. Korel and A. M. Al-Yami, “Assertion-Oriented Automated Test Data Generation,” inProceedings of the 18th International Conference on Software Engineering (ICSE), pp. 71-80, Berlin, Germany, March 1996
[3] A. E.Eiben and J. E. Smith, “Introduction to Evolutionary Computing,” Springer, Vol. 53, Heidelberg, Germany, 2003
[4] J. Edvardsson, “A Survey on Automatic Test Data Generation,” inProceedings of the 2nd Conference on Computer Science Engineering (CSE), pp. 21-28, Linköping, Sweden, October 1999
[5] J. R. Koza, “Genetic Programming: On the Programming of Computers by Means of Natural Selection. Massachusetts,” USA: MIT Press, 1992
[6] J. L.Wilkerson and D. Tauritz, “Coevolutionary Automated Software Correction,” inProceedings of the 12th Conference on Genetic and Evolutionary Computation (GECCO), pp. 1391-1392, Portland or USA, July 2010
[7] M. Auguston, C. Jeffery,S. Underwood, “A Framework for Automatic Debugging,” inProceedings of the 17th IEEE International Conference on Automated Software Engineering (ASE), pp. 217-222, Edinburgh, UK, September 2002
[8] Y. C. Huang, C. Y. Huang, J. R. Chang,T. Y. Chen, “A Study of Cost-Cognizant Test Case Prioritization using Genetic Algorithm with Test History,” inProceedings of the 34th Annual IEEE International Computer Software and Applications Conference (COMPSAC), pp. 413-418, Seoul, South Korea, July 2010
[9] R. Poli, W. B. Langdon,N. F.McPhee, “A Field Guide to Genetic Programming,” (http://www.gp-field-guide.org.uk, accessed May 2018
[10] S. Staber, B. Jobstmann,R. Bloem, “Finding and Fixing Faults,” inProceedings of the 13th Conference on Correct Hardware Design and Verification Methods (CHARME), pp. 35-49, Saarbrücken, Germany, October 2005
[11] A. Zeller, “Automated Debugging: Are We Close?” Computer, Vol. 34, No. 11, pp. 26-31, November 2001
[12] B. Jobstmann, A. Griesmayer,R. Bloem, “Program Repair as a Game,” inProceedings of the 17th International Conference on Computer Aided Verification (CAV), pp. 226-238, Edinburgh, Scotland, UK, July 2005
[13] T. Mens and T. Tourwé, “A Survey of Software Refactoring,” IEEE Transactions on Software Engineering, Vol. 30, No. 2, pp. 126-139, February 2004
[14] W. Weimer, “Patches as Better Bug Reports,” inProceedings of the 5th International Conference on Generative Programming and Component Engineering (GPCE), pp. 181-190, Portland, Oregon, USA, October 2006
[15] A. Arcuri and X. Yao, “A Novel Co-Evolutionary Approach to Automatic Software Bug Fixing,” inProceedings of the IEEE Congress on Evolutionary Computation (CEC), pp. 162-168, Hong Kong, China, June 2008
[16] J. Clarke, et al., “Reformulating Software Engineering as a Search Problem,” in Proceedings of the Software, Vol. 150, No. 3, pp. 161-175, Junuary 2003
[17] M. Harman and B. F. Jones, “Search-based Software Engineering,” Information and Software Technology, Vol. 43, No. 14, pp. 833-839, December 2001
[18] S. Forrest, T. Nguyen, W. Weimer,C. L. Goues, “A Genetic Programming Approach to Automated Software Repair,” inProceedings of the 11th Conference on Genetic and Evolutionary Computation (GECCO), pp. 947-954, Montreal, Québec, Canada, July 2009
[19] W. Weimer, S. Forrest, C. Le Goues, N. Claire,T. Nguyen, “Automatic Program Repair with Evolutionary Computation,” Communications of the ACM, Vol. 53, No. 5, pp. 109-116, May 2010
[20] W. Weimer, T. Nguyen, C. Le Goues,S. Forrest, “Automatically Finding Patches using Genetic Programming,” inProceedings of the 31st International Conference on Software Engineering (ICSE), pp. 364-374, DC, USA, May 2009
[21] J. H.Perkins et al., “Automatically Patching Errors in Deployed Software,” inProceedings of the 22nd ACM SIGOPS Symposium on Operating Systems Principles (SOSP), pp. 87-102, Big Sky, Montana, USA, October 2009
[22] B. Demsky and M. Rinard, “Automatic Detection and Repair of Errors in Data Structures,” inProceedings of the 18th Conference on Object-Oriented Programming, Systems, Languages, and Applications(OOPSLA), pp. 78-95, Anaheim, California, USA, October 2003.
[23] B. Elkarablieh and S. Khurshid. “Juzi: A Tool for Repairing Complex Data Structures,” inProceedings of the 30th International Conference on Software Engineering (ICSE), pp. 855-858, Leipzig, Germany, May 2008
[24] M. Z. Malik, K. Ghori, B. Elkarablieh,S. Khurshid, “A Case for Automated Debugging using Data Structure Repair,” in Proceedings of the 24th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 620-624, Auckland, New Zealand, November 2009
[25] C. Le Goues, T. V. Nguyen, S. Forrest,W. Weimer, “Genprog: A Generic Method for Automatic Software Repair,” IEEE Transactions on Software Engineering, Vol. 38, No. 1, pp. 54-72, January 2012
[26] D. Kim, J. Nam, J. Song,S. Kim, “Automatic Patch Generation Learned from Human-Written Patches,” inProceedings of the 35th International Conference on Software Engineering (ICSE), pp. 802-811, San Francisco, California, USA, May 2013
[27] F. Long and M. Rinard, “Staged Program Repair with Condition Synthesis,” inProceedings of the 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE), pp. 166-178, Bergamo, Italy, August 2015
[28] S. Mechtaev, J. Yi,A. Roychoudhury, “Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis,” inProceedings of the 38th International Conference on Software Engineering (ICSE), pp. 691-701, Austin, Texas, USA, May 2016
[29] H. D. T.Nguyen, D. Qi, A. Roychoudhury, and S. Chandra, “Semfix: Program Repair via Semantic Analysis,” inProceedings of the 35th International Conference on Software Engineering (ICSE), pp. 772-781, San Francisco, California, USA, May 2013
[30] F. DeMarco, J. Xuan, D. Le Berre,M. Monperrus, “Automatic Repair of Buggy If Conditions and Missing Preconditions with SMT,” inProceedings of the 6th Workshop on Constraints in Software Testing, Verification, and Analysis (CSTVA), pp. 30-39, Hyderabad, India, May 2014
[31] S. Mechtaev, J. Yi,A. Roychoudhury, “Directfix: Looking for Simple Program Repairs,” inProceedings of the 37th International Conference on Software Engineering (ICSE), pp. 448-458, Florence, Italy, May 2015
[32] C. J.Hsu and C. Y. Huang, “A Study on the Applicability of Modified Genetic Algorithms for the Parameter Estimation of Software Reliability Modeling,” inProceedings of the 34th Annual IEEE International Computer Software and Applications Conference (COMPSAC), pp. 531-540, Seoul, South Korea, July 2010
[33] C. J. Hsu, C. Y. Huang,T. Y. Chen, “A Modified Genetic Algorithm for Parameter Estimation of Software Reliability Growth Models,” inProceedings of the 19th IEEE International Symposium on Software Reliability Engineering (ISSRE), pp. 281-282, Seattle, Washington, November 2008
[34] G. C. Necula, S. McPeak, S. P. Rahul,W. Weimer, “Cil: Intermediate Language and Tools for Analysis and Transformation of C Programs,” inProceedings of the 11th International Conference on Compiler Construction (CC), pp. 213-228, Grenoble, France, April 2002
[35] T. Ball, M. Naik,S. K. Rajamani, “From Symptom to Cause: Localizing Errors in Counterexample Traces,” ACM SIGPLAN Notices, Vol. 38, No. 1, pp. 97-105, January 2003
[36] J. A.Jones and M. J. Harrold, “Empirical Evaluation of the Tarantula Automatic Fault-Localization Technique,” inProceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 273-282, Long Beach, California, USA, November 2005
[37] V. Debroy and W. E. Wong, “Using Mutation to Automatically Suggest Fixes for Faulty Programs,” inProceedings of the 3th International Conference on Software Testing, Verification and Validation (ICST), pp. 65-74, Paris, France, April 2010
[38] E. Fast, C. Le Goues, S. Forrest,W. Weimer, “Designing Better ﬁtness Functions for Automated Program Repair,” inProceedings of the 12th Conference on Genetic and Evolutionary Computation (GECCO), pp. 965-972, Portland, Oregon, USA, July 2010
[39] C. H. Lee, “Analysis of Automatic Software Correction using A Fault-Based Genetic-Like Programming Approach,” M. S. Thesis, Institute of Information Systems and Applications, National Tsing Hua University, Hsinchu, Taiwan, 2011