Mining Finite-State Automata with Annotations - Mining Software Specifications: Methodologies and Applications - page 53

depends on the nature of traces, the characteristics of the applications, and
the kind of analysis that these models should support.
2.7 Related Work
We already discussed techniques that generate FSAs and annotated FSAs
from execution traces in Section 2.2. Here we discuss other techniques that
generate models that represent either the ordering of the events or the values
that can be assigned to the program variables.
2.7.1 Mining Models That Represent Ordering of Events
Some mining techniques derive models different from FSA to represent in-
formation about the ordering of events. Some techniques simply derive a visual
representation of the execution traces without mining any extra information
that is not already in the traces. These techniques are useful to simplify the
manual inspection of execution traces, but do not derive compact representa-
tions of the (general) program behaviors. For instance, techniques presented
in [14, 22] can represent execution traces as sequence diagrams.
Other techniques analyze execution traces to derive frequent patterns of
events [8,16,26]. Frequent patterns can be useful to discover anomalous behav-
iors, but their usage is restricted to anomalies that impact the frequent events.
On the contrary, FSAs represent the entire behavior of a software program
and can include all the events recorded in execution traces. Thus, FSAs can
discover anomalies impacting any behavior of a software program, regardless
the frequency of these behaviors. The cost of this wider scope of the model is
a stronger dependency of the quality of the model on the completeness of the
samples used to infer the model.
Other techniques mine temporal rules that capture a set of dependen-
cies between events [17, 29]. These models focus on the relations between key
events, rather then the exact ordering of the single events. Temporal rules
have an interesting complementarity with respect to FSA: Temporal rules can
suitably represent relations between events occurring at arbitrary points of an
execution, while FSAs can well represent relations between non-consecutive
events only by suitably representing the relations between the intermediate
events, which is typically harder to achieve. This complementarity has been
exploited in [18, 27] to derive FSAs that satisfy inferred relations between
events that occur at arbitrary points within traces.
Yet other techniques mine algebraic specifications and graph transforma-
tions from program traces. They rely on a ground mathematical background
and can compactly represent a large number of behaviors [12, 15], but so far,