Theory Refinement for Program Verification

TitleTheory Refinement for Program Verification
Publication TypeConference Proceedings
Year of Conference2017
AuthorsHyvärinen, Antti E. J., Asadi Sepideh, Even Mendoza Karine, Fedyukovich Grigory, Chockler Hana, and Sharygina Natasha
Conference NameSAT 2017
PublisherSpringer LNCS series
Conference LocationMelbourne, 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.
Full Text