Relational queries over program traces

ABSTRACT

Instrumenting programs with code to monitor runtime behavior is a common technique for profiling and debugging. In practice, instrumentation is either inserted manually by programmers, or automatically by specialized tools that monitor particular properties. We propose Program Trace Query Language (PTQL), a language based on relational queries over program traces, in which programmers can write expressive, declarative queries about program behavior. We also describe our compiler, Partiqle. Given a PTQL query and a Java program, Partiqle instruments the program to execute the query on-line. We apply several PTQL queries to a set of benchmark programs, including the Apache Tomcat Web server. Our queries reveal significant performance bugs in the jack SpecJVM98 benchmark, in Tomcat, and in the IBM Java class library, as well as some correct though uncomfortably subtle code in the Xerces XML parser. We present performance measurements demonstrating that our prototype system has usable performance.

REFERENCES

• 1: Chris Allan , Pavel Avgustinov , Aske Simon Christensen , Laurie Hendren , Sascha Kuzins , Ondřej Lhoták , Oege de Moor , Damien Sereni , Ganesh Sittampalam , Julian Tibble, Adding trace matching with free variables to AspectJ, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 2: Apache tomcat. project home page at http://jakarta.apache.org/tomcat/.
• 3: H. Barringer, A. Goldberg, K. Havelund, and K. Sen. Rule-based runtime verification. In Proceedings of the 4th International Workshop on Runtime Verification (RV'04), 2004.
• 4: Peter C. Bates, Debugging heterogeneous distributed systems using event-based models of behavior, ACM Transactions on Computer Systems (TOCS), v.13 n.1, p.1-31, Feb. 1995 [doi>10.1145/200912.200913]
• 5: Object Modeling with the OCL, The Rationale behind the Object Constraint Language, January 2002
• 6: Eclipse. Project page at http://www.eclipse.org/.
• 7: Eclipse technology - EMF project. Project page at http://www.eclipse.org/emf/.
• 8: Michael Dean Ernst , David Notkin, Dynamically discovering likely program invariants, 2000
• 9: B. Finkbeiner, S. Sankaranarayanan, and H. Sipma. Collecting statistics over runtime executions. In Proceedings of the 2nd International Workshop on Runtime Verification (RV'02), Electronic Notes in Theoretical Computer Science, Elsevier Science, volume 70, 2002.
• 10: German S. Goldszmidt , Shaula Yemini, High-level language debugging for concurrent programs, ACM Transactions on Computer Systems (TOCS), v.8 n.4, p.311-336, Nov. 1990 [doi>10.1145/128733.128737]
• 11: Sudheendra Hangal , Monica S. Lam, Tracking down software bugs using automatic anomaly detection, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581377]
• 12: Eclipse technology - Hyades project. Project page at http://www.eclipse.org/hyades/.
• 13: Java 2 Platform, Standard Edition, v 1.4.2 API Specification. http://java.sun.com/j2se/1.4.2/docs/api/.
• 14: Gregor Kiczales , Erik Hilsdale , Jim Hugunin , Mik Kersten , Jeffrey Palm , William G. Griswold, An Overview of AspectJ, Proceedings of the 15th European Conference on Object-Oriented Programming, p.327-353, June 18-22, 2001
• 15: Moonjoo Kim , Sampath K. Kannan , Insup Lee, Information extraction for run-time formal analysis, 2001
• 16: I. Lee, S. Kannan, M. Kim, O. Sokolsky, and M. Viswanathan. Runtime assurance based on formal specifications. In In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 1999.
• 17: Raimondas Lencevicius , Urs Hölzle , Ambuj K. Singh, Query-based debugging of object-oriented programs, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.304-317, October 05-09, 1997, Atlanta, Georgia, United States
• 18: Yingsha Liao, An automatic programming approach to high level program monitoring and measuring, University of Southern California, Los Angeles, CA, 1992
• 19: Yingsha Liao , Donald Cohen, A Specificational Approach to High Level Program Monitoring and Measuring, IEEE Transactions on Software Engineering, v.18 n.11, p.969-978, November 1992 [doi>10.1109/32.177366]
• 20: 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
• 21: Ben Liblit , Mayur Naik , Alice X. Zheng , Alex Aiken , Michael I. Jordan, Scalable statistical bug isolation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 22: David C. Luckham, Rapide: a language and toolset for simulation of distributed systems by partial orderings of events, Proceedings of the DIMACS workshop on Partial order methods in verification, p.329-357, February 1997, Princeton, New Jersey, United States
• 23: Darko Marinov , Robert O'Callahan, Object equality profiling, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 24: Michael Martin , Benjamin Livshits , Monica S. Lam, Finding application errors and security flaws using PQL: a program query language, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 25: K. Ostermann, M. Mezini, and C. Bockisch. Expressive pointcuts for increased modularity. In European Conference on Object-Oriented Programming (ECOOP), Springer LNCS, 2005, 2005.
• 26: Specjvm98 benchmarks. Information available at http://www.specbench.org/osg/jvm98/.
• 27: Robert J. Walker , Kevin Viggers, Implementing protocols via declarative event patterns, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 28: WebSphere application server development best practices for performance and scalability. White paper available from http://www-3.ibm.com/software/webservers/appserv/ws_bestpractices.pdf, Sept. 2000.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

General Terms:
Languages, Measurement, Performance

Keywords:
PTQL, partiqle, program trace query language, relational