GIT-CERCS-03-10
Alessandro Orso, Saurabh Sinha, Mary Jean Harrold,
Understanding Data Dependences in the Presence of Pointers
Understanding data dependences in programs is important for many
software-engineering activities, such as program understanding, impact
analysis, reverse engineering, and debugging. The presence of
pointers, arrays, and structures can cause subtle and complex data
dependences that can be difficult to understand. For example, in
languages such as C, an assignment made through a pointer dereference
can assign a value to one of several variables, none of which may
appear syntactically in that statement. In the first part of this
paper, we describe two techniques for classifying data dependences in
the presence of pointer dereferences. The first technique classifies
data dependences based on definition type, use type, and path type.
The second technique classifies data dependences based on span. We
present empirical results to illustrate the distribution of
data-dependence types and spans for a set of real C programs. In the
second part of the paper, we discuss two applications of the
classification techniques. First, we investigate different ways in
which the classification can be used to facilitate data-flow testing
and verification. We outline an approach that uses types and spans of
data dependences to determine the appropriate verification technique
for different data dependences; we present empirical results to
illustrate the approach. Second, we present a new slicing paradigm
that computes slices based on types of data dependences. Based on the
new paradigm, we define an incremental slicing technique that computes
a slice in multiple steps. We present empirical results to illustrate
the sizes of incremental slices and the potential usefulness of
incremental slicing for debugging.