CHCVerif : A Portfolio-Based Solver for Constrained Horn Clauses
Mihály Dobos-Kovács Levente Bajczi András Vörös · 2025
Read CHCVerif : A Portfolio-Based Solver for Constrained Horn Clauses by Mihály Dobos-Kovács Levente Bajczi András Vörös (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-2510-26431.txt.
Introduction
Mihály Dobos-Kovács, Levente Bajczi, and András Vörös present CHCVerif, a solver for constrained Horn clauses. These clauses are a common middle format for program checks, such as safety tests, invariant finding, and analysis across procedures. Rather than build a new engine from scratch, the team routes the clauses to mature software verification tools.
Dobos-Kovács and his two co-authors run several such tools as a portfolio, so the strengths of each can cover the others. Their tests show moderate success on clauses about whole numbers. On bitvector benchmarks, which reflect low-level program detail, the results were modest but real. The paper argues the route is viable, above all when the portfolio is chosen with care.
Catalog record
| CREATOR | Mihály Dobos-Kovács Levente Bajczi András Vörös |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-26431
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
CHCVerif : A Portfolio-Based Solver for Constrained Horn Clauses Mihály Dobos-Kovács Levente Bajczi András Vörös Abstract Constrained Horn Clauses (CHCs) are widely adopted as intermediate representations for a variety of verification tasks, including safety checking, invariant synthesis, and interprocedural analysis. This paper introduces CHCVerif , a portfolio-based CHC solver that adopts a software verification approach for solving CHCs. This approach enables us to reuse mature software verification tools to tackle CHC benchmarks, particularly those involving bitvectors and low-level semantics. Our evaluation shows that while the method enjoys only moderate success with linear integer arithmetic, it achieves modest success on bitvector benchmarks. Moreover, our results demonstrate the viability and potential of using software verification tools as backends for CHC solving, particularly when supported by a carefully constructed portfolio. Funding. This research was partially funded by the 2024-2.1.1-EKOP-2024-00003 University Research Scholarship Programme under project numbers EKOP-24-3-BME-213, and the Doctoral Excellence Fellowship Programme under project numbers DKÖP-23-1-BME-5 and DKÖP-23-1-BME-15; with the support provided by the Ministry of Culture and Innovation of Hungary from the NRDI Fund. 1 Introduction Constrained Horn Clauses (CHCs) form a widely adopted intermediate representation for a variety of verification tasks, including safety checking [ 30 , 17 , 19 ] , invariant synthesis [ 22 , 24 , 18 ] , and systems verification [ 13 ] . Consequently, CHC solving has become a fundamental component in many formal verification pipelines. Despite the maturity of existing solvers such as Eldarica [ 21 ] and Spacer [ 25 ] , there are still unsolved challenges, such as supporting CHCs with bitvector theories. We present CHCVerif , a portfolio-based CHC solver that adopts a software verification perspective. Rather than solving CHCs directly at the logical level, CHCVerif translates CHC problems into semantically equivalent C programs and applies a portfolio of C verifiers to determine their correctness. The satisfiability of the original CHC system corresponds to the correctness of the generated C program. This approach enables CHCVerif to take advantage of mature software verification backends while diversifying its solving strategy through portfolio composition. CHCVerif builds on CoVeriTeam [ 5 ] , a recently proposed framework for constructing compositional verification portfolios. CoVeriTeam allows CHCVerif to orchestrate multiple C verifiers within a configurable and extensible architecture. By expressing CHC solving as a software verification task and managing diverse tools through CoVeriTeam , CHCVerif offers a novel and modular pathway to Horn clause verification. The remainder of the paper is structured as follows. Section 2 provides background on portfolio-based verification. Section 3 describes our overall approach to verification. Section 4 presents our process of constructing the portfolio. In Section 5 , we reflect on our results. 2 Background 2.1 CHC to C transformation Let us define a CHC problem as a set of deduction rules in the context of this work. A deduction rule consists of a premise and a consequence. The premise can have zero or more uninterpreted functions , while the consequence can have zero or exactly one. If there are no uninterpreted functions in the premise, we call that rule an atom . If there is more than one uninterpreted function in the premise of a rule, we call that rule non-linear . If a deduction rule deduces the literal false , we call that rule a query . If any rule is non-linear in a CHC problem, we call that problem non-linear . Otherwise, we say that the CHC is linear . In practical applications, CHC problems are frequently represented using the SMT-LIBv2 format [ 12 , 14 ] . This format depicts deduction rules as imply expressions over a specific SMT theory. Moreover, every variable involved in the deduction rules is subject to universal quantification across the entire domain of variables, as required by the respective SMT theories. In this paper, we focus on the SMT theories core , linear integer arithmetic , and fixed-size bitvectors . Note that problems requiring support for more theories exist (such as those using arrays or algebraic data types ), but we discount those in the context of this work. In the following, we present a simple example to showcase the basic idea behind the CHC to C transformation from [ 27 , 3 ] . \displaystyle A(x)\leftarrow x=1 \displaystyle A(x)\leftarrow A(x-1) \displaystyle\mathit{false}\leftarrow A(11) The first rule declares that A(1) is true . The second rule propagates this fact forward, stating that if A(x) holds, then A(x+1) must also hold. Finally, the third rule is a query that leads to a contradiction if A(11) holds. Intuitively, this system is unsatisfiable: by repeated application of the second rule, starting from A(1) , we deduce A(2) , A(3) , and so on up to A(11) . Thus, A(11) is deduced, which triggers the contradiction, making the system unsatisfiable. The CHC system can be encoded in software in a top-down or bottom-up manner [ 27 ] . In the backward (top-down) encoding in 1 , the verifier starts with the query A(11) and recursively unfolds the rules until it reaches the exit condition. Note that this program might fall into an infinite recursion based on the value of the parameter of the function A . However, tools that can reason about recursion may find that the exit condition of A(11) is reachable. In contrast, the forward (bottom-up) version shown in 2 constructs the program starting from the facts. It iteratively applies the rules using a loop and a nondeterministic choice of the current state. By explicitly modeling the inference steps, this version avoids recursion and can often be more amenable to automated reasoning by tools that support nondeterminism and state exploration, but in return, it only works with linear CHCs. Listing 1: Backward transformation ⬇ 1 int A ( int x ) { 2 if ( x == 1) return 1; 3 else if ( A ( x - 1)) return 1; 4 else return 0; 5 } 6 7 int main () { 8 if ( A (11)) return -1; 9 else return 0; 10 } Listing 2: Forward transformation ⬇ 1 int main () { 2 int A = 1, x ; 3 4 while ( true ) { 5 x = nondet (); 6 if ( A == 11) return -1; 7 else if ( A == x - 1) A = x ; 8 } 9 } 2.2 Algorithm selection and portfolios Formal verification, in general, is a resource-intensive task that involves a variety of analysis techniques, such as symbolic execution, bounded model checking, abstract interpretation, and others, each with its own strengths and limitations. Given the inherent variability in how different tools perform across verification problems, using portfolio-based and algorithm selection strategies has received increasing attention in recent years [ 8 ] . In the context of formal verification, the task of algorithm selection involves determining the most suitable algorithm, configuration, or tool from a set of options to solve a verification problem. The choice is typically based on characteristics derived from the problem, such as its structural details, control flow, data types, or recognizable patterns. In contrast, a portfolio involves the execution of multiple verification tools or configurations on the same verification problem, either in parallel or in a coordinated sequence.