صفحه 1:
Chapter 27: Lattices
* Overview
* Definitions
* Lattices
¢ Examples
November 1, 2004 Introduction to Computer Slide #27-1
صفحه 2:
Overview
* Lattices used to analyze Bell-
LaPadula, Biba constructions
* Consists of a set and a relation
٠ Relation must partially order set
- Partial ordering < orders some, but
not all, elements of set
November 1, 2004 Introduction to Computer Slide #27-2
Security
eet آ
صفحه 3:
Sets and Relations
* Sset, R: Sx Srelation
-If a, be S, and (a, b) € R, write aRb
¢ Example
-Il={1, 2,3}; Riss
-R={(1, 1), (1, 2), (1, 3), (2, 2), (2,
3), (3, 3) }
- So we write 1 < 2 and 3 < 3 but not 3
<2
November 1, 2004 Introduction to Computer Slide #27-3
صفحه 4:
Relation Properties
* Reflexive
- Forall ae S, aRa
- On ], > وج ۲6۲60۷6 و1 1 > 1, 2 > 2,3 > 3
¢ Antisymmetric
- Forall a, be S, aRb* bRa=a=b
- On J, s is antisymmetric
¢ Transitive
- For all a, b, ce S, aRb * bRc= aRc
- On J, sis transitive as 1 = 2 and2 <3
means 1 <3
November 1, 2004 Introduction to Computer Slide #27-4
Security
eet آ
صفحه 5:
Bigger Example
* Cset of complex numbers
۰ 2 ع< و دن ع agt aj, apg ajintegers
eas, bif, and only if, ag s b, and a, < رط
*as_ bis reflexive, antisymmetric,
transitive
- As s is over integers, and a, , a,are
integers
November 1, 2004 Introduction to Computer Slide #27-5
Security
eet آ
صفحه 6:
Partial Ordering
* Relation R orders some members of
set S
- If all ordered, it’s total ordering
٠ Example
- < on integers is total ordering
- S, is partial ordering on C (because
neither 3+5i<,4+2inor 4+2i<,
3+5i holds)
November 1, 2004 Introduction to Computer Slide #27-6
Security
eet آ
صفحه 7:
Upper Bounds
*For a, be S, if uin S with aRu,
bRu exists, then u is upper bound
- Least upper if there is no t€ Ssuch
that aRt, bRt, and tRu
° Example
- For 1 + 57, 2 + 4ie€ C, upper bounds
include 2 + 51,3 + 8i and 9 + 1007
- Least upper bound of those is 2 + 5i
November 1, 2004 Introduction to Computer Slide #27-7
Security
eet آ
صفحه 8:
Lower Bounds
* For a, be S, if Jin S with /Ra, IRb
exists, then /is lower bound
- Greatest lower if there isno te S
such that tRa, tRb, and ۶
° Example
- For 1+ 5i 2 + 4ie€ C, lower bounds
include 0, -1 + 24,1 +17 and1+4i
- Greatest lower bound of those is 1 +
4
November 1, 2004 Introduction to Computer Slide #27-8
Security
eet آ
صفحه 9:
Lattices
* Set S, relation R
- Ris reflexive, antisymmetric,
transitive on elements of S
- For every s, t€ S, there exists a
greatest lower bound under R
- For every s, t€ S, there exists a least
upper bound under R
November 1, 2004 Introduction to Computer Slide #27-9
Security
eet آ
صفحه 10:
Example
۰» ح و ) 0,1,2 (: ۲۲ < < isa lattice
- Ris clearly reflexive,
antisymmetric, transitive on
elements of S
- Least upper bound of any two
elements of Sis the greater
- Greatest lower bound of any two
elements of S is the lesser
November 1, 2004 Introduction to Computer Slide #27-10
Security
eet آ
صفحه 11:
Picture
2
|
1
|
0
Arrows represent S; total ordering
November 1, 2004 Introduction to Computer Slide #27-11
Security
eet آ
صفحه 12:
Example
٠ 0, > form a lattice
- Ss, is reflexive, antisymmetric, and
transitive
* Shown earlier
- Least upper bound for a and b:
* Cp = max(ap, Dz), C, = Max(a, b); then c = c,+
cd
- Greatest lower bound for a and b:
* Cp = min(ag, D,), c,= min(a, b); then c= Cyt Gi
November 1, 2004 Introduction to Computer Slide #27-12
Security
eet آ
صفحه 13:
Picture
2+5 \
1+5i 2+4i
1+4
Arrows represent ع كك
November 1, 2004 Introduction to Computer Slide #27-13
Security
Pee ae A
