Information Technology Reference
In-Depth Information
performed. Statistical methods can then be employed to infer the most probable se-
quence of state transitions that occurred during the time in which sampling was sus-
pended. For instance, Stoller et al. [12] consider the scenario where instrumentation is
suspended for some period of time, leaving a gap in the sequence of observed events.
Their approach focused on reconstructing the missed events via probabilistic models,
which estimate the next state based on traces that were observed previously. This ap-
proach di
ers from that explored in this work, as the gaps are devoid of information,
not even specifying the number of missed events. In contrast, our work only considers
unordered traces, and still requires that the number and type of events be logged.
Bodden et al. [5, 6] provide an implementation of e
ff
cient time-triggered automata,
which consider gaps of events during monitoring. The approach explored can report
false positives (but not false negatives) if continuously monitoring “skip” events that
prevent an error state from being reached.
Bartocci et al. [2] extend the concept of probabilistically monitoring gaps in events,
and introduce the notion of
criticality levels
, which vary based on the probability that
a system reaches an error state. Criticality levels can then be used to determine the
degree of instrumentation performed, with the system increasing sampling to determine
the precise system state. A similar concept could be integrated into the construction
examined in this work. For example, sampling could be increased on detecting that the
current state set contains a final state.
Another approach, adopted by Basin et al. [3], is to handle the uncertainty brought
about by incomplete traces using a three-valued logic, whereby the property's evalua-
tion function is modified to also reason about indeterminate results.
Bauer et al. [4] present a multi-valued logic that is able to express not only whether a
violation has taken place, but also whether a violation would occur if the trace terminated
right now. One could easily combine such acceptance conditions with our approach.
The choice of algorithm when generating regular expressions from a finite-state au-
tomaton will a
ect the size and complexity of the resultant expressions [10]. Bounded
iteration with choice produces constraint expressions with multiple constraint vectors.
In broad terms, unbounded iteration will cause the o
ff
set value to be added to the mod-
ulo set. Subsequent nesting of an iterated expression within unbounded iterations will
have no further e
ff
ect on the constraint expression's size. Ideally, the algorithm em-
ployed would thus minimize the number of choice operators in the output expressions.
Nevertheless, the upper-bound on running time remains independent of the number of
missed events. In addition, by isolating the ine
ff
cient component of the constraints into
modulo sets, one may choose to apply existing results and libraries addressing the
Sat-
isfiability Modulo Theories
problem [1] to speed up the computation.
7Con lu ion
We have presented a trace model that allows for the monitoring of distributed systems
by compressing partial event streams before they are sent to the monitoring server.
We described an algorithm for constructing ahead-of-time a monitor that can deal with
compressed event streams in such a way that it provably recognizes property violations
without false negatives. We have further shown that the resulting automaton is as precise
as possible, and has a complexity low enough to promise performance gains in practice.
