Databases Reference
In-Depth Information
4.6.2 Mining of Temporal Rules and Other Specifications
Besides specification miners that produce FSMs, numerous approaches to
infer other kinds of rules and recurring patterns from programs have been
proposed. Zhong et al. [44] produce graphs that describe dependencies between
API method calls based on known facts, such as that arrays must be initialized
before writing to them. Acharya et al. [3] mine frequent partial orders of
method calls from static traces extracted with a model checker. Henkel et
al. [18] infer algebraic specifications for Java container classes, which describe
equalities resulting from different sequences of method calls.
Several static rule miners are presented together with bug finding tech-
niques that exploit rarely occurring violations of the inferred rules. Engler
et al. [13] statically detect frequently occurring instances of predefined rule
templates and check violations of the rules. Li and Zhou [21] mine associa-
tion rules that relate functions or variables that are often used together and
present call paths where those rules may be violated to the user. Weimer and
Necula [40] extract pairs of methods that occur together in exception handling
paths and use them to identify potential bugs. Thummalapenta and Xie [38]
mine sequence association rules in exception handling code and use anomalies
to identify bugs. Wasylkowski and Zeller [39] learn conditions that should be
fulfilled before passing a particular parameter to a method and search bugs
through anomalies. Nguyen et al. [28] present a graph-based miner of usage
protocols that can be used to identify bugs and to provide code skeletons
showing a usage scenario. The specifications inferred by our analysis could be
combined with existing bug-finding techniques. Having a scalable analysis for
mining usage patterns that can analyze many different API clients leads to
more complete specifications, and hence, reduces the problem of false warnings
reported by a checker.
Among the dynamic approaches to infer usage rules, Yang et al. [43] also
focus on scalability. Their approach is, similar to [15], based on predefined
templates. Salah et al. [34] infer usage scenarios for a class by grouping simi-
lar method invocation sequences on instances of this class into canonical sets.
Lo and Maoz [25] infer scenario-based specifications and present them hierar-
chically, which allows users to inspect them at different levels of abstraction.
An alternative source to infer typical programming patterns is the history
of version control systems. Livshits and Zimmermann [23] mine association
rules from sets of methods that are checked-in together. Similarly, Williams
and Hollingsworth [42] infer relations between pairs of methods from version
control histories. Liu et al. [22] propose a method for checking the likelihood
of API usage patterns using a model checker that counts the number of val-
idations and violations for each pattern. Such an approach could be used to
further filter the protocols found by our analysis.
Search WWH ::
Custom Search