Reducing Monitoring Overhead by Integrating Event- and Time-Triggered Techniques - Runtime Verification - page 304

Reducing Monitoring Overhead by Integrating
Event- and Time-Triggered Techniques
Chun Wah Wallace Wu 1 , Deepak Kumar 1 ,
Borzoo Bonakdarpour 2 , and Sebastian Fischmeister 1
1 Department of Electrical and Computer Engineering
University of Waterloo
200 University Avenue West
Waterloo, Ontario, Canada, N2L 3G1
{ cwwwu,d6kumar,sfischme } @uwaterloo.ca
2 School of Computer Science
University of Waterloo
200 University Avenue West
Waterloo, Ontario, Canada, N2L 3G1
[e-mail]
Abstract. Runtime verification is a formal technique used to check
whether a program under inspection satisfies its specification by using
a runtime monitor. Existing monitoring approaches use one of two ways
for evaluating a set of logical properties: (1) event-triggered ,wherethe
program invokes the monitor when the state of the program changes,
and (2) time-triggered , where the monitor periodically preempts the pro-
gram and reads its state. Realizing the former is straightforward, but the
runtime behaviour of event-triggered monitors are dicult to predict.
Time-triggered monitoring (designed for real-time embedded systems),
on the other hand, provides predictable monitoring behavior and over-
head bounds at run time. Our previous work shows that time-triggered
monitoring can potentially reduce the runtime overhead provided that
the monitor samples the program state at a low frequency.
In this paper, we propose a hybrid method that leverages the benefits
of both event- and time-triggered methods to reduce the overall monitor-
ing overhead. We formulate an optimization problem, whose solution is a
set of instrumentation instructions that switches between event-triggered
and time-triggered modes of monitoring at run time; the solution may
indicate the use of exactly one mode or a combination of the two modes.
We fully implemented this method to produce instrumentation schemes
for C programs that run on an ARM Cortex-M3 processor, and experi-
mental results validate the effectiveness of this approach.
1 Introduction
Runtime verification [5, 19, 26] is a technique, where a monitor checks at run
time whether or not the execution of a system under inspection satisfies a given
correctness property. The main challenge in augmenting a system with runtime