Efficient Implementation of an Abstract Domain of Quantified First-Order Formulas

Recent years have seen significant progress in automated verification based on first-order logic. In particular, quantified first-order formulas have been used to model many systems, their properties and their inductive invariants [1, 6, 9,10,11, 13,14,15,16,17,18, 20, 22, 24, 26, 28, 30, 31]. Automatic verification in this domain is challenging because of the combination of the complexity of first-order reasoning performed by solvers and the enormous search space of formulas, especially due to the use of quantifiers. Despite these challenges, there are impressive success stories of automatically inferring quantified inductive invariants for complex distributed and concurrent algorithms [9,10,11, 14, 15, 17, 26, 30, 31].

Previous works on invariant inference for first-order logic search for invariants in the form of sets of formulas (interpreted conjunctively) from some language of quantified first-order formulas. Each approach fixes some restricted, typically finite (but extremely large) language \(\mathcal {L}\), and searches for a set of \(\mathcal {L}\)-formulas that form an inductive invariant using sophisticated heuristics and algorithmic techniques, such as property-directed reachability (IC3) [14, 15], incremental induction [11, 26], generalization from finite instances [9, 17], and clever forms of pruning and exploration [30, 31]. While prior techniques can successfully handle some challenging examples, the accumulation of specially-tailored techniques makes the results computed by these techniques unpredictable, and makes it hard to extend or improve them.

Abstract interpretation [4, 5] suggests a more systematic approach for the development of verification algorithms based on logical languages, where we consider sets of \(\mathcal {L}\)-formulas as elements in an abstract domain. The abstraction of a set of states S in this domain is given by \(\alpha (S) = \{ \varphi \in \mathcal {L}\mid \forall s\in S.\ s\models \varphi \}\), i.e., the formulas that are satisfied by all states in the set. Algorithms based on abstract interpretation are better understood and are easier to combine, extend, and improve. However, an abstract domain of quantified first-order formulas seems infeasible: for interesting systems, the abstract elements involved in proofs would contain an astronomical number of formulas.

The main contribution of this work is to develop algorithms and data structures that make an abstract domain based on quantified first-order formulas feasible. Working with this abstract domain introduces two main challenges: (i) efficiently storing and manipulating abstract elements comprising of many formulas, and (ii) overcoming solver limitations when reasoning over them. This work focuses on the first challenge and adopts ideas from prior work [15] to deal with the second. Our techniques lay a practical foundation for using an abstract interpretation approach to develop new analyses in the domain of quantified first-order formulas. We demonstrate feasibility of the abstract domain by applying it to an analysis of several intricate distributed protocols.

Our first key idea is to design a subsumption relation for quantified first-order formulas and use it to represent abstract elements (sets of formulas) more compactly, pruning away some formulas that are redundant since they are equivalent to or are entailed by another formula. Subsumption over propositional clauses (disjunctions of literals) is traditionally used for similar pruning purposes (e.g., [19]), but the generalization to first-order formulas, which include disjunction, conjunction, and quantification, is novel.

The second key ingredient of our approach is a way to manipulate abstract elements in our representation. Rather than implementing the standard operations of \(\alpha \) (abstraction) and \(\sqcup \) (abstract join), we observe that our subsumption-based representation makes it more natural to directly implement an operation that computes the join of an abstract element a with the abstraction of a given concrete state \(s\), i.e., \(a \sqcup \alpha (\{s\})\). This operation can be used to compute the abstraction of a set of states, and can also be used to compute the least fixpoint of the best abstract transformer (in the style of symbolic abstraction [27]). The crux of computing \(a \sqcup \alpha (\{s\})\) is to weaken the formulas in the representation of a to formulas that are subsumed by them and that \(s\) satisfies.

Finally, the third key ingredient of our approach is a data structure for storing a set of formulas, with efficient filters for (i) formulas that a given state does not satisfy, and (ii) formulas that subsume a given formula. This data structure is then used to store abstract elements, and the filters make the implementation of \(a \sqcup \alpha (\{s\})\) more efficient.

While the paper presents the ingredients of our approach (subsumption, weakening, and the data structure) sequentially, they are interconnected; they all affect each other in subtle ways, and must be designed and understood together. Specifically, there is an intricate tradeoff between the precision of subsumption, which determines the extent of pruning (and therefore the compactness of the representation), and the complexity of abstract domain operations such as weakening (e.g., for computing \(a \sqcup \alpha (\{s\})\)). The definitions, algorithms, and data structures we present are carefully crafted to balance these considerations. Our subsumption relation, which approximates entailment, is cheap to compute, eliminates enough redundancy to keep the representation of abstract elements compact, and enables an efficient implementation of the weakening operation.

To evaluate our implementation of the abstract domain, we use it to implement a symbolic abstraction [27] procedure that computes the least fixpoint of the best abstract transformer of a transition system (i.e., the strongest inductive invariant for the transition system in the given language). Our evaluation uses benchmarks from the literature, mostly from safety verification of distributed protocols. While our fixpoint computation algorithm is not fully competitive with property-directed invariant inference approaches that exploit various sophisticated heuristics and optimizations, it does demonstrate that fixpoint computation in our abstract domain is feasible, which is quite surprising given the amount of quantified formulas the domain considers. Our approach successfully computes the least fixpoint for transition systems that previously could only be analyzed using property-directed, heuristic techniques (which do not compute the least fixpoint, but an unpredictable heuristic fixpoint). For example, we succeed at finding the strongest inductive invariant of Paxos as modeled in [24] (which in our representation has 1,438 formulas with \(\forall ^*\exists ^*\forall ^*\) quantification, representing orders of magnitude more subsumed formulas).

In summary, this paper makes the following contributions:

1. 1.

   We develop a compact representation of sets of formulas based on a novel syntactic subsumption relation. We make a tradeoff here between the extent of pruning and efficiency, accepting some redundant formulas in exchange for practical algorithms. (Sect. 3)

2. 2.

   We show how to implement a key operation of weakening a formula to be satisfied by a given state, and leverage it to compute the join of an abstract element and the abstraction of a state, when abstract elements are represented using our subsumption-based representation. (Sect. 4)

3. 3.

   We present a data structure that provides an efficient implementation of operations used in the join computation described above. (Sect. 5)

4. 4.

   We evaluate the approach by applying it to compute the least fixpoint of the best abstract transformer for several distributed and concurrent protocols from the literature, demonstrating the promise of our approach. (Sect. 6)

The rest of this paper is organized as follows: Sect. 2 introduces definitions and notation, Sects. 3 to 6 present the main contributions outlined above, Sect. 7 discusses related work, and Sect. 8 concludes. The proofs of all theorems stated in the paper are given in [8].

First-Order Logic. For simplicity of the presentation, we present our approach for single-sorted first-order logic, although in practice we consider many-sorted logic. The generalization of our methods to many-sorted logic is straightforward.

Given a first-order signature \(\varSigma \) that consists of constant, function and relation symbols, the sets of terms and formulas are defined in the usual way: a term t is either a variable x, a constant c or a function application \(f(t_1,\ldots ,t_n)\) on simpler terms; a formula is either an equality between terms \(t_1 = t_2\), a relation application \(r(t_1,\ldots ,t_n)\) on terms, or the result of applying Boolean connectives or quantification. We also include \(\bot \) as a formula (that is never satisfied).

Terms and formulas are interpreted over first-order structures and assignments to the (free) variables. Given a first-order signature \(\varSigma \), a structure \(\sigma =(\mathcal {U},\mathcal {I})\) consists of a universe \(\mathcal {U}\) and an interpretation \(\mathcal {I}\) to the symbols in \(\varSigma \). We denote by \(\textbf{structs}[{\varSigma }]\) the set of structures of \(\varSigma \) whose universe is a finite set.^{Footnote 1} When considering formulas with free variables \(V\), and given some structure \(\sigma =(\mathcal {U},\mathcal {I})\), an assignment \(\mu : V\rightarrow \mathcal {U}\) maps each variable to an element of the structure’s universe. We write \((\sigma ,\mu )\models \varphi \) to mean that a structure \(\sigma \) with an assignment \(\mu \) satisfies a formula \(\varphi \), and \(\psi \models \varphi \) to mean that a formula \(\psi \) semantically entails \(\varphi \), i.e., \((\sigma ,\mu )\models \psi \) whenever \((\sigma ,\mu )\models \varphi \).

Abstract Interpretation. Abstract interpretation [4, 5] is a framework for approximating the semantics of systems. It assumes a concrete domain and an abstract domain, each given by a partially ordered set, \((\mathcal {C}, \sqsubseteq _\mathcal {C})\) and \((\mathcal {A}, \sqsubseteq _\mathcal {A})\), respectively. These are related via a Galois connection consisting of a monotone abstraction function \(\alpha : \mathcal {C}\rightarrow \mathcal {A}\) and a monotone concretization function \(\gamma : \mathcal {A}\rightarrow \mathcal {C}\) satisfying \(\alpha (c)\sqsubseteq _\mathcal {A}a \iff c\sqsubseteq _\mathcal {C}\gamma (a)\) for all \(a\in \mathcal {A}\) and \(c\in \mathcal {C}\).

In this work we consider logical abstract domains parameterized by a finite first-order language \(\mathcal {L}\) of closed formulas over signature \(\varSigma \). In this context, concrete elements are sets of states from \(\mathbb {S}= \textbf{structs}[{\varSigma }]\),^{Footnote 2} i.e., \(\mathcal {C}={\mathcal {P}(\mathbb {S})}\), ordered by \(\sqsubseteq _\mathcal {C}=\subseteq \) (set inclusion). Abstract elements are sets of formulas from \(\mathcal {L}\), i.e., \(\mathcal {A}={\mathcal {P}(\mathcal {L})}\), ordered by \(\sqsubseteq _\mathcal {A}=\supseteq \), and the Galois connection is given by \(\alpha (S) = \{\varphi \in \mathcal {L}\mid \forall s\in \mathbb {S}.\ s\models \varphi \}\) and \(\gamma (F) = \{s\in \mathbb {S}\mid \forall \varphi \in F.\ s\models \varphi \}\). That is, abstraction in this domain consists of all \(\mathcal {L}\)-formulas that hold on a given concrete set, and concretization consists of all states that satisfy a given set of formulas. Note that sets of formulas are interpreted conjunctively in this context.

This logical abstract domain forms a join-semilattice (meaning every two elements have a least upper bound) with a least element. The least element, denoted \(\bot _\mathcal {A}\) (not to be confused with the formula \(\bot \)), is \(\mathcal {L}\), and join, denoted \(\sqcup \), corresponds to set intersection. For example, \(F \sqcup \alpha (\{s\}) = F \cap \{\varphi \in \mathcal {L}\mid s\models \varphi \} = \{\varphi \in F \mid s\models \varphi \}\), and can be understood as weakening F by eliminating from it all formulas that are not satisfied by \(s\).

In this section we develop an efficient representation for elements in the abstract domain \(\mathcal {A}= {\mathcal {P}(\mathcal {L})}\) induced by a finite first-order language \(\mathcal {L}\). The abstract elements are sets of formulas, interpreted conjunctively, which may be extremely large (albeit finite). Our idea is to reduce the size and complexity of such sets by avoiding redundancies that result from semantic equivalence and entailment. For example, when representing a set of formulas we would like to avoid storing both \(\varphi \) and \(\psi \) when they are semantically equivalent (\(\varphi \equiv \psi \)). Similarly, if \(\varphi \models \psi \) then instead of keeping both \(\varphi \) and \(\psi \) we would like to keep only \(\varphi \).

In practice, it is not possible to remove all such redundancies based on semantic equivalence and entailment, since, as we shall see in Sect. 4, performing operations over the reduced representation of abstract elements involves recovering certain subsumed formulas, and finding these in the case of entailment essentially requires checking all formulas in the language. This is clearly infeasible for complex languages such as the ones used in our benchmarks (see Table 1), and is exacerbated by the fact that merely checking entailment is expensive for formulas with quantifiers. Instead, our key idea is to remove redundancies based on a cheap-to-compute subsumption relation, which approximates semantic entailment, and enables efficient operations over abstract elements such as joining them with an abstraction of a concrete state.

We start the section with an inductive definition of a family of finite first-order languages that underlies all of our developments (Sect. 3.1). We then introduce a syntactic subsumption relation for first-order formulas (Sect. 3.2), which we leverage to develop an efficient canonicalization of formulas, effectively determining a single representative formula for each subsumption-equivalence class (Sect. 3.3). We then use antichains of canonical formulas, i.e., sets of canonical formulas where no formula is subsumed by another, to represent sets of formulas (Sect. 3.4). Sects. 4 and 5 develop ways to effectively manipulate this representation in order to accommodate important operations for abstract interpretation algorithms, such as weakening an abstraction to include a given concrete state.

3.1 Bounded First-Order Languages

At core of our approach is an inductively-defined family of first-order languages, termed bounded first-order languages. These languages are all finite and bound various syntactic measures of formulas (e.g., number of quantifiers, size of the Boolean structure), which, in turn, determine the precision of the abstract domain. The inductive definition of bounded languages facilitates efficient recursive implementations of our developments.

We fix a signature \(\varSigma \) and a variable set \(V\). Definition 1 provides the inductive definition of the family of bounded first-order languages (over \(\varSigma \) and V), where each language \(\mathcal {L}\) is also equipped with a bottom element \(\bot _\mathcal {L}\) (equivalent to false). We use \(\mathfrak {S}_X\) to denote the set of permutations over a set of variables X, and use \(\varphi \pi \) to denote the formula obtained by substituting free variables in a formula \(\varphi \) according to \(\pi \in \mathfrak {S}_X\). A set of formulas F is \(\mathfrak {S}_X\)-closed if \(\varphi \pi \in F\) for every \(\varphi \in F\), \(\pi \in \mathfrak {S}_X\). All bounded first-order languages will be \(\mathfrak {S}_V\)-closed; this will be important for canonicalization. We use \(\bar{\varphi }= \langle {\varphi _1, \ldots , \varphi _n}\rangle \) to denote a sequence of formulas, \(\varphi _{-i}\) to denote the formula \(\varphi _{n-i+1}\) in the sequence, \({|{\bar{\varphi }}|}\) for the length of \(\bar{\varphi }\), and \([{\bar{\varphi }}]\) for its set of indices \(\{1,\dots ,|\bar{\varphi }|\}\). We use \(\mathcal {L}^*\) for the set of all (finite) sequences of formulas from \(\mathcal {L}\), and \(\epsilon \) for the empty sequence (\({|{\epsilon }|}=0\)).

Definition 1

(Bounded First-Order Languages). A bounded first-order language is one of the following, where \(X \subseteq V\) denotes a finite set of variables, and \(\mathcal {L}\), \(\mathcal {L}_1\) and \(\mathcal {L}_2\) denote bounded first-order languages:

The base case is any finite set of formulas (over \(\varSigma \) and V) that is closed under variable permutations, augmented by \(\bot \) (denoting false). Typical examples include the set of all literals over \(\varSigma \) and V with a bounded depth of function applications. We introduce binary language constructors for disjunction and conjunction, each operating on two possibly different languages. We also introduce constructors for homogeneous disjunction of at most k disjuncts, as well as unbounded non-empty conjunction, over any single language. Finally, we introduce constructors for quantification (\(\exists \) or \(\forall \)) over a finite set of variables and a language, as well as a constructor that includes both quantifiers for languages where both options are desired. Note that for the construction of a logical abstract domain, we are interested in languages where all formulas are closed (have no free variables), but the inductive definition includes languages with free variables.

The semantics of formulas in each language is defined w.r.t. states \(\mathbb {S}\) that consist of first-order structures and assignments to the free variables, following the standard first-order semantics, extended to conjunctions and disjunctions of finite sequences in the natural way, where \(\bigvee \epsilon \equiv \bot \). (We do not allow \(\bigwedge \epsilon \), which would have been equivalent to “true”, since it is not useful for our developments.)

Observe that for a fixed language \(\mathcal {L}\), the formulas \(\varphi _1\vee \varphi _2 \in {{\boldsymbol{\vee }}[{\mathcal {L}}, {\mathcal {L}}]}\) and \(\bigvee \langle {\varphi _1,\varphi _2}\rangle \in {{\boldsymbol{\vee }}_{2}[{\mathcal {L}}]}\) are syntactically different but semantically equivalent (and similarly for conjunctions). Nonetheless, we introduce homogeneous disjunction and conjunction since they admit a more precise subsumption relation, yielding a more efficient representation of sets of formulas. Also note that we consider bounded disjunction but unbounded conjunction; Sect. 4.3 explains this choice.

Example 1

\(\mathcal {L}= {{\boldsymbol{\forall }}_{\{x,y\}}[{{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}}]}\) with \(A = \{ p(x),\lnot p(x), p(y),\lnot p(y) \}\) is a bounded first-order language over signature \(\varSigma \) that has one unary predicate p and variables \(V=\{x,y\}\). Formulas in this language are universally quantified homogeneous disjunctions of at most two literals. For instance, \(\mathcal {L}\) includes \(\forall \{x,y\}.\bigvee \epsilon \), which is also \(\bot _\mathcal {L}\), as well as \(\forall \{x,y\}.\bigvee \langle {p(x)}\rangle \), \(\forall \{x,y\}.\bigvee \langle {p(x), \lnot p(y)}\rangle \), etc.

3.2 Syntactic Subsumption

Next, we define a subsumption relation for each bounded first-order language. The subsumption relation serves as an easy-to-compute under-approximation for entailment between formulas from the same language. We use \(\sqsubseteq _\mathcal {L}\) to denote the subsumption relation for language \(\mathcal {L}\), or simply \(\sqsubseteq \) when \(\mathcal {L}\) is clear from context. When \(\varphi \sqsubseteq \psi \) we say \(\varphi \) subsumes \(\psi \), and then we will also have \(\varphi \models \psi \).

Definition 2

(Subsumption). We define \(\sqsubseteq _\mathcal {L}\) inductively, following the definition of bounded first-order languages, as follows, where \(\circ \in \{\vee , \wedge \}\), \(k\in \mathbb {N}\), \(Q, Q' \in \{\exists , \forall \}\), X is a finite set of variables, and \(\mathcal {L}\), \(\mathcal {L}_1\) and \(\mathcal {L}_2\) are bounded first-order languages:

The subsumption relation of a bounded first-order language \(\mathcal {L}\) is composed, hierarchically, from the subsumption relations of the bounded first-order languages that \(\mathcal {L}\) is composed from. For example, the languages participating in the composition of \(\mathcal {L}= {{\boldsymbol{\forall }}_{\{x,y\}}[{{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}}]}\) defined in Example 1 are \(\mathcal {L}_A\), \({{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}\), and \({{\boldsymbol{\forall }}_{\{x,y\}}[{{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}}]}\), and each is equipped with its own subsumption relation.

In the base case, formulas in \({\mathcal {L}_{A}}\) are only subsumed by themselves or by \(\bot \). For example, considering Example 1, \(p(x)\not \sqsubseteq _{\mathcal {L}_A} p(y)\). Subsumption is lifted to languages obtained by binary conjunctions and disjunctions in a pointwise manner. For the languages obtained by homogeneous constructors, a mapping over indices determines which element of one sequence subsumes which element of the other. To approximate entailment, the mapping in the disjunctive case maps each element of \(\bigvee \bar{\varphi }\) to one in \(\bigvee \bar{\psi }\) that it subsumes, and in the conjunctive case maps each element of \(\bigwedge \bar{\psi }\) to one in \(\bigwedge \bar{\varphi }\) that subsumes it. As a result, subsumption is more precise in the homogeneous case than in the binary one. For example, considering A from Example 1, \(p(x) \vee p(y) \not \sqsubseteq _{{{\boldsymbol{\vee }}[{\mathcal {L}_A}, {\mathcal {L}_A}]}} p(y) \vee p(x)\), even though the formulas are semantically equivalent. On the other hand, \(\bigvee \langle {p(x), p(y)}\rangle \sqsubseteq _{{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}} \bigvee \langle {p(y), p(x)}\rangle \)

In the case of quantifiers, subsumption is lifted from the language of the body while considering permutations over the quantified variables. For example, in Example 1, \(\forall \{x,y\}.\bigvee \langle {p(x)}\rangle \sqsubseteq _{\mathcal {L}} \forall \{x,y\}.\bigvee \langle {p(y)}\rangle \) due to variable permutations, even though \(\bigvee \langle {p(x)}\rangle \not \sqsubseteq _{{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}} \bigvee \langle {p(y)}\rangle \). When both quantifiers are considered, a universal quantifier can subsume an existential one.

The injectivity requirement for \(\sqsubseteq _{{{\boldsymbol{\vee }}_{k}[{\mathcal {L}}]}}\) can be dropped without damaging any of the definitions or theorems in this section, but it enables a simpler definition of the weakening operator in Sect. 4 (as discussed further in Sect. 4.3).

The following theorem establishes the properties of \(\sqsubseteq _\mathcal {L}\).

Theorem 1

(Properties of \(\sqsubseteq _\mathcal {L}\)). For any bounded first-order language \(\mathcal {L}\), \(\sqsubseteq _\mathcal {L}\) is a preorder (i.e., reflexive and transitive) such that for any \(\varphi ,\psi \in \mathcal {L}\), if \(\varphi \sqsubseteq \psi \) then \(\varphi \models \psi \). Moreover, \(\bot _\mathcal {L}\sqsubseteq _\mathcal {L}\varphi \) for any \(\varphi \in \mathcal {L}\).

As with entailment, where two distinct formulas can entail each other (i.e., be semantically equivalent), there can be distinct formulas \(\varphi ,\psi \in \mathcal {L}\) with \(\varphi \sqsubseteq _\mathcal {L}\psi \) and \(\psi \sqsubseteq _\mathcal {L}\varphi \) (since \(\sqsubseteq _\mathcal {L}\) is not always a partial order, i.e., not antisymmetric). We call such formulas subsumption-equivalent, and denote this by \(\varphi \equiv _{\sqsubseteq _\mathcal {L}} \psi \). (\(\equiv _{\sqsubseteq _\mathcal {L}}\) is clearly an equivalence relation.) The existence of subsumption-equivalent formulas is a positive sign, indicating that our subsumption relation manages to capture nontrivial semantic equivalences. This is thanks to the definition of subsumption for homogeneous disjunction and conjunction, as well as for quantification. For example, \(\bigvee \langle {\varphi ,\psi }\rangle \equiv _\sqsubseteq \bigvee \langle {\psi ,\varphi }\rangle \) (and similarly for conjunction), and if \(\varphi \sqsubseteq \psi \) then \(\bigwedge \langle {\varphi , \psi }\rangle \equiv _\sqsubseteq \bigwedge \langle {\varphi }\rangle \). For quantifiers, \(QX. \varphi \equiv _\sqsubseteq QX. \varphi \pi \) for any \(\pi \in \mathfrak {S}_X\) and \(Q\in \{\exists , \forall \}\). (In contrast, \(\sqsubseteq _{\mathcal {L}_{A}}\) is always antisymmetric, and the definitions of \({{\boldsymbol{\vee }}[{\mathcal {L}_1}, {\mathcal {L}_2}]}\) and \({{\boldsymbol{\wedge }}[{\mathcal {L}_1}, {\mathcal {L}_2}]}\) preserve antisymmetry.)

3.3 Canonicalization

As a first step towards an efficient representation of sets of formulas, we use a canonicalization of formulas w.r.t. \(\equiv _\sqsubseteq \), which allows us to only store canonical formulas as unique representatives of their (subsumption-) equivalence class. In general, a canonicalization w.r.t. an equivalence relation \(\equiv \) over a set S is a function \(c:S \rightarrow S\) such that \(\forall x \in S.\, c(x) \equiv x\) (representativeness) and \(\forall x,y \in S.\, x \equiv y \iff c(x) = c(y)\) (decisiveness). We say that x is canonical if \(c(x) = x\). When the equivalence relation is derived from a preorder (as \(\equiv _\sqsubseteq \) is derived from \(\sqsubseteq \)) then the preorder is a partial order over the set of canonical elements. For our case, that means that \(\sqsubseteq _\mathcal {L}\) is a partial order over the set of canonical \(\mathcal {L}\)-formulas.

It is useful, both for the algorithms developed in the sequel and for the definition of canonicalization for \({Q_{X}[{\mathcal {L}}]}\) (\(Q \in \{\boldsymbol{\exists }, \boldsymbol{\forall }, {\exists }\!{\forall }\}\)), to define a total order \(\le _\mathcal {L}\) over canonical \(\mathcal {L}\)-formulas that extends \(\sqsubseteq _\mathcal {L}\). We thus define the canonicalization function \(c_\mathcal {L}\) and the total order \(\le _\mathcal {L}\) over canonical \(\mathcal {L}\)-formulas by mutual induction. For a set of canonical \(\mathcal {L}\)-formulas F, we use \(\min _{\sqsubseteq _\mathcal {L}} F\) to denote the set of formulas in F not subsumed by others, i.e., \(\min _{\sqsubseteq _\mathcal {L}} F = \{\varphi \in F \mid \forall \psi \in F \setminus \{\varphi \}. \, \psi \not \sqsubseteq \varphi \}\), and use \(\min _{\le _\mathcal {L}} F\) to denote the minimal element of a non-empty set F w.r.t. the total order \(\le _\mathcal {L}\). Finally, we use \({{\langle {\bar{\varphi }}\rangle }_{\le }}\) for the sequence obtained by sorting \(\bar{\varphi }\) according to \(\le \) in ascending order, and similarly \({{\langle {F}\rangle }_{\le }}\) for the sequence obtained by sorting the elements of a set F.

Definition 3

(Canonicalization). For every bounded first-order language \(\mathcal {L}\), we define the canonicalization function \(c_\mathcal {L}:\mathcal {L}\rightarrow \mathcal {L}\) and a total order \(\le _\mathcal {L}\) over canonical \(\mathcal {L}\)-formulas by mutual induction (where \(\circ \in \{\vee , \wedge \}\) and \(Q\in \{\exists , \forall \}\)):

and

where \(\varphi <_\mathcal {L}\psi \) is shorthand for “\(\varphi \le _\mathcal {L}\psi \) and \(\varphi \ne \psi \)”.

Our inductive definition of canonicalization in Definition 3 recognizes the only possible sources of nontrivial subsumption-equivalence in our construction: non-canonicity of subformulas, ordering of sequences, internal subsumption in \({{\boldsymbol{\wedge }}_{\omega }[{\cdot }]}\)-sequences, and permuting of quantified variables. To address these, we canonicalize all subformulas, order their sequences w.r.t \(\le _\mathcal {L}\) in \({{\boldsymbol{\vee }}_{k}[{\mathcal {L}}]}\) and \({{\boldsymbol{\wedge }}_{\omega }[{\mathcal {L}}]}\), minimize \({{\boldsymbol{\wedge }}_{\omega }[{\mathcal {L}}]}\)-sequences w.r.t \(\sqsubseteq _\mathcal {L}\), and in \({Q_{X}[{\mathcal {L}}]}\), \(Q\in \{\boldsymbol{\exists },\boldsymbol{\forall },{\exists }\!{\forall }\}\), choose the permutation yielding the \(\le _\mathcal {L}\)-least (canonical) body. For the total order in the cases of Boolean connectives, we use lexicographic-like orderings carefully designed to extend their associated subsumption relations (e.g., homogeneous disjunction uses a right-to-left lexicographic ordering). For quantification, the total order is directly lifted from the total order for canonical bodies.

As an example, consider \(\mathcal {L}= {{\boldsymbol{\forall }}_{\{x,y\}}[{{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}}]}\) from Example 1. To obtain a canonicalization for \(\mathcal {L}\), we provide an arbitrary total order \(\le _{\mathcal {L}_A}\), say \(p(x) <_{\mathcal {L}_A} \lnot p(x) <_{\mathcal {L}_A} p(y) <_{\mathcal {L}_A} \lnot p(y)\) (recall that \(\bot \in \mathcal {L}_A\) is least). This uniquely determines the total order and canonicalization of \(\mathcal {L}\) and all of its sub-languages. For example, canonicalization of both \(\forall \{x,y\}.\bigvee \langle {p(x)}\rangle \) and \(\forall \{x,y\}.\bigvee \langle {p(y)}\rangle \), which are \(\sqsubseteq _\mathcal {L}\)-equivalent, is \(\forall \{x,y\}.\bigvee \langle {p(x)}\rangle \). This is because \(p(x)<_{\mathcal {L}_A}p(y)\), and thus \(c_{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}\left( \bigvee \langle {p(x)}\rangle \right) = \bigvee \langle {p(x)}\rangle <_{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]} \bigvee \langle {p(y)}\rangle = c_{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}\left( \bigvee \langle {p(y)}\rangle \right) \). Note that \(\bigvee \langle {p(x)}\rangle \) and \(\bigvee \langle {p(y)}\rangle \) are both canonical, but adding quantifiers merges the two formulas into the same subsumption-equivalence class, necessarily making the quantified version of one of them non-canonical. Similarly, the \(\sqsubseteq _{{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}}\)-equivalent formulas \(\bigvee \langle {p(x),p(y)}\rangle \) and \(\bigvee \langle {p(y),p(x)}\rangle \) are both canonicalized into \(\bigvee \langle {p(x),p(y)}\rangle \) (by sorting the sequences of literals according to \(\le _{\mathcal {L}_A}\)).

The properties of \(c_\mathcal {L}\) and \(\le _\mathcal {L}\) defined above are established by the following theorem, which ensures that Definition 3 is well-defined (e.g., that whenever \(\min _{\le _\mathcal {L}}\) is used, \(\le _\mathcal {L}\) is a total order).

Theorem 2

For any bounded language \(\mathcal {L}\), \(c_\mathcal {L}\) is a canonicalization w.r.t. \(\equiv _{\sqsubseteq _\mathcal {L}}\), that is, it is representative (\(c_\mathcal {L}(\varphi ) \equiv _{\sqsubseteq _\mathcal {L}} \varphi \)) and decisive (\(\varphi \equiv _{\sqsubseteq _\mathcal {L}} \psi \iff c_\mathcal {L}(\varphi ) = c_\mathcal {L}(\psi )\)); \(\sqsubseteq _\mathcal {L}\) is a partial order over canonical \(\mathcal {L}\)-formulas; and \(\le _\mathcal {L}\) is a total order over canonical \(\mathcal {L}\)-formulas that extends \(\sqsubseteq _\mathcal {L}\).

Corollary 1

For any \(\varphi ,\psi \in \mathcal {L}\), if \(\varphi \sqsubseteq _\mathcal {L}\psi \) then \(c_\mathcal {L}(\varphi ) \le _\mathcal {L}c_\mathcal {L}(\psi )\).

Henceforth, we use \({\boldsymbol{\mathcal {L}}}\) to denote the set of canonical \(\mathcal {L}\)-formulas.

3.4 Representing Sets of Formulas

We utilize the subsumption relation and canonicalization to efficiently represent sets of formulas which are interpreted conjunctively as antichains of canonical formulas, where an antichain is a set of formulas incomparable by subsumption.

Definition 4

(Set Representation). Given a set of formulas \(F \subseteq \mathcal {L}\), we define its representation as the set \(R_F = \mathop {\min {}}\nolimits _{\sqsubseteq _{\mathcal {L}}} \{c(\varphi ) \mid \varphi \in F\}\).

The representation combines two forms of redundancy elimination: the use of canonical formulas eliminates redundancies due to subsumption-equivalence, and the use of \(\sqsubseteq _{\mathcal {L}}\)-minimal elements reduces the size of the set by ignoring subsumed formulas. Observe that the more permissive the subsumption relation is, the smaller the set representations are, because more formulas will belong to the same equivalence class and more formulas will be dropped by \(\min _{\sqsubseteq _\mathcal {L}}\).

This representation preserves the semantics of a set of formulas (interpreted conjunctively). For sets that are upward-closed w.r.t. subsumption (e.g., \(\alpha (S)\) for some set of states S), the representation is lossless as a set can be recovered by taking the upward closure of its representation. For a set \(F \subseteq \mathcal {L}\), we use \({\uparrow }{F}\) to denote its upward closure (w.r.t. \(\sqsubseteq _\mathcal {L}\)), given by \({\uparrow }{F} = \{\varphi \in \mathcal {L}\mid \exists \psi \in F. \, \psi \sqsubseteq _\mathcal {L}\varphi \}\).

Theorem 3

(Antichain Representation). For \(F \subseteq \mathcal {L}\) and \(R_F = \mathop {\min {}}\nolimits _{\sqsubseteq _{\mathcal {L}}} \{c(\varphi ) \mid \varphi \in F\}\) its representation, \(\bigwedge R_F \equiv \bigwedge F\) and \({\uparrow }{R_F} = {\uparrow }{F}\).

Corollary 2

If \(F \subseteq \mathcal {L}\) is upward closed w.r.t. \(\sqsubseteq _\mathcal {L}\) then \(F = {\uparrow }{R_F}\).

In particular, Corollary 2 applies to any set that is closed under entailment.

This section develops an algorithm that computes a weaken operator, which takes a representation of an upward-closed set \(F\subseteq \mathcal {L}\) and a state s and computes a representation of \(F \cap \alpha (\{s\}) = \{\varphi \in F \mid s\models \varphi \}\). When F is viewed as an abstract element, this operation corresponds to computing \(F \sqcup \alpha (\{s\})\). While it is not a general abstract join operator, joining an abstract element with the abstraction of a single concrete state is a powerful building block that can be used, for example, to compute the abstraction of a set of states or even the least fixpoint of the best abstract transformer (á la symbolic abstraction [27]).

In an explicit representation of F, computing \(F \sqcup \alpha (\{s\})\) would amount to removing from F all the formulas that are not satisfied by \(s\). However, in the subsumption-based representation \(R_F\), simply removing said formulas is not enough. Instead, we must weaken them, i.e., replace them by formulas they subsume that are satisfied by \(s\). To this end, Sect. 4.1 develops an appropriate weakening operator for a single formula, and Sect. 4.2 then lifts it to antichains used as representations.

4.1 Weakening a Single Canonical Formula

Given a canonical formula \(\varphi \) and a state \(s\) such that \(s\not \models \varphi \), the weaken operator computes the set of minimal canonical formulas that are subsumed by \(\varphi \) and satisfied by \(s\), which can be understood as a representation of \({\uparrow }{\{\varphi \}}\cap \alpha (\{s\})\).

Definition 5

(The Weaken Operator). The weaken operator of \(\mathcal {L}\) is the function \(\mathcal {W}_\mathcal {L}:{\boldsymbol{\mathcal {L}}} \times \mathbb {S}\rightarrow {\mathcal {P}({\boldsymbol{\mathcal {L}}})}\) defined as follows:

Note that \({\mathcal {W}_{\mathcal {L}}\left( {\varphi },{s}\right) }\) returns a set of formulas, since there may be different incomparable ways to weaken \(\varphi \) such that it is satisfied by \(s\).

While Definition 5 does not suggest a way to compute \({\mathcal {W}_{\mathcal {L}}\left( {\varphi },{s}\right) }\), the following theorem provides a recursive implementation of \({\mathcal {W}_{\mathcal {L}}\left( {\varphi },{s}\right) }\) that follows the inductive structure of bounded languages. For the quantification cases, we weaken according to all assignments of variables in \(X \subseteq V\). Recall that a state can be unpacked as \(s= ((\mathcal {U},\mathcal {I}),\mu )\) where \((\mathcal {U},\mathcal {I})\) is a first-order structure (universe and interpretation) and \(\mu \) is an assignment to variables (into \(\mathcal {U}\)). For assignments \(\mu \) and \(\nu \), we use \({\mu }\overleftarrow{\cup }{\nu }\) to denote the assignment obtained from \(\mu \) by updating (possibly extending) it according to \(\nu \).

Theorem 4

(Implementation of Weaken). Let \(\varphi \in \mathcal {L}\) be a canonical formula in a bounded first-order language \(\mathcal {L}\) and \(s\in \mathbb {S}\) a state. If \(s\models \varphi \) then \({\mathcal {W}_{\mathcal {L}}\left( {\varphi },{s}\right) } = \{ \varphi \}\). If \(s\not \models \varphi \), then \({\mathcal {W}_{\mathcal {L}}\left( {\varphi },{s}\right) }\) is given by:

When \(s\models \varphi \), no weakening of \(\varphi \) is needed for \(s\) to satisfy it. In the case of \(\mathcal {L}_{A}\), only \(\bot \) can be weakened to make \(s\) satisfy it, yielding the set of formulas from \(A\) that are satisfied by \(s\). (For \(\mathcal {L}_{A}\), weakening anything except \(\bot \) that is not satisfied by \(s\) yields the empty set.) In the case of disjunction, it suffices for one of the disjuncts to be satisfied by \(s\). Therefore, weakening is done by (i) weakening exactly one of the existing disjuncts, which applies to both \({{\boldsymbol{\vee }}[{\mathcal {L}_1}, {\mathcal {L}_2}]}\) and \({{\boldsymbol{\vee }}_{k}[{\mathcal {L}}]}\); or by (ii) adding a disjunct that weakens \(\bot _{\mathcal {L}}\), which applies only to \(\bigvee \bar{\varphi }\in {{\boldsymbol{\vee }}_{k}[{\mathcal {L}}]}\) when \({|{\bar{\varphi }}|} < k\). In the case of homogeneous disjunction, each resulting disjunction needs to be sorted to restore canonicity; moreover, some of the resulting disjunctions may be subsumed by others, so \(\mathop {\min {}}\nolimits _{\sqsubseteq _{{{\boldsymbol{\vee }}_{k}[{\mathcal {L}}]}}}\) is applied to the set of weakened disjunctions. In the case of conjunction, all conjuncts need to be weakened to be satisfied by \(s\). In the binary case, this leads to all pairs that combine weakened conjuncts. But in the homogeneous case a single conjunction can accumulate all weakened conjuncts, so weakening always yields a singleton set; filtering the weakened conjuncts using \(\mathop {\min {}}\nolimits _{\sqsubseteq _\mathcal {L}}\) is required to ensure canonicity, as one weakened conjunct may subsume another. To satisfy an existentially quantified formula, it suffices for the body to be satisfied by a single assignment. Therefore, each possible assignment \(\nu \) contributes to the result of weakening. In contrast, for a universally quantified formula the body must be satisfied by all assignments. Therefore, the body of the formula is iteratively weakened by all assignments. In both cases, formulas are re-canonicalized and non-minimal elements are removed. The case of \({{\exists }\!{\forall }_{X}[{\mathcal {L}}]}\) combines the two quantified cases.

Example 2

Consider applying the weaken operator of \(\mathcal {L}= {{\boldsymbol{\forall }}_{\{x,y\}}[{{{\boldsymbol{\vee }}_{2}[{\mathcal {L}_A}]}}]}\) from Example 1 to the bottom element \(\bot _\mathcal {L}= \forall \{x,y\}.\bigvee \epsilon \), with the state \(s=((\mathcal {U},\mathcal {I}),\mu )\) where \(\mathcal {U}=\{a,b\}\), \(p^\mathcal {I}=\{a,b\}\), and \(\mu \) is an empty assignment. To weaken the universally quantified formula, we first iteratively weaken its body, \(\varphi _0=\bigvee \epsilon \), with the states \(s_1,\ldots ,s_4\), each of which extends s with one of the 4 possible assignments to x, y. Since all of these states satisfy p(x) and p(y), the first weakening (with \(s_1\)) results in \(\{\bigvee \langle {p(x)}\rangle , \bigvee \langle {p(y)}\rangle \}\), and no formula is weakened further in later iterations (since both of them are already satisfied by \(s_2,s_3,s_4\)). As we have seen in Sect. 3.3, both formulas are canonical; however, they become subsumption-equivalent when the quantifier prefix is added, demonstrating the need for additional canonicalization in the computation of weaken for \({{\boldsymbol{\forall }}_{X}[{\cdot }]}\). The result is the antichain of canonical formulas \(\{\forall \{x,y\}.\bigvee \langle {p(x)}\rangle \}\). Note that the weakened formula \(\bot _\mathcal {L}\) has 21 formulas in its \(\sqsubseteq _{\mathcal {L}}\)-upward closure, and its weakening has 14 formulas (see [8] for the lists of formulas); yet throughout the weakening process we only dealt with at most two formulas.

In-place Weaken for \(\text {LSet}[{\mathcal {L}}]\)

Full size image

4.2 Weakening Sets of Formulas

We lift the weaken operator to sets of canonical formulas. For a set \(R \subseteq {\boldsymbol{\mathcal {L}}}\), we define \({\mathcal {W}_{\mathcal {L}}\left( {R},{s}\right) } = \mathop {\min {}}\nolimits _\sqsubseteq \bigcup _{\varphi \in R} {\mathcal {W}_{\mathcal {L}}\left( {\varphi },{s}\right) }\), motivated by the following theorem.

Theorem 5

(From Weaken to Join). Let \(F \subseteq \mathcal {L}\) be upward-closed w.r.t. \(\sqsubseteq \), \(R_F\) its representation (\(R_F = \mathop {\min {}}\nolimits _\sqsubseteq \{c(\varphi ) \mid \varphi \in F\}\)), and \(s\) a state. The representation of \(F \sqcup \alpha (\{s\})\) is given by \({\mathcal {W}_{\mathcal {L}}\left( {R_F},{s}\right) } = \mathop {\min {}}\nolimits _\sqsubseteq \bigcup _{\varphi \in R_F} {\mathcal {W}_{\mathcal {L}}\left( {\varphi },{s}\right) }\).

Corollary 3

(Weaken for a Set of States). Let \(F \subseteq \mathcal {L}\) be upward-closed w.r.t. \(\sqsubseteq \), \(R_F\) its representation, and \(s_1,\ldots ,s_n\) states. The representation of \(F \sqcup \alpha (\{s_1,\ldots ,s_n\})\) is given by \({\mathcal {W}_{\mathcal {L}}\left( {{\mathcal {W}_{\mathcal {L}}\left( {\cdots {\mathcal {W}_{\mathcal {L}}\left( {{\mathcal {W}_{\mathcal {L}}\left( {R_F},{s_1}\right) }},{s_2}\right) }},{\cdots s_{n-1}}\right) }},{s_n}\right) }\).

Corollary 4

(Abstraction of a Set of States). The representation of \(\alpha (S)\) for a set of states S The representation of \(\alpha (\{s_1,\ldots ,s_n\})\) is given by \({\mathcal {W}_{\mathcal {L}}\left( {{\mathcal {W}_{\mathcal {L}}\left( {\cdots {\mathcal {W}_{\mathcal {L}}\left( {{\mathcal {W}_{\mathcal {L}}\left( {\{\bot _\mathcal {L}\}},{s_1}\right) }},{s_2}\right) }},{\cdots s_{n-1}}\right) }},{s_n}\right) }\).

Theorem 5 and Corollary 3 show that weakening of a single formula can be lifted to compute join between an upward-closed set of formulas (represented using its minimal elements w.r.t. \(\sqsubseteq \)) and the abstraction of one or more states.

Next, we observe that we can implement \({\mathcal {W}_{\mathcal {L}}\left( {R},{s}\right) }\) by (i) focusing only on formulas that actually need weakening, i.e., formulas in R that are not satisfied by \(s\), without iterating over formulas that \(s\) satisfies; and (ii) leveraging the \(\le _{\mathcal {L}}\) total order to accumulate the set of minimal elements more efficiently.

Algorithm 1 presents our implementation of \({\mathcal {W}_{\mathcal {L}}\left( {R},{s}\right) }\) for an antichain R of canonical formulas and a state \(s\). It updates R to \({\mathcal {W}_{\mathcal {L}}\left( {R},{s}\right) }\) in place, which is useful for computing an abstraction of a set of states (Corollary 3) or even for fixpoint computation (Sect. 6). The algorithm uses a data structure \(\text {LSet}[{\mathcal {L}}]\) (whose implementation is explained in Sect. 5) that stores a set of canonical \(\mathcal {L}\)-formulas and supports two efficient filters: one for formulas that are not satisfied by a given state \(s\), denoted by ; and one for formulas that subsume a given formula \(\varphi \), denoted by \({R}|_{\sqsubseteq {\varphi }}\). Formally: and \({R}|_{\sqsubseteq {\varphi }} = \{\psi \in R \mid \varphi \sqsupseteq \psi \}\).

To weaken R, Algorithm 1 first identifies all formulas that need weakening using the filter. It then removes these formulas, weakens them, and adds the weakened formulas back to the set, while filtering out formulas that are not \(\sqsubseteq _{\mathcal {L}}\)-minimal. For the minimality filtering, we leverage \(\le _{\mathcal {L}}\) to ensure that if \(\varphi \sqsubseteq _{\mathcal {L}} \psi \) then \(\varphi \) is added before \(\psi \). As a result, when inserting a formula \(\varphi \) we only need to check that it is not already subsumed by another formula in the set, which is done by checking if \({R}|_{\sqsubseteq {\varphi }}\) is empty^{Footnote 3}. Importantly, a formula cannot be subsumed by a formula from \({\mathcal {W}_{\mathcal {L}}\left( {\psi },{s}\right) }\) for . (If we assume the contrary we easily get that \(\psi \sqsubseteq \varphi \), contradicting the fact that R is an antichain.)

4.3 Design Consideration and Tradeoffs

We are now in a position to discuss the tradeoffs and considerations that arise in our framework in the design of languages and their subsumption relations, explaining the design choices behind Definitions 1 and 2.

There is a tradeoff between the precision of the subsumption relation \(\sqsubseteq _\mathcal {L}\) and the complexity of implementing the weaken operator \(\mathcal {W}_\mathcal {L}\). From a representation perspective, a more precise \(\sqsubseteq _\mathcal {L}\) is desirable (i.e., relating more formulas), since it means that the upward closure \({\uparrow }{\{\varphi \}}\) of a formula \(\varphi \) is larger, and (upward-closed) sets of formulas can be represented using less minimal formulas. On the other hand, when \({\uparrow }{\{\varphi \}}\) is larger, computing \({\mathcal {W}_{\mathcal {L}}\left( {\varphi },{s}\right) }\) is generally more complicated. As an extreme case, if \(\sqsubseteq _\mathcal {L}\) is trivial (i.e., a formula only subsumes itself), we get no pruning in the representation, but computing \({\mathcal {W}_{\mathcal {L}}\left( {\varphi },{s}\right) }\) is very easy, since it is either \(\{\varphi \}\) or \(\emptyset \). As another example, compare \({{\boldsymbol{\vee }}[{\mathcal {L}}, {\mathcal {L}}]}\) with \({{\boldsymbol{\vee }}_{2}[{\mathcal {L}}]}\). The subsumption relation of \({{\boldsymbol{\vee }}[{\mathcal {L}}, {\mathcal {L}}]}\) is a pointwise extension, while that of \({{\boldsymbol{\vee }}_{2}[{\mathcal {L}}]}\) allows swapping the two formulas, which is more precise. (E.g., \(\bigvee \langle {\varphi , \psi }\rangle \sqsubseteq _{{{\boldsymbol{\vee }}_{2}[{\mathcal {L}}]}} \bigvee \langle {\psi , \varphi }\rangle \) always holds but we might have \(\varphi \vee \psi \not \sqsubseteq _{{{\boldsymbol{\vee }}[{\mathcal {L}}, {\mathcal {L}}]}} \psi \vee \varphi \).) Accordingly, weakening of \({{{\boldsymbol{\vee }}_{2}[{\mathcal {L}}]}}\)-formulas is slightly more involved.

As opposed to reordering of disjuncts, \(\sqsubseteq _{{{\boldsymbol{\vee }}_{k}[{\mathcal {L}}]}}\) does not allow multiple disjuncts to subsume the same one, e.g., \(\bigvee \langle {\varphi , \psi }\rangle \not \sqsubseteq _{{{\boldsymbol{\vee }}_{k}[{\mathcal {L}}]}} \bigvee \langle {\psi }\rangle \) even if \(\varphi \sqsubseteq _\mathcal {L}\psi \) (recall that the mapping between disjuncts must be injective). This choice makes the computation of \(\mathcal {W}_{{{\boldsymbol{\vee }}_{k}[{\mathcal {L}}]}}\) simpler, as it only needs to consider individually weakening each disjunct or adding a new one, but not merging of disjuncts (to “make space” for a new disjunct). For example, when computing \({\mathcal {W}_{{{\boldsymbol{\vee }}_{2}[{\mathcal {L}}]}}\left( {\bigvee \langle {\varphi _1, \varphi _2}\rangle },{s}\right) }\), we do not have to consider formulas of the form \(\bigvee \langle {\varphi , \psi }\rangle \) where \(s\models \psi \) and \(\varphi _1,\varphi _2 \sqsubseteq _\mathcal {L}\varphi \), which we would need to include if the mapping was not required to be injective. One seemingly undesirable consequence of the injectivity requirement is that canonical formulas may contain redundant disjuncts, e.g., \(\bigvee \langle {\varphi , \psi }\rangle \) when \(\varphi \sqsubseteq \psi \) (or even \(\bigvee \langle {\varphi , \varphi }\rangle \)). However, when formulas are obtained by iterative weakening, as in the computation of the representation of \(\alpha (S)\) for a set of concrete states S, formulas with such redundancies will be eliminated as they are always subsumed by a canonical formula without redundancies.

Our design of bounded first-order languages uses bounded disjunction but unbounded conjunction. The reason is that we obtain formulas by weakening other formulas, starting from \(\bot _\mathcal {L}\). In this scenario, bounding the size of conjunctions would have replaced one conjunction by all of its subsets smaller than the bound, causing an exponential blowup in the number of formulas, without contributing much to generalization. On the other hand, bounding the size of disjunctions yields generalization without blowing up the number of formulas (in fact, it reduces the number of formulas compared to unbounded disjunction).

The implementation of \({\mathcal {W}_{\mathcal {L}}\left( {R},{s}\right) }\) presented in Algorithm 1 uses the filters and \({R}|_{\sqsubseteq {\varphi }}\). Since the sets may be very large, a naive implementation that iterates over R to find formulas that are not satisfied by \(s\) ( ) or formulas that subsume \(\varphi \) (\({R}|_{\sqsubseteq {\varphi }}\)) may become inefficient. We therefore introduce a data structure for bounded first-order languages, which we call \(\text {LSet}[{\mathcal {L}}]\), that stores a set of canonical \(\mathcal {L}\)-formulas R (not necessarily an antichain), and implements and \({R}|_{\sqsubseteq {\varphi }}\) without iterating over all formulas in R. The key idea is to define the \(\text {LSet}[{\mathcal {L}}]\) data structure recursively, following the structure of \(\mathcal {L}\), and to use auxiliary data to implement the and \({R}|_{\sqsubseteq {\varphi }}\) filters more efficiently.

For example, to implement \(\text {LSet}[{{{\boldsymbol{\vee }}[{\mathcal {L}_1}, {\mathcal {L}_2}]}}]\), we store a set of \({{\boldsymbol{\vee }}[{\mathcal {L}_1}, {\mathcal {L}_2}]}\)-formulas and two auxiliary data fields: an LSet \(L:\text {LSet}[{\mathcal {L}_1}]\) and a map \(M:\text {Map}[{\mathcal {L}_1}, {\text {LSet}[{\mathcal {L}_2}]}]\). We maintain the invariant that \(\varphi _1\vee \varphi _2\) is in the set iff \(\varphi _2\in M[\varphi _1]\), and that L contains the same \(\mathcal {L}_1\)-formulas as the keys of M. Then, to find formulas that are not satisfied by a state \(s\), i.e., formulas where both disjuncts are not satisfied by \(s\), we first query L to find \(\varphi _1\)’s that are not satisfied by \(s\), and for each such \(\varphi _1\) we query the LSet \(M[\varphi _1]\) to find \(\varphi _2\)’s that are not satisfied by \(s\). Implementing the subsumption filter follows a similar logic.

Our implementation of \(\text {LSet}[{{{\boldsymbol{\vee }}_{k}[{\mathcal {L}}]}}]\) uses a trie data structure that generalizes the binary case. Each edge is labeled by an \(\mathcal {L}\)-formula, and each node represents an \({{\boldsymbol{\vee }}_{k}[{\mathcal {L}}]}\)-formula that is the disjunction of the edge labels along the path from the root to the node. The outgoing edges of each node are stored using an \(\text {LSet}[{\mathcal {L}}]\) that can be used to filter only the edges whose label is not satisfied by a given state, or subsumes a given formula. Then, the and \({R}|_{\sqsubseteq {\bigvee \bar{\varphi }}}\) filters are implemented by recursive traversals of the tree that only traverse filtered edges.

The recursive implementation for the other language constructors is simpler, and follows a similar intuition to that of the cases presented above. The base case \(\text {LSet}[{\mathcal {L}_{A}}]\) is implemented without any auxiliary data using straightforward iteration. The full details of the \(\text {LSet}[{\mathcal {L}}]\) data structure appear in [8].

To evaluate our abstract domain implementation, we used it to implement a symbolic abstraction [27, 29] algorithm that computes the least fixpoint of the best abstract transformer of a transition system. We evaluated our implementation on 19 distributed protocols commonly used as benchmarks in safety verification and obtained promising results.

6.1 Implementation

We implemented our abstract domain and the symbolic abstraction algorithm in Flyvy,^{Footnote 4} an open-source verification tool written in Rust, whose implementation leverages parallelism and the optimizations detailed below. The implementation and benchmarks used, as well as the log files and raw results from the experiments reported, are publicly available in this paper’s artifact [7].

Our implementation receives as input (i) a first-order transition system \((\iota , \tau )\) over signature \(\varSigma \), where \(\iota \) is a closed first-order formula over \(\varSigma \) specifying the initial states and \(\tau \) is a closed first-order formula over two copies of \(\varSigma \) specifying the transitions, and (ii) a specification of a bounded first-order language \(\mathcal {L}\) over \(\varSigma \) that defines the abstract domain \({\mathcal {P}(\mathcal {L})}\). The reachable states of the system are the least fixpoint of a concrete transformer \(\mathcal {T}: {\mathcal {P}(\mathbb {S})} \rightarrow {\mathcal {P}(\mathbb {S})}\) given by \( \mathcal {T}(S) = \{s' \in \mathbb {S}\mid s' \models \iota \vee \exists s\in S. \ \langle {s, s'}\rangle \models \tau \}\), where \(\langle {s, s'}\rangle \models \tau \) indicates that the pair of states satisfies the two-vocabulary formula \(\tau \), i.e., that \(s'\) is a successor of \(s\) w.r.t the transition relation defined by \(\tau \). For more details on this style of modeling distributed systems in first-order logic, see [23,24,25].

The Galois connection \((\alpha , \gamma )\) between \({\mathcal {P}(\mathbb {S})}\) and \({\mathcal {P}(\mathcal {L})}\) induces a best abstract transformer \({\mathcal {T}}^\sharp : {\mathcal {P}(\mathcal {L})} \rightarrow {\mathcal {P}(\mathcal {L})}\) defined by \({\mathcal {T}}^\sharp = \alpha \circ \mathcal {T}\circ \gamma \). Any fixpoint of \({\mathcal {T}}^\sharp \), i.e., a set \(F \subseteq \mathcal {L}\) such that \({\mathcal {T}}^\sharp (F) = F\), is an inductive invariant of \((\iota ,\tau )\) (when sets are interpreted conjunctively), and the least fixpoint, \(\text {lfp}{\mathcal {T}}^\sharp \), is the strongest inductive invariant in \(\mathcal {L}\). The strongest inductive invariant is useful for verifying safety properties of the system, or showing that they cannot be proven in \(\mathcal {L}\) (if the strongest inductive invariant in \(\mathcal {L}\) cannot prove safety, neither can any other inductive invariant expressible in \(\mathcal {L}\)).

Symbolic abstraction computes \(\text {lfp}{\mathcal {T}}^\sharp \) without computing \({\mathcal {T}}^\sharp \) explicitly: beginning with \(F= \mathcal {L}\) (the least element in \({\mathcal {P}(\mathcal {L})}\)), and as long as \(F \ne {\mathcal {T}}^\sharp (F)\), a counterexample to induction (CTI) of F is sampled, i.e., a state \(s' \not \models \bigwedge F\) that is either an initial state or the successor of a state s with \(s\models \bigwedge F\), and F is updated to \(F \sqcup \alpha (\{s'\})\). Our implementation uses the representation \(R_F\) and Algorithm 1 to compute the join (more details in [8]). To find CTIs or determine that none exist we use SMT solvers (Z3 [21] and cvc5 [2]), with queries restricted to the EPR fragment (following [24]), which ensures decidability and the existence of finite counterexamples. Solvers still struggle in some challenging benchmarks, and we employ several optimizations detailed in [8] to avoid solver timeouts.

6.2 Experiments

To evaluate our techniques, we computed the least fixpoints (strongest inductive invariants) of 19 distributed protocols commonly used as benchmarks in safety verification, in a language expressive enough to capture their human-written safety invariants. We used all EPR benchmarks from [15], except for universally quantified Paxos variants. To evaluate the utility of the LSet data structure described in Sect. 5, we ran each experiment twice, once using LSet and once using a naive (but parallelized) implementation for the filters and \({R}|_{\sqsubseteq {\varphi }}\).

To specify the bounded first-order language for each example, we provide the tool with a quantifier prefix (using \({{\boldsymbol{\exists }}_{X}[{\cdot }]}\), \({{\boldsymbol{\forall }}_{X}[{\cdot }]}\), and \({{\exists }\!{\forall }_{X}[{\cdot }]}\)) composed on top of a quantifier-free bounded language that captures k-pDNF (following [15]). A k-pDNF formula has the structure \(c_1\rightarrow (c_2\vee \dots \vee c_k)\), where \(c_1,c_2,\dots ,c_k\) are cubes (conjunctions of literals). We specify such formulas as \({{\boldsymbol{\vee }}[{{{\boldsymbol{\vee }}_{n}[{\mathcal {L}_{A_1}}]}}, {{{\boldsymbol{\vee }}_{k-1}[{{{\boldsymbol{\wedge }}_{\omega }[{\mathcal {L}_{A_2}}]}}]}}]}\), where k and n are parameters, and \(A_1\) and \(A_2\) are sets of literals. Inspired by [30], we observe that we can restrict the variables used in \(A_1\) and \(A_2\) to reduce the size of the language without losing precision.^{Footnote 5} For additional details see [8]. The list of examples with their language parameters appears in Table 1. For each example, we report the quantifier structure, the k and n parameters of the k-pDNF quantifier-free matrix, and the approximate size of the language \(\mathcal {L}\). Recall that the size of the abstract domain is \(2^{|\mathcal {L}|}\).

All experiments were performed on a 48-threaded machine with 384 GiB of RAM (AWS’s z1d.metal) and a three-hour time limit. For each example we also provide runtimes of two state-of-the-art safety verification tools, DuoAI [30] and P-FOL-IC3 [15]. Note that, unlike our technique, these tools look for some inductive invariant proving safety, not necessarily the strongest, but are also given fewer explicit language constraints. Moreover, the runtimes of DuoAI and P-FOL-IC3 are sourced from their respective papers, and reflect different architectures and time limits. Thus, the inclusion of their results is not intended as a precise comparison to our tool, but as a reference for the difficulty of the invariant inference task of each example, as evidenced by state-of-the-art techniques.

6.3 Results

The results of the symbolic abstraction computation are presented in Table 1. For each experiment we report the runtime of our tool and the following statistics: the percentage of time spent weakening formulas (as opposed to searching for CTIs), the number of formulas in the representation of the fixpoint (if reached), and the maximal number of formulas in the representation of an abstract element throughout the run. Each experiment was run five times, unless it timed out, in which case it was run only once. We aggregate the results of each statistic across multiple runs as \(median \pm deviation\), where deviation is the maximal distance between the median value and the value of the statistic in any given run.

For simple examples, the fixpoint computation terminates very quickly, often faster than the other tools, and maintains only tens or hundreds of formulas throughout its run. Some of the larger examples, such as ticket, paxos-epr, flexible-paxos-epr, and cache also terminate after similar times to the other tools. In fact, this is the first work to compute least fixpoints for any Paxos variant or cache. (DuoAI, for instance, has a component that attempts to compute a precise fixpoint, but [30] reports that it times out on all Paxos variants.)

Unsurprisingly, there is a significant gap between the runtimes of examples with and without quantifier alternation, mostly due to the time spent in SMT solvers. For example, in ticket we spend about \(43\%\) of the runtime performing weakenings, but this percentage drops to \(1\%\) and \(4\%\) for paxos-epr and flexible-paxos-epr, respectively. This causes the runtime of paxos-epr to exceed that of ticket by more than an order of magnitude, although its fixpoint computation considers fewer formulas and actually spends less time weakening. Similarly, in cache we manage to prove a fixpoint of a hundred thousand formulas in about an hour and spend a third of it weakening formulas, while multi-paxos-epr and fast-paxos-epr time out, although they consider far fewer formulas and spend a negligible amount of time weakening.

Next, we observe that the use of LSet significantly reduces time spent in weakening, leading to more than an order of magnitude difference even in moderate examples, e.g., ticket and paxos-epr. In terms of the total fixpoint computation time, in examples where the runtime is small or dominated by the SMT solvers, the effect might be negligible, but otherwise the speedup is significant. For example, cache is not solved within the 3-hour limit with a naive data structure; it gets stuck after reaching \(\sim \) 20,000 formulas in the abstraction, whereas using LSet it is solved in about an hour while handling more than ten times the number of formulas. Similarly, in the two unsolved examples where SMT calls seem to be the bottleneck (multi-paxos-epr and fast-paxos-epr), using a naive data structure causes weakening to become the bottleneck and time out.

Finally, the remaining timeouts, learning-switch, stoppable-paxos-epr, and vertical-paxos-epr, are the only examples where the weakening process itself is the bottleneck. These are cases where the language induced by the human-written invariant, using the constraining parameters of bounded languages, create a inefficient weakening process. The cause for this is either a profusion of literals in the basis language (>600 in learning-switch and stoppable-paxos-epr, less than 200 in all other examples), or a very expressive language (e.g., vertical-paxos-epr uses 3-pDNF, whereas all other examples use 1- and 2-pDNF). For these examples, it might be necessary to restrict the languages in additional ways, e.g., as was done in [30]. Our experience, however, is that the more significant bottleneck for computing least fixpoints for the most complicated examples is the SMT queries.

Many recent works tackle invariant inference in first-order logic [9,10,11, 14, 15, 17, 26, 30, 31]. These works are all property-guided and employ sophisticated heuristics to guide the search for invariants. Of these works, the most closely related to ours are [30, 31]. DistAI [31] is restricted to universally quantified invariants, while DuoAI [30] infers invariants with quantifier alternations. DuoAI defines a “minimum implication graph” enumerating all formulas in a first-order logical language, whose transitive closure can be understood as a specific subsumption relation, and where replacing a node with its successors can be understood as a form of weakening. DuoAI’s “top-down refinement” precisely computes the strongest invariant in the logical domain. However, this computation does not scale to complex examples such as all Paxos variants, in which case “bottom-up refinement” is used—a property-guided process that does not compute the strongest invariant. Our approach based on a generic subsumption relation is both more principled and more scalable, as it succeeds in computing the least fixpoint for some Paxos variants.

Another work concerning a least-fixpoint in a logical domain is [19], which computes the set of propositional clauses up to length k implied by a given formula, minimized by the subsumption relation \(\sqsubseteq =\subseteq \); a trie-based data structure is used to maintain the formulas, weaken them, and check subsumption of a formula by the entire set. Both that data structure and \(\text {LSet}[{{{\boldsymbol{\vee }}_{k}[{\cdot }]}}]\) bear similarity to UBTrees [12], also employed in [3], which store sets and implement filters for subsets and supersets. However, while UBTrees and LSets always maintain ordered tree paths, these are unordered in [19], which allows [19] to perform weakening directly on the data structure, whereas we need to remove the unsatisfied disjunctions, weaken, and insert them. On the other hand, this makes filtering for subsets in UBTrees and LSets more efficient. Also note that LSet is more general than both, since it supports a more general subsumption relation.

We have developed key algorithms and data structures for working with a logical abstract domain of quantified first-order formulas. Our fundamental idea is using a well-defined subsumption relation and a weaken operator induced by it. This idea makes the abstract domain feasible, and it is also extensible: while we explored one possible subsumption relation and its associated weaken operator, future work may explore others, representing different tradeoffs between pruning and weakening. We demonstrated the feasibility of our approach by computing the least abstract fixpoint for several distributed protocols modeled in first-order logic—a challenging application domain where previously only property-directed heuristics have been successful. For some of the examples in our evaluation, the computation still times out. In some of these cases, SMT queries (for computing CTIs) become the bottleneck. Dealing with this bottleneck is an orthogonal problem that we leave for future work. For the examples with the largest logical languages, abstract domain operations remain the bottleneck, and future work may either scale the abstract domain implementation to such languages or explore combinations with property-directed approaches.