ExplainFuzz: Explainable and Constraint-Conditioned Test Generation with Probabilistic Circuits

Annaëlle Baiget; Jaron Maene; Seongmin Lee; Benjie Wang; Guy Van den Broeck; Miryung Kim

cs.SEApr 8, 2026

ExplainFuzz: Explainable and Constraint-Conditioned Test Generation with Probabilistic Circuits

Authors: Annaëlle Baiget, Jaron Maene, Seongmin Lee, Benjie Wang, Guy Van den Broeck, Miryung Kim

Organizations: UCLA, USA · KU Leuven, Belgium

Abstract

Understanding and explaining the structure of generated test inputs is essential for effective software testing and debugging. Existing approaches--including grammar-based fuzzers, probabilistic Context-Free Grammars (pCFGs), and Large Language Models (LLMs)--suffer from critical limitations. They frequently produce ill-formed inputs that fail to reflect realistic data distributions, struggle to capture context-sensitive probabilistic dependencies, and lack explainability. We introduce ExplainFuzz, a test generation framework that leverages Probabilistic Circuits (PCs) to learn and query structured distributions over grammar-based test inputs interpretably and controllably. Starting from a Context-Free Grammar (CFG), ExplainFuzz compiles a grammar-aware PC and trains it on existing inputs. New inputs are then generated via sampling. ExplainFuzz utilizes the conditioning capability of PCs to incorporate test-specific constraints (e.g., a query must have GROUP BY), enabling constrained probabilistic sampling to generate inputs satisfying grammar and user-provided constraints. Our results show that ExplainFuzz improves the coherence and realism of generated inputs, achieving significant perplexity reduction compared to pCFGs, grammar-unaware PCs, and LLMs. By leveraging its native conditioning capability, ExplainFuzz significantly enhances the diversity of inputs that satisfy a user-provided constraint. Compared to grammar-aware mutational fuzzing, ExplainFuzz increases bug-triggering rates from 35% to 63% in SQL and from 10% to 100% in XML. These results demonstrate the power of a learned input distribution over mutational fuzzing, which is often limited to exploring the local neighborhood of seed inputs. These capabilities highlight the potential of PCs to serve as a foundation for grammar-aware, controllable test generation that captures context-sensitive, probabilistic dependencies.

Figures & tables

Panel of Figure 1 — Figure 1. JSON and XML grammar excerpts (left) with context-sensitive generation graphs (right). Fixed weights illustrate pCFG probabilities; red arrows indicate context-sensitive probabilistic dependencies among inputs.

Figure 2. ExplainFuzz : grammar-aware probabilistic circuit compilation, training, and sampling

Panel of Figure 3 — Figure 3. ANTLR-style EBNF grammar of simple arithmetic expressions, a refactored BNF-style grammar, and the corresponding PC (sequence length 5) built from the BNF grammar. Observe that $\theta_{2}$ and $\theta_{3}$ would be the same value in a PCFG, while they may differ in the PC.

Query type	Form	Example / interpretation
EVI (Evidence)	Probability of a specific input.	Probability assigned to this exact anonymized input: $\qquad P(\text{``SELECT ID FROM ID ORDER BY ID ;''})$
MAR (Marginal)	(i) Token marginal: probability of token $t$ appearing in an input.	Probability that the input contains at least one JOIN : $P(\text{``JOIN''})$
	(ii) Span marginal: probability of a contiguous sequence at position $p$ .	Probability that GROUP BY ID starts at position 6: $\qquad P([\text{``GROUP'', ``BY'', ``ID''}],\,\text{position}=6)$
COND (Conditional)	(i) Token conditional: probability of token $t_{2}$ given token $t_{1}$ .	Probability of HAVING given GROUP : $P(\text{``HAVING''}\mid\text{``GROUP''})$
	(ii) Next-token conditional at position $p$ .	Probability that BY follows GROUP at position 8: $\qquad P([\text{``GROUP'', ``BY''}]\mid(\text{``GROUP''},\,\text{position}=8))$
	(iii) Following-token conditional after a given span at position $p$ .	Probability that GROUP appears after JOIN ID ON at position 12: $\qquad P(\text{``GROUP''}\mid([\text{``JOIN'', ``ID'', ``ON''}],\,\text{position}=12))$

Table 1. Examples of the four query classes supported by ExplainFuzz .

Domain	Form	Conversion
SQL	PC sample	SELECT ID COMMA ID FROM ID WHERE ID EQUAL Integral ORDER BY ID ASC SEMI EOF
SQL	Concretized	SELECT salary, performance_score FROM employees WHERE salary = 80000 ORDER BY performance_score ASC ;
XML	PC sample	OPEN Name Name EQUALS STRING Name EQUALS STRING SLASH_CLOSE EOF
XML	Concretized	<file path="auth_service_xml/data/resources.api.txt" name="api"/>

Table 2. Example concretization of anonymized tokens to concrete string.

Domain	Max	LLM	pCFG	PC-HMM	Grammar-aware PC
Domain	length	LLM	pCFG	PC-HMM	( ExplainFuzz )
B	40	7.19	2.43	1.53	1.51
CSV	45	2.83	1.46	1.20	1.15
HTML	50	9.03	1.31	1.26	1.20
JANUS	30	15.05	2.53	1.56	1.61
JSON	50	6.37	1.88	1.37	1.32

Figure 4. Perplexity comparison between grammar-aware PC, probabilistic CFG, grammar-unaware PC (PC-HMM), and LLM across domains.

Table 3. (left) Characteristics of the four seed sets used in our evaluation for the SQL domain. (right) Marginal probability of key SQL constructs across four subdomains; the last row, ‘nested select‘, is computed as

P(\text{"SELECT"})\cdot P(\text{"SELECT"}\mid\text{"SELECT"})

Table 4. (left) Characteristics of the XML seed sets used in our evaluation. (right) Marginal probability of key XML constructs across four subdomains.

Panel of Figure 5 — Figure 5. Effect of conditioning on ExplainFuzz for the XML1 seed set. The heatmap (left) shows per-bug distinct triggers, while the table (right) summarizes alignment, coverage, and diversity improvements.

	Bug Coverage (%)			Diversity
Seed	ExplainFuzz	EF+Cond	$\Delta_{\text{Cov}}$	$\Delta_{\text{Div}}$
SQL1	17.6%	33.3%	+15.7%	–3.46
SQL2	43.1%	86.7%	+43.6%	+45.25
SQL3	47.1%	66.7%	+19.6%	+19.85
SQL4	51.0%	66.7%	+15.7%	+22.67
Global	39.7 %	63.3 %	+23.6 %	+21.08

Table 5. Global summary of conditioning evaluation for XML and SQL domain.

\Delta_{\text{Cov}}

shows bug coverage improvement from conditioning;

\Delta_{\text{Div}}

shows the increase in distinct bug-triggering inputs (out of 10,000) due to conditioning.

Seeds (Description)	Model	Executable rate (%)	Bug coverage (%)	Total triggers	Distinct triggering inputs	Explicit sensitivity (%)
SQL1 (Homogeneous structure)	Grammarinator	45.1	20.0	132.0	27.0	0.0
SQL1 (Homogeneous structure)	ExplainFuzz	73.2	20.0	1060.0	1057.0	78.6
SQL2 (Homogeneous column)	Grammarinator	43.1	53.3	80.3	30.3	0.0
SQL2 (Homogeneous column)	ExplainFuzz	50.0	48.9	426.3	309.7	65.0
SQL3 (Small set + diverse)	Grammarinator	40.0	40.0	123.7	10.0	0.0
SQL3 (Small set + diverse)	ExplainFuzz	43.4	53.3	212.7	168.7	62.5

Table 6. Multi-bug evaluation per seed set: Grammarinator vs ExplainFuzz

Panel of Figure 6 — Figure 6. Bug trigger summary across seeds and models; the x-axis shows bug IDs, the y-axis lists seed sets and models, color intensity denotes the number of distinct inputs triggering each bug, and the rightmost columns report the global success ratio per bug.

SQL, BUG02_ order_ salary_ ssn
Grammarinator	SELECT * FROM employees WHERE department_id = 5 ORDER BY hire_date DESC;
ExplainFuzz (anonymized)	SELECT ID , ID FROM ID WHERE ID LT Integral ORDER BY Identifier USING GT;
ExplainFuzz (concretized)	SELECT salary , ssn_number FROM employees WHERE performance_ score < 8334 ORDER BY ssn_number USING >;

XML, BUG01_ control_ bug
Grammarinator	<request user_id="106" quota="200"> <query q="_kQw?jN)" limit="3"/> <file path="data/ temp.xml" name="tempfile" /> </request>

Table 7. Qualitative comparison of bug-triggering inputs between Grammarinator and ExplainFuzz .

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Column	Type	Nullable
id	integer	no
employee_name	text	no
hire_date	date	no
salary	numeric	yes
full_time	boolean	yes
performance_score	integer	yes

Appendix

Table 14

Column	Type	Nullable
proj_number	integer	no
project_name	text	no
start_date	date	yes
end_date	date	yes
budget	numeric	yes
dep_id	integer	yes

Appendix

Table 15

Column	Type	Nullable
dep_number	integer	no
department_name	text	no
location	text	yes
dep_budget	numeric	yes

Appendix

Table 16

Figure 7. Layout of the XML project used as a testbed

Bug ID	Static Trigger	Dynamic Trigger	Motivation
BUG01_control _bug	incorrect_start _query	—	Detect if an xpath inside a query element doesn’t start with ’/’; serves as a reachability baseline.
BUG02_numeric _overflow_bug	numeric_overflow _candidate	—	Detect numeric overflows causing logic errors or potential DoS.
BUG03_read _system_file	—	system_file_read	Identify dynamic reads that expose sensitive files via XXE or path traversal.
BUG04_read _sensitive_local _files	—	local_repo_file _read	Detect reads of local sensitive files, indicating possible information leakage.
BUG05_xpath _injection_observed	xpath_injection _candidate	xpath_query _executed	Execution of untrusted XPath queries shows potential data access or auth bypass.
BUG06_xpath _injection_error	xpath_injection _candidate	xpath_injection _error	Errors from attacker-controlled XPath indicate validation flaws and DoS vectors.

Appendix

Table 8. Bug predicates for XML fuzzing

Bug ID	Token Required	Sensitive Columns	Motivation
BUG01_order _email	ORDER, BY	email	Ordering on long text fields may expose encoding, collation, or comparator bugs.
BUG02_order _salary_ssn	ORDER, BY	salary, ssn_number	ORDER BY on mixed/large types can trigger correctness and stability bugs.
BUG03_where _salary	WHERE	salary	Type coercion in WHERE may cause incorrect filtering or planner errors.
BUG04_where_or _salary	WHERE, OR	salary	Short-circuit/NULL-handling inconsistencies can lead to wrong row selection.
BUG05_where_or _email_salary	WHERE, OR	email, salary	Compound OR on sensitive fields may trigger logic simplification bugs.
BUG06_join_email _ssn	JOIN	email, ssn_number	Join reorderings may expose protected columns or bypass filters.

Appendix

Table 9. SQL Bug Predicates

Panel of Figure 8 — Figure 8. Effect of conditioning on ExplainFuzz for the SQL-1 domain. The heatmap (top) shows per-bug distinct triggers, while the table (bottom) summarizes alignment, coverage, and diversity improvements.

Panel of Figure 9 — Figure 9. Effect of conditioning on ExplainFuzz for the SQL-3 domain. The heatmap (top) shows per-bug distinct triggers, while the table (bottom) summarizes alignment, coverage, and diversity improvements.

Panel of Figure 10 — Figure 10. Effect of conditioning on ExplainFuzz for the SQL-4 domain. The heatmap (top) shows per-bug distinct triggers, while the table (bottom) summarizes alignment, coverage, and diversity improvements.

Panel of Figure 11 — Figure 11. Effect of conditioning on ExplainFuzz for the XML-2- domain. The heatmap (top) shows per-bug distinct triggers, while the table (bottom) summarizes alignment, coverage, and diversity improvements.

Panel of Figure 12 — Figure 12. Effect of conditioning on ExplainFuzz for the XML-3 domain. The heatmap (top) shows per-bug distinct triggers, while the table (bottom) summarizes alignment, coverage, and diversity improvements.

Panel of Figure 13 — Figure 13. Effect of conditioning on ExplainFuzz for the XML-4 domain. The heatmap (top) shows per-bug distinct triggers, while the table (bottom) summarizes alignment, coverage, and diversity improvements.

Automated Test Generation

Automated test generation creates inputs, scenarios, and checks to expose software and system defects with less manual effort.

See all 132 papers

FunFuzz: An LLM-Powered Evolutionary Fuzzing Framework
May 4, 2026Mario Rodríguez Béjar, B. Romera-Paredes, Jose L. Hernández-RamosEvolutionary Optimization Software Vulnerability Detection
Universidad de Murcia Murcia, Spain · Hiverge London, England
Program Structure-aware Language Models: Targeted Software Testing beyond Textual Semantics
Apr 20, 2026Khang Tran, Khoa Nguyen, Cristian Borcea +1LLM-Based Program Synthesis Automated Test Generation
New Jersey Institute of Technology, Newark, NJ, USA
Beyond Rule-Based Mutation Testing: Test-Aware Mutant Generation Using Large Language Models
Sep 24, 2026Nils Kiele, Zainab Saad, Zirui Wang +2Automated Software Testing Mutation Testing
Department of Electrical and Software Engineering, University of Calgary, AB, Canada

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

FunFuzz: An LLM-Powered Evolutionary Fuzzing Framework

Mario Rodríguez Béjar, B. Romera-Paredes, Jose L. Hernández-Ramos

Universidad de Murcia Murcia, Spain · Hiverge London, England

Evolutionary Optimization Software Vulnerability Detection LLMs for Cybersecurity Automated Test Generation

Open paper AskPDF arXiv

Modern fuzzers increasingly use Large Language Models (LLMs) to generate structured inputs, but LLM-driven fuzzing is sensitive to prompt initialization and sampling variance, which can reduce exploration efficiency and lead to redundant inputs. We present FunFuzz, a multi-island evolutionary fuzzing framework that runs several isolated searches in parallel and periodically migrates high-value candidates to maintain diversity. FunFuzz derives initial generation prompts from documentation and initializes islands with topic-specific instructions, then continuously adapts prompts using feedback-guided selection. During fuzzing, candidates are prioritized by incremental compiler coverage, while compiler-internal failure signals are used to identify crash-inducing inputs. We evaluate FunFuzz on compiler fuzzing, where inputs are source programs and success is measured by compiler coverage and unique compiler-internal failures. Across repeated 24-hour campaigns on GCC and Clang, FunFuzz achieves higher compiler coverage than previous LLM-driven baselines and discovers more unique failure-triggering inputs.

Abstract

Automated Test Generation

Explore similar work

FunFuzz: An LLM-Powered Evolutionary Fuzzing Framework

Program Structure-aware Language Models: Targeted Software Testing beyond Textual Semantics

Beyond Rule-Based Mutation Testing: Test-Aware Mutant Generation Using Large Language Models