Concurrent abstraction layers are ubiquitous in modern computer systems because of the pervasiveness of multithreaded programming and multicore hardware. Abstraction layers are used to hide the implementation details (e.g., fine-grained synchronization) and reduce the complex dependencies among components at different levels of abstraction. Despite their obvious importance, concurrent abstraction layers have not been treated formally. This severely limits the applicability of layer-based techniques and makes it difficult to scale verification across multiple concurrent layers.
In this paper, we present CCAL—a fully mechanized programming toolkit developed under the CertiKOS project—for specifying, composing, compiling, and linking certified concurrent abstraction layers. CCAL consists of three technical novelties: a new game-theoretical, strategy-based compositional semantic model for concurrency (and its associated program verifiers), a set of formal linking theorems for composing multithreaded and multicore concurrent layers, and a new CompCertX compiler that supports certified thread-safe compilation and linking. The CCAL toolkit is implemented in Coq and supports layered concurrent programming in both C and assembly. It has been successfully applied to build a fully certified concurrent OS kernel with fine-grained locking.
Fri 22 JunDisplayed time zone: Eastern Time (US & Canada) change
14:00 - 15:40 | VerificationPLDI Research Papers at Grand Ballroom AB Chair(s): Adam Chlipala Massachusetts Institute of Technology, USA | ||
14:00 25mTalk | VeriPhy: Verified Controller Executables from Verified Cyber-Physical System Models PLDI Research Papers Brandon Bohrer , Yong Kiam Tan Carnegie Mellon University, USA, Stefan Mitsch Carnegie Mellon University, USA, Magnus O. Myreen Chalmers University of Technology, Sweden, André Platzer Carnegie Mellon University Media Attached | ||
14:25 25mTalk | Crellvm: Verified Credible Compilation for LLVM PLDI Research Papers Jeehoon Kang Seoul National University, Yoonseung Kim Seoul National University (South Korea), Youngju Song Seoul National University, Juneyoung Lee Seoul National University, Sanghoon Park Seoul National University, South Korea, Mark Dongyeon Shin Seoul National University, South Korea, Yonghyun Kim Seoul National University, South Korea, Sungkeun Cho Seoul National University, South Korea, Joonwon Choi Massachusetts Institute of Technology, USA, Chung-Kil Hur Seoul National University, Kwangkeun Yi Seoul National University Media Attached | ||
14:50 25mTalk | Certified Concurrent Abstraction Layers PLDI Research Papers Ronghui Gu Columbia University, Zhong Shao Yale University, Jieung Kim Yale University, USA, Xiongnan (Newman) Wu Yale University, Jérémie Koenig , Vilhelm Sjöberg Yale University, Hao Chen Yale University, David Costanzo Yale University, Tahina Ramananandro Microsoft Research, n.n. Media Attached | ||
15:15 25mTalk | Modularity for Decidability of Deductive Verification with Applications to Distributed Systems PLDI Research Papers Marcelo Taube Tel Aviv University, Israel, Giuliano Losa University of California at Los Angeles, USA, Kenneth L. McMillan Microsoft Research, Oded Padon Tel Aviv University, Mooly Sagiv Tel Aviv University, Sharon Shoham Tel Aviv university, James R. Wilcox University of Washington, Doug Woos University of Washington Media Attached | ||