Stateful Breakpoints: A Practical Approach to Defining Parameterized Runtime Monitors

Eric | July 1, 2011

To appear at the New Ideas track of ESEC/FSE:

A runtime monitor checks a safety property during a program’s execution. A parameterized runtime monitor can monitor properties containing free variables, or parameters. For instance, a monitor for the regular expression “close(s)+ read(s)” will warn the user when reading from a stream s that has previously been closed. Parameterized runtime monitors are very expressive, and research on this topic has lately gained much traction in the Runtime Verification community. Existing monitoring algorithms are very efficient. Nevertheless, existing tools provide little support for actually defining runtime monitors, probably one reason for why few practitioners are using runtime monitoring so far.

In this work we propose the idea of allowing programmers to express parameterized runtime monitors through stateful breakpoints, temporal combinations of normal breakpoints, a concept well known to programmers. We show how we envision programmers to define runtime monitors through stateful breakpoints and parameter bindings through breakpoint expressions. Further, we explain how stateful break- points improve the debugging experience: they are more expressive than normal breakpoints, nevertheless can be evaluated more efficiently. Stateful breakpoints can be attached to bug reports for easy reproducibility: they often allow developers to run directly to the bug in one single step. Further, stateful breakpoints can potentially be inferred from a running debugging session or using property inference and fault localization tools.

Download the paper here.

Clara: a Framework for Partially Evaluating Finite-state Runtime Monitors Ahead of Time

Eric | August 19, 2010

In my publications section you can now find our RV 2010 paper on the Clara Framework. This is by far the most concise introduction to Clara; therefore I hope that people will find it more accessible than my thesis. download the paper here

Abstract: Researchers have developed a number of runtime verification tools that generate runtime monitors in the form of AspectJ aspects. In this work, we present Clara, a novel framework to statically optimize such monitoring aspects with respect to a given program under test. Clara uses a sequence of increasingly precise static analyses to automatically convert a monitoring aspect into a residual runtime monitor. The residual monitor only watches events triggered by program locations that the analyses failed to prove safe at compile time. In two-thirds of the cases in our experiments, the static analysis succeeds on all locations, proving that the program fulfills the stated properties, and completely obviating the need for runtime monitoring. In the remaining cases, the residual runtime monitor is usually much more efficient than a full monitor, yet still captures all property violations at runtime.

Comments
Comments Off on Clara: a Framework for Partially Evaluating Finite-state Runtime Monitors Ahead of Time
Categories
Research
Tags
Clara, Runtime Monitoring, Runtime verification, RV, RV 2010

Reducing Configurations to Monitor in a Software Product Line

Eric | July 26, 2010

Joint work with Chang Hwan Peter Kim, Don Batory, and Sarfraz Khurshid, to appear at RV 2010.

Abstract: A software product line is a family of programs where each program is defined by a unique combination of features. Product lines, like conventional programs, can be checked for safety properties through execution monitoring. However, because a product line induces a number of programs that is potentially exponential in the number of features, it would be very expensive to use existing monitoring techniques: one would have to apply those techniques to every single program. Doing so would also be wasteful because many programs can provably never violate the stated property. We introduce a monitoring technique dedicated to product lines that, given a safety property, statically determines the feature combinations that cannot possibly violate the property, thus reducing the number of programs to monitor. Experiments show that our technique is effective, particularly for safety properties that crosscut many optional features.

Download the paper here.

Comments
Comments Off on Reducing Configurations to Monitor in a Software Product Line
Categories
Research
Tags
Clara, Product Lines, Runtime verification

Save the Date: Nov 1st-4th – Clara Tutorial at RV 2010

Eric | May 18, 2010

RV ConferenceToday I am having good news for everybody who is working on runtime monitoring in a Java-based setting and is thinking about using my Clara framework for partially evaluating runtime monitors at compile time. My tutorial proposal for RV 2010 has just been accepted.

For now, I am planning to cover the following topics:

  • Problem Statement: Why partial evaluation?
  • What’s out there? Overview of existing runtime-monitoring tools
  • Architecture of Clara: Important Design Decisions
  • Static analyses in Clara: How do they work? How can we use them?
    • Quick Check: syntactic, flow-insensitive
    • Orphan-Shadows Analysis: pointer-based, flow-insensitive
    • Nop-Shadows Analysis: pointer-based, flow-sensitive
  • Clara as a generic optimizer: How to allow your own runtime-verification tool to use Clara for static optimizations

If time permits also:

  • Clara and testing: Using Clara to tell apart useful from useless test cases

You can read the full tutorial proposal here. Patrick Lam will likely be joining me for the fun. We will likely be allocated a 2.5h slot, which is not a lot of time to cover all these topics. Therefore, if you would like me to cover some special topic in more detail than others, don’t be shy and let me know ;-)

P.S. Also don’t forget that the paper submission deadline for RV is approaching quickly: June 1st!

Comments
Comments Off on Save the Date: Nov 1st-4th – Clara Tutorial at RV 2010
Categories
Research
Tags
Clara, Runtime verification, RV, Static Analysis

Now available: Clara, a novel framework for implementing hybrid typestate analyses

Eric | September 10, 2009

ClaraIn my doctoral dissertation (click here for a draft), I present Clara (Compile-time Approximation of Runtime Analyses), a novel research framework for the implementation of hybrid typestate analyses. Clara is now online – fully documented – at: http://www.bodden.de/clara/

Typestate properties aid program understanding, and one can even define type systems that prevent programmers from causing typestate errors, or derive static typestate analyses that try to determine whether a given program violates typestate properties. Unfortunately, the typestate-analysis problem is generally undecidable. Researchers have therefore proposed a hybrid approach that uses
static-analysis results to generate a residual runtime monitor. This monitor captures actual property violations as they occur, but only updates its internal state at relevant statements, as determined through static analysis.

Read the rest of this entry »

Comments
Comments Off on Now available: Clara, a novel framework for implementing hybrid typestate analyses
Categories
Research
Tags
Clara, Runtime Monitoring, Runtime verification, Static Analysis, Thesis, tracematches, Typestate

The RV 2009 DEADLINE has been EXTENDED

Eric | March 5, 2009

image The RV 2009 DEADLINE has been EXTENDED to:
    Wednesday 25 March 2009, 23:59 Samoan time (= UTC-11)
http://www-rv2009.imag.fr/
9th International Workshop on Runtime Verification
RV 2009, June 26 – June 28, 2009
Grenoble, France

Read the rest of this entry »

Collaborative Runtime Verification with Tracematches

Eric | November 29, 2008

imageAfter only a little more than one and a half years, we were now able to publish the (extended) journal version of our RV07 paper on Collaborative Runtime Verification with Tracematches. What’s it about? The idea is simple: Assume you are doing runtime verification, but the nature of the property you want to monitor requires you to instrument some really hot loops in your code. In result, your instrumented program runs very slow. So why not split up the instrumentation load? Multiple users get different “probes” of instrumentation. Instrumentation can even be enabled only temporarily in order to reduce the imageoverall runtime overhead. In this paper we showed that this approach works  and most importantly scales (see graphic to the right). Plus, we avoid any false positive (false warnings), due to a special pointer analysis of the verification property, even if the instrumentation is partially disabled and therefore certain events may be missed. The journal paper is very similar to the workshop paper but it’s self-contained. free download here

Comments
Comments Off on Collaborative Runtime Verification with Tracematches
Categories
Research
Tags
collaborative, LinkedIn, Runtime verification, tracematches

New publication: Finding Programming Errors Earlier by Evaluating Runtime Monitors Ahead-of-Time

Eric | July 31, 2008

image I am happy to announce the final version of our new FSE paper (joint work with Patrick Lam and my supervisor Laurie Hendren). You can grab the paper here. The idea of the paper is that runtime monitoring is nice because it manages to show you only actual errors, but nevertheless one should make a best effort to evaluate a runtime monitor ahead-of-time, i.e. at compile-time, as well as possible, so that programmers can find errors in the programs earlier in the development process.

Read the rest of this entry »

Comments
Comments Off on New publication: Finding Programming Errors Earlier by Evaluating Runtime Monitors Ahead-of-Time
Categories
Research
Tags
Bug finding, Object representatives, Runtime Monitoring, Runtime verification, Static Analysis, tracematches