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

they have been applied only to rather simple software components (single
classes and containers), while FSAs have been shown to be useful with a
broader set of applications.
2.7.2 Mining Models That Represent Program Variables
Several techniques can infer models on the values assigned to program vari-
ables during program executions. Such data-oriented models well complement
FSAs that focus on the ordering of the events rather than on the data values
that occurred in a given execution.
A well-known technique for inferring models that represent the values that
can be assigned to program variables is Daikon [9]. Daikon accepts a set of
variables and their values across several executions as input, and generates a
set of Boolean properties on these variables. Daikon is integrated in gkTail to
derive transition constraints.
Hangal and Lam present a technique for generating models about program
variables expressed as bit masks [13]. The technique traces the values of these
variables across multiple executions and builds a model out of these obser-
vations. The technique is very ecient, but the derived models are of little
use for tester designers because they do not explicitly represent meaningful
relations. These models can be hardly integrated with FSAs because they rep-
resent code level information useful for fault-localization, but less useful for
understanding executions.
A complementary approach about models that capture program properties
that may involve multiple program variables is the case of models on single
variables. For instance Raz et al. generate statistical indexes that represent
the range of values assigned to single variables in order to automatically detect
anomalous values in new executions [25].
2.8 Concluding Remarks
In this chapter we illustrated two algorithms, gkTail and KLFA, that can
infer finite state models from traces. Differently from classic FSAs that rep-
resent only the ordering of events, gkTail and KLFA models have the unique
capability of representing the interplay between the ordering of events and
the values of attributes. The two algorithms differ in the way attributes are
handled. gkTail produces EFSAs where transitions are annotated with con-
straints that indicate the legal values of attributes. KLFA produces FSAs that
represent the recurrence of attribute values with symbols added to transition
labels. These two aspects are complemental and useful, as also confirmed by
the early empirical results.