SecurePtrs: Proving Secure Compilation with Data-Flow Back-Translation and Turn-Taking Simulation
Preprint
Abstract
Proving secure compilation of partial programs typically requires back-translating an attack against the compiled program to an attack against the source program. To prove back-translation, one can syntactically translate the target attacker to a source one -- i.e., syntax-directed back-translation -- or show that the interaction traces of the target attacker can also be emitted by source attackers -- i.e., trace-directed back-translation. Syntax-directed back-translation is not suitable when the target attacker may use unstructured control flow that the source language cannot directly represent. Trace-directed back-translation works with such syntactic dissimilarity because only the external interactions of the target attacker have to be mimicked in the source, not its internal control flow. Revealing only external interactions is, however, inconvenient when sharing memory via unforgeable pointers, since information about shared pointers stashed in private memory is not present on the trace. This made prior proofs unnecessarily complex, since the generated attacker had to instead stash all reachable pointers. In this work, we introduce more informative *data-flow traces*, combining the best of syntax- and trace-directed back-translation in a simpler technique that handles both syntactic dissimilarity and memory sharing well, and that is proved correct in Coq. Additionally, we develop a novel *turn-taking simulation* relation and use it to prove a recomposition lemma, which is key to reusing compiler correctness in such secure compilation proofs. We are the first to mechanize such a recomposition lemma in the presence of memory sharing. We use these two innovations in a secure compilation proof for a code generation compiler pass between a source language with structured control flow and a target language with unstructured control flow, both with safe pointers and components.Keywords
All Related Versions
This publication has 45 references indexed in Scilit:
- Verified secure compilation for mixed-sensitivity concurrent programsJournal of Functional Programming, 2021
- Journey Beyond Full Abstraction: Exploring Robust Property Preservation for Secure Compilation2019
- Temporal Safety for Stack Allocated Memory on Capability Machines2019
- Secure Compilation of Side-Channel Countermeasures: The Case of Cryptographic “Constant-Time”2018
- A Logic of Programs with Interface-Confined Code2015
- Protected Software Module Architectures2013
- A Formally Verified Compiler Back-endJournal of Automated Reasoning, 2009
- Formal Verification of a C-like Memory Model and Its Uses for Verifying Program TransformationsJournal of Automated Reasoning, 2008
- A Fully Abstract Trace Semantics for General References2007
- Security types preserving compilationComputer Languages, Systems & Structures, 2007