|Title||Theory Refinement for Program Verification|
|Publication Type||Conference Proceedings|
|Year of Conference||2017|
|Authors||Hyvärinen, Antti E. J., Asadi Sepideh, Even Mendoza Karine, Fedyukovich Grigory, Chockler Hana, and Sharygina Natasha|
|Conference Name||SAT 2017|
|Publisher||Springer LNCS series|
|Conference Location||Melbourne, Australia|
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.
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.