Databases Reference
In-Depth Information
clearly overfits the observed behavior. gkTail and KLFA extract information
from attribute values and synthesize automata that generalize the observed
behaviors.
2.4 Inferring FSA Annotated with Constraints
In this section we present gkTail [19], a technique to automatically generate
Extended Finite State Automata (EFSA), that is, automata augmented with
constraints on transitions. gkTail derives EFSA from a set of interaction traces
(positive samples) that include information about both the ordering of the
events and the values of the attributes associated with the events, such as the
ones shown in Figure 2.2. gkTail processes traces in four steps:
1. merge similar traces
2. generate constraints associated with the events in the traces
3. produce an initial EFSA
4. merge equivalent states in the EFSA
In the first step, gkTail identifies similar traces, namely, traces with the
same sequences of method invocations and possibly different values of the
parameters, and merges sets of similar traces into traces where method invo-
cations are annotated with sets of attribute values. In the second step, gkTail
derives constraints that represent the set of attribute values associated with
the same method invocation. In the third step, gkTail creates an initial EFSA
from interaction traces annotated with constraints. In the fourth step, gkTail
iteratively merges states that can accept similar sequences of method calls.
Hereafter, we describe in detail the four steps referring to the running
example introduced in Section 2.3.
2.4.1 Merging Similar Traces
In the first step, gkTail processes a sequence of interaction traces
fit
1
:::it
m
g. Each interaction trace is a sequence of inter-component method
invocations. An inter-component method invocation in the jth trace is a tuple
(x
j
i
;p
j
1
x
i
:::p
j
n
x
i
), where x
j
i
is the signature of the ith invoked method, and
p
j
1
x
i
:::p
j
n
x
i
are its parameter and return values, if any. Figure 2.2 shows four
examples of interaction traces collected from the execution of the running
example.
When the monitored component executes similar tasks, we obtain similar
traces, namely, traces that share the same sequence of method invocation, and
Search WWH ::
Custom Search