Evaluating explicitly context-sensitive program slicing

ABSTRACT

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.

REFERENCES

• 1: Ole Agesen. Constrained-based type inference and parametric polymorphism. In Proceedings of Static Analysis Symposium (SAS), appeared as the volume no. 864 of the Springer Lecture Notes in Computer Science Series, pages 78-100, September 1994.
• 2: Darren C. Atkinson , William G. Griswold, The design of whole-program analysis tools, Proceedings of the 18th international conference on Software engineering, p.16-27, March 25-29, 1996, Berlin, Germany
• 3: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 4: David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.108-124, October 05-09, 1997, Atlanta, Georgia, United States
• 5: Mary Jean Harrold , Ning Ci, Reuse-driven interprocedural slicing, Proceedings of the 20th international conference on Software engineering, p.74-83, April 19-25, 1998, Kyoto, Japan
• 6: Mary Jean Harrold , Brian Malloy , Gregg Rothermel, Efficient construction of program dependence graphs, Proceedings of the 1993 ACM SIGSOFT international symposium on Software testing and analysis, p.160-170, June 28-30, 1993, Cambridge, Massachusetts, United States
• 7: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 8: J. C. Hwang, M. W. Du, and C. R. Chou. Finding program slices for recursive procedures. In In Proceedings of 12th Annual Internation Conference on Computer Software and Applications, 1988.
• 9: William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99599]
• 10: Loren Larsen , Mary Jean Harrold, Slicing object-oriented software, Proceedings of the 18th international conference on Software engineering, p.495-505, March 25-29, 1996, Berlin, Germany
• 11: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 12: Thomas Reps , Susan Horwitz , Mooly Sagiv , Genevieve Rosay, Speeding up slicing, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.11-20, December 06-09, 1994, New Orleans, Louisiana, United States
• 13: Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199462]
• 14: Erik Ruf, Context-insensitive alias analysis reconsidered, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.13-22, June 18-21, 1995, La Jolla, California, United States
• 15: Saurabh Sinha , Mary Jean Harrold , Gregg Rothermel, System-dependence-graph-based slicing of programs with arbitrary interprocedural control flow, Proceedings of the 21st international conference on Software engineering, p.432-441, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302675]
• 16: Raja Vallee-Rai. Soot: A Java ByteCode Optimization Framework. Master's thesis, McGill University, 1999.
• 17: Raja Vallée-Rai , Etienne Gagnon , Laurie J. Hendren , Patrick Lam , Patrice Pominville , Vijay Sundaresan, Optimizing Java Bytecode Using the Soot Framework: Is It Feasible?, Proceedings of the 9th International Conference on Compiler Construction, p.18-34, March 25-April 02, 2000
• 18: Mark Weiser. Program slicing. IEEE Transactions on Software Engineering, 10:352-357, 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs

General Terms:
Algorithms, Performance