Rely/Guarantee Reasoning for Noninterference in Non-Blocking Algorithms
Nicholas Coughlin, Graeme Smith · 2020
Noninterference characterizes a security property in which an attacker cannot determine the inputs to a system based on outputs of a lower classification. Value-dependent noninterference enables the analysis of systems in which these classifications may depend on the system's state and evolve throughout execution. Existing approaches to enforcing such a property for concurrent systems are constrained in their capability to express how the concurrent components modify shared variables and, therefore, the value-dependent classifications. Such approaches typically make use of externally verified annotations or coarse locking primitives to express limited constraints on variables, such as read and write permissions. Consequently, these techniques are insufficient for the analysis of programs that feature complex concurrent behaviours or require fine-grained synchronisation, as seen in non-blocking algorithms. This paper presents a compositional logic for enforcing value-dependent noninterference properties for complex concurrent algorithms, including non-blocking algorithms. It uses rely/guarantee reasoning to establish how classifications may be modified by concurrent components. Additionally, the logic allows for the specification of security policies at a component level and ensures their valid composition. These results have been formalised in Isabelle/HOL.