Article

Making trace monitors feasible

Authors:

Pavel Avgustinov,

Oege de MoorAuthors Info & Claims

OOPSLA '07: Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications

Pages 589 - 608

https://doi.org/10.1145/1297027.1297070

Published: 21 October 2007 Publication History

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, and Julian Tibble. Adding Trace Matching with Free Variables to AspectJ. In Object-Oriented Programming, Systems, Languages and Applications, pages 345--364. ACM Press, 2005.

Digital Library

[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, and Julian Tibble. Optimising AspectJ. In Programming Language Design and Implementation (PLDI), pages 117--128. ACM Press, 2005.

Digital Library

[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.

Digital Library

[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 and Grigore Roşu. Mop: An efficient and generic runtime verification framework. In David Bacon, editor, Proceedings of OOPSLA 2007, 2007.

Digital Library

[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 and Klaus Havelund. Event-based runtime verification of java programs. In WODA'05: Proceedings of the third international workshop on Dynamic analysis, pages 1--7. ACM Press, 2005.

Digital Library

[15]

Rémi Douence, Thomas Fritz, Nicolas Loriant, Jean-Marc Menaud, Marc Ségura, and Mario Südholt. An expressive aspect language for system applications with arachne. In Aspect-Oriented Software Development, pages 27--38. ACM Press, 2005.

Digital Library

[16]

Rémi Douence, Olivier Motelet, and Mario Südholt. A formal definition of crosscuts. In Akinori Yonezawa and Satoshi Matsuoka, editors, Reflection 2001, volume 2192 of Lecture Notes in Computer Science, pages 170--186. Springer, 2001.

Digital Library

[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, and Emmanuel Geay. Effective typestate verification in the presence of aliasing. In ISSTA'06: Proceedings of the 2006 international symposium on Software testing and analysis, pages 133--144, New York, NY, USA, 2006. ACM Press.

Digital Library

[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 Goldsmith, Robert O'Callahan, and Alex Aiken. Relational queries over program traces. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications, pages 385--402. ACM Press, 2005.

Digital Library

[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, and William G. Griswold. An overview of AspectJ. In J.Lindskov Knudsen, editor, European Conference on Object-Oriented Programming, volume 2072 of Lecture Notes in Computer Science, pages 327--353. Springer, 2001.

Digital Library

[24]

Ramnivas Laddad. AspectJ in Action. Manning, 2003.

[25]

Michael Martin, Benjamin Livshits, and Monica S. Lam. Finding application errors using PQL: a program query language. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications, pages 365--383. ACM Press, 2005.

Digital Library

[26]

Volker Stolz and Eric Bodden. Temporal Assertions using AspectJ. In Electronic Notes in Theoretical Computer Science, volume 144, pages 109--124, 2006.

Digital Library

[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.

Digital Library

[29]

w3c. Jigsaw. http://www.w3.org/Jigsaw/, 2006.

[30]

Robert Walker and Kevin Viggers. Implementing protocols via declarative event patterns. In ACM Sigsoft International Symposium on Foundations of Software Engineering (FSE-12), pages 159--169. ACM Press, 2004.

Digital Library

[31]

Ian H. Witten and Eibe Frank. Data Mining: Practical Machine Learning Tools and Techniques with Java implementations. Morgan Kaufmann Publishers, 2000.

Digital Library

Cited By

Andrici CCiobâcă ȘHriţcu CMartínez GRivas ETanter ÉWinterhalter T(2024)Securing Verified IO Programs Against Unverified Code in F*Proceedings of the ACM on Programming Languages10.1145/36329168:POPL(2226-2259)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632916
Allabadi GDhar ABashir APurandare R(2018)METIS: Resource and Context-Aware Monitoring of Finite State PropertiesRuntime Verification10.1007/978-3-030-03769-7_10(167-186)Online publication date: 8-Nov-2018
https://doi.org/10.1007/978-3-030-03769-7_10
Chen Z(2017)Parametric runtime verification is NP-complete and coNP-completeInformation Processing Letters10.1016/j.ipl.2017.02.006123:C(14-20)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1016/j.ipl.2017.02.006
Show More Cited By

Index Terms

Making trace monitors feasible
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Making trace monitors feasible
Proceedings of the 2007 OOPSLA conference

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: ...
Programming event monitors
Abstract
Specification languages for runtime verification are commonly rooted in formal languages, such as temporal logic, automata, or regular expressions. We argue that, for practical purposes, specification languages for monitoring should allow language ...
Overhead-Aware Deployment of Runtime Monitors
Runtime Verification
Abstract
One important issue needed to be handled when applying runtime verification is the time overhead introduced by online monitors. According to how monitors are deployed with the system to be monitored, the overhead may come from the execution of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '07: Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications

October 2007

728 pages

ISBN:9781595937865

DOI:10.1145/1297027

General Chair:
Richard P. Gabriel
IBM Research, USA
,
Program Chairs:
David F. Bacon
IBM Research, USA
,
Cristina Videira Lopes
University of California, Irvine, USA
,
Guy L. Steele
Sun Labs, USA

ACM SIGPLAN Notices Volume 42, Issue 10
Proceedings of the 2007 OOPSLA conference
October 2007
686 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1297105
Issue’s Table of Contents

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

OOPSLA07

Sponsor:

OOPSLA07: ACM SIGPLAN Object Oriented Programming Systems and Applications Conference

October 21 - 25, 2007

Quebec, Montreal, Canada

Acceptance Rates

OOPSLA '07 Paper Acceptance Rate 33 of 156 submissions, 21%;

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

95
Total Citations
View Citations
690
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)2

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Andrici CCiobâcă ȘHriţcu CMartínez GRivas ETanter ÉWinterhalter T(2024)Securing Verified IO Programs Against Unverified Code in F*Proceedings of the ACM on Programming Languages10.1145/36329168:POPL(2226-2259)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632916
Allabadi GDhar ABashir APurandare R(2018)METIS: Resource and Context-Aware Monitoring of Finite State PropertiesRuntime Verification10.1007/978-3-030-03769-7_10(167-186)Online publication date: 8-Nov-2018
https://doi.org/10.1007/978-3-030-03769-7_10
Chen Z(2017)Parametric runtime verification is NP-complete and coNP-completeInformation Processing Letters10.1016/j.ipl.2017.02.006123:C(14-20)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1016/j.ipl.2017.02.006
Dimoulas CNew MFindler RFelleisen M(2016)Oh Lord, please don't let contracts be misunderstood (functional pearl)ACM SIGPLAN Notices10.1145/3022670.295193051:9(117-131)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/3022670.2951930
Dimoulas CNew MFindler RFelleisen MGarrigue JKeller GSumii E(2016)Oh Lord, please don't let contracts be misunderstood (functional pearl)Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming10.1145/2951913.2951930(117-131)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/2951913.2951930
Pezzé MWuttke J(2016)Model-driven generation of runtime checks for system propertiesInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-014-0325-218:1(1-19)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s10009-014-0325-2
Chen ZWang ZZhu YXi HYang Z(2016)Parametric Runtime Verification of C ProgramsProceedings of the 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems - Volume 963610.1007/978-3-662-49674-9_17(299-315)Online publication date: 2-Apr-2016
https://dl.acm.org/doi/10.1007/978-3-662-49674-9_17
Legunsen OMarinov DRoşu GBertolino ACanfora GElbaum S(2015)Evolution-aware monitoring-oriented programmingProceedings of the 37th International Conference on Software Engineering - Volume 210.5555/2819009.2819118(615-618)Online publication date: 16-May-2015
https://dl.acm.org/doi/10.5555/2819009.2819118
Huang JLuo QRosu GBertolino ACanfora GElbaum S(2015)GPredictProceedings of the 37th International Conference on Software Engineering - Volume 110.5555/2818754.2818856(847-857)Online publication date: 16-May-2015
https://dl.acm.org/doi/10.5555/2818754.2818856
Huang JLuo QRosu G(2015)GPredict: Generic Predictive Concurrency Analysis2015 IEEE/ACM 37th IEEE International Conference on Software Engineering10.1109/ICSE.2015.96(847-857)Online publication date: May-2015
https://doi.org/10.1109/ICSE.2015.96
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents