betaFeedback

WorksComputer Science

Leveraging Restrictions to Optimize Register Automata Learning

Abstract

Active automata learning algorithms, especially those that are able to learn extended finite state machines, such as register automata, can capture the behavior of complex systems and help analyses that uncover critical bugs in them. However, the performance and scalability of these algorithms often becomes an issue when models increase in size. SLλSL^λ, the current state-of-the-art algorithm for learning register automata, uses a cost-efficient data structure with mechanisms for computing short and restricted tests. In this paper, we present SL=λSL^λ_{=}, an extension of SLλSL^λ for the theory of equality, which improves scalability by employing knowledge gained from prior tests at subsequent steps to restrict future tests to only those that are necessary to achieve progress in the next step. We have implemented SL=λSL^λ_{=} as a new algorithm in RALib, and evaluate its performance by comparing it against SL∗SL^{*} and SLλSL^λ on a series of benchmarks, including five widely used implementations of DTLS servers. Our evaluation shows that SL=λSL^λ_{=} needs significantly fewer tests than SL∗SL^{*} and SLλSL^λ to infer models of systems, and scales clearly better than them.

Introduction

Model Learning, also known as Active Automata Learning (AAL) [7, 44, 55], uses tests to infer automata models that represent the dynamic behavior of software or hardware components. Models obtained by AAL have proven useful for many purposes, such as analyzing security protocols [22, 23, 45, 50] [28], mining APIs [6], supporting model-based testing [30, 52, 57] and conformance testing [4]. Efficient AAL algorithms have been developed [7, 33, 35, 44, 54] and implemented [36], supported by various domain-specific optimizations. However, their scope is limited to finite state machine (FSM) models, such as Mealy machines.

For many analysis tasks, however, it is crucial for models to also be able to describe data flow, including constraints on data parameters that are passed between the component and its environment, as well as the mutual influence between dynamic behavior and data flow. For instance, models of protocol components should describe how different values of sequence numbers, identifiers, etc. influence and are influenced by dynamic behavior. This has motivated several approaches for extending AAL to Extended Finite State Machine (EFSM) models. Some approaches reduce the problem to inferring FSMs by employing manually supplied abstractions on the data domain [3, 5]; this requires insight into the control/data dependencies of the System Under Learning (SUL). Other approaches extend AAL for finite state models by allowing transitions to contain predicates over rich data domains, but cannot generate state variables to model data dependencies between consecutive interactions [16, 39]. Finally, there exist extensions to EFSM models with state variables and guards from a fixed theory, such as Register Automata (RA) [1, 2, 13, 14, 34], automata which can express relations between data parameters. RA models have uncovered bugs in e.g., TCP implementations [19, 20], but the learning algorithms that these works used do not scale well, especially with increasing numbers of registers.

This work aims to improve the scalability of state-of-the-art RA learning algorithms. The main challenge is reducing the number of tests that are performed. In typical RA learning algorithms, tests are sequences of actions (e.g., protocol messages or API calls) of form uvuv, composed from a prefix uu and a suffix vv. When learning FSMs, such tests are used to determine whether prefixes uu and u′u' can be distinguished by the SUL’s reaction to uvuv and u′vu'v for some vv. In RA learning, such tests must also detect dependencies between data parameters in the prefix uu and the suffix vv. Such dependencies are inferred by varying the data parameters in vv to examine how the choice of parameters in uu affect the SUL’s reaction to the composition uvuv. These dependencies are then used to infer state variables and guards on outgoing transitions from uu; prefixes that are separated by differences in these dependencies will lead to different control states in the learned RA. For instance, if the SUL reacts differently to a(1)b(1)a(1)b(1) and a(1)b(2)a(1)b(2), it is inferred that the parameter of aa must be remembered in a state variable; if it also does not distinguish c(1)b(1)c(1)b(1) from c(1)b(2)c(1)b(2), then a(1)a(1) and c(1)c(1) must lead to different control locations. A main scalability problem is that in a naïve approach, the number of tests for inferring dependencies grows exponentially with the length of the suffix. The SLλSL^\lambda algorithm [14, 15], the current state-of-the-art in RA learning, addressed this by (i) reducing the number of tested prefix-suffix combinations by employing a classification tree [35, 37], (ii) preferring shorter suffixes over longer ones [33], and (iii) employing a simple scheme for restricting the range of values considered in suffixes. These techniques achieve significant performance improvements over SLλSL^\lambda [13], the previous state-of-the-art algorithm. However, the restriction scheme of SLλSL^\lambda is simplistic; suffix parameters can be restricted only if they have no dependencies to any prefix parameter. In SULs which exhibit many data dependencies, this causes a large subset of suffixes to be unrestricted, potentially causing an exponential blow-up in the number of tests.

This paper introduces SL≡λSL^\lambda_{\equiv}, an extension of SLλSL^\lambda optimized for inferring RA models with equality relations between values of data parameters. In addition to the simple restrictions that SLλSL^\lambda comes with, SL≡λSL^\lambda_{\equiv} also allows to restrict parameters to be equal to one or more prefix values by using information gained about dependencies between suffix parameters and prefix values. For example, if it is detected that a(1)a(1) and a(1)a(2)a(1)a(2) are separated by b(1)b(1)b(1)b(1) then SL≡λSL^\lambda_{\equiv} restricts the data parameters to these values (1 and 1) also when investigating whether another prefix, e.g., a(1)a(2)a(3)a(1)a(2)a(3), can be distinguished from a(1)a(1) or a(1)a(2)a(1)a(2). This allows SL=λSL^\lambda_{=} to separate locations using only one test in most cases, in contrast to the seventeen tests that SLλSL^\lambda would use, corresponding to the possible inequivalent instantiations of the parameters of b(p1)b(p2)b(p_1)b(p_2) after the prefix a(1)a(2)a(3)a(1)a(2)a(3).

We present the SL=λSL^\lambda_{=} algorithm in detail (Section 4), and prove (§ 5) that SL=λSL^\lambda_{=}, when presented with a data language L\mathcal{L} of finite index, is guaranteed to infer a minimal (in the number of locations) RA which accepts L\mathcal{L}.

We have implemented SL=λSL^\lambda_{=} as a new algorithm in RALib [12], a library for RA learning which comes with implementations of SL∗SL^* [13] and SLλSL^\lambda [14, 15]. Our performance evaluation (§ 6), on a variety of benchmarks, including experiments to learn models for five DTLS server implementations, shows that SL=λSL^\lambda_{=} uses fewer tests than the other two algorithms, both during model construction and in total, and scales much better than them as SULs increase in size.

Related Work. AAL has been researched for almost four decades; see [31, 32] for overviews. Applications of AAL include generation of behavioral models for software [48, 51], e.g. for network protocol implementations [22, 45], security analyses and model checking [3, 21, 24], testing [41, 49], and formal analyses of systems [55]. Learning beyond FSMs has been investigated for many models aside from register automata. For example, algorithms have been presented for workflow Petri nets [18], data automata [26], generic nondeterministic transition systems [56], symbolic automata [16, 40], NetKAT programs [42], automata with timers [10, 53], sub-classes of timed automata [27], session automata [9], and procedural systems [25].

Several algorithms combine learning algorithms for FSMs with various approaches for inferring symbolic data constraints: Daikon [17] has been combined with state merging for passive learning [38]; FSM learners have been combined with a bespoke inference of data constraints [19], or with genetic programming [29]. One approach for learning EFSMs combines an FSM learner with a manually created abstraction module that maps symbolic RA transitions to a finite alphabet [1, 2]. Another approach for inferring registers is to extend the learning model with memorability queries that directly provide registers [8].

The previous approaches do not tackle the problem of inferring registers from only membership and equality queries. Approaches that address this problem include that of Sakamoto [47], which presented the first AAL algorithm for a version of register automata, called finite memory automata, that was never implemented. More closely related to our work are the RA learning algorithms [13, 14] implemented in RALib. Compared to these algorithms, and to SLλSL^\lambda in particular, we employ more fine-grained restrictions, which result in significant performance improvements and better scalability, as we demonstrate in § 6.

Main Ideas

In this section, we introduce the main ideas behind the SL=λSL^\lambda_{=} algorithm and how it differs from SLλSL^\lambda. As an illustrating example, we will use the data language LP(n)\mathcal{L}_{P(n)}, which assumes a data domain N\mathbb{N} of natural numbers and the single action a. In the context of LP(n)\mathcal{L}_{P(n)}, a data symbol is a term of form a(d), where the parameter d is a natural number, and a data word (or word) is a finite sequence of data symbols. A data language L\mathcal{L} is a set of data words, such that membership in L\mathcal{L} depends only on the equalities and inequalities between its parameters; put differently, if the word w is in L\mathcal{L} then any bijection on N\mathbb{N} applied to w is also in L\mathcal{L}. The language LP(n)\mathcal{L}_{P(n)} contains words of length at most n in which the parameters form a palindrome. In the following, we will consider LP(3)\mathcal{L}_{P(3)}; for example, a(5)a(5) and a(3)a(1)a(3) are in LP(3)\mathcal{L}_{P(3)}, but a(5)a(7) and a(3)a(1)a(2) are not.

The task of AAL is to learn an acceptor for LP(3)\mathcal{L}_{P(3)} in a black-box scenario, i.e., knowing only the alphabet {a}\{a\} and the data domain, by asking two kinds of queries: A membership query (MQ) asks whether a word w is in LP(3)\mathcal{L}_{P(3)}; it can be realized by a simple test. An equivalence query (EQ) asks whether a hypothesis H\mathcal{H} accepts LP(3)\mathcal{L}_{P(3)}; it is answered either by yes or by a counterexample, i.e., a word on which L(H)\mathcal{L}(\mathcal{H}) and LP(3)\mathcal{L}_{P(3)} disagree; Typically, a sequence of MQs is used to construct H\mathcal{H}, which is then subject to validation by an EQ; if a counterexample is found, hypothesis construction is resumed, etc., until convergence.

An acceptor for LP(3)\mathcal{L}_{P(3)}, in the form of a register automaton is shown in Figure 1. This RA can be the output of an AAL algorithm. It has four accepting locations (l0l_0, l1l_1, l2l_2, and l3l_3) and two rejecting locations (l4l_4 and a sink location, not shown). Each location is labeled by its set of active registers (e.g., {x1}\{x_1\} in l2l_2). Each transition is labeled by a parameterized data symbol a(p), a guard (to right), and an assignment to registers (bottom). The guard is a boolean combination of equalities and negated equalities between p and registers. The RA processes a data word by considering its data symbols one by one, starting in the initial location l0l_0. When in a location lil_i and seeing a symbol a(d), it (i) matches the parameterized data symbol a(p) with a(d) (essentially assigning d to p) (ii) selects an outgoing transition from lil_i whose guard evaluates to true when p is assigned d, (iii) performs that transition’s assignment to registers, and (iv) moves to its target location. The accepting locations l0l_0 and l1l_1 are reached on words of length zero and one, respectively. The accepting location l2l_2 is reached on inputs a(d1d_1)a(d2d_2) of length two where d1=d2d_1=d_2 whereas the rejecting location l4l_4 corresponds to inputs a(d1d_1)a(d2d_2) where d1≠d2d_1\ne d_2, and l3l_3 corresponds to inputs a(d1d_1)a(d2d_2)a(d3d_3) where d1=d3d_1=d_3. In locations l1l_1, l2l_2 and l4l_4 register x1x_1 stores the parameter of the first symbol in the word.

Register automaton accepting language $\mathcal{L}_{P(3)}$

Figure 1. Register automaton accepting language LP(3)\mathcal{L}_{P(3)}.

References

  1. [1]Aarts, F., Fiterău-Broșțean, P., Kuppens, H., Vaandrager, F.: Learning register automata with fresh value generation. In: Leucker, M., Rueda, C., Valencia, F.D. (eds.) Theoretical Aspects of Computing - ICTAC 2015. LNCS, vol. 9399, pp. 165–183. Springer International Publishing, Cham (Oct 2015). https://doi.org/10.1007/978-3-319-25150-9_11
  2. [2]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: Formal Methods. LNCS, vol. 7436, pp. 10–27. Springer, Berlin, Heidelberg (Aug 2012). https://doi.org/10.1007/978-3-642-32759-9_4
  3. [3]Aarts, F., Jonsson, B., Uijen, J., Vaandrager, F.: Generating models of infinite-state communication protocols using regular inference with abstraction. Formal Methods in System Design 46(1), 1–41 (Feb 2015). https://doi.org/10.1007/s10703-014-0216-x
  4. [4]Aarts, F., Kuppens, H., Tretmans, J., Vaandrager, F.W., Verwer, S.: Learning and testing the bounded retransmission protocol. In: Proceedings of the Eleventh International Conference on Grammatical Inference, ICGI 2012. JMLR Proceedings, vol. 21, pp. 4–18. JMLR.org, College Park, MA, USA (Sep 2012), http://proceedings.mlr.press/v21/aarts12a.html
  5. [5]Aarts, F., Schmaltz, J., Vaandrager, F.: Inference and abstraction of the biometric passport. In: Margaria, T., Steffen, B. (eds.) International Symposium On Leveraging Applications of Formal Methods, Verification and Validation. LNCS, vol. 6415, pp. 673–686. Springer, Berlin, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16558-0_54
  6. [6]Ammons, G., Bodík, R., Larus, J.R.: Mining specifications. In: Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. pp. 4–16. POPL ’02, ACM, New York, NY, USA (Jan 2002). https://doi.org/10.1145/503272.503275
  7. [7]Angluin, D.: Learning regular sets from queries and counterexamples. Information and Computation 75(2), 87–106 (1987). https://doi.org/10.1016/0890-5401(87)90052-6
  8. [8]Balachander, M., Filiot, E., Gentilini, R., Tzevelekos, N.: Register automata with permutations. In: 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), vol. 345, pp. 14:1–14:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2025). https://doi.org/10.4230/LIPIcs.MFCS.2025.14
  9. [9]Bollig, B., Habermehl, P., Leucker, M., Monmege, B.: A fresh approach to learning register automata. In: Developments in Language Theory. LNCS, vol. 7907, pp. 118–130. Springer, Berlin, Heidelberg (Jun 2013). https://doi.org/10.1007/978-3-642-38771-5_12
  10. [10]Bruÿere, V., Garhewal, B., Pérez, G.A., Stacquet, G., Vaandrager, F.W.: Active learning of Mealy machines with timers. In: Prabhakar, P., Vandin, A. (eds.) International Conference on Quantitative Evaluation of Systems and Formal Modeling and Analysis of Timed Systems. LNCS, vol. 16143, pp. 42–61. Springer, Cham (Oct 2025). https://doi.org/10.1007/978-3-032-05792-1_3
  11. [11]Cassel, S., Howar, F., Jonsson, B., Merten, M., Steffen, B.: A succinct canonical register automaton model. J. Log. Algebr. Meth. Program. 84(1), 54–66 (Jan 2015). https://doi.org/10.1016/j.jlamp.2014.07.004
  12. [12]Cassel, S., Howar, F., Jonsson, B.: RALib: a LearnLib extension for inferring EFSMs. In: Proceedings of the 4th International Workshop on Design and Implementation of Formal Tools and Systems (DIFTS). pp. 1–8 (Sep 2015), https://www.faculty.ece.vt.edu/chaowang/difts2015/papers/paper_5.pdf
  13. [13]Cassel, S., Howar, F., Jonsson, B., Steffen, B.: Active learning for extended finite state machines. Formal Asp. Comput. 28(2), 233–263 (2016). https://doi.org/10.1007/s00165-016-0355-5
  14. [14]Dierl, S., Fiterău-Broștean, P., Howar, F., Jonsson, B., Sagonas, K., Tăqūist, F.: Scalable tree-based register automata learning. In: Tools and Algorithms for the Construction and Analysis of Systems - 30th International Conference, TACAS 2024, Proceedings, Part II. LNCS, vol. 14571, pp. 87–108. Springer, Cham (Apr 2024). https://doi.org/10.1007/978-3-031-57249-4_5
  15. [15]Dierl, S., Fiterău-Broștean, P., Howar, F., Jonsson, B., Sagonas, K., Tăqūist, F.: SL^λ: A scalable algorithm for register automata learning. J. Autom. Reason. 70(2) (Dec 2026). https://doi.org/10.1007/S10817-026-09758-9
  16. [16]Drews, S., D’Antoni, L.: Learning symbolic automata. In: Legay, A., Margaria, T. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 10205, pp. 173–189. Springer, Berlin, Heidelberg (Apr 2017). https://doi.org/10.1007/978-3-662-54577-5_10
  17. [17]Ernst, M.D., Perkins, J.H., Guo, P.J., McCamant, S., Pacheco, C., Tschantz, M.S., Xiao, C.: The Daikon system for dynamic detection of likely invariants. Science of Computer Programming 69(1-3), 35–45 (2007). https://doi.org/10.1016/j.scico.2007.01.015
  18. [18]Esparza, J., Leucker, M., Schlund, M.: Learning workflow Petri nets. Fundamenta Informaticae 113(3-4), 205–228 (2011). https://doi.org/10.3233/FI-2011-607
  19. [19]Ferreira, T., Brewton, H., D’Antoni, L., Silva, A.: Pronosis: Closed-box analysis of network protocol implementations. In: Proceedings of the 2021 ACM SIGCOMM 2021 Conference. pp. 762–774. ACM, New York, NY, USA (Aug 2021). https://doi.org/10.1145/3452296.3472938
  20. [20]Fiterău-Broștean, P., Howar, F.: Learning-based testing the sliding window behavior of TCP implementations. In: Critical Systems: Formal Methods and Automated Verification - Joint 22nd International Workshop on Formal Methods for Industrial Critical Systems - and - 17th International Workshop on Automated Verification of Critical Systems, FMICS-AVoCS. LNCS, vol. 10471, pp. 185–200. Springer, Cham (Sep 2017). https://doi.org/10.1007/978-3-319-67113-0_12
  21. [21]Fiterău-Broștean, P., Janssen, R., Vaandrager, F.: Combining model learning and model checking to analyze TCP implementations. In: Chaudhuri, S., Farzan, A. (eds.) Computer Aided Verification. LNCS, vol. 9780, pp. 454–471. Springer International Publishing, Cham (Jul 2016). https://doi.org/10.1007/978-3-319-41540-6_25
  22. [22]Fiterău-Broștean, P., Jonsson, B., Merget, R., de Ruiter, J., Sagonas, K., Somorovsky, J.: Analysis of DTLS implementations using protocol state fuzzing. In: 29th USENIX Security Symposium (USENIX Security 20). pp. 2523–2540. USENIX Association, Boston, MA, USA (Aug 2020), https://www.usenix.org/conference/usenixsecurity20/presentation/fiterau-brostean
  23. [23]Fiterău-Broștean, P., Jonsson, B., Sagonas, K., Tăquist, F.: Automata-based automated detection of state machine bugs in protocol implementations. In: Network and Distributed System Security Symposium. NDSS 2023, The Internet Society, San Diego, CA, USA (Feb 2023), https://www.ndss-symposium.org/wp-content/uploads/2023/02/ndss23_68_paper.pdf
  24. [24]Fiterău-Broștean, P., Lenaerts, T., Poll, E., de Ruiter, J., Vaandrager, F., Verleg, P.: Model learning and model checking of SSH implementations. In: Proceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software. pp. 142–151. ACM, New York, NY, USA (Jul 2017). https://doi.org/10.1145/3092282.3092289
  25. [25]Frohme, M., Steffen, B.: Compositional learning of mutually recursive procedural systems. International Journal on Software Tools for Technology Transfer 23(4), 521–543 (Aug 2021). https://doi.org/10.1007/s10009-021-00634-y
  26. [26]Garg, P., Löding, C., Madhusudan, P., Neider, D.: Learning universally quantified invariants of linear data structures. In: Sharygina, N., Veith, H. (eds.) Computer Aided Verification. LNCS, vol. 8044, pp. 813–829. Springer, Berlin, Heidelberg (Jul 2013). https://doi.org/10.1007/978-3-642-39799-8_57
  27. [27]Grinchtein, O., Jonsson, B., Pettersson, P.: Inference of event-recording automata using timed decision trees. In: Baier, C., Hermanns, H. (eds.) CONCUR 2006 – Concurrency Theory. LNCS, vol. 4137, pp. 435–449. Springer, Berlin, Heidelberg (Aug 2006). https://doi.org/10.1007/11817949_29 Groz, R., Irfan, M.N., Oriat, C.: Algorithmic improvements on regular inference of software models and perspectives for security testing. In: Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change. ISoLA 2012. LNCS, vol. 7609, pp. 444–457. Springer, Berlin, Heidelberg (Oct 2012). https://doi.org/10.1007/978-3-642-34026-0_33
  28. [29]Groz, R., Oriat, C., Vega, G., da Silva Simão, A., Foster, M., Walkinshaw, N.: Active inference of extended finite state models of software systems. In: Coste, F., Ouardi, F., Rabusseau, G. (eds.) Proceedings of 16th edition of the International Conference on Grammatical Inference. Proceedings of Machine Learning Research, vol. 217, pp. 265–269. ML Research Press, Cambridge, MA (2023), https://proceedings.mlr.press/v217/groz23a/groz23a.pdf
  29. [30]Hagerer, A., Hungar, H., Niese, O., Steffen, B.: Model generation by moderated regular extrapolation. In: Kutsche, R.D., Weber, H. (eds.) Fundamental Approaches to Software Engineering, 5th International Conference, FASE 2002. LNCS, vol. 2306, pp. 80–95. Springer, Berlin, Heidelberg (Apr 2002). https://doi.org/10.1007/3-540-45923-5_6
  30. [31]de la Higuera, C.: A bibliographical study of grammatical inference. Pattern Recognition 38(9), 1332–1348 (Sep 2005). https://doi.org/10.1016/j.patcog.2005.01.003
  31. [32]Howar, F., Steffen, B.: Active automata learning in practice. In: Bennaceur, A., Hähnle, R., Meinke, K. (eds.) Machine Learning for Dynamic Software Analysis: Potentials and Limits, LNCS, vol. 11026, pp. 123–148. Springer International Publishing, Cham (Aug 2018). https://doi.org/10.1007/978-3-319-96562-8_5
  32. [33]Howar, F., Steffen, B.: Active automata learning as black-box search and lazy partition refinement. In: Jansen, N., Stoelinga, M., van den Bos, P. (eds.) A Journey from Process Algebra via Timed Automata to Model Learning. LNCS, vol. 13560, pp. 321–338. Springer, Cham (Sep 2022). https://doi.org/10.1007/978-3-031-15629-8_17
  33. [34]Howar, F., Steffen, B., Jonsson, B., Cassel, S.: Inferring canonical register automata. In: Kunčak, V., Rybalchenko, A. (eds.) Verification, Model Checking, and Abstract Interpretation - 13th International Conference, VMCAI 2012, Proceedings. LNCS, vol. 7148, pp. 251–266. Springer, Berlin, Heidelberg (Jan 2012). https://doi.org/10.1007/978-3-642-27940-9_17
  34. [35]Isberner, M., Howar, F., Steffen, B.: The TTT algorithm: A redundancy-free approach to active automata learning. In: Runtime Verification: 5th International Conference, RV 2014, Proceedings. LNCS, vol. 8734, pp. 307–322. Springer, Cham (Sep 2014). https://doi.org/10.1007/978-3-319-11164-3_26
  35. [36]Isberner, M., Howar, F., Steffen, B.: The open-source LearnLib - A framework for active automata learning. In: Computer Aided Verification - 27th International Conference, CAV. LNCS, vol. 9206, pp. 487–495. Springer (Jul 2015). https://doi.org/10.1007/978-3-319-21690-4_32
  36. [37]Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA (1994)DOI
  37. [38]Lorenzoli, D., Mariani, L., Pezzè, M.: Automatic generation of software behavioral models. In: Proceedings of the 30th International Conference on Software Engineering. pp. 501–510. ICSE ’08, ACM, New York, NY, USA (May 2008). https://doi.org/10.1145/1368088.1368157
  38. [39]Maler, O., Mens, I.E.: Learning regular languages over large alphabets. In: Tools and Algorithms for the Construction and Analysis of Systems - 20th International Conference, LNCS, vol. 8413, pp. 485–499. Springer, Berlin, Heidelberg (Apr 2014). https://doi.org/10.1007/978-3-642-54862-8_41
  39. [40]Maler, O., Mens, I.: A generic algorithm for learning symbolic automata from membership queries. In: Aceto, L., Bacci, G., Bacci, G., Ingólfsdóttir, A., Legay, A., Mardare, R. (eds.) Models, Algorithms, Logics and Tools. LNCS, vol. 10460, pp. 146–169. Springer, Cham (Aug 2017). https://doi.org/10.1007/978-3-319-63121-9_8
  40. [41]Margaria, T., Niese, O., Rafelt, H., Steffen, B.: Efficient test-based model generation for legacy reactive systems. In: Proceedings of the Ninth IEEE International High-Level Design Validation and Test Workshop. pp. 95–100. IEEE, New York, NY, USA (Nov 2004). https://doi.org/10.1109/HLDVT.2004.1431246
  41. [42]Moeller, M., Ferreira, T., Lu, T., Foster, N., Silva, A.: Active learning of symbolic NetKAT automata. Proc. ACM Program. Lang. 9(PLDI), 1119–1142 (Jun 2025). https://doi.org/10.1145/3729295
  42. [43]Neider, D., Smetsers, R., Vaandrager, F.W., Kuppens, H.: Benchmarks for automata learning and conformance testing. In: Models, Mindsets, Meta: The What, the How, and the Why Not? - Essays Dedicated to Bernhard Steffen on the Occasion of His 60th Birthday. LNCS, vol. 11200, pp. 390–416. Springer, Cham (Jun 2018). https://doi.org/10.1007/978-3-030-22348-9_23
  43. [44]Rivest, R.L., Schapire, R.E.: Inference of finite automata using homing sequences. Information and Computation 103(2), 299–347 (1993). https://doi.org/10.1006/inco.1993.1021
  44. [45]de Ruiter, J., Poll, E.: Protocol state fuzzing of TLS implementations. In: 24th USENIX Security Symposium (USENIX Security 15). pp. 193–206. USENIX Association, Washington, D.C., USA (Aug 2015). https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/de-ruiter
  45. [46]Sagonas, K., Jonsson, B., Howar, F., Dierl, S., Fiterău-Broștean, P., Tăquist, F.: Reproduction artifact for TACAS 2024 paper “Scalable tree-based register automata learning” (Dec 2023). https://doi.org/10.5281/zenodo.10442556
  46. [47]Sakamoto, H.: Learning simple deterministic finite-memory automata. In: Algorithmic Learning Theory. ALT ’97. LNCS, vol. 1316, pp. 416–431. Springer-Verlag, Berlin, Heidelberg (Oct 1997). https://doi.org/10.1007/3-540-63577-7_58
  47. [48]Schuts, M., Hooman, J., Vaandrager, F.: Refactoring of legacy software using model learning and equivalence checking: An industrial experience report. In: Ábrahám, E., Huisman, M. (eds.) Integrated Formal Methods. LNCS, vol. 9681, pp. 311–325. Springer International Publishing, Cham (Jun 2016). https://doi.org/10.1007/978-3-319-33693-0_20
  48. [49]Shahbaz, M., Groz, R.: Analysis and testing of black-box component-based systems by inferring partial models. Software Testing, Verification and Reliability 24(4), 253–288 (2014). https://doi.org/10.1002/stvr.1491
  49. [50]Shu, G., Lee, D.: Testing security properties of protocol implementations - a machine learning based approach. In: 27th IEEE International Conference on Distributed Computing Systems. p. 25. ICDCS 2007, IEEE Computer Society, Los Alamitos, CA (Jun 2007). https://doi.org/10.1109/ICDCS.2007.147
  50. [51]Sun, J., Xiao, H., Liu, Y., Lin, S.W., Qin, S.: TLV: abstraction through testing, learning, and validation. In: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering. pp. 698–709. ESEC/FSE 2015, ACM, New York, NY, USA (Aug 2015). https://doi.org/10.1145/2786805.2786817
  51. [52]Tappler, M., Aichernig, B.K., Bloem, R.: Model-based testing IoT communication via active automata learning. In: IEEE International Conference on Software Testing, Verification and Validation. pp. 276–287. IEEE Computer Society, Tokyo, Japan (Mar 2017). https://doi.org/10.1109/ICST.2017.32 P. Fiterău-Broștean, B. Jonsson, K. Sagonas, and F. Tăquist
  52. [53]Vaandrager, F., Bloem, R., Ebrahimi, M.: Learning Mealy machines with one timer. In: Leporati, A., Martín-Vide, C., Shapira, D., Zandron, C. (eds.) Language and Automata Theory and Applications. LNCS, vol. 12638, pp. 157–170. Springer International Publishing, Cham (Mar 2021). https://doi.org/10.1007/978-3-030-68195-1_13
  53. [54]Vaandrager, F., Garhewal, B., Rot, J., Wißmann, T.: A new approach for active automata learning based on apartness. In: Fisman, D., Rosu, G. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 13243, pp. 223–243. Springer International Publishing, Cham (Apr 2022). https://doi.org/10.1007/978-3-030-99524-9_12
  54. [55]Vaandrager, F.W.: Model learning. Commun. ACM 60(2), 86–95 (Jan 2017). https://doi.org/10.1145/2967606
  55. [56]Volpato, M., Tretmans, J.: Active learning of nondeterministic systems from an ioco perspective. In: Margaria, T., Steffen, B. (eds.) Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change. LNCS, vol. 8802, pp. 220–235. Springer, Berlin, Heidelberg (Oct 2014). https://doi.org/10.1007/978-3-662-45234-9_16
  56. [57]Walkinshaw, N., Bogdanov, K., Derrick, J., París, J.: Increasing functional coverage by inductive testing: A case study. In: Testing Software and Systems - 22nd IFIP WG 6.1 International Conference, ICTSS 2010. LNCS, vol. 6435, pp. 126–141. Springer, Berlin, Heidelberg (Nov 2010). https://doi.org/10.1007/978-3-642-16573-3_10

Paper details

vlnc:W_hq9rs222
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents