Fault localization through execution traces

The process used by humans when debugging is known to be effective but inefficient. The research we report on in this dissertation focuses on showing how slicing, dicing and algorithmic debugging techniques used within the framework of the process improves it by reducing the workload of the debugger. In particular we developed methods for automating the following three steps of the process: (1) Finding an initial estimate to the program fault-area: Debuggers often begin the fault localization process by using the full program as the fault area. We present two algorithms, one based on slicing, the other on dicing, that can be used to produce a more exacting first estimate of the program fault-area. We show through data from an empirical study that the relative size of our fault area estimates can substantially reduce the number of statements that have to be examined when debugging a program. (2) Reducing the program fault-area: Once an initial program fault-area is identified, the debugger repeatedly reduces the area using statement correctness information until the program faults are recognizable. We present dicing based algorithms for fault-area reduction founded on statement correctness information and demonstrate their effectiveness through an exhaustive study of a faulty program. (3) Choosing a “next statement” to examine: Our study of fault-area reduction showed that the statements chosen for examination and the order they are examined in strongly influence the number of steps used in the fault-area reduction process. We present an algorithm that automates the process of choosing a “next statement” to examine in such a way as to maximize fault-area; To validate that debuggers benefit from using slicing while debugging, we present the results from two experiments. The first shows that slicers have a better understanding of the code after debugging. The second shows that slicing while debugging improves a debugger's ability to localize the program fault-area.