An improved slicer for Java

ABSTRACT

We present an improved slicing algorithm for Java. The best algorithm known so far, first presented in [11], is not always precise if nested objects are used as actual parameters. The new algorithm presented in this paper always generates correct and precise slices, but is more expensive in general.We describe the algorithms and their treatment of objects as parameters. In particular, we present a new, safe criterion for termination of unfolding nested parameter objects. We then compare the two algorithms by providing measurements for a benchmark of Java and JavaCard programs.

REFERENCES

• 1: C. S. Ananian. The static single information form. Master's thesis, MIT, September 1999. Tech. Report MIT-LCS-TR-801.
• 2: P. Bieber, J. Cazin, A. E. Marouani, P. Girard, J.-L. Lanet, V. Wiels, and G. Zanon. The PACAP prototype: a tool for detecting Java Card illegal flow. In Java Card Forum Cannes, France, Sept. 2000.
• 3: M. B. Dwyer and J.Hatcliff. Slicing software for model construction. In Partial Evaluation and Semantic-Based Program Manipulation pages 105--118, 1999.
• 4: Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237724]
• 5: S. Horwitz , T. Reps , D. Binkley, Interprocedural slicing using dependence graphs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.35-46, June 20-24, 1988, Atlanta, Georgia, United States
• 6: G. Kovács, F. Magyar, and T. Gyimóthy. Static slicing of java programs. Technical Report TR-96-108, József Attila University, Hungary, 1996.
• 7: J. Krinke. Advanced Slicing of Sequential and Concurrent Programs PhD thesis, Univ.of Passau, Germany, 2003.
• 8: Jens Krinke, Context-sensitive slicing of concurrent programs, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 9: 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
• 10: O. Lhoták. Spark: A flexible points-to analysis framework for java. Master's thesis, McGill University, Montreal, Canada, February 2003.
• 11: D. Liang , M. J. Harrold, Slicing Objects Using System Dependence Graphs, Proceedings of the International Conference on Software Maintenance, p.358, March 16-19, 1998
• 12: Brian A. Malloy , John D. McGregor , Anand Krishnaswamy , Murali Medikonda, An extensible program representation for object-oriented software, ACM SIGPLAN Notices, v.29 n.12, p.38-47, Dec. 1994 [doi>10.1145/193209.193218]
• 13: Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to and side-effect analyses for Java, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 14: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• 15: 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
• 16: Torsten Robschink , Gregor Snelting, Efficient path conditions in dependence graphs, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581398]
• 17: A. Sabelfeld and A. Myers. Language-based information-flow security. IEEE Journal on Selected Areas in Communications 21(1), January 2003.
• 18: G.Snelting, T. Robschink, and J. Krinke. Efficient path conditions in dependence graphs for software safety analysis. Submitted for publication, 2003.
• 19: T. Teitelbaum. Code surfer user guide and reference. Technical report, Gramma Tech Product Documentation, 2001. http://www.grammatech.com/csurf-doc/manual.html.
• 20: F. Tip. A survey of program slicing techniques. Journal of Programming Languages 3(3):121--189, Sept. 1995.
• 21: Frank Tip , Jens Palsberg, Scalable propagation-based call graph construction algorithms, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.281-293, October 2000, Minneapolis, Minnesota, United States
• 22: Paolo Tonella , Giuliano Antoniol , Roberto Fiutem , Ettore Merlo, Flow insensitive C++ pointers and polymorphism analysis and its application to slicing, Proceedings of the 19th international conference on Software engineering, p.433-443, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253371]
• 23: N. Walkinshaw, M.Roper, and M. Wood. The java system dependence graph. In SCAM 2003.
• 24: Jianjun Zhao, Dependence Analysis of Java Bytecode, 24th International Computer Software and Applications Conference, p.486-491, October 25-28, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Algorithms

Keywords:
Java, object trees, static program slicing