Effective Slicing: A Generalization of Full and Relevant Slicing

This research was conducted by Anne Mulhern and Ben Liblit.

Abstract

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 well-behaved if it calculates the same values for V at p as P. A well-behaved slice exhibits good behavior. A static slice must be well-behaved for every input while a dynamic slice must be well-behaved 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.

Well-behaved union slices allow reasoning about program behavior on sets of inputs, but existing union slicing algorithms may yield ill-behaved 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 well-behaved 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 well-behaved. 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.

Full Paper

The full paper is available as a single PDF document. A suggested BibTeX citation record is also available.

Return to Ben’s Home Page.