Tracking down software bugs using automatic anomaly detection

ABSTRACT

This paper introduces DIDUCE, a practical and effective tool that aids programmers in detecting complex program errors and identifying their root causes. By instrumenting a program and observing its behavior as it runs, DIDUCE dynamically formulates hypotheses of invariants obeyed by the program. DIDUCE hypothesizes the strictest invariants at the beginning, and gradually relaxes the hypothesis as violations are detected to allow for new behavior. The violations reported help users to catch software bugs as soon as they occur. They also give programmers new visibility into the behavior of the programs such as identifying rare corner cases in the program logic or even locating hidden errors that corrupt the program's results.We implemented the DIDUCE system for Java programs and applied it to four programs of significant size and complexity. DIDUCE succeeded in identifying the root causes of programming errors in each of the programs quickly and automatically. In particular, DIDUCE is effective in isolating a timing-dependent bug in a released JSSE (Java Secure Socket Extension) library, which would have taken an experienced programmer days to find. Our experience suggests that detecting and checking program invariants dynamically is a simple and effective methodology for debugging many different kinds of program errors across a wide variety of application domains.

REFERENCES

• 1: Thoms Bell, The concept of dynamic analysis, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.216-234, September 06-10, 1999, Toulouse, France
• 2: 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]
• 3: ByteCode Engineering Library. http://www.sourceforge.net/projects/bcel
• 4: Robert DeLine , Manuel Fähndrich, Enforcing high-level protocols in low-level software, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.59-69, June 2001, Snowbird, Utah, United States
• 5: D. L. Detlefs, R. M. Leino, G. Nelson, J. B. Saxe. Extended Static Checking. SRC Research Reports SRC-159, Compaq SRC, December 1998.
• 6: 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 System Design and Implementation, October 2000.
• 7: Dawson Engler , David Yu Chen , Seth Hallem , Andy Chou , Benjamin Chelf, Bugs as deviant behavior: a general approach to inferring errors in systems code, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 8: 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]
• 9: European Space Agency. Arianne-5 flight 501 Inquiry Board Report. http://ravel.esrin.esa.it/docs/esa-x-1819eng.pdf
• 10: R. Hastings and R. Joyce. Purify: Fast Detection of Memory Leaks and Access Errors. In Proceedings of the Winter Usenix Conf. pp. 125-136, January 1992.
• 11: Joeq. http://www.sourceforge.net/projects/joeq
• 12: N. G. Leveson , C. S. Turner, An Investigation of the Therac-25 Accidents, Computer, v.26 n.7, p.18-41, July 1993 [doi>10.1109/MC.1993.274940]
• 13: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 14: Mailmanage: http://www.sourceforge.net/projects/mailmanage
• 15: J. Nimmer and M. D. Ernst. Static Verification of Dynamically Detected Program Invariants: Integrating Daikon and ESC/Java. In Proceedings of RV-01, The First Workshop on Runtime Verification, July 2001.
• 16: Robert O'Callahan , Daniel Jackson, Lackwit: a program understanding tool based on type inference, Proceedings of the 19th international conference on Software engineering, p.338-348, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253351]
• 17: Thomas Reps , Thomas Ball , Manuvir Das , James Larus, The use of program profiling for software maintenance with applications to the year 2000 problem, Proceedings of the 6th European conference held jointly with the 5th ACM SIGSOFT international symposium on Foundations of software engineering, p.432-449, September 22-25, 1997, Zurich, Switzerland
• 18: 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]
• 19: Marc Tremblay , Jeffrey Chan , Shailender Chaudhry , Andrew W. Conigliaro , Shing Sheung Tse, The MAJC Architecture: A Synthesis of Parallelism and Scalability, IEEE Micro, v.20 n.6, p.12-25, November 2000 [doi>10.1109/40.888700]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing); Distributed debugging

General Terms:
Algorithms, Design, Performance