Satisfiability.jl: Satisfiability Modulo Theories in Julia

Emiko Soroka, Mykel J. Kochenderfer, Sanjay LallJ. Open Source Softw 2024 · DOI · DBLP

Introduction

Satisfiability Modulo Theories (SMT) is a fundamental tool in formal verification, used extensively to prove software correctness, validate hardware models, and solve complex combinatorial problems. Despite its importance, interacting with SMT solvers has traditionally been a low-level, cumbersome process. Satisfiability.jl addresses this gap by providing a high-level, idiomatic Julia interface that leverages the language's unique strengths to simplify formal modeling.

The SMT Interface Problem

The industry standard for interacting with solvers, SMT-LIB, utilizes a Lisp-like syntax that is difficult to script and maintain. Furthermore, SMT-LIB has strict state-dependent rules; for instance, a user cannot query a model unless the solver is explicitly in a "satisfied" state. While libraries exist for Python and C++, previous Julia integrations were often thin wrappers around C++ APIs. These wrappers failed to utilize Julia’s expressive type system and syntax, creating a significant barrier for researchers in the formal methods community who prefer Julia's high-performance, high-level environment.

Technical Architecture

Satisfiability.jl acts as a sophisticated abstraction layer over the SMT-LIB standard. Its design is centered on several core Julia features:

  • Multiple Dispatch: The package utilizes Julia’s multiple dispatch to handle type promotion and expression simplification. For example, logical operations involving mixed types (e.g., Booleans and Integers) are automatically converted into valid SMT "if-then-else" (ite) expressions.
  • Metaprogramming: Drawing inspiration from the JuMP.jl ecosystem, the library uses macros to define variables and uninterpreted functions efficiently, reducing boilerplate code.
  • Solver Agnosticism: Rather than linking to specific C++ binaries, Satisfiability.jl communicates with solvers via input/output pipes. This approach ensures the library is solver-agnostic; it can interface with any SMT-LIB compliant solver (such as Z3 or CVC5) available on the user's system path.
  • Automated State Management: The library transparently manages the solver’s internal assertion stack. By handling push! and pop! operations automatically, it allows users to interactively modify and re-solve problems without manual SMT-LIB scripting.

Key Innovations

The primary contribution of Satisfiability.jl is the transition from writing string-based Lisp code to using standard Julia mathematical operators. Key features include:

  • Idiomatic Modeling: The package supports Unicode and standard operator precedence, allowing SMT formulae to be written as standard mathematical code.
  • Array Broadcasting: While SMT-LIB does not natively support operations across arrays, Satisfiability.jl implements broadcasting. This enables users to apply logical constraints across entire vectors or matrices of variables in a single line.
  • Automatic Type Promotion: The library uses Julia’s type system to ensure that expressions are valid before they are sent to the solver, handling the conversion between types like Bool, Int, and BitVector.

Future Directions

While Satisfiability.jl currently provides robust support for propositional logic, integer/real arithmetic, and bit vectors, the authors have identified several areas for future development. These include expanding support for other SMT-LIB theories, such as strings and arrays, and implementing automatic logic detection. The latter would allow the library to identify the simplest logic type for a given problem, helping back-end solvers select the most efficient algorithms automatically.

By providing a modern, idiomatic interface, Satisfiability.jl lowers the barrier to entry for formal verification in Julia, enabling researchers to focus on problem modeling rather than the intricacies of solver communication.

Reference: Soroka et al., (2024). Satisfiability.jl: Satisfiability Modulo Theories in Julia. Journal of Open Source Software, 9(100), 6757. https://doi.org/10.21105/joss.06757

Summary updated

BibTeX
@article{soroka2024satisfiability,
  author = {Emiko Soroka and Mykel J. Kochenderfer and Sanjay Lall and Mykel Kochenderfer},
  title = {{Satisfiability.jl: Satisfiability Modulo Theories in Julia}},
  journal = {J. Open Source Softw.},
  year = {2024},
  doi = {10.21105/joss.06757},
}
Figure