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

  • Published on

  • View

  • Download


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.


  • 1. A Runtime Monitoring Framework for Event Streams with Non-Primitive Arguments Jrme Calvar, Raphal Tremblay- Lessard, Sylvain Hall Universit du Qubec Chicoutimi CANADAPresented by Roger Villemaire Universit du Qubec Montral Fonds de recherche sur la nature et les technologies NSERC CRSNGCalvar et al.

2. Presentation overview 1. What is runtime monitoring? 2. Current issues in runtime monitoring 3. Our runtime monitoring framework 4. Experimental resultsCalvar et al. 3. What is runtime monitoring? Runtime monitoring is the process of observing an actual run of a system and dynamically checking and enforcing constraints on its executionSystemMonitorSpecication}EventVeries that Gives conditions onEvent sequence ofevents and... events followsspecication sequences of events allowed to happenin realtime The execution of the system produces eventsCalvar et al. 4. Runtime monitoring use cases Web applications: lter out messages sent by a browser when the client-server protocol is not followed- Saves CPU time on server (spared handling oferroneous messages)- Useful for developing/debugging the client- The presence of a monitor compels the server todocument its protocol in a machine-readableformatCalvar et al. 5. Runtime monitoring use cases An example, the BeepBeep runtime monitor (Hall and Villemaire)JavaScriptInternet XMLHttpRequestNormal situation: JavaScript objectXmlHttpRequest centralizes allcommunications with the outsideworldCalvar et al. 6. Runtime monitoring use cases An example, the BeepBeep runtime monitor (Hall and Villemaire)JavaScriptInternet XMLHttpRequestRuntime monitoring: a new classwraps around this object andchecks incoming/outgoingmessages before passing them tothe original XMLHttpRequestCalvar et al. 7. Runtime monitoring use cases In object-oriented programs: enforce valid use of objects methods according to their statestart unknownhasnext() == truehasnext() == false next()hasnext()hasnext()morenext()nonenext() errorCorrect usage of the JavaIterator class (from Jinet al., PLDI 2011)Calvar et al. 8. 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 :unsafe [ start [next -> unsafe next -> unsafe hasnext -> safe hasnext -> safe] ] safe [ alias match = unsafe next -> start hasnext -> safe @match { ] System.out.println("next calledwithout hasNext!"); } }Calvar et al. 9. An example: the Bank class A simple (Java) class oering four methods:void open(int act)void close(int act)void withdraw(int act, int amt)boolean isApproved(int act, int amt) Other classes interact with the Bank to perform transactionsCalvar et al. 10. 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 after close S2. For the same account, the amount cannot change between an approval request and the following call to withdraw Declarative constraints: specify what must be true, but not how to check/enforce itCalvar et al. 11. Issues in runtime monitoring The properties deal with sequences of method calls AND values of the arguments inside these callsS1: close(x) prevents any other method call, butonly for that same xS2: requires that methods isApproved(x,y) andthe subsequent withdraw(x,y) have the samevalue y, but only if they also have the samevalue x These are called data-aware constraints. Why is it problematic?Calvar et al. 12. Data-aware constraints These properties cannot be expressed by a simple nite-state automaton withdraw(x,y)How to express constraint open(x) isApproved(x,y)on x and y?close(x)x=1Calvar et al. 13. Data-aware constraints Existing runtime monitors extend the representation by tracking multiple instances of an automation, parameterized by some value withdraw(x,y)withdraw(x,y) open(x) isApproved(x,y)open(x) isApproved(x,y)close(x) close(x)x=1x=2Calvar et al. 14. Data-aware constraints If multiples values are involved in the same constraint, one must use nested automata withdraw(x,y) open(x) isApproved isApproved (x,y) withdraw(x,y)withdraw ... (x,y)(x,y) y=1y=2x=1Calvar et al. 15. Data-aware constraints Issue #1: the same event may (or may not) need to be dispatched to more than one automaton......the specication must hence also describe howto combine the (potentially conicting) decisionreturned by each automatonm1(x,y)m1(x,y)m2(y,x)m2(y,x)y=2y=1 x=1 x=2 ERROR OKand? / or?Calvar et al. 16. Data-aware constraints Issue #2: the specication 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 specicationCalvar et al. 17. Separation of concerns Monitor and specication become tangled: loss of separation of concernsSystemMonitorSpecication}EventVeries that Gives conditions onEvent sequence ofevents and... events followsspecication sequences of events allowed to happenin realtime The execution of the system produces eventsCalvar et al. 18. Data-aware constraints Issue #3: current monitoring frameworks are very language-dependent; the specication contains code in the systems native languageCalvar et al. 19. Separation of concerns Monitor and system become tangled: loss of separation of concerns (again)SystemMonitorSpecication}EventVeries that Gives conditions onEvent sequence ofevents and... events followsspecication sequences of events allowed to happenin realtime The execution of the system produces eventsCalvar et al. 20. 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 specication from the algorithm to verify itCalvar et al. 21. Monitoring frameworkPointcut Eventm formatterMonitorAdviceOutcome executionProgramAspect 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 Specication is expressed as constraints on sequences of XML structures -> system-independentCalvar et al. 22. Event formatting Example: a call to myBank.withdraw(123, 500) is formatted as Method namewithdraw123 Method arguments, named as500 in the methods prototype For a message m, data can be referred to by a path expression ; hence if = call/method/act, m() = "123"Calvar et al. 23. 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 = ybetween a path expression and a constant(a/b/c = d)Calvar et al. 24. 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 satises Calvar et al. 25. Properties on event sequences - First-order quantiers 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 trueCalvar et al. 26. Properties on event sequences S1. No operation on an account can be made after closeG (call/method = close a call/act : X G ( a call/act : a a ))Calvar et al. 27. Writing the specification PROTOTYPES void Bank.open(int act); Method calls to void Bank.close(int ac); intercept void Bank.withdraw(int act, int amount); boolean Bank.isApproved(int act, int amt); SPEC LTL-FO+ G ((call/method/close) -> ([a1 call/act] Property to (X (G ([a2 call/act] (!((a1) = (a2)))))))) monitor @FALSE {Action to take System.out.println("This is forbidden");if property is } violated PROTOTYPES shields the property from language- specic considerationsCalvar et al. 28. Properties on event sequences For Java, a PHP script converts the PROTOTYPES section into the appropriate event formatter, and the @FALSE section into the appropriate advice executor... PointcutEventmformatter Monitor AdviceOutcomeexecutionProgram Aspect...the monitor itself is always the same!Calvar et al. 29. Non-primitive objects What if the methods arguments are not primitive types? Example:Account a = new Account(...);myBank.withdraw(a, 500);withdrawWhat is the accounts "value"?500Calvar et al. 30. Non-primitive objects Observation: runtime constraints are expressed about objects specic properties that ultimately boil down to primitive typesAccount 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 elds of the object (not the full object), but only those necessary for the constraint to monitorCalvar et al. 31. Non-primitive objects Example: PROTOTYPES void AdvancedBank.getAuthorization (Account a, int amount); getAuthorization Message template used {return.getId()} by event formatter for {return.getAmount()} this method call void AdvancedBank.withdraw(Account a, Authorization auth); Code to execute on withdraw callee or its arguments {auth.getId()} to populate element {auth.getAmount()} with primitive value Calvar et al. 32. 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 le and veried a posteriori; would be impossible if events contained references to raw Java objectsCalvar et al. 33. 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 simplies the property to monitor - Surprising nding - See paper, "autonomous" vs. "query" approach in experiments - Work in progress: systematize this observation ("piggyback runtime monitoring")Calvar et al. 34. Experiments Runtime monitoring framework tested on the "simple" (primitive) and "advanced" (non-primitive) Bank examples, with randomly generated calls 60Number of traces 50 40 30 20 100[-.08, [-.04,[-.02, [0, [.02,.08) [-.06,-.03) [-.03,0) [0,.02) [.02, [.04,.08)-.04)-.02) 0) .02) .04) S1S2 Overhead per method call (ms)Simple bankCalvar et al. 35. 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 eventCalvar et al.


View more >