Automata Learning (Basic)

How do we actually generate models?

To start learning behavioral models, it's useful to know a bit more about the techniques behind it. The learning setups HermieLab generates make use of a technique called automata learning. In this wiki, we will only summarise the basic concepts; a more detailed explanation and discussion can be found in [1].

Figure 1: Basic System Under Learning (SUL)

In Automata Learning, models of a target system, often called SUL (System Under Learning) are created by active interaction with them and reasoning about the observed output behavior. This is done by constructing queries, which are sequences of input symbols from an input alphabet that represents actions executable on the SUL, and answering these queries by means of actual execution. [2]

In Figure 1, an example SUL is shown. The SUL is a small GUI-Program with one button and a circle which can change color. The program can be started by calling it's 'main()' function. When the program starts, the circle is red. Whenever the user presses the button a 'press()' function is called, turning the circle green. If the user then drags the button a 'drag()' function is called which paints the circle yellow. When the user releases the button, a 'release()' function is called, painting the circle red. The program contains a 'reset()' function which can reset the program.

Figure 2: Basic Learning Setup

Just as physics expirements often require some kind of setup, learning experiments require learning setups.

A learning setup generally consists of 2 components: a Learner and a Teacher. The Leaner questions the Teacher and reasons about the observed output. The Teacher answers the learner. The Teacher is either the SUL itself or more often an adapter to the SUL. This is because generally, the SUL has no interface to apply test cases for realizing queries. After each query, the program should reset to its original state (Very important, this is the cause of many "bugs").

If we take our example SUL again, this means that we have 2 things. First, we have a Learner who will generate many queries based upon some learning algorithm. Secondly, we have a Teacher (adapter) which can fire the 'start()', 'press()', 'drag()', 'release()' and 'reset()' functions of the GUI-Program and which can observe the color of the circle. When we want to Learn the SUL, the Learner will generate queries constructed 'press()', 'release()' and 'drag()' to get an idea how the SUL works. The Teacher will be given these queries and execute the contained functions in the SUL. When he has executed them all it will report the color of the circle back to the Learner. When the Learner thinks it has successfully learned the model, it performs a 'check' with the teacher who will either confirm he has correctly learned the SUL or it will give him a counterexample showing why the model is wrong and the Learner will continue learning (More about this 'check' is explained in Advanced).

//TODO: Image of a Mealy Machine and DFA of the example System.

The learned models are Finite State Machines (FSMs). Currently, HermieLab supports learning 2 kinds of FSMs, namely Deterministic Finite Automatons (DFAs) and Mealy Machines. Finite State Machines have been around even before the inception of software engineering. [Y] Using finite state models in the design and testing of software and hardware has been long established and is considered a standard practice today. A good example of a model based test tool is GraphWalker, a tool used by Spotify to test it's desktop and web player. A lot has been written on FSMs, instead of explaining everything here I suggest you check out X, Y or Z.