Abstract
In this paper we address the major bottleneck of active automata learning, the typically huge number of required tests, by investigating the impact of using a distributed testing environment (a crowd of teachers) to execute test cases (membership queries) in parallel. This kind of parallelization of automata learning has the best potential when the time for test case execution is dominant, an assumption valid for most practical applications. Our investigation explicitly focuses on the impact of the structure of the system under learning (number of states, size of alphabet) and the degree of supported parallelism. It comprises three variants of active learning algorithms with different test case generation profiles. These differences can be observed directly at the level of the run-times, which all show a linear speedup for moderate degrees of parallelization, but with different saturation points beyond which further parallelization does not pay off.
This work is supported by the European FP 7 project CONNECT (IST 231167).
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
Alur, R., Cerný, P., Madhusudan, P., Nam, W.: Synthesis of interface specifications for Java classes. In: POPL 2005, pp. 98–109. ACM (2005)
Angluin, D.: Learning Regular Sets from Queries and Counterexamples. Information and Computation 75(2), 87–106 (1987)
Balcázar, J.L., Díaz, J., Gavaldà, R., Watanabe, O.: An optimal parallel algorithm for learning dfa. In: Proceedings of the Seventh Annual Conference on Computational Learning Theory, COLT 1994, pp. 208–217. ACM, New York (1994)
Chow, T.S.: Testing Software Design Modeled by Finite-State Machines. IEEE Transactions on Software Engineering 4(3), 178–187 (1978)
Howar, F., Steffen, B., Merten, M.: From ZULU to RERS - Lessons Learned in the ZULU Challenge. In: Margaria, T., Steffen, B. (eds.) ISoLA 2010, Part I. LNCS, vol. 6415, pp. 687–704. Springer, Heidelberg (2010)
Hungar, H., Margaria, T., Steffen, B.: Test-based model generation for legacy systems. In: ITC 2003, pp. 971–980. IEEE Computer Society (2003)
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)
Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press, Cambridge (1994)
Margaria, T., Niese, O., Raffelt, H., Steffen, B.: Efficient test-based model generation for legacy reactive systems. In: HLDVT 2004, pp. 95–100. IEEE Computer Society (2004)
Margaria, T., Raffelt, H., Steffen, B.: Analyzing Second-Order Effects Between Optimizations for System-Level Test-Based Model Generation. In: ITC 2005. IEEE Computer Society (2005)
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)
Merten, M., Howar, F., Steffen, B., Margaria, T.: Automata Learning with on-the-Fly Direct Hypothesis Construction. In: Hähnle, R., et al. (eds.) ISoLA 2011 Workshops. CCIS, vol. 336, pp. 248–260. Springer, Heidelberg (2012)
Merten, M., Steffen, B., Howar, F., Margaria, T.: Next Generation LearnLib. In: Abdulla, P.A., Leino, K.R.M. (eds.) TACAS 2011. LNCS, vol. 6605, pp. 220–223. Springer, Heidelberg (2011)
Nerode, A.: Linear Automaton Transformations. Proceedings of the American Mathematical Society 9(4), 541–544 (1958)
Niese, O.: An Integrated Approach to Testing Complex Systems. PhD thesis, University of Dortmund, Germany (2003)
Peled, D., Vardi, M.Y., Yannakakis, M.: Black Box Checking. Journal of Automata, Languages and Combinatorics 7(2), 225–246 (2002)
Raffelt, H., Steffen, B., Berg, T., Margaria, T.: LearnLib: a framework for extrapolating behavioral models. Int. J. Softw. Tools Technol. Transf. 11(5), 393–407 (2009)
Rivest, R.L., Schapire, R.E.: Inference of finite automata using homing sequences. Information and Computation 103(2), 299–347 (1993)
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
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Howar, F., Bauer, O., Merten, M., Steffen, B., Margaria, T. (2012). 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) Leveraging Applications of Formal Methods, Verification, and Validation. ISoLA 2011. Communications in Computer and Information Science, vol 336. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34781-8_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-34781-8_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34780-1
Online ISBN: 978-3-642-34781-8
eBook Packages: Computer ScienceComputer Science (R0)