Once4All: Skeleton-Guided SMT Solver Fuzzing with LLM-Synthesized Generators

1. Problem Statement

Satisfiability Modulo Theory (SMT) solvers are critical components in formal verification, symbolic execution, and automated reasoning. Ensuring their correctness is paramount, as bugs can lead to security vulnerabilities and incorrect verification results. While various fuzzing techniques exist (generation-based, mutation-based, and LLM-based), they face significant challenges in the context of rapidly evolving SMT solvers:

• Adaptability: Traditional generation-based methods rely on rigid, manually crafted grammars that struggle to keep pace with new SMT-LIB standards and solver-specific extensions (e.g., Bag, Set, or Finite Field theories).
• Validity & Cost: Direct LLM-based approaches often generate a high rate of syntactically invalid formulas (nearly 50%) and incur substantial computational overhead due to repeated, iterative interactions with the LLM during the fuzzing process.
• Depth: Purely grammar-based generators often miss deep solver logic triggered by complex structural elements (like quantifiers) that are not fully specified in theory documentation.

2. Methodology: Once4All

The authors propose Once4All, a novel fuzzing framework that unifies the high throughput of mutation-based fuzzing with the adaptability of Large Language Models (LLMs). The core innovation is shifting from direct formula generation to the synthesis of reusable generators for logical terms. The framework operates in two distinct phases:

Phase 1: LLM-Assisted Generator Construction (One-Time Investment)

Instead of querying the LLM for every test case, Once4All uses the LLM once per theory to build robust, self-correcting Python generators.

1. CFG Extraction: The LLM analyzes official SMT-LIB documentation and solver-specific extension docs to automatically summarize Context-Free Grammars (CFGs) for various theories.
2. Generator Synthesis: Using the extracted CFGs, the LLM synthesizes Python code that generates Boolean terms (logical expressions) conforming to the grammar.
3. Self-Correction Loop: To ensure validity, the system employs a feedback loop. The generated generator produces sample terms, which are parsed by multiple solvers (e.g., Z3, cvc5). If parsing errors occur, the error messages are fed back to the LLM to refine the generator code. This process repeats until the generator produces a high rate of syntactically valid terms.

Phase 2: Skeleton-Guided Mutation

Once the generators are ready, the fuzzing loop begins:

1. Skeleton Extraction: The system takes existing "seed" formulas (from benchmarks or historical bug reports) and removes atomic sub-formulas, replacing them with <placeholder> markers. This preserves the high-level structural logic (e.g., quantifiers, logical connectives) which is often crucial for triggering deep bugs.
2. Term Synthesis: The LLM-synthesized generators produce new Boolean terms.
3. Integration: The new terms are inserted into the skeletons. The system performs sort-checking (ensuring types like Int, Real, or Bool match) and variable substitution to maximize semantic interaction between the new terms and the existing skeleton.
4. Differential Testing: The resulting formulas are fed to multiple solvers. Discrepancies in output (e.g., one solver returns sat while another returns unsat, or a crash occurs) indicate potential bugs.

3. Key Contributions

• Novel Architecture: A hybrid approach that leverages LLMs for meta-programming (creating generators) rather than direct input generation, combined with skeleton-guided mutation to ensure structural depth.
• Adaptability: The framework automatically adapts to new SMT theories and solver-specific extensions by re-running the generator construction phase, eliminating the need for manual grammar updates.
• Efficiency: By synthesizing generators once and reusing them, Once4All avoids the high latency and cost of continuous LLM interaction during the fuzzing loop.
• High Validity: The self-correction mechanism ensures that the vast majority of generated terms are syntactically valid, overcoming the "hallucination" problem common in direct LLM prompting.

4. Experimental Results

The authors evaluated Once4All on two leading SMT solvers: Z3 and cvc5.

• Bug Discovery:
  • Identified 45 unique bugs in total.
  • 43 bugs were confirmed by developers.
  • 40 bugs have been fixed in the latest versions.
  • Crucially, 11 bugs involved newly added or solver-specific theories (e.g., Finite Fields, Sets) that existing fuzzers could not detect.
  • The tool uncovered long-latent bugs (some present for over 6 years) and bugs in the latest trunk versions.
• Code Coverage:
  • Once4All consistently achieved higher line and function coverage compared to state-of-the-art fuzzers (including HistFuzz, OpFuzz, Fuzz4All, and LaST).
  • It reached code paths in solver-specific extensions (e.g., src/theory/sets/ in cvc5) that baseline tools missed.
• Ablation Studies:
  • Removing the skeleton guidance significantly reduced code coverage and bug discovery, proving that structural templates are essential for triggering deep logic.
  • Changing the underlying LLM (e.g., from GPT-4 to Gemini or Claude) resulted in comparable performance, demonstrating the framework's robustness.

5. Significance

• Practical Impact: The tool has already led to significant improvements in the stability of major SMT solvers, with 40 confirmed fixes.
• Methodological Shift: It demonstrates a new paradigm for using LLMs in software testing: using them to build tools (generators) that are then used for high-volume testing, rather than using them as the test generator itself. This solves the scalability and validity issues of direct prompting.
• Future-Proofing: As SMT solvers continue to evolve with new theories and features, Once4All offers a scalable, automated pathway to maintain high-quality testing coverage without requiring constant manual intervention from researchers.