Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2021, Vol. 15 Issue (5) : 155210    https://doi.org/10.1007/s11704-019-9212-z
REVIEW ARTICLE
Model learning: a survey of foundations, tools and applications
Shahbaz ALI1,2, Hailong SUN1,2,3, Yongwang ZHAO1,2,4()
1. Beijing Advanced Innovation Center for Big Data and Brain Computing Beihang University, Beijing 100191, China
2. SKLSDE, School of Computer Science and Engineering, Beihang University, Beijing 100191, China
3. School of Software, Beihang University, Beijing 100191, China
4. School of Cyber Science and Technology, College of Computer Science, Zhejiang University, Hangzhou 310058, China
 Download: PDF(700 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Software systems are present all around us and playing their vital roles in our daily life. The correct functioning of these systems is of prime concern. In addition to classical testing techniques, formal techniques like model checking are used to reinforce the quality and reliability of software systems. However, obtaining of behavior model, which is essential for model-based techniques, of unknown software systems is a challenging task. To mitigate this problem, an emerging black-box analysis technique, called Model Learning, can be applied. It complements existing model-based testing and verification approaches by providing behavior models of blackbox systems fully automatically. This paper surveys the model learning technique, which recently has attracted much attention from researchers, especially from the domains of testing and verification. First, we review the background and foundations of model learning, which form the basis of subsequent sections. Second, we present some well-known model learning tools and provide their merits and shortcomings in the form of a comparison table. Third, we describe the successful applications of model learning in multidisciplinary fields, current challenges along with possible future works, and concluding remarks.

Keywords model learning      active automata learning      automata learning libraries/tools      inferring behavior models      testing and formal verification     
Corresponding Author(s): Yongwang ZHAO   
Just Accepted Date: 24 October 2019   Issue Date: 13 July 2021
 Cite this article:   
Shahbaz ALI,Hailong SUN,Yongwang ZHAO. Model learning: a survey of foundations, tools and applications[J]. Front. Comput. Sci., 2021, 15(5): 155210.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-019-9212-z
https://academic.hep.com.cn/fcs/EN/Y2021/V15/I5/155210
1 M Blair, S Obenski, P Bridickas. Patriot missile defense: software problem led to system failure at dhahran. Report GAO/IMTEC-92-26, 1992
2 J L Lions. Ariane 5 flight 501 failure. Report by the Inquiry Board, 1996
3 A G Stephenson, D R Mulville, F H Bauer, G A Dukeman, P Norvig, L S LaPiana, P J Rutledge, D Folta, R Sackheim. Mars Climate Orbiter Mishap Investigation Board Phase I Report. NASA, Washington, DC, 1999
4 N G Leveson, C S Turner. An investigation of the therac-25 accidents. Journal of Computer, 1993, 26(7): 18–41
https://doi.org/10.1109/MC.1993.274940
5 T Coe. Inside the pentium FDIV bug. DR Dobbs Journal, 1995, 20(4): 129
6 T Ball, S K Rajamani. The slam project: debugging system software via static analysis. In: Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2002, 1–3
https://doi.org/10.1145/503272.503274
7 T A Henzinger, R Jhala, R Majumdar, G Sutre. Lazy abstraction. Journal of ACM SIGPLAN Notices, 2002, 37(1): 58–70
https://doi.org/10.1145/565816.503279
8 N Walkinshaw, K Bogdanov, S Ali, M Holcombe. Automated discovery of state transitions and their functions in source code. Journal of Software Testing, Verification and Reliability, 2008, 18(2): 99–121
https://doi.org/10.1002/stvr.380
9 N Walkinshaw, K Bogdanov, M Holcombe, S Salahuddin. Reverse engineering state machines by interactive grammar inference. In: Proceedings of Working Conference on Reverse Engineering. 2007, 209–218
https://doi.org/10.1109/WCRE.2007.45
10 AW Biermann, R Krishnaswamy. Constructing programs from example computations. Journal of IEEE Transactions on Software Engineering, 1976, 3: 141–153
https://doi.org/10.1109/TSE.1976.233812
11 M Muller-Olm, D A Schmidt, Steffen B. Model-checking: a tutorial introduction. In: Proceedings of International Static Analysis Symposium. 1999, 330–354
https://doi.org/10.1007/3-540-48294-6_22
12 E M Clarke, O Grumberg, D Peled. Model Checking. MIT Press, 1999
13 C Baier, J P Katoen. Principles of Model Checking. MIT Press, 2008
14 M Broy, B Jonsson, J P Katoen, M Leucker, A Pretschner. Model-based testing of reactive systems. Lecture Notes in Computer Science, 2005
https://doi.org/10.1007/b137241
15 M Utting, B Legeard. Practical Model-based Testing: a Tools Approach. Elsevier, 2010
16 F Arbab. Reo: a channel-based coordination model for component composition. Journal ofMathematical Structures in Computer Science, 2004, 14(3): 329–366
https://doi.org/10.1017/S0960129504004153
17 T Ball, E Bounimova, B Cook, V Levin, J Lichtenberg, C McGarvey, B Ondrusek, S K Rajamani, A Ustuner. Thorough static analysis of device drivers. Journal of ACM SIGOPS Operating Systems Review, 2006, 40(4): 73–85
https://doi.org/10.1145/1218063.1217943
18 H Hungar, O Niese, B Steffen. Domain-specific optimization in automata learning. In: Proceedings of International Conference on Computer Aided Verification. 2003, 315–327
https://doi.org/10.1007/978-3-540-45069-6_31
19 T Margaria, O Niese, H Raffelt, B Steffen. Efficient test-based model generation for legacy reactive systems. In: Proceedings of the 9th IEEE International High-Level Design Validation and Test Workshop. 2004, 95–100
https://doi.org/10.1109/HLDVT.2004.1431246
20 H Muccini, A Polini, F Ricci, A Bertolino. Monitoring architectural properties in dynamic component-based systems. In: Proceedings of International Symposium on Component-Based Software Engineering. 2007, 124–139
https://doi.org/10.1007/978-3-540-73551-9_9
21 M Shahbaz. Reverse engineering enhanced state models of black box software components to support integration testing. Doctoral Dissertation, 2008
22 G Shu, D Lee. Testing security properties of protocol implementations-a machine learning based approach. In: Proceedings of the 27th International Conference on Distributed Computing Systems. 2007
https://doi.org/10.1109/ICDCS.2007.147
23 F Aarts, F Vaandrager. Learning I/O automata. In: Proceedings of International Conference on Concurrency Theory. 2010, 71–85
https://doi.org/10.1007/978-3-642-15375-4_6
24 E F Moore. Gedanken-experiments on sequential machines. Journal of Automata Studies, 1956, 34: 129–153
https://doi.org/10.1515/9781400882618-006
25 T Berg, O Grinchtein, B Jonsson, M Leucker, H Raffelt, B Steffen. On the correspondence between conformance testing and regular inference. In: Proceedings of International Conference on Fundamental Approaches to Software Engineering. 2005, 175–189
https://doi.org/10.1007/978-3-540-31984-9_14
26 A Hagerer, H Hungar, O Niese, B Steffen. Model generation by moderated regular extrapolation. In: Proceedings of International Conference on Fundamental Approaches to Software Engineering. 2002, 80–95
https://doi.org/10.1007/3-540-45923-5_6
27 M Isberner. Foundations of active automata learning: an algorithmic perspective. Doctoral Dissertation, 2015
28 J De Ruiter, E Poll. Protocol state fuzzing of TLS implementations. In: Proceedings of the 24th USENIX Security Symposium. 2015, 193–206
29 F Vaandrager. Model learning. Journal of Communications of ACM, 2017, 60(2): 86–95
https://doi.org/10.1145/2967606
30 D Peled, M Y Vardi, M Yannakakis. Black box checking. Journal of Automata, Languages and Combinatorics, 2002, 7(2): 225–246
31 G Ammons, R Bodík, J R Larus. Mining specifications. Journal of ACM Sigplan Notices, 2002, 37(1): 4–16
https://doi.org/10.1145/565816.503275
32 D Lo, S C Khoo. Smartic: towards building an accurate, robust and scalable specification miner. In: Proceedings of the 14th ACM SIGSOFT International Symposium on Foundations of Software Engineering. 2006, 265–275
https://doi.org/10.1145/1181775.1181808
33 D Lorenzoli, L Mariani, M Pezzè. Automatic generation of software behavioral models. In: Proceedings of the 30th International Conference on Software Engineering. 2008, 501–510
https://doi.org/10.1145/1368088.1368157
34 A Bennaceur, K Meinke. Machine learning for software analysis: models, methods, and applications. In: Bennaceur A, Hähnle R, Meinke K, eds. Machine Learning for Dynamic Software Analysis: Potentials and Limits. Springer, Cham, 2018
https://doi.org/10.1007/978-3-319-96562-8_1
35 B Starkie, V M Zaanen, D Estival. The tenjinno machine translation competition. In: Proceedings of International Colloquium on Grammatical Inference. 2006, 214–226
https://doi.org/10.1007/11872436_18
36 B Starkie, F Coste, V M Zaanen. The omphalos context-free grammar learning competition. In: Proceedings of International Colloquium on Grammatical Inference. 2004, 16–27
https://doi.org/10.1007/978-3-540-30195-0_3
37 N Walkinshaw, B Lambeau, C Damas, K Bogdanov, P Dupont. Stamina: a competition to encourage the development and assessment of software model inference techniques. Journal of Empirical Software Engineering, 2013, 18(4): 791–824
https://doi.org/10.1007/s10664-012-9210-3
38 D Combe, C De La Higuera , J C Janodet . Zulu: an interactive learning competition. In: Proceedings of International Workshop on Finite-State Methods and Natural Language Processing. 2009, 139–146
https://doi.org/10.1007/978-3-642-14684-8_15
39 D Angluin. Learning regular sets from queries and counterexamples. Journal of Information and Computation, 1987, 75(2): 87–106
https://doi.org/10.1016/0890-5401(87)90052-6
40 EM Gold. Language identification in the limit. Information and Control, 1967, 10(5): 447–474
https://doi.org/10.1016/S0019-9958(67)91165-5
41 L G Valiant. A theory of the learnable. Journal of Communications of ACM, 1984, 27(11): 1134–114 2
https://doi.org/10.1145/1968.1972
42 D Angluin, C H Smith. Inductive inference: theory and methods. Journal of ACM Computing Surveys (CSUR), 1983, 15(3): 237–269
https://doi.org/10.1145/356914.356918
43 C H GasarchWI, Smith. Learning via queries. Journal of ACM (JACM), 1992, 39(3): 649–674
https://doi.org/10.1145/146637.146670
44 O Watanabe. A framework for polynomial-time query learnability. Journal of Mathematical Systems Theory, 1994, 27(3): 211–229
https://doi.org/10.1007/BF01578843
45 A Blumer, A Ehrenfeucht, D Haussler, M K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of ACM (JACM), 1989, 36(4): 929–965
https://doi.org/10.1145/76359.76371
46 L Pitt, L G Valiant. Computational limitations on learning from examples. Journal of ACM (JACM), 1988, 35(4): 965–984
https://doi.org/10.1145/48014.63140
47 L Pitt, M K Warmuth. Prediction-preserving reducibility. Journal of Computer and System Sciences, 1990, 41(3): 430–467
https://doi.org/10.1016/0022-0000(90)90028-J
48 D Angluin, M Kharitonov. When won’t membership queries help? Journal of Computer and System Sciences, 1995, 50(2): 336–355
https://doi.org/10.1006/jcss.1995.1026
49 B Steffen, F Howar, M Merten. Introduction to active automata learning from a practical perspective. In: Proceedings of International School on Formal Methods for the Design of Computer, Communication and Software Systems. 2012, 256–296
https://doi.org/10.1007/978-3-642-21455-4_8
50 R L Rivest, R E Schapire. Inference of finite automata using homing sequences. Journal of Information and Computation, 1993, 103(2): 299–347
https://doi.org/10.1006/inco.1993.1021
51 R Groz, A Simao, A Petrenko, C Oriat. Inferring finite state machines without reset using state identification sequences. In: Proceedings of International Conference on Testing Software and Systems. 2015, 161–177
https://doi.org/10.1007/978-3-319-25945-1_10
52 S AR Groz, A Petrenko, C Oriat. Inferring fsm models of systems without reset. In: Bennaceur A, Hähnle R,Meinke K, eds. Machine Learning for Dynamic Software. Springer, Cham, 2018
https://doi.org/10.1007/978-3-319-96562-8_7
53 J E Hopcroft, R Motwani, J D Ullman. Introduction to automata theory, languages, and computation. ACM Sigact News, 2001, 32(1): 60–65
https://doi.org/10.1145/568438.568455
54 O Niese. An integrated approach to testing complex systems. Doctoral Disseration, Technical University of Dortmund, Germany, 2003
55 M Shahbaz, R Groz. Inferring mealy machines. In: Proceedings of International Symposium on Formal Methods. 2009, 207–222
https://doi.org/10.1007/978-3-642-05089-3_14
56 M Shahbaz, K Li, R Groz. Learning parameterized state machine model for integration testing. In: Proceedings of Computer Software and Applications Conference. 2007, 755–760
https://doi.org/10.1109/COMPSAC.2007.134
57 F Aarts, H Kuppens, J Tretmans, F Vaandrager, S Verwer. Improving active mealy machine learning for protocol conformance testing. Journal of Machine Learning, 2014, 96(1–2): 189–224
https://doi.org/10.1007/s10994-013-5405-0
58 N Walkinshaw, J Derrick, Q Guo. Iterative refinement of reverseengineered models by model-based testing. In: Proceedings of International Symposium on Formal Methods. 2009, 305–320
https://doi.org/10.1007/978-3-642-05089-3_20
59 R Groz, K Li, A Petrenko, M Shahbaz. Modular system verification by inference, testing and reachability analysis. In: Suzuki K, Higashino T, Ulrich A, Hasegawa T, eds. Testing of Software and Communicating Systems. Springer,Berlin, Hedelberg, 2008
https://doi.org/10.1007/978-3-540-68524-1_16
60 A Huima. Implementing conformiq qtronic. In: Petrenko A, Veanes M, Tretmans J, Griekamp W, eds.Testing of Software and Communicating Systems. Springer, Berlin, Hedelberg, 2007
61 R Jhala, R Majumdar. Software model checking. Journal of ACM Computing Surveys (CSUR), 2009, 41(4): 21
https://doi.org/10.1145/1592434.1592438
62 F Howar, B Steffen, B Jonsson, S Cassel. Inferring canonical register automata. In: Proceedings of International Workshop on Verification, Model Checking, and Abstract Interpretation. 2012, 251–266
https://doi.org/10.1007/978-3-642-27940-9_17
63 F Howar, M Isberner, B Steffen, O Bauer, B Jonsson. Inferring semantic interfaces of data structures. In: Proceedings of International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. 2012, 554–571
https://doi.org/10.1007/978-3-642-34026-0_41
64 M Merten, F Howar, B Steffen, S Cassel, B Jonsson. Demonstrating learning of register automata. In: Proceedings of International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 2012, 466–471
https://doi.org/10.1007/978-3-642-28756-5_32
65 M Isberner, F Howar, B Steffen. Learning register automata: from languages to program structures. Journal of Machine Learning, 2014, 96(1–2): 65–98
https://doi.org/10.1007/s10994-013-5419-7
66 S Cassel, F Howar, B Jonsson, B Steffen. Active learning for extended finite state machines. Journal of Formal Aspects of Computing, 2016, 28(2): 233–263
https://doi.org/10.1007/s00165-016-0355-5
67 O Maler, I E Mens. Learning regular languages over large alphabets. In: Proceedings of International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 2014, 485–499
https://doi.org/10.1007/978-3-642-54862-8_41
68 G Argyros, L D’Antoni. The learnability of symbolic automata. In: Proceedings of International Conference on Computer Aided Verification. 2018, 427–445
https://doi.org/10.1007/978-3-319-96145-3_23
69 S Drews, L D’Antoni. Learning symbolic automata. In: Proceedings of International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 2017, 173–189
https://doi.org/10.1007/978-3-662-54577-5_10
70 G Argyros, I Stais, A Kiayias, A D Keromytis. Back in black: towards formal, black box analysis of sanitizers and filters. In: Proceedings of IEEE Symposium on Security and Privacy. 2016, 91–109
https://doi.org/10.1109/SP.2016.14
71 M Veanes, P Hooimeijer, B Livshits, D Molnar, N Bjorner. Symbolic finite state transducers: algorithms and applications. In: Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2012, 137–150
https://doi.org/10.1145/2103621.2103674
72 M Veanes. Applications of symbolic finite automata. In: Proceedings of International Conference on Implementation and Application of Automata. 2013, 16–23
https://doi.org/10.1007/978-3-642-39274-0_3
73 G Argyros, I Stais, S Jana, A D Keromytis, A Kiayias. Sfadiff: automated evasion attacks and fingerprinting using black-box differential automata learning. In: Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. 2016, 1690–1701
https://doi.org/10.1145/2976749.2978383
74 R Alur, D L Dill. A theory of timed automata. Journal of Theoretical Computer Science, 1994, 126(2): 183–235
https://doi.org/10.1016/0304-3975(94)90010-8
75 O Grinchtein, B Jonsson, M Leucker. Learning of event-recording automata. Journal of Theoretical Computer Science, 2010, 411(47): 4029–4054
https://doi.org/10.1016/j.tcs.2010.07.008
76 A Clark, F Thollard. Pac-learnability of probabilistic deterministic finite state automata. Journal of Machine Learning Research, 2004, 5(May):473–497
77 J Castro, R Gavaldà. Towards feasible pac-learning of probabilistic deterministic finite automata. In: Proceedings of International Colloquium on Grammatical Inference. 2008, 163–174
https://doi.org/10.1007/978-3-540-88009-7_13
78 T Yokomori. Learning Non-Deterministic Finite Automata From Queries and Counterexamples. Oxford University Press, 1994
https://doi.org/10.1145/168304.168338
79 F Denis, A Lemay, A Terlutte. Learning regular languages using non deterministic finite automata. In: Proceedings of International Colloquium on Grammatical Inference. 2000, 39–50
https://doi.org/10.1007/978-3-540-45257-7_4
80 R Alur, C Courcoubetis, T A Henzinger, Ho P H. Hybrid automata: an algorithmic approach to the specification and verification of hybrid systems. In: Grossman R L, Herode A, Ravn A P, eds.Hybrid Systems. Springer, Berlin, Heideberg, 1993
https://doi.org/10.1007/3-540-57318-6_30
81 W Van Der Aalst, A Adriansyah, A K A De Medeiros, F Arcieri, T Baier, T Blickle, J C Bose, V. d P Brand, R Brandtjen, J Buijs, et al.. Process mining manifesto. In: Proceedings of International Conference on Business Process Management. 2011, 169–194
82 C de la Higuera, J C Janodet. Inference of ω-languages from prefixes. Theoretical Computer Science, 2004, 313(2): 295–312
https://doi.org/10.1016/j.tcs.2003.11.009
83 J E Hopcroft, R Motwani, J D Ullman. Introduction to automata theory, languages, and computation. Journal of ACM Sigact News, 2001, 32(1): 60–65
https://doi.org/10.1145/568438.568455
84 B Bollig, P Habermehl, C Kern, M Leucker. Angluin-style learning of NFA. In: Proceedings of International Joint Conference on Artificial Intelligence. 2009, 1004–1009
85 M Merten, F Howar, B Steffen, T Margaria. Automata learning with onthe-fly direct hypothesis construction. In: Leveraging Applications of Formal Methods, Verification, and Validation. Springer, 2012
https://doi.org/10.1007/978-3-642-34781-8_19
86 O Maler, A Pnueli. On the learnability of infinitary regular sets. Journal of Information and Computation, 1995, 118(2): 316–326
https://doi.org/10.1006/inco.1995.1070
87 M N Irfan, C Oriat, R Groz. Model inference and testing. In: Advances in Computers. Elsevier, 2013
88 M J Kearns, U V Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994
https://doi.org/10.7551/mitpress/3897.001.0001
89 M Isberner, F Howar, B Steffen. The TTT algorithm: a redundancy-free approach to active automata learning. In: Proceedings of International Conference on Runtime Verification. 2014, 307–322
https://doi.org/10.1007/978-3-319-11164-3_26
90 A Groce, D Peled, M Yannakakis. Adaptive model checking. Logic Journal of the IGPL, 2006, 14(5): 729–744
https://doi.org/10.1093/jigpal/jzl007
91 W Smeenk, J Moerman, F Vaandrager, D N Jansen. Applying automata learning to embedded control software. In: Proceedings of International Conference on Formal Engineering Methods. 2015, 67–83
https://doi.org/10.1007/978-3-319-25423-4_5
92 D Lee, M Yannakakis. Principles and methods of testing finite state machines-a survey. Proceedings of IEEE, 1996, 84(8): 1090–1123
https://doi.org/10.1109/5.533956
93 V P Bos, R Smetsers, F Vaandrager. Enhancing automata learning by log-based metrics. In: Proceedings of International Conference on Integrated Formal Methods. 2016, 295–310
https://doi.org/10.1007/978-3-319-33693-0_19
94 Y F Chen, C Hsieh, O Lengál, T J Lii, MH Tsai , B Y Wang, F Wang. PAC learning-based verification and model synthesis. In: Proceedings of the 38th International Conference on Software Engineering. 2016, 714–724
https://doi.org/10.1145/2884781.2884860
95 T S Chow. Testing software design modeled by finite-state machines. IEEE Transactions on Software Engineering, 1978, 3: 178–187
https://doi.org/10.1109/TSE.1978.231496
96 S Fujiwara, G V Bochmann, F Khendek, M Amalou, A Ghedamsi. Tes selection based on finite state models. IEEE Transactions on Software Engineering, 1991, 17(6): 591–603
https://doi.org/10.1109/32.87284
97 Y Shen, F Lombardi, A T Dahbura. Protocol conformance testing using multiple UIO sequences. IEEE Transactions on Communications, 1992, 40(8): 1282–128 7
https://doi.org/10.1109/26.156631
98 S T Vuong. The uiov-method for protocol test sequence generation. In: Proceedings of the 2nd IFIP International Workshop on Protocol Test Systems. 1989, 161–175
99 F Aarts, B Jonsson, J Uijen. Generating models of infinite-state communication protocols using regular inference with abstraction. In: Proceedings of IFIP International Conference on Testing Software and Systems. 2010, 188–204
https://doi.org/10.1007/978-3-642-16573-3_14
100 F Aarts, B Jonsson, J Uijen, F Vaandrager. Generating models of infinitestate communication protocols using regular inference with abstraction. Journal of Formal Methods in System Design, 2015, 46(1): 1–41
https://doi.org/10.1007/s10703-014-0216-x
101 C Y Cho, D Babíc, E C R Shin, D Song. Inference and analysis of formal models of botnet command and control protocols. In: Proceedings of the 17th ACM Conference on Computer and Communications Security. 2010, 426–439
https://doi.org/10.1145/1866307.1866355
102 G Chalupar, S Peherstorfer, E Poll, J De Ruiter. Automated reverse engineering using lego® . In: Proceedings of the 8th {USENIX} Workshop on Offensive Technologies ({WOOT} 14). 2014
103 F Vaandrager. Active learning of extended finite state machines. In: Proceedings of International Conference on Testing Software and Systems. 2012, 5–7
https://doi.org/10.1007/978-3-642-34691-0_2
104 F Aarts, F Heidarian, H Kuppens, P Olsen, F Vaandrager. Automata learning through counterexample guided abstraction refinement. In: Proceedings of International Symposium on Formal Methods. 2012, 10–27
https://doi.org/10.1007/978-3-642-32759-9_4
105 F Aarts, F Heidarian, F Vaandrager. A theory of history dependent abstractions for learning interface automata. In: Proceedings of International Conference on Concurrency Theory. 2012, 240–255
https://doi.org/10.1007/978-3-642-32940-1_18
106 E M Gold. Complexity of automaton identification from given data. Journal of Information and Control, 1978, 37(3): 302–320
https://doi.org/10.1016/S0019-9958(78)90562-4
107 M Isberner, B Steffen, F Howar. Learnlib tutorial. In: Bartocci E, Majumdar R, eds.Runtime Verification. Springer, Cham, 2015, 358–377
https://doi.org/10.1007/978-3-319-23820-3_25
108 H Xiao. Automatic model learning and its applications in malware detection. Doctoral Dissertation, Nanyang Technological University, 2017
109 F D Aarts. Tomte: bridging the gap between active learning and realworld systems. Doctoral Dissertation, Radboud University Nijmegen, 2014
110 P Fiterau-Brostean. Active model learning for the analysis of network protocols. Doctoral Dissertation, Radboud University, 2018
111 M N Irfan. Analysis and optimization of software model inference algorithms. Universita de Grenoble, Grenoble, France, 2012
112 M X Czerny. Learning-based software testing: evaluation of angluin’s L* algorithm and adaptations in practice. Batchelors Thesis, Karlsruhe Institute of Technology, 2014
113 M Henrix. Performance improvement in automata learning. Master thesis, Radboud University, 2015
114 J Uijen. Learning models of communication protocols using abstraction techniques. Master Thesis, Uppscola University, 2009
115 F Aarts. Inference and abstraction of communication protocols. Master Thesis, Uppscola University, 2009
116 T Bohlin, B Jonsson. Regular inference for communication protocol entities. Technical Report 2008-024, Uppsala University, Computer Systems, 2008
117 T Berg. Regular inference for reactive systems. Doctoral Dissertation, Uppsala Universitet, 2006
118 T Berg, B Jonsson, M Leucker, M Saksena. Insights to angluin’s learning. Journal of Electronic Notes in Theoretical Computer Science, 2005, 118: 3–18
https://doi.org/10.1016/j.entcs.2004.12.015
119 M N Irfan. State machine inference in testing context with long counterexamples. In: Proceedings of International Conference on Software Testing, Verification and Validation. 2010, 508–511
https://doi.org/10.1109/ICST.2010.68
120 D P Sidhu, T K Leung. Formal methods for protocol testing: a detailed study. IEEE Transactions on Software Engineering, 1989, 15(4): 413–426
https://doi.org/10.1109/32.16602
121 R Dorofeeva, K El-Fakih, S Maag, A R Cavalli, N Yevtushenko. Experimental evaluation of fsm-based testing methods. In: Proceedings of the 3rd IEEE International Conference on Software Engineering and Formal Methods. 2005, 23–32
https://doi.org/10.1109/SEFM.2005.17
122 F Aarts, F Howar, H Kuppens, F Vaandrager. Algorithms for inferring register automata. In: Proceedings of International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. 2014, 202–219
https://doi.org/10.1007/978-3-662-45234-9_15
123 P Stevens, F Moller. The edinburgh concurrency workbench user manual (version 7.1). Laboratory for Foundations of Computer Science, University of Edinburgh, 1999, 7
124 O Maler, A Pnueli. On the learnability of infinitary regular sets. Information and Computation, 1991, 118: 316–326
https://doi.org/10.1006/inco.1995.1070
125 M N Irfan, C Oriat, R Groz. Angluin style finite state machine inference with non-optimal counterexamples. In: Proceedings of the 1st International Workshop on Model Inference in Testing. 2010, 11–19
https://doi.org/10.1145/1868044.1868046
126 M Merten, F Howar, B Steffen, T Margaria. Automata learning with onthe-fly direct hypothesis construction. In: Proceedings of International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. 2011, 248–260
https://doi.org/10.1007/978-3-642-34781-8_19
127 M Isberner, B Steffen. An abstract framework for counterexample analysis in active automata learning. In: Proceedings of International Conference on Grammatical Inference. 2014, 79–93
128 K Li, R Groz, M Shahbaz. Integration testing of distributed components based on learning parameterized I/O models. In: Proceedings of International Conference on Formal Techniques for Networked and Distributed Systems. 2006, 436–450
https://doi.org/10.1007/11888116_31
129 F Howar. Active Learning of Interface Programs. Doctoral Dissertation, TU Dortmund University, 2012
130 S Cassel, F Howar, B Jonsson, B Steffen. Learning extended finite state machines. In: Proceedings of International Conference on Software Engineering and Formal Methods. 2014, 250–264
https://doi.org/10.1007/978-3-319-10431-7_18
131 L D’Antoni, M Veanes. The power of symbolic automata and transducers. In: Proceedings of International Conference on Computer Aided Verification. 2017, 47–67
https://doi.org/10.1007/978-3-319-63387-9_3
132 M Isberner, F Howar, B Steffen. The open-source learnlib. In: Proceedings of International Conference on Computer Aided Verification. 2015, 487–495
https://doi.org/10.1007/978-3-319-21690-4_32
133 M Isberner, F Howar, B Steffen. The open-source learnlib. In: Proceedings of International Conference on Computer Aided Verification. 2015, 487–495
https://doi.org/10.1007/978-3-319-21690-4_32
134 H Raffelt, B Steffen. LearnLib a library for automata learning and experimentation. In: Proceedings of the 9th International Conference on Fundamental Approaches to Software Engineering. 2006, 377–380
https://doi.org/10.1007/11693017_28
135 M Isberner, F Howar, B Steffen. Inferring automata with state-local alphabet abstractions. In: Proceedings of NASA Formal Methods Symposium. 2013, 124–138
https://doi.org/10.1007/978-3-642-38088-4_9
136 J E Hopcroft, R M Karp. A linear algorithm for testing equivalence of finite automata. Technical Report, Cornell University, 1971
137 D Giannakopoulou, Z Rakamarič, V Raman. Symbolic learning of component interfaces. In: Proceedings of International Static Analysis Symposium. 2012, 248–264
https://doi.org/10.1007/978-3-642-33125-1_18
138 F Howar, D Giannakopoulou, Z Rakamarič. Hybrid learning: interface generation through static, dynamic, and symbolic analysis. In: Proceedings of the 2013 International Symposium on Software Testing and Analysis. 2013, 268–279
https://doi.org/10.1145/2483760.2483783
139 A Bainczyk, A Schieweck, M Isberner, T Margaria, J Neubauer, B Steffen. Alex: mixed-mode learning of web applications at ease. In: Proceedings of International Symposium on Leveraging Applications of Formal Methods. 2016, 655–671
https://doi.org/10.1007/978-3-319-47169-3_51
140 M Botinčan, D Babič. Sigma* symbolic learning of input-output specifications. Journal of ACM SIGPLAN Notices, 2013, 48(1): 443–456
https://doi.org/10.1145/2480359.2429123
141 B Bollig, J P Katoen, C Kern, M Leucker, D Neider, D R Piegdon. Libalf: the automata learning framework. In: Proceedings of International Conference on Computer Aided Verification. 2010, 360–364
https://doi.org/10.1007/978-3-642-14295-6_32
142 M Merten, B Steffen, F Howar, T Margaria. Next generation learnlib. In: Proceedings of International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 2011, 220–223
https://doi.org/10.1007/978-3-642-19835-9_18
143 S Cassel, F Howar, B Jonsson. RAlib: A learnLib extension for inferring EFSMs. DIFTS, 2015
144 A Khalili, A Tacchella. Aide: automata-identification engine. See Archive. codeplex Website, 2014
145 F Aarts, J Schmaltz, F Vaandrager. Inference and abstraction of the biometric passport. In: Proceedings of International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. 2010, 673–686
https://doi.org/10.1007/978-3-642-16558-0_54
146 F Aarts, J De Ruiter, E Poll. Formal models of bank cards for free. In: Proceedings of Software Testing, Verification and Validation Workshops. 2013, 461–468
https://doi.org/10.1109/ICSTW.2013.60
147 W Smeenk. Applying automata learning to complex industrial software. Master’s Thesis, Radboud University Nijmegen, 2012
148 R Janssen, F W Vaandrager, S Verwer. Learning a state diagram of tcp using abstraction. Bachelor Thesis, ICIS, Radboud University Nijmegen, 2013, 12
149 P Fiterău-Bro¸stean, R Janssen, F Vaandrager. Learning fragments of the tcp network protocol. In: Proceedings of International Workshop on Formal Methods for Industrial Critical Systems. 2014, 78–93
https://doi.org/10.1007/978-3-319-10702-8_6
150 M Tijssen. Automatic modeling of ssh implementations with state machine learning algorithms. Bachelor thesis, Radboud University, Nijmegen, 2014
151 T P Fiter, R Janssen, F Vaandrager. Combining model learning and model checking to analyze tcp implementations. In: Proceedings of International Conference on Computer Aided Verification. 2016, 454–471
https://doi.org/10.1007/978-3-319-41540-6_25
152 P Fiterău-Bro¸stean, T Lenaerts, E Poll, d J Ruiter, F Vaandrager, P Verleg. Model learning and model checking of SSH implementations. In: Proceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software. 2017, 142–151
https://doi.org/10.1145/3092282.3092289
153 M Schuts, J Hooman, F Vaandrager. Refactoring of legacy software using model learning and equivalence checking: an industrial experience report. In: Proceedings of International Conference on Integrated Formal Methods. 2016, 311–325
https://doi.org/10.1007/978-3-319-33693-0_20
154 J Neubauer, B Steffen, O Bauer, S Windmüller, M Merten, T Margaria, F Howar. Automated continuous quality assurance. In: Proceedings of International Workshop on Formal Methods in Software Engineering: Rigorous and Agile Approaches. 2012, 37–43
https://doi.org/10.1109/FormSERA.2012.6229787
155 S Windmüller, J Neubauer, B Steffen, F Howar, O Bauer. Active continuous quality control. In: Proceedings of the 16th International ACM Sigsoft Symposium on Component-based Software Engineering. 2013, 111–120
https://doi.org/10.1145/2465449.2465469
156 P Verleg, E Poll, F Vaandrager. SSH Inferringstate machines using protocol state fuzzing. Masters Thesis, Radboud University, 2016
157 A Groce, D Peled, M Yannakakis. Adaptive model checking. In: Proceedings of International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 2002, 269–301
https://doi.org/10.1007/3-540-46002-0_25
158 K Li, R Groz, M Shahbaz. Integration testing of components guided by incremental state machine learning. In: Proceedings of the Testing: Academic and Industrial Conference on Practice and Research Techniques. 2006, 59–70
159 M Shahbaz , R Groz. Analysis and testing of black-box component-based systems by inferring partial models. Journal of Software Testing, Verification and Reliability, 2014, 24(4): 253–288
https://doi.org/10.1002/stvr.1491
160 M Shahbaz, K Li, R Groz. Learning and integration of parameterized components through testing. In: Petrenko A, Veanes M, Tretmans J, Grieskamp W, eds. Testing of Software and Communicating Systems. Springer, Berlin, Hedelberg, 2007
https://doi.org/10.1007/978-3-540-73066-8_22
161 M Shahbaz, B Parreaux, F Klay. Model inference approach for detecting feature interactions in integrated systems. In: Proceedings of International Conference on Feature Interactions in Software and Communication Systems. 2007, 161–171
162 N Walkinshaw, K Bogdanov, J Derrick, J Paris. Increasing functional coverage by inductive testing: a case study. In: Proceedings of International Conference on Testing Software and Systems. 2010, 126–141
https://doi.org/10.1007/978-3-642-16573-3_10
163 JM Cobleigh, D Giannakopoulou, C S Pasareanu. Learning assumptions for compositional verification. In: Proceedings of International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 2003, 331–346
https://doi.org/10.1007/3-540-36577-X_24
164 S C Păsăreanu, D Giannakopoulou, M G Bobaru, J M Cobleigh, H Barringer. Learning to divide and conquer: applying the L* algorithm to automate assume-guarantee reasoning. Formal Methods in System Design, 2008, 32(3): 175–205
https://doi.org/10.1007/s10703-008-0049-6
165 F He, S Mao, B Y Wang. Learning-based assume-guarantee regression verification. In: Proceedings of International Conference on Computer Aided Verification. 2016, 310–328
https://doi.org/10.1007/978-3-319-41528-4_17
166 Y F Chen, E M Clarke, A Farzan, F He, M H Tsai, Y K Tsay, B Y Wang, L Zhu. Comparing learning algorithms in automated assume-guarantee reasoning. In: Proceedings of International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. 2010, 643–657
https://doi.org/10.1007/978-3-642-16558-0_52
167 Y F Chen, E M Clarke, A Farzan, M H Tsai, Y K Tsay, B Y Wang. Automated assume-guarantee reasoning through implicit learning. In: Proceedings of International Conference on Computer Aided Verification. 2010, 511–526
https://doi.org/10.1007/978-3-642-14295-6_44
168 F He, B Y Wang, L Yin, L Zhu. Symbolic assume-guarantee reasoning through BDD learning. In: Proceedings of the 36th International Conference on Software Engineering. 2014, 1071–1082
169 S W Lin, P A Hsiung. Compositional synthesis of concurrent systems through causal model checking and learning. In: Proceedings of International Symposium on Formal Methods. 2014, 416–431
https://doi.org/10.1007/978-3-319-06410-9_29
170 D Neider, U Topcu. An automaton learning approach to solving safety games over infinite graphs. In: Proceedings of International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 2016, 204–221
https://doi.org/10.1007/978-3-662-49674-9_12
171 T Margaria, O Niese, B Steffen, A Erochok. System level testing of virtual switch (re-) configuration over IP. In: Proceedings of the 7th IEEE European Test Workshop. 2002, 67–72
172 O Niese, B Steffen, T Margaria, A Hagerer, G Brune, H D Ide. Librarybased design and consistency checking of system-level industrial test cases. In: Proceedings of International Conference on Fundamental Approaches to Software Engineering, 2001, 233–248
https://doi.org/10.1007/3-540-45314-8_17
173 L Feng, S Lundmark, K Meinke, F Niu, M A Sindhu, P Y Wong. Case studies in learning-based testing. In: Proceedings of International Conference on Testing Software and Systems. 2013, 164–179
https://doi.org/10.1007/978-3-642-41707-8_11
174 A L Oliveira, J P Silva. Efficient algorithms for the inference of minimum size dfas. Journal of Machine Learning, 2001, 44(1–2): 93–119
https://doi.org/10.1023/A:1010828029885
175 W Choi, G Necula, K Sen. Guided gui testing of android apps with minimal restart and approximate learning. ACM SIGPLAN Notices, 2013, 48(10): 623–640
https://doi.org/10.1145/2544173.2509552
176 R Alur, P Černỳ, P Madhusudan, W Nam. Synthesis of interface specifications for java classes. ACM SIGPLAN Notices, 2005, 40(1): 98–109
https://doi.org/10.1145/1047659.1040314
177 H Xiao, J Sun, Y Liu, S W Lin, C Sun. Tzuyu: learning stateful typestates. In: Proceedings of the 28th International Automated Software Engineering. 2013, 432–442
https://doi.org/10.1109/ASE.2013.6693101
178 H Raffelt, B Steffen, T Margaria. Dynamic testing via automata learning. In: Proceedings of Haifa Verification Conference. 2007, 136–152
https://doi.org/10.1007/978-3-540-77966-7_13
179 E Clarke, D Long, K McMillan. Compositional model checking. In: Proceedings of the 4th Annual Symposium on Logic in Computer Science. 1989
180 W Smeenk , FW Vaandrager. Applying automata learning to complex industrial software. Master’s Thesis, Radboud University Nijmegen, 2012
181 M Tappler, B K Aichernig, R Bloem. Model-based testing IoT communication via active automata learning. In: Proceedings of IEEE International Conference on Software Testing, Verification and Validation. 2017, 276–287
https://doi.org/10.1109/ICST.2017.32
182 F Aarts, P Fiterau-Brostean, H Kuppens, F Vaandrager. Learning register automata with fresh value generation. In: Proceedings of International Colloquium on Theoretical Aspects of Computing. 2015, 165–183
https://doi.org/10.1007/978-3-319-25150-9_11
183 K Meinke, M A Sindhu. Incremental learning-based testing for reactive systems. In: Proceedings of International Conference on Tests and Proofs. 2011, 134–151
https://doi.org/10.1007/978-3-642-21768-5_11
184 M Volpato, J Tretmans. Active learning of nondeterministic systems from an ioco perspective. In: Proceedings of International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. 2014, 220–235
https://doi.org/10.1007/978-3-662-45234-9_16
185 R Groz, M N Irfan, C Oriat. Algorithmic improvements on regular inference of software models and perspectives for security testing. In: Proceedings of International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. 2012, 444–457
https://doi.org/10.1007/978-3-642-34026-0_33
186 M D Ernst, J H Perkins, P J Guo, S McCamant, C Pacheco, M S Tschantz, C Xiao. The daikon system for dynamic detection of likely invariants. Journal of Science of Computer Programming, 2007, 69(1–3): 35–45
https://doi.org/10.1016/j.scico.2007.01.015
187 L Nachmanson, M Veanes, W Schulte, N Tillmann, W Grieskamp. Optimal strategies for testing nondeterministic systems. ACM SIGSOFT Software Engineering Notes, 2004, 29(4): 55–64
https://doi.org/10.1145/1013886.1007520
188 M Volpato, J Tretmans. Approximate active learning of nondeterministic input output transition systems. Electronic Communications of the EASST, 2015, 72
189 A Khalili, A Tacchella. Learning nondeterministic mealy machines. In: Proceedings of International Conference on Grammatical Inference. 2014, 109–123
190 K El-Fakih, R Groz, M N Irfan, M Shahbaz. Learning finite state models of observable nondeterministic systems in a testing context. In: Proceedings of International Conference on Testing Software and Systems. 2010, 97–102
191 V Dallmeier. Mining and checking object behavior. Doctoral Dissertation, 2010
192 WM P Van der Aalst, V Rubin, H M W Verbeek, V B F Dongen, E Kindler, C W Günther. Process mining: a two-step approach to balance between underfitting and overfitting. Journal of Software & Systems Modeling, 2010, 9(1): 87
https://doi.org/10.1007/s10270-008-0106-z
193 K Meinke. CGE: a sequential learning algorithm for mealy automata. In: Proceedings of International Colloquium on Grammatical Inference. 2010, 148–162
https://doi.org/10.1007/978-3-642-15488-1_13
194 D Peled, MY Vardi , M Yannakakis. Black box checking. In: Wu J, Chanson S T, Gao Q, eds. Formal Methods for Protocol Engineering and Distributed Systems. Springer, Boston, MA, 1999
https://doi.org/10.1007/978-0-387-35578-8_13
195 S Cassel, F Howar, B Jonsson, M Merten, B Steffen. A succinct canonical register automaton model. In: Proceedings of International Symposium on Automated Technology for Verification and Analysis. 2011, 366–380
https://doi.org/10.1007/978-3-642-24372-1_26
[1] Article highlights Download
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed