Automata Learning (Basic)
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 to learn models. In this wiki, we will only summarise the basic concepts; a more detailed explanation and discussion can be found in this awesome paper by the LearnLib team. LearnLib is the most popular automata learning library and HermieLab is build on top of it.
In Automata Learning, models of a target system, often called a SUL (System Under Learning) are created by active interaction with them and reasoning about the observed output. This is done by constructing queries, which are sequences of input symbols from an input alphabet that represents the actions executable on the SUL, and answering these queries by means of actual execution.
Above an example SUL is shown. We have 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.
To perform a learning experiment a learning setup is required. Learning setup generally consists of 2 components: a Learner and a Teacher.
The Learner questions the Teacher and reasons about the observed output. The Teacher answers the queries of the Learner. The Teacher is either the SUL itself or, more often, an adapter to the SUL. This is because in general, a SUL has no interface to apply the queries. After each query, the Teacher resets the program to its initial state. This is last part is very important since all queries must be independent. (Watch out when building your learning experiment, forgetting to reset and faulty resets are the cause of many "bugs").
If we generate a learning setup for our exampe SUL, we have also Learner who will generate queries, consisting of input symbols from our SULs input alphabet, based on some learning algorithm we have specified.
Additionally, a Teacher will be generated who can execute the behavior tied to the input symbols (he can fire the 'press()', 'drag()', 'release()' functions), start the SUL with the help of the 'main()' function, reset the SUL after each query by executing the 'reset()' function and can observe the color of the circle.
When we want to learn a model of the SUL, we start the experiment. When the experiment is started, the Learner will generate queries consisting of the 'press()', 'release()' and 'drag()' symbols to get an idea how the SUL works. The Teacher will be given these queries and execute the functions contained in this query on our GUI program. When he has executed all the functions it gets the color of the circle, reports it back the Learner and resets the SUL. The Learner then tries to build a model which encapsulates the observed behavior, otherwise said a model which can correctly predict the circles color after any arbitrary sequence of 'press()', 'release()' and 'drag()' invocations.
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. When this happens will just continue the learning process until the teacher will agree with our learned model. (More about this 'check' is explained in Advanced).
The models we can learn 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, therefore a lot has been written on FSMs. Instead of explaining everything here I suggest you check out this, this or this introduction.
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 testing tool is GraphWalker, a tool used by Spotify to test it's desktop and web player.