Databases Reference
In-Depth Information
Chapter 3
Adapting Grammar Inference
Techniques to Mine State Machines
Neil Walkinshaw
Department of Computer Science, The University of Leicester
Kirill Bogdanov
Department of Computer Science, The University of Sheeld
3.1
Introduction ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 59
3.2
The Conventional Reverse-Engineering Approach and Its Problems ::::: 61
3.2.1
State Machines and Their Languages ::::::::::::::::::::::::::::: 61
3.2.2
State Merging ::::::::::::::::::::::::::::::::::::::::::::::::::::: 62
3.2.3
Problems with This Approach :::::::::::::::::::::::::::::::::::: 64
3.3
Applying Advances from the Field of Grammar Inference ::::::::::::::: 66
3.3.1
Negative Samples :::::::::::::::::::::::::::::::::::::::::::::::::: 67
3.3.2
Improved State-Merging Heuristics ::::::::::::::::::::::::::::::: 67
3.3.2.1
Evidence-Driven State Merging ::::::::::::::::::::::::: 68
3.3.2.2
Blue-Fringe Search Strategy ::::::::::::::::::::::::::::: 70
3.3.3
Active Approaches :::::::::::::::::::::::::::::::::::::::::::::::: 71
3.3.4
Applying These Advances in Practice :::::::::::::::::::::::::::: 73
3.3.4.1
The Software System as Oracle :::::::::::::::::::::::::: 73
3.4
Integrating Constraints ::::::::::::::::::::::::::::::::::::::::::::::::::: 75
3.4.1
Integrating Data Constraints ::::::::::::::::::::::::::::::::::::: 76
3.4.2
Integrating Temporal Constraints :::::::::::::::::::::::::::::::: 76
3.5
Conclusions and Future Work :::::::::::::::::::::::::::::::::::::::::::: 79
Bibliography ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 80
3.1 Introduction
State-based models are valuable for a range of software development tasks.
They help the developer to understand how the system works. They formally
document the system behaviour. Most importantly, a range of powerful, au-
tomated model-based testing techniques can be used to rigorously test im-
59
Search WWH ::
Custom Search