Error-awareness Accelerates Active Automata Learning

Loes Kruger; Sebastian Junges; Jurriaan Rot

cs.LGFeb 25, 2026

Error-awareness Accelerates Active Automata Learning

Authors: Loes Kruger, Sebastian Junges, Jurriaan Rot

Organizations: Institute for Computing and Information Sciences, Radboud University, Nijmegen, the Netherlands

Abstract

Active automata learning (AAL) algorithms can learn a behavioral model of a system from interacting with it. The primary challenge remains scaling to larger models, in particular in the presence of many possible inputs to the system. Modern AAL algorithms fail to scale even if, in every state, most inputs lead to errors. In various challenging problems from the literature, these errors are observable, i.e., they emit a known error output. Motivated by these problems, we study learning these systems more efficiently. Further, we consider various degrees of knowledge about which inputs are non-error producing at which state. For each level of knowledge, we provide a matching adaptation of the state-of-the-art AAL algorithm L# to make the most of this domain knowledge. Our empirical evaluation demonstrates that the methods accelerate learning by orders of magnitude with strong but realistic domain knowledge to a single order of magnitude with limited domain knowledge.

Figures & tables

Test suite	Sec.	Explanation	Alg.	Sec.	Explanation
$\displaystyle T_{\mathsf{e}}$	3.1	Test suite w persistent errors	$\displaystyle L_{\mathsf{e}}^{\#}$	4.1	$\displaystyle L^{\#}$ ( [ 32 ] ) w persistent errors
$\displaystyle T_{\mathtt{S}}$	3.2	Sound test suite	$\displaystyle AL^{\#}_{\mathsf{e}}$	4.2	$\displaystyle L^{\#}_{\mathsf{e}}$ + $\displaystyle AL^{\#}$ ( [ 19 ] ) w arbitrary reference
$\displaystyle\mathsf{MoE}(T_{\mathsf{e}},T_{\mathtt{S}})$	3.2	Distribution over test suites ( [ 18 ] )	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{S}}$	4.3	$\displaystyle L^{\#}_{\mathsf{e}}$ w sound reference
			$\displaystyle L^{\#}_{\mathsf{e},\mathtt{SC}}$	4.4	$\displaystyle L^{\#}_{\mathsf{e}}$ w sound and complete reference

Table 1: Overview of novel testing and learning algorithms.

Panel of Figure 1 — Figure 1: Mealy machine, DFA references and an observation tree related to a toy TLS system. Double circle states represent final states. Omitted DFA transitions lead to the (non-final) sink state. The $\displaystyle+$ -symbol on transitions represents all inputs for which a transition is not explicitly drawn.

Panel of Figure 3 — Algorithm 1 $\displaystyle L^{\#}_{\mathsf{e}}$ for a sound reference.

Panel of Figure 2 — Figure 2: Number of symbols (lower is better) for Experiment 1 and 2.

Algorithm $\displaystyle\to$	$\displaystyle AL^{\#}_{\mathsf{e}}(\mathcal{L})$	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{S}}(\mathcal{L})$	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{SC}}(\mathcal{L})$
Reference $\displaystyle\downarrow$	Incorrect(Violations)	Incorrect(Violations)	Incorrect(Violations)
$\displaystyle\mathcal{L}_{MUT}$	0	55.6(0)	100(100)
$\displaystyle\mathcal{L}_{P}$	0	87.1(0)	95.1(85.3)
$\displaystyle\mathcal{L}_{M}$	0	0	100(100)
$\displaystyle\mathcal{L}_{\mathtt{S}\mathtt{C}}$	0	0	0

Table 2: Results RQ3, values represent percentages over all seeds.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 6 — Algorithm 5 $\displaystyle L^{\#}$ with persistent $\displaystyle\mathsf{e}$ (see Section 4.1 ).

Panel of Figure 7 — Algorithm 6 $\displaystyle AL^{\#}$ with persistent $\displaystyle\mathsf{e}$ (see Section 4.2 ).

Panel of Figure 8 — Algorithm 7 $\displaystyle L^{\#}_{\mathsf{e}}$ for a sound and complete reference (see Section 4.4 ).

model	m54	m41	m199	m196	m158	m159	m76	m45	m164	m106	m34
states	27	25	27	81	28	30	210	184	43	79	115
reference states	16	24	25	38	18	19	57	47	14	65	74

Appendix

Table 3: Information on the ASML benchmark and associated references.

model	parameters	horizon	states	inputs	reference states
airportA-3	DMAX=3PMAX=3	8	61	18	13
airportA-3	DMAX=3PMAX=3	9	56	18	14
airportA-7	DMAX=3PMAX=3	8	46	18	16
airportA-7	DMAX=3PMAX=3	9	50	18	16
airportB-3	DMAX=3PMAX=3	8	70	18	14
airportB-3	DMAX=3PMAX=3	9	59	18	13

Appendix

Table 4: Information on the monitor benchmark and associated references.

model	states	inputs	reference	reference states	sound	sound & complete
GnuTLS_3.3.12_client_full	8	12	chat	8	False	False
GnuTLS_3.3.12_client_full	8	12	domain	7	True	False
GnuTLS_3.3.12_client_full	8	12	passive	7	False	False
GnuTLS_3.3.12_client_full	8	12	sound & complete	8	True	True
GnuTLS_3.3.12_server_full	9	12	chat	9	False	False
GnuTLS_3.3.12_server_full	9	12	domain	9	True	False

Appendix

Table 5: Information on the TLS benchmark and references.

model	states	inputs	reference	reference states	sound	sound & complete
GnuTLS_3.3.8_server_regular	11	8	chat	7	False	False
GnuTLS_3.3.8_server_regular	11	8	domain	6	True	False
GnuTLS_3.3.8_server_regular	11	8	passive	8	False	False
GnuTLS_3.3.8_server_regular	11	8	sound & complete	10	True	True
OpenSSL_1.0.1g_client_regular	9	7	chat	7	False	False
OpenSSL_1.0.1g_client_regular	9	7	domain	5	True	False

Appendix

Table 6: (Continued) Information on the TLS benchmark and references.

Model	States	Inputs	Algorithm	Learned	Learned States	Learn Symbols	Conformance Symbols	Total Symbols	Total Symbols Median	Total Symbols Std
m54	27	10	$\displaystyle L^{\#}$	100.0%	27	7018	135744	142762	127074	74596
m54	27	10	$\displaystyle L^{\#}_{\mathsf{e}}$	100.0%	27	1575	11235	12810	12204	2762
m54	27	10	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{SC}}$	100.0%	27	329	0	329	329	0
m41	25	47	$\displaystyle L^{\#}$	46.7%	24	47049	799740	846789	1000000	213277
m41	25	47	$\displaystyle L^{\#}_{\mathsf{e}}$	100.0%	25	5819	24487	30306	22943	19536
m41	25	47	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{SC}}$	100.0%	25	423	0	423	423	0

Appendix

Table 7: Results Experiment 1 for the ASML benchmark. The last two columns show the median and standard deviation for the total number of symbols.

Name	Horizon	Parameters	States	Inputs	Algorithm	Learned	Learned States	Learn Symbols	Conformance Symbols	Total Symbols	Total Symbols Median	Total Symbols Std
airportA-7	8	(’DMAX=3’, ’PMAX=3’)	46	18	$\displaystyle L^{\#}$	0.0%	29	33140	966866	1000006	1000007	4
airportA-7	8	(’DMAX=3’, ’PMAX=3’)	46	18	$\displaystyle L^{\#}_{\mathsf{e}}$	100.0%	46	5384	59066	64450	59911	18270
airportA-7	8	(’DMAX=3’, ’PMAX=3’)	46	18	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{SC}}$	100.0%	46	1404	6530	7934	7571	4846
airportB-7	8	(’DMAX=3’, ’PMAX=3’)	46	18	$\displaystyle L^{\#}$	0.0%	29	34165	965840	1000005	1000005	5
airportB-7	8	(’DMAX=3’, ’PMAX=3’)	46	18	$\displaystyle L^{\#}_{\mathsf{e}}$	100.0%	46	7072	85688	92760	88113	27382
airportB-7	8	(’DMAX=3’, ’PMAX=3’)	46	18	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{SC}}$	100.0%	46	1478	7700	9178	8409	3799

Appendix

Table 8: Results Experiment 1 for the monitor benchmark. The last two columns show the median and standard deviation for the total number of symbols.

Model	States	Inputs	Reference	Learned	Learned States	Learn Symbols	Conformance Symbols	Total Symbols	Total Symbols Median	Total Symbols Std
OpenSSL_1.0.1j_client_regular.dot	6	7	$\displaystyle L^{\#}_{\mathsf{e}}()$	100.0%	6	295	1731	2027	833	2298
OpenSSL_1.0.1j_client_regular.dot	6	7	$\displaystyle AL^{\#}_{\mathsf{e}}(\mathcal{L}_{P})$	100.0%	6	229	0	229	227	5
OpenSSL_1.0.1j_client_regular.dot	6	7	$\displaystyle AL^{\#}_{\mathsf{e}}(\mathcal{L}_{GPT})$	100.0%	6	215	174	390	373	71
OpenSSL_1.0.1j_client_regular.dot	6	7	$\displaystyle AL^{\#}_{\mathsf{e}}(\mathcal{L}_{M})$	100.0%	6	191	204	395	381	83
OpenSSL_1.0.1j_client_regular.dot	6	7	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{S}}(\mathcal{L}_{M})$	100.0%	6	140	85	225	223	29
OpenSSL_1.0.1j_client_regular.dot	6	7	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{SC}}(\mathcal{L}_{\mathtt{S}\mathtt{C}})$	100.0%	6	41	0	41	41	0

Appendix

Table 9: Results Experiment 2 for the TLS benchmark. The last two columns show the median and standard deviation for the total number of symbols.

Model	States	Algorithm	Reference Type	Correct (%)	Incorrect (%)	Learned States	Learn Symbols	Conformance Symbols	Total Symbols	Total Symbols Median	Total Symbols Std
GnuTLS_3.3.8_client_regular.dot	6	$\displaystyle AL^{\#}_{\mathsf{e}}$	$\displaystyle\mathcal{L}_{MUT}$	100	0	6	255	371	627	598	176
GnuTLS_3.3.8_client_regular.dot	6	$\displaystyle AL^{\#}_{\mathsf{e}}$	$\displaystyle\mathcal{L}_{P}$	100	0	6	282	197	479	435	144
GnuTLS_3.3.8_client_regular.dot	6	$\displaystyle AL^{\#}_{\mathsf{e}}$	$\displaystyle\mathcal{L}_{M}$	100	0	6	269	283	552	515	130
GnuTLS_3.3.8_client_regular.dot	6	$\displaystyle AL^{\#}_{\mathsf{e}}$	$\displaystyle\mathcal{L}_{\mathtt{S}\mathtt{C}}$	100	0	6	305	0	305	302	10
GnuTLS_3.3.8_client_regular.dot	6	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{S}}$	$\displaystyle\mathcal{L}_{MUT}$	100	0	6	123	30	153	147	24
GnuTLS_3.3.8_client_regular.dot	6	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{S}}$	$\displaystyle\mathcal{L}_{P}$	0	100	8	175	33	208	206	23

Appendix

Table 10: Results Experiment 3 for the TLS benchmark. The last two columns show the median and standard deviation for the total number of symbols.

Model	States	Algorithm	Reference Type	Correct (%)	Incorrect (%)	Learned States	Learn Symbols	Conformance Symbols	Total Symbols	Total Symbols Median	Total Symbols Std
GnuTLS_3.3.12_client_full.dot	8	$\displaystyle AL^{\#}_{\mathsf{e}}$	$\displaystyle\mathcal{L}_{MUT}$	100	0	8	470	83	553	532	63
GnuTLS_3.3.12_client_full.dot	8	$\displaystyle AL^{\#}_{\mathsf{e}}$	$\displaystyle\mathcal{L}_{P}$	100	0	8	424	329	753	730	157
GnuTLS_3.3.12_client_full.dot	8	$\displaystyle AL^{\#}_{\mathsf{e}}$	$\displaystyle\mathcal{L}_{M}$	100	0	8	366	667	1033	1014	266
GnuTLS_3.3.12_client_full.dot	8	$\displaystyle AL^{\#}_{\mathsf{e}}$	$\displaystyle\mathcal{L}_{\mathtt{S}\mathtt{C}}$	100	0	8	460	0	460	462	17
GnuTLS_3.3.12_client_full.dot	8	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{S}}$	$\displaystyle\mathcal{L}_{MUT}$	100	0	8	100	66	166	154	56
GnuTLS_3.3.12_client_full.dot	8	$\displaystyle L^{\#}_{\mathsf{e},\mathtt{S}}$	$\displaystyle\mathcal{L}_{P}$	0	100	6	58	0	58	58	0

Appendix

Table 11: (Continuation) Results Experiment 3 for the TLS benchmark. The last two columns show the median and standard deviation for the total number of symbols.

Automata Learning

See all 15 papers

SMT-Based Active Learning of Weighted Automata
May 8, 2026Tiago Ferreira, Kevin Batz, Alexandra SilvaActive Learning Satisfiability Modulo Theories
University College London, London, UK · Cornell University, Ithaca, NY, USA
Warm Starting State-Space Models with Automata Learning
Mar 5, 2026William Fishell, Sam Nicholas Kouteili, Mark SantolucitoAutomata Learning State Space Models
Columbia University · Yale University · Barnard College, Columbia University
Learning Canonical Register Automata over Ordered Data Domains
Aug 19, 2026Yong Li, Qiyi Tang, Di-De YenAutomata Learning Active Learning
Key Laboratory of System Software (Chinese Academy of Sciences), Beijing, China · Institute of Software, Chinese Academy of Sciences, Beijing, China · School of Computer Science and Informatics, University of Liverpool, UK

May 8, 2026J/K move · Enter open · S save

SMT-Based Active Learning of Weighted Automata

Tiago Ferreira, Kevin Batz, Alexandra Silva

University College London, London, UK · Cornell University, Ithaca, NY, USA

Active Learning Satisfiability Modulo Theories Automata Learning

Open paper AskPDF arXiv

We present an SMT-based active learning algorithm for nondeterministic weighted automata (WFAs) as a practical and robust alternative to Hankel/L*-style methods. Our algorithm is parametric in a given semiring and, if it terminates, guaranteed to produce minimal WFAs. We prove partial correctness and provide a sufficient termination condition, which in particular implies termination for all finite semirings. Our extensive experimental evaluation shows that our algorithm is capable of learning numerous minimal WFAs over both finite and infinite semirings, vastly outperforms a naive baseline, and is competitive with a state-of-the-art algorithm while producing significantly smaller automata and requiring less interaction with the teacher.

Abstract

Automata Learning

Explore similar work

SMT-Based Active Learning of Weighted Automata

Warm Starting State-Space Models with Automata Learning

Learning Canonical Register Automata over Ordered Data Domains