IS 2150 / TEL 2810IS 2150 / TEL 2810Introduction to SecurityJames JoshiAssociate Professor SISAssociate Professor, SISLecture 3.1September 13, 2011Mathematical ReviewMathematical ReviewSecurity Policies1Objective 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:(pp)?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 1210(1, 2) Ris another way of writing 1 2Lattice Properties of relations Reflexive: ifaRafor allaSif 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 everystS there exists alowest upper boundFor every s, tS, 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