Developing automated techniques for identifying a fault candidate set (i.e., subset of executed statements that contains the faulty code responsible for the failure during a program run), can greatly reduce the effort of debugging. Over 15 years ago precise dynamic slicing was proposed to identify a fault candidate set as consisting of all executed statements that influence the computation of an incorrect value through a chain of data and/or control dependences. However, the challenge of making precise dynamic slicing practical has not been addressed. This dissertation addresses this challenge and makes precise dynamic slicing useful for debugging realistic applications. First, the cost of computing precise dynamic slices is greatly reduced. Second, innovative ways of using precise dynamic slicing are identified to produce small failure candidate sets. The key cause of high space and time cost of precise dynamic slicing is the very large size of dynamic dependence graphs that are constructed and traversed for computing dynamic slices. By developing a novel series of optimizations the size of the dynamic dependence graph is greatly reduced leading to a compact representation that can be rapidly traversed. Average space needed is reduced from 2 Gigabytes to 94 Megabytes for dynamic dependence graphs corresponding to executions with average lengths of 130 Million instructions. The precise dynamic slicing time is reduced from up to 20 minutes for a demand-driven algorithm to 16 seconds. A compression algorithm is developed to further reduce dependence graph sizes. The resulting representation achieves the space efficiency such that the dynamic execution history of executing a couple of billion instructions can be held in a Gigabyte of memory. To further scale precise dynamic slicing to longer program runs, a novel approach is proposed that uses checkpointing/logging to enable collection of dynamic history of only the relevant window of execution. Classical backward dynamic slicing can often produce fault candidate sets that contain thousands of statements making the task of identifying faulty code very time consuming for the programmer. Novel techniques are proposed to improve effectiveness of dynamic slicing for fault location. The merit of these techniques lies in identifying multiple forms of dynamic slices in a failed run and then intersecting them to produce smaller fault candidate sets. Using these techniques, the fault candidate set size corresponding to the backward dynamic slice is reduced by nearly a factor of 3. A fine-grained statistical pruning technique based on value profiles is also developed and this technique reduces the sizes of backward dynamic slices by a factor of 2.5. In conclusion, this dissertation greatly reduces the cost of precise dynamic slicing and presents techniques to improve its effectiveness for fault location.

Reverse execution can be defined as a method which recovers the states that a program attains during its execution. Therefore, reverse execution eliminates the need for repetitive program restarts every time a bug location is missed. This potentially shortens debug time considerably. This thesis presents a new approach which, for the first time ever (to the best of the author's knowledge), achieves reverse execution at the assembly instruction level on general purpose processors via execution of a reverse program. A reverse program almost always regenerates destroyed states rather than restoring them from a record. Furthermore, a reverse program provides assembly instruction by assembly instruction execution in the backward direction. This significantly reduces state saving and thus decreases the associated memory and time costs of reverse execution support. Furthermore, this thesis presents a new dynamic slicing algorithm that is built on top of assembly instruction level reverse execution. Dynamic slicing is a technique which isolates the code parts that influence an erroneous variable at a program point. The algorithm presented in this thesis achieves dynamic slicing via execution of a reduced reverse program. A reduced reverse program is obtained from a full reverse program by omitting the instructions that recover states irrelevant to the dynamic slice under consideration. This provides a reverse execution capability along a designated dynamic slice only. The use of a reduced reverse program for dynamic slicing removes the need for runtime execution trajectories. The methodology of this thesis has been implemented on a PowerPC processor with a custom made debugger. As compared to previous work, all of which heavily use state saving techniques, the experimental results show up to 2206X reduction in runtime memory usage, up to 403X reduction in forward execution time overhead and up to 2.32X reduction in forward execution time for the tested benchmarks. Measurements on the selected benchmarks also indicate that the dynamic slicing method presented in this thesis can achieve up to six orders of magnitude (1,928,500X) speedups in reverse execution along the dynamic slice as compared to full-scale reverse execution.