IMP Program Diagnosis Based On Operator Component Matrix Model

Model-based diagnosis is a diagnostic method based on logic consistency, which is first proposed in 1987 by Reiter. It was mostly applied in the diagnosis of the systems composed of physical components in early time. Applying Model-based diagnostic techniques in program diagnosis is still a new topic. Because of the complexity and diversity of program's logic model, program diagnosis seems much more difficult than those physical systems. Model-based program diagnosis is different from traditional program debugging technology, the former uses more information about program model and is less dependent on manual intervention, and can also find more hidden logical errors. So it is better than traditional testing methods in guaranteeing the correctness of programs.The core issue in model-based diagnostic methods is the construction of a suitable model, and program diagnosis also has the same issue. At present, the program models for diagnosis purpose mainly include dependency model and value-based model, both models are aimed at computing program slices, with the former at static program slices and the latter at dynamic slices. Both models are represented as the form of a directional graph. However, if a program has a complex structure (for example, multi-branch and multi-cycle), the graph will be very messy, and need use supergraph to represent it. Moreover, the model reflects only part of the characteristics of the program (such as dependency and valuation trajectory), and results in too much candidate diagnoses.This paper presents a new program modeling technique, i.e., operator component matrix model. The model use a simple imperative programming language -IMP as a backdrop. Chapter 2 of this paper gives the IMP language syntax and semantics.Chapter 3 presents a formal definition of operator component and its operation rules, and two special operator components, 1-operator -component and 0-operator-component are discussed of their properties, and introduces the concept of constant-variable in order to represent any expression with a form of operator components. Taking IMP language as the background, the chapter gives the operator component matrix form of the IMP program. In the operator component matrix model (OCM model) of an IMP program, each of the sentences corresponds to an operator matrix, and the entire program could be translated into the product form of a number of operator component matrixes. The model reveals the constant migration process of the state space of a program.Chapter 4 discusses the dependencies of IMP program under its OCM model. By introducing characteristic operator component and the establishing of characteristic OCM, we can easily calculate the value dependencies of the final variables (occurrences) on initial variables (occurences), that is the black-box dependencies; By introducing formal operator component, from the formal OCM , the dependencies of the output variables on program statements can be easily obtained, named as white-box dependencies. Meanwhile the white-box dependency of one variable is also its corresponding program slice. This is a new technology of program slicing with using algebraic method.Chapter 5 illustrates the program diagnosis method based on OCM model. It gives the formal description of the program diagnosis problem under isomorphism assumption, where adopting specifications to represent the expected program, and presents the concept of program diagnosis and some theorems for computing the conflict sets. An example is given to illustrate the process of applying this program diagnosis method. Moreover, the chapter presents sectional and hierarchical diagnosis techniques to accelerate and refine the diagnosis. Finally, it compares the model with two traditional models (dependency model and value-based model).Because only using dependencies knowledge to comptute diagnoses generally results in a lot of candidate diagnoses, further diagnosis identification is necessary. Chapter 6 presents a new diagnosis identification method by performing value domain analysis without adding additional observation points. In fact, this method can get rid of some non-abductive diagnoses, that is, the real outputs can not be logically derived from those diagnoses. So value domain analysis is actually a process of abduction.Chapter 7 expands IMP syntax to IMP-A by adding array type, and gives the method of computing the white-box dependency of array subscript variables. This expansion makes OCM model have more representative capacity on actual programs.The final chapter raises a new method for automatic correction of program errors by genetic programming. Under G?del program coding idea, we use a G?del binary tree to represent a program and acquire its chromosome code. The use of genetic programming, can convert a wrong program to a correct program by genetic evolution, and can be considered as a self-correcting process.Of course, our research work is not enough much, it needs further enrich and improve. However, we believe the new program modeling method has a strong vitality and can adapt more complicated properties of a program in future, to make the diagnosed program closer to the actual program.