1Courtesy of Professors Prasant Krisnamurthy, Chris Clifton & Matt BishopINFSCI 2935: Introduction of Computer Security 1September 9, 2004September 9, 2004Introduction to Introduction to Computer SecurityComputer SecurityAccess Control MatrixAccess Control MatrixTakeTake--grant modelgrant modelINFSCI 2935: Introduction to Computer Security 2Protection SystemProtection SystemzzState of a systemState of a system{ Current values of z memory locations, registers, secondary storage, etc.z other system componentszzProtection state (P)Protection state (P){ A system state that is considered securezzA protection system A protection system { Describes the conditions under which a system is secure (in a protection state){ Consists of two parts:z A set of generic rightsz A set of commandszzState transitionState transition{ Occurs when an operation (command) is carried out2INFSCI 2935: Introduction to Computer Security 3Protection SystemProtection SystemzzSubject (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.zzObject (O: set of all objects)Object (O: set of all objects){Eg.:Processes, files, deviceszzRightRight{An action/operation that a subject is allowed/disallowed on objectsINFSCI 2935: Introduction to Computer Security 4Access Control Matrix ModelAccess Control Matrix ModelzzAccess 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 objectszzACM is an abstract modelACM is an abstract model{ Rights may vary depending on the object involvedzzACM is implemented primarily in two waysACM is implemented primarily in two ways{ Capabilities (rows){ Access control lists (columns)3INFSCI 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 Matrixftp, nsf, mail, ownftp, mailToadflaxftp, nfs, mailftp, nsf, mail, ownNobftpftpownTelegraphToadflaxNobTelegraphHostnamesCallCallCallmanager-Dcr_ctr+Inc_ctrManagerDcr_ctrInc_ctrCounter•telegraph is a PC with ftp client but no server•nob is provides NFS but not to Toadfax•nob and toadfax can exchange mail4INFSCI 2935: Introduction to Computer Security 7Boolean Expression EvaluationBoolean Expression EvaluationzzACM controls access to database fieldsACM controls access to database fields{Subjects have attributes{Verbs define type of access{Rules associated with objects, verb pairzzSubject attempts to access objectSubject attempts to access object{Rule for object, verb evaluated, grants or denies accessINFSCI 2935: Introduction to Computer Security 8ExampleExamplezzSubject Subject annieannie{Attributes role (artist), groups (creative)zzVerb paintVerb paint{Default 0 (deny unless explicitly granted)zzObject pictureObject picture{Rule:paint: ‘artist’ in subject.role and‘creative’ in subject.groups andtime.hour ≥ 0 and time.hour < 55INFSCI 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 HistoryzzStatistical databases need to Statistical databases need to {answer queries on groups{prevent revelation of individual recordszzQueryQuery--setset--overlap controloverlap 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 answered50K33TeacherEve50K50TeacherDilbert60K37PrincipalCathy20K20AideBob40K45TeacherAliceSalaryAgePositionName6INFSCI 2935: Introduction to Computer Security 11Access Controlled by HistoryAccess Controlled by HistoryzzQuery 1:Query 1:{ sum_salary(position = teacher){ Answer: 140KzzQuery 2:Query 2:{ sum_salary(age > 40 & position = teacher){ Should not be answered as Matt’s salary can be deducedzzCan be represented as an Can be represented as an ACMACM50K33TeacherMatt50K50TeacherLeonard40K45TeacherCeliaSalaryAgePositionName50K50TeacherLeonard40K45TeacherCeliaSalaryAgePositionNameINFSCI 2935: Introduction to Computer Security 12Solution: Query Set Overlap Control (Solution: Query Set Overlap Control (DobkinDobkin, Jones & , Jones & Lipton ’79)Lipton ’79)zzQuery valid if intersection of query Query valid if intersection of query coverage and each previous query < coverage and each previous query < rrzzCan 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)sqiqorO∈−∀∩<7INFSCI 2935: Introduction to Computer Security 13zzQuery 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, Matt] = {read}zzQuery 2:Query 2:OO22= {Celia, Leonard} but | = {Celia, Leonard} but | OO22∩∩OO11| = | = 2; so the query cannot be answered2; so the query cannot be answered{A[asker, Celia] = ∅{A[asker, Leonard] = ∅INFSCI 2935: Introduction to Computer Security 14State TransitionsState TransitionszzLet initial state Let initial state XX00= (= (SS00, , OO00, , AA00))zzNotationNotation{Xi├τi+1Xi+1: upon transition τi+1, the system moves from state Xito Xi+1{X ├* Y : the system moves from state X to Yafter a set of transitions{Xi├ ci+1(pi+1,1, pi+1,2, …, pi+1,m) Xi+1: state transition upon a commandzzFor every command there is a sequence For every command there is a sequence of state transition operationsof state transition operations8INFSCI 2935: Introduction to Computer Security 15Primitive commands (HRU)Primitive commands (HRU)Deletes column from ACMDeletes column from ACMDestroy objectDestroy object oDeletes row, column from ACM;Deletes row, column from ACM;Destroy subjectDestroy subject sRemoves