Abstract
Links are established between three widely used modeling frameworks for reactive systems: the ioco theory of Tretmans, the interface automata of De Alfaro and Henzinger, and Mealy machines. It is shown that, by exploiting these links, any tool for active learning of Mealy machines can be used for learning I/O automata that are deterministic and output determined. The main idea is to place a transducer in between the I/O automata teacher and the Mealy machine learner, which translates concepts from the world of I/O automata to the world of Mealy machines, and vice versa. The transducer comes equipped with an interface automaton that allows us to focus the learning process on those parts of the behavior that can effectively be tested and/or are of particular interest. The approach has been implemented on top of the LearnLib tool and has been applied successfully to three case studies.
This research was supported by European Community’s Seventh Framework Programme under grant agreement no 214755 (QUASIMODO).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Aarts, F.: Inference and Abstraction of Communication Protocols. Master thesis, Radboud University Nijmegen and Uppsala University (November 2009)
Aarts, F., Schmaltz, J., Vaandrager, F.: Inference and abstraction of the biometric passport (May 2010)
ALDEBARAN manual, http://www.inrialpes.fr/vasy/cadp/man/aldebaran.html
Alur, R., Henzinger, T., Kupferman, O., Vardi, M.: Alternating refinement relations. In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 163–178. Springer, Heidelberg (1998)
Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87–106 (1987)
Berg, T., Grinchtein, O., Jonsson, B., Leucker, M., Raffelt, H., Steffen, B.: On the correspondence between conformance testing and regular inference. In: Cerioli, M. (ed.) FASE 2005. LNCS, vol. 3442, pp. 175–189. Springer, Heidelberg (2005)
BSI. Advanced security mechanisms for machine readable travel documents - extended access control (eac) - version 1.11. Technical Report TR-03110, German Federal Office for Information Security (BSI), Bonn, Germany (2008)
de Alfaro, L., Henzinger, T.: Interface automata. In: ESEC/FSE 2001. Software Engineering Notes, vol. 26, pp. 109–120. ACM Press, New York (2001)
Henzinger, T.: Two challenges in embedded systems design: Predictability and robustness. Philosophical Trans. of the Royal Society A 366, 3727–3736 (2008)
Higuera, C.d.: Grammatical Inference: Learning Automata and Grammars. Cambridge University Press, Cambridge (2010)
Hungar, H., Niese, O., Steffen, B.: Domain-specific optimization in automata learning. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 315–327. Springer, Heidelberg (2003)
ICAO. Doc 9303 - machine readable travel documents - part 1-2. Technical report, International Civil Aviation Organization, 6th edn. (2006)
Jonsson, B.: Modular verification of asynchronous networks. In: PODC 1987, pp. 152–166 (1987)
Larsen, K., Nyman, U., Wasowski, A.: Modal i/o automata for interface and product line theories. In: De Nicola, R. (ed.) ESOP 2007. LNCS, vol. 4421, pp. 64–79. Springer, Heidelberg (2007)
Lee, D., Yannakakis, M.: Principles and methods of testing finite state machines — a survey. Proceedings of the IEEE 84(8), 1090–1123 (1996)
Leucker, M.: Learning meets verification. In: de Boer, F.S., Bonsangue, M.M., Graf, S., de Roever, W.-P. (eds.) FMCO 2006. LNCS, vol. 4709, pp. 127–151. Springer, Heidelberg (2007)
Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publishers, Inc., San Francisco (1996)
Lynch, N., Tuttle, M.: Hierarchical correctness proofs for distributed algorithms. In: PODC 1987, pp. 137–151 (1987)
Mostowski, W., Poll, E., Schmaltz, J., Tretmans, J., Wichers Schreur, R.: Model-based testing of electronic passports. In: FMICS 2009, pp. 207–209. Springer, Heidelberg (2009)
Niese, O.: An Integrated Approach to Testing Complex Systems. PhD thesis, University of Dortmund (2003)
Panangaden, P., Stark, E.: Computations, residuals, and the power of indeterminancy. In: Lepistö, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol. 317, pp. 439–454. Springer, Heidelberg (1988)
Raffelt, H., Steffen, B., Berg, T.: Learnlib: a library for automata learning and experimentation. In: FMICS 2005, pp. 62–71. ACM Press, New York (2005)
Raffelt, H., Steffen, B., Berg, T., Margaria, T.: Learnlib: a framework for extrapolating behavioral models. STTT 11(5), 393–407 (2009)
Rosenberg, J., Schulzrinne, H.: Reliability of Provisional Responses in Session Initiation Protocol (SIP). RFC 3262 (Proposed Standard) (June 2002)
Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, A., Peterson, J., Sparks, R., Handley, M., Schooler, E.: SIP: Session Initiation Protocol. RFC 3261 (Proposed Standard). Updated by RFCs 3265, 3853, 4320, 4916, 5393 (June 2002)
Tretmans, J.: Test generation with inputs, outputs, and repetitive quiescence. Software–Concepts and Tools 17, 103–120 (1996)
Tretmans, J.: Model based testing with labelled transition systems. In: Hierons, R.M., Bowen, J.P., Harman, M. (eds.) FORTEST. LNCS, vol. 4949, pp. 1–38. Springer, Heidelberg (2008)
Veanes, M., Bjørner, N.: Input-output model programs. In: Leucker, M., Morgan, C. (eds.) Theoretical Aspects of Computing - ICTAC 2009. LNCS, vol. 5684, pp. 322–335. Springer, Heidelberg (2009)
Willemse, T.: Heuristics for ioco-based test-based modelling. In: Brim, L., Haverkort, B.R., Leucker, M., van de Pol, J. (eds.) FMICS 2006 and PDMC 2006. LNCS, vol. 4346, pp. 132–147. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aarts, F., Vaandrager, F. (2010). Learning I/O Automata. In: Gastin, P., Laroussinie, F. (eds) CONCUR 2010 - Concurrency Theory. CONCUR 2010. Lecture Notes in Computer Science, vol 6269. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15375-4_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-15375-4_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15374-7
Online ISBN: 978-3-642-15375-4
eBook Packages: Computer ScienceComputer Science (R0)