On the automation of fixing software bugs

ABSTRACT

Software Testing can take up to half of the resources of the development of new software. Although there has been a lot of work on automating the testing phase, fixing a bug after its presence has been discovered is still a duty of the programmers. Techniques to help the software developers for locating bugs exist though, and they take name of Automated Debugging. However, to our best knowledge, there has been only little attempt in the past to completely automate the actual changing of the software for fixing the bugs. Therefore, in this paper we propose an evolutionary approach to automate the task of fixing bugs. The basic idea is to evolve the programs (e.g., by using Genetic Programming) with a fitness function that is based on how many unit tests they are able to pass. If a formal specification of the buggy software is given, more sophisticated fitness functions can be designed. Moreover, by using the formal specification as an oracle, we can generate as many unit tests as we want. Hence, a co-evolution between programs and unit tests might take place to give even better results. It is important to know that, to fix the bugs in a program with this novel approach, a user needs only to provide either a formal specification or a set of unit tests. No other information is required.

References

1. A. Arcuri and X. Yao. A novel co-evolutionary approach to automatic software bug fixing. To appear in the IEEE Congress on Evolutionary Computation (CEC), 2008.
2. A. Arcuri and X. Yao. Coevolving programs and unit tests from their specification. In IEEE International Conference on Automated Software Engineering (ASE), pages 397---400, 2007.
3. A. Arcuri and X. Yao. Search based software testing of objeot-oriented containers. Information Sciences, 2008. Accepted for publication.
4. H. Barringer, D. Rydeheard, and D. Gabbay. A logical framework for monitoring and evolving software components. In IEEE/IFIP Symposium on Theoretical Aspects of Software Engineering (TASE), pages 273--282, 2007.
5. B. Beizer. Software Testing Techniques. Van Nostrand Rheinhold, New York, 1990.
6. K. Deb. Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley and Sons, 2001.
7. R. A. DeMillo, R. J. Lipton, and F. Sayward. Hints on test data selection: Help for the practicing programmer. Computer, 11(4):34--41, 1978.
8. S. G. Ficici and J. B. Pollack. Challenges in coevolutionary learning: Arms-race dynamics, open-endedness, and mediocre stable states. In Artificial Life VI, pages 238--247, 1998.
9. J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. The MIT Press, 1992.
10. W. B. Langdon and R. Poli. Foundations of Genetic Programming. Springer, 2002.
11. P. McMinn. Search-based software test data generation: A survey. Software Testing, Verification and Reliability, 14(2):105--156, June 2004.
12. G. Myers. The Art of Software Testing. Wiley, New York, 1979.
13. G. Palshikar. Applying formal specifications to real-world software development. IEEE Software, 18(6):89--97, 2001.
14. M. Reformat, C. Xinwei, and J. Miller. On the possibilities of (pseudo-) software cloning from external interactions. Soft Computing, 12(1):29--49, 2007.
15. M. Renieris and S. Reiss. Fault localization with nearest neighbor queries. In IEEE International Conference on Automated Software Engineering (ASE), pages 30--39, 2003.
16. C. Rich and R. C. Waters. Automatic programming: myths and prospects. Computer, 21(8):40--51, 1988.
17. C. D. Rosin and R. K. Belew. New methods for competitive coevolution. Evolutionary Computation, 5(1):1--29, 1997.
18. S. Staber, B. Jobstmann, and R. Bloem. Finding and fixing faults. In 13th Conference on Correct Hardware Design and Verification Methods (CHARME), pages 35--49, 2005.
19. M. Stumptner and F. Wotawa. Model-based program debugging and repair. In Proceedings of the International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, 1996.
20. G. Tassey. The economic impacts of inadequate infrastructure for software testing, final report. National Institute of Standards and Technology, 2002.
21. N. J. Tracey. A Search-Based Automated Test Data Generation Framework for Safety-Critical Software. PhD thesis, University of York, 2000.
22. W. Weimer, "Patches as better bug reports," in phProceedings of the 5th international conference on Generative programming and component engineering, 2006, pp. 181---190.
23. A. Zeller. Automated debugging: Are we close? IEEE Computer, pages 26--31, November 2001.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Search methodologies

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming