Using likely invariants for automated software fault localization

We propose an automatic diagnosis technique for isolating the root cause(s) of software failures. We use likely program invariants, automatically generated using correct inputs that are close to the fault-triggering input, to select a set of candidate program locations which are possible root causes. We then trim the set of candidate root causes using software-implemented dynamic backwards slicing, plus two new filtering heuristics: dependence filtering, and filtering via multiple failing inputs that are also close to the failing input. Experimental results on reported software bugs of three large open-source servers show that we are able to narrow down the number of candidate bug locations to between 5 and 17 program expressions, even in programs that are hundreds of thousands of lines long. Categories and Subject Descriptors D.2.5 [Software Engineering]: Testing and Debugging-Debugging aids; B.8.1 [Performance and Reliability]: Reliability, Testing, and Fault-Tolerance General Terms Algorithms, Performance, Reliability.