Efficient online detection of dynamic control dependence

ABSTRACT

Capturing dynamic control dependence is critical for many dynamic program analysis such as dynamic slicing, dynamic information flow, and data lineage computation. Existing algorithms are mostly a simple runtime translation of the static definition, which fails to capture certain dynamic properties by its nature, leading to inefficiency. In this paper, we propose a novel online detection technique for dynamic control dependence. The technique is based upon a new definition, which is equivalent to the existing one in the intraprocedural case but it enables an efficient detection algorithm. The new algorithm naturally and efficiently handles interprocedural dynamic control dependence even in presence of irregular control flow. Our evaluation shows that the detection algorithm slows down program execution by a factor of 2.57, which is 2.54 times faster than the existing algorithm that was used in prior work.

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: Matthew Allen , Susan Horwitz, Slicing java programs that throw and catch exceptions, Proceedings of the 2003 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.44-54, June 07-07, 2003, San Diego, California, USA
• 3: Thomas Ball , Susan Horwitz, Slicing Programs with Arbitrary Control-flow, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.206-222, May 03-05, 1993
• 4: A. Beszedes, T. Gergely, and T. Gyimothy. Graphless dynamic dependence-based dynamic slicing algorithms. pages 21--30, Philadelphia, Pennsylvania, 2006.
• 5: Diablo binary rewriting framework. http://www.elis.ugent.be/diablo/.
• 6: 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]
• 7: 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
• 8: 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]
• 9: Sumit Kumar , Susan Horwitz, Better Slicing of Programs with Jumps and Switches, Proceedings of the 5th International Conference on Fundamental Approaches to Software Engineering, p.96-112, April 08-12, 2002
• 10: Andrew C. Myers, JFlow: practical mostly-static information flow control, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.228-241, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292561]
• 11: J. Newsome and D. Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. Technical Report CMU-CS-04-140, Carnegie Mellon University, 2004.
• 12: A. Podgurski , L. A. Clarke, A Formal Model of Program Dependences and its Implications for Software Testing, Debugging, and Maintenance, IEEE Transactions on Software Engineering, v.16 n.9, p.965-979, September 1990 [doi>10.1109/32.58784]
• 13: V. Ranganath, T. Amtoft, A. Banerjee, M. Dwyer, and J. Hatcliff. A new foundation for control-dependence and slicing for modern program structures. In ESOP 2005: The European Symposium on Programming, pages 77--93, Edinburgh, Scotland, 2005.
• 14: 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]
• 15: Saurabh Sinha , Mary Jean Harrold , Gregg Rothermel, Interprocedural control dependence, ACM Transactions on Software Engineering and Methodology (TOSEM), v.10 n.2, p.209-254, April 2001 [doi>10.1145/367008.367022]
• 16: Neil Vachharajani , Matthew J. Bridges , Jonathan Chang , Ram Rangan , Guilherme Ottoni , Jason A. Blome , George A. Reis , Manish Vachharajani , David I. August, RIFLE: An Architectural Framework for User-Centric Information-Flow Security, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.243-254, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.31]
• 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: M. Zhang, X. Zhang, X. Zhang, and S. Prabhakar. Tracing lineage beyond relational operators. Technical report, Purdue University, 2007.
• 20: Xiangyu Zhang , Rajiv Gupta, Matching execution histories of program versions, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 21: 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
• 22: Xiangyu Zhang , Haifeng He , Neelam Gupta , Rajiv Gupta, Experimental evaluation of using dynamic slices for fault location, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.33-42, September 19-21, 2005, Monterey, California, USA [doi>10.1145/1085130.1085135]
• 23: Xiangyu Zhang , Sriraman Tallam , Neelam Gupta , Rajiv Gupta, Towards locating execution omission errors, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA

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: Testing tools (e.g., data generators, coverage testing); Tracing
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Debuggers

General Terms:
Algorithms, Measurement, Reliability

Keywords:
dynamic control dependence, dynamic information flow, dynamic post-dominance, dynamic program slicing, irregular control flow