1IS 2150 / TEL 2810Introduction to SecurityJames JoshiAssociate Professor, SISLecture 4September 22, 2009Access Control ModelFoundational ResultsObjective Understand the basic results of the HRU model Saftey issue Turing machine Undecidability23Protection System State of a system Current values of memory locations, registers, secondary storage, etc. other system components Protection state (P) A subset of the above values that deals with protection (determines if system state is 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) e.g. users, processes, agents, etc. Object (O: set of all objects) e.g. 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 TransitionsXiXi+1i+1Xi├i+1Xi+1: upon transition i+1, the system moves from state Xito Xi+1X ├* Y: the system moves from state X toYafter a set of transitionsX Y*XiXi+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)Create subjectsCreates new row, column in ACM; s does not exist prior to thisCreate objectoCreates new column in ACModoes not exist prior to thisEnterrinto a[s, o]Adds rright for subject sover object oIneffective if r is already thereDeleterfroma[s, o] Removes r right from subject sover object oDestroy subjectsDeletes row, column from ACM;Destroy objectoDeletes column from ACM7Primitive commands (HRU)Create subjectsCreates new row, column in ACM; s does not exist prior to thisPrecondition: sSPostconditions:S´ = S{ s}, O´ = O{ s}(yO´)[a´[s, y] = ] (row entries for s)(xS´)[a´[x, s] = ] (column entries for s)(xS)(yO)[a´[x, y] = a[x, y]]8Primitive commands (HRU)Enterrinto a[s, o]Adds rright for subject sover object oIneffective if r is already therePrecondition: sS, oOPostconditions:S´ = S, O´ = Oa´[s, o] = a[s, o] { r}(xS´)(yO´) [(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,p]Enter w into a[q,p]EndParent 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: 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 Leakage of rights: (unsafe with respect to right r) Assume that A representing a secure state does not contain a right rin an 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 description of its initial arguments, determine whether the algorithm, when executed with these arguments, ever halts (the alternative is that it runs forever without halting).23Turing Machine & Safety problem Theorem: It is undecidable if a given state of a given protection system is safe for a given generic right Reduce TM to Safety problem If Safety problem is decidable then it implies that TM halts (for all inputs) – showing that the halting problem is decidable (contradiction) TM is an abstract model of computer Alan Turing in 193624Turing Machine TM consists of A tape divided into cells; infinite in one direction A set of tape symbols
View Full Document
Unlocking...