Effective Slicing: A Generalization of Full and Relevant Slicing
Anne Mulhern, Ben Liblit
2008
A program slice, P′, is the part of a program, P, that may affect the value of a set of variables, V, at a program point, p. Informally, P′ is wellbehaved if it calculates the same values for V at p as P′. A wellbehaved slice exhibits good behavior. A static slice must be wellbehaved for every input while a dynamic slice must be wellbehaved for just one input. A union slice is the union of several dynamic slices calculated with respect to different inputs but the same V and some occurrence(s) of p in the program's execution history. A realizable slice is a union slice calculated with respect to all initial states. A realizable slice is, in general, not computable. Wellbehaved union slices allow reasoning about program behavior on sets of inputs, but existing union slicing algorithms may yield illbehaved slices, i.e., for some input among those used to construct the dynamic slices, the union slice will calculate incorrect values for V. We find that bad behavior of union slices is an artifact of the particular dynamic slicing algorithm, full slicing, used to calculate the individual slices. Full slicing is the name given to the originally proposed version of dynamic slicing, to distinguish this version from other variants of dynamic slicing that have arisen since. In contrast, the unions of relevant slices do yield wellbehaved slices. We propose a generalization of full and relevant slices, effective slices, that can be used to calculate unions of dynamic slices that are more precise than the unions of relevant slices, but still wellbehaved. We extend the generalization to scant slices. We show that the nodes in the set differences between unions of different kinds of slices have certain properties useful in debugging.
Download this report (PDF)
Return to tech report index
