Validating SMT Solvers for Correctness and Performance via Grammar-based Enumeration
We introduce ET, a grammar-based enumerator for validating SMT solver correctness and performance. By compiling grammars of the SMT theories to algebraic datatypes, ET leverages the functional enumerator FEAT. ET is highly effective at bug finding and has many complimentary benefits. Despite the extensive and continuous testing of the state-of-the-art SMT solvers Z3 and cvc5, ET found 102 bugs, out of which 76 were confirmed and 32 were fixed. Moreover, ET can be used to understand the evolution of solvers. We derive eight grammars realizing all major SMT theories including the booleans, integers, reals, realints, bit-vectors, arrays, floating points, and strings. Using ET, we test all consecutive releases of the SMT solvers Z3 and CVC4/cvc5 from the last six years (61 versions) on 8 million formulas, and 488 million solver calls. Our results suggest improved correctness in recent versions of both solvers but decreased performance in newer releases of Z3 on small timeouts (since z3-4.8.11) and regressions in early cvc5 releases on larger timeouts. Due to its systematic testing and efficiency, we further advocate ET’s use for continuous integration.
Fri 25 OctDisplayed time zone: Pacific Time (US & Canada) change
13:50 - 15:30 | Program Synthesis and Verification 2OOPSLA 2024 at San Gabriel Chair(s): Tony Hosking Australian National University | ||
13:50 20mTalk | Automating Unrealizability Logic: Hoare-style Proof Synthesis for Infinite Sets of Programs OOPSLA 2024 Shaan Nagy University of Wisconsin-Madison, Jinwoo Kim Seoul National University, Thomas Reps University of Wisconsin-Madison, Loris D'Antoni University of Wisconsin-Madison DOI | ||
14:10 20mTalk | Compositionality and Observational Refinement for Linearizability with Crashes OOPSLA 2024 Arthur Oliveira Vale Yale University, Zhongye Wang Shanghai Jiao Tong University, Yixuan Chen Yale University, Peixin You Yale University, Zhong Shao Yale University DOI | ||
14:30 20mTalk | Hypra: A Deductive Program Verifier for Hyper Hoare Logic OOPSLA 2024 DOI | ||
14:50 20mTalk | SMT2Test: From SMT Formulas to Effective Test Cases OOPSLA 2024 DOI | ||
15:10 20mTalk | Validating SMT Solvers for Correctness and Performance via Grammar-based Enumeration OOPSLA 2024 DOI |