IS 2150 / TEL 2810IS 2150 / TEL 2810Introduction to SecurityJames JoshiAssistant Professor SISAssistant Professor, SISLecture 4September 16, 2008Access Control ModelFoundational Results1Foundational ResultsObjective Understand the basic results of the HRU modelmodel Saftey issueTuring machineTuring machine Undecidability2Protection System State of a system Current values of memory locations registers secondary storage etcmemory locations, registers, secondary storage, etc. other system components Protection state (P)A system state that is considered secureA 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 commands3Protection System Subject (S: set of all subjects) Eg.: users, processes, agents, etc. Object (O: set of all objects) Eg.:Processes, files, devicesRi ht (Rtflliht)Right (R: set of all rights) An action/operation that a subject is allowed/disallowed on objectsallowed/disallowed on objects Access Matrix A: a[s, o] ⊆R Set of Protection States: (S, O, A)4 Initial state X0= (S0, O0, A0)State Transitionsτi+1XiXi+1Xi├τi+1Xi+1: upon transition τi+1, the system moves from state Xito Xi+1X├*Y: the system moves from*X ├ Y: the system moves from state X to Y after a set of transitionsX Yci+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 command5XiXi+1pFor every command there is a sequence of state transition operationsPrimitive commands (HRU)Create subject sCreates new row, column in ACM; s does not exist prior to thisCreate object oCreates new column in ACMo does not exist prior to thisAddsrright for subjectsover objectoEnter r into a[s, o]Adds rright for subject sover object oIneffective if r is already thereDeleterfroma[s,o]Removesrright from subjectsover objectoDeleterfroma[s, o]Removes r right from subject sover object oDestroy subject sDeletes row, column from ACM;6Destroy object oDeletes column from ACMPrimitive commands (HRU)Create subject sCreates new row, column in ACM; s does not exist prior to thisPrecondition: Precondition: ss∉∉SSPostconditionsPostconditions::S´S{}O´O{}Precondition: Precondition: ss∉∉SSPostconditionsPostconditions::S´S{}O´O{}S´= S∪{ s}, O´= O∪{ s}(∀y∈O´)[a´[s, y] = ∅] (row entries for s)S´= S∪{ s}, O´= O∪{ s}(∀y∈O´)[a´[s, y] = ∅] (row entries for s)(y)[[,y]]( )(∀x∈S´)[a´[x, s] = ∅] (column entries for s)(∀x∈S)(∀y∈O)[a´[x, y] = a[x, y]](y)[[,y]]( )(∀x∈S´)[a´[x, s] = ∅] (column entries for s)(∀x∈S)(∀y∈O)[a´[x, y] = a[x, y]]7Primitive commands (HRU)Enter r into a[s, o]Adds r right for subject s over object oIneffective if r is already therePrecondition: Precondition: ss∈∈SS, , oo∈∈OOPostconditionsPostconditions::Precondition: Precondition: ss∈∈SS, , oo∈∈OOPostconditionsPostconditions::S´= S, O´= Oa´[s,o]=a[s,o]∪{r}S´= S, O´= Oa´[s,o]=a[s,o]∪{r}a[s, o] a[s, o] ∪{ r}(∀x∈S´)(∀y∈O´) [(x, y)≠(s, o) →a´[x, y] = a[x, y]]a[s, o] a[s, o] ∪{ r}(∀x∈S´)(∀y∈O´) [(x, y)≠(s, o) →a´[x, y] = a[x, y]]8System 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]Enterinto[f]Enter rinto a[p,f]Enter w into a[p,f]End9EndSystem commands Process p creates a new process qCommand spawn_process(p, q)Create subject q;Enter own into a[p,q]Etit[]Enter rinto a[p,q]Enter w into a[p,q]Enterrintoa[qp]P t d hildP t d hildEnter rinto a[q,p]Enter w into a[q,p]EndParent and child cansignal each otherParent and child cansignal each other10System commands Defined commands can be used to update ACMCommand make_owner(p, f)Enter own into a[p,f]EdEnd Mono-operational: the command invokes only one primitivethe command invokes only one primitive11Conditional Commands Mono-operational + mono-conditionalconditionalCommand grant_read_file(p, f, q)If ownin a[p,f]Then Enter rinto a[q,f]End12Conditional Commands Mono-operational + biconditionalCommandgrant read file(pfq)Command grant_read_file(p, f, q)If rin a[p,f] andcin a[p,f]Then Enterrintoa[qf]Enter rinto a[q,f]End Why not “OR”??y13Fundamental questions How can we determine that a system is secure?secure? Need to define what we mean by a system being “secure”g Is there a generic algorithm that allows us to determine whether a computerus to determine whether a computer system is secure?14What is a secure system? A simple definition A secure system doesn’t allow violations of a security policypolicy Alternative view: based on distribution of rights Leakage of rights: (unsafe with respect to right r)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 r15What is a secure system? Safety of a system with initial protection state Xoo 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.16Safety Problem: yformally Given initial state X0= (S0, O0, A0)0(0,0,0) Set of primitive commands cris not in A0[s, o]0 Can we reach a state Xnwhere ∃s,osuch that An[s,o] includes a right rnot ,n[,]gin A0[s,o]?- If so, the system is not safe17- But is “safe” secure?Undecidable Problems Decidable ProblemA decision problem can be solved by anA decision problem can be solved by an algorithm that halts on all inputs in a finite number of steps. Undecidable ProblemA problem that cannot be solved for allA problem that cannot be solved for all cases by any algorithm whatsoever18Decidability 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 stateX0is safe withprotection system with initial state X0is safe with respect to right r.19Decidability 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
View Full Document
Unlocking...