IS 2150 / TEL 2810IS 2150 / TEL 2810Introduction to SecurityJames JoshiAssociate ProfessorSISAssociate Professor, SISLecture 3September 15, 2009Mathematical ReviewSecurity Policies1Security PoliciesObjective Review some mathematical conceptsPropositional logicPropositional logic Predicate logicMathematical inductionMathematical induction Lattice2Propositional logic/calculus Atomic, declarative statements (propositions) that can be shown to be either TRUE or FALSE but not both;Eg “Skyisblue”;“3islessthan4”both; E.g., “Sky is blue”; “3 is less than 4” Propositions can be composed into compound sentences using connectivesg Negation ¬ p (NOT) highest precedence Disjunction p ∨ q(OR) second precedenceConjunctionpq(AND)second precedenceConjunction p ∧q(AND)second precedence Implication p → q q logical consequence of p Exercise: Truth tables?3Propositional logic/calculus Contradiction: Formula that is always false : p ∧¬pWhat about:(p∧p)?What about: ¬(p ∧¬p)? Tautology: Formula that is always True : p ∨¬pWh t b t()?What about: ¬(p ∨¬p)? Others Exclusive OR: p ⊕ q; p or q but not both Bi-condition: p ↔q [p if and only ifq (p iff q)] Logical equivalence: p ⇔ q [p is logically equivalent to q] Some exercises…4Some Laws of Logic Double negation DeMorgan’s law(pq)⇔(pq) ¬(p ∧q) ⇔(¬p ∨¬q) ¬(p ∨ q) ⇔ (¬p ∧¬q) Commutative()()(p ∨ q)⇔(q ∨ p) Associative law p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r Distributive law p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)5Predicate/first order logic Propositional logic Variable, quantifiers, constants and functions Consider sentence: Every directory contains some files Need to capture “every” “some” F(x): x is a fileD(y):yisadirectoryD(y): y is a directory C(x, y): x is a file in directory y6Predicate/first order logic Existential quantifiers ∃ (There exists) E.g., ∃ x is read as There exists x Universal quantifiers ∀(For all) ∀y D(y) → (∃x (F(x) ∧C(x, y))) read as for every y, ify is a directory, then there exists a xsuch that xis a fileandx is in directory ysuch that xis a file and x is in directory y What about ∀x F(x) → (∃y (D(y) ∧C(x, y)))?7Mathematical Induction Proof technique - to prove some mathematical propertyEtt thtM()hldflltlE.g. want to prove that M(n) holds for all natural numbers Base case OR Basis: Prove that M(1) holds Induction Hypothesis: Assert that M(n)holdsforn=1kAssert that M(n) holds for n= 1, …, k Induction Step: Prove that if M(k) holds then M(k+1) holds8()()Mathematical Induction Exercise: prove that sum of first n natural numbers isnatural numbers is S(n): 1 + … + n = n(n+ 1)/2 ProveS(n): 1^2+ +n^2 =n(n+1)(2n+1)/6S(n): 1^2+ .. +n^2 = n (n +1)(2n + 1)/69Lattice Sets Collection of unique elements Let S, T be sets Cartesian product: S x T = {(a, b) | a ∈ A, b ∈ B} A set of order pairs Binary relation R from S to T is a subset of S x TBi l tiSi b t fS SBinary relation R on S is a subset of S x S If (a, b) ∈Rwe write aRb Example: R is “less than equal to” (≤) For S = {1, 2, 3} Example of R on S is {(1, 1), (1, 2), (1, 3), ????)(1 2)∈Ris another way of writing 1≤210(1, 2) ∈Ris another way of writing 1 ≤2Lattice Properties of relations Reflexive: ifaRafor alla∈Sif aRafor all a ∈S Anti-symmetric: if aRb and bRa implies a = b for all a, b ∈ STitiTransitive: if aRb and bRc imply that aRc for all a, b, c ∈ S Which properties hold for “less than equal to” ()?(≤)? Draw the Hasse diagram Captures all the relations11pLattice Total ordering: when the relation orders all elements E.g., “less than equal to” (≤) on natural numbers Partial ordering (poset): the relation orders only some elements not allE“l th lt”()lE.g. “less than equal to” (≤) on complex numbers; Consider (2 + 4i) and (3 + 2i)12Lattice Upper bound (u, a, b ∈ S) u is an upper bound of a and b means aRu and ppbRu Least upper bound : lub(a, b)closest upper bdbound Lower bound (l, a, b ∈ S)lis a lower bound of a and b meanslRandlRbl is a lower bound of a and b means lRaand lRb Greatest lower bound : glb(a, b)closest lower bound13boundLattice A lattice is the combination of a set of elements Sand a relation Rmeeting the following criteriaR is reflexive antisymmetric and transitive on theR is reflexive, antisymmetric, and transitive on the elements of S For every s, t∈ S, there exists a greatest lower boundFor everyst∈S there exists alowest upper boundFor every s, t∈S, there exists a lowest upper bound Some examples S = {1, 2, 3} and R = ≤?{}d S = {2+4i; 1+2i; 3+2i, 3+4i} and R = ≤?14Overview of Lattice Based Models Confidentiality Bell LaPadula Model First rigorously developed model for high assurance - for military Objects are classifiedObjec s a e c ass ed Objects may belong to Compartments Subjects are given clearanceClassification/clearance levels form a latticeClassification/clearance levels form a lattice Two rules No read-upNid15No
View Full Document
Unlocking...