A genetic programming approach to automated software repair

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A genetic programming approach to automated software repair

Full text

Pdf (470 KB)

Source

Genetic And Evolutionary Computation Conference archive
Proceedings of the 11th Annual conference on Genetic and evolutionary computation table of contents

Montreal, Québec, Canada

SESSION: Track 10: genetic programming table of contents

Pages 947-954

Year of Publication: 2009

ISBN:978-1-60558-325-9

Authors

Stephanie Forrest	University of New Mexico, Albuquerque, NM, USA
ThanhVu Nguyen	University of New Mexico, Albuquerque, NM, USA
Westley Weimer	University of Virginia, Charlottesville, VA, USA
Claire Le Goues	University of Virginia, Charlottesville, VA, USA

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 46, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1569901.1570031 What is a DOI?

ABSTRACT

Genetic programming is combined with program analysis methods to repair bugs in off-the-shelf legacy C programs. Fitness is defined using negative test cases that exercise the bug to be repaired and positive test cases that encode program requirements. Once a successful repair is discovered, structural differencing algorithms and delta debugging methods are used to minimize its size. Several modifications to the GP technique contribute to its success: (1) genetic operations are localized to the nodes along the execution path of the negative test case; (2) high-level statements are represented as single nodes in the program tree; (3) genetic operators use existing code in other parts of the program, so new code does not need to be invented. The paper describes the method, reviews earlier experiments that repaired 11 bugs in over 60,000 lines of code, reports results on new bug repairs, and describes experiments that analyze the performance and efficacy of the evolutionary components of the algorithm.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Monica S. Lam , Ravi Sethi , Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools (2nd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
	2	Raihan Al-Ekram , Archana Adma , Olga Baysal, diffX: an algorithm to detect changes in multi-version XML documents, Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research, p.1-11, October 17-20, 2005, Toranto, Ontario, Canada
	3	Andrea Arcuri, On the automation of fixing software bugs, Companion of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1370175.1370223]
	4	Andrea Arcuri , David Robert White , John Clark , Xin Yao, Multi-objective Improvement of Software Using Co-evolution and Smart Seeding, Proceedings of the 7th International Conference on Simulated Evolution and Learning, December 07-10, 2008, Melbourne, Australia [doi>10.1007/978-3-540-89694-4_7]
	5	A. Arcuri and X. Yao. A novel co-evolutionary approach to automatic software bug fixing. In IEEE Congress on Evolutionary Computation, 2008.
	6	Thomas Ball , Mayur Naik , Sriram K. Rajamani, From symptom to cause: localizing errors in counterexample traces, ACM SIGPLAN Notices, v.38 n.1, p.97-105, January 2003
	7	Thomas Ball , Sriram K. Rajamani, Automatically validating temporal safety properties of interfaces, Proceedings of the 8th international SPIN workshop on Model checking of software, p.103-122, May 2001, Toronto, Ontario, Canada
	8	BBC News. Microsoft zune affected by 'bug'. In http://news.bbc.co.uk/2/hi/technology/7806683.stm, Dec. 2008.
	9	Theodore B. Van Belle , David H. Ackley, Modularity and the evolution of software evolvability, University of New Mexico, Albuquerque, NM, 2004
	10	Terry Van Belle , David H. Ackley, Code Factoring And The Evolution Of Evolvability, Proceedings of the Genetic and Evolutionary Computation Conference, p.1383-1390, July 09-13, 2002
	11	Robert V. Binder, Testing object-oriented systems: models, patterns, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
	12	Brian Demsky , Michael D. Ernst , Philip J. Guo , Stephen McCamant , Jeff H. Perkins , Martin Rinard, Inference and enforcement of data structure consistency specifications, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146266]
	13	B. Demsky and M. C. Rinard. Automatic data structure repair for self-healing systems. In Object-Oriented Programming, Systems, Languages, and Applications. 2003.
	14	Stephanie Forrest , Steven A. Hofmeyr , Anil Somayaji , Thomas A. Longstaff, A Sense of Self for Unix Processes, Proceedings of the 1996 IEEE Symposium on Security and Privacy, p.120, May 06-08, 1996
	15	Mark Gabel , Zhendong Su, Symbolic mining of temporal specifications, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368096]
	16	David Hovemeyer , William Pugh, Finding bugs is easy, Companion to the 19th annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 24-28, 2004, Vancouver, BC, CANADA [doi>10.1145/1028664.1028717]
	17	Ben Liblit , Alex Aiken , Alice X. Zheng , Michael I. Jordan, Bug isolation via remote program sampling, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
	18	G. C. Necula, S. McPeak, S. P. Rahul, and W. Weimer. Cil: An infrastructure for C program analysis and transformation. In International Conference on Compiler Construction, pages 213--228, Apr. 2002.
	19	Thomas M. Pigoski, Practical Software Maintenance: Best Practices for Managing Your Software Investment, John Wiley & Sons, Inc., New York, NY, 1996
	20	Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
	21	Kristen R. Walcott , Mary Lou Soffa , Gregory M. Kapfhammer , Robert S. Roos, TimeAware test suite prioritization, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146240]
	22	Westley Weimer, Patches as better bug reports, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA [doi>10.1145/1173706.1173734]
	23	Westley Weimer , ThanhVu Nguyen , Claire Le Goues , Stephanie Forrest, Automatically finding patches using genetic programming, Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, p.364-374, May 16-24, 2009 [doi>10.1109/ICSE.2009.5070536]
	24	Andreas Zeller, Yesterday, my program worked. Today, it does not. Why?, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.253-267, September 06-10, 1999, Toulouse, France
	25	Andreas Zeller , Ralf Hildebrandt, Simplifying and Isolating Failure-Inducing Input, IEEE Transactions on Software Engineering, v.28 n.2, p.183-200, February 2002 [doi>10.1109/32.988498]