RefinedC: Automating the Foundational Verification of C Code with Refined Ownership Types
Fri 25 Jun 2021 02:00 - 02:05 at PLDI-B - Talks 4B: Concurrency, Compilation, and Debugging
Given the central role that C continues to play in systems software, and the difficulty of writing safe and correct C code, it remains a grand challenge to develop effective formal methods for verifying C programs.
In this paper, we propose a new approach to this problem: a type system we call \textbf{RefinedC}, which combines \emph{ownership types} (for modular reasoning about shared state and concurrency) with \emph{refinement types} (for encoding precise invariants on C data types and Hoare-style specifications for C functions).
RefinedC is both \emph{automated} (requiring minimal user intervention) and \emph{foundational} (producing a proof of program correctness in Coq), while at the same time handling a range of low-level programming idioms such as pointer arithmetic.
In particular, following the approach of RustBelt, the soundness of the RefinedC type system is justified semantically by interpretation into the Coq-based Iris framework for higher-order concurrent separation logic.
However, the typing rules of RefinedC are also designed to be encodable in a new ``separation logic programming'' language we call \textbf{Lithium}.
By restricting to a carefully chosen (yet expressive) fragment of separation logic, Lithium supports predictable, automatic, goal-directed proof search \emph{without backtracking}.
We demonstrate the effectiveness of RefinedC on a range of representative examples of C code.
Thu 24 JunDisplayed time zone: Eastern Time (US & Canada) change
13:30 - 14:05 | |||
13:30 5mTalk | Mirror: Making Lock-Free Data Structures Persistent PLDI DOI | ||
13:35 5mTalk | Fluid: A Framework for Approximate Concurrency via Controlled Dependency Relaxation PLDI Huaipan Jiang Pennsylvania State University, Haibo Zhang Pennsylvania State University, Xulong Tang University of Pittsburgh, Vineetha Govindaraj Pennsylvania State University, Jack Sampson Pennsylvania State University, Mahmut Taylan Kandemir Pennsylvania State University, Danfeng Zhang Pennsylvania State University DOI | ||
13:40 5mTalk | Frequent Background Polling on a Shared Thread, using Light-Weight Compiler Interrupts PLDI Nilanjana Basu University of Illinois at Chicago, Claudio Montanari University of Illinois at Chicago, Jakob Eriksson University of Illinois at Chicago DOI | ||
13:45 5mTalk | Alive2: Bounded Translation Validation for LLVM PLDI Nuno P. Lopes Microsoft Research, Juneyoung Lee Seoul National University, Chung-Kil Hur Seoul National University, Zhengyang Liu University of Utah, John Regehr University of Utah DOI Pre-print | ||
13:50 5mTalk | Incremental Whole-Program Analysis in Datalog with Lattices PLDI Tamás Szabó JGU Mainz; Workday, Sebastian Erdweg JGU Mainz, Gábor Bergmann Budapest University of Technology and Economics; IncQuery Labs DOI | ||
13:55 5mTalk | Logical Bytecode Reduction PLDI Christian Gram Kalhauge University of California at Los Angeles; Technical University of Denmark, Jens Palsberg University of California at Los Angeles DOI | ||
14:00 5mTalk | RefinedC: Automating the Foundational Verification of C Code with Refined Ownership Types PLDI Michael Sammler MPI-SWS, Rodolphe Lepigre MPI-SWS, Robbert Krebbers Radboud University Nijmegen, Kayvan Memarian University of Cambridge, Derek Dreyer MPI-SWS, Deepak Garg MPI-SWS DOI |
Fri 25 JunDisplayed time zone: Eastern Time (US & Canada) change
01:30 - 02:05 | |||
01:30 5mTalk | Mirror: Making Lock-Free Data Structures Persistent PLDI DOI | ||
01:35 5mTalk | Fluid: A Framework for Approximate Concurrency via Controlled Dependency Relaxation PLDI Huaipan Jiang Pennsylvania State University, Haibo Zhang Pennsylvania State University, Xulong Tang University of Pittsburgh, Vineetha Govindaraj Pennsylvania State University, Jack Sampson Pennsylvania State University, Mahmut Taylan Kandemir Pennsylvania State University, Danfeng Zhang Pennsylvania State University DOI | ||
01:40 5mTalk | Frequent Background Polling on a Shared Thread, using Light-Weight Compiler Interrupts PLDI Nilanjana Basu University of Illinois at Chicago, Claudio Montanari University of Illinois at Chicago, Jakob Eriksson University of Illinois at Chicago DOI | ||
01:45 5mTalk | Alive2: Bounded Translation Validation for LLVM PLDI Nuno P. Lopes Microsoft Research, Juneyoung Lee Seoul National University, Chung-Kil Hur Seoul National University, Zhengyang Liu University of Utah, John Regehr University of Utah DOI Pre-print | ||
01:50 5mTalk | Incremental Whole-Program Analysis in Datalog with Lattices PLDI Tamás Szabó JGU Mainz; Workday, Sebastian Erdweg JGU Mainz, Gábor Bergmann Budapest University of Technology and Economics; IncQuery Labs DOI | ||
01:55 5mTalk | Logical Bytecode Reduction PLDI Christian Gram Kalhauge University of California at Los Angeles; Technical University of Denmark, Jens Palsberg University of California at Los Angeles DOI | ||
02:00 5mTalk | RefinedC: Automating the Foundational Verification of C Code with Refined Ownership Types PLDI Michael Sammler MPI-SWS, Rodolphe Lepigre MPI-SWS, Robbert Krebbers Radboud University Nijmegen, Kayvan Memarian University of Cambridge, Derek Dreyer MPI-SWS, Deepak Garg MPI-SWS DOI |