Beyond First-Order Satisfaction: Fixed Points, Interpolants, Automata and Polynomials

In the last decade, advances in satisfiability-modulo-theories (SMT) solvers have powered a new generation of software tools for verification and testing. These tools transform various program analysis problems into the problem of satisfiability of formulas in propositional or first-order logic, where they are discharged by SMT solvers, such as Z3 from Microsoft Research. This paper briefly summarizes four initiatives from Microsoft Research that build upon Z3 and move beyond first-order satisfaction:

Fixed points

—

μZ

is a scalable, efficient engine for discharging fixed point queries over recursive predicates with logical constraints, integrated in Z3;

Interpolants

—Interpolating Z3 uses Z3’s proof generation capability to generate Craig interpolants in the first-order theory of uninterpreted functions, arrays and linear arithmetic;

Automata

—The symbolic automata toolkit lifts classical automata analyses to work modulo symbolic constraints on alphabets;

Polynomials

—a new decision procedure for the existential theory of the reals allows efficient solving of systems of non-linear arithmetic constraints.