Program Instrumentation and Software Testing J.C. Huang University of Houston The program tester needs to know what goes on inside a program as it executes during a test Instrumentation (methods 0qk permit collection of testing coverage data without modifying the logical properties of programs being tested. It is well known that one cannot find all the errors in a program simply by testing it for a set of input data.'-3 Nevertheless, program testing is the most commonly used technique for error detection in today's software industry. Consequently, the problem of finding a program test method with increased error-detection capability has recived considerable attention in the field of software research. There appear to be two major approaches to this problem. One is to find better criteria for test-case selection.'"7 The other is to find a way to obtain additional information (i.e., information other than that provided by the output of the program) that can be used to detect errors.8-" The technique of program instrumentation discussed in this article can be regarded as a major outgrowth of the second approach. The main idea is to insert additional statements (instruments) into the program to be tested for the purpose of computing certain program attributes. By testing (executing) the instrumented program for a properly chosen set of test cases, we will be able to obtain the values of the program attributes automatically. The attribute values provide us with additional information for error detection. The following pages illustrate the utility of this technique and explore its potential as a tool for program validation. m o c . 5 generate program profiles by Russell and Estrin,12 to measure instruction mix and execution time by Bussell and Koster,13 and to produce information about the syntactic and operational characteristics of programs by Stucki,"4 to mention a few. The first direct application of program instrumentation to program testing appears to have been the measurement of the thoroughness of a test.18-'9 b u th i g Test requirements. It seems intuitively clear that existence of an error in a program will not be reflected in the test result unless the program component in error is executed during the test. Furthermore, the probability of discovering errors through testing can be improved by increasing the number of times each component is executed (exercised).2 Based on this observation we can formulate three test requirements: (1) Each statement in the program should be executed at least once. (2) Each edge in the flowchart should be traversed at least once. (3) Each edge in the flowchart should be traversed for more than once. Since satisfaction of any test requirement implies satisfaction of the preceding one, these three requirements (in the order listed) represent three increasing levels of test thoroughness. Examples of program instrumentation One cannot find all the errors in a proNumeous apphcations of program istrumentation gram by testing it for a set of input data. in program analysis and evaluation have been reported. For example, it has been utilized to April 1978 0018-9162/78/0400.0025$00.75 © 1978 IEEE 25 Software counters. A simple and practical way to determine the level of thoroughness of a test is to instrument the program to be tested with a set of software counters..16-20 First we have to identify a set, of points in the program such that, if we know the number of times each point is crossed, we can determine the number of times each statement is executed (or each edge is traversed). We then. prepare the program for testing by inserting the counters at these points. After having the program tested for a number of test cases, we can determine the level of thoroughness by examining the resulting counter values. The counter idea can be illustrated by using the example program shown in Figure 1. For the purpose of discussion, let us assume that the software counters are to be implemented by a procedure (subroutine) named count (i), where i is an integer parameter. This procedure consists of an integer array, counter[1], counter[2], .., counter[n]; the value of each element is set to zero initially. A call of count(i) will increase the vaulue of counter[i] by one. Initially, let us take the simple-minded approach of placing a counter on each edge, as shown in Figure 2. Now we are ready for a set of test cases (listed, with the resulting counter values, in Table 1). The fact tha