Applying Automata Learning to Embedded Control Software

Wouter Smeenk, Joshua Moerman, Frits W. Vaandrager, David N. Jansen

Research output: Chapter in Book/Report/Conference proceedingConference Article in proceedingAcademicpeer-review


Using an adaptation of state-of-the-art algorithms for black-box automata learning, as implemented in the LearnLib tool, we succeeded to learn a model of the Engine Status Manager (ESM), a software component that is used in printers and copiers of Océ. The main challenge that we encountered was that LearnLib, although effective in constructing hypothesis models, was unable to find counterexamples for some hypotheses. In fact, none of the existing FSM-based conformance testing methods that we tried worked for this case study. We therefore implemented an extension of the algorithm of Lee and Yannakakis for computing an adaptive distinguishing sequence. Even when an adaptive distinguishing sequence does not exist, Lee and Yannakakis’ algorithm produces an adaptive sequence that ‘almost’ identifies states. In combination with a standard algorithm for computing separating sequences for pairs of states, we managed to verify states with on average 3 test queries. Altogether, we needed around 60 million queries to learn a model of the ESM with 77 inputs and 3.410 states. We also constructed a model directly from the ESM software and established equivalence with the learned model. To the best of our knowledge, this is the first paper in which active automata learning has been applied to industrial control software.
Original languageEnglish
Title of host publicationFormal Methods and Software Engineering
Subtitle of host publication17th International Conference on Formal Engineering Methods, ICFEM 2015, Paris, France, November 3-5, 2015, Proceedings
EditorsMichael Butler, Sylvain Conchon, Fatiha Zaïdi
Number of pages17
ISBN (Electronic)978-3-319-25423-4
ISBN (Print)978-3-319-25422-7
Publication statusPublished - Dec 2015
Externally publishedYes

Publication series

SeriesLecture Notes in Computer Science


Dive into the research topics of 'Applying Automata Learning to Embedded Control Software'. Together they form a unique fingerprint.

Cite this