Tracking Down Software Bugs Using Automatic Anomaly Detection
Sudheendra Hangal, and Monica S. Lam
In the Proceedings of the International Conference on Software Engineering, May, 2002.
[pdf] [gzipped ps] [summary]

Quick Summary
They developed an automatic bug detection tool, DIDUCE, that dynamically checks invariants in Java applications; they plan to reduce the overhead to perfrom online testing and couple this with recovery mechanisms.

Main Ideas

• They have developed an automatic bug detection tool, DIDUCE, that instruments Java byte codes to perform dynamic and automatic invariant detection and checking. No invariant entry, design, or listing required by user.
• As a debugging tool, DIDUCE can help: 1) debug programs that fail on some inputs by training DIDUCE on good inputs and monitoring invariants on inputs that result in failure, 2) debug failures in long-running programs by flagging anomalies prior to the failure, 3) debugging component based software where the component works in some systems but not in others, 3) testing programs where the correct output of some inputs is unknown by training on known input/output pairs and testing on the unknown pairs, 4) aids in program evolution by testing if program modifications affect other portions of code.
• DIDUCE associates invariants with static program points. These points are 1) program points which read from or write to objects, 2) program points which read from or write to a static variable, and 3) procedure call sites. Stack accesses are ignored because of overhead and since all Java objects are on the heap.
• Automatically tracked expressions/invariants include: 1) the value being read or written, 2) the difference between old and new values after a write, 3) the parent object. Users can extend the basic DIDUCE classes to customize their invariant tracking.
• Invariants are assigned a confidence level that is a function of the number of successful evalations. Invariants that have held true for a long time are assigned a high confidence. High confidence invariants that fail often indicate a bug.
• DIDUCE can be trained on functional code where it relaxes invariant expressions. Then it can be run on failing code/inputs to determine when invariants are violated.
• DIDUCE was implemented to test Java programs using the ByteCode Engineering Library (BCEL).
• DIDUCE was used to test four applications: a MAJC memory system simulator from Sun, an email client, the Java SSE Library, and Joeq--a java VM with a just-in-time compiler. DIDUCE helped discover the root source of bugs in all tests. It helped in rare corner cases to isolate the context of the bug. It helped discover an interface bug in Sun's IMAP server when testing the email manager application. It also helped detect programmer misunderstandings of library interfaces.
• Slow down factor due to instrumentation ranged from 6-20x. For offline testing, testing can be parallized with replication of application with smaller subsets of instumentation.
• Good related work section on other debugging tools.
• Future work...reduce the run-time overhead to enable online use of DIDUCE and couple failure dedection with recovery mechanisms. Very ROCish.