Felix Wallner

Active automata learning enables model-based testing and verification of black-box systems by automatically constructing models from observations via interactions with the system. As interactions are usually expensive, active algorithms attempt to perform as few interactions as possible to learn a given system. However, many such algorithms struggle when confronted with noise, such as message loss, when learning otherwise deterministic systems. We investigate and adapt different algorithms to learn deterministic automata in a noisy setting. One of these is a novel active algorithm based on our previous passive Partial Max-SAT algorithm. In our analysis, we demonstrate techniques to lower the required number of interactions and order the evaluated algorithms accordingly. Finally, we show that the necessary interactions can be further reduced when leaving the classical active learning framework.

Automata learning enables model-based analysis of black-box systems by automatically constructing models from system observations, which are often collected via testing. The required testing budget to learn adequate models heavily depends on the applied learning and testing techniques. Test cases executed for learning (1) collect behavioural information and (2) falsify learned hypothesis automata. Falsification test-cases are commonly selected through conformance testing. Active learning algorithms additionally implement test-case selection strategies to gain information, whereas passive algorithms derive models solely from given data. In an active setting, such algorithms require external test-case selection, like repeated conformance testing to extend the available data. There exist various approaches to learning and conformance testing, where interdependencies among them affect performance. We investigate the performance of combinations of six learning algorithms, including a passive algorithm, and seven testing algorithms by performing experiments using 153 benchmark models. We discuss insights regarding the performance of different configurations for various types of systems. Our findings may provide guidance for future users of automata learning. For example, counterexample processing during learning strongly impacts efficiency, which is further affected by testing approach and system type. Testing with the random Wp-method performs best overall, while mutation-based testing performs well on smaller models.

The mining of models from data finds widespread use in industry. There exists a variety of model inference methods for perfectly deterministic behaviour, however, in practice, the provided data often contains noise due to faults such as message loss or environmental factors that many of the inference algorithms have problems dealing with. We present a novel model mining approach using Partial Max-SAT solving to infer the best possible automaton from a set of noisy execution traces. This approach enables us to ignore the minimal number of presumably faulty observations to allow the construction of a deterministic automaton. No pre-processing of the data is required. The method's performance as well as a number of considerations for practical use are evaluated, including three industrial use cases, for which we inferred the correct models.