Experimental evaluation of using dynamic slices for fault location

ABSTRACT

Dynamic slicing algorithms have been considered to aid in debugging for many years. However, as far as we know, no detailed studies on evaluating the benefits of using dynamic slicing for detecting faulty statements in programs have been carried out. We have developed a dynamic slicing framework that uses dynamic instrumentation to efficiently collect dynamic slices and reduced ordered Binary Decision Diagrams (roBDDs) to compactly store them. We have used the above framework to implement three variants of dynamic slicing algorithms including: data slicing, full slicing, and relevant slicing algorithms. We have carried out detailed experiments to evaluate these algorithms. Our results show that full slices and relevant slices can considerably reduce the subset of program statements that need to be examined to locate faulty statements. We expect that the observations presented here will enable development of new slicing based algorithms for automated debugging.

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: Hiralal Agrawal , Joseph R. Horgan , Edward W. Krauser , Saul London, Incremental Regression Testing, Proceedings of the Conference on Software Maintenance, p.348-357, September 01, 1993
• 4: H. Agrawal, J. Horgan, S. London, and W. Wong, "Fault Localization Using Execution Slices and Dataflow Tests," 6th IEEE International Symposium on Software Reliability Engineering, pages 143--151, 1995.
• 5: Á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
• 6: Holger Cleve , Andreas Zeller, Locating causes of program failures, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062522]
• 7: Tibor Gyimóthy , Árpád Beszédes , Istán Forgács, An efficient relevant slicing method for debugging, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.303-321, September 06-10, 1999, Toulouse, France
• 8: Ralf Hildebrandt , Andreas Zeller, Simplifying failure-inducing input, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.135-145, August 21-24, 2000, Portland, Oregon, United States
• 9: Monica Hutchins , Herb Foster , Tarak Goradia , Thomas Ostrand, Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria, Proceedings of the 16th international conference on Software engineering, p.191-200, May 16-21, 1994, Sorrento, Italy
• 10: James A. Jones, Fault Localization Using Visualization of Test Information, Proceedings of the 26th International Conference on Software Engineering, p.54-56, May 23-28, 2004
• 11: M. Kamkar, "Interprocedural Dynamic Slicing with Applications to Debugging and Testing," PhD Thesis, Linkoping University, 1993.
• 12: 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]
• 13: B. Korel and J. Rilling, "Application of Dynamic Slicing in Program Debugging," 3rd International Workshop on Automatic Debugging, pages 43--58, Linkoping, Sweden, 1997.
• 14: J. Lin-Nielsen. "BuDDy, A Binary Decision Diagram Package," Department of Information Technology, Technical University of Denmark, http://www.itu.dk/research/buddy/.
• 15: H. Pan and E. H. Spafford, "Heuristics for Automatic Localization of Software Faults", Technical Report SERC-TR-116-P, Purdue University, 1992.
• 16: M. Renieris and S. Reiss, "Fault Localization with Nearest Neighbor Queries," IEEE International Conference on Automated Software Engineering, pages 30--39, 2003.
• 17: Tao Wang , Abhik Roychoudhury, Using Compressed Bytecode Traces for Slicing Java Programs, Proceedings of the 26th International Conference on Software Engineering, p.512-521, May 23-28, 2004
• 18: M. Weiser, "Program Slicing," IEEE Transactions on Software Engineering, Vol. SE-10, No. 4, pages 352--357, 1982.
• 19: Andreas Zeller, Isolating cause-effect chains from computer programs, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587053]
• 20: Xiangyu Zhang , Rajiv Gupta , Youtao Zhang, Precise dynamic slicing algorithms, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 21: 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
• 22: 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
• 23: http://www.cse.unl.edu/~galileo/sir
• 24: http://www.elis.ugent.be/diablo/
• 25: http://valgrind.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: Debugging aids; Testing tools (e.g., data generators, coverage testing); Tracing

General Terms:
Algorithms, Measurement, Reliability, Verification

Keywords:
data slice, debugging, full slice, relevant slice