ABSTRACTThis paper introduces an automatic debuggingframework that relies on model–based reasoning techniquesto locate faults in programs. In particular, model–based diagnosis, together with an abstract interpretationbased conﬂict detection mechanism is used to derive diagnoses, which correspond to possible faults in pro-grams. Design information and partial speciﬁcations are applied to guide a model revision process, whichallows for automatic detection and correction of structural faults. KEYWORDS : Model–based Debugging, Diagnosis, Abstract Interpretation, Program Analysis 1 Introduction Detecting a faulty behavior within a program, locating the cause of the fault, and ﬁxing the faultby means of changing the program, continues to be a crucial and challenging task in software de-velopment. Many papers have been published so far in the domain of detecting faults in software,e.g., testing or formal veriﬁcation [CDH + 00], and locating them, e.g., program slicing [Wei84] andautomatic program debugging [Llo87]. More recently model–based diagnosis [Rei87] has been usedfor locating faults in software [CFD93, MSWW02a].This paper extends previous research in several directions: Firstly, a parameterized debuggingframework is introduced, which integrates dynamic and static properties, as well as design infor-mation of programs. The framework is based on results derived in the ﬁeld of abstract interpreta-tion [CC77], and can therefore be parameterized with different lattices and context selection strate-gies.Secondly, the one–to–one correspondence between model components and program statementsis replaced by a hierarchy of components, which provides means for more efﬁcient reasoning proce-dures, as well as more ﬂexibility when focusing on interesting parts of a program.This work is organized as follows. In Section 2, we give an introduction to model-based debug-ging. Section 3 describes mapping from source code to model components and the (approximate)computation of program effects in the style of [CC77] and [Bou93]. The next section discusses themodeling of programs and the reasoning framework. In Section 5, we provide an example whichputs together the different models and demonstrates the debugging capabilities of our approach.
A program slice consists of the parts of a program that (potentially) affect the values computed at some point of interest. Such a point of interest is referred to as a slicing criterion, and is typically specified by a location in the program in combination with a subset of the program’s variables. The task of computing program slices is called program slicing. The original definition of a program slice was presented by Weiser in 1979. Since then, various slightly different notions of program slices have been proposed, as well as a number of methods to compute them. An important distinction is that between a static and a dynamic slice. Static slices are computed without making assumptions regarding a program’s input, whereas the computation of dynamic slices relies on a specific test case. This survey presents an overview of program slicing, including the various general approaches used to compute slices, as well as the specific techniques used to address a variety of language features such as procedures, unstructured control flow, composite data types and pointers, and concurrency. Static and dynamic slicing methods for each of these features are compared and classified in terms of their accuracy and efficiency. Moreover, the possibilities for combining solutions for different features are investigated. Recent work on the use of compiler-optimization and symbolic execution techniques for obtaining more accurate slices is discussed. The paper concludes with an overview of the applications of program slicing, which include debugging, program integration, dataflow testing, and software maintenance. Abstract The state of the art in hardware design is the use of hardware description languages such as VHDL. The designs are tested by simulating them and comparing their output to that prescribed by the specification. A significant part of the design effort is spent on detecting unacceptable deviations from this specification and subsequently localizing the sources of such faults. In this paper, we describe an approach to employ model-based diagnosis for fault detection and localization in very large VHDL programs, by automatically generating the diagnosis model from the VHDL code and using observations about the program behavior to derive possible fault locations from the model. In order to achieve sufficient performance for practical applicability, we have developed a representation that provides a highly abstracted view of programs and faults, but is sufficiently detailed to yield substantial reductions in the fault localization costs when compared to the current manpower-intensive approach. The implementation in conjunction with the knowledge representation is designed with openness in mind in order to facilitate use of the highly optimized simulation tools available.  Program slicing is a general, widely-used, and accepted technique applicable to different software engineering tasks including debugging, whereas model-based diagnosis is an AI technique originally developed for finding faults in physical systems. During the last years it has been shown that model-based diagnosis can be used for software debugging. In this paper we discuss the relationship between debugging using a dependency-based model and program slicing. As a result we obtain that slices of a program in a fault situation are equivalent to conflicts in model-based debugging.