Multi-level Security

Lecturer: Professor Fred B. Schneider

Lecture notes by Michael Clarkson
based in part on notes by Lynette I. Millett
from lectures by Professor Fred B. Schneider


This lecture is based in part on:

Pierangela Samarati and Sabrina De Capitani di Vimercati.  Access Control:  Policies, Models, and Mechanisms.  In Foundations of Security Analysis and Design: Tutorial Lectures, Lecture Notes in Computer Science, vol. 2171, p. 137--193, 2001.

Note:  If your browser does not support Unicode, you will not be able to view this page correctly.  Your browser must be able to render the following symbols: ⊆ (subset or equal), ≤ (less than or equal), ≠ (not equal).


In national security and military environments, documents are labeled according to their sensitivity levels.  In the US, these range from Unclassified (anyone can see this) to Confidential to Secret and finally (we believe) to Top Secret; other countries use similar classifications.  These levels correspond to the risk associated with release of the information.   

But it is not sufficient to use only sensitivity levels to classify objects if one wants to comply with the need to know principle:  access to information should only be granted if it is necessary to perform one's duties.  Compartments are used to handle this decomposition of information.  Every object is associated with a set of compartments (e.g. crypto, nuclear, biological, reconnaissance, etc.).  An object associated with {crypto, nuclear} may be accessed only by subjects who need to know about both cryptography and nuclear weapons.

A label is a pair of a sensitivity level and a set of compartments.  A document might have the label (Top Secret, {crypto,nuclear}) if it contained extremely sensitive information regarding cryptography and nuclear weapons.  In practice, each paragraph in a document is assigned a set of compartments and a sensitivity.  The classification of the entire document would then be the most restrictive classification given to a paragraph in that document.

Users are also labelled according to their security clearance.  A user's clearance, just like a document's label, is a pair of a sensitivity level and a set of compartments.

Given two labels L1 = (S1, C1) and L2 = (S2, C2), we write that L1 ≤  L2---meaning that L1 is no more restrictive than L2---when

Notice that ≤  is a partial order:  it is possible to have two labels that are incomparable (e.g. (secret, {crypto}) vs. (top secret, {nuclear})) according to ≤ .  The following diagram depicts some of the ≤  relationships as a lattice, where a line from a label L1 lower in the lattice to a label L2 higher in the lattice denotes that L1 ≤  L2. 

Bell and LaPadula (1973) gave a formal, mathematical model of multi-level security.  This model enforces the BLP policy:

Information cannot leak to subjects who are not cleared for the information.

Let L(X) denote the label of an entity X, where an entity is either a subject or an object.  The BLP security conditions are:

Do the BLP security conditions enforce the BLP policy?  First, note that a subject can never directly read an object for which it is not cleared.  The first condition guarantees this.  Second, a subject must never be able to learn information about some highly-labeled object O by reading another low-labeled object O'.  Note that this is only possible if some other subject first reads O then writes O'.  By the two conditions, a read then write by S entails L(O) ≤  L(S) ≤  L(O').  But then O actually has a lower label than O', so no information can have leaked. 

The above was considered a significant result when it first was proved. But there are still some problems with the BLP formulation of MLS.  These include:

Some real-world systems, including SELinux and TrustedBSD, combine MAC and DAC policies.  In such cases, an operation is allowed only if both the MAC policy and the DAC policy both permit the operation.