Semantics-aware trace analysis

ABSTRACT

As computer systems continue to become more powerful and complex, so do programs. High-level abstractions introduced to deal with complexity in large programs, while simplifying human reasoning, can often obfuscate salient program properties gleaned from automated source-level analysis through subtle (often non-local) interactions. Consequently, understanding the effects of program changes and whether these changes violate intended protocols become difficult to infer. Refactorings, and feature additions, modifications, or removals can introduce hard-to-catch bugs that often go undetected until many revisions later.

To address these issues, this paper presents a novel dynamic program analysis that builds a semantic view of program executions. These views reflect program abstractions and aspects; however, views are not simply projections of execution traces, but are linked to each other to capture semantic interactions among abstractions at different levels of granularity in a scalable manner.

We describe our approach in the context of Java and demonstrate its utility to improve regression analysis. We first formalize a subset of Java and a grammar for traces generated at program execution. We then introduce several types of views used to analyze regression bugs along with a novel, scalable technique for semantic differencing of traces from different versions of the same program. Benchmark results on large open-source Java programs demonstrate that semantic-aware trace differencing can identify precise and useful details about the underlying cause for a regression, even in programs that use reflection, multithreading, or dynamic code generation, features that typically confound other analysis techniques.

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: Taweesup Apiwattanapong , Alessandro Orso , Mary Jean Harrold, JDiff: A differencing technique and tool for object-oriented programs, Automated Software Engineering, v.14 n.1, p.3-36, March 2007 [doi>10.1007/s10515-006-0002-0]
• 3: L. Bergroth , H. Hakonen , T. Raita, A Survey of Longest Common Subsequence Algorithms, Proceedings of the Seventh International Symposium on String Processing Information Retrieval (SPIRE'00), p.39, September 27-29, 2000
• 4: Christoph Csallner , Yannis Smaragdakis, DSD-Crasher: a hybrid analysis tool for bug finding, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146267]
• 5: Valentin Dallmeier , Thomas Zimmermann, Extraction of bug localization benchmarks from history, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321702]
• 6: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957]
• 7: Matthew Flatt , Shriram Krishnamurthi , Matthias Felleisen, Classes and mixins, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.171-183, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268961]
• 8: Liang Guo, Abhik Roychoudhury, and Tao Wang. Accurately Choosing Execution Runs for Software Fault Localization. In CC, pages 80--95, 2006.
• 9: D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
• 10: Kevin Hoffman, Patrick Eugster, and Suresh Jagannathan. RPrism: Efficient Regression Analysis Using View-Based Trace Differencing. Technical Report dynt-200811-1, Purdue University, 2008.
• 11: Atsushi Igarashi , Benjamin C. Pierce , Philip Wadler, Featherweight Java: a minimal core calculus for Java and GJ, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.3, p.396-450, May 2001 [doi>10.1145/503502.503505]
• 12: G. Kiczales, J. Lamping, A. Menhdhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-Oriented Programming. In ECOOP-97, pages 220--242, 1997.
• 13: Zhenmin Li , Lin Tan , Xuanhui Wang , Shan Lu , Yuanyuan Zhou , Chengxiang Zhai, Have things changed now?: an empirical study of bug characteristics in modern open source software, Proceedings of the 1st workshop on Architectural and system support for improving software dependability, p.25-33, October 21-21, 2006, San Jose, California [doi>10.1145/1181309.1181314]
• 14: Ben Liblit , Alex Aiken , Alice X. Zheng , Michael I. Jordan, Bug isolation via remote program sampling, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 15: Guillaume Pothier , Éric Tanter , José Piquer, Scalable omniscient debugging, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 16: Xiaoxia Ren , Fenil Shah , Frank Tip , Barbara G. Ryder , Ophelia Chesley, Chianti: a tool for change impact analysis of java programs, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 17: Maximilian Stoerzer , Barbara G. Ryder , Xiaoxia Ren , Frank Tip, Finding failure-inducing changes in java programs using change classification, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181783]
• 18: F. Tip. A Survey of Program Slicing Techniques. Journal of programming languages, 3:121--189, 1995.
• 19: 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]
• 20: Bin Xin , William N. Sumner , Xiangyu Zhang, Efficient program execution indexing, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA
• 21: 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]
• 22: Andreas Zeller , Ralf Hildebrandt, Simplifying and Isolating Failure-Inducing Input, IEEE Transactions on Software Engineering, v.28 n.2, p.183-200, February 2002 [doi>10.1109/32.988498]
• 23: 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
• 24: 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

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); Diagnostics; Tracing

General Terms:
Algorithms, Reliability

Keywords:
automated debugging, debugging aids, semantic tracing, testing tools, trace views, tracing