Violet: A Logical Framework for Information Security via Possibilistic Conditional Independence
Language-based information flow control is varied by necessity: no single security notion fits every setting. Perfect security forbids all flow from secret to public, but real systems must release information in controlled ways, and the appropriate declassification policies depend on the application context. This diversity of definitions is matched by a proliferation of verification methods, from type systems and logical relations to bisimulations, relational program logics, and hyperlogics.
Our thesis is that underneath this variety sits a single notion: Conditional independence between secret and public information. As a conditional version of Sutherland’s non-deducibility, conditional independence captures perfect security, generalizes cleanly to declassification, and applies uniformly to nondeterministic programs. We realize this potential by internalizing conditional independence in a modal separation logic, Violet. Reading the separating conjunction as independence and a partitioning modality as conditioning, Violet becomes at once a language for specifying security policies and a proof system for verifying programs against them. Because assertions are predicates over sets of states, reasoning stays unary in feel despite a relational target. From a small set of general-purpose rules over these connectives, we specify and verify perfect security and several declassification policies across deterministic and nondeterministic programs, and we recover a standard information flow type system as derived rules.