Z3 — High-Performance SMT Solver by Microsoft Research

Introduction

Z3 is an SMT (Satisfiability Modulo Theories) solver developed by Microsoft Research. It decides the satisfiability of logical formulas over integers, bit-vectors, arrays, floating-point numbers, and other data types. Z3 is widely used in program verification, symbolic execution, test generation, and constraint-based synthesis.

What Z3 Does

• Solves satisfiability problems over arithmetic, bit-vectors, arrays, and strings
• Powers program verification tools like Dafny, KLEE, and Seahorn
• Supports optimization objectives (MaxSMT) for constrained optimization
• Provides proof generation and unsatisfiable core extraction
• Offers bindings for Python, C, C++, Java, .NET, and OCaml

Architecture Overview

Z3 implements a DPLL(T) architecture combining a SAT solver core with theory solvers for linear arithmetic, non-linear arithmetic, bit-vectors, arrays, datatypes, sequences, and floating-point. Theories communicate through an equality graph, and the solver supports incremental solving with push/pop scopes. The fixedpoint engine adds Datalog and CHC (constrained Horn clause) solving.

Self-Hosting & Configuration

• Install the Python binding: pip install z3-solver
• Pre-built binaries available for Linux, macOS, and Windows
• Build from source with CMake for custom configurations
• No external dependencies beyond a C++ compiler for source builds
• Embeddable as a library via the C API in any application

Key Features

• One of the fastest and most widely adopted SMT solvers in the world
• Incremental solving for interactive verification workflows
• Supports quantifiers with pattern-based and MBQI instantiation
• Parallel solving mode for multi-core utilization
• Extensive documentation and an active research community

Comparison with Similar Tools

• CVC5 — competitive SMT solver; Z3 has broader industry adoption
• Yices 2 — lightweight and fast for specific theories; Z3 covers more theory combinations
• MathSAT — strong on interpolation; Z3 has wider language bindings
• STP — specialized for bit-vector/array; Z3 is more general-purpose

FAQ

Q: Is Z3 suitable for production use? A: Yes. Z3 is used in production by Microsoft, Amazon, and others for verification, security analysis, and network configuration validation.

Q: Can Z3 solve optimization problems? A: Yes. Z3 supports optimization via its Optimize class, handling both hard constraints and soft objectives with priorities.

Q: What is the difference between SAT and SMT? A: SAT solves Boolean satisfiability. SMT extends SAT with theories like arithmetic and arrays, letting you reason about richer domains.

Q: Does Z3 support non-linear arithmetic? A: Yes, Z3 has a dedicated nlsat solver for non-linear real arithmetic and heuristic support for non-linear integer arithmetic.

Sources

• https://github.com/Z3Prover/z3
• https://z3prover.github.io/