Constraint solving for finite model finding in SMT solvers

Andrew Reynolds, Cesare Tinelli, Clark W. Barrett

TL;DR

This paper introduces a novel approach to finite model finding within Satisfiability Modulo Theories (SMT) solvers. By integrating constraint solving techniques, particularly for cardinality constraints, the authors enable SMT solvers to find finite models for quantified formulas, overcoming limitations of existing methods that often report "unknown." This advancement is crucial for applications like automated verification where counter-models are essential.

What Problem Does This Paper Address?

SMT solvers are powerful tools for automated reasoning, widely used in areas like software and hardware verification. They excel at determining the satisfiability of quantifier-free formulas within specific theories (e.g., arithmetic, arrays). However, many real-world problems require reasoning about quantified formulas (e.g., "for all processes...", "for any memory location..."). Current SMT solvers often struggle with these, frequently returning "unknown" when they can't prove unsatisfiability. This inability to provide a counter-model (a specific example showing the formula is satisfiable) limits their usefulness in applications that need to demonstrate the existence of such examples. The paper aims to bridge this gap by enabling SMT solvers to find finite models for quantified formulas.

Methods

The core contribution is the integration of finite model finding techniques into the architecture of modern SMT solvers. This is achieved through:

  • A Novel Solver for Cardinality Constraints: The paper introduces a theory of "EUF with Finite Cardinality Constraints" (FCC) and a decision procedure for it. This allows the solver to reason about the finite size of domains for uninterpreted sorts.
  • On-Demand Instantiation of Quantified Formulas: Instead of generating all possible instances of quantified formulas (which is computationally infeasible), the approach uses model-based techniques. This means it leverages the structure of a candidate model to intelligently select which instances to check.
  • Integration with DPLL(T) Framework: The proposed methods are designed to fit seamlessly into the existing DPLL(T) architecture, which underpins many SMT solvers. This involves defining "weak effort" and "strong effort" checks within the framework to handle cardinality constraints and quantifier instantiation.
  • Candidate Model Construction: A procedure is described to construct finite models from satisfying assignments, using equivalence classes of terms as domain elements.

Datasets

The paper evaluates its approach on several benchmark sets:

  • Intel benchmarks: Verification conditions generated by DVF, covering various theories including linear integer arithmetic, arrays, EUF, and algebraic datatypes.
  • TPTP benchmarks: A widely-used library for automated theorem proving, focusing on problems involving equality and quantified formulas.
  • Isabelle benchmarks: Proof obligations from the Isabelle proof assistant, often involving integer arithmetic and quantifiers.

The authors also mention using randomly generated graph coloring problems as a specific type of benchmark for evaluating the FCC solver.

Key Insights and Ideas

  • Finite Models are Sufficient: For many practical problems, if a quantified formula is satisfiable, it often has a small finite model. This observation justifies focusing on finding finite models rather than arbitrary ones.
  • Cardinality Constraints as a Key Tool: Explicitly reasoning about the finite size of domains (cardinality constraints) is crucial for enabling finite model finding within SMT.
  • Model-Based Instantiation is Scalable: Generating all instances of quantified formulas is intractable. By using information from a candidate model, the solver can intelligently select instances, significantly improving scalability.
  • Orthogonal to Theorem Proving: The approach is presented as complementary to traditional automated theorem proving techniques, offering a different way to tackle quantified formulas.

Key Results

  • Competitive Performance: The implemented approach, integrated into the CVC4 SMT solver, shows competitive performance against state-of-the-art SMT solvers and automated theorem provers on various benchmarks.
  • Improved Scalability: Configurations using model-based quantifier instantiation (e.g., cvc4+fm) significantly outperform those using exhaustive instantiation, especially on benchmarks with a large number of potential instances. For example, cvc4+fm could solve benchmarks with trillions of instances, while cvc4+f struggled with those exceeding millions.
  • Effectiveness on Verification Benchmarks: The system demonstrates strong performance on benchmarks derived from industrial verification tasks (Intel benchmarks) and proof obligations from Isabelle.
  • Handling Unsatisfiable Cases: While primarily focused on finding models, the approach also contributes to solving unsatisfiable problems, often by finding conflicts related to cardinality bounds.

Limitations and Future Work

  • Limited Quantifier Scope: The current approach is primarily designed for formulas with quantifiers over uninterpreted sorts or finite built-in sorts (like bit-vectors).
  • Performance on Unsatisfiable Problems: For unsatisfiable problems, the finite model finding approach can be slower than dedicated SMT solvers that use E-matching, as it explores larger search spaces to find models.
  • Future Work: The authors plan to extend their approach to handle quantifiers over built-in domains like integers and inductive datatypes. They also aim to integrate their work with interactive proof assistants like Isabelle and Coq, where finding small counterexamples is often valuable. Further research into combining their techniques with advanced preprocessing methods (like clause splitting) is also suggested for improved scalability.

Summary updated

Abstract

Satisfiability modulo theories (SMT) solvers have been used successfully as reasoning engines for automated verification and other applications based on automated reasoning. Current techniques for dealing with quantified formulas in SMT are generally incomplete, forcing SMT solvers to report “unknown” when they fail to prove the unsatisfiability of a formula with quantifiers. This inability to return counter models limits their usefulness in applications that produce queries involving quantified formulas. In this paper, we reduce these limitations by integrating finite model finding techniques based on constraint solving into the architecture used by modern SMT solvers. This approach is made possible by a novel solver for cardinality constraints, as well as techniques for on-demand instantiation of quantified formulas. Experiments show that our approach is competitive with the state of the art in SMT, and orthogonal to approaches in automated theorem proving.
BibTeX
@article{reynolds2017constraint,
  author = {Andrew Reynolds and Cesare Tinelli and Clark W. Barrett},
  title = {{Constraint solving for finite model finding in SMT solvers}},
  journal = {Theory Pract. Log. Program.},
  year = {2017},
  doi = {10.1017/s1471068417000175},
}
Figure