September 9, 2004Protection SystemSlide 3Access Control Matrix ModelAccess Control MatrixSlide 6Boolean Expression EvaluationExampleACM at 3AM and 10AMAccess Controlled by HistorySlide 11Solution: Query Set Overlap Control (Dobkin, Jones & Lipton ’79)Slide 13State TransitionsPrimitive commands (HRU)Create SubjectCreate ObjectAdd RightDelete RightDestroy SubjectDestroy ObjectSystem commands using primitive operationsConditional CommandsAttenuation of privilegeFundamental questionsWhat is a secure system?Safety Problem: formallyDecidability Results (Harrison, Ruzzo, Ullman)Slide 29What is the implication?Take-Grant Protection ModelSlide 32Take-Grant Protection Model: SharingAny two subjects with tg-path of length 1 can share rightsSlide 35Other definitionsBridgeTheorem: Can_share(α,x,y,G0) (for subjects)What about objects? Initial, terminal spansTheorem: Can_share(α,x,y,G0)Courtesy of Professors Prasant Krisnamurthy, Chris Clifton & Matt BishopINFSCI 2935: Introduction of Computer Security1September 9, 2004September 9, 2004Introduction to Introduction to Computer SecurityComputer SecurityAccess Control MatrixAccess Control MatrixTake-grant modelTake-grant modelINFSCI 2935: Introduction to Computer Security 2Protection SystemProtection SystemState of a systemState of a systemCurrent values of memory locations, registers, secondary storage, etc.other system componentsProtection state (P)Protection state (P)A system state that is considered secureA protection system A protection system Describes the conditions under which a system is secure (in a protection state)Consists of two parts:A set of generic rightsA set of commandsState transitionState transitionOccurs when an operation (command) is carried outINFSCI 2935: Introduction to Computer Security 3Protection SystemProtection SystemSubject (S: set of all subjects)Subject (S: set of all subjects)Active entities that carry out an action/operation on other entities; Eg.: users, processes, agents, etc.Object (O: set of all objects)Object (O: set of all objects)Eg.:Processes, files, devicesRightRightAn action/operation that a subject is allowed/disallowed on objectsINFSCI 2935: Introduction to Computer Security 4Access Control Matrix ModelAccess Control Matrix ModelAccess control matrix Access control matrix Describes the protection state of a system.Characterizes the rights of each subjectElements indicate the access rights that subjects have on objectsACM is an abstract modelACM is an abstract modelRights may vary depending on the object involvedACM is implemented primarily in two waysACM is implemented primarily in two waysCapabilities (rows)Access control lists (columns)INFSCI 2935: Introduction to Computer Security 5Access Control MatrixAccess Control Matrixs3 r s1f1 f2 f3 f4 f5 f6s2s3o, r, wo, r, wo, r, wo, r, wo, r, wo, r, wr r r r w f1f2f3f4f6s2s1 o, r, w s2 r s1 o, r, w s3 r s3 o, r, wf5s2 o, r, w s3 r s1 w s3 o, r, wf5 w s1f2 o, r, w f3 o, r, wf2 r s2f1 o, r, w f5 o, r, wf3 r s3f4 o, r, wf2 r f5 r f6 o, r, wo: ownr: readw:writeAccess MatrixAccess Control ListCapabilitieso, r, wINFSCI 2935: Introduction to Computer Security 6Access Control MatrixAccess Control MatrixHostnames Telegraph Nob ToadflaxTelegraph own ftp ftpNob ftp, nsf, mail, own ftp, nfs, mailToadflax ftp, mail ftp, nsf, mail, ownCounter Inc_ctr Dcr_ctr ManagerInc_ctr +Dcr_ctr -manager Call Call Call•telegraph is a PC with ftp client but no server•nob is provides NFS but not to Toadfax•nob and toadfax can exchange mailINFSCI 2935: Introduction to Computer Security 7Boolean Expression EvaluationBoolean Expression EvaluationACM controls access to database fieldsACM controls access to database fieldsSubjects have attributesVerbs define type of accessRules associated with objects, verb pairSubject attempts to access objectSubject attempts to access objectRule for object, verb evaluated, grants or denies accessINFSCI 2935: Introduction to Computer Security 8ExampleExampleSubject annieSubject annieAttributes role (artist), groups (creative)Verb paintVerb paintDefault 0 (deny unless explicitly granted)Object pictureObject pictureRule:paint: ‘artist’ in subject.role and‘creative’ in subject.groups andtime.hour ≥ 0 and time.hour < 5INFSCI 2935: Introduction to Computer Security 9ACM at 3AM and 10AMACM at 3AM and 10AM… picture …… annie …paintAt 3AM, time conditionmet; ACM is:… picture …… annie …At 10AM, time conditionnot met; ACM is:INFSCI 2935: Introduction to Computer Security 10Access Controlled by HistoryAccess Controlled by HistoryStatistical databases need to Statistical databases need to answer queries on groupsprevent revelation of individual recordsQuery-set-overlap controlQuery-set-overlap controlPrevent an attacker to obtain individual piece of information using a set of queries CA parameter r (=2) is used to determine if a query should be answeredName Position Age SalaryAlice Teacher 45 40KBob Aide 20 20KCathy Principal 37 60KDilbert Teacher 50 50KEve Teacher 33 50KINFSCI 2935: Introduction to Computer Security 11Access Controlled by HistoryAccess Controlled by HistoryQuery 1:Query 1:sum_salary(position = teacher) Answer: 140K Query 2:Query 2:sum_salary(age > 40 & position = teacher) Should not be answered as Matt’s salary can be deducedCan be represented as an Can be represented as an ACMACMName Position Age SalaryCelia Teacher 45 40KLeonard Teacher 50 50KMatt Teacher 33 50KName Position Age SalaryCelia Teacher 45 40KLeonard Teacher 50 50KINFSCI 2935: Introduction to Computer Security 12Solution: Query Set Overlap Control (Dobkin, Jones & Solution: Query Set Overlap Control (Dobkin, Jones & Lipton ’79)Lipton ’79)Query valid if intersection of query Query valid if intersection of query coverage and each previous query < coverage and each previous query < rrCan represent as access control matrixCan represent as access control matrixSubjects: entities issuing queriesObjects: Powerset of recordsOs(i) : objects referenced by s in queries 1..iA[s,o] = read iff( 1)sq iq o rO� -" � <INFSCI 2935: Introduction to Computer Security 13Query 1Query 1: : OO11 = {Celia, Leonard, Matt} so the = {Celia, Leonard, Matt} so the query can be answered. Hencequery can be answered. HenceA[asker, Celia] = {read}A[asker, Leonard] = {read}A[asker,