VerCors: Verification of Concurrent Data Structures
Funded by: European Research Council
Duration: February 2011 until February 2016
Contact: prof.dr. Marieke Huisman
Publications: in EPrints
High-level description: in dutch, in english
Other documents: overview presentation
Summary of the project
Increasing performance demands, application complexity and explicit multi-core parallelism makes concurrency omnipresent in software applications. However, due to the complex interferences between threads in an application, concurrent software is also notoriously hard to get correct. Instead of spending large amounts of money to fix incorrect software, formal techniques are needed to reason about the behaviour of concurrent programs.
In earlier work, we developed a variant of permission-based separation logic that is particularly suited to reason about multithreaded Java programs with dynamic thread creation and termination, and reentrant locks. The VerCors project will extend expressiveness of the logic, to specify and verify concurrent data structures. The verification logic will be parameterised over the locking policy, so that a high-level specification of the behaviour of a data structure can be reused for different implementations. Thus the implementation of a concurrent data structure can be changed, without affecting correctness of the applications using it.
The logic will also be parameterised with concurrency and synchronisation primitives, so that a logic for a different programming language can be defined as an instance of the general logic. It will also be adapted to reason about programs with benign data races, i.e., data races where the same value is written simultaneously by different threads. Also techniques to generate part of the specifications automatically will be developed. Finally, the logic will be adapted to a distributed setting, where data consistency between the different sites has to be maintained.
All results are integrated in a tool set that is available online. The tool generates and proves proof obligations automatically. It will be validated on realistic case studies.
For more general information about the project, see the overview presentation of the project, and a high-level description (in Dutch or in English). For more detailed information about the project, see the original project proposal: part B1 and part B2.
The VerCors project is supported by the European Resource Council
Research teamThe following people are involved in the project:
- prof.dr. Marieke Huisman (project leader)
- Afshin Amighi MSc
- dr. Stefan Blom
- dr. Wojciech Mostowski
- Marina Zaharieva-Stojanovski MSc
Relevant Background Publications
- Christian Haack, Marieke Huisman, and Clément Hurlin. Permission-based separation logic for Java. Manuscript, 2010.
- Clément Hurlin. Specification and Verification of Multithreaded Object-Oriented Programs with Separation Logic. PhD thesis, Université Nice - Sophia Antipolis, September 2009.
- Christian Haack and Clément Hurlin. Resource usage protocols for iterators. Journal of Object Technology, 8(4), 2009.
- Christian Haack, Marieke Huisman, and Clément Hurlin. Reasoning about Java's Reentrant Locks. In Grama Ramalingam, editor, Asian Symposium on Programming Languages and Systems (APLAS'08), volume 5356 of Lecture Notes in Computer Science, pages 171-187. Springer-Verlag, 2008.
- Christian Haack and Clément Hurlin. Separation Logic Contracts for a Java-like Language with Fork/Join. In Jose Meseguer and Grigore Rosu, editors, International Conference on Algebraic Methodology and Software Technology (AMAST'08), volume 5140 of Lecture Notes in Computer Science, pages 199-215. Springer-Verlag, July 2008.
- Jeroen Meijer. Formal Specification of LinkedBlockingQueue Using Concurrent Separation Logic. Bachelor assignment, 2011.