Background

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.

Project

Understanding how (low level) concurrent programs work is difficult. The specification and verification tools developed in the project can prove programs correct, but explaining how the specifications work is again difficult. Part of those specifications is a careful accounting of which thread can read or write any memory location, encoded in the form of access permissions. The goal of the project is to visualize how these permissions and other pieces of information are exchanged between threads in order to show how the program works and why it is correct.

Practical Aspects

 Concretely, as the outcome of the project we would like to have a tool that can take a correctly specified program as input, and then visualise how permissions to access heap locations are exchanged during the execution of the program, in such a way that a programmer can get insight into why the program works correctly.