Information Technology Reference
In-Depth Information
monitor takes; a
'redundant' sample
is an invocation of the monitor, where there
are no events to process in the buffer. The dashed ovals in Figure 1(b) mark
the redundant samples in this example. Although our goal in [2, 3] was tack-
ling the unpredictability of runtime overhead, we observed that time-triggered
runtime verification (TTRV) may also reduce the cumulative runtime overhead
effectively.
From Figures 1(a) and 1(b), it is evident that both event- and time-triggered
monitoring techniques have some advantages and disadvantages with respect to
the monitor's execution overhead. Event-triggered monitoring tends to be ad-
vantageous in situations, where critical events occur sparsely since the monitor
is active only when the program encounters a critical event; time-triggered mon-
itoring tends to be better when many critical events to process within a short
time frame.
With this motivation, in this paper, we propose a novel technique based on
static analysis that exploits the benefits of both ETRV and TTRV to reduce the
runtime overhead, which we call
hybrid
runtime verification (HyRV). Our goal
is to supply a program under scrutiny with a monitor that supports both ET
and TT modes of operation. The program switches from one mode to another
at run time depending upon the current execution path. HyRV automatically
obtains the locations to
switch modes
in the program by solving an optimization
problem; this method accounts for all monitoring and switching costs in terms
of execution time overhead. The main challenge in formulating the optimization
problem is threefold:
1. determining the precise timing behaviour of the program under inspection,
2. identifying the overhead of all required activities for implementing an ET
or TT monitor (e.g., cost of monitoring mode switching, sampling, monitor
invocation),
3. identifying the execution subpaths that are likely to be suitable for ET and
TT monitoring modes.
The solution to the problem is an instrumentation scheme for a program
that may switch monitoring modes at runtime. For instance, in Figure 1(c),
the reduction in monitoring activity will likely reduce the overall monitoring
execution overhead. Obviously, using hybrid monitoring will incur overhead costs
in performing mode switches. In this example, a mode switch occurs right before
i
and right after
j
to switch from ET to TT and TT to ET monitoring modes,
respectively.
We implemented this technique in a toolchain that leverages static analysis
techniques and integer linear programming (ILP) to solve the optimization prob-
lem. The input to our toolchain is a C program and a set of variables to monitor.
The toolchain outputs the program source code augmented with the instrumen-
tation scheme that may toggle the monitoring mode at runtime to reduce the
monitoring overhead. Currently, our toolchain does not include static analysis of
library calls. The results of our experiments on a benchmark suite for real-time
embedded programs strongly validate the effectiveness of our technique.
