Towards a General Automated Debugging Framework

Опубликовано 27 июля 2016, 1:19

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.