🤖 machine learning

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

ExplainFuzz is a novel test generation framework that leverages Probabilistic Circuits to learn structured, interpretable distributions from context-free grammars, enabling the generation of realistic, constraint-satisfying inputs that significantly outperform existing grammar-based, probabilistic, and LLM-driven approaches in terms of coherence, diversity, and bug-triggering rates.

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

Published 2026-04-09

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a quality control inspector for a massive, complex factory that builds software. Your job is to throw "test inputs" (like strange sentences, weird code, or odd data files) at the software to see if it breaks. If the software crashes or behaves strangely, you've found a bug!

The problem is: How do you throw the right kind of rocks at the machine?

The Old Ways: Throwing Rocks Blindly

The "Grammar Robot" (Grammar-based Fuzzers):
Imagine a robot that knows the rules of grammar (like "a sentence needs a subject and a verb"). It can build a sentence that is grammatically correct, like "The cat sat on the mat."
- The Flaw: It doesn't understand context. It might generate: "The cat sat on the moon." Grammatically correct, but weird and unrealistic. It also can't easily be told, "Hey, I specifically want a sentence about a dog," without starting over. It just mutates what it already knows.
The "Magic Black Box" (Large Language Models/LLMs):
Imagine a super-smart wizard who has read every book in the world. You ask for a test sentence, and it gives you a perfect one.
- The Flaw: It's a black box. You don't know why it chose those words. If you ask, "Why did you include a dragon?" it might just say, "Because it felt right." Also, it's slow and expensive to run millions of times. It's like hiring a wizard to throw pebbles at a wall; it works, but it's overkill and you can't control the outcome precisely.
The "Simple Statistician" (Probabilistic CFGs):
Imagine a robot that knows the rules and also knows that "The" is usually followed by a noun.
- The Flaw: It assumes every choice is independent. It doesn't know that if you use the word "Group," you are very likely to also use the word "By" later in the sentence. It misses the subtle connections between different parts of the input.

The New Solution: ExplainFuzz (The "Smart Architect")

The paper introduces ExplainFuzz. Think of this as a Smart Architect who builds test inputs.

Here is how it works, using a simple analogy:

1. Learning the Blueprint (The Probabilistic Circuit)

Instead of just memorizing rules, the Architect studies thousands of real-world examples (like real SQL queries or XML files). It builds a massive, transparent 3D map (called a Probabilistic Circuit) of how these inputs are actually structured.

The Magic: This map doesn't just say "A is followed by B." It understands complex relationships. It knows: "If I see a 'Group' clause, there is a 90% chance a 'By' clause will appear later, and a 10% chance it won't." It captures the context that the other methods miss.

2. The "Why" Button (Explainability)

Unlike the Magic Wizard, this Architect is transparent. You can ask it questions:

"What is the probability that a random input will contain the word 'JOIN'?"
"Given that I have a 'SELECT' statement, what is the most likely next word?"
You can look at the map and see exactly how the probabilities are calculated. It's not a black box; it's a glass box.

3. The "Constraint" Dial (Conditioned Generation)

This is the superpower. You can tell the Architect: "I want to build a test case, but it MUST include a 'GROUP BY' clause."

The Architect looks at its 3D map, finds the path where "GROUP BY" exists, and generates a perfect, realistic input that satisfies that rule.
It doesn't just guess; it mathematically guarantees the input fits the rules and your specific constraint.

Why Does This Matter? (The Results)

The paper tested this on two complex languages: SQL (database queries) and XML (data files).

Realism: The inputs generated by ExplainFuzz sounded much more like real human data than the "Grammar Robot" or the "Simple Statistician." They were less likely to be nonsense.
Finding Bugs: When they threw these inputs at software to find bugs:
- The old "Grammar Robot" (Grammarinator) found bugs in 35% of SQL cases and 10% of XML cases.
- ExplainFuzz found bugs in 63% of SQL cases and 100% of XML cases!
Diversity: It didn't just find the same bugs over and over. It found many more unique ways to break the software because it understood the deep, hidden connections in the data.

The Bottom Line

ExplainFuzz is like upgrading from a blindfolded rock-thrower to a guided missile system with a clear view of the target.

It learns the deep, hidden patterns of how data is actually built. It lets you ask "Why?" and "What if?" and then generates perfect, realistic test cases that are specifically designed to stress-test software in ways humans might not think of. It's faster, smarter, and much more effective at finding the hidden cracks in software.

1. Problem Statement

Effective software testing, particularly for compilers and databases, requires generating high-quality, structured test inputs that are syntactically valid and semantically realistic. Existing approaches suffer from critical trade-offs:

Grammar-based Fuzzers (e.g., Grammarinator): Generate syntactically valid inputs via mutation but lack control over input distributions. They often produce unnatural or ill-formed inputs because they rely on local seed mutations and fail to capture context-sensitive probabilistic dependencies (e.g., the likelihood of a HAVING clause depends on the presence of GROUP BY).
Probabilistic Context-Free Grammars (pCFGs): Extend grammars with rule probabilities but assume independence between production rules. They cannot model long-range or context-sensitive dependencies.
Large Language Models (LLMs): Can generate realistic text but act as "black boxes" lacking transparent control mechanisms. They are computationally expensive for high-volume fuzzing and struggle with tokenized, domain-specific inputs.
Grammar-Unaware Probabilistic Models: Offer expressivity but cannot guarantee syntactic validity, rendering them ineffective for testing parsers or compilers.

Core Gap: There is a lack of a test generation framework that is simultaneously grammar-aware, capable of capturing context-sensitive dependencies, explainable, and controllable via user constraints.

2. Methodology: ExplainFuzz

ExplainFuzz leverages Probabilistic Circuits (PCs) to learn and query structured distributions over grammar-based test inputs. The workflow consists of four stages:

A. Preprocessing & Refactoring

Grammar Refactoring: Input ANTLR grammars are parsed and refactored. Inlined literals are replaced with named tokens to create an explicit symbolic alphabet.
Seed Amplification & Anonymization: Existing seed inputs are amplified using Grammarinator. Concrete lexemes (e.g., specific table names, numbers) are anonymized into tokens (e.g., ID, Numeric) to create a training corpus of symbolic sequences.

B. PC Compilation (Grammar-Aware Construction)

The system compiles the Context-Free Grammar (CFG) into a grammar-aware Probabilistic Circuit.
Algorithm: Similar to the CYK parsing algorithm, the construction is bottom-up. It creates a computational graph where:
- Sum Nodes represent mixtures of alternatives (production rules).
- Product Nodes represent independent substructures (concatenation of symbols).
- Leaf Nodes represent base distributions (terminal tokens).
The circuit models every possible input sequence up to a maximum length $n$ , ensuring that any generated sample is syntactically valid by construction.

C. Training

The compiled PC is trained on the anonymized seed corpus using standard learning algorithms (e.g., Expectation-Maximization or gradient-based methods) to learn the probabilities of transitions and rule selections.
This allows the model to capture context-sensitive dependencies (e.g., how the presence of a JOIN influences the probability of a WHERE clause) that pCFGs miss.

D. Inference and Generation

Explainability (Inference): Users can perform tractable probabilistic queries on the trained PC, such as:
- Marginal: "What is the probability of a JOIN appearing?"
- Conditional: "What is the probability of HAVING given GROUP BY?"
- MAP: "What is the most likely token following SELECT?"
Constraint-Conditioned Generation: Users can specify constraints (e.g., "Must contain GROUP BY"). The PC performs conditioned sampling to generate inputs that satisfy both the grammar and the user constraints.
Concretization: The generated token sequences are mapped back to concrete, executable values (e.g., valid SQL column names, file paths) using domain-specific concretizers.

3. Key Contributions

Explainable and Controllable Framework: Unlike black-box LLMs or seed-dependent mutational fuzzers, ExplainFuzz provides an interpretable view of the input space and allows systematic steering of generation via constraint conditioning.
Superior Coherence and Realism: By capturing context-sensitive dependencies, ExplainFuzz generates inputs with significantly lower perplexity than pCFGs, grammar-unaware PCs, and LLMs.
Targeted Generation via Conditioning: The framework can systematically steer generation toward specific structures (e.g., rare bug-triggering patterns) while maintaining global diversity and semantic coherence.
Enhanced Bug-Finding Effectiveness: Demonstrated significant improvements in bug coverage and the diversity of bug-triggering inputs compared to state-of-the-art grammar-based mutational fuzzers.

4. Experimental Results

The authors evaluated ExplainFuzz across seven domains (SQL, JANUS, REDIS, B, CSV, HTML, JSON) with a deep dive into SQL and XML.

RQ1: Coherence and Realism

Metric: Perplexity (lower is better).
Result: ExplainFuzz achieved the lowest perplexity in 5 out of 7 domains compared to pCFGs, PC-HMMs (grammar-unaware), and LLMs.
Insight: It successfully models implicit, context-sensitive dependencies that pCFGs (which assume independence) and LLMs (which struggle with tokenized domain data) fail to capture.

RQ2: Impact of Targeted Sampling (Conditioning)

Setup: Generated 10,000 inputs with specific token constraints (e.g., forcing CDATA in XML).
Results:
- SQL: Bug coverage increased from 39.7% to 63.3% (+23.6%).
- XML: Bug coverage increased from 82.5% to 100% (+17.5%).
- Diversity: Conditioning significantly increased the number of distinct bug-triggering inputs (e.g., +121 additional distinct triggers per bug in XML).
Insight: Conditioning effectively amplifies underrepresented patterns without sacrificing structural validity, especially when seed sets are sparse.

RQ3: Bug Triggering Input Diversity

Comparison: ExplainFuzz vs. Grammarinator (grammar-aware mutational fuzzer).
Results:
- Bug Coverage: Improved from 35.3% to 39.7% in SQL and from 10% to 82.5% in XML.
- Distinct Triggers: ExplainFuzz produced +417 additional distinct bug-triggering inputs per seed set in SQL and +1587 in XML.
- Qualitative Analysis: ExplainFuzz generated semantically plausible inputs (e.g., correct column joins, realistic file paths) whereas Grammarinator often produced generic or semantically weak inputs (e.g., SELECT *).
Insight: While Grammarinator is limited to the local neighborhood of seed inputs, ExplainFuzz's learned distribution explores a much broader semantic space.

5. Significance

Paradigm Shift: Moves fuzzing from "local mutation" to "global probabilistic modeling," enabling the discovery of bugs that require specific, rare combinations of syntactic structures.
Interpretability: Provides developers with a transparent mechanism to understand why certain inputs are generated and to debug the input distribution itself.
Practical Utility: The ability to condition generation on specific constraints (e.g., "test only queries with UNION") makes it a powerful tool for targeted security auditing and regression testing.
Foundation for Future Work: Demonstrates that Probabilistic Circuits are a viable, efficient, and scalable foundation for next-generation, grammar-aware test generation tools.

The paper concludes that ExplainFuzz bridges the gap between the syntactic guarantees of grammar-based fuzzing and the probabilistic expressivity of modern generative models, offering a controllable, explainable, and highly effective approach to software testing.