Databases Reference
In-Depth Information
to mine specifications that capture both the temporal ordering constraints
and invariants among values/variables [49]. Lo and Maoz also extend their
algorithm with Daikon to enable the extraction of sequence diagrams in the
form of Live Sequence Charts with value-based invariants from program exe-
cutions [45].
1.5 Mining Patterns and Rules
In this section, we describe past studies mining rules and patterns.
Engler et al. are among the first pioneers in proposing statistical ap-
proaches to nd bugs [21]. Their tool is built upon the tenet: \If two beliefs
contradict, we know that one is an error without knowing what the correct
belief is." Their system works on a set of templates that associates a few vari-
ables together, e.g., \Does lock hLi protect a resource hRi?" \Must IS ERR
be used to check the return value of function F?" etc. Instances of these tem-
plates with sucient statistical values are then identified. Violations of these
instances are reported as potential bugs in a ranked list based on statistical
likelihood of them being errors.
El-Ramly et al. extract frequent patterns of usage termed as interaction
patterns from a set of sequences of events extracted from runtime program
executions [20]. They formulate a new frequent pattern mining semantics and
an ecient algorithm to mine the patterns. They applied their solution in a
software maintenance task. In particular, they show the viability of the mined
patterns in helping the migration of a legacy system to a new web-based
solution.
Li and Zhou propose an approach that mines for rules from program
code [37]. In their approach, every function is mapped into a transaction.
The database of transactions corresponding to functions in a program under
analysis is later mined. Association rule mining is employed to find rules that
satisfy minimum support and confidence thresholds. The mined rules are used
for the detection of anomalies.
Livshits and Zimmermann propose an approach that combines reposi-
tory mining with the analysis of program execution traces to infer specifi-
cations [35]. First, transactions are formed from sets of method calls that are
added together in a revision in a software repository. These transactions are
later subject to association rule mining to mine for rules satisfying minimum
support and confidence thresholds. Mined rules are later filtered and ranked.
For the remaining set of rules, a user can choose some of them. These selected
rules would be verified using a dynamic analysis approach. If there are many
violations of a rule in execution traces, the rule is less likely to be valid. On
Search WWH ::
Custom Search