Dependent advice: A general approach to optimizing history-based aspects (extended version)

Technical Report abc-2008-2.

Authors: Eric Bodden (McGill University), Feng Chen and Grigore Rosu (University of Illinois at Urbana-Champaign)
Date of first publication: July 16th, 2008
Updated on: October 15th, 2008 and January 7th, 2009

Abstract

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.

(PDF, PS)

You can find our benchmarks for this Technical Report on this webpage.
Racer: Effective Race Detection Using AspectJ (extended version)

Technical Report abc-2008-1.

Authors: Eric Bodden (McGill University) and Klaus Havelund (California Institute of Technology)
Date: May 19th, 2008

Note: This Technical Report is an extended version of this ISSTA publication.

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.

(PDF, PS)

Download our implementation of Racer, RacerAJ here.

Static Analysis Techniques for Evaluating Runtime Monitoring Properties Ahead-of-Time

Technical Report abc-2007-6.

Authors: Eric Bodden, Patrick Lam and Laurie Hendren
Date: November 23rd, 2007

Abstract

Runtime monitoring enables developers to specify code that executes whenever certain sequences of events occur during program execution. In particular, runtime monitors can check for illegal API uses, such as attempts to read from already-closed files. This paper presents techniques for evaluating runtime monitoring properties ahead-of-time. Statically evaluating runtime monitors is advantageous for two reasons: 1) it enables the optimization and removal of unnecessary monitoring code; furthermore, 2) it can increase developers' confidence that their programs conform to their stated correctness properties. In the best case, static analysis can successfully guarantee that a program never violates those properties at all.

Our work focuses on tracematches, a monitoring notation based on regular expressions with free variables over program events that bind these variables to heap objects. Statically deciding properties of tracematches is difficult: tracematches bind heap objects throughout the course of their evaluation. One might expect that an interprocedural flow-sensitive analysis would be required. However, our approach successfully analyzes tracematches by combining inexpensive whole-program summary information with a suite of carefully-designed intraprocedural flow-sensitive analyses. Our analyses use a novel abstraction which captures both positive information, indicating that an object could be associated with a particular monitor state, and negative information, indicating that the object is known not to be in a state. This abstraction enables us to eliminate unnecessary monitoring instrumentation.

We implemented our analyses and applied them to 43 program/tracematch combinations. In 18 cases, our analysis removes all instrumentation from the programs, statically verifying the tracematch property. In 12 more cases, our analysis leaves no more than 10 instrumentation points, and we easily verified (by hand) that these programs satisfied (or falsified) the stated property. In 36 of 43 cases, our techniques reduce runtime overhead to below 10%.

Download the benchmarks for this technical report here. In this document we provide the raw benchmark data.

(PDF, PS)

Static Aspect Impact Analysis

Technical Report abc-2007-5.

Authors: Dehua Zhang and Laurie Hendren
Date: November 14th, 2007

Abstract

One of the major challenges in aspect-oriented programming is that aspects may have unintended impacts on a base program. Thus, it is important to develop techniques and tools that can both summarize the impacts and provide information about the causes of the impacts. This paper presents static impact analyses for AspectJ.

Our approach focuses on two kinds of impacts, state impacts which cause changes of state in the base program, and computation impacts which cause changes in functionality by adding, removing or replacing computations of the base program.

We provide a classification scheme for these two kinds of impacts and then develop a set of static analyses to estimate these impacts. A key feature of our approach is the use of points-to analysis to provide more accurate estimates. Further, our analysis results allow us to trace back to find the causes of the impacts.

We have implemented our techniques in the AspectBench compiler and provide examples of impact results.

This is a revised version of the technical report as of November 14th, 2007.

(PDF)

Relational Aspects as Tracematches

Technical Report abc-2007-4.

Authors: Eric Bodden, Reehan Shaikh, Laurie Hendren
Date of first publication: October 13th, 2007
Updated on: February 8th, 2008

Note: This Technical Report is an extended version of this AOSD publication.

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.

(PDF, PS)

The benchmarks from the paper can be downloaded here, along with our initial implementation. Relational aspects will be part of our next abc release.

Flow-sensitive static optimizations for runtime monitors

Technical Report abc-2007-3.

Authors: Eric Bodden, Patrick Lam, Laurie Hendren
Date: July 18th, 2007

Abstract

Runtime monitoring enables developers to specify code that executes whenever certain sequences of events occur during program execution. Tracematches, a Java language extension, permit developers to specify and execute runtime monitors. Tracematches consist of regular expressions over events, where each event may specify free variables that are bound to run-time objects. Na\"ive implementations of runtime monitoring are expensive and can cause prohibitive slowdowns. In previous work, we proposed optimizations based on flow-insensitive pointer analyses. While these optimizations worked well in most cases, more difficult cases with large overheads remained.

In this paper, we propose three novel intraprocedural optimizations with the goal of eliminating the overhead from runtime monitors. Our optimizations rely on flow-sensitivity and precise local may-alias and must-alias information. The first two optimizations identify and remove unnecessary instrumentation, while the third one hoists instrumentation out of loop bodies.

We applied our transformations to seven difficult combinations of tracematches with programs from the DaCapo benchmark suite which defeated our earlier analyses. Our results show that our three optimizations, in combination, can remove much of the instrumentation in this benchmark set. For two of the seven cases, we can remove all instrumentation: our analysis successfully shows that the benchmark programs will always satisfy the verification properties stated in the tracematches. Our results furthermore suggest that our analysis can detect hidden method preconditions which ought to documented and visible to the developers.

After our optimizations, only three cases (out of an original 90 cases) still have noticeable runtime overheads. One of these cases cannot possibly be optimized, because the runtime monitors actually trigger. While our optimizations ought to be able to handle the remaining two cases, only an imprecision in our underlying global points-to analysis currently prevents us from removing the overhead in those cases as well.

(PDF, PS)

The benchmarks for this report can be downloaded here.

A staged static program analysis to improve the performance of runtime monitoring (extended version)

Technical Report abc-2007-2.

Authors: Eric Bodden, Laurie Hendren, Ondřej Lhoták
Date: April 25th, 2007

This is an extended version of our ECOOP 07 submission.

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 Technical Report 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.

(PDF, PS)

The benchmarks for this report can be downloaded here.

Making Trace Monitors Feasible

Technical Report abc-2007-1.

Authors: Pavel Avgustinov, Julian Tibble, Oege de Moor
Date: March 20th, 2007

Abstract

A trace monitor observes an execution trace at runtime; when it recognises a specified sequence of events, the monitor runs extra code. Typical applications of runtime monitors include type-state checking, and implementing variations of the observer pattern.

This paper shows how to generate efficient trace monitors from declarative specifications of the relevant event pattern. We present the first set of trace monitoring benchmarks to facilitate comparative experiments in the field. Using these benchmarks we provide experimental evidence of two show-stopping problems that need to be addressed in any implementation: space leaks and the organisation of partial solutions.

We evaluate a space leak elimination analysis proposed elsewhere, and confirm (through a series of careful experiments) that it is effective in keeping memory consumption under control. We also introduce a novel algorithm and data structure to minimise the work involved in updating the matching state. Again we validate this optimisation through our benchmark set.

Our optimisations depend solely on analyses of the specification, and they do not require interprocedural analysis of the observed code. Nevertheless, we often achieve performance close to that of hand-optimised monitors, and always within an order of magnitude.

(PDF, PS)

Please see the benchmarks page for the trace monitoring benchmarks.

A staged static program analysis to improve the performance of runtime monitoring

Technical Report abc-2006-4.

Authors: Eric Bodden, Laurie Hendren, Ondřej Lhoták
Date: December 21st, 2006

(This report is outdated. Please download version abc-2007-2 instead.)

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.

(PDF, PS)

The benchmarks for this report can be downloaded here.

Semantics of Static Pointcuts in AspectJ

Technical Report abc-2006-3.

Authors: Pavel Avgustinov, Elnar Hajiyev, Neil Ongkingco, Oege de Moor, Damien Sereni, Julian Tibble, Mathieu Verbaere
Date: July 25, 2006

Abstract

In aspect-oriented programming, one can intercept events by writing patterns called pointcuts. The pointcut language of the most popular aspect-oriented programming language, AspectJ, allows the expression of highly complex properties of the static program structure.

We present the first rigorous semantics of the AspectJ pointcut language, by translating static patterns into safe (i.e. range-restricted and stratified) Datalog queries. Safe Datalog is a logic language like Prolog, but it does not have data structures; consequently it has a straightforward least fixpoint semantics and all queries terminate.

The translation from pointcuts to safe Datalog consists of a set of simple conditional rewrite rules, implemented using the Stratego system. The resulting queries are themselves executable with the CodeQuest system. We present experiments indicating that direct execution of our semantics is not prohibitively expensive.

(PDF, PS)

Datalog Semantics of Static Pointcuts in AspectJ 1.2.1

Technical Report abc-2006-2.

Authors: Pavel Avgustinov, Elnar Hajiyev, Neil Ongkingco, Oege de Moor, Damien Sereni, Julian Tibble, Mathieu Verbaere
Date: July 22, 2006

Abstract

In aspect-oriented programming, one can intercept events by writing patterns called pointcuts. The pointcut language of the most popular aspect-oriented programming language, AspectJ, allows the expression of highly complex properties of the static program structure.

We present the first rigorous semantics of the AspectJ pointcut language, by translating static patterns into safe (i.e. range-restricted and stratified) Datalog queries. Safe Datalog is a logic language like Prolog, but it does not have data structures; consequently it has a straightforward least fixpoint semantics and all queries terminate.

The translation from pointcuts to safe Datalog consists of a set of simple conditional rewrite rules, implemented using the Stratego system. The resulting queries are themselves executable with the CodeQuest system. This technical report presents a full discussion of the rewrite rules required for AspectJ 1.2.1.

Download: The entire rewrite rules package is available for download here. See the included README for instructions.

(PDF, PS)

Efficient Trace Monitoring

Technical Report abc-2006-1.

Authors: Pavel Avgustinov, Julian Tibble, Eric Bodden, Ondřej Lhoták, Laurie Hendren, Oege de Moor, Neil Ongkingco, Ganesh Sittampalam
Date: March 19, 2006

Abstract

A trace monitor observes the sequence of actions in a software system, and when it detects that this sequence matches a given pattern, it executes some extra code of its own. Trace monitors are often specified declaratively using patterns based on regular expressions, context free grammars or logical formulae, and then the trace monitor implementation is generated from the specification. Trace monitors are particularly useful for runtime verification, and many variations have been proposed. Despite this intense interest, there have been hardly any systems that implement the idea in its full generality, because it is hard to generate efficient code from a purely declarative statement of the pattern. This paper identifies and addresses the challenges faced in generating efficient trace monitors from declarative pattern-based specifications.

We present the first set of benchmarks and experiments to identify these implementation challenges which include:

  1. careful generation of the automaton for recognising the pattern,
  2. specialising the generated code to the pattern being recognised,
  3. avoiding memory leaks and
  4. quickly locating relevant partial matches.
We also examine the impact of the choice of specification formalism on performance.

Based on our experimental observations we present several novel techniques that address these challenges, purely through a careful analysis of the monitor specification. Our techniques do not require a whole-program analysis of the base program that is being monitored. All of our techniques have been implemented in abc, an extensible compiler for the AspectJ language, which is itself an extension of Java. Their applicability is by no means restricted to this setup, however, and we argue that they can be used to improve any trace monitoring system. Both the benchmarks and the implementation are publicly available.

(PDF, PS)

Please see the benchmarks page for the trace monitoring benchmarks.

Adding Open Modules to AspectJ

Technical Report abc-2005-2.

Authors: Neil Ongkingco, Pavel Avgustinov, Julian Tibble, Laurie Hendren, Oege de Moor, Ganesh Sittampalam
Date: September 30, 2005

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.

(PDF, PS)

Source code for ants example: (tar.gz, zip)

Adding trace matching to AspectJ

Technical Report abc-2005-1.

Authors: 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
Date: March 23, 2005

Abstract

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 also by Walker and Viggers. In this paper we present a new history-based language feature called tracematches, where the programmer can 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 to 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 where 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.

This report is now obsolete, and superseded by our OOPSLA 2005 paper.

(PDF, PS)

Building the abc AspectJ compiler with Polyglot and Soot

Technical Report abc-2004-4.

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: December 20, 2004

Abstract

Aspect-oriented programming and the development of aspect-oriented languages is rapidly gaining momentum, and the advent of this new kind of programming language provides interesting challenges for compiler developers. Aspect-oriented language features require new compilation approaches, both in the frontend semantic analysis and in the backend code generation. This paper is about the design and implementation of the abc compiler for the aspect-oriented language AspectJ.

One important contribution of this paper is to show how we can leverage existing compiler technology by combining Polyglot (an extensible compiler framework for Java) in the frontend and Soot (a framework for analysis and transformation of Java) in the backend. In particular, the extra semantic checks needed to compile AspectJ are implemented by extending and augmenting the compiler passes provided by Polyglot. All AspectJ-specific language constructs are then extracted from the program to leave a pure Java program that can be compiled using the existing Java code generation facility of Soot. Finally, all code generation and transformation is performed on Jimple, Soot's intermediate representation, which allows for a clean and convenient method of applying aspects to source code and class files alike.

A second important contribution of the paper is that we describe our implementation strategies for the new challenges that are specific to aspect-oriented language constructs. Although our compiler is targeted towards AspectJ, many of these ideas apply to aspect-oriented languages in general.

Our abc compiler implements the full AspectJ language as defined by ajc 1.2.0 and is freely available under the GNU LGPL.

(PDF, PS)

Optimising AspectJ

Technical Report abc-2004-3.

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: November 2004

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

A slightly abridged version of this report has been accepted for PLDI 2005.

(PDF, PS)

Building the abc AspectJ compiler with Polyglot and Soot (obsolete version)

Technical Report abc-2004-2.

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 2004

This report is now obsolete, and superseded by abc-2004-4 above.

(PDF, PS)

abc: An extensible AspectJ compiler

Technical Report abc-2004-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: September 2004

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.

A slightly revised version of this report will appear in AOSD 2005. Please cite the final version which can be found here.

(PDF, PS)