Information Technology Reference
In-Depth Information
def
= {
Example 3.
Two examples of constraint expressions on an automaton with
Σ
a
,
b
}
,
the latter being a DCE.
}
2
·
a
,∅
3
·
b
}
∗
{{
5
(1)
{{
5
}
2
·
a
,∅
3
·
b
}∨{∅
3
·
a
,{
2
}
2
·
b
}
(2)
3.5
Evaluating Constraints
The functioneval
v
(
˙
) evaluates a DCE
˙
C
C
on an aggregated event input
v
, and is defined
as follows:
def
=
eval
v
(
⊥
)
false
eval
v
(
C
M
i
·
a
∈
C.
M
i
∨
def
= ∀
#
a
=
)
= ∅∧
M
M
)
#
a
≥
∧
loops(#
a
−
∅∧
i
i
,
eval
v
(
C
1
∨
C
2
∨...∨
C
n
)
=
eval
v
(
C
1
)
∨
eval
v
(
C
2
)
∨...∨
eval
v
(
C
n
)
def
Assuming that
Mods
i
returns the member of
Mods
at position
i
based on some ordering,
loops is defined as:
|
Mods
|
Mods
)
def
∈ N
|
Mods
|
.
loops(
N
,
= ∃
k
Mods
i
×
k
i
=
N
i
=
1
The predicate loops holds when there exists a set of coe
cients such that, when mul-
tiplied by members of
Mods
, will result in the sum of the products being equal to
N
.
Example 4.
loops(7
,{
2
,
3
}
) is true, as 2
k
1
+
3
k
2
=
7for
k
1
=
2,
k
2
=
1.
3.6
Traversing a Constraint Automaton
Algorithm 1 details a general approach to traversing a constraint automaton. The algo-
rithm is designed for online use, with the blocking nextInputEventCount() function
returning aggregated event counts collected by the monitoring system. Naturally, this
can readily be adapted for o
ine inputs.
When traversing an automaton, the algorithm must evaluate the constraint expression
for each transition leaving the current state (line 9). Multiple constraint expressions may
evaluate to
true
simultaneously, which results in a set of possible next states. Thus, the
current automaton state must be modelled as a set of states, with the automaton poten-
tially being in any of those states. This non-determinism may arise even if the original
automaton was deterministic. For example, while the automaton illustrated in Figure
1 is deterministic, it has branches that accept two traces with di
ff
ering order but equal
event frequencies. Its constraint automaton (Figure 5) is thus a
icted by ambiguity, as
an aggregated input of two events would lead to the automaton potentially being in ei-
ther
A
2
or
B
2
. A subsequent event would cause the automaton to converge onto
B
3
.As
we detail in Section 5, determinizing the constraint automaton would not help, as the
