Published: 2nd December 2014
DOI: 10.4204/EPTCS.169
ISSN: 2075-2180

EPTCS 169

Proceedings First Workshop on
Horn Clauses for Verification and Synthesis
Vienna, Austria, 17 July 2014

Edited by: Nikolaj Bjørner, Fabio Fioravanti, Andrey Rybalchenko and Valerio Senni

Preface
Invited Presentation: Proof and Refutations for Horn-clause Encodings of Reachability Problems
Daniel Kröning
1
Invited Presentation: Towards Constraint-Solving over Higher-Order Unbounded Datatypes using Formal Methods Tools
Michael Leuschel
2
Verification of Programs by Combining Iterated Specialization with Interpolation
Emanuele De Angelis, Fabio Fioravanti, Jorge A. Navas and Maurizio Proietti
3
Synthesizing Modular Invariants for Synchronous Code
Pierre-Loic Garoche, Arie Gurfinkel and Temesghen Kahsai
19
Generalised Interpolation by Solving Recursion-Free Horn Clauses
Ashutosh Gupta, Corneliu Popeea and Andrey Rybalchenko
31
Horn Clauses for Communicating Timed Systems
Hossein Hojjat, Philipp Rümmer, Pavle Subotic and Wang Yi
39
Convex polyhedral abstractions, specialisation and property-based predicate splitting in Horn clause verification
Bishoksan Kafle and John P. Gallagher
53
Runtime Verification Through Forward Chaining
Alan Perotti, Guido Boella and Artur d'Avila Garcez
68

Preface

This volume contains the proceedings of HCVS 2014, the First Workshop on Horn Clauses for Verification and Synthesis which was held on July 17, 2014 in Vienna, Austria as a satellite event of the Federated Logic Conference (FLoC) and part of the Vienna Summer of Logic (VSL 2014).

HCVS 2014 was affiliated to the 26th International Conference on Computer Aided Verification (CAV 2014) and to the 30th International Conference on Logic Programming (ICLP 2014).

Most Program Verification and Synthesis problems of interest can be modeled directly using Horn clauses and many recent advances in the Constraint/Logic Programming and Program Verification communities have centered around efficiently solving problems presented as Horn clauses. Since Horn clauses for verification and synthesis have been advocated by these communities in different times and from different perspectives, the HCVS workshop was organized to stimulate interaction and a fruitful exchange and integration of experiences.

The workshop featured six regular papers and two invited talks by Daniel Kröning (University of Oxford) and Michael Leuschel (Heinrich-Heine-Universität Düsseldorf).

We are grateful to all the people involved in the organization of the events HCVS was colocated with. We also thank the Program Committee, the authors, the reviewers and all the workshop participants for their contribution to the success of HCVS 2014. Finally, we would like to thank EasyChair for providing us with a tool for handling submissions, and EPTCS for publishing the proceedings of the workshop.

Program Chairs

Program Committee


Proof and Refutations for Horn-clause Encodings of Reachability Problems

Daniel Kröning (University of Oxford)

The talk focuses on solving program reachability problems by means of a Horn-clause style program encoding and suitable decision procedures. We will first examine a way to construct the necessary invariants using a combination of abstract interpretation and DPLL-style satisfiability solving. We will then consider a technique for generating counterexamples, and ways how these counterexamples can be used for proof in a synergistic fashion. I will finally show an encoding for concurrent systems based on partial-order semantics.


Towards Constraint-Solving over Higher-Order Unbounded Datatypes using Formal Methods Tools

Michael Leuschel (Heinrich-Heine-Universität Düsseldorf)

We argue that formal methods such as B can be used to conveniently express a wide range of constraint satisfaction problems. We also show that some problems can be solved quite effectively by existing formal methods tools such as Alloy or ProB. We illustrate our claim on several examples. Our approach is particularly interesting when a high assurance of correctness is required. Indeed, validation and double checking of solutions is available for certain formal methods tools and formal proof can be applied to establish important properties or provide unambiguous semantics to problem specifications. The experiments also provide interesting insights about the effectiveness of existing formal method tools, and highlight interesting avenues for future improvement.