Lattices: Chapter 27
اسلاید 1: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-1Chapter 27: LatticesOverviewDefinitionsLatticesExamples
اسلاید 2: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-2OverviewLattices used to analyze Bell-LaPadula, Biba constructionsConsists of a set and a relationRelation must partially order setPartial ordering < orders some, but not all, elements of set
اسلاید 3: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-3Sets and RelationsS set, R: S S relationIf a, b S, and (a, b) R, write aRbExampleI = { 1, 2, 3}; R is ≤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
اسلاید 4: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-4Relation PropertiesReflexiveFor all a S, aRaOn I, ≤ is reflexive as 1 ≤ 1, 2 ≤ 2, 3 ≤ 3AntisymmetricFor all a, b S, aRb bRa a = bOn I, ≤ is antisymmetricTransitiveFor all a, b, c S, aRb bRc aRcOn I, ≤ is transitive as 1 ≤ 2 and 2 ≤ 3 means 1 ≤ 3
اسلاید 5: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-5Bigger ExampleC set of complex numbersa C a = aR + aIi, aR, aIintegersa ≤C b if, and only if, aR ≤ bR and aI ≤ bIa ≤C b is reflexive, antisymmetric, transitiveAs ≤ is over integers, and aR , aI are integers
اسلاید 6: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-6Partial OrderingRelation R orders some members of set SIf all ordered, it’s total orderingExample≤ on integers is total ordering≤C is partial ordering on C (because neither 3+5i ≤C 4+2i nor 4+2i ≤C 3+5i holds)
اسلاید 7: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-7Upper BoundsFor a, b S, if u in S with aRu, bRu exists, then u is upper boundLeast upper if there is no t S such that aRt, bRt, and tRuExampleFor 1 + 5i, 2 + 4i C, upper bounds include 2 + 5i, 3 + 8i, and 9 + 100iLeast upper bound of those is 2 + 5i
اسلاید 8: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-8Lower BoundsFor a, b S, if l in S with lRa, lRb exists, then l is lower boundGreatest lower if there is no t S such that tRa, tRb, and lRtExampleFor 1 + 5i, 2 + 4i C, lower bounds include 0, -1 + 2i, 1 + 1i, and 1+4iGreatest lower bound of those is 1 + 4i
اسلاید 9: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-9LatticesSet S, relation RR is reflexive, antisymmetric, transitive on elements of SFor every s, t S, there exists a greatest lower bound under RFor every s, t S, there exists a least upper bound under R
اسلاید 10: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-10ExampleS = { 0, 1, 2 }; R = ≤ is a latticeR is clearly reflexive, antisymmetric, transitive on elements of SLeast upper bound of any two elements of S is the greaterGreatest lower bound of any two elements of S is the lesser
اسلاید 11: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-11Picture012Arrows represent ≤; total ordering
اسلاید 12: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-12ExampleC, ≤C form a lattice≤C is reflexive, antisymmetric, and transitiveShown earlierLeast upper bound for a and b: cR = max(aR, bR), cI = max(aI, bI); then c = cR + cIiGreatest lower bound for a and b: cR = min(aR, bR), cI = min(aI, bI); then c = cR + cIi
اسلاید 13: November 1, 2004Introduction to Computer Security©2004 Matt BishopSlide #27-13Picture1+5i2+4i1+4i2+5iArrows represent ≤C
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.