Specification Mining: A Concise Introduction - Mining Software Specifications: Methodologies and Applications - page 3

mining has been ongoing for over a decade and more than 50 papers have
been published on this topic. We provide a brief summary starting from one
of the first papers on this topic published in 1995 by Cook and Wolf [14], to
many recent papers. The remaining chapters of this topic describe 11 dierent
techniques appearing in recent literature in detail.
Section 1.2 describes a general scheme to categorize existing works into sev-
eral groups. Section 1.3 describes studies on the extraction of finite state ma-
chines. Section 1.4 describes works that mine for value-based invariants. Sec-
tion 1.5 describes approaches to mine rules and patterns. Section 1.6 presents
yet another family of studies extracting sequence diagram-like specifications.
We conclude our discussion in Section 1.7.
1.2 Categorization
There are various ways to organize the many studies on specification min-
ing. We choose to categorize them in terms of the specifications forms pro-
duced by the miners. These include finite state machine or automata, value-
based invariants, patterns/rules, and sequence diagram-like representations.
Some examples of studies mining the various specification formalisms are
shown in Table 1.1. 1
A finite state machine consists of states and transitions. The states or the
transitions could be labeled { depending on whether a Mealy or Moore ma-
chine is mined. These labels could correspond to various pieces of information
depending on the level of granularity considered. Typically, the labels corre-
spond to method calls of interest. Most studies on the extraction of finite state
machines listed in Table 1.1 propose the extraction of models governing the
order in which methods of a particular library could be invoked. An example
of a model specifying how a file access library should be used is shown in
Figure 1.1. The finite state machine specifies that a call to open needs to be
made before any call to read or write. At the end of an interaction, with the
library a call to close is made.
A value-based invariant captures a constraint among various global or local
variables at a particular point in a program. Various constraints could be
considered ranging from a simple equality constraint involving two variables/
-values to more complex inequalities or even conditional constraints involving
multiple variables. Value-based invariants thus capture the constraints among
the various variables characterizing a system's state. An example of a value-
based invariant is shown in Figure 1.2. It illustrates that at the end of a simple
program that computes a square, the computation result is greater than or
equal to zero.
1 Our list might not be complete.