models. Again, a major effort will be
required to incorporate these ideas in
state-of-the-art tools such as LearnLib,
libalf, RALib, or Tomte.
Quality of models. Since the models produced by model learning algorithms have been obtained through
a finite number of tests, we can
never be sure that they are correct.
Nevertheless, from a practical perspective, we would like to be able to
make quantitative statements about
the quality of learned models and,
for instance, assert that a hypothesis
is approximately correct with high
probability. Angluin6 proposed such
a setting, along the lines of the PAC
learning approach of Valiant. 37 Her
idea was to assume some (unknown)
probability distribution on the set of
words over the input alphabet I. In order
to test a hypothesis, the conformance
tester (see Figure 4) selects a specified number of input words (these
are statistically independent events)
and checks for each word whether the
resulting output of SUL and hypothesis
agrees. Only when there is full agreement the conformance tester returns
answer yes to the learner. An hypothesis is said to be an ε-approximation of
the SUL if the probability of selecting
a string that exhibits a difference is
at most ε. Given a bound on the number of states of the SUL, and two constants ε and δ, Angluin’s polynomial
algorithm produces a model such
that the probability that this model
is an ε-approximation of the SUL is at
least 1 − δ. Angluin’s result is elegant
but not realistic in a setting of reactive systems, since there we typically
do not have a fixed distribution over
the input words. (Inputs are under the
control of the environment of the SUL,
and this environment may change.)
Using traditional conformance test-
ing, 29 we can devise a test suite that
can guarantee the correctness of a
learned model, given an upper bound
on the number of states of the SUL.
But such an approach is also not sat-
isfactory, since the required number
of test sequences grows exponentially
with the number of states of the SUL.
The challenge therefore is to establish
a middle ground between Angluin’s
approach and traditional conformance
testing. Systems logs often provide a
probability distribution on the set of
input words that may be used as a start-
ing point for defining a metric.
Opening the box. There can be many
reasons for using black box model
learning techniques. For instance, we
may want to understand the behavior
of a component but do not have access
to the code. Or we may have access to
the code but not to adequate tools for
analyzing it (for example, in the case
of legacy software). Even in “white
box” situations where we have access
both to the code and to powerful code
analysis tools, black box learning can
make sense, for instance because a
black box model can be used to gen-
erate regression tests, for checking
conformance to a standard, or as part
of model-based development of a
larger system. An important research
challenge is to combine black box
and white box model extraction tech-
niques and, for instance, to use white
box methods such as static analysis
and concolic testing to help answering
equivalence queries posed by a black
Acknowledgments. Portions of
this work were performed in the context of STW projects 11763 (ITALIA)
and 13859 (SUMBAT), and NWO
projects 628.001.009 (LEMMA) and
1. Aarts, F., Fiterău-Broştean, P., Kuppens, H.,
Vaandrager, F. Learning register automata with fresh
value generation. In ICTAC’ 15, LNCS 9399 (2015).
2. Aarts, F., Jonsson, B., Uijen, J., Vaandrager, F.
Generating models of infinite-state communication
protocols using regular inference with abstraction.
Formal Methods Syst. Des. 46, 1 (2015), 1–41.
3. Aarts, F., de Ruiter, J., Poll, E. Formal models of bank
cards for free. In SECTEST’ 13 (2013). IEEE, 461–468.
4. Aarts, F., Vaandrager, F. Learning I/O automata. In
CONCUR’ 10, LNCS 6269 (2010). Springer, 71–85.
5. Alur, R., Madhusudan, P. Visibly pushdown languages.
In STOC’04 (2004). ACM, 202–211.
6. Angluin, D. Learning regular sets from queries and
counterexamples. Inf. Comput. 75, 2 (1987), 87–106.
7. Bennett, K. Legacy systems: coping with success.
IEEE Softw. 12, 1 (1995), 19–23.
8. Berg, T., Grinchtein, O., Jonsson, B., Leucker, M.,
Raffelt, H., Steffen, B. On the correspondence
between conformance testing and regular
inference. In FASE’05, LNCS 3442 (2005). Springer,
9. Bollig, B., Katoen, J.-P., Kern, C., Leucker, M.,
Neider, D., Piegdon, D. libalf: The automata learning
framework. In CAV’ 10, LNCS 6174 (2010). Springer,
10. Cassel, S., Howar, F., Jonsson, B. RALib: A LearnLib
extension for inferring EFSMs. In DIF TS 15 (2015).
11. Cassel, S., Howar, F., Jonsson, B., Merten, M., Steffen,
B. A succinct canonical register automaton model.
J. Log. Algebr. Meth. Program. 84, 1 (2015), 54–66.
12. Cassel, S., Howar, F., Jonsson, B., Steffen, B. Active
learning for extended finite state machines. Formal
Asp. Comput. 28, 2 (2016), 233–263.
13. Chalupar, G., Peherstorfer, S., Poll, E., Ruiter, J.
Automated reverse engineering using Lego. In
WOOT’ 14 (Aug. 2014). IEEE Computer Society.
14. Cho, C., Babic, D., Shin, E., Song, D. Inference and
analysis of formal models of botnet command and
control protocols. In CCS’ 10 (2010). ACM, 426–439.
15. Clarke, E., Grumberg, O., Peled, D. Model Checking.
MI T Press, Cambridge, MA, 1999.
16. Feng, L., Lundmark, S., Meinke, K., Niu, F., Sindhu, M.,
Wong, P. Case studies in learning-based testing. In
IC TSS’ 13, LNCS 8254 (2013). Springer, 164–179.
17. Fiterău-Broştean, P., Janssen, R., Vaandrager, F.
Combining model learning and model checking to
analyze TCP implementations. In CAV’ 16, LNCS 9780
(2016). Springer, 454–471.
18. Grinchtein, O., Jonsson, B., Leucker, M. Learning of
event-recording automata. Theor. Comput. Sci. 411,
47 (2010), 4029–4054.
19. Groce, A., Peled, D., Yannakakis, M. Adaptive model
checking. Logic J. IGPL 14, 5 (2006), 729–744.
20. Hagerer, A., Hungar, H., Niese, O., Steffen, B. Model
generation by moderated regular extrapolation. In
FASE’02, LNCS 2306 (2002). Springer, 80–95.
21. Henrix, M. Performance improvement in automata
learning. Master thesis, Radboud University (2015).
22. Hungar, H., Niese, O., Steffen, B. Domain-specific
optimization in automata learning. In CAV 2003,
LNCS 2725 (2003). Springer, 315–327.
23. de la Higuera, C. Grammatical Inference: Learning
Automata and Grammars. Cambridge University
24. Isberner, M. Foundations of active automata learning:
An algorithmic perspective. PhD thesis, Technical
University of Dortmund (2015).
25. Isberner, M., Howar, F., Steffen, B. The TTT algorithm: A
redundancy-free approach to active automata learning.
In RV’ 14, LNCS 8734 (2014). Springer, 307–322.
26. Isberner, M., Howar, F., Steffen, B. The open-source
LearnLib – A framework for active automata learning.
In CAV’ 15, LNCS 9206 (2015). Springer, 487–495.
27. Jhala, R., Majumdar, R. Software model checking.
ACM Comput. Surv. 41, 4 (Oct. 2009), 21:1–21: 54.
28. Kearns, M. J., Vazirani, U. V. An Introduction to
Computational Learning Theory. MI T Press, 1994.
29. Lee, D., Yannakakis, M. Principles and methods of
testing finite state machines—A survey. Proc. IEEE
84, 8 (1996), 1090–1123.
30. Margaria, T., Niese, O., Raffelt, H., Steffen, B. Efficient
test-based model generation for legacy reactive
systems. In HLDV T’04 (2004). IEEE Computer
31. Moore, E. Gedanken-experiments on sequential
machines. In Automata Studies, Annals of Mathematics
Studies 34 (1956). Princeton University Press, 129–153.
32. Peled, D., Vardi, M., Yannakakis, M. Black box checking.
J. Autom. Lang. Comb. 7, 2 (2002), 225–246.
33. Rivest, R.L., Schapire, R.E. Inference of finite
automata using homing sequences. Inf. Comput. 103,
2 (1993), 299–347.
34. de Ruiter, J., Poll, E. Protocol state fuzzing of TLS
implementations. In USENIX Security’ 15 (2015).
USENIX Association, 193–206.
35. Schuts, M., Hooman, J., Vaandrager, F. Refactoring
of legacy software using model learning and
equivalence checking: an industrial experience report.
In iFM’ 16, LNCS 9681 (2016). Springer, 311–325.
36. Shahbaz, M., Groz, R. Analysis and testing of black-box
component-based systems by inferring partial models.
Softw. Test. Verif. Reliab. 24, 4 (2014), 253–288.
37. Valiant, L.G. A theory of the learnable. In STOC’ 84
(1984). ACM, 436–445.
38. Volpato, M., Tretmans, J. Approximate active learning
of nondeterministic input output transition systems.
Electron. Commun. EASS T 72 (2015).
39. Windmüller, S., Neubauer, J., Steffen, B., Howar, F.,
Bauer, O. Active continuous quality control. In
CBSE’ 13 (2013). ACM, 111–120.
Frits Vaandrager ( F.Vaandrager@cs.ru.nl), Department
of Software Science, Institute for Computing and
Information Sciences at Radboud University, Nijmegen,
© 2017 ACM 0001-0782/17/02 $15.00
Watch the author discuss
his work in this exclusive