Debugging Functional Programs

1 Introduction

Although model-based diagnosis (MBD) [Reiter, 1987; de Kleer and Williams, 1987] provides a general diagnosis framework, most of its applications are within the hardware domain or use models of the physical world. However, sev­ eral attempts have been made to extend the application of diagnosis methods to software debugging. A model for di­ agnosing logic programs was introduced in [Console et al., 1993] and further studied in [Bond, 1994; 1996]; qualitative models of recursive functions wer studied in [Missier et al., 1994]. In [Friedrich et al., 1996], the model-based diagnosis of circuit designs written in the VHDL hardware specifica­ tion language used an abstract model that allows diagnosing very large programs. A graph-based model for diagnosing a functional language, EXP was presented in [Stumptner and Wotawa, 1996].

All these approaches have in common that they use only a model which can be directly derived from the given program and the used programming language. No additional formal specification must be available, so that the diagnosis system can be directly integrated into a traditional software develop­ ment process. In this paper, we describe the underlying con­ cepts of replacement-based software diagnosis by defining a concise logic-based model for a variant of EXP. The model can be adapted to other functional , or sequential assignment languages, and has the advantage of being executable over the definition of [Stumptner and Wotawa, 1996]. We keep the ability to introduce models for expression replacements that explain a faulty behavior, and discuss the application of mul­ tiple test cases, which can reduce the number of diagnoses by excluding certain replacements - a phenomenon that is dual to the concept of physical impossibility. This helps to focus on faulty program parts without using too sophisticated mod­ els. User interaction (the user as oracle) is replaced by sets of prespecified test values.

·This work was partially supported by the Austrian Science Fund (FWF) project N Z29-INF.

To begin, we briefly recapitulate the basic MBD defini­ tions (see [Reiter, 1987; Struss and Dressler, 1989; Wotawa, 1996]). A diagnosis problem consists of a system description (SD) describing the behavior of components (COMP) and their interconnections. The component behavior is associated with component modes. For every component at least the correct behavior ( ·ab mode) must be specified. Let 0 B S be a set of observations. A diagnosis for (SD, COM P, OBS) is a set of mode assignments D., associating one mode with every component, such thatSDUOBSU{m(C)Im(C) ED.} does not lead to a contradiction.

This paper is organized as follows. First, syntax and se­ mantics of the language of expressions (EXP) is given, fol­ lowed by the introduction of the associated system descrip­ tion. Afterwards, replacements and the use of multiple test cases are discussed. The final section concludes the paper and gives future research directions.

2 Modeling Programs for Diagnosis

Programs can be viewed as static and dynamic objects. The program's static part is limited by the syntax given by the used programming language, while the dynamic part is related to the semantics. Executing a program causes the evaluation of constants, variables, functions, etc. using environments (which map variables to their actual values and function iden­ tifiers to their definition or body) which can be changed dur­ ing evaluation. In this paper, we introduce a model for a simple functional programming language EXP with the fol­ lowing instruction syntax (declaration constructs omitted for brevity):

expression ::=

if expression then expression else expression end if

I ( expression )

I expression bin_op expression I June Lid ( expression_list ) I var _id I const expression_list :: = € I expression expressionJist..rest expression_list..rest :: = € I , expression expression_list..rest

It is assumed that V S contains all variable symbols, F S all built-in functions, FV all user-defined functions, and A all constants. Built-in functions (including predicates) rep­ resen~ the basic functionality of the language. They include functwns such as + or * depending on the implemented data typ~s. While constants evaluate to the same value every time, vanables evaluate to values depending on the current state of the environment that stores the values. Likewise, the bod­ ies of user-defined functions are stored in a function environ­ ment. Formally, we define a variable environment as a func­ tion t : V S f-t VALUE and a function environment as a function J : FV f-t £ XP associating expressions with func­ tion symbols. We denote the set of all variable environments by V E NV, the set of all function environments by FE NV.

In addition to the function environment we introduce the function variables which returns all variables used in the body of a user-defined function.

The semantics of EXP, given in a declarative manner, de­ scribe how EXP expressions are evaluated. We use a call-by value semantics for this paper. The semantics are given by an evaluation function r : EX p X v ENV X F ENV f-t VALUES which maps expressions (programs) together with the given environments to a set of result values.

V E V S => r(V, L, o) = t(V) c E A => rc c, L, o) = c r( (E), L, 6) = r(E, L, 6) FE FS => r(F(el, . .. , en), t, 6) = F(r(el, L, 6), . .. , r(en, L, 6)) FE FS => r(e1Fe2,t,6) = r(el,t,6)Fr(e2,t,6) r(if el then e2 else e3 end if,t,6) = ={ r(e2,L,6) ifr(el,L,O)=true r(e3, L, 6) otherwise FE FV => r(F(el , . . . , en), t, o) = r(o(F), t', o) where Vi E variables(F) : L 1 ( v;) = r(e;, L, o) and v ft. variables(F) : t'(v) = t(v) ..

We demonstrate the usage of the semantics on a small EXP example implementing the user-defined function twodimln:

{ if (X > 0) and (Y > 0) o(twodimln) = then ln(X * Y) else 0 end if

~he .variables used are variables(twodimln) = {X, Y} which IS a subset of V S. F S includes the functions (predi­ cates)'>',' and',' ln', '*'. The constant 0 is contained in A.

The following shows the initial steps of the evaluation of twodimln assuming a given t and J:

r(twodimln ( 1, 2), L, 0) [t' (x) = r(l, L, o) = 1, t' (Y) = r(2, L, 6) = 21 r(o( twodimln) , L 1 , 6) r(if (X > 0) and (Y > 0) then ln (X * Y) else 0 end if, t', o)

To ~se MBD for software debugging we must identify di­ agnosis components and build a system description. Because EXP allows building programs out of expressions, we use ex­ pressi?ns (or, put differently, nodes in the syntax tree) as di­ agnosis components. To differentiate between separate occur­ rences of textually identical expressions we introduce a func­ tion K which assigns an unique number to every expression. A system description for EXP must have the same properties as the semantics. Results obtained by the semantics must be also derivable by the system description.

The diagnosis components for twodimln example are: Co = if (X > 0) and (Y > 0) then ln(X*Y) else 0 end if, C1 = (X > 0) and (Y > 0), C2 = (X > 0), c3 = x, c4 = o, c5 = (Y > o) , c6 = Y, c1 = o, Cs = ln (X*Y) , Cg = X*Y, C10 = x, Cn = Y, C12 = 0

If we examine the data flow between the components, we find that they form a tree-structured system with Co as top component. Such a system can be diagnosed very effec­ tively [Stumptner and Wotawa, 1997]. In the next step, we define a system description EXPSD for EXP programs.

The semantics definition in [Stumptner and Wotawa, 1996] turned out to be somewhat unwieldy. The formal definitions where complex, and required another step to be mapped to a logical representation for a diagnosis system. Therefore we use a PROLOG-Iike description, which also has the advan­ tage of being executable. The evaluation is defined using a predicate eval ( Expr, VarEnv, Val, Step) where Expr denotes the expression to be evaluated, VarEnv a list of variable value pairs, Val the value returned by the eval­ uation, and Step the number of iteration steps. The vari­ able environment of our running example is expressed by [ [X, 1] , [ Y, 1] l . Note: To handle unknown values, i.e., values that cannot be derived from the description and obser­ vations, we introduce the distinguished value f .

The function environment is represented by the predi­ cates body/2 and variables/2. To evaluate a call to twodimln, the facts body ( twodimln, if (X > 0) and (Y > 0) then ln(X*Y) else 0 end if) and variables (twodimln, [X, Y]) are added to the system description.

• Constants are evaluated to themselves. eval(Expr,VarEnv, Expr, Step) :- not_ab(Expr).
• Variables are evaluated to the associated value in the cur­ rent variable environment.

eval(Expr,VarEnv,V, Step) :- not_ab(Expr), value(VarEnv,Expr,V). where value is defined as follows: value( [ [X,VliRest), X, V). value ( [) , X, €) . value( [ [Y,VliRest), X, V')

Y #X, value(Rest, X, V').

· Built-in functions

The following rule belongs to the system description for every built-in function (or predicate) used in the program

eval(F(El, ... ,En) ,VarEnv,V,Step) not_ab(F(El, . . . ,En),

(e.g.,'+', or'-'). eval(E1,VarEnv,V1,Step),

eval(En,VarEnv,Vn,Step), F(V1, ... ,Vn,V).

The behavior of the function is given by the FIn + 1 pred­ icate. As an example, for the logical and function the be­ havior could be described by:

and(true,true,true). and(false,X,false).

and(X,false,false). and(true,f,f).

and ( f, true, f) .

• Conditional expression E = if E1 then E2 else

E3 end if

eval(E,VarEnv,V,Step)

not_ab(E), eval(E1,VarEnv,true,Step),

eval(E2,VarEnv,V,Step).

eval(E,VarEnv,V,Step) :-

not_ab(E), eval(E1,VarEnv,false,Step),

eval(E3 ,VarEnv,V,Step).

eval(E,VarEnv,f,Step) :-

noLab(E), eval(E1,VarEnv,f,Step) .

• User-defined functions are evaluated by changing the en­ vironment and executing the body using it.
• Undefined Behavior

eval(F(E1, ... ,En) ,VarEnv,V,Step) body(F,B), variables(F,Vars), ~rnaxirnumSteps(Step), changeEnv(VarEnv, [E1, ... ,Enl ,Vars,VE, Step), eval(B,VE,V,Step+1). changeEnv(VarEnv, (], [],[],Step). changeEnv(VarEnv, [EIRest], [VariVRest], [ [Var, V] I ERest], Step) :­ eval(E,VarEnv,V,Step), changeEnv(VarEnv,Rest,VRest,ERest,Step). rnaxirnurnSteps(Step) :- Step>= rnaxStep.

If a component is assumed to behave incorrectly, the unde­ fined value is returned as result.

eval(E,VarEnv,E,Step) :- ab(E) .

It can be shown that this system description produces an evaluation that corresponds exactly to the semantics of EXP.

To complete the system description for model-based di­ agnosis we must introduce the concept of observations. Therefore we introduce the predicate observe/ 3 using the expression, the environment, and the expected value as arguments. An observation for our example can be observe(twodimln(l,l) ,Env,O).

In this case no environment ist specified because the func­ tion call does not make use of variables. We say that an obser­ vation contradicts the system description if the value derived from SD is not equal to the observation. This rule is added to our system description.

contradiction :- eval(E,Env,V,Step), observe(E,Env1,V1), equa1Env(Env,Env1), V # f, V1 # V.

Observations are facts and cannot contain the undefined value c The predicate equalEnv I 2 is true if both envi­ ronments contain the same elements.

With the system description EXPSD we can compute (minimal) diagnoses as described by Reiter [Reiter, 1987]. For example assume that instead of ( Y > 0 ) the program­ mer has written ( Y > 1) as subcondition. Using the test case twodimln ( 2, 1) we can compute the following six single diagnoses:

{Co} = {if (X > 0) and (Y > 1) then ln(X*Y) else 0 end if}, {C!} = {(X > 0) and (Y > 1) } , {C5} = { (Y > 1) }, {CB} = {Y}, {C7} = {1} , {C12} = {o}

Among 13 diagnosis components, the diagnosis engine has found 6 diagnosis candidates. In the rest of the paper, we discuss how to further reduce the number of suspected com­ ponents. First, by using replacements to attempt to correct a program, as described in [Stumptner and Wotawa, 1996]. The second idea is to use multiple test cases and the information related to them. Finally, we can introduce fault modes and their corresponding behavior. We can easily prove whether a condition within a conditional statement is a single bug or not by inverting the conditional statement's behavior. Unfor­ tunately, applying this fault mode has a significant drawback. If we are diagnosing a recursive function, inverting the con­ dition may lead to an infinite loop. In the example we can use this mode effectively - if the condition is be inverted, cor­ rect behavior will result. Therefore, only the diagnoses { C1}, { C5}, { C6 } and { C7} remain. We refer to the variant of EX­ PSD with the wrong condition fault mode as EXPSD+ . We assume this variant is used below whenever the function to be diagnosed is not recursive.

3 Software Debugging as Search for Replacements

As argued in [Console et al., 1993], applying model-based di­ agnosis to software debugging reduces the number of diagno­ sis candidates compared to classical program debugging tech­ niques such as [Shapiro, 1983; Fritzson and Nilsson, 1994], and this is already the case with a straightforward applica­ tion of the standard diagnosis approach to debugging. On the other hand, we are normally not only interested in finding an expression explaining the wrong behavior, we also want to give a correction that will produce the expected behav­ ior instead. In the hardware domain this correction is sim­ ple. Only the defective component of one type must be re­ placed by a working component of the type specified in the hardware design 1 · In this case, the search space for replace­ ment is of size 1. In the software domain (or design domain), a replacement can be every buildable function, and in this case, the search space is infinite. However, attempting to cor­ rect a program also has the benefit that diagnoses that cannot be combined with a meaningful correction of the error can be excluded from consideration. This was the main reason for the introduction of expression replacements in [Stumpt­ ner and Wotawa, 1996]. Every replacement represents a pos­ sible correction for the program, and to handle the infinite search space, we need to define an effective ordering on re­ placements. Note that even in simple cases, it is not always clear what criteria should be applied to produce this order. For example, is replacing the variable X by the constant XC a smaller change than replacing it by the variable Y?

We define replacements as expressions, i.e., a replacement is an element of EXP. We introduce an ordering on the re­ placements that are used instead of a given original expres­ sion. This ordering is specified by defining a function replace that, for a given expression and specified term depth (called size below since other measures are possible) defines a set of possible replacements of that depth.

1 This formulation includes the possibility that a component of a wrong type has been used.

Variables: A variable can be replaced by another variable, constant, and function.

Constants: Replacements for constants are similar to vari­ able replacements.

Others: Function Calls, Predicates, and Conditionals can be replaced by any other expression.

where the subfunctions are given by:

• Change the function and use a subset of the original arguments. The arguments are not modified.

• Select an argument. The function is discarded and the argument is not changed.
• replaceSel(F(eJ, . .. ,en) , n) = {ele E {eJ, . .. ,en}}

For simplicity, we do not allow argument permutation in the definitions here and do not include any in our examples. Replacements for the expression Y < 1 of our example are:

Note that for diagnosis purposes we can ignore replace­ ments of subexpressions, as the need for replacement of only a subexpression would be directly expressed by that subex­ pression becoming a diagnosis candidate of its own.

Figure 1 illustrates the application of replacements to the syntactical representation of a program as a tree. In case (1) the constant 0 is replaced by the constant 1. (2) gives the case where an argument has been selected from a function , case (3) shows a constant replaced by a function with two arguments.

The set of possible replacements can be further reduced by considering type compatibility. E.g., a multiplication func­ tion should be only replaced by another function returning a number. The same holds for variables and constants.

To use the replacements in our system description we must add a fault mode replace. We represent it by the predicate replaces I 2 that can be constructed from the computed re­ placements. Let E be an expression, and n be the order of the replacements. For every replacement used for diagnosis we have to add the (ground) fact replaces ( E, R) to the system description, where R E Ui<n replaces(E, i) . The be­ havior for the fault mode is specified in a natural way by:

where it is assumed that the expression Rand all of its subex­ pressions behave correctly, i.e., ·ab. In principle, given these definitions, the system description is equivalent to EXPSD combined with the explicit enumeration of all possible re­ placements for a given program. While the latter set is infinite in general, the subsets corresponding to a maximum expres­ sion depth of replacements (referred to as EXPSDi from here on) are finite for given i.

The DEBUG algorithm (from [Stumptner and Wotawa, 1996]) computes diagnoses using replacements. Diagnoses are searched for incrementally, starting with replacements of order 0 and stopping after reaching a specified size limit. Af­ ter a replacement is generated, it is tested for outcome. Note that only replacements of minimal order are taken into ac­ count, e.g., if a replacement of order i explains the fault, no replacements of order j > i must be considered.

Assuming that consistency checks take linear time, the time complexity of diagnosis is of order o(ziCOMPI) where COM P denotes the set of diagnosis components. Adding as set of fault modes MODE, e.g., as done by introducing replacements, increases time complexity to o(IMODEIICOMPI). The time for computing single diag­ noses is of order o(IMODEI · ICOM PI), limiting the ap­ plicability of this approach to small programs. However, use of focusing techniques or incrementing the replacement size during debugging increases practicability. Focusing can be achieved through a more abstract model, exploiting structural properties of the program (e.g., using only those expressions evaluated for a testcase as diagnosis components), or (static) program slicing (see [Weiser, 1984]). In this paper we will instead focus on the use of multiple testcases as described in the next section.

4 Using Multiple Test Cases

In this section, we show the use of (multiple) test cases for debugging, with two ways of filtering diagnoses. First, the goal is simply to find replacements at all -diagnoses that can­ not be repaired are discarded. Second, multiple testcases can be combined for finding common diagnoses.

Consider for example the following (buggy) functional program implementing the equality predicate

The program can be corrected by replacing the > by>=. As­ sume further the existence of the following test cases:

Only the third input vector (A= l,B = 1) leads to a wrong output value (false instead of true). Using the MBD approach leads to the four single diagnoses:

1. The and function is faulty.

2. The condition B > A contains the fault.

3./4. The variable occurrences A orB are faulty.

By using the following argument, we can show that the function and cannot be the source of the bug.

First, assume that the statement explains the fault, e.g., ab(and). Then there must exist a replacement, e.g., another function, repairing the program. Since all other expressions are assumed to behave correctly, we can calculate the inputs and output of the and function .

Such a replacement function must deliver true and false using the same input vector! Therefore no replacement can be found, contradicting our initial assumption. As final result we get that ab(and) cannot be a (single) diagnosis.

A limitation to this use of test cases is that the argument used to eliminate a diagnosis can only be applied if no faults in structure are assumed. This assumption is avoided by the second way of using test cases.

A collection of test cases can help to focus on the right fault in a more traditional way as well. Consider for example the recursive function myMul t implementing the multiplication on natural numbers (including zero).

This implementation contains a (single) bug, namely (A < = 1), which should be (A <= 0). Applying five test cases to the implementation results in the following:

Using program debugging based on program traces (one of the approaches described in [Stumptner and Wotawa, 1996]) leads only to the unsatisfactory result that all subexpressions can explain the faulty behavior. This holds especially for the third test case (tc3). For tc2, only the subexpressions leading to the expression 0 are diagnoses. By computing the inter­ section of all minimal (non-empty) diagnoses, we obtain the diagnoses explaining all test cases. The prerequisite for using the intersection is of course the assumption that all test cases only exhibit one fault in the program. In the general case, the following definition can be used instead together with a gen­ eral diagnosis algorithm, e.g., Reiter's Hitting Set algorithm.

Formally, a diagnosis .6. for a diagnosis system (SD, COM P) using multiple test cases OS is a subset of COM P such that

Similarly, a conflict CO is a subset of COM P such that

A conflict contradicts at least one observation. The above definitions can now be used for computing diagnoses as de­ scribed in [Reiter, 1987]. The filter criterion previously de­ scribed in this section, which avoids replacements that are impossible due to contradictory input-output vectors, must then be incorporated into the system description SD, e.g., by introducing meta rules of the form

In [Stumptner and Wotawa, 1996], we have presented as one of the main differences between software and hardware diagnosis the property that in the software domain the system description is of necessity derived from the program code it­ self, and therefore describes the incorrect behavior of the sys­ tem. This is the reason why fault modes are represented by replacements, i.e., actually removing components instead of altering their behavior.

The same duality can be found here, with the non­ replacability described above being the dual concept to the notion of physical impossibility in hardware diagnosis. The major difference is the infinite nature of the replacement search space as opposed to the fact that physical impossibil­ ity is a fixed restriction that always holds. The reduction in the search space does not result from properties of the original expression (diagnosis component), but of the specific replace­ ment expression chosen.

5 Conclusion

In this paper we have introduced a logic model for the de­ bugging of the functional language EXP. The model includes the handling of recursive functions. Infinite loops are simply avoided by specifying a maximum recursion level (which is just what programmers do to stop computation of a program that exceeds its expected runtime). We use this representa­ tion for the diagnosing EXP programs via replacements for expressions [Stumptner and Wotawa, 1996], which yields the following principal advantages: (1) the number of diagno­ sis candidates can be reduced (EXPSD plus appropriate filter criteria), and (2) the program can be automatically repaired up to a given level of "damage" (EXPSDi). Since diagno­ sis time increases with the number of component modes, re­ placements should be only used when necessary, i.e., if too many diagnoses are derived and measurement selection is dif­ ficult or not possible. Therefore we prefer simpler explana­ tions when conducting replacements and incorporate multiple test cases. We have given an example that shows how differ­ ent tests can help to improve diagnosis results by eliminating diagnosis candidates.

In this context the questions becomes relevant how test­ cases are actually generated. Test generation is still an open problem in software engineering research. One current re­ search approach in this field uses path analyses techniques combined with constraint satisfaction techniques to reduce the search space [ Gotlieb et al., 1998]. A different technique is the so-called mutation testing which attempts to produce testcases for correct behavior of a certain program part by making local alterations, or mutations to the program. Note that there is a certain similarity to the replacement approach. However, mutation testing works by applying alterations to a correct program in the hope of creating a representative set of incorrect ones [Offutt and Lee, 1994]. Those testcase generation techniques are intended to find a faulty behavior rather than locating a specific bug. In our case an incremen­ tal test generation algorithm using previous results, i.e., test­ cases and diagnoses, to find a testcase helping to distinguish between diagnoses should have an improved performance. A classification of testcases from a model-based diagnosis point of view with a rough outline of testcase generation has been given in [Mcllraith, 1993].

Future research along the track described in this paper in­ cludes an empirical evaluation of the proposed methods to­ gether with the development of a heuristics for controlling the debugging process. Overall control consists of selecting an appropriate sequence of actions leading to a bug free pro­ gram within a minimum amount of time. Actions are observe, use-replacement, and use-other-testcase (with test cases au­ tomatically chosen from a library). It is interesting to note that the relative costs for these actions can be (depending on program size and complexity.) significantly different from the usual relationships in the hardware domain. [Friedrich and Nejdl, 1992; Williams and Nayak, 1997] provide a basic framework for integrating planning in model-based diagnosis and can be adapted to be used in the software domain.