paperbot · PL 论文追踪

全部论文 待读 收藏

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

Once4All:骨架引导的 SMT 求解器模糊测试与 LLM 合成生成器
ASPLOS Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 22026匹配度 5/10 · 论文用 LLM 合成可复用生成器来模糊测试 SMT 求解器,属于 LLM 辅助形式化验证/静态分析基础设施的邻近工作,但核心任务是测试求解器而非程序分析或验证方法本身。与用户关注的浮点程序分析、贝叶斯程序分析及 Agentic 程序静态分析无直接交集。引用 1 inbox
Maolin Sun, Yibiao Yang, Yuming Zhou
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:用 LLM 一次性地合成可复用项生成器,并以结构骨架引导填充,实现语法合法且高效的 SMT 求解器模糊测试。

SMT 求解器是符号执行与自动验证等工作的基础,其正确性至关重要,但已有测试技术难以跟上求解器快速演进的新特性;基于 LLM 的方法虽能探索高级功能,却存在近半生成公式语法非法、以及反复与 LLM 交互带来高昂开销两大障碍。本文提出 Once4All,将 LLM 的用途从直接生成公式转为合成可复用项(逻辑表达式)的生成器:先用 LLM 从文档中自动抽取各 SMT 理论(含求解器特有扩展)的上下文无关文法,再合成符合这些文法的可组合布尔项生成器;模糊测试时,从已有公式导出结构骨架,并用生成器迭代产出的项填充骨架,从而在保证语法合法的同时提升语义多样性,且仅需一次性的 LLM 交互投入,大幅降低运行时开销。作者在 Z3 与 cvc5 上评估,共发现 43 个已确认缺陷,其中 40 个已被开发者修复。

问题
SMT 求解器是符号执行与自动验证的关键基础设施,但现有测试技术难以覆盖其快速演进的新特性;基于 LLM 的测试方法生成的公式近半数语法非法,且迭代调用 LLM 带来巨大计算开销。
方法
Once4All 用 LLM 从文档中抽取各 SMT 理论(包括求解器特有扩展)的上下文无关文法,并合成符合文法的可组合布尔项生成器;模糊测试时以现有公式导出的结构骨架为载体,用这些生成器迭代产生的项填充骨架。
评估
在 Z3 和 cvc5 两个主流 SMT 求解器上进行评估,共发现 43 个已被确认的缺陷,其中 40 个已由开发者修复,并验证了该设计在语法合法率与运行时开销上的优势。
原文摘要(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 LLMs introduce substantial computational overhead. In this study, we present Once4All, a novel LLM-assisted fuzzing framework that addresses both issues by shifting from direct formula generation to the synthesis of generators for reusable terms (i.e., logical expressions). Specifically, Once4All uses LLMs to (1) automatically extract context-free grammars (CFGs) for SMT theories, including solverspecific extensions, from documentation, and (2) synthesize composable Boolean term generators that adhere to these grammars. During fuzzing, Once4All 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, Once4All requires only one-time LLM interaction investment, dramatically reducing runtime cost. We evaluated Once4All on two leading SMT solvers: Z3 and cvc5. Our experiments show that Once4All has identified 43 confirmed bugs, 40 of which have already been fixed by developers.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@inproceedings{SunYZ26,
  title = {Once4All: Skeleton-Guided SMT Solver Fuzzing with LLM-Synthesized Generators},
  author = {Maolin Sun and Yibiao Yang and Yuming Zhou},
  booktitle = {ASPLOS},
  year = {2026},
  doi = {10.1145/3779212.3790195}
}