Model-Based Diagnosis Meets Error Diagnosis in Logic Programs

1 Introduction

Program debugging is one of the most critical activi­ ties in software development and many efforts have been made in order to build tools that support such a task (see e.g. [Sommerville, 1989]). In particular, a lot of atten­ tion has been paid in the logic programming community to the design of automatic declarative error diagnosers (after Shapiro's seminal work [1983]) . Such diagnosers are declarative in the sense that they do not need any understanding of the computational behavior of the pro­ gram but they need to know only the intended interpre­ tation of the program (the set of answers that the pro­ gram should compute). Information on such an intended behavior is obtained querying an oracle, usually corre­ sponding to the user . Several procedures for diagnos­ ing logic programs have been developed [Shapiro, 1983; Lloyd, 1987; Naish, 1992], dealing with two types of bugs: wrong answers, i.e. undesired consequences that are derived by the program, and missing answers, i.e. desired consequences that are not derived . Moreover , search strategies are adopted in order to minimize the number of queries to the oracle .

·This work has been partially supported on the Italian part by MURST 40% and on the Austrian part by the Aus­ trian Industries.

Daniele Theseider Dupre

Dipartimento di Informatica Universita di Torino Corso Svizzera 185 I-10149 T1)rino, Italy

Model-Based Diagn<,sis (MBD) concentrates on the problem of isolating faults of physical systems, starting from a model of the structure (components and their connections) and function (or behavior) of the system and a set of observations indicating an abnormal be­ havior [Hamscher et al., 1992] . In particular, a sys­ tem is faulty if the observed behavior of the system contradicts the behavior predicted by assuming that all of its components are correct . Making assump­ tions about faulty components of the modeled system allows explaining the deviation of the observed behav­ ior from the predicted one; thus the faulty compo­ nents can be isolated (see figure 1). Moreover , one of the goals of MBD is to select the observation that best discriminates among a set of competing leading diagnoses (using information-theoretic concepts) . For­ mal characterizations of the diagnostic task have been proposed, namely the consistency-based [de Kleer and Williams, 1987; Reiter, 1987; Friedrich and Nejdl, 1990; de Kleer et al. , 1992] and the abductive one [Poole, 1989; Console et al., 1989; Console and Torasso, 1991].

The goal of this paper is to use MBD techniques to diagnose logic programs (and suggest corrections). Such a use of MBD will cause conceptual shifts with respect to both traditional MBD and declarative error diagno­ sis. With respect to the former, the main problem is to identify what plays the roles of the model and the obser­ vations . At a first glance, it would be intuitive that the specification of the program plays the role of the model of the system while the program to be debugged plays the role of the actual system, i.e. it provides observations. However, since we do not want to restrict our approach by the assumption of having a formal, complete speci­ fication for the procedures in the program (this is not realistic since providing it could be at least as difficult as writing the correct program), we cannot use specifications as models. Thus, in our approach the program to be diagnosed (whose structure and behavior is known in detail) is technically used in the same way as the model is used in MBD; the clauses of the program are regarded as components which may be correct or abnormal. In con­ trast, the role of the observations is technically played by the information available on the user's model of the intended behavior of the program.

Given a set of assertions about the intended behav­ ior of the program (a set of expected answers and a set of undesired ones), the goal is to determine the bugs by comparing the actual program behavior with such assertions. In the same way as a system is faulty when assuming that all its components are correct is in contra­ diction with the observed behavior, a program is faulty when assuming that all its clauses are correct is in con­ tradiction with the assertions on the intended behavior. The goal is to remove such a discrepancy, isolating a set of clauses which are not correct and must be fixed. In particular, this amounts to determining a set of clauses to be removed and, possibly, a set of clauses to be added such that the resulting modified program is in accor­ dance with the assertions (see figure 2) 1 .

Given a partial specification of the intended behavior, our approach characterizes the alternative ways of modi­ fying the program in order to match such a specification . This is a conceptual shift with respect to declarative de­ bugging whose aim is at querying the user until a fault (one at a time) is isolated.

The approach we present has some advantages with re­ spect to other error diagnosers. We look at the program and at all the 'observations' globally and thus we are able to characterize the whole set of diagnoses (possibly in­ volving multiple faults), ranking them according to some preference criteria, rather than looking at one execution tree for one wrong or missing clause instance at a time. This allows us to devise an algorithm for computing the diagnoses in increasing order of preference. Moreover, the use of MBD techniques can provide a more focused interaction with the user . For example, if one diagnosis is much more likely than all the others, we simply output it without asking new information. More generally, we can include in our approach techniques similar to those used in MBD to ask information that can discriminate as much as possible among competing leading diagnoses rather than asking information about the predicates in the considered AND-OR execution tree.

Section 2 presents a motivating example; section 3 pro­ vides definitions of diagnoses and preference orderings among them; section 4 presents an algorithm for com­ puting diagnoses; section 5 introduces a further example; section 6 compares our approach to related ones.

1 This is something more than traditional MBD, involving also some form of repair [Friedrich et al., 1992).

2 Motivating Example

The following example motivates the use of MBD tech­ niques for localizing errors in logic programs.

Example 1 Consider the following program (constants, functions and predicates are in lower case, variables are in upper case and are universally quantified) :

Assume that the user queries q1(X), r1(X), s1(X) and the program returns X = 0 as the only answer. In contrast, the intended behavior of the program is the following: neither q1(0) nor r 1(0) nor s1(0) should be entailed by the program, while q1(1), r1(1), s1(1) should be a valid answer to the query (and it is not returned even on backtracking). In this case all the declarative diagnosers mentioned in the introduction (in particular, Shapiro's one which aims at minimizing the number of queries to the 11ser needed to isolate a fault) would query the user about the validity of at least 0( log( n)) facts.

The approach based on MBD we will describe does not need to query the user at all in order to identify the most likely diagnosis. In fact, one possibility is that the clause p(O) is faulty (and should be replaced by p(l)); this corresponds to a single fault in MBD. Of course, there are other possible solutions which do not include p(O) but any of them has to involve at least three clauses (e.g. c1, Cn+1, c2n+d, i.e. it corresponds to a triple fault. Thus we can conclude immediately that p(O) is the most likely diagnosis, i.e. only this clause has to be fixed . We succeed in doing so because we look at the whole space of solutions rather than considering one execution tree and trying to isolate one fault at a time.

3 Definitions

In this section we provide the definitions for error diag­ nosis in logic programs.

Definition 1 (Error diagnosis problem) An error diagnosis problem is a triple (P, s+, s-) where:

• P is a definite logic program;
• s+ and s- are sets of queries, where variables in s+ are intended as universally quantified and vari­ ables in s- are intended as existentially quantified.

The program P has an intended interpretation I (a Herbrand model); s+ and s- can be seen as approxi­ mations of I. In most practical cases, in fact, we cannot assume to have a complete specification available, since providing it would not be realistic 2 . In particular, in our specification s+ (s-) is a set of queries that are true (false) in the intended interpretation . In other words, s+ (S-) can be seen as a set of positive (negative) ex­ amples about the intended behavior of P. Depending on the power of the available deduction system, p' s+ and s- can be made more expressive.

In the declarative diagnosis literature, a distinction between wrong and missing answers is made . In our framework, a wrong answer corresponds to a member of s- which is entailed by the program, while a missing answer corresponds to a member of s+ which is not en­ tailed. Notice that s+ may also contain correct answers (formulae that are true in the intended interpretation and are indeed entailed by the program) while s- can contain formulae that are false in the intended interpre­ tation and are not entailed by the program.

In example 1' p is the set of clauses {Co' ... ' CJn}' s+ is {qt(1), rt(1), St(1)} and s- is {qt(O) , rt(O), St(O)} .

Solving an error diagnosis problem corresponds to identifying a set of clauses to be removed and a set of clauses to be added in order to restore consistency with respect to s- and to derive all the desired answers in s+. Changing a clause can be seen as removing and adding. Note that s- and s+ correspond to consistency and provability constraints in deductive databases .

Definition 2 (Diagnosis) A pair (C, E) of sets of clauses, where C ~ P, is a diagnosis if and only if:

• (P \C) u E f= a for all a E s+
• (P \C) U E It a for all a E s-

The set C of clauses to be removed is the "core" of a diagnosis, while the choice of E, given a C, is highly un­ derconstrained. However, the following property holds.

Property 1 Given an error diagnosis problem and a set C of clauses, then the following are equivalent:

1. There exists an E such that (C, E) is a diagnosis; 2. (C, s+) is a diagnosis .

We could thus be satisfied with providing as solution a set C of clauses such that (C, s+) is a diagnosis (accord­ ing to definition 2). On the other hand, we believe that it can be important to provide as a solution an E which is more informative for the user, giving a hint on how the program could be corrected. Notice that this is more than diagnosis, in the sense that it provides also a rough form of repair. However, in order to do this in a con­ strained way, it would be important to have a canonical syntactic form in which E has to be expressed (we shall return to that later) . It is important to stress that we do not aim at synthesizing the correct program but only at checking whether it is possible to change the program to entails+ and at giving some constraints on how the pro­ gram could be changed . Our goal is thus very different from those of automatic program synthesis and, specifi­ cally, from "inductive logic programming" (originated in [Shapiro, 1983] and developed e.g. in [Muggleton, 1991; Quinlan, 1991]) .

2 The declarative diagnosers mentioned in the introduction also assume that there is such an intended interpretation, but they do not assume it is specified in advance (information about it can be asked to an oracle when needed).

In practice, it can be useful to introduce some prefer­ ence criteria among alternative solutions. Several crite­ ria are possible. A reasonable one is based on the number of clauses to be removed or added, which corresponds to the number of faulty components in MBD if we assume that all components have the same probability of failing (and failing is less probable than being correct).

Definition 3 (Ordering among diagnoses) (C, E) < (C',E') iff ICI < IC'I or nGI = IC'I .and the num­ ber of predicates in the heads of clauses in E is less than the number of predicates in the heads of clauses in E' ) .

Definition 4 (Preferred diagnosis) A diagnosis is preferred iff it is minimal with respect to <.

Intuitively, we want to remove as few clauses as pos­ sible and add clauses for as less predicates as possible.

Another possible ordering could be based on preferring diagnoses where the sum of the number of clauses to be removed and the number of predicates for which clauses are added is minimum.

In the ordering defined above, for a given C and a given set of predicates , there can be several Es defining these predicates such that the diagnoses given by C and each one of such Es are preferred diagnoses.

In order not to distinguish among such solutions, we would like to have a compact way to represent all of them. This could be done limiting E to clauses in the language of P and s+ (this means that we do not "in­ vent" auxiliary predicates) and of the form:

such that they give the strongest definition of Pi which is consistent with s- (i.e. the exceptions are minimized) . We shall call these clauses "exception clauses" and we shall say that each aj is an "exception" for p; . This is the canonical form advocated above for providing "repair" information to the user . In fact, clauses in this form provide the user with a constraint on how the actual definition of Pi should be: the clause for p; provides an upper bound for the extension of Pi which is consistent with the program and the 'observations'.

Diagnoses where E is a set of exception clauses will be denoted as diagnoses in exception form. It is worth noting that limiting to such a syntactic form is not restrictive, since the following property holds:

Property 2 For a fixed C, if there is a definite progmm E in a language L such that (C, E) is a diagnosis, then for some set E' of exception clauses in the same language L, (C, E') is a diagnosis.

In practice, diagnoses in exception form can be built just in case the exceptions for each one of the predicates in E' can be expressed in a finite way (we shall return to that in section 4) .

Example 1 (contd.). We have that

is the only preferred diagnosis in exception form. The next diagnoses in the order which are not supersets of the previous one are

The use of the exception form allows us to provide an upper bound for the extension of the predicates for which a new definition is added to the program. It could be interesting to provide also a lower bound for such an extension . This corresponds to specifying what is strictly needed in order to entail s+ . Providing both the upper and lower bound can help the user in fixing the program. In the example above, the lower bound for the definition ofp for the preferred diagnosis is p(1). In fact, when c0 is removed, a definition for p must be added in order to entail s+. In order to do so consistently with s-, such a definition must at least entail p(1) and at most any instance of pother than p(O).

4 Computing Diagnoses

In this section we first outline a non-deterministic , gen­ eral algorithm for computing the diagnoses in exception form (on backtracking on the non-deterministic choices). We also discuss how such an algorithm should be mod­ ified in order to provide both upper and lower bounds for the extension of the predicates for which new defini­ tions are added. Finally, we briefly discuss how such an algorithm should be modified in order to generate the solutions in increasing order of preference.

Let us first introduce a couple of definitions.

Definition 5 (Most General Exception Clause) Given a predicate panda setH of atoms, the Most Gen­ eral Exception Clause (MGEC) for p consistent with H is the clause:

where X is a tuple of new variables. In case there is no p(t) E H , the MGEC for p is the clause p(X).

Definition 6 (Universal Abductive Explanation) Given a background theory T and a set A of assumable predicates, a Universal Abductive Explanation of a set S of formulae is a set E of formulae of the form VXp(X), where pEA, such that T U E I= S .

The algorithm is as follows :

Input: P, s+, s-.

Output: A diagnosis (C, E).

Procedure:

1. Find a set C' of clauses in P such that (P \ C') U s+ ~ a for all a E s- . This can be done using the traditional techniques of consistency-based diag­ nosis [Reiter, 1987], that is, generating "conflicts", which in our case are sets of clauses in P used to derive some element of s- from PuS+; then, com­ puting a hitting set C' of such conflicts, i.e. a set of clauses that contains at least an element from each conflict and then cuts every derivation of an element

a E s- . The reason why we use also s+ to gener­ ate conflicts is a way of generating only those C's for which s+ can be consistently added, i.e. given property 1, those for which an E exists. This means that the algorithm can be stopped after this step, if one is not interested in determining E .

1. Determine, given C', an E which allows the entail­ ment of the elements in s+. This can be done as follows.

Compute a universal abductive explanation E' of s+ using P \ C' as a background theory and all the predicates as assumable; we generate universal ex­ planations because we want to generate E in excep­ tion form. Now the exceptions have to be generated to avoid that some element of s- follows from the modified program. In order to do that, compute the set of conflicts:

D = { {A1, ... , Am} such that there exists a deriva­ tion of some p E s- from (P \ C') U E' and { A1 , ... , Am} is the set of the heads of the instances of the clauses used in the derivation }

Choose a hitting set H of D, removing subsumed atoms. Let p1, . . . , Pn be the predicates occurring in some element of H . H characterizes a possible set of exceptions to be imposed on the predicates P1, ... , Pn in order not to entail elements of s- .

For each p;, let C; be the set of clauses in (P\C')uE' defining p;, and let e; be the M G EC of Pi consistent with H . In order to modify the program, we have to add e1, . .. , en and to remove the existing clauses C" = C1 u ... u Cn for Pl, ... ,Pn · However, we have to check that the program modified in this way actually entails s+. If

In the output we take the intersection between C" and P in order to list only clauses that were in the original program.

In case we want to associate with each of the diagnoses computed with the above algorithm also a lower bound on the extension of the predicates for which new defi­ nitions are added, we proceed as follows. In step 2 we compute both an abductive explanation E" of s+ and the corresponding universal abductive explanation E'; as regards the latter we perform the steps discussed above; as regards the former, we consider the set D" of conflicts produced by E" and we choose a hitting set H" of D"; for each predicate p:' occurring in H", instead of remov­ ing the existing definitions adding the most general ex­ tension, we simply add the exceptions mentioned by H" to the body of each existing clause for r:'; this requires that the clauses are first put in "general form" [Clark, 1978], i.e. in a form such that the clause r(I) +-- £1, . . . Ln is transformed into r(X) +--X =I, £ 1, . .. Ln where X is a tuple of distinct variables not occurring in the clause. Example 1 ( contd. ). Let us now show how the algo­ rithm described above computes some of the diagnoses. The conflicts in step 1 are the following:

A hitting set is {co} (there are of course several other hitting sets). A universal abductive explanation that can be computed in step 2 is p(X). In this case we have

A hitting set of Dis H1 = {p(O)}. From it we generate the following M G EC for p:

This gives the preferred diagnosis reported in section 3. In order to compute the lower bound for the definition of p, we can consider the abductive explanation p( 1) from which we generate no conflict, thus getting p(1) as the clause to be added.

Other hitting sets of Dare {q;(O), rj(O), sk(O)} for any 1 ~ i, j, k ~ n . Each of them provides one of the other solutions mentioned in section 3.

It should be clear that the algorithm is correct accord­ ing to definition 2: the solution is built in such a way that it is consistent with s- and the algorithm explic­ itly checks that s+ is entailed by the modified program. Moreover, the algorithm can generate all the diagnoses in exception form, provided that there are no infinite ex­ ecution trees for the goals in s+ and s-. In fact, in the first step we can generate (using techniques like those in [Reiter , 1987; Greiner et al., 1989]) all sets of clauses that, if removed, restore consistency, while in the second step we can consider all abductive explanations; remov­ ing the candidates that do not entail s+ at the end of step 2 does not lead to loosing any solution, since in step 2 we consider not only minimal abductive explanations and thus, if we exclude one candidate E' because it does not lead to covering s+ and there is some superset of E' which leads to covering s+, we consider also such a redundant explanation and the solutions it generates .

An implementation of the algorithm should be able to generate the diagnoses in the order of the preference relation (without necessarily generating all of them). In case we limit the algorithm to step 1 (producing a C for which an E exists), this can be done easily: in step 1 we generate hitting sets in order of increasing cardi­ nality. Considering also step 2 is more complex since the explanation E' may lead to removing further clauses and thus C and E cannot be minimized independently. Given a preferred candidate C~ from step 1 (a candidate removing less clauses than the others), in step 2 we gen­ erate explanations in the order of increasing cardinality of the set of predicates involved and we build the solu­ tions . Each E' may lead to removing further clauses, so before outputting a solution, we have to guarantee that we cannot generate better ones by using some other set c~ removing more clauses than c~ but such that, after the second step, leads to removing less clauses. In par­ ticular, we have to wait until we consider candidates C: that, in the first step, lead to removing more clauses than the final solution generated from C~. Similar problems arise with both orderings discussed in section 3.

It is worth noting that MBD techniques to generate preferred diagnoses in an efficient way (e.g. [de Kleer,

1991]) can be transferred to the above algorithm (this , however, is outside the scope of this paper).

5 A further example

In this section we briefly discuss an example showing further advantages of our approach, namely the fact that we can isolate all bugs at once. ·

Example 2 Consider the following diagnosis problem:

In the first step of our algorithm we determine two minimal sets of clauses that, if removed, restore consis­ tency: Cf = {cl} and q ={co} (notice that these two candidates can be discriminated by asking whether p(1) is in the intended interpretation). By considering step 2, the first diagnoses that we generate which are not su­ persets of previous ones are the following:

Suppose that the definition of s+ and s- arises from the following interaction with the user: first he/she runs the query r(X) (or r(1)) and labels as correct the answer X = 1 (or yes); then he/she runs the query q(X) (or q(1)) and labels as incorrect the answer X= 1 (or yes) .

In the diagnosers in [Shapiro, 1983; Lloyd, 1987; Naish, 1992] this would correspond to searching a bug in the computation tree of q(1). This will cause asking to the oracle whether p( 1) is in the intended interpreta­ tion . If we assume that the answer is "no", co is output as the wrong clause instance. The fact that r(l) must be derived from the program is not considered; it would be necessary to re-run previous successful queries after the program has been modified, in order to check whether they are still correctly answered, and, if this is not true, re-run the diagnoser. On the other hand, we consider all 'observations' at once and thus a diagnosis directly takes into account all of them and isolates all bugs at once.

6 Comparison with related work

It is interesting to compare our approach with the declarative diagnosers in the literature [Shapiro, 1983; Lloyd, 1987; Naish, 1992] . First of all, it is important to consider that the goals we are pursuing are different . We are interested in characterizing the diagnosis space and in designing a procedure which can compute the lead­ ing diagnoses according to some preference order. Each diagnosis may include multiple faults and explains all the misbehaviors of the program. On the other hand, most of the research on declarative diagnosis concen­ trated on defining procedures for determining one bug at a time using an oracle for asking information about the intended behavior of the program at hand. In our terminology, such diagnosers look at one conflict (for a wrong answer) or one explanation (for a missing answer) at a time, trying to isolate .one fault from such a conflict

(or explanation); then repeat the same process again on another wrong or missing answer. Moreover, they as­ sume that the oracle is able to answer any question on the considered execution tree.

However, it is interesting to show how the solution(s) they compute are included in the space characterized by definition 2. We shall analyze this point informally, using as references the characterizations provided in [Naish, 1992], where two different types of bugs are considered (as in most declarative diagnosers):

• Incorrect clause instances, defined by the following Prolog clause:

("valid" and "unsatisfiable" are calls to an oracle; an atom is valid if it is in the intended interpreta­ tion, it is unsatisfiable if it is not in the intended interpretation).

• Uncovered atoms, defined by the following Prolog clause:

where "all" can be read as a universal quantifier . A is uncovered if it is valid but there is no clause in the program with a valid body that implies A .

In the practical versions of the diagnosers, such types of bugs are considered only if they actually lead to a wrong or missing answer. In our approach we consider globally all the pieces of information in s+ and s­ (which can include wrong and missing answers as well as correct answers and incorrect answers not computed by the program) . Given a clause c; having an incorrect instance, if c; is actually used to derive a wrong answer (and thus is recognized as a bug by the practical versions of the diagnosers after a number of queries to the oracle), it is clear that c; belongs to the first component of some diagnosis according to our definition (since removing c; - and, possibly, other clauses - is a way of removing the inconsistency). Moreover, given an uncovered atom, if it actually leads to some missing answer (i.e. the atom is such that if it were derivable, some missing answer would not be missing), then in our definition a clause implying such an atom will be part of the second component of some diagnosis.

7 Conclusions

Software is tremendously more erroneous than hardware and thus enhancing software diagnosis is very important. This paper proposes the use of MBD in such a task (in particular, error diagnosis in logic programs) and con­ centrates on the core of the diagnostic process, defining the concept of model-based diagnosis of logic programs and an algorithm for computing diagnoses. Other tech­ niques developed in the MBD community can be trans­ ferred to software diagnosis; for example: use of fault probabilities based on metrics or user models, informa­ tion theoretic techniques for observation selection, fo­ cusing techniques to improve the algorithm, hierarchical decomposition as well as the integration of diagnosis and repair.