Boosting Skeleton-Driven SMT Solver Fuzzing by Leveraging LLM to Produce Formula Generators DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8

Maolin Sun, Yibiao Yang, Yuming Zhou · 2025

Read Boosting Skeleton-Driven SMT Solver Fuzzing by Leveraging LLM to Produce Formula Generators DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8 by Maolin Sun, Yibiao Yang, Yuming Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20340.txt.

Introduction

Maolin Sun and co-authors present Once4All in a 2025 paper, a skeleton-guided method to fuzz SMT solvers with language model help. The hosted head gives the method its full name, and solvers underpin program checking, so their bugs matter.

Direct model generation yields many invalid formulas and costly chat loops. Once4All instead has the model write reusable term generators once, guided by grammars drawn from solver documents. Fuzzing then fills skeletons from real formulas with fresh generated terms. That keeps syntax valid while varying meaning widely. Tests on two leading solvers back the approach. A one-time model cost replaces repeated calls, cutting runtime overhead for deep bug hunts.

Catalog record

CREATORMaolin Sun, Yibiao Yang, Yuming Zhou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-20340

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Boosting Skeleton-Driven SMT Solver Fuzzing by Leveraging LLM to Produce Formula Generators DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8 Maolin Sun, Yibiao Yang, Yuming Zhou Abstract . Satisfiability Modulo Theory (SMT) solvers are foundational to modern systems and programming languages research, providing the foundation for tasks like symbolic execution and automated verification. Because these solvers sit on the critical path, their correctness is essential, and high-quality test formulas are key to uncovering bugs. However, while prior testing techniques performed well on earlier solver versions, they struggle to keep pace with rapidly evolving features. Recent approaches based on Large Language Models (LLMs) show promise in exploring advanced solver capabilities, but two obstacles remain: nearly half of the generated formulas are syntactically invalid, and iterative interactions with the LLMs introduce substantial computational overhead. In this study, we present Sphinx , a novel LLM-assisted fuzzing framework that addresses both issues by shifting from direct formula generation to the synthesis of reusable term (i.e., logical expression) generators. Particularly, Sphinx uses LLMs to (1) automatically extract context-free grammars (CFGs) for SMT theories, including solver-specific extensions, from documentation, and (2) synthesize composable Boolean term generators that adhere to these grammars. During fuzzing, Sphinx populates structural skeletons derived from existing formulas with the terms iteratively produced by the LLM-synthesized generators. This design ensures syntactic validity while promoting semantic diversity. Notably, Sphinx requires only one-time LLM interaction investment , dramatically reducing runtime cost. We evaluated Sphinx on two leading SMT solvers: Z3 and cvc5. Our experiments show that Sphinx has identified 43 confirmed bugs, 40 of which have already been fixed by developers. 1. Introduction Satisfiability Modulo Theory (SMT) solvers are essential systems for automatically determining the satisfiability of logical formulas with respect to background theories, such as arithmetic, bit-vectors, and strings ( Barrett and Tinelli 2018 ) . They play a critical role across multiple domains, including computer systems ( Jia et al. 2019 ; Nelson et al. 2017 ; Hawblitzel et al. 2014 ; Hance et al. 2020 ) , computer networks ( Han et al. 2024 ; Lopes et al. 2015 ; El-Hassany et al. 2018 ) , and programming languages ( Li et al. 2014 ; Kang et al. 2019 ; Liu et al. 2023 ) . For instance, the renowned symbolic execution engine KLEE ( Cadar et al. 2008 ) relies on SMT solvers to check the feasibility of program paths. However, bugs hidden in SMT solvers would inevitably mislead client applications, resulting in serious consequences and even security vulnerabilities ( Huang 2023 ) . Thus, ensuring the reliability of SMT solvers is of critical importance. To this end, various approaches have been proposed for testing SMT solvers, which can be broadly classified into three categories: (1) generation-based ( Brummayer and Biere 2009 ; Niemetz et al. 2022 ; Winterer and Su 2024 ) , (2) mutation-based ( Winterer et al. 2020b ; Mansur et al. 2020 ; Winterer et al. 2020a ; Park et al. 2021 ; Kim et al. 2023 ; Sun et al. 2023b ) , and (3) LLM-based ( Sun et al. 2023a ; Xia et al. 2024b ) . Generation-based approaches typically generate formulas from scratch based on predefined generation rules or grammar. For instance, ET ( Winterer and Su 2024 ) is a representative technique that enumerates formulas based on grammar. Mutation-based approaches, on the other hand, involve mutating existing formulas to generate new ones. One of the most advanced approaches in this category is HistFuzz ( Sun et al. 2023b ) , which utilizes historical bug-triggering formulas to generate new formulas. Furthermore, researchers have explored LLM-based approaches inspired by the advancement of large language models (LLMs). These approaches aim to generate SMT formulas directly using LLMs ( Sun et al. 2023a ; Xia et al. 2024b ) . For instance, LaST ( Sun et al. 2023a ) retrained an LLM, aiming to generate effective test formulas from scratch. Fuzz4All ( Xia et al. 2024b ) is a universal framework that is applicable to various software systems, including SMT solvers. It can generate test inputs for SMT solvers by prompting the generation LLM with the prompt generated by another LLM. Despite notable progress, existing SMT solver fuzzing approaches still face several challenges. Generation-based techniques often struggle to produce diverse formulas because they rely on rigid generative rules, and their from-scratch generation process makes it costly to reach deeper solver states. In comparison, mutation-based approaches can leverage seed formulas to more efficiently explore deeper execution paths. However, their effectiveness still depends heavily on the design of mutation strategies ( Park et al. 2021 ; Sun et al. 2023a ) . For instance, OpFuzz ( Winterer et al. 2020a ) only mutate the operators in seed formulas, which may restrict the diversity of generated formulas. More recently, LLM-based techniques directly prompt large language models to generate complete SMT formulas. While attractive in principle, such approaches often produce inputs that are syntactically or semantically invalid (approximately 50%) ( Sun et al. 2023a ; Xia et al. 2024b ) , sometimes leads to nonsensical bug reports 1 1 1 https://github.com/Z3Prover/z3/issues/6818 , and incur substantial computational cost due to heavy interaction with LLMs. Meanwhile, the SMT-LIB standard ( Barrett et al. 2022 ) , the primary input language for SMT solvers, continues to evolve. The recent release of version 2.7 and the planned introduction of SMT-LIBv3 reflect the community’s ongoing efforts to support richer language features. Concurrently, SMT solvers like cvc5 have introduced extended, solver-specific theories ( cvc5 2025 ) to better express real-world constraints. Collectively, these developments increase the demand for fuzzing techniques that can adapt to evolving changes for better testing emerging solver capabilities. Our Approach. In this study, we propose Sphinx , a novel SMT solver fuzzing framework that unifies the strengths of mutation-based fuzzing with the advanced capabilities of LLMs. While mutation-based fuzzing techniques achieve high testing throughput and deep state exploration by mutating existing test cases, adapting them to support newly introduced or evolving SMT features typically requires substantial manual effort. Sphinx overcomes this limitation by leveraging LLMs’ contextual understanding and program synthesis abilities to enable rapid, automated adaption to changes in solver input language. Specifically, Sphinx includes two key phases: (1) LLM-assisted generator construction and (2) skeleton-guided mutation . In the first phase, Sphinx prompts LLMs to extract and summarize the context-free grammars (CFGs) of SMT-LIB theories, drawing from the official documentation ( Barrett et al. 2022 ) . We also include grammar for solver-specific extensions, such as the Bag and Set theories in cvc5 ( cvc5 2025 ) . Based on these CFGs, LLMs then synthesize reusable generators that emit Boolean terms (i.e., logical expressions) conforming to the theories. This process is a one-time investment , only requiring repetition when grammar evolve. The second phase employs these generators within a skeleton-guided mutation procedure. The skeletons are derived by removing small Boolean terms from seed formulas ( Sun et al. 2023b ) . The terms generated by the LLM-implemented generators are then synthesized into the skeletons, producing novel test formulas. Sphinx finally performs differential testing across multiple solvers to detect behavioral divergences indicative of bugs. We have implemented Sphinx as a practical and extensible

Read the complete text