Modular Verification of Safe Memory Reclamation in Concurrent Separation Logic
Formal verification is an effective method to address the challenge of designing correct and efficient concurrent data structures.
But verification efforts often ignore \emph{memory reclamation},
which involves nontrivial synchronization between concurrent accesses and reclamation.
When incorrectly implemented, it may lead to critical safety errors such as use-after-free and the ABA problem.
Semi-automatic safe memory reclamation schemes such as hazard pointers and RCU encapsulate the complexity of manual memory management in modular interfaces.
However, this modularity has not been carried over to formal verification.
We propose modular specifications of hazard pointers and RCU, and formally verify realistic implementations of them in concurrent separation logic.
Specifically, we design abstract predicates for hazard pointers that capture the meaning of \emph{validating} the protection of nodes,
and those for RCU that support \emph{optimistic traversal} to possibly retired nodes.
We demonstrate that the specifications indeed facilitate modular verification
in three criteria: compositional verification, general applicability, and easy integration.
In doing so, we present the first formal verification of Harris's list, the Harris-Michael list, the Chase-Lev deque, and RDCSS with reclamation.
We report the Coq mechanization of all our results in the Iris separation logic framework.
Fri 27 OctDisplayed time zone: Lisbon change
16:00 - 17:30 | |||
16:00 18mTalk | Verification-Preserving Inlining in Automatic Separation Logic Verifiers OOPSLA DOI | ||
16:18 18mTalk | Leaf: Modularity for Temporary Sharing in Separation Logic OOPSLA Travis Hance Carnegie Mellon University, Jon Howell VMware Research, Oded Padon VMware Research, Bryan Parno Carnegie Mellon University DOI | ||
16:36 18mTalk | Proof Automation for Linearizability in Separation Logic OOPSLA DOI Pre-print | ||
16:54 18mTalk | Modular Verification of Safe Memory Reclamation in Concurrent Separation Logic OOPSLA Jaehwang Jung KAIST, Janggun Lee KAIST, Jaemin Choi KAIST, Jaewoo Kim KAIST, Sunho Park KAIST, Jeehoon Kang KAIST DOI | ||
17:12 18mTalk | Functional collection programming with semi-ring dictionaries OOPSLA Amir Shaikhha University of Edinburgh, Mathieu Huot University of Oxford, Jaclyn Smith Oxford University, Dan Olteanu University of Zurich Link to publication DOI |