Lo D., Khoo S.-C., Han J., Liu C. Mining Software Specifications. Methodologies and Applications

CRC Press, 2011. — 450 p.Data mining and machine learning techniques have been used to learn models of software behavior. These models appear in various forms following different formalisms of software specifications, each capturing different aspects of a software system. The mined models can later be tuned, adapted, and used for various purposes.
Mined models help in understanding existing systems and hence reduce the cost incurred during software maintenance (i.e., when features are added, bugs are fixed, etc.). This is particularly advantageous in the cases of maintaining legacy systems and keeping pace with changes in evolving systems, where significant maintenance cost can be saved through better understanding of such systems with the help of mined models.
The mined models/specifications can also be used to aid program testing efforts and help program verification tools to _nd bugs and ensure correctness of systems. As reported by US National Institute of Standards and Technology (NIST) in 2002, bugs have been causing US economy to lose 59.5 billion dollars annually. Also, the first test ight of Ariane 5 ended up in an explosion due to a software bug. Automated methods to _nd bugs and ensure correctness of systems are certainly valuable.
There has been a proliferation of research in the area of specification mining in both academia and industry. Research and development in specification mining have been performed in various institutions across the globe with results presented in various venues such as conferences on software engineering, programming languages, data mining, and databases. Due to its appearance in a wide range of research domains, it is often hard to find and relate different works on mining specification in the literature. There has not been a single reference to describe and categorize these studies in a unified setting. This book aims to serve as the first reference to the wealth of knowledge in this new emerging field of mining software specifications.
There are diverse forms of target formalism considered in various research work. Two of the most common ones are finite state machines and rules/patterns of behavior. A finite state machine is typically larger and captures more complex behavior. Many works on mining finite state machine extract models that capture the overall behavior of a system. A set of rules or patterns tends to be smaller and decompose complex behavior into simpler parts. Much work on mining rules/patterns extracts strongly observed sub-behaviors either in terms of their frequency of appearance or some other statistical measures. In this book, we present in detail a number of past studies on mining finite state machines (Chapters 2-6) and also those on mining rules/patterns (Chapters 7-12).
There are also differences in terms of how the raw data used as input for the mining and learning tasks are obtained. Some works analyze program code (i.e., static analysis) while others analyze execution traces (i.e., dynamic analysis). There are also works that analyze both code and execution traces. Either static or dynamic analysis has its own advantages and disadvantages. Static analysis could potentially consider all possible behaviors as all the behaviors of the system are in the code. Dynamic analysis on the other hand only analyzes a sample of the behaviors of a system exhibited on a set of runs of a system. However, dynamic analysis can be more precise as exact events that happen during runtime are collected rather than inferred. Its performance is not affected by the difficulties arising from dealing with infeasible paths in a software system or pointer analysis. This book presents both approaches and even some synergies of the two: Some chapters present works that employ dynamic analysis, some others present works that employ static analysis, and yet a few present works that employ a combination of both static and dynamic analyses.Specification Mining: A Concise Introduction
Mining Finite-State Automata with Annotations
Adapting Grammar Inference Techniques to Mine State Machines
Mining API Usage Protocols from Large Method Traces
Static API Specification Mining: Exploiting Source Code Model Checking
Static Specification Mining Using Automata-Based Abstractions
DynaMine: Finding Usage Patterns and Their Violations by Mining Software Repositories
Automatic Inference and Effective Application of Temporal Specifications
Path-Aware Static Program Analyses for Specification Mining
Mining API Usage Specifications via Searching Source Code from the Web
Merlin: Specification Inference for Explicit Information Flow Problems
Lightweight Mining of Object Usage