Scientific Discussion

A short history of active learning

Active learning of automata structures has been a research interest for several decades, focussing mainly on theoretical formulation and analisys of different approaches. In active learning, deterministic finite automata (Dfa), may be actively inferred with a polynomial bounded (in the number of states) number of Membership- and Equivalence Queries. There Membership Queries ask, if a certain word is part of the language, accepted by the target automaton and Equivalence Queries test the identity of the languages of a current hypothetical model (conjecture) and the language of the target system. In the case, both languages are not equivalent, an Equivalence Query will produce as counterexample a word from the symmetric difference of the languages.

The introduction of Equivalence Queries, however, is an abstraction that on one hand simplyfies and structures the theoretical formulation of regular inference, but on the other hand is unrealistic for true black-box scenarios. In practice every Equivalence Query will have to be approximated by a number of Membership Queries. Actually, the number of Membership Queries, needed to simulate one Equivalence Query, is exponential in the size (number of states) of the target automaton, and if this number is unknown, equivalence is undecidable.

These well established theoretical considerations are contrasted by a more than sparse field of applications. Publications only sporadically contain case studies, typically basing on a small set of well-known examples and/or on sets of randomly generated target concepts. Case studies with practical relevance are very rare.

To summarize: from the theoretical point of view, Angluin's algorithm L* and its derivations form a theoretically well studied and well understood approach. But, L* relies on the availability of Equivalence Queries, which in pratice typically do not exist. The equivalence of hypothetical model and target system can only be approximated, e.g., using conformance testing methods . Only additional information, e.g., about the maximum number of states of the target system, let Equivalence Queries become decidable; typically at a price of exponential complexity. This places even small problems with n>100 states and k>10 inputs outside the power of current learning tools. RERS aims at discipline of practical learning which turn this state of the art around, and establishes technologies of practical impact.

Challenges in active learning

Automata learning can be considered as a key technology for dealing with black box systems, i.e., systems which can be observed, but for which no or little knowledge about the internal structure or even their intent is available. Active automata learning is characterized by its specific means of observation, i.e., its proactive way of posing membership queries and equivalence queries. Thus it requires some way to realize this query-based interaction for the considered application contexts. Whereas membership queries may often be realized via testing in practice, equivalence queries are typically unrealistic. Below we discuss the challenges according to the various characteristics of application scenarios, and illustrate that "black does not equal black" for real-life black box scenarios:

A: Interfacing to the system

One very basic premise of active automata learning is the ability to apply test cases on the target system, which requires an adequate connection of the learning system to the target system. Systems designed for connectivity (e.g., Web Services or code libraries) have a native concept of being invoked from the outside and come with documentation on how to accomplish this, while e.g. some embedded systems may work within well-concealed environments and only be accessible via some proprietary GUI.

In addition to technical reachability, learning-based system interaction requires a communication alphabet in order to generate test cases. While this is no problem for system which provide interface descriptions, like Web Services in WSDL, obtaining this information in other scenarios may cause severe problems.

B: Membership Queries

Whereas small learning experiments typically require only a few hundred membership queries, learning realistic systems may easily require several orders of magnitude more. This directly shows that the speed of the target system when processing Membership Queries, or as in most practical settings the corresponding test cases, is of utmost importance. In contrast to simulation environments, which typically process several thousand of queries per second, real systems may well need many seconds or sometime even minutes per test case. Such cases required dedicated optimizations.

C: Reset

Active learning requires Membership Queries to be independent. Whereas this is no problem for simulated system, this may be quite problematic in practice. Solutions range here from reset mechanisms via homing sequences or snapshots of the system state to the generation of independent fresh system scenarios. Indeed, in certain situations executing each membership query with a separate independent user scenario may be the best what can do. Besides the overhead of establishing these scenarios, this also requires an adequate aggregation of the query results. E.g., the different user password combinations of the various used scenarios must be abstractly identified.

D: Equivalence Queries

Equivalence Queries are supposed to compare a (learned) hypothesis model with the target system for language equivalence, and in case of failure, to return a counterexample exposing a difference. Also their realization is typically rather simple in simulation scenarios, but in practice, only approximative solutions exploiting membership queries exist. It has turned out that changing the view from trying to proof equivalence, e.g., by using conformance testing techniques, to finding counterexamples fast has a strong positive impact, and it establishes a new research direction.

E: Parameters and Value domains

Active learning is classically based on abstract communication alphabets. Parameters and interpreted value are only treated to an extend expressible within the abstract alphabet. In practice, this is typically not sufficient, not even for systems as simple as communication protocols, where e.g. increasing sequence numbers must be handled, or where authentification requires matching user password combinations. Due to the complexity of this problem, we do not expect any comprehensive solutions here. Rather we think that domain and problem-specific approaches must be developed in order to produce dedicated solutions.

Bibliography (to be completed)

  • Fides Aarts and Frits Vaandrager. Learning I/O Automata. accepted for CONCUR 2010.
  • Dana Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39(3):337-350, 1978.
  • Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 2(75):87-106, 1987.
  • Jose L. Balcazar, Josep Diaz, Ricard Gavalda, and Osamu Watanabe. The query complexity of learning DFA. New Generation Comput., 12(4):337-358, 1994.
  • Therese Berg, Olga Grinchtein, Bengt Jonsson, Martin Leucker, Harald Raffelt, and Bernhard Steffen. On the correspondence between conformance testing and regular inference. In Maura Cerioli, editor, Proc. of #1th Int. Conf. on Fundamental Approaches to Software Engineering (FASE '05), volume 3442 of Lecture Notes in Computer Science, pages 175-189. Springer Verlag, April 4-8 2005.
  • Therese Berg, Bengt Jonsson, Martin Leucker, and Mayank Saksena. Insights to Angluin's Learning. Technical Report 2003-039, Department of Information Technology, Uppsala University, August 2003.
  • Therese Berg, Bengt Jonsson, and Harald Raffelt. Regular Inference for State Machines with Parameters. In Luciano Baresi and Reiko Heckel, editors, Proc. FASE '10, 13th Int. Conf. on Fundamental Approaches to Software Engineering, volume 3922 of Lecture Notes in Computer Science, pages 107-121. Springer Verlag, 2006.
  • Therese Berg, Bengt Jonsson, and Harald Raffelt. Regular Inference for State Machines Using Domains with Equality Tests. In Jose Luiz Fiadeiro and Paola Inverardi, editors, Proc. FASE '08, 11th Int. Conf. on Fundamental Approaches to Software Engineering, volume 4961 of Lecture Notes in Computer Science, pages 317-331. Springer Verlag, 2008.
  • Therese Bohlin and Bengt Jonsson. Regular inference for communication protocol entities. Technical report, Department of Information Technology, Uppsala University, Schweden, 2009.
  • Benedikt Bollig, Joost-Pieter Katoen, Carsten Kern, and Martin Leucker. Replaying play in and play out: Synthesis of design models from scenarios by learning. In Orna Grumberg and Michael Huth, editors, Proc. of #1th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS '07), Held as Part of the Joint European Conferences on Theory and Practice of Software (ETAPS '07) Braga, Portugal, volume 4424 of Lecture Notes in Computer Sci- ence, pages 435-450. Springer, 2007.
  • Benedikt Bollig, Joost-Pieter Katoen, Carsten Kern, and Martin Leucker. Smyle: A Tool for Synthesizing Distributed Models from Scenarios by Learning. In Franck van Breugel and Marsha Chechik, editors, Proc. of 19th Int. Conf. on Concurrency Theory (CONCUR '08), Toronto, Canada, August 19-22, 2008, volume 5201 of Lecture Notes in Computer Science, pages 162-166. Springer, 2008.
  • Manfred Broy, Bengt Jonsson, Joost-Pieter Katoen, Martin Leucker, and Alexander Pretschner. Model-Based Testing of Reactive Systems:, volume 3472 of Lecture Notes in Computer Science. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005.
  • Tsun S. Chow. Testing software design modeled by finite-state machines. IEEE Transactions on Software Engineering, 4(3):178-187, May 1978.
  • Jamieson M. Cobleigh, Dimitra Giannakopoulou, and Corina S. Pasareanu. Learning assumptions for compositional veri cation. In Proc. TACAS '03, 9th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, volume 2619 of Lecture Notes in Computer Science, pages 331-346. Springer Verlag, 2003.
  • David Combe, Colin de la Higuera, and Jean-Christophe Janodet. Zulu: an Interactive Learning Competition. In Proceedings of FSMNLP 2009, 2010. to appear.
  • Francois Denis, Aurelien Lemay, and Alain Terlutte. Residual Finite State Automata. Fundamenta Informaticae, 51(4):339-368, 2002.
  • Javier Esparza, Martin Leucker, and Maximilian Schlund. Learning Workflow Petri Nets. In Proceedings of the 31st International Conference on Application and Theory of Petri Nets and Other Models of Concurrency (Petri Nets'10), Lecture Notes in Computer Science. Springer, 2010. to appear.
  • Susumu Fujiwara, Gregor von Bochmann, Ferhat Khendek, Mokhtar Amalou, and Abderrazak Ghedamsi. Test selection based on finite state models. IEEE Transactions on Software Engineering, 17(6):591-603, 1991.
  • Mihaela Gheorghiu, Dimitra Giannakopoulou, and Corina S. Pasareanu. Refining Interface Alphabets for Compositional Verification. In TACAS, pages 292-307, 2007.
  • E. Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302-320, 1978.
  • Olga Grinchtein, Bengt Jonsson, and Paul Pettersson. Inference of Event- Recording Automata Using Timed Decision Trees. In Proc. CONCUR 2006, 17th Int. Conf. on Concurrency Theory, pages 435-449, 2006.
  • A. Hagerer, H. Hungar, O. Niese, and B. Steffen. Model generation by moderated regular extrapolation. Lecture Notes in Computer Science, pages 80-95, 2002.
  • A. Hagerer, T. Margaria, O. Niese, B. Steffen, G. Brune, and H.D. Ide. E.- cient regression testing of CTI-systems: Testing a complex call-center solution. Annual review of communication, Int.Engineering Consortium (IEC), 55:1033-1040, 2001.
  • Hardi Hungar, Oliver Niese, and Bernhard Steffen. Domain-specific optimization in automata learning. In Warren A. Hunt Jr. and Fabio Somenzi, editors, Proc. of the #1th Int. Conf. on Computer Aided Verification (CAV '03), volume 2725 of Lecture Notes in Computer Science, pages 315-327. Springer Verlag, July 2003.
  • Hardi Hungar and Bernhard Steffen. Behavior-based model construction. Int. J. Softw. Tools Technol. Transf., 6(1):4-14, 2004.
  • B. Jeannet, T. Jeron, V. Rusu, and E. Zinovieva. Symbolic test selection based on approximate analysis. In TACAS, pages 349-364. Springer, 2005.
  • Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA, 1994.
  • Oded Maler and Amir Pnueli. On the learnability of infinitary regular sets. In Proc. of the #1th annual workshop on Computational learning theory (COLT '91), pages 128-138, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc.
  • Tiziana Margaria, Harald Raffelt, and Bernhard Steffen. Knowledge-based relevance filtering for efficient system-level test-based model generation. Innovations in Systems and Software Engineering, 1(2):147-156, July 2005.
  • T. Margaria, O. Niese, H. Raffelt, and B. Steffen. Ecient test-based model generation for legacy reactive systems. In HLDVT '04: Proceedings of the High- Level Design Validation and Test Workshop, 2004. Ninth IEEE International, pages 95-100, Washington, DC, USA, 2004. IEEE Computer Society.
  • Tiziana Margaria, Harald Raffelt, and Bernhard Ste en. Analyzing Second- Order Effects Between Optimizations for System-Level Test-Based Model Generation. In Test Conference, 2005. Proceedings. ITC 2005. IEEE International. IEEE Computer Society, November 2005.
  • Corina S. Pasareanu, Dimitra Giannakopoulou, Mihaela Gheorghiu Bobaru, Jamieson M. Cobleigh, and Howard Barringer. Learning to divide and conquer: applying the L* algorithm to automate assume-guarantee reasoning. Formal Methods in System Design, 32(3):175-205, 2008.
  • Doron Peled, Moshe Y. Vardi, and Mihalis Yannakakis. Black box checking. In Jianping Wu, Samuel T. Chanson, and Qiang Gao, editors, Proc. of the Joint Int. Conf. on Formal Description Techniques for Distributed System and Communication/Protocols and Protocol Specification, Testing and Verification FORTE/PSTV '99:, pages 225-240. Kluwer Academic Publishers, 1999.
  • Harald Raffelt, Tiziana Margaria, Bernhard Steffen, and Maik Merten. Hybrid test of web applications with webtest. In TAV-WEB '08: Proceedings of the 2008 workshop on Testing, analysis, and verification of web services and applications, pages 1-7, New York, NY, USA, 2008. ACM.
  • Harald Raffelt, Maik Merten, Bernhard Steffen, and Tiziana Margaria. Dynamic testing via automata learning. Int. J. Softw. Tools Technol. Transf., 11(4):307- 324, 2009.
  • Harald Raffelt, Bernhard Steffen, Therese Berg, and Tiziana Margaria. Learn- Lib: a framework for extrapolating behavioral models. Int. J. Softw. Tools Technol. Transf., 11(5):393-407, 2009.
  • Ronald L. Rivest and Robert E. Schapire. Inference of finite automata using homing sequences. In Proc. of the #1st Annual ACM Symposium on Theory of Computing (STOC '89), pages 411-420. MIT Laboratory for Computer Science, ACM Press, May 1989.
  • Vlad Rusu, Lydie Du Bousquet, and Thierry Jeron. An approach to symbolic test generation. In In Proc. Integrated Formal Methods, pages 338-357. Springer Verlag, 2000.
  • Muzammil Shahbaz and Roland Groz. Inferring Mealy Machines. In FM '09: Proceedings of the 2nd World Congress on Formal Methods, pages 207-222, Berlin, Heidelberg, 2009. Springer Verlag.
  • Muzammil Shahbaz, Keqin Li, and Roland Groz. Learning Parameterized State Machine Model for Integration Testing. In Proc. 31st Annual Int. Computer Software and Applications Conf., volume 2, pages 755-760, Washington, DC, USA, 2007. IEEE Computer Society.
  • Bernhard Steffen, Tiziana Margaria, Harald Raffelt, and Oliver Niese. Efficient test-based model generation of legacy systems. In Proc. of the #1th IEEE Int. Workshop on High Level Design Validation and Test (HLDVT '04), pages 95-100, Sonoma (CA), USA, November 2004. IEEE Computer Society Press.