Evaluating explicitly context-sensitive program slicing

摘要

One of the important issues in constructing interprocedural program slices is maintaining context-sensitivity or preserving calling context when a procedure is called at multiple call sites. Though a number of context-sensitive techniques have been presented in the last decade, the following important questions remain unanswered: 1) What is the level of precision lost if context-sensitivity is not maintained ? 2) What are the additional costs for achieving context-sensitivity?

In this paper, we evaluate a PDG based explicitly context-sensitive interprocedural program slicing technique for accuracy and efficiency. We compare this technique against a context-insensitive technique using a program slicing framework we have developed for Java programs for which only the byte-code sequences are available.

Our results show that the context-sensitive technique, in spite of its worst case exponential complexity, can be very efficient in practice. The execution time for our set of benchmarks is, on the average, only twice as much as the execution time for the context-insensitive technique. The results on the accuracy for the context-insensitive technique are mixed. For 53% of the 2464 slicing criteria used in our experiments, the context-insensitive technique does not loose accuracy. However, in some cases, it can also lead to slices with 35 times more vertices. On the average, the slices constructed from the context-insensitive technique are twice as large as the one from the context-sensitive technique.