Verifying embedded software functionality: The power of dynamic slicing

Abhik Roychoudhury

August 7, 2012

Abhik Roychoudhury

Detailing the methodology
We now formally describe the dynamic slicing method for software debugging. Traditionally, dynamic slicing is performed w.r.t. a slicing criterion (H, l, v), where H represents an execution trace of the program being debugged, l represents a control location in the program, and v is a program variable.

A dynamic slice contains all statement instances (or statements) that have affected the value of variable v referenced at l in the trace H. A dynamic slicing algorithm can proceed by forward or backward exploration of an execution trace.

Here we summarize a backwards slicing algorithm that is goal-directed (w.r.t. the slicing criterion), but requires efficient storage/traversal of the trace. During the trace traversal that starts from the statement in the slicing criterion, a dynamic slicing algorithm maintains the following quantities: (a) the dynamic slice φ (b) a set of variables ζ whose dynamic data dependencies need to be explained, and (c) a set of statement instances γ whose dynamic control dependencies need to be explained. Initially, we set the following: φ =γ= last instance of location l in trace H, and (b) ζ {v}.

For each statement instance stmt encountered during the backward traversal, the algorithm performs the following two checks. The algorithm terminates when we reach the beginning of the trace.

Check dynamic data dependencies. Let v^stmt _def be the variable defined by stmt. If v^stmt _def ε, it means that we have found the definition of vstmt which the slicing algorithm was looking for. So, v^stmt_def is removed from ζ , and variables used by stmt are inserted into. In addition, stmt is inserted into ζ and γ .

Check dynamic control dependencies. If any statement instance in γ is dynamically control dependent on stmt, all statement instances which are dynamically control dependent on stmt are removed from γ . Variables used by stmt are inserted into ζ, and stmt is inserted into φ and γ. When the dynamic slicing algorithm terminates, the resultant dynamic slice, (i.e., the setφ) is reported back to the programmer for inspection.

Figure 5.6 below describes how slicing can be made to fit in with software testing and debugging. Usually a program is tested against inputs from a test suite. If the program outputs are as “expected,” the tests are said to pass.

Figure 5-6. Software testing and debugging with slicing as the debugging method

For a failed test (i.e., where the output is “unexpected”), the programmer needs to find the cause of unexpected program behavior. This brings us to debugging, and dynamic slicing is one debugging method. The slicing criterion comes from the failed test case itself; the slicing criterion is (I, l, v), where I is the input for the failed test case, l is the line number where the “unexpected” output is observed, and v is the output variable whose observed value is “unexpected.”

For dynamic slicing, the program is run against the same input (the one leading to a failed test case) in an instrumented fashion— that is, (part of ) the execution trace is collected. The execution trace is analyzed via dynamic slicing as mentioned in the preceding. The constructed dynamic slice acts as the bug report.

The programmer can use it for program comprehension and debugging, thereby locating the source of error. Needless to say, only the computation of the slice is automatic. Comprehension and debugging of programs using the slice is a fully manual activity.

Time and Space Complexity
Note that dynamic slicing is an algorithmic framework, and it can be adapted for different programming languages. The complexity of dynamic slicing algorithm for modern programming languages such as Java is as follows:

1 - Worst-case space complexity is linear in the length of the execution trace, and
2 - Worst-case time complexity is quadratic in the length of the execution trace.

The quadratic time complexity is owing to the dependence computation, which involves checking pairs of operations in the trace.We note that state-of-the-art slicing tools (such as the JSlice tool for Java) employ online compression of the execution trace—where the execution trace is compacted as it is collected, achieving compaction ratios (memory taken up by original trace versus memory taken up by compact trace) of 10 to 1000.