The documents linked from this page are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. Those works owned by other copyright holders may not be reposted without the explicit written permission of the copyright holder.
Authors:
Eric Bodden (McGill University), Feng Chen (Univ. of Illinois at UC) and Grigore Rosu (Univ. of Illinois at UC)
AOSD 09, March 2009, Charlottesville, VAAbstract
Many aspects for runtime monitoring are history-based: they contain pieces of advice that execute conditionally, based on the observed execution history. History-based aspects are notorious for causing high runtime overhead. Compilers can apply powerful optimizations to history-based aspects using domain knowledge. Unfortunately, current aspect languages like AspectJ impede optimizations, as they provide no means to express this domain knowledge.
In this paper we present dependent advice, a novel AspectJ language extension. A dependent advice contains dependency annotations that preserve crucial domain knowledge: a dependent advice needs to execute only when its dependencies are fulfilled. Optimizations can exploit this knowledge: we present a whole-program analysis that removes advice-dispatch code from program locations at which an advice's dependencies cannot be fulfilled.
Programmers often opt to have history-based aspects generated automatically, from formal specifications from model-driven development or runtime monitoring. As we show using code-generation tools for two runtime-monitoring approaches, tracematches and JavaMOP, such tools can use knowledge contained in the specification to automatically generate dependency annotations as well.
Our extensive evaluation using the DaCapo benchmark suite shows that the use of dependent advice can significantly lower, sometimes even completely eliminate, the runtime overhead caused by history-based aspects, independently of the specification formalism.
An extended Technical Report is available here. You can find our benchmarks for this paper on this webpage.
Authors:
Eric Bodden (McGill University), Patrick Lam (University of Waterloo) and Laurie Hendren (McGill University)
FSE 08, November 2008, Atlanta, GAAbstract
Runtime monitoring allows programmers to validate, for instance, the proper use of application interfaces. Given a property specification, a runtime monitor tracks appropriate runtime events to detect violations and possibly execute recovery code. Although powerful, runtime monitoring inspects only one program run at a time and so may require many program runs to find errors. Therefore, in this paper, we present ahead-of-time techniques that can (1) prove the absence of property violations on all program runs, or (2) flag locations where violations are likely to occur.
Our work focuses on tracematches, an expressive runtime monitoring notation for reasoning about groups of correlated objects. We describe a novel flow-sensitive static analysis for analyzing monitor states. Our abstraction captures both positive information (a set of objects could be in a particular monitor state) and negative information (the set is known not to be in a state). The analysis resolves heap references by combining the results of three points-to and alias analyses. We also propose a machine learning phase to filter out likely false positives.
We applied a set of 13 tracematches to the DaCapo benchmark suite and SciMark2. Our static analysis rules out all potential points of failure in 50% of the cases, and 75% of false positives on average. Our machine learning algorithm correctly classifies the remaining potential points of failure in all but three of 461 cases. The approach revealed defects and suspicious code in three benchmark programs.
This paper won an ACM SIGSOFT Distinguished Paper Award at ISSTA 2008.
Authors:
Eric Bodden (McGill University) and Klaus Havelund (California Institute of Technology)
ISSTA 08, July 2008, Seattle, WANote: This paper was updated on 19/05/2008 to accommodate the page limit of 11 pages. There now exists an extended technical report version of this paper.
Abstract
Programming errors occur frequently in large software systems, and even more so if these systems are concurrent. In the past researchers have developed specialized programs to aid programmers detecting concurrent programming errors such as deadlocks, livelocks, starvation and data races.
In this work we propose a language extension to the aspect-oriented programming language AspectJ, in the form of three new pointcuts, lock(), unlock() and maybeShared(). These pointcuts allow programmers to monitor program events where locks are granted or handed back, and where values are accessed that may be shared amongst multiple Java threads. We decide thread-locality using a static thread-local objects analysis developed by others. Using the three new primitive pointcuts, researchers can directly implement efficient monitoring algorithms to detect concurrent programming errors online. As an example, we expose a new algorithm which we call Racer, an adoption of the well-known Eraser algorithm to the memory model of Java.
We implemented the new pointcuts as an extension to the AspectBench Compiler, implemented the Racer algorithm using this language extension and then applied the algorithm to the NASA K9 Rover Executive. Our experiments proved our implementation very effective. In the Rover Executive Racer finds 70 data races. Only one of these races was previously known. We further applied the algorithm to two other multi-threaded programs written by Computer Science researchers, in which we found races as well.
Download our implementation of Racer, RacerAJ here.
Authors:
Pavel Avgustinov, Torbjorn Ekman, Julian Tibble (Oxford University)
AOSD 2008, March 2008, Brussels, BelgiumAbstract
We have reimplemented the frontend of the extensible AspectBench Compiler for AspectJ, using the aspect-oriented meta-compiler JastAdd. The original frontend extends Java with AspectJ and an additional set of pointcuts in a modular fashion. In this paper we give a detailed comparison of both approaches and show a number of advantages of using JastAdd: the implementation is half the size, twice as fast, concerns are better localised, extensions are composable, and computations are automatically scheduled.
JastAdd provides a very constrained form of static AOP where only inter-type declarations and method execution interception are supported. However, additional modularisation mechanisms from the compiler construction community are supported in the form of demand-driven evaluation and attribute grammars. Our implementation would not have benefited from a richer pointcut language, while both demand-driven evaluation and declarative attributes were essential in enabling composable extensions and flexible modularisation.
We believe that the AOP community at large can benefit from acknowledging demand-driven evaluation as an important modularisation mechanism. Also, reference attribute grammars enhance the extensible implementation of graph-based computations that rely on context-sensitive information.
Authors:
Eric Bodden, Reehan Shaikh and Laurie Hendren (McGill University)
AOSD 2008, March 2008, Brussels, BelgiumNote: There exists an extended technical report version of this paper.
Abstract
The relationships between objects in an object-oriented program are an essential property of the program's design and implementation. Two previous approaches to implement relationships with aspects were association aspects, an AspectJ-based language extension, and the relationship aspects library. While those approaches greatly ease software development, we believe that they are not general enough. For instance, the library approach only works for binary relationships, while the language extension does not allow for the association of primitive values or values from non-weavable classes.
Hence, in this work we propose a generalized alternative implementation via a direct reduction to tracematches, a language feature for executing an advice after having matched a sequence of events.
This new implementation scheme yields multiple benefits. Firstly, our implementation is more general than existing ones, avoiding most previous limitations. It also yields a new language construct, relational tracematches.
We provide an efficient implementation based on the AspectBench Compiler, along with test cases and microbenchmarks. Our empirical studies showed that our implementation, when compared to previous approaches, uses a similar memory footprint with no leaking, but the generality of our approach does lead to some runtime overhead. We believe that our implementation can provide a solid foundation for future research.
The benchmarks from the paper can be downloaded here, along with our initial implementation. Relational aspects will be part of our next abc release.
Authors:
Pavel Avgustinov, Julian Tibble and Oege de Moor (Oxford University)
OOPSLA 2007, October 2007, Montreal, CanadaAbstract
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 originated as a generalisation of the advice-trigger mechanism: instead of matching on 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 [1] 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.
Note: The tracematch extension has been part of the standard abc release since version 1.1.0. The optimisations presented in this paper are included in abc version 1.2.1. For more details, see the extensions page.
Authors: Eric Bodden, Laurie Hendren, Patrick Lam, Ondřej Lhoták and Nomair A. Naeem
Date: September 2007
7th workshop on Runtime Verification at the 6th International Conference on Aspect-Oriented Software Development, March 13th 2007, Vancouver, Canada. To appear in LNCS.
Abstract
Perfect pre-deployment test coverage is notoriously difficult to achieve for large applications. With enough end users, many more test cases will be encountered during an application's deployment than during testing. The use of runtime verification after deployment would enable developers to detect and report on unexpected situations. Unfortunately, the prohibitive performance cost of runtime monitors prevents their use in deployed code.
In this work we study the feasibility of collaborative runtime verification, a verification approach which distributes the burden of runtime verification onto multiple users. Each user executes a partially instrumented program and therefore suffers only a fraction of the instrumentation overhead.
We focus on runtime verification using tracematches. Tracematches are a specification formalism that allows users to specify runtime verification properties via regular expressions with free variables over the dynamic execution trace. We propose two techniques for soundly partitioning the instrumentation required for tracematches: spatial partitioning, where different copies of a program monitor different program points for violations, and temporal partitioning, where monitoring is switched on and off over time. We evaluate the relative impact of partitioning on a user's runtime overhead by applying each partitioning technique to a collection of benchmarks that would otherwise incur significant instrumentation overhead.
Our results show that spatial partitioning almost completely eliminates runtime overhead (for any particular benchmark copy) on many of our test cases, and that temporal partitioning scales well and provides runtime verification on a ``pay as you go'' basis.
The benchmarks for this paper can be downloaded here.
Authors: Eric Bodden, Laurie Hendren, Ondřej Lhoták
Date: July 2007
21st European Conference on Object-Oriented Programming, July 30th - August 3rd 2007, Berlin, Germany
There exists an extended Technical Report version of this paper: abc-2007-2.
Abstract
In runtime monitoring, a programmer specifies a piece of code to execute when a trace of events occurs during program execution. Our work is based on tracematches, an extension to AspectJ, which allows programmers to specify traces via regular expressions with free variables. In this paper we present a staged static analysis which speeds up trace matching by reducing the required runtime instrumentation.
The first stage is a simple analysis that rules out entire tracematches, just based on the names of symbols. In the second stage, a points-to analysis is used, along with a flow-insensitive analysis that eliminates instrumentation points with inconsistent variable bindings. In the third stage the points-to analysis is combined with a flow-sensitive analysis that also takes into consideration the order in which the symbols may execute.
To examine the effectiveness of each stage, we experimented with a set of nine tracematches applied to the DaCapo benchmark suite. We found that about 25% of the tracematch/benchmark combinations had instrumentation overheads greater than 10%. In these cases the first two stages work well for certain classes of tracematches, often leading to significant performance improvements. Somewhat surprisingly, we found the third, flow-sensitive, stage did not add any improvements.
Errata
When working on Dependent Advice, a generalization of the ideas presented in this paper, we discovered a conceptual flaw. In this ECOOP paper we state that it is sound to not regard edges generated by Kleene-* sub-expressions when generating shadow groups. This is equivalent to regarding only such acceptings paths through the tracematch automaton that visit no state more than once. In fact, this is unsound: as we show in the Technical Report on Dependent Advice, one has to regard all such paths that visit no state more than twice. As of July 2008, abc implements the correct semantics (based on dependent advice). Note that this error does not invalidate any of our benchmark results, because none of the tracematches used in our benchmarks would trigger this bug.
The benchmarks for this paper can be downloaded here.
Authors: Pavel Avgustinov, Eric Bodden, Elnar Hajiyev, Laurie Hendren, Ondřej Lhoták, Oege de Moor, Neil Ongkingco, Damien Sereni, Ganesh Sittampalam, Julian Tibble, Mathieu Verbaere
Date: August 2006
Invited paper at FATES/RV 2006, Seattle, USA, August 2006, published in K. Havelund et al (Eds): FATES/RV 2006, LNCS 4262, pp. 20-39, 2006.
Abstract
A trace monitor observes the sequence of events in a system, and takes appropriate action when a given pattern occurs in that sequence. Aspect-oriented programming provides a convenient framework for writing such trace monitors.
We provide a brief introduction to aspect-oriented programming in AspectJ. AspectJ only provides support for triggering extra code with single events, and we present a new language feature (named tracematches) that allows one to directly express patterns that range over the whole current trace. Implementing this feature efficiently is challenging, and we report on our work towards that goal.
Another drawback of AspectJ is the highly syntactic nature of the event patterns, often requiring the programmer to list all methods that have a certain property, rather than specifying that property itself. We argue that Datalog provides an appropriate notation for describing such properties. Furthermore, all of the existing patterns in AspectJ can be reduced to Datalog via simple rewrite rules.
This research is carried out with abc, an extensible optimising compiler for AspectJ, which is freely available for download.
Authors: Neil Ongkingco, Pavel Avgustinov, Julian Tibble, Laurie Hendren, Oege de Moor, Ganesh Sittampalam
Date: January 2006
AOSD 2006, March 2006, Bonn, Germany.
Abstract
AspectJ does not provide a mechanism to hide implementation details from advice. As a result, aspects are tightly coupled to the implementation of the code they advise, while the behaviour of the base code is impossible to determine without analysing all advice that could modify its behaviour.
The concept of open modules is proposed by Aldrich to solve the problems that arise from unrestricted advice. Defined for a small functional language, it provides an encapsulation construct that allows an implementation to limit the set of points to which external advice may apply.
We present an adaptation of open modules for AspectJ. We expand open modules to encompass the full set of pointcut primitives for AspectJ, extend its method of module composition to include the ability to open up a module, and describe the implementation of the design as an extension of the AspectBench compiler. We also provide an example of the use of open modules on a substantial AspectJ program to show how it would fit into existing AspectJ projects.
Sample open module code: ( omants.tar.gz, omants.zip )
Note: The open modules extension has been part of the standard abc release since version 1.1.0. See the extensions page for details.
Authors: 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
Date: October 2005
Transactions on Aspect-Oriented Software Development, 2005.
Abstract
Research in the design of aspect-oriented programming languages requires a workbench that facilitates easy experimentation with new language features and implementation techniques. In particular, new features for AspectJ have been proposed that require extensions in many dimensions: syntax, type checking and code generation, as well as data flow and control flow analyses.
The AspectBench Compiler abc is an implementation of such a workbench. The base version of abc implements the full AspectJ language. Its frontend is built, using the Polyglot framework, as a modular extension of the Java language. The use of Polyglot gives flexibility of syntax and type checking. The backend is built using the Soot framework, to give modular code generation and analyses. In this paper, we outline the design of abc, focusing mostly on how the design supports extensibility. We then provide a general overview of how to use abc to implement an extension. Finally, we illustrate the extension mechanisms of abc through a number of small, but non-trivial, examples. abc is freely available under the GNU LGPL.
Authors:
Chris Allan, Pavel Avgustinov, Sascha Kuzins, Oege de Moor, Damien Sereni, Ganesh Sittampalam, Julian Tibble (Oxford University)
Aske Simon Christensen (University of Aarhus)
Laurie Hendren, Ondřej Lhoták (McGill University)
Date: August 2005
OOPSLA 2005, October 2005, San Diego, CaliforniaAbstract
An aspect observes the execution of a base program; when certain actions occur, the aspect runs some extra code of its own. In the AspectJ language, the observations that an aspect can make are confined to the current action: it is not possible to directly observe the history of a computation.Recently, there have been several interesting proposals for new history-based language features, most notably by Douence et al. and by Walker and Viggers. In this paper, we present a new history-based language feature called tracematches that enables the programmer to trigger the execution of extra code by specifying a regular pattern of events in a computation trace. We have fully designed and implemented tracematches as a seamless extension of AspectJ.
A key innovation in our tracematch approach is the introduction of free variables in the matching patterns. This enhancement enables a whole new class of applications in which events can be matched not only by the event kind, but also by the values associated with the free variables. We provide several examples of applications enabled by this feature.
After introducing and motivating the idea of tracematches via examples, we present a detailed semantics of our language design, and we derive an implementation from that semantics. The implementation has been realised as an extension of the abc compiler for AspectJ.
Note: The tracematch extension has been part of the standard abc release since version 1.1.0. For more details, see the extensions page.
Authors: 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
Date: April 2005
PLDI 2005, June 2005, Chicago, USA
Abstract
AspectJ, an aspect-oriented extension of Java, is becoming increasingly popular. However, not much work has been directed at optimising compilers for AspectJ. Optimising AOP languages provides many new and interesting challenges for compiler writers, and this paper identifies and addresses three such challenges.
First, compiling around advice efficiently is particularly challenging. We provide a new code generation strategy for around advice, which (unlike previous implementations) both avoids the use of excessive inlining and the use of closures. We show it leads to more compact code, and can also improve run-time performance. Second, woven code sometimes includes run-time tests to determine whether advice should execute. One important case is the cflow pointcut which uses information about the dynamic calling context. Previous techniques for cflow were very costly in terms of both time and space. We present new techniques to minimise or eliminate the overhead of cflow using both intra- and inter-procedural analyses. Third, we have addressed the general problem of how to structure an optimising compiler so that traditional analyses can be easily adapted to the AOP setting.
We have implemented all of the techniques in this paper in abc, our AspectBench Compiler for AspectJ, and we demonstrate significant speedups with empirical results. Some of our techniques have already been integrated into the production AspectJ compiler, ajc 1.2.1.
Authors: 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
Date: January 2005
AOSD 2005, March 2005, Chicago, USA.
Abstract
Research in the design of aspect-oriented programming languages requires a workbench that facilitates easy experimentation with new language features and implementation techniques. In particular, new features for AspectJ have been proposed that require extensions in many dimensions: syntax, type checking and code generation, as well as data flow and control flow analyses.
The AspectBench Compiler abc is an implementation of such a workbench. The base version of abc implements the full AspectJ language. Its frontend is built, using the Polyglot framework, as a modular extension of the Java language. The use of Polyglot gives flexibility of syntax and type checking. The backend is built using the Soot framework, to give modular code generation and analyses. In this paper, we outline the design of abc, focusing mostly on how the design supports extensibility. We then provide a general overview of how to use abc to implement an extension. Finally, we illustrate the extension mechanisms of abc through a number of small, but non-trivial, examples. abc is freely available under the GNU LGPL.
Authors:
Bruno Dufour, Christopher Goard, Laurie Hendren and Clark Verbrugge (McGill University)
Oege de Moor and Ganesh Sittampalam (Oxford University)
Date: May 2004
OOPSLA 2004, October 2004, Vancouver, CanadaAbstract
This paper proposes and implements a rigorous method for studying the dynamic behaviour of AspectJ programs. As part of this methodology several new metrics specific to AspectJ programs are proposed and tools for collecting the relevant metrics are presented. The major tools consist of: (1) a modified version of the AspectJ compiler that tags bytecode instructions with an indication of the cause of their generation, such as a particular feature of AspectJ; and (2) a modified version of the *J dynamic metrics collection tool which is composed of a JVMPI-based trace generator and an analyzer which propagates tags and computes the proposed metrics. This dynamic propagation is essential, and thus this paper contributes not only new metrics, but also non-trivial ways of computing them.
We furthermore present a set of benchmarks that exercise a wide range of AspectJ's features, and the metrics that we measured on these benchmarks. The results provide guidance to AspectJ users on how to avoid efficiency pitfalls, to AspectJ implementors on promising areas for future optimization, and to tool builders on ways to understand runtime behaviour of AspectJ.
(postscript, PDF).