Beyond Labels: Permissiveness for Dynamic Information Flow Enforcement

Flow-sensitive labels used by dynamic enforcement mechanisms might themselves encode sensitive information, which can leak. Metalabels, employed to represent the sensitivity of labels, exhibit the same problem. This paper derives a new family of enforcers—k-Enf, for 2 ≤ k ≤ ∞—that uses label chains, where each label defines the sensitivity of its predecessor. These enforcers satisfy Block-safe Noninterference (BNI), which proscribes leaks from observing variables, label chains, and blocked executions. Theorems in this paper characterize where longer label chains can improve the permissiveness of dynamic enforcement mechanisms that satisfy BNI. These theorems depend on semantic attributes—k-precise, k-varying, and k-dependent—of such mechanisms, as well as on initialization, threat model, and lattice size.