|
Published Articles >> Table of Contents >> Abstract
26th International Conference on Software Engineering (ICSE'04)
pp. 502-511
Efficient Forward Computation of Dynamic Slices Using Reduced Ordered Binary Decision Diagrams
Xiangyu Zhang, University of Arizona
Rajiv Gupta, University of Arizona
Youtao Zhang, University of Texas at Dallas
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICSE.2004.1317472
Send link to a friend
| Abstract |
|
Dynamic slicing algorithms can greatly reduce the debugging
effort by focusing the attention of the user on a relevant
subset of program statements. Recently algorithms for
forward computation of dynamic slices have been
proposed which maintain dynamic slices of all variables as
the program executes. An advantage of this approach is that
when a request for a slice is made, it is already available.
The main disadvantage of using such an algorithm for slicing
realistic programs is that the space and time required
to maintain a large set of dynamic slices corresponding to
all program variables can be very high. In this paper we
analyze the characteristics of dynamic slices and identify
properties that enable space efficient representation of a set
of dynamic slices. We show that by using reduced ordered
binary decision diagrams (roBDDs) to represent a set of
dynamic slices, the space and time requirements of maintaining
dynamic slices are greatly reduced. In fact not only
can the latest dynamic slices of all variables be easily
maintained, but rather all dynamic slices of all variables
throughout a program’s execution can be maintained. Our
experiments show that our roBDD based algorithm for forward
computation of dynamic slices can maintain 107-217
million dynamic slices arising during long program runs using
only 28-392 megabytes of storage. In addition, the performance
of the roBDD based forward computation method
compares favorably with the performance of the LP backward
computation algorithm.
|
 Additional Information
|
Citation:
Xiangyu Zhang, Rajiv Gupta, Youtao Zhang,
"Efficient Forward Computation of Dynamic Slices Using Reduced Ordered Binary Decision Diagrams,"
icse,
pp. 502-511,
26th International Conference on Software Engineering (ICSE'04),
2004
|
|
