Information Technology Reference
In-Depth Information
next state, assuming the worst-case scenario of a fully-connected aggregate automaton
and a full current state set, is:
|
current
states
|
Q
×|
|
constraint
expressions
Q
×
vecs
vectors
/
CE
×|Σ|
basic
constraints
/
CV
×
(
mods
!
modulo
set size
/
BC
+
1
o
ff
set
comparison
)
As noted earlier, the magnitude of
mods
and
vecs
is dependent on the form of the ex-
tracted regular expressions, specifically the number of cycles and choice operators, re-
spectively. Evaluating the modulo set requires calls to loops(), which has a worst-case
running time that is factorial to the input size. As will be discussed in Section 6, in
practice, one can lower the average running time by ordering the evaluation of con-
straints based on their weakness, and by using more sophisticated techniques for solving
loops().
Implementation Considerations
A notable feature of constraint automata is that the running time is independent of
the number of events encoded in an aggregated event burst. An indirect correlation
may exist, as a large number of such events would be more likely to lead to multiple
next states, which would consequently enlarge the current state set. The use of a set
of current states could be eliminated by making the automaton deterministic, yet this
generally results in an exponential growth in states, increasing the number of constraint
expressions to be evaluated at every state by an equivalent degree. By maintaining a
dynamic set of current states, one can thus reduce the average traversal time, as only
the outgoing transitions from potential current states are evaluated.
In this work, we have opted to use regular expressions to produce an initial constraint
automaton so as to modularize the transformation stages. It is possible that some per-
formance gains may be obtained by generating constraint expressions directly from the
original automaton. More specifically, this may allow the detection of sub-expressions
that are shared across constraints, facilitating the caching and reuse of partial results
during constraint evaluation. Optimizations could also extract common sub-expressions
among constraint expressions emanating from states, rather than evaluating each out-
going transition in isolation. Such considerations could give rise to interesting future
work.
A system implementing constraint automata would most likely benefit from chang-
ing the representation from the one used into one that is more amenable to comparisons.
For example, constraints could be organized in a tree structure based on their o
set val-
ues, speeding up evaluation by excluding branches which do not meet the minimum.
ff
6
Related Work
Instrumentation is recognized as a source of overhead in runtime verification. This over-
head can be reduced by decreasing the amount of instrumentation, or
sampling
,thatis
