Fault localization and repair for Java runtime exceptions

ABSTRACT

This paper presents a new approach for locating and repairing faults that cause runtime exceptions in Java programs. The approach handles runtime exceptions that involve a flow of an incorrect value that finally leads to the exception. This important class of exceptions includes exceptions related to dereferences of null pointers, arithmetic faults (e.g., ArithmeticException), and type faults (e.g., ArrayStoreException). Given a statement at which such an exception occurred, the technique combines dynamic analysis (using stack-trace information) with static backward data-flow analysis (beginning at the point where the runtime exception occurred) to identify the source statement at which an incorrect assignment was made; this information is required to locate the fault. The approach also identifies the source statements that may cause this same exception on other executions, along with the reference statements that may raise an exception in other executions because of this incorrect assignment; this information is required to repair the fault. The paper also presents an application of our technique to null pointer exceptions. Finally, the paper describes an implementation of the null-pointer-exception analysis and a set of studies that demonstrate the advantages of our approach for locating and repairing faults in the program.

REFERENCES

• 1: William R. Bush , Jonathan D. Pincus , David J. Sielaff, A static analyzer for finding dynamic programming errors, Software—Practice & Experience, v.30 n.7, p.775-802, June 2000 [doi>10.1002/(SICI)1097-024X(200006)30:7<775::AID-SPE309>3.0.CO;2-H]
• 2: David Evans, Static detection of dynamic memory errors, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.44-53, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 3: Manuel Fähndrich , K. Rustan M. Leino, Declaring and checking non-null types in an object-oriented language, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 4: Cormac Flanagan , K. Rustan M. Leino , Mark Lillibridge , Greg Nelson , James B. Saxe , Raymie Stata, Extended static checking for Java, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 5: Chen Fu , Barbara G. Ryder, Exception-Chain Analysis: Revealing Exception Handling Architecture in Java Server Applications, Proceedings of the 29th international conference on Software Engineering, p.230-239, May 20-26, 2007 [doi>10.1109/ICSE.2007.35]
• 6: Sudheendra Hangal , Monica S. Lam, Tracking down software bugs using automatic anomaly detection, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581377]
• 7: David Hovemeyer , Jaime Spacco , William Pugh, Evaluating and tuning a static analysis to find null pointer bugs, Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, September 05-06, 2005, Lisbon, Portugal
• 8: B. Korel , J. Laski, Dynamic program slicing, Information Processing Letters, v.29 n.3, p.155-163, October 26, 1988 [doi>10.1016/0020-0190(88)90054-3]
• 9: Alexey Loginov , Eran Yahav , Satish Chandra , Stephen Fink , Noam Rinetzky , Mangala Nanda, Verifying dereference safety via expanding-scope analysis, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA [doi>10.1145/1390630.1390657]
• 10: Mangala Gowri Nanda , Saurabh Sinha, Accurate Interprocedural Null-Dereference Analysis for Java, Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, p.133-143, May 16-24, 2009 [doi>10.1109/ICSE.2009.5070515]
• 11: Martin P. Robillard , Gail C. Murphy, Static analysis to support the evolution of exception structure in object-oriented systems, ACM Transactions on Software Engineering and Methodology (TOSEM), v.12 n.2, p.191-221, April 2003 [doi>10.1145/941566.941569]
• 12: Atanas Rountev , Scott Kagan , Michael Gibas, Evaluating the imprecision of static analysis, Proceedings of the 5th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA [doi>10.1145/996821.996829]
• 13: Hina Shah , Carsten Görg , Mary Jean Harrold, Visualization of exception handling constructs to support program understanding, Proceedings of the 4th ACM symposium on Software visualization, September 16-17, 2008, Ammersee, Germany [doi>10.1145/1409720.1409724]
• 14: Saurabh Sinha , Alessandro Orso , Mary Jean Harrold, Automated Support for Development, Maintenance, and Testing in the Presence of Implicit Control Flow, Proceedings of the 26th International Conference on Software Engineering, p.336-345, May 23-28, 2004
• 15: Aaron Tomb , Guillaume Brat , Willem Visser, Variably interprocedural program analysis for runtime error detection, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273478]
• 16: M. Weiser. Program slicing. IEEE Trans. Softw. Eng., 10(4):352--357, July 1984.
• 17: Yichen Xie , Dawson Engler, Using redundancies to find errors, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587060]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
fault localization, null dereference, runtime exceptions, static analysis