IS 2150 / TEL 2810 Introduction to SecurityObjectivePropositional logic/calculusSlide 4Some Laws of LogicPredicate/first order logicSlide 7Mathematical InductionSlide 9LatticeSlide 11Slide 12Slide 13Slide 14Overview of Lattice Based Models1IS 2150 / TEL 2810Introduction to SecurityJames JoshiAssistant Professor, SISLecture 3September 9, 2008Mathematical ReviewSecurity PoliciesObjectiveReview some mathematical conceptsPropositional logicPredicate logicMathematical inductionLattice23Propositional logic/calculusAtomic, declarative statements (propositions) that can be shown to be either TRUE or FALSE but not both; E.g., “Sky is blue”; “3 is less than 4”Propositions can be composed into compound sentences using connectivesNegation p (NOT) highest precedenceDisjunction p q (OR) second precedenceConjunction p q (AND) second precedenceImplication p q q logical consequence of p Exercise: Truth tables?4Propositional logic/calculusContradiction: Formula that is always false : p pWhat about: (p p)?Tautology: Formula that is always True : p pWhat about: (p p)?OthersExclusive OR: p q; p or q but not bothBi-condition: p q [p if and only if q (p iff q)]Logical equivalence: p q [p is logically equivalent to q]Some exercises…5Some Laws of LogicDouble negationDeMorgan’s law(p q) (p q)(p q) (p q)Commutative(p q) (q p)Associative lawp (q r) (p q) rDistributive lawp (q r) (p q) (p r)p (q r) (p q) (p r)6Predicate/first order logicPropositional logic Variable, quantifiers, constants and functionsConsider sentence: Every directory contains some filesNeed to capture “every” “some”F(x): x is a fileD(y): y is a directoryC(x, y): x is a file in directory y7Predicate/first order logicExistential quantifiers (There exists)E.g., x is read as There exists xUniversal quantifiers (For all)y D(y) (x (F(x) C(x, y))) read asfor every y, if y is a directory, then there exists a x such that x is a file and x is in directory yWhat about x F(x) ( y (D(y) C(x, y)))?8Mathematical InductionProof technique - to prove some mathematical propertyE.g. want to prove that M(n) holds for all natural numbersBase case OR Basis: Prove that M(1) holdsInduction Hypothesis: Assert that M(n) holds for n = 1, …, kInduction Step: Prove that if M(k) holds then M(k+1) holds9Mathematical InductionExercise: prove that sum of first n natural numbers is S(n): 1 + … + n = n (n + 1)/2ProveS(n): 1^2+ .. +n^2 = n (n +1)(2n + 1)/610LatticeSetsCollection of unique elementsLet S, T be setsCartesian product: S x T = {(a, b) | a A, b B}A set of order pairsBinary relation R from S to T is a subset of S x TBinary relation R on S is a subset of S x SIf (a, b) R we write aRbExample: 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) R is another way of writing 1 211LatticeProperties of relationsReflexive: if aRa for all a SAnti-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” ()?Draw the Hasse diagram Captures all the relations12LatticeTotal ordering: when the relation orders all elementsE.g., “less than equal to” () on natural numbersPartial ordering (poset): the relation orders only some elements not allE.g. “less than equal to” () on complex numbers; Consider (2 + 4i) and (3 + 2i)13LatticeUpper bound (u, a, b S)u is an upper bound of a and b means aRu and bRuLeast upper bound : lub(a, b) closest upper boundLower bound (l, a, b S)l is a lower bound of a and b means lRa and lRbGreatest lower bound : glb(a, b) closest lower bound14LatticeA lattice is the combination of a set of elements S 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 boundSome examplesS = {1, 2, 3} and R = ?S = {2+4i; 1+2i; 3+2i, 3+4i} and R = ?15Overview of Lattice Based ModelsConfidentiality Bell LaPadula ModelFirst rigorously developed model for high assurance - for military Objects are classifiedObjects may belong to CompartmentsSubjects are given clearanceClassification/clearance levels form a latticeTwo rulesNo read-upNo
View Full Document
Unlocking...