Visible to the public Transparent IFC Enforcement: Possibility and (In)Efficiency Results

TitleTransparent IFC Enforcement: Possibility and (In)Efficiency Results
Publication TypeConference Paper
Year of Publication2020
AuthorsAlgehed, M., Flanagan, C.
Conference Name2020 IEEE 33rd Computer Security Foundations Symposium (CSF)
Date Publishedjun
Keywordsblack-box, black-box enforcement, Browsers, composability, computational complexity, Computer languages, efficiency, faceted secure multiexecution, FlowFox browser, FSME, IFC community, Information Flow Control, Lattices, memory overhead, Metrics, Multiple Facets, no-write-down no-read-up style security policy, noninterference, polynomial time, programming languages, pubcrawl, real-world programs, resilience, Resiliency, Runtime, secure information flow control, Secure Multi-Execution, secure programs, security, security condition, security lattice, security of data, Semantics, SME family, termination insensitive noninterference, third-party systems, transparency, transparent enforcement, transparent IFC enforcement, white box, White Box Security, white-box

Information Flow Control (IFC) is a collection of techniques for ensuring a no-write-down no-read-up style security policy known as noninterference. Traditional methods for both static (e.g. type systems) and dynamic (e.g. runtime monitors) IFC suffer from untenable numbers of false alarms on real-world programs. Secure Multi-Execution (SME) promises to provide secure information flow control without modifying the behaviour of already secure programs, a property commonly referred to as transparency. Implementations of SME exist for the web in the form of the FlowFox browser and as plug-ins to several programming languages. Furthermore, SME can in theory work in a black-box manner, meaning that it can be programming language agnostic, making it perfect for securing legacy or third-party systems. As such SME, and its variants like Multiple Facets (MF) and Faceted Secure Multi-Execution (FSME), appear to be a family of panaceas for the security engineer. The question is, how come, given all these advantages, that these techniques are not ubiquitous in practice? The answer lies, partially, in the issue of runtime and memory overhead. SME and its variants are prohibitively expensive to deploy in many non-trivial situations. The natural question is why is this the case? On the surface, the reason is simple. The techniques in the SME family all rely on the idea of multi-execution, running all or parts of a program multiple times to achieve noninterference. Naturally, this causes some overhead. However, the predominant thinking in the IFC community has been that these overheads can be overcome. In this paper we argue that there are fundamental reasons to expect this not to be the case and prove two key theorems: (1) All transparent enforcement is polynomial time equivalent to multi-execution. (2) All black-box enforcement takes time exponential in the number of principals in the security lattice. Our methods also allow us to answer, in the affirmative, an open question about the possibility of secure and transparent enforcement of a security condition known as Termination Insensitive Noninterference.

Citation Keyalgehed_transparent_2020