Making trace monitors feasible

ABSTRACT

A trace monitor observes an execution trace at runtime; when it recognises a specified sequence of events, the monitor runs extra code. In the aspect-oriented programming community, the idea originatedas a generalisation of the advice-trigger mechanism: instead of matchingon single events (joinpoints), one matches on a sequence of events. The runtime verification community has been investigating similar mechanisms for a number of years, specifying the event patterns in terms of temporal logic, and applying the monitors to hardware and software.

In recent years trace monitors have been adapted for use with mainstream object-oriented languages. In this setting, a crucial feature is to allow the programmer to quantify over groups of related objects when expressing the sequence of events to match. While many language proposals exist for allowing such features, until now no implementation had scalable performance: execution on all but very simple examples was infeasible.

This paper rectifies that situation, by identifying two optimisations for generating feasible trace monitors from declarative specifications of the relevant event pattern. We restrict ourselves to optimisations that do not have a significant impact on compile-time: they only analyse the event pattern, and not the monitored code itself.

The first optimisation is an important improvement over an earlier proposal in [2] to avoid space leaks. The second optimisation is a form of indexing for partial matches. Such indexing needs to be very carefully designed to avoid introducing new space leaks, and the resulting data structure is highly non-trivial.

REFERENCES

• 1: The abc team. Benchmarks for Trace Monitoring. Scripts and sources to compile and run the benchmarks: http://aspectbench.org/benchmarks.
• 2: 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
• 3: AProVE. Automated Program Verification Environment. http://aprove.informatik.rwth-aachen.de/, 2006.
• 4: AspectJ Eclipse Home. The AspectJ home page. http://eclipse.org/aspectj/, 2003.
• 5: Pavel Avgustinov , Aske Simon Christensen , Laurie Hendren , Sascha Kuzins , Jennifer Lhoták , Ondřej Lhoták , Oege de Moor , Damien Sereni , Ganesh Sittampalam , Julian Tibble, Optimising aspectJ, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 6: Pavel Avgustinov, Oege de Moor, and Julian Tibble. On the semantics of trace monitoring patterns. In Runtime Verification, 2007.
• 7: Howard Barringer, Allen Goldberg, Klaus Havelund, and Koushik Sen. Rule-based runtime verification. In Fifth International Conference on Verification, Model Checking and Abstract Interpretation (VMCAI 04), volume 2937, pages 44--57. Lecture Notes in Computer Science, 2003.
• 8: Christoph Bockisch, Mira Mezini, and Klaus Ostermann. Quantifying over dynamic properties of program execution. In 2nd Dynamic Aspects Workshop (DAW05), Technical Report 05.01, pages 71--75. Research Institute for Advanced Computer Science, 2005.
• 9: Eric Bodden, Laurie Hendren, and Ondřej Lhoták. A staged static program analysis to improve the performance of runtime monitoring. In Proceedings of the European Conference on Object-Oriented Programming, Lecture Notes in Computer Science, page to appear. Springer, 2007.
• 10: Eric Bodden, Patrick Lam, and Laurie Hendren. Flow-sensitive static optimizations for runtime monitors. Technical Report abc-2007-3, abc project, 2007. http://abc.comlab.ox.ac.uk/techreports#abc-2007-3.
• 11: Feng Chen and Grigore Roşu. Towards monitoring-oriented programming: A paradigm combining specification and implementation. In Workshop on Runtime Verification (RV'03), volume 89(2) of ENTCS, pages 108--127, 2003.
• 12: Feng Chen , Grigore Roşu, Mop: an efficient and generic runtime verification framework, Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 13: María Augustina Cibrán and Bart Verheecke. Dynamic business rules for web service composition. In 2nd Dynamic Aspects Workshop (DAW05), pages 13--18, 2005.
• 14: Marcelo d'Amorim , Klaus Havelund, Event-based runtime verification of java programs, Proceedings of the third international workshop on Dynamic analysis, p.1-7, May 17-17, 2005, St. Louis, Missouri
• 15: Rémi Douence , Thomas Fritz , Nicolas Loriant , Jean-Marc Menaud , Marc Ségura-Devillechaise , Mario Südholt, An expressive aspect language for system applications with Arachne, Proceedings of the 4th international conference on Aspect-oriented software development, p.27-38, March 14-18, 2005, Chicago, Illinois [doi>10.1145/1052898.1052901]
• 16: Rémi Douence , Olivier Motelet , Mario Südholt, A Formal Definition of Crosscuts, Proceedings of the Third International Conference on Metalevel Architectures and Separation of Crosscutting Concerns, p.170-186, September 25-28, 2001
• 17: Grigore Rosu et al. JavaMOP homepage. http://fsl.cs.uiuc.edu/index.php/JavaMOP, 2007.
• 18: Stephen Fink , Eran Yahav , Nurit Dor , G. Ramalingam , Emmanuel Geay, Effective typestate verification in the presence of aliasing, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146254]
• 19: Thomas Fritz, Marc Ségura, Mario Südholt, Egon Wuchner, and Jean-Marc Menaud. An application of dynamic AOP to medical image generation. In 2nd Dynamic Aspects Workshop (DAW05), Technical Report 05.01, pages 5--12. Research Institute for Advanced Computer Science, 2005.
• 20: Erich Gamma. JHotDraw. Available from http://sourceforge.net/projects/jhotdraw, 2004.
• 21: Simon F. Goldsmith , Robert O'Callahan , Alex Aiken, Relational queries over program traces, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 22: Peter Hui and James Riely. Temporal aspects as security automata. In Foundations of Aspect-Oriented Languages (FOAL 2006), Workshop at AOSD 2006, Technical Report #06--01, pages 19--28. Iowa State University, 2006.
• 23: 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
• 24: Ramnivas Laddad. AspectJ in Action. Manning, 2003.
• 25: 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
• 26: Volker Stolz and Eric Bodden. Temporal Assertions using AspectJ. In Electronic Notes in Theoretical Computer Science, volume 144, pages 109--124, 2006.
• 27: Arie van Deursen, Leon Moonen, and Marius Marin. AJHotDraw. http://sourceforge.net/projects/ajhotdraw/, 2006.
• 28: Wim Vanderperren, Davy Suvé, María Augustina Cibrán, and Bruno De Fraine. Stateful aspects in JAsCo. In Software Composition: 4th International Workshop, volume 3628 of Lecture Notes in Computer Science. Springer, 2005.
• 29: w3c. Jigsaw. http://www.w3.org/Jigsaw/, 2006.
• 30: 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
• 31: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Experimentation, Languages, Performance

Keywords:
program analysis, program monitors, runtime verification