RefinedC: automating the foundational verification of C code with refined ownership types
Authors:
Open Access
- 18 June 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 158-174
Abstract
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 RefinedC, which combines ownership types (for modular reasoning about shared state and concurrency) with refinement types (for encoding precise invariants on C data types and Hoare-style specifications for C functions). RefinedC is both automated (requiring minimal user intervention) and 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 Lithium. By restricting to a carefully chosen (yet expressive) fragment of separation logic, Lithium supports predictable, automatic, goal-directed proof search without backtracking. We demonstrate the effectiveness of RefinedC on a range of representative examples of C code.Keywords
Funding Information
- European Research Council (683289 and 789108)
- Engineering and Physical Sciences Research Council (EP/K008528/1)
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (016.Veni.192.259)
This publication has 88 references indexed in Scilit:
- An overview of the K semantic frameworkThe Journal of Logic and Algebraic Programming, 2010
- Mind the Gap2009
- VCC: A Practical System for Verifying Concurrent C2009
- Oracle Semantics for Concurrent Separation Logic2008
- Formal Verification of a C-like Memory Model and Its Uses for Verifying Program TransformationsJournal of Automated Reasoning, 2008
- Dependent ML An approach to practical programming with dependent typesJournal of Functional Programming, 2007
- Safe manual memory management in CycloneScience of Computer Programming, 2006
- A type system for certified binariesACM Transactions on Programming Languages and Systems, 2005
- Programming in Lygon: An overview1996
- Logic Programming with Focusing Proofs in Linear LogicJournal of Logic and Computation, 1992