Browse Prior Art Database

ON THE DERIVATION OF LATTICE STRUCTURED INFORMATION FLOW POLICIES

IP.com Disclosure Number: IPCOM000128261D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 5 page(s) / 22K

Publishing Venue

Software Patent Institute

Related People

Dorothy E. Denning: AUTHOR [+3]

Abstract

Recent research in computer systems security has focused on specifying and enforcing "information flow policies" - i.e., policies regulating information dissemination. It has been shown that lattice structured policies have properties which lead to simple and efficient enforcement mechanisms' (1,3,4,8,9]. The program certification mech-anism described in [41, for example, verifies that the flow of data through a program does not violate a given lattice structured policy. The lattice properties of the policy are exploited to construct an efficient mechanism that can easily be incorporated into the analysis phase of a compiler. tie have already argued intuitively that lattice structured flow policies follow naturally froiTi the semantics of information flow [3]. The objective o f this paper is to show further that lattice structured policies lose no generality. We shall g,ive a construction for transforming an arbitrary flow policy, satisfying minimal conditions, into a lattice while preserving the validity of all flows.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 26% of the total text.

Page 1 of 5

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON THE DERIVATION OF LATTICE STRUCTURED INFORMATION FLOW POLICIES

Dorothy E. Denning Purdue University

March 1976 CSD TR 180

Recent studies in secure computer svstems have shown that lattice structured information flow policies have properties Which lead to simple and efficient enforcement mechanisms. This Daper outlines a method for transforming nonlattice structured policies into lattices while Dreserving the validity of all~flows.

Key Words and Phrases: protection, security, information flow, security class, lattice

CR Categories: 4.35

1

2

Introduction Recent research in computer systems security has focused on specifying and enforcing "information flow policies" - i.e., policies regulating information dissemination. It has been shown that lattice structured policies have properties which lead to simple and efficient enforcement mechanisms' (1,3,4,8,9]. The program certification mech-anism described in [41, for example, verifies that the flow of data through a program does not violate a given lattice structured policy. The lattice properties of the policy are exploited to construct an efficient mechanism that can easily be incorporated into the analysis phase of a compiler.

tie have already argued intuitively that lattice structured flow policies follow naturally froiTi the semantics of information flow [3]. The objective o f this paper is to show further that lattice structured policies lose no generality. We shall g,ive a construction for transforming an arbitrary flow policy, satisfying minimal conditions, into a lattice while preserving the validity of all flows.

2. I.attice Properties

A lattice is a structure L (A, < is reflexive, transitive, and anti-symmetric; that is, for all a,b,c e A: 2

1.

(Equation Omitted)

1 1 Work reported herein was supnorted in nart by NSF Grant . GJ-43176.

2 2 Author's present address: Purdue University, Computer Sciences Dept., W. Lafayette, Ind. 47907.

Purdue University Page 1 Dec 31, 1976

Page 2 of 5

ON THE DERIVATION OF LATTICE STRUCTURED INFORMATION FLOW POLICIES

2.

3.

(Equation Omitted)

That + is a least upper bound operator on A implies that for each pair of elements a and b in A, there exists a unique element c E A (c a + b), such that:

1. a < c and b < c, and 2. a < d and b < d => c < d for all d c A. By extension, corresponding toany nonempty subset B {a 1 ...,a n of A, there is a unique element +B a I +a 2 +...+a n which is the least upper bound for the set. That is a greatest lower bound operator on A implies that for each pair of elements a and b in A, there exists a unique element e in A (e = a b) such that:

1. e < a and e < b, and

2. d < a and d < b => d < e for all d c A. By extension, corresponding toany subset B = (a I ...,a n I of A, there is a unique element *B = a I *a 2 *a n which is the greatest lower bound for the set.

An example of a lattice is derived from the subsets of a given finite set X: L j~'(X) , C,...