Finding bugs is easy

ABSTRACT

Many techniques have been developed over the years to automatically find bugs in software. Often, these techniques rely on formal methods and sophisticated program analysis. While these techniques are valuable, they can be difficult to apply, and they aren't always effective in finding real bugs.Bug patterns are code idioms that are often errors. We have implemented automatic detectors for a variety of bug patterns found in Java programs. In this paper, we describe how we have used bug pattern detectors to find serious bugs in several widely used Java applications and libraries. We have found that the effort required to implement a bug pattern detector tends to be low, and that even extremely simple detectors find bugs in real applications.From our experience applying bug pattern detectors to real programs, we have drawn several interesting conclusions. First, we have found that even well tested code written by experts contains a surprising number of obvious bugs. Second, Java (and similar languages) have many language features and APIs which are prone to misuse. Finally, that simple automatic techniques can be effective at countering the impact of both ordinary mistakes and misunderstood language features.

REFERENCES

• 1: Eric Allen, Bug Patterns in Java, APress L. P., 2002
• 2: Apache Ant, http://ant.apache.org/, 2004.
• 3: Cyrille Artho , Armin Biere, Applying Static Analysis to Large-Scale, Multi-Threaded Java Programs, Proceedings of the 13th Australian Conference on Software Engineering, p.68, August 27-28, 2001
• 4: Ken Ashcraft , Dawson Engler, Using Programmer-Written Compiler Extensions to Catch Security Holes, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.143, May 12-15, 2002
• 5: G. Back and D. Engler. MJ: A system for constructing bug-finding analyses for Java. http://www.stanford.edu/~gback/gback-icse2004.pdf, 2003.
• 6: Thomas Ball , Sriram K. Rajamani, The SLAM project: debugging system software via static analysis, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-3, January 16-18, 2002, Portland, Oregon
• 7: The Byte Code Engineering Library, http://jakarta.apache.org/bcel/, 2004.
• 8: Joshua Bloch, Effective Java programming language guide, Sun Microsystems, Inc., Mountain View, CA, 2001
• 9: 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]
• 10: CheckStyle, http://checkstyle.sourceforge.net, 2004.
• 11: Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 12: Andy Chou , Junfeng Yang , Benjamin Chelf , Seth Hallem , Dawson Engler, An empirical study of operating systems errors, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 13: R. F. Crew. ASTLOG: A language for examining abstract syntax trees. In USENIX Conference on Domain Specific Languages, pages 229--241, Santa Barbara, 1997.
• 14: M. C. Daconta, E. Monk, J. P. Keller, and K. Bohnenberger. Java Pitfalls. John Wiley & Sons, Inc., 2000.
• 15: 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
• 16: DrJava, http://www.drjava.org/, 2004.
• 17: A. Druin, B. Bederson, A. Weeks, A. Farber, J. Grosjean, M. Guha, J. Hourcade, J. Lee, S. Liao, K. Reuter, A. Rose, Y. Takayama, L., and L. Zhang. The international children's digital library: Description and analysis of first use. Technical Report HCIL-2003-02, Human-Computer Interaction Lab, Univ. of Maryland, January 2003.
• 18: Eclipse, http://www.eclipse.org/, 2004.
• 19: Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 20: 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, Oct. 2000.
• 21: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957]
• 22: 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
• 23: David Evans , John Guttag , James Horning , Yang Meng Tan, LCLint: a tool for using specifications to check code, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.87-96, December 06-09, 1994, New Orleans, Louisiana, United States
• 24: 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
• 25: Jeffrey S. Foster , Manuel Fähndrich , Alexander Aiken, A theory of type qualifiers, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.192-203, May 01-04, 1999, Atlanta, Georgia, United States
• 26: Jeffrey S. Foster , Tachio Terauchi , Alex Aiken, Flow-sensitive type qualifiers, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 27: GNU Classpath, http://www.gnu.org/software/classpath/, 2004.
• 28: Seth Hallem , Benjamin Chelf , Yichen Xie , Dawson Engler, A system and language for building system-specific, static analyses, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 29: 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]
• 30: D. Hovemeyer and W. Pugh. Finding concurrency bugs in Java. In Proceedings of the PODC Workshop on Concurrency and Synchronization in Java Programs, St. John's, Newfoundland, Canada, July 2004.
• 31: Java(tm) 2 Platform, Standard Edition, http://java.sun.com/j2se/, 2004.
• 32: Collected java practices. http://www.javapractices.com.
• 33: JBoss, http://www.jboss.org/, 2004.
• 34: jEdit, http://www.jedit.org/, 2004.
• 35: S. Johnson, Lint, a C program checker. In UNIX Programmer's Supplementary Documents Volume 1 (PS1), April 1986.
• 36: T. Kremenek and D. R. Engler. Z-ranking: Using statistical analysis to counter the impact of static analysis approximations. In Proceedings of Static Analysis, 10th International Symposium, SAS 2003, San Diego, CA, USA, pages 295--315, June 2003.
• 37: Yanhong A. Liu , Tom Rothamel , Fuxiang Yu , Scott D. Stoller , Nanjun Hu, Parametric regular path queries, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 38: PMD, http://pmd.sourceforge.net, 2004.
• 39: W. Pugh. The double checked locking is broken declaration. http://www.cs.umd.edu/users/pugh/java/memory-Model/DoubleCheckedLocking.html, July 2000.
• 40: Nick Rutar , Christian B. Almazan , Jeffrey S. Foster, A Comparison of Bug Finding Tools for Java, Proceedings of the 15th International Symposium on Software Reliability Engineering (ISSRE'04), p.245-256, November 02-05, 2004 [doi>10.1109/ISSRE.2004.1]
• 41: 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]
• 42: Douglas C. Schmidt , Tim Harrison, Double-checked locking, Pattern languages of program design 3, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 43: U. Shankar, K. Talwar, J. S. Foster, and D. Wagner. Detecting format string vulnerabilities with type qualifiers. In Proceedings of the 10th Usenix Security Symposium, Washington, D.C., Aug. 2001.
• 44: N. Sterling. WARLOCK --- a static data race analysis tool. In Proceedings of the USENIX Annual Technical Conference, pages 97--106, Winter 1993.
• 45: Bruce A. Tate, Bitter Java, Manning Publications Co., Greenwich, CT, 2002
• 46: 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]