Fritzson, P., Gyimothy, T., Kamkar, M., and Shahmehri, N. (1990). Generalized Algorithmic Debugging and Testing. Technical Report LiTH-IDA-R-90-42, Department of Computer and Information Science, Linköping University, Sweden. Also accepted to SIGPLAN'91 Conference on Programming Language Design and Implementation, Toronto, Ontario, Canada June, 1991. Proc in SIGPLAN Notices 26:6, June 1991 and has been accepetd to the journal: ACM LOPLAS-ACM Letters of Programming Languages and Systems. (bibtex),
Abstract: This paper presents a version of generalized algorithmic debugging integrated with the category partition method for functional testing. In this way the efficiency of the algorithmic debugging method for semi-automatic bug localization can be improved by using test specifications and test results. The long-range goal of this work is a semi-automatic debugging and testing system which can be used during large-scale program development of non-trivial programs.The method is generally applicable to procedural languages, and is not dependent on any ad hoc assumptions regarding the subject program. The original form of algorithmic debugging, introduced by Shapiro [Shapiro-83], is however limited to small Prolog programs without side-effects. Another drawback of the original method is the large number of interactions with the user during bug localization.To our knowledge, this is the first method which uses category partition testing to improve the bug localization properties of algorithmic debugging. The method can avoid irrelevant questions to the programmer by categorizing input parameters, and match these against test cases in the test database. In addition, we use program slicing, a data flow analysis technique, to dynamically compute which parts of the program are relevant for the search, thus further improving bug localization.We believe that this is the first generalization of algorithmic debugging for programs with side-effects written in imperative languages such as Pascal. These improvements together makes it more feasible to debug larger programs.A prototype generalized algorithmic debugger for Pascal, and a test case generator for real size application programs in Pascal, C, dBase and LOTUS have been implemented.
CS Dept TR Overview