Noninterference for free
Authors:
Open Access
- 29 August 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 101-113
Abstract
The dependency core calculus (DCC) is a framework for studying a variety of dependency analyses (e.g., secure information flow). The key property provided by DCC is noninterference, which guarantees that a low-level observer (attacker) cannot distinguish high-level (protected) computations. The proof of noninterference for DCC suggests a connection to parametricity in System F, which suggests that it should be possible to implement dependency analyses in languages with parametric polymorphism. We present a translation from DCC into Fω and prove that the translation preserves noninterference. To express noninterference in Fω, we define a notion of observer-sensitive equivalence that makes essential use of both first-order and higher-order polymorphism. Our translation provides insights into DCC's type system and shows how DCC can be implemented in a polymorphic language without loss of the noninterference (security) guarantees available in DCC. Our contributions include proof techniques that should be valuable when proving other secure compilation or full abstraction results.Keywords
Funding Information
- National Science Foundation (CCF-1422133)
This publication has 19 references indexed in Scilit:
- Noninterference for free2015
- Verifying an Open Compiler Using Multi-language Semantics2014
- An equivalence-preserving CPS translation via multi-language semantics2011
- Relational Parametricity for a Polymorphic Linear Lambda CalculusLecture Notes in Computer Science, 2010
- Parametricity, type equality, and higher-order polymorphismJournal of Functional Programming, 2010
- Proving Noninterference by a Fully Complete Translation to the Simply Typed lambda-calculusLogical Methods in Computer Science, 2008
- Step-Indexed Syntactic Logical Relations for Recursive and Quantified Types2006
- Translating dependency into parametricityACM SIGPLAN Notices, 2004
- Protection in programming-language translations1998
- Notions of computation and monadsInformation and Computation, 1991