Abstract
In this paper we present TTT, a novel active automata learning algorithm formulated in the Minimally Adequate Teacher (MAT) framework. The distinguishing characteristic of TTT is its redundancy-free organization of observations, which can be exploited to achieve optimal (linear) space complexity. This is thanks to a thorough analysis of counterexamples, extracting and storing only the essential refining information. TTT is therefore particularly well-suited for application in a runtime verification context, where counterexamples (obtained, e.g., via monitoring) may be excessively long: as the execution time of a test sequence typically grows with its length, this would otherwise cause severe performance degradation. We illustrate the impact of TTT’s consequent redundancy-free approach along a number of examples.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aarts, F., Heidarian, F., Kuppens, H., Olsen, P., Vaandrager, F.: Automata Learning through Counterexample Guided Abstraction Refinement. In: Giannakopoulou, D., Méry, D. (eds.) FM 2012. LNCS, vol. 7436, pp. 10–27. Springer, Heidelberg (2012), http://dx.doi.org/10.1007/978-3-642-32759-9_4
Angluin, D.: Learning Regular Sets from Queries and Counterexamples. Inf. Comput. 75(2), 87–106 (1987)
Balcázar, J.L., Díaz, J., Gavaldà, R.: Algorithms for Learning Finite Automata from Queries: A Unified View. In: Advances in Algorithms, Languages, and Complexity, pp. 53–72 (1997)
Berg, T., Jonsson, B., Leucker, M., Saksena, M.: Insights to Angluin’s Learning. Electron. Notes Theor. Comput. Sci. 118, 3–18 (2005), http://dx.doi.org/10.1016/j.entcs.2004.12.015
Bertolino, A., Calabrò, A., Merten, M., Steffen, B.: Never-Stop Learning: Continuous Validation of Learned Models for Evolving Systems through Monitoring. ERCIM News 2012(88) (2012)
Bollig, B., Habermehl, P., Kern, C., Leucker, M.: Angluin-style Learning of NFA. In: Proc. IJCAI 2009, San Francisco, CA, USA, pp. 1004–1009 (2009)
Broy, M., Jonsson, B., Katoen, J.-P., Leucker, M., Pretschner, A. (eds.): Model-Based Testing of Reactive Systems. LNCS, vol. 3472. Springer, Heidelberg (2005)
Cho, C.Y., Babić, D., Shin, R., Song, D.: Inference and Analysis of Formal Models of Botnet Command and Control Protocols. In: CCS 2010, pp. 426–440. ACM, Chicago (2010)
Choi, W., Necula, G., Sen, K.: Guided GUI Testing of Android Apps with Minimal Restart and Approximate Learning. In: Proc. OOPSLA 2013, pp. 623–640. ACM, New York (2013), http://doi.acm.org/10.1145/2509136.2509552
Clarke, E.M., Grumberg, O., Peled, D.A.: Model Checking. MIT Press (1999)
Corbett, J., Dwyer, M., Hatcliff, J., Laubach, S., Pasareanu, C., Robby, Z.H.: Bandera: Extracting Finite-state Models from Java Source Code. In: Proc. Software Engineering, pp. 439–448 (2000)
De La Briandais, R.: File Searching Using Variable Length Keys. In: Western Joint Computer Conference, IRE-AIEE-ACM 1959, Western, pp. 295–298. ACM, New York (1959), http://doi.acm.org/10.1145/1457838.1457895
Domaratzki, M., Kisman, D., Shallit, J.: On the Number of Distinct Languages Accepted by Finite Automata with n States. Journal of Automata, Languages and Combinatorics 7(4), 469–486 (2002)
Hagerer, A., Hungar, H.: Model generation by moderated regular extrapolation. In: Kutsche, R.-D., Weber, H. (eds.) FASE 2002. LNCS, vol. 2306, pp. 80–95. Springer, Heidelberg (2002)
Howar, F.: Active Learning of Interface Programs. Ph.D. thesis, TU Dortmund University (2012), http://dx.doi.org/2003/29486
Howar, F., Bauer, O., Merten, M., Steffen, B., Margaria, T.: The Teachers Crowd: The Impact of Distributed Oracles on Active Automata Learning. In: Hähnle, R., Knoop, J., Margaria, T., Schreiner, D., Steffen, B. (eds.) ISoLA 2011 Workshops 2011. CCIS, vol. 336, pp. 232–247. Springer, Heidelberg (2012)
Howar, F., Steffen, B., Jonsson, B., Cassel, S.: Inferring Canonical Register Automata. In: Kuncak, V., Rybalchenko, A. (eds.) VMCAI 2012. LNCS, vol. 7148, pp. 251–266. Springer, Heidelberg (2012)
Irfan, M.N., Oriat, C., Groz, R.: Angluin Style Finite State Machine Inference with Non-optimal Counterexamples. In: 1st Int. Workshop on Model Inference in Testing (2010)
Isberner, M., Howar, F., Steffen, B.: Learning Register Automata: From Languages to Program Structures. Machine Learning 96(1-2), 65–98 (2014), http://dx.doi.org/10.1007/s10994-013-5419-7
Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press, Cambridge (1994)
Lorenzoli, D., Mariani, L., Pezzè, M.: Inferring State-based Behavior Models. In: Proc. WODA 2006, pp. 25–32. ACM, New York (2006)
Maler, O., Pnueli, A.: On the Learnability of Infinitary Regular Sets. Information and Computation 118(2), 316–326 (1995)
Margaria, T., Raffelt, H., Steffen, B.: Knowledge-based Relevance Filtering for Efficient System-level Test-based Model Generation. Innovations in Systems and Software Engineering 1(2), 147–156 (2005)
Nerode, A.: Linear Automaton Transformations. Proceedings of the American Mathematical Society 9(4), 541–544 (1958)
Peled, D., Vardi, M.Y., Yannakakis, M.: Black Box Checking. In: Wu, J., Chanson, S.T., Gao, Q. (eds.) Proc. FORTE 1999, pp. 225–240. Kluwer Academic (1999)
Rivest, R.L., Schapire, R.E.: Inference of Finite Futomata Using Homing Sequences. Inf. Comput. 103(2), 299–347 (1993)
Shahbaz, M., Groz, R.: Inferring Mealy Machines. In: Cavalcanti, A., Dams, D.R. (eds.) FM 2009. LNCS, vol. 5850, pp. 207–222. Springer, Heidelberg (2009)
Steffen, B., Howar, F., Merten, M.: Introduction to Active Automata Learning from a Practical Perspective. In: Bernardo, M., Issarny, V. (eds.) SFM 2011. LNCS, vol. 6659, pp. 256–296. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Isberner, M., Howar, F., Steffen, B. (2014). The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning. In: Bonakdarpour, B., Smolka, S.A. (eds) Runtime Verification. RV 2014. Lecture Notes in Computer Science, vol 8734. Springer, Cham. https://doi.org/10.1007/978-3-319-11164-3_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-11164-3_26
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11163-6
Online ISBN: 978-3-319-11164-3
eBook Packages: Computer ScienceComputer Science (R0)