Unformatted text preview:

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 InductionProof technique - to prove some mathematical Proof technique - to prove some mathematical propertypropertyE.g. want to prove that M(n) holds for all natural E.g. want to prove that M(n) holds for all natural numbersnumbersBase case: Prove that M(1) holds – called Induction Hypothesis: Assert that M(n) holds for n = 1 to kInduction Step: Prove that if M(k) holds then M(k+1) holdsExercise: 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 3LatticeLatticeLet S, a setLet S, a setCartesian product: S x SCartesian product: S x SBinary relation R on S is a subset of S x SBinary relation R on S is a subset of S x SIF (a, b) IF (a, b)  R we write aRb R we write aRbExample, 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 relationsReflexive: is aRa for all a  SAntis-symmetric: if aRb and bRa implies a = b for all a, b  STransitive: if aRb and bRc imply that aRc for all a, b, c  SWhich properties hold for “less than equal to” ()?IS 2935 / TEL 2810: Introduction to Computer Security 4LatticeLatticeTotal ordering: when the relation orders all elementsTotal ordering: when the relation orders all elementsE.g., “less than equal to” () on natural numbersPartial ordering (poset): when the relation orders only Partial ordering (poset): when the relation orders only some elements not allsome elements not allE.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 bRuLeast upper bound : lub(a, b) closest upper boundLower bound (u, a, b Lower bound (u, a, b  S S))l is a lower bound of a and b means lRa and lRbGreatest lower bound : glb(a, b) closest lower boundIS 2935 / TEL 2810: Introduction to Computer Security 5LatticeLatticeA 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 criteriaR is reflexive, antisymmetric, and transitive on the elements of SFor every s, t  S, there exists a greatest lower boundFor every s, t  S, there exists a lowest upper boundWhat 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 ModelSystem is represented as a directed graphSystem is represented as a directed graphSubject:Object:Labeled edge indicate the rights that the source object has on the destination objectFourFour 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:SharingSharingGiven 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 Gntg-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+1Vertices tg-connected if tg-path between themTheorem: 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 rightsFour 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 rightsLemma 3.1Lemma 3.1Sequence:CreateTakeGrantTakeβ  αα {t}Can_share(α, xx, , yy,G0)xygtgβ  α{t}αzIS


View Full Document

Pitt IS 2935 - Mathematical Induction

Download Mathematical Induction
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Mathematical Induction and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Mathematical Induction 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?