Information Technology Reference
In-Depth Information
a
a
a
2
2
2
2
2
2
c
1
5
c
1
5
c
1
5
b
b
b
a
1,2
2
2
1
LSP
=1
1
c
5-7
c
2
6-7
c
2
6-7
c
2
6-7
b
3
1
1
1
1
3
2
2
2
d
9
d
9
d
9
d
9
LSP
=3
1
1
1
1
10
10
10
10
1
1
1
1
f
f
f
f
(a) CFG
(b) Step 1
(c) Step 2
(d) Step 3
Fig. 3.
Steps for obtaining optimized instrumentation and sampling period
graph,
CFG
, where critical instruction
inst
in
v
changes the value of a variable
a
∈V
Π
. We insert an instruction
inst
:
a
←
a
immediately following
inst
,where
a
is an auxiliary memory location, to the sequence of instructions corresponding
to vertex
v
. After instrumenting (i.e., adding
inst
)
v
,
v
is no longer a critical
basic block (i.e.,
v
V
c
) because the added instruction guarantees that
the monitor will observe this change when it processes the history stored in
auxiliary memory. For example, instrumenting vertex
c
2
in Figure 3(c) by adding
an instruction of the form '
ch=c
' directly after line 6 of the program results
in the CFG shown in Figure 3(d). Instrumenting the critical instruction in
c
2
effectively increases the LSP to 3 because of the buffered event. The maximum
violation detection latency
(i.e., the time elapsed between the occurrence of a
property violation and the detection of the violation) of Π, the availability of
auxiliary memory and other system constraints limit the number of times we
can apply step 3 to increase the LSP.
∈
V
\
3 Hybrid Event-Triggered and Time-Triggered Runtime
Verification
In this paper, our goal is to select the monitoring scheme that minimizes the ex-
pected total overhead incurred from executing the monitor. In order to formally
introduce the problem statement, we need to define the underlining monitoring
overhead cost model.
3.1 Overhead Runtime Costs
Broadly, we classify the
overhead costs
incurred from monitoring into three cat-
egories:
