Information Technology Reference
In-Depth Information
Where
Δ
π
is set of longest subpaths of
π
whose vertices are monitored using TT
scheme. Three sums in equation 2 correspond to
C
event
,C
switch
,
and
C
sample
costs respectively. Let
Π
denotes set of all execution paths of CFG
G
,theover-
head of a monitoring scheme
M
for program
P
with CFG
G
is:
M
o
(
G
)=
π∈Π
M
o
(
π
)
(3)
3.3 Complexity Analysis
We believe that finding the monitoring scheme 1, which minimizes the over-
head cost (Equation 3) for a given CFG, requires knowledge of execution paths
of the CFG. This is because depending upon what had happened on a path it
may not be beneficial to switch to the optimal monitoring scheme for the rest
of the path. Such an interference is not only present in an execution path but
also among interacting paths. To illustrate this further consider Figure 4. In an
optimal solution, the distribution of critical events on the path
c
d
affects the
decision about the monitoring mode (i.e., TT or ET) for vertices on the path
a
and vice-versa. It may not be correct to choose optimal strategy for the
paths
d
separately if it causes switching on edge (
a,c
), and the cost
of this switching overruns the benefit gained by choosing local optimal solutions
for the two paths. This causes intra-path interference among vertices. Note that
monitoring mode decision about vertices on the path
a
and
c
b
is influenced by choice
of monitoring mode for virtices on the path
c
d
which in turn gets affected by
events on the path
a
. This results into inter-path interference among inter-
secting paths. The presence of intra- and inter-path interference among vertices
indicates that local optimization cannot guarantee overall optimal solution for
a given CFG, and all execution paths should be analyzed. However, the pres-
ence of unbounded loops makes analysis of all execution paths impossible. Also,
even in the absence of unbounded loops, a general CFG can have exponentially
many execution paths. This makes the problem of finding the optimal solution
intractable.
In order to tackle the high computational complexity of the problem and to
make this technique practical, we introduce a heuristic that aims to return a
monitoring scheme whose monitoring overhead is equal to or better (i.e. lower)
than exclusively in ET or TT schemes. We formulate an
integer linear program
(ILP) as a heuristic for this problem. In order to make this heuristic reflect
the realities of the program without computing all execution paths, we assume
that function
F
:(
u,v
)
→
N
,(
u,v
)
∈
A
,
u,v
∈
V
is provided along with CFG
of a program
P
.
(
u,v
) defines the expected number of times
P
will execute
the basic block corresponding to
v
immediately after executing the basic block
corresponding to
u
. Figure 5 illustrates a
CFG
, where the critical vertices are
highlighted. The set of numerical values within parentheses defines the function,
F
F
(
u,v
). We note that this function can be evaluated using standard techniques
such as program profiling and symbolic execution. The suboptimality stems from
the division of the program into subpaths to estimate the monitoring cost and
