Detecting Critical Bugs in SMT Solvers Using Blackbox Mutational Fuzzing
Preprint
Abstract
Formal methods use SMT solvers extensively for deciding formula satisfiability, for instance, in software verification, systematic test generation, and program synthesis. However, due to their complex implementations, solvers may contain critical bugs that lead to unsound results. Given the wide applicability of solvers in software reliability, relying on such unsound results may have detrimental consequences. In this paper, we present STORM, a novel blackbox mutational fuzzing technique for detecting critical bugs in SMT solvers. We run our fuzzer on seven mature solvers and find 29 previously unknown critical bugs. STORM is already being used in testing new features of popular solvers before deployment.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Automatically testing string solvers2020
- Testing static analyses for precision and soundness2020
- Finding and understanding bugs in software model checkers2019
- Automatically testing implementations of numerical abstract domains2018
- Automatic testing of symbolic execution engines via program generation and differential testing2017
- Views on Internal and External Validity in Empirical Software Engineering2015
- The Oracle Problem in Software Testing: A SurveyIEEE Transactions on Software Engineering, 2015
- Formal verification of a modern SAT solver by shallow embedding into Isabelle/HOLTheoretical Computer Science, 2010
- Automated Testing and Debugging of SAT and QBF Solvers2010
- Fuzzing and delta-debugging SMT solvers2009