Page 81 - DCAP516_COMPUTER_SECURITY

Unit 7: Designing Trusted Operating System

Obviously a total ordering is a special case of a lattice. For any two elements a ∈ S, b ∈ S is a set Notes
with a total ordering, let l = min(a, b) and u = max(a, b) to satisfy the lattice property.
The most common example of a lattice is the relationship of divisibility in the set of positive
integers. Note that addition of zero to the set ruins the divisibility property.
The divisibility operator is denoted by the symbol “|”; we say a | b if the integer a divides the
integer b, equivalently that the integer b is an integer multiple of the integer a. Let’s verify that
this operator on the set of positive integers satisfies the requirements of a partial order.
1. Both equality and inequality are defined for the set of integers.

2. We are given the ordering operator “|”.
3. The operator is transitive.
For any a ∈ S, b ∈ S, c ∈ S, if a | b and b | c, then a | c. The proof is easy.
If b | c, then there exists an integer q such that c = q • b.

If a | b, then there exists an integer p such that b = p • a.
Thus c = q • b = c = q • p·a = (q • p) • a, and a | c.
4. The operator is antisymmetric.
For any a ∈ S, b ∈ S, if a | b and b | a, then a = b.

If the divisibility operator imposed a total order on the set of integers, then it would be the case
that for any two integers a and b, that either a | b or b | a. It is easy to falsify this claim by picking
two prime numbers; say a = 5 and b = 7. Admittedly, there are many pairs of integers that are not
3
2
prime and still falsify the claim (27 = 3 and 25 = 5 ), but one set is enough. We now ask if the set
of integers under the divisibility operator forms a lattice.
It turns out that the set does form a lattice as it is quite easy to form the lower and upper bounds
for any two integers. Let a ∈ S and b ∈ S, where S is the set of positive integers.

A lower bound that always works is l = 1 and an upper bound that always works is u = a • b.
Admittedly, these are not the greatest lower bound or least upper bound, but they show that
such bounds do exist. To illustrate the last statement, consider this example.
a = 4 and b = 6, with a • b = 24.
The greatest lower bound is l = 2, because 2 | 6 and 3 | 6, and the number 2 is the largest integer
to have that property.
The least upper bound is u = 12, because 4 | 12 and 6 | 12, and the number 12 is the smallest
integer to have that property.

The lattice model has been widely accepted as a model for security systems because it incorporates
two of the basic requirements.
1. There is a sense of the idea that some data are more sensitive than other data.

2. It is not always possible to rank the sensitivity of two distinct sets of data.
2
The Figure 7.1 shows a lattice model based on the factors of the number 60 = 2 • 3 • 5.

LOVELY PROFESSIONAL UNIVERSITY 75