A General Framework for Debugging KEIJIRO ARAKI , ZENGO FURUKAWA, and JKVGDE CHENG , Kyushu Unioersity I) Programmers have no clear idea bow to systematically debug a program, which makes it d$j%ult to share and evaluate methods. This article presents the requirements for a general debugging framework. a e ug&g. is said to be -- the least established area h software de- velopment: Industrial developers have no clear ideas about general debugging methods or effective and smart debugging tools, yet they debug programs anyway. Debugging requires much experience in program development because it relies on heuristic insights. Because it is not es- tablished as a disciplined task, it is difficult to share as a systematic method. In an ef- fort to correct this, we have developed a process model that establishes a minimum set of requirements for systematic debug- ging- Our process model views debugging as an iterated process of developing hypothe- ses and verifying or refuting them. Hy- potheses may concern the location of bugs, the causes of errors, expected program be- havior, and how to modify the program to correct errors, among other things. STATE OF THE ART The most primitive way to debug a program is to insert so-called debug state- ments, which during execution print in- formation like what statements are exe- cuted or what values particular variables have at a particular point. Debug state- ments let you observe a program’s behav- ior. The most important considerations in this method of debugging are where to in- sert debug statements, what kind of infor- mation to print, and what to comprehend by analyzing the output. Another approach is to use debugging tools, many ofwhich provide only primitive, low-level facilities. These tools help pro- grammers insert breakpoints, inspect the states at those points during program exe- cution, change the values of variables and program parts, and continue the execution. 14 07407459/91/05co/0314/$01 co 0 IEEE MAY 1991Other tools include nacers, which let you observe or analyze a program’s execution history, and symbolic debuggers, which provide high-level interfaces. The same considerations hold when using debugging tools that hold when using debug statements-what to observe and what information will be obtained. Some programmers do not completely trust the information obtained with de- buggers, insisting that debuggers some- times report incorrect information. debugging that programmers can follow? We believe so. As we describe here, you can derive many processes from our gen- eral model, from traditional debugging processes to an algorithmic process for a class of logic programs4 to an execution monitoring tool for concurrent Ada pro- grams.’ DEBUGGING PROCESS You can derive many In addition to this concern, debugging tools are not yet effective because they do not provide enough abstraction to repre- sent and retrieve informa- tion at the specification and computation-model level. Researchers have tried different ways to manage the huge amount of output from debuggers and have used graphics and animation to try to make program execution more understandable, but so far these attempts have not produced debuggers that are effective enough for high-level debug- ging.’ In this article, “error” means the differ- ence between a program and its specifica- tion - the difference between the behav- ior requested by the specification and the behavior performed by the program - and “bug” means the cause of an error. We assume that the specification has no error, that the cause of the error - the bug - is in the program. We also assume that errors are detected ei- ther when developers test a program or when users use it, and we assume these errors are to be cor- rected by debugging. Concurrent programs present an even more dif- ficult debugging problem because it is difficult to re- peat the execution that outputs an error.2l3 When an error is found in a con- processes trom our general model, from traditional debugging processes to an algorithmic process for a class of logic programs to an execution monitoring tool for concurrent Ada programs. current program, the very first thing pro- grammers try to do is reproduce the error. They may spend a great deal of time and effort only to find the conditions that caused the error by chance. Programmers often say that debugging a concurrent program is almost complete when you’ve figured out how to reproduce the error. Another serious problem overall is the effect the probe or monitoring device itself has on program behavior during execu- tion. It’s possible that the probes them- selves may give programmers incorrect in- formation about a program’s behavior. With these problems in mind, is it pos- sible to develop a general framework for Debugging is the pro- cess of locating and cor- recting errors in a pro- gram in which errors have been detected. In locating the errors and grasping their causes, program- mers develop hypotheses about the errors and their causes, and verify or refute these hypothe- ses by examining the program. In correct- ing the errors, programmers again de- velop hypotheses about how to modify the program and verify or refute them. Figure 1 shows our debugging process model: Programmers begin with a set of hypotheses, modify that set, select hypotheses for verification, and verify or refute the selected hypotheses until the bug is fixed. Hypothesis set. In our model, hypotheses relate to source code, its specification, and its behavior. In faq programmers hypothesize about the errors in the program, including the places in the program where errors are supposed to occur, the supposed causes of the errors, behaviors that are supposed to be correct or incorrect, and modifications that ate supposed to correct the errors. These hypotheses include the facts that have been proved so far about the properties of the program and its errors, although in this article we also call these facts hypotheses. The programmer’s em- pirical knowledge of development, the program itself, and its specifications are also included in the hypothesis set. For simplicity, our debugging process model starts with error reports as the