Automated Catamorphism Synthesis for Solving Constrained Horn Clauses over Algebraic Data Types
Hiroyuki Katsura, Naoki Kobayashi, Ken Sakayori, Ryosuke Sato · 2025
Read Automated Catamorphism Synthesis for Solving Constrained Horn Clauses over Algebraic Data Types by Hiroyuki Katsura, Naoki Kobayashi, Ken Sakayori, Ryosuke Sato (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20726.txt.
Introduction
Programs that manipulate lists and trees are hard to verify automatically, because proofs need facts about whole structures, like the sum of a list. Hiroyuki Katsura, Naoki Kobayashi, Ken Sakayori, and Ryosuke Sato attack the problem through constrained Horn clauses, a standard logic format for verification. Their insight is to let the solver invent fold functions, called catamorphisms, that summarize a structure in one value.
The framework discovers the right folds on demand and uses them to state a model of the clauses. Their solver, Catalia, beat leading rivals on the satisfiable problems of a 2024 benchmark. A combined tool built on it then won its category at the 2025 competition. The results suggest automatic fold-finding closes a real gap in software verification.
Catalog record
| CREATOR | Hiroyuki Katsura, Naoki Kobayashi, Ken Sakayori, Ryosuke Sato |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-20726
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Automated Catamorphism Synthesis for Solving Constrained Horn Clauses over Algebraic Data Types Hiroyuki Katsura, Naoki Kobayashi, Ken Sakayori, Ryosuke Sato Abstract We propose a novel approach to satisfiability checking of Constrained Horn Clauses (CHCs) over Algebraic Data Types (ADTs). CHC-based automated verification has gained considerable attention in recent years, leading to the development of various CHC solvers. However, existing solvers for CHCs over ADTs are not fully satisfactory, due to their limited ability to find and express models involving inductively defined functions/predicates (e.g., those about the sum of list elements). To address this limitation, we consider catamorphisms (generalized fold functions), and present a framework for automatically discovering appropriate catamorphisms on demand and using them to express a model of given CHCs. We have implemented a new CHC solver called Catalia based on the proposed method. Our experimental results for the CHC-COMP 2024 benchmark show that Catalia outperforms state-of-the-art solvers in solving satisfiable CHCs over ADTs. Catalia was also used as a core part of the tool called ChocoCatalia, which won the ADT-LIA category of CHC-COMP 2025. 1 Introduction Fully automated verification of programs through satisfiability checking of constrained Horn clauses (CHCs) has attracted considerable attention in recent years, as it offers a uniform and language-agnostic framework for verifying diverse program properties [ 13 , 17 , 25 , 1 ] . For example, consider the following functional program. let rec plus m n = if n=0 then m else (plus m (n-1))+1 let main m n = if n>=0 then assert(plus m n >= m) The lack of assertion failures in the above program can be reduced to the satisfiability of the following CHCs, i.e, the problem of whether there exists a predicate \mathit{Plus} that satisfies them: \displaystyle\forall m.\;\mathit{Plus}(m,0,m). \displaystyle\forall m,n,r.\;\mathit{Plus}(m,n,r+1)\Leftarrow\mathit{Plus}(m,n-1,r). \displaystyle\forall m,n,r.\;\textbf{ff}\Leftarrow\mathit{Plus}(m,n,r)\land n\geq 0\land r<m. Here, ff represents false. The predicate \mathit{Plus} may be considered an invariant among arguments m,n and the corresponding return value r ; indeed, \mathit{Plus}(m,n,r)\equiv m+n=r satisfies the above CHCs. State-of-the-art CHC solvers [ 22 , 15 , 14 , 5 , 4 ] can quickly solve problems like the above, finding an appropriate invariant ( \mathit{Plus}(m,n,r)\equiv m+n=r or \mathit{Plus}(m,n,r)\equiv r\geq m in this case), enabling fully automated program verification. Despite various efforts, however, the current CHC solvers are not very good at dealing with data structures. For example, consider the following variant of the example above, where natural numbers are represented as data structures. \displaystyle\forall m.\;\mathit{PlusNat}(m,Z,m). \displaystyle\forall m,n,r.\;\mathit{PlusNat}(m,S(n),S(r))\Leftarrow\mathit{PlusNat}(m,n,r). \displaystyle\forall n.\;\mathit{Lt}(Z,S(n)).\qquad\forall m,n.\;\mathit{Lt}(S(m),S(n))\Leftarrow\mathit{Lt}(m,n). \displaystyle\forall m,n,r.\;\textbf{ff}\Leftarrow\mathit{PlusNat}(m,n,r)\land\mathit{Lt}(r,m). Z3 Spacer [ 22 ] , a state-of-the-art CHC solver, fails to prove the satisfiability of the CHCs above. A problem is that while a model for \mathit{Plus} can be expressed by a simple linear arithmetic formula ( m+n=r ), an inductively defined predicate is required to express a model for \mathit{PlusNat} , and it is, in general, hard to automatically find such an inductively defined predicate and check that it is indeed a model (i.e., satisfies all the clauses). To address the issue above, we propose a method for abstracting CHCs by using a catamorphism [ 26 ] from data structures to (tuples of) integers, on which existing CHC solvers perform well in practice. For the example above, we can abstract Z and S respectively to 0 and \lambda x.x+1 1 1 1 Actually, we do not lose any information using this abstraction , as the induced catamorphism is injective. In general, however a catamorphism may not be injective, hence introducing abstraction. , and obtain the following “abstract” CHCs over integers, whose satisfiability implies that of the original CHCs. \displaystyle\forall m.\;\overline{\mathit{PlusNat}}(m,0,m). \displaystyle\forall m,n,r.\;\overline{\mathit{PlusNat}}(m,n+1,r+1)\Leftarrow\overline{\mathit{PlusNat}}(m,n,r). \displaystyle\forall n.\;\overline{\mathit{Lt}}(0,n+1).\qquad\forall m,n.\;\overline{\mathit{Lt}}(m+1,n+1)\Leftarrow\overline{\mathit{Lt}}(m,n). \displaystyle\forall m,n,r.\;\textbf{ff}\Leftarrow\overline{\mathit{PlusNat}}(m,n,r)\land\overline{\mathit{Lt}}(r,m). Universal quantifiers are now over integers, and for the sake of simplicity, we have omitted some conditions on the variables; see later sections. State-of-the-art solvers can instantly deduce its satisfiability, which also implies the satisfiability of the original CHCs. The remaining question is how to automatically find appropriate catamorphisms. In the above example, the required catamorphism is just the “size” function incorporated by default in some CHC solvers like Eldarica [ 15 ] , but as we will see later, the size function is not always sufficient. To this end, we propose a method for automatically finding appropriate catamorphisms in a counterexample-guided manner. We have implemented the proposed method and developed a new CHC solver called Catalia . According to our experiments using the benchmark set of the ADT category of CHC-COMP 2024, Catalia significantly outperformed state-of-the-art CHC solvers for SAT instances. Our contributions are summarized as follows. • Formalization of abstraction of CHCs using catamorphisms. • Counterexample-guided automatic synthesis of appropriate catamorphisms. • Implementation of the proposed method and experimental evaluation. The idea of using catamorphisms for verification of programs with ADTs itself is not new [ 34 , 30 , 28 , 16 , 9 ] . Thus, our main contributions lie in the formalization and implementation of the procedure for automatically discovering catamorphisms in the context of CHC solving. The rest of this paper is organized as follows. Section 2 reviews CHCs over ADTs and catamorphisms for ADTs. Section 3 gives an overview of our framework. Section 4 formalizes our catamorphism-based abstraction, and Section 5 introduces our template-based catamorphism synthesis procedure. Section 6 reports the experimental results. Section 7 discusses related work, and Section 8 concludes the paper. 2 Preliminaries 2.1 Constrained Horn Clauses modulo Algebraic Data Types and Integer Arithmetic We consider a standard first-order logic and a theory of algebraic data types and integer arithmetic, which is written as T_{\text{ADT+Z}} . We also denote the theory of integer arithmetic by T_{\text{Z}} . For simplicity, we consider formulas that involve only integers and a single algebraic data type (ADT) (\delta,\{\,C_{1},\dots,C_{k}\,\}) where \delta is a sort and C_{i} is a function symbol called a constructor . 2 2 2 Extending our proposed method to support multiple ADTs is straightforward. As detailed in Section 6 , our implementation is already capable of handling multiple ADTs within a single instance. In a standard theory of algebraic data types, projections and testers are used as the standard connectives for algebraic data types in addition to constructors. We omit them for simplicity, since they can be easily removed by standard preprocessing techniques (c.f. Section 4.5 of [ 23 ] ). Each constructor C_{i} is assumed to be a function of m_{i}+n_{i} arguments with its sort specified as (\overbrace{\mathit{int}\times\dots\times\mathit{int}}^{m_{i}}\times\overbrace{\delta\times\dots\times\delta}^{n_{i}})\to\delta. Note that m_{i}+n_{i} can be 0 . We often simply write \delta to mention the ADT. Example 1 An algebraic data type for natural numbers \mathit{nat} in the introduction is defined as (\mathit{nat},\{\,Z,S\,\}) where Z is a constant of sort \mathit{nat} and S has the sort \mathit{nat}\to\mathit{nat} . An algebraic data type for integer lists, written as \mathit{ilist} , is defined as (\mathit{ilist},\{\,\mathit{nil},\mathit{cons}\,\}) where \mathit{nil} is a constant of sort \mathit{ilist} and \mathit{cons} has the sort \mathit{\mathit{int}}\times\mathit{ilist}\to\mathit{ilist} . A list [1;2] is written as \mathit{cons}(1,\mathit{cons}(2,\mathit{nil})) . ∎ The sets of terms and constraint formulas are defined by: \displaystyle(\textit{terms})\quad t \displaystyle::=x\mid n\mid C_{i}(\widetilde{t_{i}})\mid t_{1}\mathbin{\textbf{op}}t_{2} \displaystyle(\textit{constraint formulas})\quad\theta \displaystyle::=\textbf{tt}\mid\textbf{ff}\mid\theta_{1}\wedge\theta_{2}\mid\theta_{1}\vee\theta_{2}\mid t_{1}\bowtie t_{2}\mid\exists x^{\xi}.\>\theta\mid\forall x^{\xi}.\>\theta. Here, x , n , and \xi are metavariables for variables, integers, and sorts respectively, \bowtie ranges over binary predicates in \{\,=_{\mathit{int}},\neq_{\mathit{int}},>,\leq,=_{\delta}\,\} and \mathbin{\textbf{op}} ranges over binary arithmetic operations \{\,+,-,\times\,\} . We also write \widetilde{t_{i}}