City Research Online

A Quantale of Information

Hunt, S. ORCID: 0000-0001-7255-4465 and Sands, D. (2021). A Quantale of Information. 2021 IEEE 34th Computer Security Foundations Symposium (CSF), 1, pp. 358-372. doi: 10.1109/CSF51468.2021.00031 ISSN 2374-8303

Abstract

Information flow properties are the semantic cornerstone of a wide range of program transformations, program analyses, and security properties. The variety of information that can be transmitted from inputs to outputs in a deterministic system can be captured by representing information as equivalence relations over the sets of possible values, using an equivalence relation on the input domain to model what may be learned, and an equivalence relation on the output to model what maybe observed. The set of equivalence relations over a given set of values form a lattice, where the partial order models containment of information, and lattice join models the effect of combining information. This elegant and general structure is sometimes referred to as the lattice of information.In this paper we identify an abstraction of information flow which has not been studied previously, namely disjunctive dependency(depending on x or y, as distinct from depending on both x and y). We argue that this refines the space of semantic models for dependency in a way which is both interesting inits own right and which has applications in security settings of practical interest (in particular, where so-called “Chinese wall policies” are in effect).To model disjunctive dependency we introduce a nontrivial generalisation of the lattice of information in the form of a richer structure, built on sets of equivalence relations closed under a novel condition called tiling-closure. This structure forms a quantale - a lattice equipped with a tensor operation - in which lattice join corresponds to disjunctive combination of information, and tensor corresponds to conjunctive combination. Using this we generalise the definition of information flow properties, and show that the definition has the key properties needed to support compositional reasoning about programs.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: © 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Publisher Keywords: dependency analysis, information flow, noninterference, security policy
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Z Bibliography. Library Science. Information Resources > Z665 Library Science. Information Science
Departments: School of Mathematics, Computer Science & Engineering > Computer Science > Software Reliability
Date available in CRO: 26 Jul 2021 13:53
Date deposited: 26 July 2021
Date of acceptance: 11 May 2021
Date of first online publication: 21 June 2021
URI: https://openaccess.city.ac.uk/id/eprint/26499
[img]
Preview
Text - Accepted Version
Download (490kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login