{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T07:01:27Z","timestamp":1779087687563,"version":"3.51.4"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031711619","type":"print"},{"value":"9783031711626","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T00:00:00Z","timestamp":1726012800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T00:00:00Z","timestamp":1726012800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Active automata learning (AAL) is a method to infer state machines by interacting with black-box systems. Adaptive AAL aims to reduce the sample complexity of AAL by incorporating domain specific knowledge in the form of (similar) reference models. Such reference models appear naturally when learning multiple versions or variants of a software system. In this paper, we present state matching, which allows flexible use of the structure of these reference models by the learner. State matching is the main ingredient of adaptive <jats:inline-formula><jats:alternatives><jats:tex-math>$$L^{\\#}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>L<\/mml:mi>\n                    <mml:mo>#<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, a novel framework for adaptive learning, built on top of <jats:inline-formula><jats:alternatives><jats:tex-math>$$L^{\\#}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>L<\/mml:mi>\n                    <mml:mo>#<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our empirical evaluation shows that adaptive <jats:inline-formula><jats:alternatives><jats:tex-math>$$L^{\\#}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>L<\/mml:mi>\n                    <mml:mo>#<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> improves the state of the art by up to two orders of magnitude.<\/jats:p>","DOI":"10.1007\/978-3-031-71162-6_14","type":"book-chapter","created":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T02:02:27Z","timestamp":1725933747000},"page":"267-284","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["State Matching and\u00a0Multiple References in\u00a0Adaptive Active Automata Learning"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-3275-6806","authenticated-orcid":false,"given":"Loes","family":"Kruger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0978-8466","authenticated-orcid":false,"given":"Sebastian","family":"Junges","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1404-6232","authenticated-orcid":false,"given":"Jurriaan","family":"Rot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,11]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Aichernig, B.K., Muskardin, E., Pferscher, A.: Active vs. passive: a comparison of automata learning paradigms for network protocols. In: FMAS\/ASYDE@SEFM. EPTCS, vol.\u00a0371, pp. 1\u201319 (2022)","DOI":"10.4204\/EPTCS.371.1"},{"issue":"2","key":"14_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87\u2013106 (1987)","journal-title":"Inf. Comput."},{"issue":"6","key":"14_CR3","doi-asserted-by":"publisher","first-page":"1519","DOI":"10.1007\/s10270-020-00809-2","volume":"19","author":"K Aslam","year":"2020","unstructured":"Aslam, K., Cleophas, L., Schiffelers, R.R.H., van den Brand, M.: Interface protocol inference to aid understanding legacy software components. Softw. Syst. Model. 19(6), 1519\u20131540 (2020)","journal-title":"Softw. Syst. Model."},{"key":"14_CR4","doi-asserted-by":"publisher","unstructured":"Bainczyk, A., Steffen, B., Howar, F.: Lifelong learning of reactive systems in practice. In: Ahrendt, W., Beckert, B., Bubel, R., Johnsen, E.B. (eds.) The Logic of Software. A Tasting Menu of Formal Methods. LNCS, vol. 13360, pp. 38\u201353. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-08166-8_3","DOI":"10.1007\/978-3-031-08166-8_3"},{"issue":"3","key":"14_CR5","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s10703-008-0053-x","volume":"32","author":"S Chaki","year":"2008","unstructured":"Chaki, S., Clarke, E.M., Sharygina, N., Sinha, N.: Verification of evolving software via component substitutability analysis. Formal Methods Syst. Des. 32(3), 235\u2013266 (2008)","journal-title":"Formal Methods Syst. Des."},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-030-34968-4_8","volume-title":"Integrated Formal Methods","author":"CDN Damasceno","year":"2019","unstructured":"Damasceno, C.D.N., Mousavi, M.R., da Silva Simao, A.: Learning to reuse: adaptive model learning for evolving systems. In: Ahrendt, W., Tapia Tarifa, S.L. (eds.) IFM 2019. LNCS, vol. 11918, pp. 138\u2013156. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-34968-4_8"},{"key":"14_CR7","doi-asserted-by":"publisher","unstructured":"Ferreira, T., van Heerdt, G., Silva, A.: Tree-based adaptive model learning. 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. 164\u2013179. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15629-8_10","DOI":"10.1007\/978-3-031-15629-8_10"},{"issue":"5","key":"14_CR8","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1093\/jigpal\/jzl007","volume":"14","author":"A Groce","year":"2006","unstructured":"Groce, A., Peled, D.A., Yannakakis, M.: Adaptive model checking. Log. J. IGPL 14(5), 729\u2013744 (2006)","journal-title":"Log. J. IGPL"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/978-3-319-96562-8_5","volume-title":"Machine Learning for Dynamic Software Analysis: Potentials and Limits","author":"F Howar","year":"2018","unstructured":"Howar, F., Steffen, B.: Active automata learning in practice. In: Bennaceur, A., H\u00e4hnle, R., Meinke, K. (eds.) Machine Learning for Dynamic Software Analysis: Potentials and Limits. LNCS, vol. 11026, pp. 123\u2013148. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96562-8_5"},{"key":"14_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-030-00244-2_11","volume-title":"Formal Methods for Industrial Critical Systems","author":"D Huistra","year":"2018","unstructured":"Huistra, D., Meijer, J., van de Pol, J.: Adaptive learning for learn-based regression testing. In: Howar, F., Barnat, J. (eds.) FMICS 2018. LNCS, vol. 11119, pp. 162\u2013177. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-00244-2_11"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-319-11164-3_26","volume-title":"Runtime Verification","author":"M Isberner","year":"2014","unstructured":"Isberner, M., Howar, F., Steffen, B.: The TTT algorithm: a redundancy-free approach to active automata learning. In: Bonakdarpour, B., Smolka, S.A. (eds.) RV 2014. LNCS, vol. 8734, pp. 307\u2013322. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11164-3_26"},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-319-21690-4_32","volume-title":"Computer Aided Verification","author":"M Isberner","year":"2015","unstructured":"Isberner, M., Howar, F., Steffen, B.: The open-source LearnLib \u2013 a framework for active automata learning. In: Kroening, D., P\u0103s\u0103reanu, C.S. (eds.) CAV 2015. LNCS, vol. 9206, pp. 487\u2013495. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21690-4_32"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press (1994). https:\/\/mitpress.mit.edu\/books\/introduction-computational-learning-theory","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"14_CR14","unstructured":"Kruger, L., Junges, S., Rot, J.: State matching and multiple references in adaptive active automata learning (2024). https:\/\/arxiv.org\/abs\/2406.19714"},{"key":"14_CR15","doi-asserted-by":"publisher","unstructured":"Kruger, L., Junges, S., Rot, J.: State matching and multiple references in adaptive active automata learning: supplementary material (2024). https:\/\/doi.org\/10.5281\/zenodo.12517574","DOI":"10.5281\/zenodo.12517574"},{"key":"14_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-030-88885-5_5","volume-title":"Automated Technology for Verification and Analysis","author":"E Mu\u0161kardin","year":"2021","unstructured":"Mu\u0161kardin, E., Aichernig, B.K., Pill, I., Pferscher, A., Tappler, M.: AALpy: an active automata learning library. In: Hou, Z., Ganesh, V. (eds.) ATVA 2021. LNCS, vol. 12971, pp. 67\u201373. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-88885-5_5"},{"key":"14_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/978-3-030-22348-9_23","volume-title":"Models, Mindsets, Meta: The What, the How, and the Why Not?","author":"D Neider","year":"2019","unstructured":"Neider, D., Smetsers, R., Vaandrager, F., Kuppens, H.: Benchmarks for automata learning and conformance testing. In: Margaria, T., Graf, S., Larsen, K.G. (eds.) Models, Mindsets, Meta: The What, the How, and the Why Not? LNCS, vol. 11200, pp. 390\u2013416. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-22348-9_23"},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-319-47560-8_11","volume-title":"Secure IT Systems","author":"J Ruiter","year":"2016","unstructured":"Ruiter, J.: A tale of the OpenSSL state machine: a large-scale black-box analysis. In: Brumley, B.B., R\u00f6ning, J. (eds.) NordSec 2016. LNCS, vol. 10014, pp. 169\u2013184. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-47560-8_11"},{"key":"14_CR19","unstructured":"de\u00a0Ruiter, J., Poll, E.: Protocol state fuzzing of TLS implementations. In: USENIX Security Symposium, pp. 193\u2013206. USENIX Association (2015)"},{"key":"14_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-319-33693-0_20","volume-title":"Integrated Formal Methods","author":"M Schuts","year":"2016","unstructured":"Schuts, M., Hooman, J., Vaandrager, F.: Refactoring of legacy software using model learning and equivalence checking: an industrial experience report. In: \u00c1brah\u00e1m, E., Huisman, M. (eds.) IFM 2016. LNCS, vol. 9681, pp. 311\u2013325. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-33693-0_20"},{"key":"14_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-319-30000-9_14","volume-title":"Language and Automata Theory and Applications","author":"R Smetsers","year":"2016","unstructured":"Smetsers, R., Moerman, J., Jansen, D.N.: Minimal separating sequences for all pairs of states. In: Dediu, A.-H., Janou\u0161ek, J., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2016. LNCS, vol. 9618, pp. 181\u2013193. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-30000-9_14"},{"key":"14_CR22","unstructured":"Tappler, M., Aichernig, B.K., Bloem, R.: Model-based testing IoT communication via active automata learning. CoRR abs\/1904.07075 (2019)"},{"issue":"2","key":"14_CR23","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/2967606","volume":"60","author":"FW Vaandrager","year":"2017","unstructured":"Vaandrager, F.W.: Model learning. Commun. ACM 60(2), 86\u201395 (2017)","journal-title":"Commun. ACM"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-3-030-99524-9_12","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"F Vaandrager","year":"2022","unstructured":"Vaandrager, F., Garhewal, B., Rot, J., Wi\u00dfmann, T.: A new approach for active automata learning based on apartness. In: TACAS 2022. LNCS, vol. 13243, pp. 223\u2013243. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-99524-9_12"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Windm\u00fcller, S., Neubauer, J., Steffen, B., Howar, F., Bauer, O.: Active continuous quality control. In: CBSE, pp. 111\u2013120. ACM (2013)","DOI":"10.1145\/2465449.2465469"},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"Yang, N., et al.: Improving model inference in industry by combining active and passive learning. In: SANER, pp. 253\u2013263. IEEE (2019)","DOI":"10.1109\/SANER.2019.8668007"}],"container-title":["Lecture Notes in Computer Science","Formal Methods"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-71162-6_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T02:04:56Z","timestamp":1725933896000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-71162-6_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,11]]},"ISBN":["9783031711619","9783031711626"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-71162-6_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,11]]},"assertion":[{"value":"11 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Formal Methods","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Milan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fm2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.fm24.polimi.it\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}