Abstract
Recent progress in automated formal verification is to a large degree
due to the development of constraint languages that are sufficiently
light-weight for reasoning but still expressive enough to prove
properties of programs.
Satisfiability modulo theories (SMT) solvers implement efficient
decision procedures, but offer little direct support for adapting the
constraint language to the task at hand.
\emph{Theory refinement} is a new approach that modularly adjusts the
modeling precision based on the properties being verified through the
use of combination of theories.
We implement the approach using an augmented version of the theory of
bit-vectors and uninterpreted functions capable of directly injecting
non-clausal refinements to the inherent Boolean structure of SMT.
In our comparison to a state-of-the-art model checker, our prototype
implementation is in general competitive, being several orders of
magnitudes faster on some instances that are challenging for flattening,
while computing models that are significantly more succinct.
due to the development of constraint languages that are sufficiently
light-weight for reasoning but still expressive enough to prove
properties of programs.
Satisfiability modulo theories (SMT) solvers implement efficient
decision procedures, but offer little direct support for adapting the
constraint language to the task at hand.
\emph{Theory refinement} is a new approach that modularly adjusts the
modeling precision based on the properties being verified through the
use of combination of theories.
We implement the approach using an augmented version of the theory of
bit-vectors and uninterpreted functions capable of directly injecting
non-clausal refinements to the inherent Boolean structure of SMT.
In our comparison to a state-of-the-art model checker, our prototype
implementation is in general competitive, being several orders of
magnitudes faster on some instances that are challenging for flattening,
while computing models that are significantly more succinct.
| Original language | English |
|---|---|
| Title of host publication | 20th International Conference on Theory and Applications of Satisfiability Testing (SAT) |
| Publisher | Springer |
| Pages | 347-363 |
| Volume | 10491 |
| ISBN (Electronic) | 978-3-319-66263-3 |
| ISBN (Print) | 978-3-319-66262-6 |
| DOIs | |
| Publication status | E-pub ahead of print - 9 Aug 2017 |