Devriese, Dominique and Patrignani, Marco and Piessens, Frank and Keuchel, Steven - Modular, Fully-abstract Compilation by Approximate Back-translation

lmcs:4011 - Logical Methods in Computer Science, October 25, 2017, Volume 13, Issue 4
Modular, Fully-abstract Compilation by Approximate Back-translation

Authors: Devriese, Dominique and Patrignani, Marco and Piessens, Frank and Keuchel, Steven

A compiler is fully-abstract if the compilation from source language programs to target language programs reflects and preserves behavioural equivalence. Such compilers have important security benefits, as they limit the power of an attacker interacting with the program in the target language to that of an attacker interacting with the program in the source language. Proving compiler full-abstraction is, however, rather complicated. A common proof technique is based on the back-translation of target-level program contexts to behaviourally-equivalent source-level contexts. However, constructing such a back- translation is problematic when the source language is not strong enough to embed an encoding of the target language. For instance, when compiling from STLC to ULC, the lack of recursive types in the former prevents such a back-translation. We propose a general and elegant solution for this problem. The key insight is that it suffices to construct an approximate back-translation. The approximation is only accurate up to a certain number of steps and conservative beyond that, in the sense that the context generated by the back-translation may diverge when the original would not, but not vice versa. Based on this insight, we describe a general technique for proving compiler full-abstraction and demonstrate it on a compiler from STLC to ULC. The proof uses asymmetric cross-language logical relations and makes innovative use of step-indexing to express the relation between a context and its approximate back-translation. The proof extends easily to common compiler patterns such as modular compilation and it, to the best of our knowledge, it is the first compiler full abstraction proof to have been fully mechanised in Coq. We believe this proof technique can scale to challenging settings and enable simpler, more scalable proofs of compiler full-abstraction.


Source : oai:arXiv.org:1703.09988
DOI : 10.23638/LMCS-13(4:2)2017
Volume: Volume 13, Issue 4
Published on: October 25, 2017
Submitted on: March 30, 2017
Keywords: Computer Science - Programming Languages


Share

Browsing statistics

This page has been seen 58 times.
This article's PDF has been downloaded 36 times.