July 17, 2014 · Vienna, Austria
Most 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 workshop aims to bring together researchers working in the two communities of Constraint/Logic Programming (e.g., ICLP and CP) and Program Verification community (e.g., CAV, TACAS, and VMCAI) on the topic of Horn clause based analysis, verification and synthesis.
Horn clauses for verification and synthesis have been advocated by these two communities in different times and from different perspectives and this workshop is organized to stimulate interaction and a fruitful exchange and integration of experiences.
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 in various programming paradigms (e.g., imperative, object-oriented, functional, logic, higher-order, concurrent)
- Program synthesis
- Program testing
- Program transformation
- Constraint solving
- Type systems
- Case studies and tools
- Challenging problems
We solicit regular papers describing theory and implementation of Horn-clause based analysis, tool descriptions and extended abstracts describing work-in-progress, and finally also position papers covering previously published results that are of interest to the workshop.
- Daniel Kröning (University of Oxford)
Title: Proof and Refutations for Horn-clause Encodings of Reachability Problems
Abstract: 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.
- Michael Leuschel (Heinrich-Heine-Universität Düsseldorf)
Title: Towards Constraint-Solving over Higher-Order Unbounded Datatypes using Formal Methods Tools
Abstract: 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.
The proceedings of HCVS 2014 have been published as EPTCS 169.
9.00 - 10.15 (Location: FH, Seminarraum 134A)
Proof and Refutations for Horn-clause Encodings of Reachability Problems
10.15 - 10.45 Coffee Break
Technical Session 1 (Location: FH, Seminarraum 134A)
10.45 - 11.20 (35 minutes)
Hossein Hojjat, Philipp Ruemmer, Pavle Subotic and Wang Yi.
Horn Clauses for Communicating Timed Systems
11.20 - 11.55 (35 minutes)
Emanuele De Angelis, Fabio Fioravanti, Jorge A. Navas and Maurizio Proietti
Verification of Programs by Combining Iterated Specialization with Interpolation
11.55 - 12.30 (35 minutes)
Alan Perotti, Guido Boella and Artur D'Avila Garcez
Runtime Verification Through Forward Chaining
12.30 - 13.05 (35 minutes)
Ashutosh Gupta, Corneliu Popeea and Andrey Rybalchenko
Generalised Interpolation by Solving Recursion-Free Horn Clauses
13.00 - 14.30 Lunch
Invited talk (shared with VPT)
14.30 - 15.30 (Location: FH, Seminarraum 134A)
Michael Leuschel (Heinrich-Heine-Universität Düsseldorf)
Towards Constraint-Solving over Higher-Order Unbounded Datatypes using Formal Methods Tools
15.30 - 16.00 Coffee Break
Technical Session 2 (Location: FH, Seminarraum 134A)
16.00 - 16.35 (35 minutes)
Bishoksan Kafle and John P. Gallagher
Convex polyhedral abstractions, specialisation and property-based predicate splitting in Horn clause verification
16.35 - 17.10 (35 minutes)
Temesghen Kahsai, Pierre-Loic Garoche and Arie Gurfinkel
Synthesizing Modular Invariants for Synchronous Code
17.10 - 18.00
Final discussion and plans for future editions
- Elvira Albert (Complutense University of Madrid)
- Roberto Bagnara (University of Parma and BUGSENG)
- Nikolaj Bjorner (Microsoft Research) - chair
- Swarat Chaudhuri (Rice University)
- Gregory J. Duck (National University of Singapore)
- Fabio Fioravanti (University of Chieti-Pescara) - chair
- John Gallagher (Roskilde University and IMDEA)
- Arnaud Gotlieb (SIMULA Research Laboratory)
- Arie Gurfinkel (Software Engineering Institute, Carnegie Mellon University)
- Konstantin Korovin (Manchester University)
- Viktor Kuncak (EPFL)
- Ken McMillan (Microsoft Research)
- Jorge A. Navas (NASA)
- Corneliu Popeea (Technische Universität München)
- Maurizio Proietti (IASI-CNR, Italy)
- C. R. Ramakrishnan (University at Stony Brook)
- Grigore Rosu (University of Illinois at Urbana-Champaign)
- Philipp Ruemmer (Uppsala University, Department of Information Technology)
- Andrey Rybalchenko (Microsoft Research) - chair
- Valerio Senni (ALES srl) - chair
|Submission deadline:||May 25, 2014 *extended*|
|Workshop:||July 17, 2014 · Vienna, Austria|
Submission Format: up to 12 pages plus bibliography, in EPTCS format.
Original accepted papers will be published electronically as a volume in the Electronic Proceedings in Theoretical Computer Science (EPTCS) series, see http://www.eptcs.org/
Authors of accepted papers are required to ensure that at least one of them will be present at the workshop.
Papers must be submitted through the EasyChair system using the web page
Last update: Fabio Fioravanti 2/12/2014