Error directed execution history analysis: an approach to automatic debugging

Execution history (EH) analysis is a major unexplored area in the development of debugging technology. In this dissertation we develop a theoretical foundation for incorporating EH analysis into the process of automatically debugging programs written in imperative, strongly typed, procedure oriented languages. This foundation includes the construction of a model for EH representation, an analysis of run time errors within the model, and the development of an approach to the use of EH analysis in automatic debugging. The model represents an execution history as a sequence of state vectors. Each vector contains both the values of program variables at a particular point in a computation and additional information that is used in the debugging process. Within this model, run time errors are classified by their effect on program termination, and characterized by their appearance within the EH. Based on this classification and characterization, techniques for detecting errors within an EH are presented. These techniques form the basis of an approach to automatic debugging in which a deterministic analysis locates errors in the execution history and, based on the results of this search, heuristic techniques perform automatic fault Localization.