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

cations from natural language documentations (specifically Javadocs). These
Javadocs are analyzed to form action-resource pairs. These pairs are later
combined into a finite state machine. They have shown that the generated
finite state machines are accurate and are able to detect bugs.
Gabel and Su propose an online specification mining approach [28]. Rather
than performing an oine mining on a set of traces, they devise a technique
to perform mining at the same time as traces are generated. A trace is pro-
cessed window by window. Specification is mined/updated based on informa-
tion collected in each window. Mining and checking of mined specifications
are performed along the way as new traces are collected.
1.4 Mining Value-Based Invariants
In this section, we describe past studies mining value-based invariants.
The pioneer work in extracting value-based invariants is Daikon by Ernst
et al. [23{26]. Daikon contains many value-based invariant templates. It mon-
itors a program in execution and matches one or more invariant templates
to particular program points of interest. It then reports the invariants that
holds at the program point. Various filtering and template selection strategies
are provided by Daikon. Daikon is also integrated with constraint solvers to
reduce the redundancy in the mined invariants. Optimization strategies have
also been proposed to speed up the extraction of value-based invariants, e.g.,
by incremental detection of invariants [57].
Many other studies leverage Daikon to perform other software engineering
tasks. For example, Nimmer and Ernst integrate Daikon with ESC/Java to
evaluate the effectiveness of the mined invariants in, detecting bugs via static
analysis [56]. Pytlik et al. leverage Daikon invariants for fault localization [59].
Given a set of execution traces that fail and those that are successful Pytlik
et al. find invariants that discriminate failing and correct traces in an effort
to localize or pinpoint the wrong statement which is the root cause of the
failure. They encounter a negative result in their experiment as many of the
invariants are not related to bugs. Their study is later extended by Brun and
Ernst in [11]. The latter study is able to show that with machine learning,
Daikon invariants could be used to localize bugs. Demsky et al. use Daikon
to learn data structure consistency invariants for automatic data structure
repair [18].
In several studies the work on mining value-based invariants is combined
with mining other invariant types. For example, Ramanathan et al. mine both
value-based invariants and precedence rules as pre-conditions of various meth-
ods using an inter-procedural path-sensitive static analysis [62]. Lorenzoli et
al. integrate Daikon invariants into a finite state machine inference algorithm