Sunday, October 17, 2004Mathematical InductionLatticeSlide 4Slide 5Take-Grant Protection ModelSlide 7Take-Grant Protection Model: SharingAny two subjects with tg-path of length 1 can share rightsSlide 10Other definitionsBridgeTheorem: Can_share(α,x,y,G0) (for subjects)What about objects? Initial, terminal spansTheorem: Can_share(α,x,y,G0)Slide 16Slide 17Slide 18Slide 19Slide 20ExampleTake-Grant Model: Sharing through a Trusted EntityTheft in Take-Grant ModelA witness to theftConspiracySlide 26Slide 27TheoremsSchematic Protection ModelSlide 30Transferring RightsFilter FunctionSPM Example2Create OperationCreate operation Distinct TypesExamplesExpressing ConstraintsSample ConstraintsUsers and LevelsObjects and ClassificationsSlide 41Additional constraintsCourtesy of Professors Prasant Krisnamurthy, Chris Clifton & Matt BishopINFSCI 2935: Introduction of Computer Security1Sunday, October 17, 2004Sunday, October 17, 2004Introduction to Introduction to Computer SecurityComputer SecurityReviewReviewIS 2935 / TEL 2810: Introduction to Computer Security 2Mathematical InductionMathematical InductionProof technique - to prove some mathematical Proof technique - to prove some mathematical propertypropertyE.g. want to prove that M(n) holds for all natural E.g. want to prove that M(n) holds for all natural numbersnumbersBase case: Prove that M(1) holds – called Induction Hypothesis: Assert that M(n) holds for n = 1 to kInduction Step: Prove that if M(k) holds then M(k+1) holdsExercise: prove that sum of first n natural Exercise: prove that sum of first n natural numbers is numbers is 1 + … + n = n(n + 1)/2IS 2935 / TEL 2810: Introduction to Computer Security 3LatticeLatticeLet S, a setLet S, a setCartesian product: S x SCartesian product: S x SBinary relation R on S is a subset of S x SBinary relation R on S is a subset of S x SIF (a, b) IF (a, b) R we write aRb R we write aRbExample, R is “less than equal to” ()If S = {1, 2, 3} then R is {(1, 1), (1, 2), (1, 3), ????)(1, 2) R is another way of writing 1 2 Properties of relationsProperties of relationsReflexive: is aRa for all a SAntis-symmetric: if aRb and bRa implies a = b for all a, b STransitive: if aRb and bRc imply that aRc for all a, b, c SWhich properties hold for “less than equal to” ()?IS 2935 / TEL 2810: Introduction to Computer Security 4LatticeLatticeTotal ordering: when the relation orders all elementsTotal ordering: when the relation orders all elementsE.g., “less than equal to” () on natural numbersPartial ordering (poset): when the relation orders only Partial ordering (poset): when the relation orders only some elements not allsome elements not allE.g. “less than equal to” () on complex numbers; Consider (2 + 4i) and (3 + 2i)Upper bound (u, a, b Upper bound (u, a, b S S))u is an upper bound of a and b means aRu and bRuLeast upper bound : lub(a, b) closest upper boundLower bound (u, a, b Lower bound (u, a, b S S))l is a lower bound of a and b means lRa and lRbGreatest lower bound : glb(a, b) closest lower boundIS 2935 / TEL 2810: Introduction to Computer Security 5LatticeLatticeA lattice is the combination of a set of elements A lattice is the combination of a set of elements S and a relation R meeting the following criteriaS and a relation R meeting the following criteriaR is reflexive, antisymmetric, and transitive on the elements of SFor every s, t S, there exists a greatest lower boundFor every s, t S, there exists a lowest upper boundWhat about S = {1, 2, 3} and R = What about S = {1, 2, 3} and R = ??What about S = {2+4i; 1+2i; 3+2i, 3+4i} and R = What about S = {2+4i; 1+2i; 3+2i, 3+4i} and R = ??IS 2935 / TEL 2810: Introduction to Computer Security 6Take-Grant Protection ModelTake-Grant Protection ModelSystem is represented as a directed graphSystem is represented as a directed graphSubject:Object:Labeled edge indicate the rights that the source object has on the destination objectFourFour graph rewriting rules (“de jure”, “by law”, “by rights”)graph rewriting rules (“de jure”, “by law”, “by rights”)The graph changes as the protection state changes according to1. Take rule: if 1. Take rule: if t t γγ, the take rule produces another graph with a , the take rule produces another graph with a transitive edge transitive edge αα ββ addedadded..Either:γαβγ β├├xz yxz yx takes (α to y) from zIS 2935 / TEL 2810: Introduction to Computer Security 7Take-Grant Protection ModelTake-Grant Protection Model2. Grant rule: if 2. Grant rule: if g g γγ, the take rule produces another graph with a , the take rule produces another graph with a transitive transitive edge edge αα ββ added. added.γαβγ β├├xz yxz y3. Create rule:3. Create rule:├├αxx y4. Remove rule:4. Remove rule:├├β -αx yβx yz grants (α to y) to xx creates (α to new vertex) yx removes (α to) yIS 2935 / TEL 2810: Introduction to Computer Security 8Take-Grant Protection Model:Take-Grant Protection Model:SharingSharingGiven Given GG00, can vertex , can vertex xx obtain obtain αα rights over rights over yy??Can_share(α,x, y,G0) is true iff G0├* Gn using the four rules, &There is an α edge from x to y in Gntg-pathtg-path: : vv00,…,,…,vvnn with with t or or g edge between any edge between any pair of vertices pair of vertices vvii, , vvi+1i+1Vertices tg-connected if tg-path between themTheorem: Any two subjects with Theorem: Any two subjects with tg-pathtg-path of of length 1 can share rightslength 1 can share rightsIS 2935 / TEL 2810: Introduction to Computer Security 9Any two subjects with Any two subjects with tg-pathtg-path of length 1 of length 1 can share rightscan share rightsFour possible length 1 Four possible length 1 tgtg-paths-paths1. Take rule1. Take rule2. Grant rule2. Grant rule3. Lemma 3.13. Lemma 3.14. Lemma 3.24. Lemma 3.2{t}β αβ α{g}β α{t}{g}β αCan_share(α, xx, , yy,G0)x yzIS 2935 / TEL 2810: Introduction to Computer Security 10Any two subjects with Any two subjects with tg-pathtg-path of length 1 of length 1 can share rightscan share rightsLemma 3.1Lemma 3.1Sequence:CreateTakeGrantTakeβ αα {t}Can_share(α, xx, , yy,G0)xygtgβ α{t}αzIS
View Full Document