Horn Clauses for Verification and Synthesis

Many Program Verification and Synthesis problems of interest can be modeled directly using Horn clauses and many recent advances in the CLP and CAV communities have centered around efficiently solving problems presented as Horn clauses.

This series of workshops aims to bring together researchers working in the communities of Constraint/Logic Programming (e.g., ICLP and CP), Program Verification (e.g., CAV, TACAS, and VMCAI), and Automated Deduction (e.g., CADE, IJCAR), on the topic of Horn clause based analysis, verification, and synthesis.

Horn clauses for verification and synthesis have been advocated by these communities in different times and from different perspectives and HCVS is organized to stimulate interaction and a fruitful exchange and integration of experiences.

The workshop follows previous meetings: HCVS 2025 in Zagreb, Croatia (CAV 2025), HCVS 2024 in Luxembourg (ETAPS 2024), HCVS 2023 in Paris (ETAPS 2023), HCVS 2022 in Munich (ETAPS 2022), HCVS 2021 in Luxembourg (online, ETAPS 2021), HCVS 2020 in Dublin, Ireland (ETAPS 2020), HCVS 2019 in Prague, Czech Republic (ETAPS 2019), HCVS 2018 in Oxford, UK (CAV, ICLP and IJCAR at FLoC 2018), HCVS 2017 in Gothenburg, Sweden (CADE 2017), HCVS 2016 in Eindhoven, The Netherlands (ETAPS 2016), HCVS 2015 in San Francisco, CA, USA (CAV 2015), and HCVS 2014 in Vienna, Austria (VSL).

Aims and Scope

Topics of interest include, but are not limited to the use of Horn clauses, constraints, and related formalisms in the following areas:

  • Analysis and verification of programs and systems of various kinds (e.g., imperative, object-oriented, functional, logic, higher-order, concurrent, transition systems, petri-nets, smart contracts)
  • Program synthesis
  • Program testing
  • Program transformation
  • Constraint solving
  • Type systems
  • Machine learning and automated reasoning
  • CHC encoding of analysis and verification problems
  • Resource analysis
  • Case studies and tools
  • Challenging problems
We solicit regular papers describing theory and implementation of Horn-clause based analysis and tool descriptions. We also solicit extended abstracts describing work-in-progress, as well as presentations covering previously published results that are of interest to the workshop.

Invited speakers

  • Florian Frohn (RWTH Aachen University, Germany).
    Infinite State Model Checking without Interpolation

    Most state-of-the-art model checking algorithms for infinite state systems are based on Craig Interpolation. These algorithms are very powerful, but also highly sensitive to minor changes of the input or the underlying interpolating SMT solver. In recent years, we developed several non-interpolating model checking algorithms, with the goal of making infinite state model checking more robust and predictable. Their core ingredients are loop acceleration, which is useful for finding deep counterexamples, and recurrence analysis, which is the most important building block of our techniques for proving safety / satisfiability. In this talk, I will give an overview of these non-interpolating model checking algorithms, and highlight their strengths and weaknesses.

  • Natasha Sharygina (University of Lugano, Switzerland).
    CHC-Based Reachability Analysis via Cycle Summarization

    Modern reachability analysis techniques are highly effective when applied to software safety verification. However, they still struggle with certain classes of problems, particularly the verification of programs with complex control flow and deep nested loops. In this talk, I will present Cycle Summarization-based Reachability Analysis (CSRA), a new Constrained Horn Clause (CHC)-based approach for reachability analysis of nested-loop software. Our technique relies on the generation and refinement of cycle summaries within the CHC system. CSRA analyzes cycles in a modular manner, constructing summaries and cycle unrollings. Cycle summaries in our approach are used both to prove safety and detect potential safety violations. This enables more efficient exploration of nested loops. The prototype of CSRA is implemented within the Golem CHC solver. An empirical comparison with other reachability analysis techniques demonstrates that our approach is highly competitive in both proving safety and constructing counterexamples.

Program

25 July 2026 (All times are in CEST) — Room: TBA

08:55 - 09:00 Welcome (Fred Mesnard, Zafer Esen)
  
Session 1 (Chair: Fred Mesnard)
09:00 - 10:00 Invited Talk: Infinite State Model Checking without Interpolation
Florian Frohn (RWTH Aachen University, Germany)
Abstract

Most state-of-the-art model checking algorithms for infinite state systems are based on Craig Interpolation. These algorithms are very powerful, but also highly sensitive to minor changes of the input or the underlying interpolating SMT solver. In recent years, we developed several non-interpolating model checking algorithms, with the goal of making infinite state model checking more robust and predictable. Their core ingredients are loop acceleration, which is useful for finding deep counterexamples, and recurrence analysis, which is the most important building block of our techniques for proving safety / satisfiability. In this talk, I will give an overview of these non-interpolating model checking algorithms, and highlight their strengths and weaknesses.
10:00 - 10:30 SV-LIB 1.0: A Standard Exchange Format for Software-Verification Tasks
Dirk Beyer, Gidon Ernst, Martin Jonáš, Marian Lingsch-Rosenfeld (LMU Munich)
Abstract

In the past two decades, significant research and development effort went into the development of verification tools for individual languages, such as C, C++, and Java. Many of the used verification approaches are in fact language-agnostic and it would be beneficial for the technology transfer to allow for using the implementations also for other programming and modeling languages. To address the problem, we propose SV-LIB, an exchange format and intermediate language for software-verification tasks, including programs, specifications, and verification witnesses. SV-LIB is based on well-known concepts from imperative programming languages and uses SMT-LIB to represent expressions and sorts used in the program. This makes it easy to parse and to build into existing infrastructure, since many verification tools are based on SMT solvers already. Furthermore, SV-LIB defines a witness format for both correct and incorrect SV-LIB programs, together with means for specifying witness-validation tasks. This makes it possible both to implement independent witness validators and to reuse some verifiers also as validators for witnesses. This paper presents version 1.0 of the SV-LIB format, including its design goals, the syntax, and informal semantics. Formal semantics and further extensions to concurrency are planned for future versions.
  
10:30 - 11:00 Coffee Break
  
Session 2 (Chair: Fred Mesnard)
11:00 - 11:30 Why3-Elpi: Logic Programming Transformations for Why3
Matteo Manighetti (IRIF, Université Paris Cité)
Abstract

Why3 relies on logical task transformations both for the translation of verification conditions towards external provers and for interactive proof. The kind of metalogical programming involved in these transformations is naturally expressed in higher-order logic programming languages such as λProlog. This paper presents Why3-Elpi, a tool that exposes a typed fragment of the Why3 API to λProlog using Elpi and lets users implement Why3 transformations in λProlog. This provides an environment where non-trivial transformations can be easily prototyped and experimented with, using a declarative and concise style.
11:30 - 12:00 CHC-based Automated Verification of WebAssembly Programs
Akihisa Yagi, Ken Sakayori, Naoki Kobayashi (The University of Tokyo)
Abstract

WebAssembly is a stack-based imperative language widely used to develop safe and efficient Web applications. In this paper, we propose an automated static verification method for a subset of WebAssembly using a constrained Horn clauses (CHCs) satisfiability solver. Our main challenges are how to handle indirect function calls effectively and how to analyze huge panic handlers. A naïve approach to the former problem would be to model a function reference table as an array of functions' entry points, but it would suffer from having too many candidates for indirect calls, resulting in a large case analysis. We address the problem by utilizing type information and filtering candidates for each indirect function call. For the latter problem, a panic handler, which is a function that is called when an error occurs, can be very large and complex. We mitigate this problem by summarizing the panic handler using control-flow analysis. We confirmed the effectiveness of our approach through preliminary experiments.
  
12:00 - 14:00 Lunch Break
  
Session 3 (Chair: Zafer Esen)
14:00 - 15:00 Invited Talk: CHC-Based Reachability Analysis via Cycle Summarization
Natasha Sharygina (University of Lugano, Switzerland)
Abstract

Modern reachability analysis techniques are highly effective when applied to software safety verification. However, they still struggle with certain classes of problems, particularly the verification of programs with complex control flow and deep nested loops. In this talk, I will present Cycle Summarization-based Reachability Analysis (CSRA), a new Constrained Horn Clause (CHC)-based approach for reachability analysis of nested-loop software. Our technique relies on the generation and refinement of cycle summaries within the CHC system. CSRA analyzes cycles in a modular manner, constructing summaries and cycle unrollings. Cycle summaries in our approach are used both to prove safety and detect potential safety violations. This enables more efficient exploration of nested loops. The prototype of CSRA is implemented within the Golem CHC solver. An empirical comparison with other reachability analysis techniques demonstrates that our approach is highly competitive in both proving safety and constructing counterexamples.
15:00 - 15:30 Extended Abstract: Bit-Precise CHC Satisfiability Using Theory-Modular Reasoning
Omer Rappoport, Orna Grumberg, Yakir Vizel (Technion, Israel)
Abstract

Program safety verification with bit-precise semantics can naturally be encoded as Constrained Horn Clauses (CHCs) modulo the theory of fixed-size bit-vectors (TB). Alternatively, bit-precise semantics can be encoded as CHCs modulo the theory of Integer Arithmetic (TI) by modeling modular and bit-wise behavior using arithmetic constraints. However, neither approach consistently yields an efficient verification procedure: reasoning directly in TB often limits the generalization capabilities of CHC solvers, whereas bit-precise TI encodings produce complex arithmetic constraints that are expensive to process, especially in the presence of bit-wise operations.

We present Mosaic, a theory-modular framework for deciding satisfiability of CHCs modulo TB through modular reasoning in TB and TI. Given a CHC set modulo TB, Mosaic partitions the input into a bit-vector fragment and an integer fragment, and exchanges information between them through sound theory transformations. This avoids committing the entire CHC set to a single theory, allowing different CHCs to be handled in different background theories.

We implemented a prototype of Mosaic using Z3 and Spacer and evaluated it on bit-manipulating benchmarks. Our evaluation shows that Mosaic significantly outperforms both pure bit-vector and fully arithmetic CHC-solving approaches, often scaling to substantially larger bit-widths.
  
15:30 - 16:00 Coffee Break
  
Session 4 (Chair: Zafer Esen)
16:00 - 16:30 Presentation Only Paper: Bit-Vector CHC Solving for Binary Analysis and Binary Analysis for Bit-Vector CHC Solving
Aaron Bembenek, Toby Murray (University of Melbourne)
Abstract

For high-assurance software, source-level reasoning is insufficient: we need binary-level guarantees. Despite constrained Horn clause (CHC) solving being one of the most popular forms of automated verification, prior work has not evaluated the viability of CHC solving for binary analysis. To fill this gap, we assemble a pipeline that encodes binary analysis problems as CHCs in the SMT logic of quantifier-free bit vectors, and show that off-the-shelf CHC solvers achieve reasonable success on binaries compiled from 983 C invariant inference benchmarks: a portfolio solves 59.5% and 66.0% of the problems derived from the unoptimized and optimized binaries, respectively—roughly equal to the success rate of a leading C verifier on the source code (60.1%). Moreover, we show that binary analysis provides a valuable source of bit-vector CHC benchmarks (which are in short supply): binary-derived problems differ from existing benchmarks both structurally and in solver success rates and rankings. Augmenting CHC solving competitions with binary-derived benchmarks will encourage solver developers to improve bit-vector reasoning, in turn making CHC solving a more effective tool for binary analysis.
16:30 - 17:30 Presentation of CHC-COMP Results and Discussion
Konstantin Britkov (University of Lugano, Switzerland), Levente Bajczi (BME-MIT, Hungary)

Program Chairs

Program Committee

  • Nikolaj Bjørner, Microsoft, USA
  • Martin Blicha, Argot Collective, Switzerland
  • Emanuele De Angelis, CNR-IASI, Italy
  • Catherine Dubois, ENSIIE-Samovar, France
  • Gidon Ernst, Ludwig Maximilian University of Munich, Germany
  • Grigory Fedyukovich, Florida State University, USA
  • Florian Frohn, RWTH Aachen University, Germany
  • Carsten Fuhs, Birkbeck, University of London, UK
  • Roberta Gori, University of Pisa, Italy
  • Hossein Hojjat, Tehran Institute for Advanced Studies, Iran
  • Bishoksan Kafle, APS, Australian Government / The University of Melbourne
  • Dale Miller, INRIA and LIX/Institut Polytechnique de Paris, France
  • David Monniaux, CNRS / VERIMAG, France
  • Jose F. Morales, IMDEA Software Research Institute, Spain
  • Gennaro Parlato, University of Molise, Italy
  • Sabina Rossi, Ca' Foscari University of Venice, Italy
  • Wim Vanhoof, University of Namur, Belgium
  • Germán Vidal, MiST, VRAIN, Polytechnic University of Valencia, Spain

Submission

Submission has to be done in one of the following formats:

  • Extended abstracts (from half to 3 pages), which describe work in progress or aim to initiate discussions.
  • Presentation-only papers, i.e., papers already submitted or presented at a conference or another workshop. Such papers can be submitted in any format, and will not be included in the workshop post-proceedings.
  • Regular papers (up to 12 pages plus bibliography in EPTCS format), which should present previously unpublished work (completed or in progress), including descriptions of research, tools, and applications.
  • Tool papers (up to 4 pages in EPTCS format), which can outline the theoretical framework, the architecture, the usage, and experiments of the tool.
All submitted papers will be refereed by the program committee and will be selected for inclusion in the program in accordance with the referee reports. At least one author of each accepted paper will be required to attend the workshop to present the contribution. If enough regular papers are accepted, both regular papers and extended abstracts will be published electronically. The publication of a paper is not intended to preclude later publication. Full versions of extended abstracts, or substantial revisions, may later be published elsewhere.

Papers must be submitted through the FLoC 2026 submission system.