Memory slicing

ABSTRACT

Traditional dynamic program slicing techniques are code-centric, meaning dependences are introduced between executed statement instances, which gives rise to various problems such as space requirement is decided by execution length; dependence graphs are highly redundant so that inspecting them is labor intensive. In this paper, we propose a data-centric dynamic slicing technique, in which dependences are introduced between memory locations. Doing so, the space complexity is bounded by memory footprint instead of execution length. Moreover, presenting dependences between memory locations is often more desirable for human inspection during debugging as redundant dependences are suppressed. Our evaluation shows that the proposed technique supersedes traditional dynamic slicing techniques in terms of effectiveness and efficiency.

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: Marc Berndl , Ondrej Lhoták , Feng Qian , Laurie Hendren , Navindra Umanee, Points-to analysis using BDDs, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 3: Á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
• 4: Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, August 1986 [doi>10.1109/TC.1986.1676819]
• 5: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• 6: Diablo binary rewriting framework. http://www.elis.ugent.be/diablo/.
• 7: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 8: Mark Gabel , Zhendong Su, Symbolic mining of temporal specifications, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368096]
• 9: 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]
• 10: J. Lind-Nielsen. BuDDy, a binary decision diagram package. http://buddy.sourceforge.net.
• 11: S. Lu, Z. Li, F. Qin, L. Tan, P. Zhou, and Y. Zhou. Bugbench: a benchmark for evaluating bug detection tools. In Workshop on the Evaluation of Software Defect Detection Tools, Chicago, Illinois, 2005.
• 12: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 13: Feng Qin , Cheng Wang , Zhenmin Li , Ho-seop Kim , Yuanyuan Zhou , Youfeng Wu, LIFT: A Low-Overhead Practical Information Flow Tracking System for Detecting Security Attacks, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.135-148, December 09-13, 2006 [doi>10.1109/MICRO.2006.29]
• 14: F. Tip. A Survey of Program Slicing Techniques. In Journal of Program Languages, 121--189, 1995.
• 15: Mandana Vaziri , Frank Tip , Julian Dolby, Associating synchronization constraints with data in an object-oriented language, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.334-345, January 11-13, 2006, Charleston, South Carolina, USA
• 16: Tao Wang , Abhik Roychoudhury, Hierarchical dynamic slicing, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273494]
• 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: Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States
• 19: J. Whaley and D. Avots and M. Carbin and M. S. Lam. Using Datalog with Binary Decision Diagrams for Program Analysis. In Proceedings of Programming Languages and Systems: Third Asian Symposium, 2005.
• 20: Bin Xin , Xiangyu Zhang, Efficient online detection of dynamic control dependence, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273489]
• 21: Lihua Yuan , Jianning Mai , Zhendong Su , Hao Chen , Chen-Nee Chuah , Prasant Mohapatra, FIREMAN: A Toolkit for FIREwall Modeling and ANalysis, Proceedings of the 2006 IEEE Symposium on Security and Privacy, p.199-213, May 21-24, 2006 [doi>10.1109/SP.2006.16]
• 22: Xiangyu Zhang , Rajiv Gupta, Fault location via precise dynamic slicing, University of Arizona, Tucson, AZ, 2006
• 23: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Debuggers

General Terms:
Algorithms, Measurement, Reliability

Keywords:
data-centric slicing, dynamic program slicing, fault localization, memory dependence graph