A research framework for software-fault localization tools

Once a program run exposes a bug, the programmers' first task is fault localization: identifying the portions of code they need to change to correct the bug. Help for this task takes the form of fault-localization tools, which vary from static code analyzers to debuggers. This dissertation develops a research framework for fault-localization tools that require only a set of runs, some of which fail, to produce their output.; The first part of the framework is an architecture for fault-localization tools. The architecture prescribes five phases: data collection for each run, data abstraction for each run, modeling of sets of runs to produce models of correct and failing runs, contrasting the two models, and finally mapping the difference back to source code. This architecture also describes a number of existing tools.; The second part of the framework provides an evaluation method for fault-localization tools, based on the effort an ideal user must invest to interpret a tool's results. This effort is measured as the proportion of code that lies between the report and the faulty locations on a graph representing the structure of source locations.; The dissertation presents and evaluates a number of fault-localization tools developed within this framework that are built around program profiles and collections of dynamically discovered invariants. Notable contributions include the nearest neighbor idea, where failing runs are compared with their most similar successful run, and the discrete comparison and differencing of program profiles based on permutation distances. The combination of these two contributions achieved the best results of the tools we developed, as computed by the evaluation method.; Finally, this dissertation presents and quantifies elided events, a cause for caution in the interpretation of program profile data. The problem is that the execution of a part of code may have no effect on the run's correctness. As a result, code that should be suspicious is considered safe, with adverse effects for debugging.