author: | Matthijs Roelink |
title: | Encoding Deadlock-Free Monitors in the VerCors Verification Tool |
keywords: | program verification |
topics: | Logics and semantics |
committee: | Marieke Huisman |
end: | June 2020 |
Description
When reasoning about concurrent programs, one important property is the absence of deadlocks. For locks, it is well-understood how to achieve this, by imposing an order on the locks. However, for monitors (i.e. the wait and notify constructs) it is less clear how this can be achieved.
Jafar Hamin and Bart Jacobs have proposed a technique to prove the absence of deadlocks for programs using monitors. Their technique uses the notion of obligations: a thread has an obligation if it still has to notify a waiting thread, and a program is only correct if all obligations are fulfilled. Their verification technique is encoded in the VeriFast program verifier. In this project, you are asked to investigate how to encode their verification technique for the VerCors program verifier, which is being developed in the FMT group.
The project would consist of the following steps:
- understand the technique as proposed by Hamin and Jacobs
- investigate how to encode this in the VerCors verifier
- implement the encoding
- validate the encoding on several examples
References
- Final paper (Digital version available here)