Diagnostic Reasoning in Software Fault Localization

DIAGNOSTIC REASONING IN SOFTWARE FAULT LOCALIZATION

Robert L. Sedlmeyer* William B. Thompson Paul E. Johnson

University of Minnesota

faults rather than of fault localization.

ABSTRACT

We present a diagnostic model of software fault localization. A diagna~tiQ approach to fault localization has proven effective in the domains of medicine and digital hardware. Apply­ ing this approach to the software domain requires two extensions: a heuristic abstraction mechanism which infers program function from structure using recognition and transformation tactics; and a search · mechanism which integrates both prototypic and causal reasoning about faults.

I. INTRODUCTION

In this paper we present a model of fault localization for program debugging based on a trouble-shooting paradigm [1) . Within a diagnostic framework we define the software fault localization task as follows: A 6ault exists in a program when­ ever its output differs from that expected by the user. These descrepancies are called 6ault mani6~tatia~. The task is to identify the cause of each manifestation which is specific enough to effect program repair.

Application of the 'trouble-shooting strategy has proven effective in constructing intelligent systems for hardware [2,3,4) and medical [5,6,7) diagnosis. In contrast to verification- based approaches (cf . [8,9,10,11) this strategy concen­ trates computational resources on suspect compo­ nents. Applying the diagnostic approach to the software domain requires two extensions: a heuristic abstraction mechanism that infers func­ tion from structure using recognition and transfor­ mation tactics; and a search mechanism that inte­ grates both prototypic and causal reasoning to localize faults.

Several program debugging systems evidence trouble-shooting tactics [12,13,14), but none are based on a comprehensive diagnostic theory. Sussman [1) was primarily interested in developing a theory of skill acquisition and examined the role of debugging in that context . While Miller and Goldstein [13) addressed the debugging task direct­ ly, the faults which MYCROFT analyzed were tightly constrained by the simplicity of the programs involved. Shapiro [14] addresses more realistic debugging environments, but formulates a theory of Our model partitions diagnostic knowledge for the software fault localization task into knowledge usPd to locate known and novei faults. For diag­ nosing known faults the knowledge base contains a hierarchy of faults which are known to occur in programs from a particular applications domain, and a set of empirical associations which relate fault manifestations to possible causes. For diagnosing navel faults the knowledge base contains models of implementation alternatives and execution behavior of functions indigenous to the domain. Both know­ ledge sources are utilized by a set of localization tactics to generate, select and test fault hypo­ theses.

*Current address: Department of Computer Tech . , Purdue University at Fort Wayne, Indiana 46805

II. KNOWLEDGE OF PROGRAM STRUCTURE AND FUNCTION

Knowledge of program structure and function is necessary for diagnosis of both known and novel faults. In the former case it is used to confirm expectations associated with a given fault hypo­ thesis; in the latter case it is used to trace violations of expected behavior to their source. In our model this knowledge is captured in 6unQtianal p~atatyp~.

A 6unQtianal p~atatype consists of four com­ ponents: a set of recognition triggers, a list of pre- and post-conditions describing the execution behavior, a description of prototype components and their topology, and a list of constraints among components that must hold for recognition. Proto­ types are defined at three levels of abstraction: the language, programming, and applications levels; and are hierarchically organized. A portion of the functional prototype hierarchy describing the com­ ponent topology of the "master file priming read" (MFPR) function is given in Figure 1.

The f igure shows that the MFPR consists of a single component, the file_priming_read. A file_priming_ read is only recognized as a MFPR if two con­ s tra ints a re me t: the input record is used as a master record and the input file is used as a mas ter file. Recognition triggers inc lude the fi l e priming read and file input stmt prototypes as well as the language keyword "read".

III. KNOWLEDGE OF FAULTS

While f unc tiona l prototypes des cribe expected program structure and function; 6autt mod~ des­ cribe expected defects in program structure and func tion. A 6au£t model embodies knowledge of a particular implementa tion error or c l ass of errors. This knowledge consists of conditions under whi ch the model is applicable , a set of fault hypotheses , and a set of related fault models. A fault hypo­ thesis is an expected defect in a functional pro­ totype . Defects are defined as missing prototype components or viola ted constraints. Like func tion­ al prototypes fault models are hierarchically organized. Figure 2 details a fault mode l fo r a master file input error.

(mas t e r file priming read error (triggered by -

1. inv~lid first master record

2. invalid firs t new mas ter re~ord

3. invalin mas ter record count)

(expec t ed defects

1. missing MFPR)

(related faults

1 . i;sert_error)

Figure 2. Sample Fault Model

IV. LOCALIZATION TACTICS

Localization is performed using three tactics: fiautt-dniven, fiunction-dniven and computation­ dkiven. Fautt-dniven localization directs sea;ch at f inding a particular kind of fault, such as an unexpected end of file. Function-dkiven locali­ zation analyzes a-particular functional prototype for an error. Computation-dniven localization concentrates search on the computation of a set of program variables. Each makes use of an abstrac­ tion mechanism (Section 5) to generate and test fault hypotheses.

Multiple localization tactics are desirable for three reasons . First, they enhance the pro­ bability of finding faults since different tactics analyze the source code from different perspectives. Secondly, tactics which best fit the available in­ formation can be chosen. Thirdly, each tactic is opti~al, in the sense of minimizing computational resources, for a particular localization task.

Fault-driven localization uses the fault model hierarchy to generate fault hypotheses. Output discrepancies serve as triggers for selecting a particular fault model . The more salient the trigger set the more specific the fault model and the associated fault hypotheses . Given a fault model, localization continues by first choosing

one of these fault hypotheses and then invoking the abstraction mechanism to t es t it. If the hypothesis fails then a r e l ated hypothesis can be proposed, a different fault model can be applied , or the t ac tic can be abandoned .

Func tion-driven localization uses output dis­ c r epancies to suggest that a particular functional prototype is improperly implemented. The abs trac­ tion mechanism is then invoked to identify the code which implements the prototype . If the pro­ totype cannot be found then the source code pro­ ducing the most feasible match is considered -as the intended implementation . The fault is identi­ fied by the statement causing failure in the match­ ing process. This tactic can also be directed to examine a particular abstraction level for a fault. All prototypes defined a t the chosen level are con­ s idered s uspect. This application of the func tion­ driven t ac tic i s less direc t ed and us ua lly less desirable. Only when the output disc r epancies offer no bas is fo r prototype selection does this al terna tive become a ttrac tive .

Computation-driven localization traces the computa tion of a particular set of program vari­ ables. The computation is analyzed by extracting from the progr am those statements that directly affec t the values of variables in the set . This extrac tion process is known as ~tieing [lS]. The computation can be followed in either a forward or reverse order of execution flow . Faults are found by using the abstraction mechani sm to inter­ pret sta t ements in the slice as membe r s of more abs trac t functional prototypes and comparing the expected comput a tiona l r esults to those derived .

V. PROGRAM ABSTRACTION

Progr am abstraction i s performed by matching functional prototypes to the sourc~ code . Ab­ straction may either be expec tation-driven or data- driven depending upon the localiza tion tactic selected . Expectation- driven abstraction ma t ches prototypes to code in a top-down manner, recursive­ ly matching components until a direc t match can be made against the source code or previously recog­ nized prototypes. Data-driven abstraction employs language-level triggers t o select prototypes for matching . Prototypes matched at lowe r levels of abstraction serve as triggers for ma tching a t higher levels. Once a functional prototype is identified the corresponding code is bound to it.

Recognition-based abstraction is an efficient technique , but it has limitations. Recognition of a functional prototype may fail for one of three reasons: a defect exists in the source code implementing the prototype, the wrong prototype is selected, or the source code represents an un­ familiar but correct implementation . The effec­ tiveness of the recognition mechanism depends on the exactness of the triggering process and the richness of the alternative implementation set. Purely structural matching is augmented by func­ tional matching. The behavior of a program se~ment which is inferred from language semantics, can also be compared to the functional descriptions in the prototype hierarchy .

VI. AN EXANPLE

We have implemented an initial version of the model in a program named FALOSY (FAult LOcalization SYstem). FALOSY addresses faults in master file update programs [16]. In this section we illus­ trate FALOSY's reasoning for the master file priming read error.

FALOSY is presented with a discrepancy list and a list representation of the program's source code. The discrepancy list formally describes differences between expected and observed output . An abridged trace of FALOSY's reasoning is given in the Appendix. Numbers in parentheses refer to line numbers jn the Appendix.

A production system, whose antecedents are sets of discrepancies, is used to select the initial localization tactic. In this case the fault-driven tactic is chosen and the master file priming read fault model is triggered (1). FALOSY hypothesizes that the priming read for the master file is missing (2). The abstraction mechanism is invoked to identify the corresponding prototype (4). A check is first made to determine if it has been previously identified. Since it has not, the recognition mechanism is invoked recursively to find the components of the master file priming read prototype.

Eventually search is carried out at the source level, and three read statements (6, 26) are selected for further matching. Constraints are now checked starting with those at the lowest level in the abstraction hierarchy. The first candidate is rejected since the file identifier is not used as the master file (20). The second and third candidates are rejecte~ ~ecause they do not cede the update loop (24,28). No candidate fies all constraints and recognition fails. original hypothesis is thus verified. pre­ sa tis­ The

APPENDIX

1. Applicable fault models (rn f pr)
2. Expected defects ((rn f pr-rnissing))
3. 3 . Fault hypothesis (rn f-pr missing))
4. 4 . Trying to recognize! m f pr
5. 5 . Triggers are (read f i-s- f p r
6. Matching rn f pr to (s6-read-transfile transbuf)
7. rn f pr has-role f p r
8. Matching f_p_r to-(s6 read transfile transbuf)
9. f p r has role f i s

~1~ . Matching f is to(s6 read transfile transbuf)

1. f i s is pr{mitive
2. Checking constraint (data-type f ile pascal fid)
3. Checking constraint (data-type record pascal_rec)
4. Match for f i s succeeds
5. Checking constraint (before f i s update loop)
6. Trying to recognize: update-loop

-

1. Recognition of update-loop succeeds
2. Match for f_p_r succeeds
3. Checking constraint (use file rn_f)
4. Role file, which is bound to transfile, is used as a t f whereas rn f was expected
5. Match for rn f pr fails
6. 22 .· Matching rn f pr to (s24 read oldfile o1dbuf)
7. 23 . Checking constraint (before f i s update-loop)
8. 24 . Role f i s, which is bound to g 0001!·, does not precede role update loop, which is bound to g0005 -
9. Match for f p r fails
10. 2f.. Matching rn f pr to (s52 read transfile transbuf)
11. Checking constraint (before f i s update loop)
12. 28 . Role f i s, which is bound to-g00018, does not precede role update loop which is bound to g00005
13. Match for f p r fails
14. Recognition-of rn_ f_pr fails
15. Fault hypothesjs verified
16. Fault is: (rn_ f_pr missing)

BIBLIOGRAPHY

1. J . DeKleer, "Local methods for localization of faults in electonic circuits," MIT-AI Memo 394, 1976 .
2. M.Genesereth, "Diagnosis using hierarchic design models," PJtoc.eeding.6 o6 :the Sec.orui AAAI Con6eJr.enc.e, August, 1982.
3. R. Davis, H. Shrobe, W. Harnscher, K. Wieckert, M. Shirley, and S. Polit, "Diagnosis based on description of structure and function," PJtoc.eed{_ytgJ.> o6 :the Sec.ond AAAI Con6eJr.enc.e, August, 1982 .
4. R. Hartley, "How expert should an expert system be?", PJtoc.eeding.6 IJCAI-81, August 1981.
5. R. Patil, P. Szolovits, W. Schwartz, "Causal understanding of patient illness in medical diagnosis," PJtoc.eeding.6 o6 IJCAI-81, August, 1981.
6. E. Shortliffe, Compute!t Ba;..ed Medic.a.l Con6U-Ua­ tion6: MYCIN, American Elsevier, New York, New York, 1976.
7. B. Chandrasekaran and S. Mittal, "Deep versus compiled knowledge approaches to diagnostic problem-solving," PJtoc.eeding.6 o6 the Sec.ond AAAI Confie!tenc.e, August, 1982.
8. H. Wertz, "Understanding and improving LISP programs," I JCAI -77 Pl!oc.eed.ing-6.
9. R. Ruth, "Intelligent program analysis," Altti6ic.ia.l Intettigenc.e, Vol. 7, No. 1, 1976
10. C. Adam and M. "LAURA, a sys tern to debug student programs," Altti6ic.ia..e Intettigenc.e, November, 1980.
11. F. "Understanding and debugging computer programs," Inte!tnationa.l JouJtn.al. o~ Man-Mac.hine Studie-6, Vol . 12, 1980, pp. 1S9=202;
12. [12]G. Sussman, A Compu;ta;ti.ona.l Model o6 S/U.U Ac.qui'->ition, American Elsevier, New York, 1975.
13. [13]Mil1er, "A structured planning and debugging environment," InteJr.nationa.l JouJtna.l o6 Man­ Mac.hine Studie-6, Vol. 11. 1978.
14. [14]D. Shapiro, "Sniffer: a system that understands bug," MIT-AI Memo 638, June, 1981
15. [15]M. Weiser, "Program slices: formal, psychologi­ cal, and practical investigations of an automatic program abstraction method," University of Michigan Ph .D. Thesis, 1979.
16. [16]B. Dwyer, "One more time - How to update a master file," Communic.ation6 o6 -the ACM, Vol. 24, No. 1, January 1981.