1IS 2150 / TEL 2810Introduction to SecurityJames JoshiAssistant Professor, SISLecture 3September 13, 2007Mathematical ReviewSecurity Policies2Mathematics Review3Propositional logic/calculus Atomic, 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 connectives Negation ¬ p (NOT) highest precedence Disjunction p ∨ q(OR) second precedence Conjunction p ∧ q(AND) second precedence Implication p → q q logical consequence of p Exercise: Truth tables?4Propositional logic/calculus Contradiction: Formula that is always false : p ∧¬p What about: ¬(p ∧¬p)? Tautology: Formula that is always True : p ∨¬p 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…5Some Laws of Logic Double negation DeMorgan’s law ¬(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)6Predicate/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 file D(y): y is a directory C(x, y): x is a file in directory y7Predicate/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 file and x is in directory y What about ∀x F(x) → (∃y (D(y) ∧C(x, y)))?8Mathematical Induction Proof technique - to prove some mathematical property E.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) holds for n= 1, …, k Induction Step: Prove that if M(k) holds then M(k+1) holds9Mathematical Induction Exercise: prove that sum of first n natural numbers is S(n): 1 + … + n = n(n+ 1)/2 S(n): 1^2+ .. +n^2 = n (n +1)(2n + 1)/610Lattice 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 T Binary 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) ∈ R is another way of writing 1 ≤ 211Lattice Properties of relations Reflexive: if aRa for all a ∈ S Anti-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”(≤)? Draw the Hasse diagram Captures all the relations12Lattice 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 all E.g. “less than equal to” (≤) on complex numbers; Consider (2 + 4i) and (3 + 2i)13Lattice Upper bound (u, a, b ∈ 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 (l, a, b ∈ S) l is a lower bound of a and b means lRaand lRb Greatest lower bound : glb(a, b)closest lower bound14Lattice A lattice is the combination of a set of elements Sand a relation Rmeeting 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 Some examples S = {1, 2, 3} and R = ≤? S = {2+4i; 1+2i; 3+2i, 3+4i} and R = ≤?15Overview of Lattice Based Models Confidentiality Bell LaPadula Model First rigorously developed model for high assurance - for military Objects are classified Objects may belong to Compartments Subjects are given clearance Classification/clearance levels form a lattice Two rules No read-up No write-down16Security Policies17Security Policy Defines what it means for a system to be secure Formally: Partitions a system into Set of secure (authorized) states Set of non-secure (unauthorized) states Secure system is one that Starts in authorized state Cannot enter unauthorized state18Secure System - Example Is this Finite State Machine Secure?Ais start state ?Bis start state ?Cis start state ? How can this be made secure if not?Suppose A, B, and Care authorized states ?A B C DUnauthorizedstatesAuthorizedstates19Additional Definitions: Security breach: system enters an unauthorized state Let Xbe a set of entities, Ibe information.Ihas confidentiality with respect to Xif no member of Xcan obtain information on IIhas integrity with respect to Xif all members of Xtrust I Trust I, its conveyance and storage (data integrity)Imaybe origin information or an identity (authentication)Iis a resource – its integrity implies it functions as it should (assurance)Ihas availability with respect to Xif all members of Xcan access I Time limits (quality of service)20Confidentiality Policy Also known as information flow Transfer of rights Transfer of information without transfer of rights Temporal context Model often depends on trust Parts of system where information couldflow Trusted entity must participate to enable flow Highly developed in Military/Government21Integrity Policy Defines how information can be altered Entities allowed to alter data Conditions under which data can be altered Limits to change of data Examples: Purchase over $1000 requires signature Check over $10,000 must be approved by one person and cashed by anotherSeparation of duties : for preventing fraud Highly developed in commercial world22Trust Theories and mechanisms
View Full Document