[19 Jan]

Dynamic Slicing for Debugging

A dynamic slice shows only data and control dependences: ith execution of stmt s is control/data dependent on jth execution of stmt r. This information is partially useful for debugging. Because although understanding the dependences is the first thing to do, the next thing a programmer wants to know are the actual values that create the dependence. We want to know the values because that will determine if we want to investigate further for that value. If that value looks correct, we dont investigate about that value further. Otherwise, we do. So a dynamic slice algorithm should be able to produce the actual values alongwith the dependencies in order to be able to useful. Although there have been so many papers on dynamic slicing, none of them report any experience of debugging a real application using it. It is quite likely due to the above reason: without the values a slice does not help much in debugging a complex application. Thus it seems to me an interesting and practically useful problem. No previous work seem to address this problem.footnote

Elevator Pitch
The problem is to be able to show the values associated with the dependencies when the programmer needs while he navigates the dynamic slice. The language of consideration is Java, which will probably pose additional problems on handling OO features(reflection, virtual calls). The solution must scale beyond small toyish programs. And I will try to show how this is useful in debugging 20 bugs of JABA. In sum, it will feel like execution replay and backward debugging. But it will be better than them in the sense only information that is relevant to the bug is recorded(efficiency) and presented(usability).

Challenges

Is dynamic slice enough? That is, suppose the system can infact show all the values associated with the dynamic slice, is that information sufficient to debug? (after quite some thought) my answer is: pretty much. I think we may have to extend the definition of dynamic slicing to include some more dependencies, but it may not be much. For now, I can see we need "relevant" slice at the least. But that is a question that is orthogonal to how we "reproduce" the values?
How do we reproduce the values?
1. Naive solution is to record the values when we record a dynamic dependency. Agrawal et. al.[1] take this approach. But clearly it does not scale up, going by the fact that recording the dependencies itself takes so huge space.
2. Execute twice. Execute once and record the dependencies. When the programmer asks for a dynamic slice, execute the program again and record the values associated with each dependency that is included in the slice. Values can be recorded incrementally ie only changes w.r.t. previous copies.
3. Another possibility is, we recompute the values when the programmer asks for the values associated with a dependency. Naively it can be done reexecuting the program from start. But that will be undesirable in many cases. Alternatively, we can have a hybrid approach where we record the values at some points and for others we recompute them from the recorded values. Although it sounds like checkpointing, it probably should not be. Since checkpointing would be a heavyweight solution that will require us to save a copy of the entire program state. I am thinking of using a lightweight interpreter like Dynamic Java so that we can recompute only the desired values from a partial copy of the program state.
Dynamic slicing algorithms as described by Agrawal and Gupta can compute the slice for any statement in the program. That is useful for other applications of dynamic slicing, but in debugging in most cases it is possible to know the statement (point of bug "manifestation") for which dynamic slice is needed. That must be taken into our advantage. We can do some static analysis to reduce the recording overhead.

Footnote:
I have looked around quite a bit. Tracing all related papers of Agrawal and many who refer them. Gupta et. al. have just shown that recording the dependencies for real application is viable. Recording the values is more difficult than that.

Last modified 19 January 2005 at 8:16 pm by Saswat Anand