Cost and precision tradeoffs of dynamic data slicing algorithms

ABSTRACT

Dynamic slicing algorithms are used to narrow the attention of the user or an algorithm to a relevant subset of executed program statements. Although dynamic slicing was first introduced to aid in user level debugging, increasingly applications aimed at improving software quality, reliability, security, and performance are finding opportunities to make automated use of dynamic slicing. In this paper we present the design and evaluation of three precise dynamic data slicing algorithms called the full preprocessing (FP), no preprocessing (NP) and limited preprocessing (LP) algorithms. The algorithms differ in the relative timing of constructing the dynamic data dependence graph and its traversal for computing requested dynamic data slices. Our experiments show that the LP algorithm is a fast and practical precise data slicing algorithm. In fact we show that while precise data slices can be orders of magnitude smaller than imprecise dynamic data slices, for small number of data slicing requests, the LP algorithm is faster than an imprecise dynamic data slicing algorithm proposed by Agrawal and Horgan.

REFERENCES

• 1: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.246-256, June 1990, White Plains, New York, United States
• 2: Hiralal Agrawal , Richard A. Demillo , Eugene H. Spafford, Debugging with dynamic slicing and backtracking, Software—Practice & Experience, v.23 n.6, p.589-616, June 1993 [doi>10.1002/spe.4380230603]
• 3: Csaba Faragó, Union Slices for Program Maintenance, Proceedings of the International Conference on Software Maintenance (ICSM'02), p.12, October 03-06, 2002
• 4: Árpád Beszedes , Tamás Gergely , Zsolt Mihály Szabó , Janos Csirik , Tibor Gyimothy, Dynamic Slicing Method for Maintenance of Large C Programs, Proceedings of the Fifth European Conference on Software Maintenance and Reengineering, p.105, March 14-16, 2001
• 5: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Distributed Slicing and Partial Re-execution for Distributed Programs, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.497-511, August 03-05, 1992
• 6: Duesterwald, E., Gupta, R., and Soffa, M. L. 1992b. Rigorous data flow testing through output influences. In Proceedings of the 2nd Irvine Software Symposium. 131--145.
• 7: John Field , G. Ramalingam , Frank Tip, Parametric program slicing, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.379-392, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199534]
• 8: Neelam Gupta , Praveen Rao, Program Execution-Based Module Cohesion Measurement, Proceedings of the 16th IEEE international conference on Automated software engineering, p.144, November 26-29, 2001
• 9: Rajiv Gupta , Mary Lou Soffa, Hybrid slicing: an approach for refining static slices using dynamic information, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.29-40, October 12-15, 1995, Washington, D.C., United States
• 10: Pre/Post Conditioned Slicing, Proceedings of the IEEE International Conference on Software Maintenance (ICSM'01), p.138, November 07-09, 2001
• 11: Hoffner, T. 1995. Evaluation and comparison of program slicing tools. Tech. Rep., Dept. of Computer and Information Science, Linkoping University, Sweden.
• 12: Kamkar, M. 1993. Interprocedural dynamic slicing with applications to debugging and testing. Ph.D. dissertation, Linkoping University, Sweden.
• 13: B. Korel , J. Laski, Dynamic program slicing, Information Processing Letters, v.29 n.3, p.155-163, October 26, 1988 [doi>10.1016/0020-0190(88)90054-3]
• 14: Korel, B. and Rilling, J. 1997. Application of dynamic slicing in program debugging. In Proceedings of the Automated and Algorithmic Debugging. 43--59.
• 15: Bogdan Korel , Satish Yalamanchili, Forward computation of dynamic program slices, Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, p.66-79, August 17-19, 1994, Seattle, Washington, United States [doi>10.1145/186258.186514]
• 16: Markus Mock , Darren C. Atkinson , Craig Chambers , Susan J. Eggers, Improving program slicing with dynamic points-to data, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587062]
• 17: Akira Nishimatsu , Minoru Jihira , Shinji Kusumoto , Katsuro Inoue, Call-mark slicing: an efficient and economical way of reducing slice, Proceedings of the 21st international conference on Software engineering, p.422-431, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302674]
• 18: Sazeides, Y. 2003. Instruction-isomorphism in program execution. In Proceedings of the 1st Value Prediction Workshop.
• 19: Tip, F. 1995. A survey of program slicing techniques. J. Prog. Lang. 3, 3 (Sept.), 121--189.
• 20: G. A. Venkatesh, The semantic approach to program slicing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.107-119, June 24-28, 1991, Toronto, Ontario, Canada
• 21: G. A. Venkatesh, Experimental results from dynamic slicing of C programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.197-216, March 1995 [doi>10.1145/201059.201062]
• 22: Mark David Weiser, Program slices: formal, psychological, and practical investigations of an automatic program abstraction method, 1979
• 23: Weiser, M. 1982. Program slicing. IEEE Trans. Softw. Eng. SE-10, 4, 352--357.
• 24: Xiangyu Zhang , Rajiv Gupta, Cost effective dynamic program slicing, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 25: Xiangyu Zhang , Rajiv Gupta , Youtao Zhang, Efficient Forward Computation of Dynamic Slices Using Reduced Ordered Binary Decision Diagrams, Proceedings of the 26th International Conference on Software Engineering, p.502-511, May 23-28, 2004
• 26: Craig B. Zilles , Gurindar S. Sohi, Understanding the backward slices of performance degrading instructions, Proceedings of the 27th annual international symposium on Computer architecture, p.172-181, June 2000, Vancouver, British Columbia, Canada
• 27: The Trimaran Compiler Research Infrastructure. 1997. Tutorial Notes. http://www.trimaran.org.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Debuggers

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing); Tracing; Debugging aids

General Terms:
Algorithms, Measurement, Performance

Keywords:
Program slicing, data dependences, debugging, pointer references