Effective identification of failure-inducing changes: a hybrid approach

ABSTRACT

When regression tests fail unexpectedly after a long session of editing, it may be tedious for programmers to find out the failure-inducing changes by manually inspecting all code edits. To eliminate the expensive effort spent on debugging, we present a hybrid approach, which combines both static and dynamic analysis techniques, to automatically identify the faulty changes. Our approach first uses static change impact analysis to isolate a subset of responsible changes for a failed test, then utilizes the dynamic test execution information to rank these changes according to our proposed heuristic (indicating the likelihood that they may have contributed to the failure), and finally employs an improved Three-Phase delta debugging algorithm, working from the coarse method level to the fine statement level, to find a minimal set of faulty statements.

We implemented the proposed approach for both Java and AspectJ programs in our AutoFlow prototype. In our evaluation with two third-party applications, we demonstrate that this hybrid approach can be very effective: at least for the subjective programs we investigated, it takes significantly (almost 4X) fewer tests than the original delta debugging algorithm to locate the faulty code.

REFERENCES

• 1: AspectJ compiler 1.5, May 2005. http://www.eclipse.org/aspectj//.
• 2: AspectJ Development Tools (AJDT). http://www.eclipse.org/ajdt//.
• 3: GDB: The GNU Project Debugger. http://gnu.org/software/gdb.
• 4: The Eclipse Development Platform. http://www.eclipse.org/.
• 5: The XML-Security Project. http://santuario.apache.org/.
• 6: Ophelia C. Chesley , Xiaoxia Ren , Barbara G. Ryder, Crisp: A Debugging Tool for Java Programs, Proceedings of the 21st IEEE International Conference on Software Maintenance, p.401-410, September 25-30, 2005 [doi>10.1109/ICSM.2005.37]
• 7: Jong-Deok Choi , Andreas Zeller, Isolating failure-inducing thread schedules, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 8: Richard A. DeMillo , Hsin Pan , Eugene H. Spafford, Failure and Fault Analysis for Software Debugging, Proceedings of the 21st International Computer Software and Applications Conference, p.515-521, August 11-15, 1997
• 9: Dennis Jeffrey , Neelam Gupta , Rajiv Gupta, Fault localization using value replacement, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA [doi>10.1145/1390630.1390652]
• 10: M. D. Ernst. Static and dynamic analysis: Synergy and duality. In ICSE Workshop on Dynamic Analysis, pages 24--27, May 2003.
• 11: Hyunsook Do , Sebastian Elbaum , Gregg Rothermel, Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential Impact, Empirical Software Engineering, v.10 n.4, p.405-435, October 2005 [doi>10.1007/s10664-005-3861-2]
• 12: Neelam Gupta , Haifeng He , Xiangyu Zhang , Rajiv Gupta, Locating faulty code using failure-inducing chops, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101948]
• 13: David Hovemeyer , William Pugh, Finding bugs is easy, ACM SIGPLAN Notices, v.39 n.12, December 2004 [doi>10.1145/1052883.1052895]
• 14: James A. Jones , Mary Jean Harrold , John Stasko, Visualization of test information to assist fault localization, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581397]
• 15: G. Kiczales, J. Lamping, A. Menhdhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In Proc. 11th European Conference on Object-Oriented Programming, pages 220--242. 1997.
• 16: Ben Liblit , Alex Aiken , Alice X. Zheng , Michael I. Jordan, Bug isolation via remote program sampling, ACM SIGPLAN Notices, v.38 n.5, May 2003
• 17: Ghassan Misherghi , Zhendong Su, HDD: hierarchical delta debugging, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134307]
• 18: Alessandro Orso , Taweesup Apiwattanapong , James Law , Gregg Rothermel , Mary Jean Harrold, An Empirical Comparison of Dynamic Impact Analysis Algorithms, Proceedings of the 26th International Conference on Software Engineering, p.491-500, May 23-28, 2004
• 19: Xiaoxia Ren , Barbara G. Ryder, Heuristic ranking of java program edits for fault localization, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273495]
• 20: Xiaoxia Ren , Fenil Shah , Frank Tip , Barbara G. Ryder , Ophelia Chesley, Chianti: a tool for change impact analysis of java programs, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 21: M. Renieris and S. Reiss. Fault localization with nearest neighbor queries. In In Automated Software Engineering, 2003., 2003.
• 22: Barbara G. Ryder , Frank Tip, Change impact analysis for object-oriented programs, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.46-53, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379661]
• 23: Maximilian Stoerzer , Barbara G. Ryder , Xiaoxia Ren , Frank Tip, Finding failure-inducing changes in java programs using change classification, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181783]
• 24: Tao Xie , Jianjun Zhao, A framework and tool supports for generating test inputs of AspectJ programs, Proceedings of the 5th international conference on Aspect-oriented software development, March 20-24, 2006, Bonn, Germany [doi>10.1145/1119655.1119681]
• 25: Guoqing Xu , Atanas Rountev, Regression Test Selection for AspectJ Software, Proceedings of the 29th international conference on Software Engineering, p.65-74, May 20-26, 2007 [doi>10.1109/ICSE.2007.72]
• 26: M. Young. Symbiosis of static analysis and program testing. In Proc. 6th International Conference on Fundamental Approaches to Software Engineering., pages 1--5, April 2003.
• 27: 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
• 28: 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]
• 29: S. Zhang, Z. Gu, Y. Lin, and J. Zhao. Autoflow: An automatic debugging tool for AspectJ software. In Proc. 24th International Conference on Software Maintenance (ICSM 2008 demo), Oct 2008.
• 30: S. Zhang, Z. Gu, Y. Lin, and J. Zhao. Autoflow: An automatic framework for AspectJ programs. In Technical Report, SJTU-CSE-08-03, Jan 2008.
• 31: Sai Zhang , Zhongxian Gu , Yu Lin , Jianjun Zhao, Celadon: a change impact analysis tool for aspect-oriented programs, Companion of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1370175.1370184]
• 32: S. Zhang, Z. Gu, Y. Lin, and J. Zhao. Change impact analysis for AspectJ programs. In Proc. 24th International Conference on Software Maintenance (ICSM 2008), Oct 2008.
• 33: Xiangyu Zhang , Neelam Gupta , Rajiv Gupta, Locating faults through automated predicate switching, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134324]
• 34: Xiangyu Zhang , Rajiv Gupta , Youtao Zhang, Precise dynamic slicing algorithms, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 35: Jianjun Zhao, Change impact analysis for aspect-oriented software evolution, Proceedings of the International Workshop on Principles of Software Evolution, May 19-20, 2002, Orlando, Florida [doi>10.1145/512035.512060]