Output list
1–10 of 166 results
Conference proceeding
Parse this! Summoning Context-Sensitive Inputs with Goblin
Published 09/11/2026
Proceedings of the 2026 IEEE/ACM 48th International Conference on Software Engineering, 3975 - 3986
ICSE '26: 2026 IEEE/ACM 48th International Conference on Software Engineering
Grammar-based fuzzers have been effective at identifying bugs in software systems with highly structured input formats (e.g., XML). Many existing grammar-based fuzzers rely on context-free grammars (CFGs) to represent input structure; however, CFGs are often insufficient to capture the context-sensitive constraints common in real-world inputs. While application-specific fuzzers can often handle such constraints, they lack the generality needed to adapt to new applications. We present Goblin , a new input generation tool that addresses this gap. Given a context-free grammar annotated with semantic constraints, Goblin generates inputs that both conform to the grammar and satisfy the constraints. A distinguishing feature of Goblin is its support—via an external SMT solver—for constraints expressed in arbitrary SMT theories. Inspired by DPLL-style SAT solvers, Goblin enjoys formal guarantees of solution soundness, solution completeness, and refutation soundness. We evaluate Goblin by comparing it with prior work and by integrating it into a grammar-based network protocol fuzzer.
Dataset
Benchmarks for Solving LIA⋆ Constraints Using Hilbert Bases
Published 08/04/2026
Preprint
Automated Reasoning with Nested Datatypes
Posted to a preprint site 07/01/2026
ArXiv.org
We introduce a theory of nested datatypes. The theory is obtained by restricting the naive combination of datatypes and arrays, so as to prevent non-standard models from emerging. A decision procedure for the theory is given and proven correct. Finally, we describe an implementation of the procedure, as well as an evaluation over both real-world and crafted benchmarks.
Conference proceeding
Published 01/08/2026
Proceedings of the 15th ACM SIGPLAN International Conference on Certified Programs and Proofs, 216 - 230
CPP '26: 15th ACM SIGPLAN International Conference on Certified Programs and Proofs
Determining the satisfiability of formulas involving nonlinear real arithmetic and transcendental functions is necessary in many applications, such as formally verifying dynamic systems. Doing this automatically generally requires costly and intricate methods, which limits their applicability. In the context of SMT solving, Incremental Linearization was introduced recently to facilitate reasoning on this domain, via an incomplete but easy to implement and highly effective approach. The approach, based on abstraction-refinement via an incremental axiomatization of the nonlinear and transcendental operators, is currently implemented in the SMT solvers MathSAT and cvc5. The cvc5 implementation is also proof-producing. This paper presents two contributions: a formalization in the Lean proof assistant of the proof calculus employed by cvc5, and an extension of the lean-smt plugin to reconstruct the proofs produced by cvc5 using this proof calculus. These contributions ensure the soundness of the proof calculus, making the underlying algorithm more trustworthy. Moreover, they allow users to check cvc5 results obtained via incremental linearization, as well as improve Lean’s automation for problems in nonlinear arithmetic. We discuss how we modeled the rules in the proof assistant and the challenges encountered while formalizing them, as well as the issues in reconstructing proofs involving these rules in Lean, and how we solved them.
Conference proceeding
Solving Set Constraints With Comprehensions and Bounded Quantifiers
Published 10/06/2025
2025 Formal Methods in Computer-Aided Design (FMCAD), 1 - 11
Many problems in real-world applications can be expressed easily as quantified formulas in SMT. Unfortunately, reasoning about quantified formulas in SMT is notoriously difficult. While different strategies and quantifier instantiation techniques have been developed to tackle this challenge, SMT solvers still struggle with quantified formulas generated by some applications. We discuss the use of set-bounded quantifiers, quantifiers whose variable ranges over a finite, but possibly unbounded, set. Such quantifiers can be eliminated using the quantifier-free fragment of the theory of finite relations extended with a filter operator, which provides a form of restricted set comprehension. We show that this reduction to filter constraints outperforms other quantification techniques in satisfiable problems generated by the SLEEC tool, and is very competitive on unsatisfiable benchmarks with LEGOS, a specialized solver for SLEEC. We also identify a decidable class of constraints with restricted applications of the filter operator, while showing that unrestricted applications lead to undecidability.
Conference proceeding
Towards SMT Solver Stability via Input Normalization
Published 10/06/2025
2025 Formal Methods in Computer-Aided Design (FMCAD), 84 - 93
In many applications, SMT solvers are utilized to solve similar or identical tasks over time. Significant variations in performance due to small changes in the input are not uncommon and lead to frustration for users. This sort of stability problem represents an important usability challenge for SMT solvers. We introduce an approach for mitigating the stability problem based on normalizing solver inputs. We show that a perfect normalizing algorithm exists but is computationally expensive. We then describe an approximate algorithm and evaluate it on a set of benchmarks from related work, as well as a large set of benchmarks sampled from SMT-LIB. Our evaluation shows that our approximate normalizer reduces runtime variability with minimal overhead and is able to normalize a large class of mutated benchmarks to a unique normal form.
Conference proceeding
Improving the SMT Proof Reconstruction Pipeline in Isabelle/HOL
Published 09/22/2025
16th International Conference on Interactive Theorem Proving, ITP 2025, 352, 26
Preprint
Solving Set Constraints with Comprehensions and Bounded Quantifiers
Posted to a preprint site 08/11/2025
ArXiv.org
Many real applications problems can be encoded easily as quantified formulas in SMT. However, this simplicity comes at the cost of difficulty during solving by SMT solvers. Different strategies and quantifier instantiation techniques have been developed to tackle this. However, SMT solvers still struggle with quantified formulas generated by some applications. In this paper, we discuss the use of set-bounded quantifiers, quantifiers whose variable ranges over a finite set. These quantifiers can be implemented using quantifier-free fragment of the theory of finite relations with a filter operator, a form of restricted comprehension, that constructs a subset from a finite set using a predicate. We show that this approach outperforms other quantification techniques in satisfiable problems generated by the SLEEC tool, and is very competitive on unsatisfiable benchmarks compared to LEGOS, a specialized solver for SLEEC. We also identify a decidable class of constraints with restricted applications of the filter operator, while showing that unrestricted applications lead to undecidability.
Conference proceeding
Bit-Precise Reasoning with Parametric Bit-Vectors
Published 08/07/2025
28th International Conference on Theory and Applications of Satisfiability Testing, SAT 2025, 341, 4
The SMT-LIB theory of bit-vectors is restricted to bit-vectors of fixed width. However, several important applications can benefit from reasoning about bit-vectors of symbolic widths, i.e., parametric bit-vectors. Recent work has introduced an approach for solving formulas over parametric bit-vectors, via an eager translation to quantified integer arithmetic with uninterpreted functions. The approach was shown to be successful for several applications, including the bit-width independent verification of compiler optimizations, invertibility conditions, and rewrite rules. We extend and improve that approach in several aspects. Theoretically, we improve expressiveness by defining a new theory of parametric bit-vectors that supports more operators and allows reasoning about the bit-widths themselves. Algorithmically, we introduce a lazy algorithm that avoids the use of uninterpreted functions and quantified axioms for them. Empirically, we show a significant improvement by implementing and evaluating our approach, and comparing it experimentally to the previous one.
Dataset
SMT-LIB release 2025 (incremental benchmarks)
Published 05/22/2025
This is the SMT-LIB benchmark library: a large library of input problems, or benchmarks, written in the SMT-LIB language. More information about the SMT-LIB initiative can be found at https://smt-lib.org. The contributor and licence of each benchmark is indicated in the metadata fields of each benchmark file.
This collection contains the incremental benchmarks.
Benchmarks are grouped by logic and compressed with the zstd compression algorithm using the tar --zstd. SMT-LIB benchmarks usually have a very high compression rate, be aware of the required disk space when uncompressing the archives. You can find the size of each archive in compressed and uncompressed form in the following list.