CAREER: Abstracting Programs for Automated Debugging

New York University, New York NY

Investigators

Abstract

Debugging is one of the most time consuming aspects of software development costing the economy billions of dollars annually. Any automation that reduces the manual effort involved in debugging can have a significant impact on software productivity. An integral part of all debugging activities is the task of fault localization. Once undesired behavior is spotted in a program, the actual defect has to be identified before a fix can be developed. Most existing fault localization techniques rely on the availability of high quality test suites, which limits their applicability. One promising alternative is techniques that statically analyze the faulty program fragment and do not rely on testing. The goal of this project is to develop practical static fault localization algorithms. If such algorithms were available, they would broaden the scope of programs to which automated debugging tools can be applied and enable the creation of novel tools that have the potential to change the way in which software is developed and maintained. The main research hypothesis of this project is that practical static fault localization algorithms can be realized. To validate this hypothesis the PI will explore abstractions that conservatively over-approximate the behavior of faulty programs. The precision of these abstractions must be targeted so that the error-relevant portions of the program are preserved and the defect is precisely identified. The hypothesis that the construction of such targeted abstractions can be automated is supported by the observation that there exists a connection between fault localization and formal verification. The proposed work will explore new techniques and algorithms that leverage this connection. These algorithms will be implemented and evaluated in a static fault localization tool that will serve as a vehicle for studying advanced automated debugging techniques.