Theory Refinement for Program Verification

Antti Hyyvarinen, Sepideh Asadi, Karine Even-Mendoza, Grigory Fedyukovich, Hana Chockler, Natasha Sharygina

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

6 Citations (Scopus)
352 Downloads (Pure)


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.
Original languageEnglish
Title of host publication 20th International Conference on Theory and Applications of Satisfiability Testing (SAT)
ISBN (Electronic) 978-3-319-66263-3
ISBN (Print)978-3-319-66262-6
Publication statusE-pub ahead of print - 9 Aug 2017


Dive into the research topics of 'Theory Refinement for Program Verification'. Together they form a unique fingerprint.

Cite this