Towards a General Automated Debugging Framework

Automatic Fault Localization by Filtering Likely Invariants An important step in repairing software failures discovered during testing or production runs is to diagnose the root cause(s) of the failure. Our work addresses automatic fault localization (i.e., identification of the program statements which are true root cause of a software failure) directly and extracts information useful in understanding why the root cause led to the failure. This work is based on three key ideas. First, likely program invariants can summarize program state in a compact way that can be compared efficiently between failing and successful runs, i.e., we can use likely invariants as a way to make delta debugging efficient. We select the program statements where likely invariants are violated during the failing run as an initial set of candidate root causes. Second, unlike previous work using invariants (for many different purposes), we create likely range invariants using automatically generated correct inputs that are close to the fault-triggering input to increase the likelihood of identifying the true root cause. Third, we reduce the number of false positives using some novel filtering techniques: dynamic backwards slicing, dependence filtering heuristic which removes an invariant from the candidate set if it is dependent on a previous failed invariant without any intervening passing invariant and finally filtering via multiple failing inputs that are also close to the failing input.

Experimental results on reported software bugs in three widely-used large open-source applications Squid, Apache, and MySQL 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. Using manual inspection, we can quickly eliminate many of the remaining candidates because they are likely to violate invariants for incidental reasons (e.g., time-related functions, random-number generators, or input parsing etc.); remarkably, only 2-4 candidate locations remain after this manual filtering step without eliminating the true root cause.

In a real tool, we can extract more information from the existing analyses like value of statements with failed invariants, control flow differences, passing and failing inputs to help programmers understand the root cause of the bug. In future, we plan to use concolic execution to develop a framework to construct good inputs fully automatically in an application-independent way and eliminate most false positives in a more robust and systematic manner.

Speaker Details

Swarup Kumar Sahoo is a Post-Doctoral Research Associate at the University of Illinois at Urbana-Champaign. He completed his undergraduate degree in Computer Science at NIT, Trichy, India. He worked as a System Design Engineer in Texas Instruments before completing M.S. in Computer Science at the Ohio State University. He did his PhD at the University of Illinois at Urbana-Champaign under Dr. Vikram Adve. He was a recipient of the University Fellowship at OSU and the Richard T Cheng Fellowship at UIUC. His research interests lie in the areas of compilers, programming languages, computer architecture, parallel computing, software and hardware reliability. The focus of his current research work is on developing automated software debugging techniques.