Foundational and Compositional Verification of Layered Concurrent Objects
Compositionality is essential for managing complexity in verification of concurrent programs, especially when proof certificates are needed. An effective verification scheme is to divide programs into abstraction layers and verify by composing refinements between layers. However, vanilla verified layers come with \emph{global states} which severely limit their extensibility. This problem may be solved by dividing a layer into objects with \emph{encapsulated local states}. Although the idea has been successfully realized in the sequential setting, it remains unclear if it also works in a concurrent setting where function calls across layers are no longer atomic steps and foundational proofs are needed.
We propose an approach to foundational and compositional verification of concurrent objects organized into multiple layers. The central idea is to represent concurrent objects as \emph{open} labeled transition systems with \emph{encapsulated threads} and to adopt \emph{trace refinements} as a uniform notion of functional correctness which supports both \emph{vertical composition} (layered refinement) and \emph{horizontal composition} (extension of layer interfaces). Due to the operational nature of transition systems, it is straightforward to adopt traditional simulation techniques to produce foundational proof certificates. We implement this framework in the Rocq theorem prover and demonstrate its capability in foundational and compositional verification by verifying non-trivial lock-free concurrent data structures.
Wed 1 JulDisplayed time zone: Brussels, Copenhagen, Madrid, Paris change
11:00 - 12:30 | |||
11:00 22mTalk | A Complete Program Logic for Compositional LinearizabilityDistinguished paper award Technical Papers Eashan Hatti Yale University, Arthur Oliveira Vale Yale University, Zhongye Wang Yale University, Yueyang Feng Yale University, Zhong Shao Yale University | ||
11:22 22mTalk | Foundational and Compositional Verification of Layered Concurrent Objects Technical Papers | ||
11:45 22mTalk | Verifying wait-freedom for concurrent higher-order programs Technical Papers | ||
12:07 22mTalk | Vardalith: Hybrid Detection of Persistent Memory Concurrency Bugs Technical Papers João Gonçalves IST U. Lisboa & INESC-ID, Miguel Matos IST, INESC-ID, U. Lisboa, Rodrigo Rodrigues Instituto Superior Técnico, U. Lisboa & INESC-ID, José Fragoso Santos INESC-ID; Instituto Superior Técnico - University of Lisbon | ||