Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Using static analysis to detect memory access errors, such as null pointer dereferences, is not a new problem. However, much of the previous work has used rather sophisticated analysis techniques in order to detect such errors.In this paper we show that simple analysis techniques can be used to identify many such software defects, both in production code and in student code. In order to make our analysis both simple and effective, we use a non-standard analysis which is neither complete nor sound. However, we find that it is effective at finding an interesting class of software defects.We describe the basic analysis we perform, as well as the additional errors we can detect using techniques such as annotations and inter-procedural analysis.In studies of both production software and student projects, we find false positive rates of around 20% or less. In the student code base, we find that our static analysis techniques are able to pinpoint 50% to 80% of the defects leading to a null pointer exception at runtime.

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: Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 3: Eclipse. http://www.eclipse.org, 2005.
• 4: D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Proceedings of the Fourth Symposium on Operating Systems Design and Implementation, San Diego, CA, October 2000.
• 5: 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
• 6: 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
• 7: C. Flanagan, K. Leino, M. Lillibridge, C. Nelson, J. Saxe, and R. Stata. Extended static checking for Java, 2002.
• 8: 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]
• 9: Atanas Rountev , Scott Kagan , Michael Gibas, Evaluating the imprecision of static analysis, Proceedings of the ACM-SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA [doi>10.1145/996821.996829]
• 10: Jaime Spacco , Jaymie Strecker , David Hovemeyer , William Pugh, Software repository mining with Marmoset: an automated programming project snapshot and testing system, Proceedings of the 2005 international workshop on Mining software repositories, p.1-5, May 17-17, 2005, St. Louis, Missouri
• 11: 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:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Experimentation, Measurement, Reliability

Keywords:
static analysis, testing