Information Technology Reference
In-Depth Information
Algorithm 1 On-line Traversal of a Constraint Automaton
Q
,
q 0 ,Σ,
F
1: Current ←{ q 0 }
Start at initial state
Perpetual loop
2: loop
if ( Current F
3:
) then
Check if potentially in a final state
4:
reportError( Current )
Report current state set
5:
end if
6:
v
nextInputEventCount()
Get next map of aggregated events
7:
next Q ←∅
Resetnextstateset
8:
for all c Current do
Determine next states for each current state
next Q next Q c | ( c ,
C )
C, c ) ∈Γ, eval v ( ˙
˙
9:
10:
end for
11:
Current next Q
Update with computed next states
12: end loop
0 · logout ,∅ 1 · login
1 · logout ,∅ 0 · login
A 1
A 2
1 · logout ,∅ 1 · login
2 · logout ,∅ 1 · login
S
1 · logout ,∅ 1 · login
0 · logout ,∅ 1 · login
B 1
B 2
B 3
1 · logout ,∅ 0 · login
1 · logout ,∅ 0 · login
Fig. 5. The constraint automaton derived from the automaton in Figure 1
resulting deterministic automaton would still require a transition function that evaluates
the same set of transition constraints.
The size of Current may grow as well as shrink, the latter occurring when parallel
traversals converge onto a state, or when members of the set do not lead to valid next
states under the observed input. As presented, the algorithm never halts, instead report-
inganerrorwhenever Current contains some final state. This policy over-approximates
error states, which may lead to false alarms. To reduce them, one may consider using
other policies, such as reporting errors only when Current is composed entirely of final
states. Alternatively, one may augment the automaton with probabilistic information,
terminating based on the likelihood that the system is in an actual error state.
4
Constructing a Constraint Automaton from a Property FSA
The following defines the process of deriving constraint automata from finite state prop-
erties. The transformation is performed in two phases. In the first phase, regular expres-
sions are constructed for every pair of states in the property. In the second phase, each
regular expression is subsequently transformed into a constraint on frequencies.
4.1
Translating Regular Expressions into Constraint Expressions
The process of translating a regular expression into a constraint expression involves
two steps. The first step transforms the regular expression into an initial constraint
Search WWH ::




Custom Search