Abstract
We consider the problem of deciding the satisfiability of quantifier-free formulas in the theory of finite sets with cardinality constraints. Sets are a common high-level data structure used in programming; thus, such a theory is useful for modeling program constructs directly. More importantly, sets are a basic construct of mathematics and thus natural to use when formalizing the properties of computational systems. We develop a calculus describing a modular combination of a procedure for reasoning about membership constraints with a procedure for reasoning about cardinality constraints. Cardinality reasoning involves tracking how different sets overlap. For efficiency, we avoid considering Venn regions directly, as done in previous work. Instead, we develop a novel technique wherein potentially overlapping regions are considered incrementally as needed, using a graph to track the interaction among the different regions. The calculus has been designed to facilitate its implementation within SMT solvers based on the DPLL($T$) architecture. Our experimental results demonstrate that the new techniques are competitive with previous techniques and can scale much better on certain classes of problems.
Introduction
Satisfiability Modulo Theories (SMT) solvers are critical tools in formal verification, used to prove the correctness of software and hardware systems. In these domains, finite sets are ubiquitous, serving as natural abstractions for memory, data structures, and mathematical properties. However, reasoning about the size of these sets—known as cardinality constraints—has historically been a performance bottleneck.
This paper introduces a highly efficient method for SMT solvers to reason about finite sets and their sizes. By replacing the traditional approach of pre-calculating every possible set overlap with a "lazy," graph-based calculus, the authors avoid exponential performance collapses and enable solvers to handle complex set constraints instantaneously.
The Challenge of Cardinality
The core challenge in set reasoning is that sets overlap. To reason about the size of a union ($|A \cup B|$), a solver must account for the size of the intersection ($|A \cap B|$). Previous methods, such as those based on Boolean Algebra and Presburger Arithmetic (BAPA), typically reduced the problem to arithmetic by considering every possible Venn region.
This leads to what the authors call an "Exponential Nightmare." If a formula involves $n$ sets, there are $2^n$ possible Venn regions. A problem with just 20 sets could require a solver to track over a million variables. This makes traditional methods non-incremental and often impractical for real-world program analysis where the number of sets can be significant.
A Graph-Based Calculus
The authors propose a new calculus designed to be integrated into the standard DPLL(T) architecture used by modern SMT solvers like CVC4. Their approach moves away from the static generation of Venn regions toward a dynamic, incremental model.
Modular Reasoning
The logic is separated into two distinct procedures:
- Membership Reasoning: Handles constraints like "is element $x$ in set $S$?"
- Cardinality Reasoning: Handles constraints like "how big is set $S$?"
From Venn Regions to Graphs
Traditional decomposition into Venn regions (as shown in Figure 4) is replaced by a directed graph in the new calculus.
In the proposed system, the solver uses a graph to track set interactions lazily. Nodes represent sets, and edges represent "disjoint union" relationships.
Instead of generating all $2^n$ regions upfront, the solver only introduces new "overlap" regions (nodes in the graph) when they are strictly necessary to satisfy the constraints. For example, if the formula never mentions the intersection of Set A and Set C, the solver never bothers to calculate it.
Incremental Refinement and Merge Rules
The solver continuously refines the graph. When it learns that two sets are equal ($A = B$), it triggers specific graph rules to synchronize their leaf nodes. This ensures the underlying arithmetic solver receives a consistent and minimal view of the set sizes.
Experimental Evaluation
The researchers evaluated their implementation in the CVC4 solver using two primary sources of benchmarks: the Jahob Benchmarks (single-query problems from pointer-based data structure verification) and the Leon Benchmarks (incremental, multiple-query problems from Scala verification).
Key Results
- Scalability: The new procedure handles "pathological" cases that previously caused timeouts. In one test case involving a single constraint with 21 sets ($x \in A_1 \cup \dots \cup A_{21}$), previous state-of-the-art solvers ran out of memory or timed out after 85 seconds. The new CVC4 implementation solved it instantaneously.
- Competitive Performance: On standard benchmarks, the tool showed performance comparable to or better than specialized BAPA solvers, while being fully integrated into a general-purpose SMT solver.
- Robustness: Because the method is incremental, it performs much better in the context of larger verification workflows where the solver is asked many related questions in a row.
Conclusion and Future Work
The most significant contribution of this work is the realization that most Venn regions are irrelevant to the satisfiability of a specific formula. By tracking only "relevant" terms and their interactions in a graph, the search space is pruned significantly. While the current calculus is limited to finite sets and requires a "flat form" preprocessing step, it represents a major step forward in SMT efficiency.
Summary updated