Verifying embedded software functionality: The power of dynamic slicing
Editor’s Note: In this second in a four part series, Abhik Roychoudhury, author of Embedded Systems and software validation, details the ways in which dynamic slicing can be used for assessing software functionality. In this Part 2: The power of dynamic slicing.
Dynamic slicing is a generic method for program debugging and comprehension. The method takes in the following: (a) a program P, (b) an input I of the program P, and (c) a description of the error observed during the execution of P for input I.
The output of the method is a fragment of P that is likely to be responsible for the observed error. Thus, the output of the method is essentially a “bug report” of sorts, an explanation of the cause of the observed error.
To discuss the method, we first need to understand how the observed error is described. Usually, the observed error is presented as a pair (l, v), where l is a line in the program P being debugged and v is a program variable.
This usually means that the programmer is unhappy about the value of v observed in line l of a given program for a given input. That is, when a given program P is executed with a given input I, the user is unhappy about the value of v observed in line l of the program and would like to seek an explanation for it.
The explanation will be provided by dynamic slicing, which acts as a debugging method. One issue needs to clarified in this regard. A line l may be executed several times during the execution of program P with input I. Therefore, when the programmer seeks an explanation of the value of v in line l, he or she could be interested in the value of v in the last execution of l, or the value of v in some specific execution of l, or the value of v in all executions of l.
Note that whichever executions of l we are interested in, it makes little difference to the dynamic slicing method itself; it only makes a difference to the initialization of the dynamic slicing method.
Having explained the notion of observed error, we need to discuss the notion of dynamic slice and what it stands for. The dynamic slice stands for a detailed explanation of the observed error. In other words, the dynamic slice can be thought of as a “bug report,” and the task of dynamic slicing as “debugging”—finding the source of a bug that is observed elsewhere.
How is the bug report constructed? Let us say we are performing dynamic slicing of a program P with input I, where the slicing criterion is the value of variable v in the last occurrence of line 1. Slicing can now proceed in one of two ways:
1 - Via a backwards traversal of the execution trace of program P for input I; the traversal starts from the last occurrence of line l in the execution trace.
2 - Via a forward execution of the program P for input I. The first possibility involves storing the execution trace in some form and hence leads to space overheads. However, the computation in this case is goal-directed (i.e., redundancy free), because we compute the slice of only the slicing criterion we are interested in—the value of variable v in the last occurrence of l.
In the second option, we do not encounter any space overheads owing to storing of the program execution trace. We do, however, have to compute and store many slices during the execution. For each executed statement, we compute and store the slices of the variables used in the statement; these slices are used for computing slices of the subsequent variable usages.
Thus, even though the program execution trace does not need to be stored, there is a time and space overhead in computing many dynamic slices (many of which are unrelated to the actual slicing criterion the programmer is interested in). In other words, the dynamic slice computation is not goal-directed in this situation.
Whether a dynamic slice is computed by forward or backward traversal of program execution, it is computing chains of data and control dependencies. To explain these concepts, let us first consider a simple program fragment, written in C-style (Figure 5.4 below). The program constructs the sum of all even numbers from 1 to N and the product of all odd numbers from 1 to N, where N is a given integer.
We will use this example program to define the necessary concepts—(static and dynamic) control dependencies, (static and dynamic) data dependencies, dynamic dependence graphs, and dynamic program slices.
Consider an execution of the program for N = 3. The execution trace is as follows:
(1, 2, 3, 4, // initialization
5, 6, 8, 9, // first iteration, i = 1
5, 6, 7, 9, // second iteration, i = 2
5,10) // i = 3, end of execution