The Complexity of Discretionary Access Control

TheComplexityofDiscretionaryAccessControlStephenDranger,RobertH.Sloan?,andJonA.Sol[e-mail];sloan|[e-mail]ccesscontrolschemefordis-cretionaryaccesscontrolswithadecidablesafetyproblem.Thispaperdealswiththecomplexityanalysisofthataccesscontrol,andfindsittobe,initsworstcases,PSPACE-complete,butpolynomialtimeforprac-ticalcases.ThePSPACE-hardnessreductionusesthetheoryofsuccinctproblemsinamoregeneralmannerthancircuitrepresentation.1IntroductionInacomputersystem,accesscontrolsrestrictsubjects(usersand/orprocesses)toperformingonlythoseoperationsonobjects(e.g.,files)forwhichtheyareauthorized.Foreachsuchoperation,theaccesscontrolseitherallowordisallowthatoperationtobeperformed.InDiscretionaryAccessControls(DACs),eachobjecthasanownerwhoexercisesprimarycontrolovertheobject.DACsareoldestandmostwidelyusedclassofaccesscontrols,theaccesscontrolsforbothWindowsandUNIXareDAC.TheUnixDAC,forexample,hasthewellknownthreeprimitivepermissionsread,write,andexecute.Inthelate1970s,Harrison,Ruzzo,andUllman(HRU)introducedaseem-inglyverysimplegeneral-purposelanguageforDiscretionaryAccessControl(DAC).InspiteofthesimplicityoftheHRUlanguage,asafetypropertywithparametersaspecificpermissionp,subjects,andobjecto:“Alwayssdoesnothavepermissionpforo”(1)isundecidable[3].RecentlySolworthandSloangaveagroup-basedmechanismfordesigningDACsforwhichthesafetyproblem(Equation1)isdecidable[10],andshowedthatthatmechanismisexpressiveenoughtoconstructanyparticularDACfromataxonomyofDACsgivenbyOsborneetal.(OSM)[8].Thatgroup-basedaccesscontrolschemewasthefirstgeneralaccesscontrolmodelprovedbothtohaveadecidablesafetypropertyandtobecapableofimplementingthefullrangeofDACmodels.FromHRU’sworkinthe1970sthoughtheearly2000s,generalaccesscontrolmodelswerepublishedthathavebothdecidable(butrelativelyweak)andundecidable(butmoreexpressive)vari-ants.ThisincludesHRU,Sandhu’s1992TypedAccessModel(TAM)[9],and?PartiallysupportedbyNSFgrantNo.CCF-0431059.Kochetal.’s2002graph-basedmodel[4,5].Ineachofthesecases,decidabilityisobtainedbyrequiringatypeofmonotonicity:anoperationcanaddorremoveprivilegesbutnotboth.Thus,forexample,changingauser’sgroupmembershipisnotpermittedinthedecidableversionofthoseaccesscontrolschemes,sincechanginggroupstypicallybothaddsandremovesprivileges.InthispaperweconsidertheprecisecomplexityofthesafetyproblemintheSolworthandSloanaccesscontrolscheme.WeshowthatfortheimplementationofanyDACinOsborneetal.’staxonomy,thesafetyproblemcanbedecidedinpolynomialtime,andthatforthemechanisminitsfullgenerality,thesafetyproblemisPSPACEcomplete.TheproofofPSPACEhardnessmayhavesomeinterestinitsownright.AswementionverybrieflyinSection6,itgeneralizesthetheoryofsuccinctgraphproblems[2].Inthenextsectionwequicklysketchthegroup-basedaccesscontrolmodelof[10](fulldetailsaregiveninthatpaper).Section3describestheslidingmarkernet,anewmarkedgraphmodel,whichistheappropriateabstractionofthekeypartofthegroup-basedaccesscontrolsystem.Section4givesthepolynomial-timeresult,andSection5givesthePSPACE-completenessresult.WeconcludeinSection6.2ReviewoftheaccesscontrolschemeSolworthandSloan’sgroup-basedaccesscontrolmodelisageneralpurposeschemethatallowsonetodescribeawidevarietyofparticularaccesscontrolsystems.Itcorrespondstowhattheycalled“Layer1”[10],andtowhatLiandTripunitara[6]callanaccesscontrolscheme.Anaccesscontrolschemehasasetofstatesandfamilyoftransitionfunctions,andpossiblepermissions.Aparticularaccesscontrolsystemspecifiesaparticulartransitionfunction,andthespecificpermissions,andtypicallynarrowsthesetofstatesaswell.InallparticularaccesscontrolsystemsintheSolworth-Sloanscheme,pro-cessesderiveauthoritytoperformoperationsfromtheuseronwhosebehalftheyexecute.Everyobject—orentitythatcanbeaccessedbyaprocess—hasalabelthat(indirectly)definestheprivilege(alsocalledpermissionorright)thatvarioususershavetoperformoperationsontheobject.(Afileisthetypicalexampleofanobject.)Objectsaredisjointfromusers.Indefiningaparticularsystem,afixedconstantnumberofprivilegesischosen(e.g.,read,write,andexecute).Privilegesmaplabelstogroupsofusers;themappingisfixedwhenthelabeliscreated,althoughthemembershipofthegroupisnotfixed.Protectionisatthegranularityoflabels.Thegroupmechanismisthenovelpartofthescheme.Agroupsetisacollectionofoneormoregroups;agroupisasetofusers.1Everygroupsethasasetofusers,asetofgrouptags,andasetofpairs,hu,tiwhereuisauserIDandtisagrouptag,whichdeterminegroupmembership.1Whatwedescribeinthissectionare“nativegroupsandgroupsets”in[10];toimplementaparticularDACpolicyonetypicallyusesmorethanoneofthesenativegroupstoimplementonegroupinthespecifiedpolicy.2.1FormaldescriptionofSolworth-SloanschemeInthissubsection,forcompleteness,wegiveafairlydetaileddescriptionoftherelevantpartsoftheSolworth-Sloanaccesscontrolscheme.However,thereadercanprobablyfollowthemainpointsofthispaperwithoutreadingthesedetails.Formally,intheSolworth-Sloanscheme,everystate(inanypossiblesystem)isatuplewiththefollowing(many)components:–ThesetUofcurren