1IS 2150 / TEL 2810Introduction to SecurityJames JoshiAssistant Professor, SISLecture 4September 20, 2007Access Control ModelFoundational Results2Back to ..Access Control Matrix3Protection System State of a system Current values of memory locations, registers, secondary storage, etc. other system components Protection state (P) A system state that is considered secure A protection system Captures the conditions for state transition Consists of two parts: A set of generic rights A set of commands4Protection System Subject (S: set of all subjects) Eg.: users, processes, agents, etc. Object (O: set of all objects) Eg.:Processes, files, devices Right (R: set of all rights) An action/operation that a subject is allowed/disallowed on objects Access Matrix A: a[s, o] ⊆R Set of Protection States: (S, O, A) Initial state X0= (S0, O0, A0)5State TransitionsXiXiXi+1Xi+1τi+1Xi├τi+1Xi+1: upon transition τi+1, the system moves from state Xito Xi+1X ├* Y : the system moves from state X to Y after a set of transitionsXXYY*XiXiXi+1Xi+1ci+1(pi+1,1, pi+1,2, …, pi+1,m)Xi├ ci+1(pi+1,1, pi+1,2, …, pi+1,m) Xi+1: state transition upon a commandFor every command there is a sequence of state transition operations6Primitive commands (HRU)Deletes column from ACMDestroy object oDeletes row, column from ACM;Destroy subject sRemoves r right from subject sover object oDelete r from a[s, o]Adds r right for subject s over object oIneffective if r is already thereEnter r into a[s, o]Creates new column in ACMo does not exist prior to thisCreate object oCreates new row, column in ACM; s does not exist prior to thisCreate subject s7Primitive commands (HRU)Creates new row, column in ACM; s does not exist prior to thisCreate subject sPrecondition: s∉SPostconditions:S´= S∪{ s}, O´= O∪{ s}(∀y∈O´)[a´[s, y] = ∅] (row entries for s)(∀x∈S´)[a´[x, s] = ∅] (column entries for s)(∀x∈S)(∀y∈O)[a´[x, y] = a[x, y]]Precondition: Precondition: ss∉∉SSPostconditionsPostconditions::S´= S∪{ s}, O´= O∪{ s}(∀y∈O´)[a´[s, y] = ∅] (row entries for s)(∀x∈S´)[a´[x, s] = ∅] (column entries for s)(∀x∈S)(∀y∈O)[a´[x, y] = a[x, y]]8Primitive commands (HRU)Adds r right for subject s over object oIneffective if r is already thereEnter r into a[s, o]Precondition: s∈S, o∈OPostconditions:S´= S, O´= Oa´[s, o] = a[s, o] ∪ { r}(∀x∈S´)(∀y∈O´) [(x, y)≠(s, o) →a´[x, y] = a[x, y]]Precondition: Precondition: ss∈∈SS, , oo∈∈OOPostconditionsPostconditions::S´= S, O´= Oa´[s, o] = a[s, o] ∪ { r}(∀x∈S´)(∀y∈O´) [(x, y)≠(s, o) →a´[x, y] = a[x, y]]9System commands [Unix] process p creates file f with owner read and write (r, w) will be represented by the following:Command create_file(p, f)Create object fEnter own into a[p,f]Enter r into a[p,f]Enter w into a[p,f]End10System commands Process p creates a new process qCommand spawn_process(p, q)Create subject q;Enter own into a[p,q]Enter r into a[p,q]Enter w into a[p,q]Enter r into a[q,r]Enter w into a[q,r]EndParent and child cansignal each otherParent and child cansignal each other11System commands Defined commands can be used to update ACMCommand make_owner(p, f)Enter own into a[p,f]End Mono-operational: the command invokes only one primitive12Conditional Commands Mono-operational + mono-conditionalCommand grant_read_file(p, f, q)If ownin a[p,f]Then Enter rinto a[q,f]End13Conditional Commands Mono-operational + biconditionalCommand grant_read_file(p, f, q)If rin a[p,f] andcin a[p,f]Then Enter rinto a[q,f]End Why not “OR”??14Fundamental questions How can we determine that a system is secure? Need to define what we mean by a system being “secure” Is there a generic algorithm that allows us to determine whether a computer system is secure?15What is a secure system? A simple definition A secure system doesn’t allow violations of a security policy Alternative view: based on distribution of rights to the subjects Leakage of rights: (unsafe with respect to right r) Assume that A representing a secure state does not contain a right rin any element of A. A right r is said to be leaked, if a sequence of operations/commands adds rto an element of A, which did not contain r16What is a secure system? Safety of a system with initial protection state Xo Safe with respect to r: System is safe with respect to rif rcan never be leaked Else it is called unsafe with respect to right r.17Safety Problem: formally Given initial state X0= (S0, O0, A0) Set of primitive commands cris not in A0[s, o] Can we reach a state Xnwhere ∃s,osuch that An[s,o] includes a right rnot in A0[s,o]?- If so, the system is not safe- But is “safe”secure?18Undecidable Problems Decidable Problem A decision problem can be solved by an algorithm that halts on all inputs in a finite number of steps. Undecidable Problem A problem that cannot be solved for all cases by any algorithm whatsoever19Decidability Results(Harrison, Ruzzo, Ullman) Theorem: Given a system where each command consists of a single primitivecommand (mono-operational), there exists an algorithm that will determine if a protection system with initial state X0is safe with respect to right r.20Decidability Results(Harrison, Ruzzo, Ullman) Proof: determine minimum commands kto leak Delete/destroy: Can’t leak (or be detected) Create/enter: new subjects/objects “equal”, so treat all new subjects as one No test for absence Tests on A[s1, o1] and A[s2, o2] have same result as the same tests on A[s1, o1] and A[s1, o2] = A[s1, o2] ∪A[s2, o2] If nrights leak possible, must be able to leak k= n(|S0|+1)(|O0|+1)+1 commands Enumerate all possible states to decide21Decidability Results(Harrison, Ruzzo, Ullman) It is undecidable if a given state of a given protection system is safe for a given generic right For proof – need to know Turing machines and halting problem22Turing Machine & halting problem The halting problem: Given a description of an algorithm and a Given a description of an algorithm and a description of its initial arguments, description of its initial arguments, determine whether the algorithm, when determine whether the algorithm, when executed with these arguments, ever halts executed with these arguments, ever halts (the alternative is that it
View Full Document
Unlocking...