LearnLib
Contents |
A Library for Automata Learning and Experimentation
The LearnLib is a library for automata learning and experimentation. Its modular structure allows users to configure their tailored learning scenarios, which exploit specific properties of the envisioned applications. As has been shown earlier, exploiting application-specific structural features enables optimizations that may lead to performance gains of several orders of magnitude, a necessary precondition to make automata learning applicable to realistic scenarios.
The demonstration of the LearnLib will include the extrapolation of a behavioral model for a realistic (legacy) system, and the statistical analysis of different variants of automata learning algorithms on the basis of random generated models.
Motivation
Most systems in use today lack adequate specifications or make use of un(der) specified components. In fact, the much propagated component-based hard- and software design style naturally leads to under specified systems, as most libraries and third party components only provide very partial specifications. To improve this situation automata learning techniques have been proposed. They enable the automatic construction and subsequent update of behavioral models.
Automata Learning
Automata learning tries to automatically construct a finite automaton that matches the behavior of a given target automaton on the basis of (systematic) observation . This complements other automatic learning techniques which aim at the construction of invariants. The interested reader may refer to for our (practice-oriented) view of the use of (active) learning.
Active learning assumes an omniscient teacher which is able to answer membership and equivalence queries. A membership query tests whether a string (a potential run) is contained in the target automatons language (its set of runs), and an equivalence query compares the hypothesis automaton with the target automaton for language equivalence, in order to determine whether the learning procedure was successfully completed.
In any practical attempt of learning legacy systems, equivalence queries can only be treated approximately, but membership queries can be answered by testing the target systems. The LearnLib therefore provides a number of heuristics and techniques for this approximation.
The LearnLib provides a platform for experimenting with different learning algorithms and for statistically analyzing their characteristics in terms of required number and size of e.g., membership queries, run time, and memory consumption. This concerns in particular the analysis of the impact of the various techniques for optimizations.
Besides the fine granular analysis for understanding the individual components of typical learning algorithms, the LearnLib can also be used as a fully automatic tool to systematically build finite state machine models of (specific aspects of) real world systems.
The LearnLib consists of three modules:
- the automata learning module containing the basic learning algorithms,
- the filters module providing a number of strategies to reduce the number of queries, and
- the module for approximative equivalence queries, which is based on techniques adopted from the area of conformance testing. suites for the conjectures of the learning algorithms.
Automata Learning with the LearnLib
The main module of the LearnLib contains learning algorithms of different flavor. Currently, the LearnLib only supports some variants and extensions of Angluin's algorithm L* .
Angluin's algorithm works on deterministic finite state machines, which, as usual, consist of a finite set of states Q , a finite (input) alphabet S , a transition function d : (Q x S) ? Q , and a finite set of accepting states F ? Q .
Typical reactive systems do not terminate and are thereforer not modelled appropriately with accepting states. It turned out that Mealy machines, which adequately model input/output behavior provide a much better modelling, which is not only more concise, but can also be learned much faster. The LearnLib therefore provides learning algorithms for both, finite state machines and an adaptation to Mealy machines. These versions can be used in two modes: an automatic mode, which automatically proceeds in a predefined fashion, and an interactive mode, which gives the user a handle to steer the learning process in more detail.
The learning algorithms can be freely combined with a number of filters, optimizing the number of required membership queries, and with an adequate approximate solver for equivalence queries. Whereas these approximate solvers are necessary, whenever one attempts to learn a legacy system, they can can be replaced by a perfect equivalence checker for the statistical analysis of learning scenarios using randomly generated target models. The LearnLib provides a bisimulation checker for this purpose.
Simulation and Analysis of Learning Algorithms
Different learning algorithms have very different characteristics. Perhaps most importantly, they may drastically differ in the number of membership- and equivalence queries, but they also differ in the size of their queries. Our simulator analyzed these differences, and helps to gain knowledge about how learning algorithms essentially work, and where their bottlenecks lie.
Such studies are specifically supported be the LearnLib, which, besides the configuration of individual learning scenarios, also allows the configuration of whole scenarios for the statistical analysis of learning scenarios. In fact, as will be illustrated during the demonstration, it is possible to configure a set of comparative learning scenarios and to automatically generate the corresponding comparative statistical charts.
