Efficient Active Automata Learning via Mutation Testing

Bernhard Aichernig, Martin Tappler

Research output: Contribution to journalArticlepeer-review


System verification is often hindered by the absence of formal models. Peled et al. proposed black-box checking as a solution to this problem. This technique applies active automata learning to infer models of systems with unknown internal structure. This kind of learning relies on conformance testing to determine whether a learned model actually represents the considered system. Since conformance testing may require the execution of a large number of tests, it is considered the main bottleneck in automata learning. In this paper, we describe a randomised conformance testing approach which we extend with fault-based test selection. To show its effectiveness we apply the approach in learning experiments and compare its performance to a well-established testing technique, the partial W-method. This evaluation demonstrates that our approach significantly reduces the cost of learning. In multiple experiments, we reduce the cost by at least one order of magnitude.
Original languageEnglish
Pages (from-to)1103-1134
Number of pages32
JournalJournal of Automated Reasoning
Issue number4
Early online date25 Oct 2018
Publication statusPublished - 2019


Dive into the research topics of 'Efficient Active Automata Learning via Mutation Testing'. Together they form a unique fingerprint.

Cite this