Citation: Verifying concurrent software using movers in CSPEC, 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2018), Oct. 2018, pp 306-322. (with Tej Chajed, M. Frans Kaashoek, and Nickolai Zeldovich).
Links: Acrobat
Email: blampson@microsoft.com. This paper is at http://www.research.microsoft.com.
Abstract:
Writing concurrent systems software is error-prone, because multiple processes or threads can interleave in many ways, and it is easy to forget about a subtle corner case. This paper introduces CSPEC, a framework for formal verification of concurrent software, which ensures that no corner cases are missed. The key challenge is to reduce the number of interleavings that developers must consider. CSPEC uses mover types to re-order commutative operations so that usually it’s enough to reason about only sequential executions rather than all possible interleavings. CSPEC also makes proofs easier by making them modular using layers, and by providing a library of reusable proof patterns. To evaluate CSPEC, we implemented and proved the correctness of CMAIL, a simple concurrent Maildir-like mail server that speaks SMTP and POP3. The results demonstrate that CSPEC’s movers and patterns allow reasoning about sophisticated concurrency styles in CMAIL.