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 2021 in Luxembourg, Luxembourg (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.

CHC Competition

HCVS 2022 will host the 5th competition on constraint Horn clauses ( CHC-COMP ), which will compare state-of-the-art tools for CHC solving for performance and effectiveness on a set of publicly available benchmarks. A report on the 5th CHC-COMP will be part of the workshop's proceedings. The report also contains tool descriptions of the participating solvers.

Invited speakers

  • Elvira Albert (Instituto de Tecnología del Conocimiento, and Complutense University of Madrid, Spain).
    Superoptimization of (Optimized) Smart Contracts

    Superoptimization is a compilation technique that searches for the optimal sequence of instructions semantically equivalent to a given (loop-free) initial sequence. This talks overviews our approach for super-optimization of smart contracts based on Max-SMT which is split into two main phases: (i) the extraction of a functional specification from the basic blocks of the smart contract, which is simplified using rules that capture the semantics of the arithmetic, bit-wise, relational oper- ations, etc. and (ii) the synthesis of optimized blocks which, by means of an efficient Max-SMT encoding, finds the bytecode blocks with minimal cost (according to the selected optimization criteria) and whose functional specification is equal (modulo commutativity) to the extracted one. Our experiments on randomly selected real contracts achieve important gains in gas and in bytes-size over code already optimized by solc.

  • Robert Glück (University of Copenhagen, Denmark).
    Principles of Reversible Computation

    We highlight the principles and main ideas of reversible computing viewed from a programming language perspective with a focus on clean reversible languages. For a programmable computing system to be reversible, both the underlying control logic and each instruction must be deterministic in both the forward and backward directions. We relate reversible computing to inverse computation and program inversion, to mainstream computing and the Futamura projections. By exhibiting the principles of reversible computing, we hope to provide a better understanding of the potential and limitations of this unconventional computing paradigm.

  • Bruno Blanchet (INRIA, Paris, France).
    The security protocol verifier ProVerif and its Horn clause resolution algorithm

    ProVerif is a widely used security protocol verifier. Internally, ProVerif uses an abstract representation of the protocol by Horn clauses and a resolution algorithm on these clauses, in order to prove security properties of the protocol or to find attacks. In this talk, we will present an overview of ProVerif and discuss in more detail the specificities of its resolution algorithm, related to the particular application domain and the particular clauses that ProVerif generates. In particular, we will cover recent extensions done with Vincent Cheval and Véronique Cortier (paper to appear at IEEE Security and Privacy 2022).

  • Aws Albarghouthi (University of Wisconsin–Madison, USA).
    Privacy and Automated Verification

    Algorithms consume our personal data and make decisions that affect our lives. How can we make sure that these algorithms do not leak our private data? How do we make sure they are fair? Over the past few years, we have been exploring this question through the lens of automated verification and synthesis. In this talk, I will discuss automated techniques for proving the correctness of randomized algorithms and apply them to differentially private mechanisms, which have seen numerous applications in privacy-preserving data analysis as well as ensuring forms of fairness in decision-making. Technically, I will demonstrate how powerful SMT solvers, which revolutionized automated verification of traditional programs, can be applied to reasoning about randomized algorithms.

Accepted Papers

  • Leonardo Alt, Martin Blicha, Antti Hyvärinen and Natasha Sharygina
    SolCMC: Solidity Compiler’s Model Checker (Presentation-only paper)
  • Muhammad Usama Sardar, Said Musaev and Christof Fetzer
    Demystifying Attestation in Intel Trust Domain Extensions via Formal Verification (Presentation-only paper)
  • Elvira Albert, Miguel Isabel, Clara Rodríguez-Núñez and Albert Rubio
    Towards using Horn Clauses in Zero-Knowledge Protocols
  • Hossein Hojjat and Philipp Rümmer
    Opti-Rica: Towards an Efficient Optimizing Horn Solver
  • Tewodros A. Beyene and Amit Sahu
    Practical Analysis of Neural Networks Using Constraints Solving
  • Emanuele De Angelis, Fabio Fioravanti, Alberto Pettorossi and Maurizio Proietti
    Contract Verification using Catamorphisms and Constrained Horn Clause Transformations

Program Chairs

Program Committee

Submission

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

  • 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), including the papers written by the CHC-COMP participants, which can outline the theoretical framework, the architecture, the usage, and experiments of the tool.
  • Extended abstracts (up to 3 pages in EPTCS format), 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.
  • Posters that are of interest to the workshop
All submitted papers will be refereed by the program committee and will be selected for inclusion in accordance with the referee reports. Accepted regular papers and extended abstracts will be published electronically as a volume in the Electronic Proceedings in Theoretical Computer Science (EPTCS) series, see http://www.eptcs.org/ (provided that enough regular papers are accepted). The publication of a paper is not intended to preclude later publication. Full versions of extended abstracts published in EPTCS, or substantial revisions, may later be published elsewhere.

Papers must be submitted through the EasyChair system using the web page: https://easychair.org/conferences/?conf=hcvs2022