35
Calvar et al. Jérôme Calvar, Raphaël Tremblay- Lessard, Sylvain Hallé Université du Québec à Chicoutimi CANADA Fonds de recherche sur la nature et les technologies CRSNG NSERC A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments Roger Villemaire Université du Québec à Montréal Presented by

A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Embed Size (px)

DESCRIPTION

A runtime monitor is a tool that takes as input a model of some system, and observes in real time that the sequence of events produced by a run of that system follows the specification. While existing monitoring solutions generally use finite-state machines and temporal logic as their model language, the specification is ultimately tangled with hand-written, implementation-specific details which severely limit their range of application. We present a runtime monitoring platform that clearly separates the extraction of events in the running program from the specification and monitoring process. This separation allows one to cleanly monitor first-order properties involving arbitrarily complex native program objects, while still incurring reasonable overhead.

Citation preview

Page 1: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Jérôme Calvar, Raphaël Tremblay-Lessard, Sylvain Hallé

Université du Québec à ChicoutimiCANADA

Fonds de recherchesur la natureet les technologies

CRSNGNSERC

A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Roger VillemaireUniversité du Québec à Montréal

Presented by

Page 2: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Presentation overview

1. What is runtime monitoring?

2. Current issues in runtime monitoring

3. Our runtime monitoring framework

4. Experimental results

Page 3: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

What is runtime monitoring?

Runtime monitoring is the process of observing an actual run of a system and dynamically checkingand enforcing constraints on its execution

Monitor

Verifies that sequence of events follows specificationin realtime

System

Event

Event. . .

}The execution of the system produces events

Specification

Gives conditions on events and sequences of events allowed to happen

Page 4: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Runtime monitoring use cases

Web applications: filter out messages sent by a browser when the client-server protocol is not followed

- Saves CPU time on server (spared handling of erroneous messages)

- Useful for developing/debugging the client

- The presence of a monitor compels the server to document its protocol in a machine-readable format

Page 5: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Runtime monitoring use cases

An example, the BeepBeep runtime monitor (Hallé and Villemaire)

XMLHttpRequest

JavaScript

Internet

Normal situation: JavaScript object XmlHttpRequest centralizes all communications with the outside world

Page 6: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Runtime monitoring use cases

An example, the BeepBeep runtime monitor (Hallé and Villemaire)

XMLHttpRequest

JavaScript

Internet

Runtime monitoring: a new class wraps around this object and checks incoming/outgoing messages before passing them to the original XMLHttpRequest

Page 7: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Runtime monitoring use cases

In object-oriented programs: enforce valid use of objects' methods according to their state

unknownstart

more none

error

hasnext() == true hasnext() == false

next()

hasnext()

next() hasnext()

next()

Correct usage of the Java Iterator class (from Jin et al., PLDI 2011)

Page 8: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Runtime monitoring use cases

Example: Rosu et al.'s Java-MOP

full-binding HasNext(Iterator i) { event hasnext after(Iterator i) : call(* Iterator.hasNext()) && target(i) {} event next before(Iterator i) : call(* Iterator.next()) && target(i) {}

fsm : start [ next -> unsafe hasnext -> safe ] safe [ next -> start hasnext -> safe ]

unsafe [ next -> unsafe hasnext -> safe ]

alias match = unsafe

@match { System.out.println("next called without hasNext!"); }}

Page 9: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

An example: the Bank class

A simple (Java) class offering four methods:

Other classes interact with the Bank to perform transactions

void open(int act)void close(int act)void withdraw(int act, int amt)boolean isApproved(int act, int amt)

Page 10: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

An example: the Bank class

As with the Iterator, there are constraints one must follow to use the Bank properly:

S1. No operation on an account can be made afterclose

S2. For the same account, the amount cannotchange between an approval request and thefollowing call to withdraw

Declarative constraints: specify what must be true, but not how to check/enforce it

Page 11: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Issues in runtime monitoring

The properties deal with sequences of method calls AND values of the arguments inside these calls

These are called data-aware constraints. Why is it problematic?

S1: close(x) prevents any other method call, but only for that same x

S2: requires that methods isApproved(x,y) and the subsequent withdraw(x,y) have the same value y, but only if they also have the same value x

Page 12: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Data-aware constraints

These properties cannot be expressed by a simple finite-state automaton

How to express constraint on x and y?open(x)

close(x)

withdraw(x,y)isApproved(x,y)

x=1

Page 13: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Data-aware constraints

Existing runtime monitors extend the representation by tracking multiple instances of an automation, parameterized by some value

open(x)

close(x)

withdraw(x,y)isApproved(x,y) open(x)

close(x)

withdraw(x,y)isApproved(x,y)

x=1 x=2

Page 14: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Data-aware constraints

If multiples values are involved in the same constraint, one must use nested automata

open(x)withdraw(x,y)

isApproved(x,y)

x=1

withdraw(x,y)

y=1

isApproved(x,y)

withdraw(x,y)

y=2

. . .

Page 15: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Data-aware constraints

Issue #1: the same event may (or may not) need to be dispatched to more than one automaton...

...the specification must hence also describe how to combine the (potentially conflicting) decision returned by each automaton

m1(x,y)

x=1

m2(y,x)

y=2

m1(x,y)

x=2

m2(y,x)

y=1

ERROR OKand? / or?

Page 16: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Data-aware constraints

Issue #2: the specification must describe how and when automata must be instantiated, depending on the events that are observed

Consequence: a growing part of the constraints becomes procedural, and amounts to a hand-coding of a monitoring algorithm inside the specification

Page 17: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Separation of concerns

Monitor and specification become tangled: loss of separation of concerns

Monitor

Verifies that sequence of events follows specificationin realtime

System

Event

Event. . .

}The execution of the system produces events

Specification

Gives conditions on events and sequences of events allowed to happen

Page 18: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Data-aware constraints

Issue #3: current monitoring frameworks are very language-dependent; the specification contains code in the system's native language

Page 19: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Separation of concerns

Monitor and system become tangled: loss of separation of concerns (again)

Monitor

Verifies that sequence of events follows specificationin realtime

System

Event

Event. . .

}The execution of the system produces events

Specification

Gives conditions on events and sequences of events allowed to happen

Page 20: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Monitoring framework

Proposed architecture: framework that clearly separates all three aspects of the process

- Separation of the system from the events it produces

- Separation of the specification from the algorithm to verify it

Page 21: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Monitoring framework

Program

Pointcut

Aspect

OutcomeAdviceexecution

Monitor

mEventformatter

Program events are declared using a signature

Event data is extracted and formatted as an XML structure

XML is passed to a general-purpose monitor

Specification is expressed as constraints on sequences of XML structures -> system-independent

Page 22: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Event formatting

Example: a call to myBank.withdraw(123, 500) is formatted as

For a message m, data can be referred to by a path expression π; hence if π = call/method/act, m(π) = "123"

<call> <method>withdraw</method> <act>123</act> <amt>500</amt></call>

Method arguments, named asin the method's prototype

Method name

Page 23: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Properties on event sequences

LTL-FO+ is an extension of classical Linear Temporal Logic to express constraints on XML event sequences with data

- Ground terms are equalities:

between a variable and a constant (x = c) between two variables x = y between a path expression and a constant (a/b/c = d)

Page 24: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Properties on event sequences

- Boolean connectives carry their traditional meaning

- Temporal operators express modalities between messages:

G φ : all messages from now on satisfy φ F φ : some message in the future will satisfy φ X φ : the next message will satisfy φ φ U ψ : φ holds on every message until some message satisfies ψ

Page 25: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Properties on event sequences

- First-order quantifiers fetch and retain values in a message

∀ x ∈ π : φ(x)

In the current message m, for every value c such that m(π) = c, φ(c) is true

∃ x ∈ π : φ(x)

In the current message m, for some value c such that m(π) = c, φ(c) is true

Page 26: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Properties on event sequences

S1. No operation on an account can be made afterclose

G (call/method = close → ∀ a ∈ call/act : X G (∀ a' ∈ call/act : a ≠ a' ))

Page 27: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Writing the specification

PROTOTYPES shields the property from language-specific considerations

PROTOTYPESvoid Bank.open(int act);void Bank.close(int ac);void Bank.withdraw(int act, int amount);boolean Bank.isApproved(int act, int amt);

SPEC LTL-FO+G ((call/method/close) -> ([a1 call/act] (X (G ([a2 call/act] (!((a1) = (a2))))))))

@FALSE { System.out.println("This is forbidden");}

Method calls tointercept

Property tomonitor

Action to takeif property isviolated

Page 28: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Properties on event sequences

For Java, a PHP script converts the PROTOTYPESsection into the appropriate event formatter, and the @FALSE section into the appropriate advice executor...

...the monitor itself is always the same!

Program

Pointcut

Aspect

OutcomeAdviceexecution

Monitor

mEventformatter

Page 29: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Non-primitive objects

What if the method's arguments are not primitive types? Example:

Account a = new Account(...); myBank.withdraw(a, 500);

<call> <method>withdraw</method> <act>

</act> <amt>500</amt></call>

What is the account's "value"?

Page 30: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Non-primitive objects

Observation: runtime constraints are expressed about objects' specific properties that ultimately boil down to primitive types

Account a = new Account(...); myBank.withdraw(a, 500);

The constraint on withdraw only requires account numbers, not full instances of Account

Solution: have the event formatter write down member fields of the object (not the full object), but only those necessary for the constraint to monitor

Page 31: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Non-primitive objects

Example:

PROTOTYPESvoid AdvancedBank.getAuthorization(Account a, int amount);<return> <method>getAuthorization</method> <id>{return.getId()}</id> <amount>{return.getAmount()}</amount></return>

void AdvancedBank.withdraw(Account a,Authorization auth);<call> <method>withdraw</method> <id>{auth.getId()}</id> <amount>{auth.getAmount()}</amount><call>

Message template usedby event formatter forthis method call

Code to execute oncallee or its argumentsto populate elementwith primitive value

Page 32: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Pros of this approach

1. Constraints involving non-primitive objects can be expressed and monitored: once events are formatted, they are undistinguishable from "primitive" calls by the runtime monitor

2. The trace of events can be saved to a (plain) XML file and verified a posteriori; would be impossible if events contained references to raw Java objects

Page 33: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Pros of this approach

3. The monitor does not deal with native objects from the system: preserves separation of concerns discussed earlier

4. Being allowed to query the internal state of objects sometimes simplifies the property to monitor

- Surprising finding - See paper, "autonomous" vs. "query" approach

in experiments - Work in progress: systematize this observation

("piggyback runtime monitoring")

Page 34: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Experiments

Runtime monitoring framework tested on the "simple" (primitive) and "advanced" (non-primitive) Bank examples, with randomly generated calls

0

10

20

30

40

50

60

[-.08,-.04)

[-.04,-.02)

[-.02,0)

[0,.02)

[.02,.08) [-.06,-.03)[-.03,0) [0,.02) [.02,.04)

[.04,.08)

Num

ber

oftr

aces

S1 S2

Overhead per method call (ms)Simple bank

Page 35: A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments

Calvar et al.

Conclusion

We proposed a framework for the runtime monitoring of events in a system

These events can carry data parameters that are relevant to the constraints to monitor

Our framework clearly separates the extraction of event data from the system from the property to monitor

Experiments show that the formatting of native events into XML imposes an overhead of 5-10 microseconds per event