Multi-objective coevolutionary automated software correction

ABSTRACT

For a given program, testing, locating the errors identified, and correcting those errors is a critical, yet expensive process. The field of Search Based Software Engineering (SBSE) addresses these phases by formulating them as search problems. The Coevolutionary Automated Software Correction (CASC) system targets the correction phase by coevolving test cases and programs at the source code level. This paper presents the latest version of the CASC system featuring multi-objective optimization and an enhanced representation language. Results are presented demonstrating CASC's ability to successfully correct five seeded bugs in two non-trivial programs from the Siemens test suite. Additionally, evidence is provided substantiating the hypothesis that multi-objective optimization is beneficial to SBSE.

References

1. T. Ackling, B. Alexander, and I. Grunert. Evolving patches for software repair. In Proceedings of GECCO, pages 1427--1434, New York, NY, USA, 2011. ACM.
2. K. Adamopoulos, M. Harman, and R. M. Hierons. How to Overcome the Equivalent Mutant Problem and Achieve Tailored Selective Mutation Using Co-evolution. In Proceedings of GECCO, pages 1338--1349, 2004.
3. S. Ali, L. Briand, H. Hemmati, and R. Panesar-Walawege. A Systematic Review of the Application and Empirical Investigation of Search-Based Test Case Generation. Software Engineering, IEEE Transactions on, 36(6):742--762, 2010.
4. A. Arcuri. Evolutionary repair of faulty software. Applied Soft Computing, 11(4):3494--3514, 2011.
5. A. Arcuri and X. Yao. Co-evolutionary automatic programming for software development. Information Sciences, In Press, 2010.
6. J. S. Bradbury and K. Jalbert. Automatic Repair of Concurrency Bugs. In Proceedings of International SSBSE - Fast Abstacts, Sept. 2010.
7. J. P. Cartlidge. Rules of Engagement: Competitive Coevolutionary Dynamics in Computational Systems. PhD thesis, University of Leeds, 2004.
8. M. L. Collard. Addressing source code using srcml. In IEEE IWCP Working Session Textual Views of Source Code to Support Comprehension, pages 3--5. IEEE, 2005.
9. K. Deb. Multi-Objective Optimization using Evolutionary Algorithms. Wiley-Interscience Series in Systems and Optimization. John Wiley & Sons, Chichester, 2001.
10. R. DeMillo, R. Lipton, and F. Sayward. Hints on Test Data Selection: Help for the Practicing Programmer. Computer, 11(4):34--71, 1978.
11. E. Diaz, R. Blanco, and J. Tuya. Tabu search for automated loop coverage in software testing. In Proceedings of ICKEDS, pages 229--234, 2006.
12. H. Do, S. G. Elbaum, and G. Rothermel. Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential Impact. Empirical Software Engineering: An International Journal, 10(4):405--435, 2005.
13. D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. In Proceedings of the International Conference on Genetic Algorithms and their application, pages 41--49, Hillsdale, NJ, USA, 1987.
14. M. Harman. The Current State and Future of SBSE. In 2007 Future of Software Engineering, FOSE '07, pages 342--357, Washington, DC, USA, 2007. IEEE Computer Society.
15. M. Harman, S. G. Kim, K. Lakhotia, P. McMinn, and S. Yoo. Optimizing for the Number of Tests Generated in Search Based Test Data Generation with an Application to the Oracle Cost Problem. In ICSTW, pages 182--191, 2010.
16. M. Harman, S. A. Mansouri, and Y. Zhang. Search based software engineering: A comprehensive analysis and review of trends techniques and applications. Technical Report TR-09-03, Department of Computer Science, King's College London, Apr. 2009.
17. M. Harman, U. Ph, and B. F. Jones. Search-Based Software Engineering. Information and Software Technology, 43(14):833--839, 2001.
18. W. D. Hillis. Co-evolving Parasites Improve Simulated Evolution as an Optimization Procedure. Physica D, 42(1-3):228--234, 1990.
19. M. Hutchins, H. Foster, T. Goradia, and T. Ostrand. Experiments on the effectiveness of dataflow- and control-flow-based test adequacy criteria. In Proceedings of the ICSE, May 1994.
20. A. Kapoulkine. pugixml Procssing Library. http://www.pugixml.org/, June 2011.
21. J. R. Koza. Genetic Programming III: Darwinian Invention and Problem Solving. Morgan Kaufmann, 1999.
22. K. Lakhotia, M. Harman, and P. McMinn. A multi-objective approach to search-based test data generation. In Proceedings of GECCO, pages 1098--1105, New York, NY, USA, 2007. ACM.
23. D. J. Montana. Strongly Typed Genetic Programming. Evolutionary Computation, 3:199--230, 1994.
24. G. Novark, E. D. Berger, and B. G. Zorn. Exterminator: Automatically correcting memory errors with high probability. Communications of the ACM, 51(12):87--95, Dec. 2008.
25. M. Orlov and M. Sipper. Flight of the FINCH through the Java Wilderness. IEEE Transactions on Evolutionary Computation, 15(2):166--182, 2010.
26. G. Palshikar. Applying formal specifications to real-world software development. IEEE Software, 18(6):89--97, 2001.
27. C. D. Rosin and R. K. Belew. Methods for Competitive Co-evolution: Finding Opponents Worth Beating. In Proceedings of ICGA, pages 373--380, Pittsburgh, PA, 1995. Morgan Kaufmann.
28. C. D. Rosin and R. K. Belew. New Methods for Competitive Coevolution. Evolutionary Computation, 5(1):1--29, 1997.
29. E. Schulte, S. Forrest, and W. Weimer. Automated program repair through the evolution of assembly code. In Proceedings of the IEEE/ACM international conference on ASE, ASE '10, pages 313--316, New York, NY, USA, 2010. ACM.
30. G. Tassey. The economic impacts of inadequate infrastructure for software testing. Technical report, NIST, May 2002.
31. N. Tracey, J. Clark, and J. Mcdermid. Automated test-data generation for exception conditions. Software - Practice and Experience, 30(1):61--79, 2000.
32. W. Weimer, S. Forrest, C. Le Goues, and T. Nguyen. Automatic program repair with evolutionary computation. Communications of the ACM, 53(5), May 2010.
33. J. Wilkerson and D. Tauritz. Coevolutionary Automated Software Correction. In Proceedings of GECCO, pages 1391--1392, 2010.
34. J. L. Wilkerson and D. R. Tauritz. A guide for fitness function design. In Proceedings of GECCO, pages 123--124, New York, NY, USA, 2011. ACM.
35. Y. Zhan and J. A. Clark. The state problem for test generation in Simulink. In Proceedings of GECCO, pages 1941--1948, New York, NY, USA, 2006. ACM.

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