Methods and limitations of security policy reconciliation

PatrickMcDanielAT&TResearch

pdmcdan@research.att.comAbstract

Asecuritypolicyisameansbywhichparticipantsessionrequirementsarespecified.However,existingframeworksprovidelimitedfacilitiesfortheautomatedreconciliationofparticipantpolicies.Thispaperconsidersthelimitsandmethodsofreconciliationinageneral-purposepolicymodel.Weidentifyanalgorithmforefficienttwo-policyrec-onciliation,andshowthat,intheworst-case,reconciliationofthreeormorepoliciesisintractable.Further,wesug-gestefficientheuristicsforthedetectionandresolutionofintractablereconciliation.Baseduponthepolicymodel,wedescribethedesignandimplementationoftheIsmenepol-icylanguage.TheexpressivenessofIsmene,andindirectlyofourmodel,isdemonstratedthroughtherepresentationandexpositionofpoliciessupportedbyexistingpolicylan-guages.WeconcludewithbriefnotesontheintegrationandenforcementofIsmenepolicywithintheAntigonecommu-nicationsystem.

AtulPrakash

UniversityofMichiganaprakash@eecs.umich.edu

1.Introduction

Policyisfrequentlythemeansbywhichtherequirementsofcommunicationparticipantsareidentifiedandaddressed.Sessionpoliciesarestatedbythedifferentparticipantsandorganizationsfortheservicessupportingthecommunica-tion.Atpresent,facilitiesforthereconciliationofpartic-ipantpoliciesinexistingpolicyframeworksarelimitedinscopeandsemantics.Hence,policiesmustbereconciledmanually,afrequentlycomplexprocess.Alternatively,gov-erningauthoritiesmustdictatepolicy.Inthatcase,sessionparticipantsacceptingdictatedpolicyhavelimitedabilitytoaffecthowsessionsecurityisdefined.

TheIsmenepolicylanguageandsupportinginfrastruc-tureisbuiltuponthemodelandalgorithmsdefinedthrough-out.TheexpressivenessofIsmene,andindirectlytheappli-cabilityofourpolicymodel,isdemonstratedthroughtherepresentationandexpositionofpoliciesdefinedinseveralpopularpolicylanguages.WedescribetheintegrationandenforcementofIsmenepolicywithintheAntigonecommu-nicationsystem.

Policyhasbeenusedindifferentcontextsasavehicleforrepresentingauthorizationandaccesscontrol[31,5,9,32,29],peersessionsecurity[33],qualityofserviceguaran-tees[7],andnetworkconfiguration[3,2].Theseapproachesdefineapolicylanguageorschemaappropriatefortheirtar-getproblemdomain.Thispaperexpandsonthisworkbydefiningageneralapproachinwhichpolicyisusedtobothprovisionandtoregulateaccesstocommunicationservices.Theproblemofreconcilingpoliciesinanautomatedmannerisonlybeginningtobeaddressed.Inthetwo-partycase,theemergingSecurityPolicySystem(SPS)[33]definesaframeworkforthespecificationandreconcilia-tionofsecuritypoliciesfortheIPSecprotocolsuite[23].Reconciliationislargelylimitedtointersectionofspeci-fieddatastructures.Inthemulti-partycase,theDCCMsystem[13]providesanegotiationprotocolforprovision-ing.DCCMdefinesthesessionpolicyfromtheintersec-tionofpolicyproposalspresentedbyeachpotentialmem-ber.Eachproposaldefinesarangeofacceptablevaluesalongamulti-dimensionalpolicystructure.Hence,recon-ciliationinthesesystemsislargelybasedontheintersectionofpolicyschema.Incontrast,thisworkattemptstodefineageneralframeworkuponwhichmoreflexibleexpression-orientedpoliciesaredefinedandreconciled.

Language-basedapproachesforspecifyingauthorizationandaccesscontrolhavelongbeenstudied[31,9,32,29],buttheygenerallylacksupportforreconciliation.Thesesystemstypicallyidentifyarigoroussemanticsfortheeval-uationofauthorizationstatements.ThePolicyMaker[5]andKeyNote[6]trustmanagementsystemsprovideapow-erfulframeworkfortheevaluationofcredentials.Trustmanagementapproachesfocusontheestablishmentofchainsofconditionaldelegationdefinedinauthenticatedpolicyassertions.Hence,policyisdictatedbyentitiestowhichsessionauthorityisdelegated,ratherthanthroughthereconciliationofparticipantrequirements.

Thefollowingsectionconsiderstherequirementsofageneral-purposepolicylanguage.Section3considersthelimitsandmethodsofreconciliationinourgeneralpolicymodel.Section4presentstheIsmenelanguage.Section5illustratestheuseofIsmenebyrepresentingpoliciessup-portedbyexistinglanguages.Section6brieflydiscussesourexperienceswiththeimplementationanduseofIsmene.Section7concludes.

2.Requirements

Toillustratethepolicyreconciliationneeds,wepresentverysimplifiedsecurityrequirementsforanexamplecon-ferencingapplication,tc.Thetcapplicationistobede-ployedwithinacompany,

.’sor-ganizationalpolicyfortcrequiresthefollowing:

theconfidentialityofallsessioncontentmustbepro-tectedbyencryptionusingor(pro-visioningrequirement)

thesessionisrestrictedtoemployees(au-

thorizationrequirement)

Nowsupposewishestosponsorasessionoftcunderthefollowingpolicy:

Alicewishestouseonlycryptographicalgo-rithmonly(provisioningrequirement);and

shewishestorestrictthesessiontotheteam(accesscontrolrequirement)

Abasicrequirementonapolicyapproachforthisscenarioisthatitmustreconciletheprovisioningandaccesscontrolrequirements(policies)statedbyanynumberofinterestedparties.Itisthroughthisprocessofreconciliationthataconcrete,enforceablepolicyisdeveloped.Intheaboveex-ample,Alice’sandthewidget.compoliciesarereconciledtoarriveatapolicythatrestrictstheparticipantstomem-bersof’steam(accesscontrolrequirement),andtcmustbeconfiguredsothatallcontentisencryptedusing(provisioningrequirement).

Ingeneral,securityrequirementscanbemorecomplex.Forexample,Alicemaywishtorestrictaccesstocertainhoursoftheday,requirethatthesessionberekeyedperi-odically,etc.(environment-dependence).Insomecases,thesessionmustbeabletomakeaccesscontroldecisionsbasedontheuseandconfigurationofsecuritymechanisms;forexample,admitamemberonlyifAESisbeingusedforensuringconfidentiality.Ourlanguagepermitssuchde-pendenciesbetweenauthorizationandprovisioningpolicy.Thisrepresentsadivergencefrommanyexistingworksthattreatauthorizationandprovisioningindependently.

3.Policy

ThissectionpresentstheIsmeneapproachtopolicyman-agement.DepictedinFigure1,asessionisestablishedbe-tweentwoormoreentities.Eachparticipantinthesessionsubmitsasetofrelevantdomainpoliciestotheinitiator.Theinitiatormaybeaparticipantorexternalentity(e.g.,policydecisionpoint[14]).Statedbyapolicyissuer,ases-sionpolicyisatemplatedescribinglegalsessionprovision-ingandthesetofrulesusedtogovernaccess.

Participant 1󰀀Client Enterprise󰀀Internet󰀀Particilpant 󰀀nServer Enterprise󰀀App. Policy󰀀Enterprise Policy󰀀Domain󰀀Policies󰀀Session Policy󰀀App. Policy󰀀Enterprise Policy󰀀Reconciliation󰀀Policy Instance󰀀Figure1.Policyconstruction-Asession-specificpolicyinstancefortwoormorepar-ticipantsiscreatedbyaninitiator.Eachpar-ticipantsubmitsasetofdomainpoliciesiden-tifyingtherequirementsrelevanttotheses-sion.Theinitiatorconstructsthepolicyin-stancecompliantwitheachdomainandthesessionpolicythroughreconciliation.

Domainpoliciesstateconditionalrequirementsandre-strictionsplacedonthesession.Inthescenariodescribedintheprevioussection,Alice’sdomainpolicystatesthatAESmustbeusedandthesessionrestrictedmembersoftheBlueWidgetteam.Thesetofpoliciesappropriateforaparticularsessionisdependentontheenvironmentinwhichitistooccur.ThescenariodescribedinFigure1depictsanenvironmentinwhichthetwoparticipantsstatepoliciesforthesupportedapplication,aswellastheirlocalenterpriseenvironments.Theinstanceistheresultofthereconcilia-tionofthesession,application,andenterprisepolicies.Aninitiatorusesthereconciliationalgorithmtocreateapolicyinstancecompliantwiththesessionandeachdomainpolicy.Apolicyiscompliantifallstatedrequirementsandrestrictionsarerealizedintheresultinginstance.Ifanin-stanceisfound,itisusedtogoverntheprovisioningandauthorizationofthesubsequentsession.Ifaninstancecan-notbefound,thentheparticipantsmustrevisethedomainpoliciesorabortthesession.Aninstanceconcretelyde-finessessionprovisioningandauthorization.Theinitiatoristrustedtoreconcilethesessionanddomainpoliciescor-rectly1.

AsessionpolicyinIsmeneisauthoritative;theinstancemustbedirectlyderivedfromthesessionpolicy2.Domainpoliciesareconsultedonlywhereflexibilityisexpressly

formulatedasasatisfactionproblem;theinitiatorseeksaninstancethatsatisfiesthesetofexpressions.Hence,thepro-visioningexpressionindomainpoliciesneedonlyspecifythoseaspectsofpolicythattheissuerwishestoinfluence.Authorizationpolicymapsidentitiesorcredentialsontoasetofaccessrights[31].Asinprovisioning,authorizationstatementsaremodeledaslogicalexpressions.Eachautho-rizationexpression,calledanactionclause,isdefinedasaconjunctionofpositiveconditionals3.Forexample:

statesthat“readoperationshouldsucceediftheuserisBob,thefilebeingaccessedis/etc/hosts,andtheACLforthefileallowsreadaccesstoBob”.AsinothersystemssuchasKeyNote[5],theinterpretationofeachconditionalislefttotheenvironment;theestablishmentoftheidentity,file,andtheevaluationofthefile’sACLisoutsidethescopeofthepolicyspecification.

3.2.ProvisioningReconciliation

Provisioningreconciliationsearchesforasetofmecha-nismconfigurationsthatsatisfythepolicyexpressions.WeshowinAppendixAthatinitsmostgeneralform,reconcil-iationofevenoneexpressionisintractable;anyinstanceofpositive,one-in-ksatisfiability[30,15],aknownintractableproblem,canbereducedtotheproblemoffindingasolutionthatsatisfiesapolicyexpressionwithpickstatements.Thisresultisinstarkcontrasttoneedsofpolicymanagement;thealgorithmsusedtomanagepolicymustbeefficient.Inresponse,weplacethefollowingrestrictionoftheconstruc-tionofpolicy:

PolicyRestriction:Amechanismconfigurationcanonlybestatedinatmostonepickstatementinapolicy.

Forexample,if,,andaremechanismconfigurations,thefollowingpolicyexpressionisnotallowedbytheaboverestrictioninasinglepolicybecauseoccurstwiceinthepolicyexpression:

Ontheotherhand,thepolicyexpressionpresentedinSec-tion3.1islegalbecauseand

areconsidereddifferentmecha-nismconfigurations,thoughtheyrefertothesamemecha-nism.

Basedonthisrestriction,thefollowingalgorithmrec-oncilesasessionpolicyandonedomainpolicy.Figure2presentsanexampleofthealgorithmbeingappliedona

(SessionPolicy)(DomainPolicy)

==

===

======

hk󰀀h󰀀k󰀀g󰀀gh󰀀=

gj󰀀j󰀀jk󰀀Figure2.Reconciliation-theIsmenereconciliationalgorithmiterativelyreducestheintersectionofthesession()anddomain()policies.Anyreconcilablepolicywillconvergeonconfigurations(denotedbysinglelettervariables–e.g.)existingexactlyonceineachpolicy.Theremainingpickstatementscanbereconciledintoaconcreteinstance()usingan(efficient)edgecoveralgorithm.

n-PolicyReconciliationAlgorithm

Inthecasewheremorethanonedomainpolicyneedstobereconciledwithasessionpolicy,asimplealgorithmwouldbetoreconcilethesessionpolicywithonedomainpolicyatatime.Thepolicyexpressionresultingfromeach2-partyreconciliationisusedasthesessionpolicyforrec-onciliationwiththenextdomainpolicy.Asafinalstep,aspecificconfigurationischosenfrompickstatementsre-mainingafterthefinalreconciliation(duetoequivalentcon-figurations).Areasonablestrategychoosesthefirstconfig-urationineachremainingpickstatementfromthesessionpolicy,assumingthatthesessionpolicylistsconfigurationsindecreasingorderofpreference.

Theorderingofreconciliationmayaffectthereconcilia-tionresults;someorderingsofdomainpolicieswillnotbereconcilable,whileotherswill.Forexample,considerthefollowingsessionanddomainpolicies:

Ifdomainpolicy1isconsideredfirst,thepoliciesmayrec-oncileto().Thus,domainpolicy2wouldnotberecon-cilable.Ifdomainpolicy2wereconsideredfirst,reconcili-ationwouldarriveat(),andthusbereconcilablewithdomainpolicy1.Theintroductionofthethirdpolicyvio-latesthepropertythataspecificconfigurationoccursinatmosttwopickstatementsinthereconciliationexpressions–thereductiontotheedgecoverproblemfailsinsuchacase.Itcanbeshownthattheproblemisintractablebyareductionfromtheone-in-threesatisfiabilityproblem.

Wherereconciliationisnotpossible,itmaybedesirabletofindasubsetofpoliciesthatcanbereconciled.Onepo-tentialreconciliationalgorithm,LargestSubsetReconcilia-tion(LSR),wouldattempttofindaninstancereconcilable

withthelargestnumberofdomainpolicies.LSRhastheundesirablepropertythatitmayfailtoallowtheparticipa-tionofrequiredmembers(forexample,byexcludingthevideosourceinavideoconference).Moreover,asshowninAppendixB,LSRisalsointractable.

Anextensiontothereconciliationalgorithmestablishesanorderingofdomainpolicies.Higherprioritizedpoliciesareconsideredfirstandlowerprioritypoliciesareconsid-eredonlywhenhigherprioritypoliciesprovidenoguid-ance;otherwisetheymaybeexcluded.ThisalgorithmispolynomialtimeandhasbeenusedextensivelytoderivethesecuritypolicyintheAntigonecommunicationsystem[28].Ourexperienceinusingthepolicyframeworkforarangeofgroupcommunicationapplicationsindicatesthatoftenpickstatementsintersectwithatmostonepickstatementofallotherpolicies.Forexample,allIKEpolicieswillde-,,andfinesimilarpickstatementsfor

mechanisms.Inthiscasetheproblemofreconciliationistractable.Anyviolationofthisproperty(overasetofses-sionanddomainpolicies)canbeefficientlydetectedbyasimplescanofthepolicies–inthatcase,theheuristicsug-gestedaboveofprioritizingdomainpoliciescanbeused.

3.3.AuthorizationReconciliation

Theauthorizationpolicydefinedinaninstanceisthere-sultofthereconciliationofactionclausesofallconsideredpolicies.However,thesemanticsofsuchanoperationareunclear;onemayviewreconciliationofaccesscontroltobeanintersection(logicalORofeachpolicy),aunion(log-icalAND),orsomethingelse(sessionANDatleastonedo-mainpolicy).Thefirstapproach(logicalOR),however,hastheunfortunatesideaffectthatapermissivedomainpolicycancircumventanycontrolsstatedinthesessionordomainpolicies.

Ourreconciliationalgorithmtakestheconservativeap-proachofacceptingthelogicalANDofallaccesscontrolpolicies.Thisapproachwillnotallowanycontrolstobecir-cumvented;however,arestrictivedomainpolicycancauseaccesstobedenied.WediscussourexperiencewiththisissuefurtherinSection6.

Wenowillustrateauthorizationreconciliation.Consideranexamplesessionpolicythatdefinestheactionclause4

(

)andtwodomainpolicieswithactionclauses(:::accept;)and(:::accept;),respectively(whereisanactionandeachacondition).Theresult-ingpolicyfromtheAuthenticationreconciliationalgorithmis:

3.4.Compliance

Notalldomainpoliciesarerequiredto(oroftencan)beconsultedduringreconciliation.Hence,beforeparticipat-inginasession,aparticipantmustbeabletocheckthecomplianceofitsdomainpolicywiththeinstancethatisgoverningtheactivesession.Complianceissuccessfulifallrequirementsstatedinthedomainpolicyaresatisfiedbytheinstance.Notethatcomplianceinthisworkservesadif-ferentpurposethanthecompliancealgorithmsintrustman-agement[5,10,4];ourcompliancealgorithmdetermineswhetheraninstanceisconsistentwithadomainpolicy.Incontrast,complianceintrustmanagementsystemsattemptstodetermineiftheavailablecredentialsandthecurrentsys-temstatesatisfythetrustpolicy.

Aswithreconciliation,therearetwophasesofcom-pliance;provisioningandauthorization.Theprovisioningcompliancealgorithmcomparesdomainpolicywithare-ceivedpolicyinstance.Eachconfigurationandpickstate-mentmustbesatisfiedbytheinstance.Aconfigurationissatisfiedifitisexplicitlystatedintheinstance.Apickstate-mentissatisfiedifexactlyoneconfigurationiscontainedintheinstance.Thus,provisioningcomplianceisassimpleastestingthecontainmentoftheevaluateddomainpolicybytheinstance.Moreprecisely,aninstancedescribesatruthassignmentforthe(configuration)variablesinthedomainpolicyexpression.Theinstanceiscompliantiftheexpres-sionissatisfied(evaluatestoTRUE)bythetruthassign-ment.

Severalresearchershaveexaminedtheproblemofcom-plianceinanauthorizationpolicy.GongandQian’smodelofapolicycomposition(i.e.,reconciledpolicies)defineatwo-principlecompliancedefinition[17].Theprincipleofautonomyrequiresthatanyactionacceptedbyonepolicy

DomainpolicyA

tweenconfigurations.Eachassertioncontainsatag(as-sert),aconjunctionofconditions,andaconjunctionofconsequences.Conditionsandconsequencesarerestrictedtopickandconfigurationstatement,andmaybenegated.Semantically,assertionsstatethattheconsequencesmustholdwheretheconsequencesaretrue(i.e.,conditioncon-junction,consequenceconjunction,

).Forexam-ple,anissuermaywishtoassertacompletenessrequire-ment[22,8]thatconfidentialityofapplicationdataalwaysbeprovided.Thus,knowingthatthessl,ipsec,andsshtransformsaretheonlymeansbywhichconfidentialitycanbeprovided,theissuerstatesthefollowing(conditionless)assertionexpression:

Analysisdeterminesifaninstance(orpolicy)satisfiestheassertion:exactlyoneconfidentialitymechanismmustbeconfigured.

Analysistechniquesguaranteeingcorrectsoftwarecon-structionhavebeenstudiedextensivelywithincomponentarchitectures[20,25].Theseapproachestypicallydescriberelationsdefiningcompatibilityanddependencebetweencomponents.Aconfigurationisdeemedcorrectifitdoesnotviolatetheserelations.Forexample,Hiltunen[20]de-finestheconflict,dependency,containment,andindepen-dencerelations.Thefollowingdescribesassertionexpres-sionsrepresentingtheserelations(whereindependenceisassumed):

conflict(AisincompatiblewithB)dependency(AdependsonB)containment(AprovidesB)

Ananalysisalgorithmassesseswhetherapolicycanoraninstancedoesviolatetherelevantassertions.Theonlinepolicyanalysisalgorithmassessesaninstancewithrespecttoasetofassertions.Thisalgorithmevaluatestheasser-tionexpressionsagainstthetruthassignmentdefinedbytheinstance.Anyfalseevaluationresultindicatesthatanas-sertionhasbeenviolated,andtheinstancecannotbeused.Obviously,byvirtueofthetractabilityofexpressionevalu-ation,onlineanalysisisefficient.

Anofflinepolicyanalysisalgorithm(OFPA)attemptstodetermineifanyinstanceresultingfromreconciliationcanviolateasetofassertions.DemonstratedinAppendixB,offlineanalysisisintractable(coNP).However,thisalgo-rithmneedonlybeexecutedonce(atissuance),andthusdoesnotimpactsessionsetup.Moreover,mostreasonableconfigurationswehaveencounteredexhibitadegreeofin-dependence;theintroductionofaconfigurationislargelytheresultofthereconciliationofafewclauses.Hence,theevaluationofanassertioncanbereducedtotheanalysisofonlythoseclausesuponwhichtheconfigurationsstatedintheassertionsaredependent.Wepresentanoptimizedal-gorithmforOFPAin[26].

4.Ismene

ThissectionpresentsabriefoverviewoftheIsmenepol-icylanguage.Ismenespecifiesconditionalprovisioningandauthorizationrequirementsthroughageneral-purposepol-icylanguage.Athoroughsurveyofthegrammarandse-manticsofIsmeneispresentedin[26].Ismenepoliciesarecollectionsoftotallyorderedprovisioning,action,andas-sertionsclauses.Forbrevity,weomitthediscussionofas-sertionclauses(seesection3.5).

4.1ProvisioningClauses

Eachprovisioningclauseisdefinedasthetuple:

:::;

Tagsareusedtoassociatemeaningfulnameswithprovi-sioningrequirements.Conditionsarepredicatesthatiden-tifythecircumstancesunderwhichtheconsequencesareapplicable.Consequencesstatesessionprovisioningre-quirementsthroughconfigurationsandpickstatements,oridentifyrelevantsub-policiesthroughtags.Thereservedprovisiontagisusedtonametheoverallprovision-ingrequirements.Considerthefollowingsimpleexample,wherex,y,z,andwspecifymechanismconfigurations:

provision:::confidentiality,keymgmt;confidentiality:c1,c2::x,y;confidentiality:::pick(w,z);rekeying:::d

Thefirst(provision)clausesaysthatthepolicymustpro-visionbothconfidentialityandkeymanagementservices(tags).Thesecondandthirdclausesstatethatif

istrue,xandymustbeconfigured;otherwiseeitherworz(butnotbothorneither)mustbeconfigured.Thefinalclausesaysthatdmustbeconfiguredunderallcircum-stances.Therefore,thepolicyexpressionusedasinputtoreconciliationiswhereistrueatthetimeofreconciliation,andwhereisfalse.Notethattheorderingofclauseswiththesametag(e.g.,confi-dentialitytag)dictatestheorderofevaluation.Ifthecondi-tionalsforanearlierinstanceofthetagholds(e.g.,),thoseconsequences(e.g.,xandy)mustbeenforced,andthesubsequentclausesforthesametagareignored.

Conditionalsinaclauseoftenrefertoattributes.Anat-tributedescribesasingleorlist-valuedinvariant.Forexam-ple,thefollowingattributesdefineasingle-valuedversionnumberandlist-valuedACL:

version:=<1.0>;

JoinACL:=<{alice},{bob},{trent}>;

Anoccurrenceofthesymbol“$”signifiesthattheattributeshouldbereplacedwithitsvalue.AsintheKeyNoteactionenvironment[4],theattributesetisthesetofallattributes.

%IsmeneProvisioningClauses

provision:PrivSession($inaddr,$ipt,$oaddr,$opt)

::strong_key_mgmt,confidentiality;

provision:::weak_key_mgmt,confidentiality;strong_key_mgmt:Manager($ent)

::config(dh_key(refresh,60));

strong_key_mgmt:::config(dh_key(refresh,240));weak_key_mgmt:::config(lm_key(refresh,300));confidentiality:::pick(config(dhndlr(3des)),

config(dhndlr(des)));%IsmeneActionClauses

join:config(dhndlr(des)),In($JoinACL,$joiner),

Credential(&cert,sgner=$ca,subj.CN=$joiner)::accept;

join:Credential(&cert,sgner=$ca,delegatejoin=true),

Credential(&tocert,sgner=$cert.pk,

subj.CN=$joiner)

::accept;

Figure3.IsmenePolicy-Theprovisioningclausesinthesessionanddomainpoliciesareevaluatedtoarriveatthepolicyexpres-sionsusedasinputtoreconciliation.Actionclausesareevaluatedoverthelifetimeofthesessiontoenforceauthorizationpolicy.

Enforcementinfrastructures(e.g.,applications)providead-ditionalevaluationcontextbyaddingattributestotheat-tributeset.ConditionalevaluationisoutsidethescopeofIs-mene;theenvironmentinwhichIsmeneisusedisrequiredtoprovideapredicateinterfaceforeachcondition.ThisissimilartoGAAAPIconditionupcalls[29]).

ConsidertheprovisioningclausesinFigure3thatde-finerequirementsforpublicandprivatesessionsoftc.Ifthesessionisprivate(asclassifiedbysessionaddressat-mgmtclausesareeval-tributes),thenthestronguated;otherwiseweakmgmtisevaluated.Theconfidentialityclauseisevaluatedineithercase.ThestrongkeymanagementclausestatesthataDiffie-Hellman[12]keyingmechanismmustbeused.Thebehav-iorofthismechanismisfurtherrefinedtorefreshtheses-sionkeyevery60(240)secondswhereamanagementis(isnot)present.Wherethesessionisnotdeemedprivate,theweakmgmtclausesimplyprovisionstheLeighton-Micalikeymanagementmechanism[24].Theconfidential-ityclauseinstructsthedatahandlermechanismtouseeither3DESorDES,dependingontheresultofreconciliation.Notethatthemechanismsindicatedinthepolicyspeci-fication(e.g.,dh

IKESessionPolicy(Responder)provision:selector(any,12.14.9.1,17,23,any)::pick(config(ike(cast-cbc,sha1,group2)),

config(ike(cast-cbc,md5,group2))),

config(preshare());auth:config(ike(preshare)),

Credential(&cert,modulus=$prekey.mod)::accept;

Figure4.IKEPolicy-session(responder)anddomain(requestor)policiesareusedtoim-plementIKEphaseonepolicynegotiation.TheIKESApolicy(instance)isarrivedatthroughtheintersectionoftheresponder(session)policyandrequestor(domainpol-icy)proposals.

Thesepoliciesservetohighlightthesimilaritiesanddiffer-encesbetweenIsmeneandotherpolicylanguagesandar-chitectures.

5.1.InternetKeyExchange

TheInternetKeyExchange[19](IKE)dynamicallyes-tablishessecurityassociations(SA)fortheIPSec[23]suiteofprotocols.TheIKEphaseoneexchangenegotiatesanIKESAforsecuringIPSecSAnegotiationandkeyagree-ment.Policyisnegotiatedthroughofaroundofpolicypro-posalsdefiningthealgorithmsandmeansofauthenticationprotectingtheIKESA.

Figure4depictsIsmenepolicieswhosereconciliationmodelsanIKEphaseonepolicynegotiation.Thesessionpolicy(IKEpolicyoftheresponder)anddomainpolicy(IKEpolicyproposal)arereconciledtoarriveattheSApolicy.SimilartoIPSecselectors,theselectorcondi-tionintheexampleidentifieswheretheidentifiedpolicyisrelevant.Hence,bycreatingsimilarpolicieswithdifferentselectors,itispossibletoconstructpoliciesforallIPSectrafficsupportedbyaparticularhostornetwork;aprovi-sionclauseandassociatedselectoriscreatedforeachclassoftrafficthatrequiresIKESAnegotiation.

AsinIKEnegotiation,thereconciliationalgorithmin-tersectsthepolicyproposalsresultingintheprovisioning

DCCMSessionPolicy(CCNT)

provision:::

pick(config(conf(3DES)),config(conf(CAST))),pick(config(kman(OFT)),config(kman(LKH))),pick(config(trans(SSH)),config(trans(SSL)),

config(trans(IPSec)));

DCCMDomainPolicy2(member)

GAA-APIPrinterPolicyTokenValue

Kv5

rightssubmittimePSTprinterlpd

Authority

GROUP

manager

operator@acme.edu

job

IsmenePrinterPolicy

jobrighttoanyentityau-thenticatedbythesameKerberosservice.Moreover,theclausestatesthatconditionsunderwhichjoeisallowedac-cessareexplicitlyimposedonanysuchdelegation.Forbrevity,weomittheoperator’srighttodelegatejobsub-mission.

5.4.KeyNote

CentraltoKeyNotetrustmanagementsystemistheno-tionofcredentials[4,6].Acredentialisastructuredpol-icydescribingconditionaldelegation;anauthority(autho-rizer)statesthataprincipal(licensee)hastherighttoper-formsomeactionunderasetofconditions.Anactionisallowedifadelegationchaincanbeconstructedfromacre-dentialmatchingtherequestedactiontoatrustedlocalpol-icy.Userssupplycredentialsasisneededtogainaccess.Hence,KeyNotesignificantlyeasestheburdenofpolicymanagementbyallowingpolicytobedistributedtousers,ratherthanconfiguredatallpolicyenforcementpoints.TheKeyNotepolicydepictedinFigure7delegatesdecisionsaboutIPSecpolicytotheADMIN

KEYcredentialencapsulatesapolicythattheuser

Bob(whoisidentifiedbyakey)shouldbeallowedaccessifIPsecisconfiguredwiththe3-DESorCASTencryptionalgorithmsandSHA-1HMACsareusedformessageau-thentication.

TheIsmenepoliciesstateasimilarrequirement,whilealsoprovidingareconciliationalgorithmforgeneratinganacceptablepolicyinstancetoprovisionthesession.How-

KeyNoteLocalPolicy

ADMIN_KEY:=<0xba34...>;provision:::

pick(config(esp_enc_alg(3des)),config(esp_enc_alg(aes)),

config(esp_enc_alg(cast))),

pick(config(esp_auth_alg(hmac-sha)),

config(esp_auth_alg(hmac-md5)));

accept_policy:

Credential(&policy,policy.issuer=$ADMIN_KEY)

::accept;

KeyNoteIPSecCredential

signer:=<0xba34...>;signature:=<0x98cc...>;id:=;

provision:::pick(config(esp_enc_alg(3des)),

config(esp_enc_alg(cast))),

config(esp_auth_alg(hmac-sha));

Figure7.KeyNotePolicy-KeyNotecredentialsareonlyconsultedwheretheyhavebeenexplicitlydelegatedauthoritybyalocalpolicy.Conversely,Ismeneregulatestheacceptanceofpolicythroughtheproperassignmentofaccept

policies.Theinvestigationalsosuggestedareasoffurtherstudy:

Performance-Theenforcementoffine-grainedaccesscontrolcannegativelyaffectperformance.Forexample,onefile-systemmirroringpolicyrequirestheevaluationofsendactionclausespriortoeachpackettransmission.Suchevaluationslowedfiletransfers.Wenotedthatbe-causeactionclauseevaluationwasofteninvariant,resultscouldbecached.Wepresentthedesignofapolicyevalua-tioncacheandacomprehensivestudyofenforcementper-formancein[26].Cachingsignificantlymitigatedthecostofpolicyenforcement.

AuthorizationReconciliation-Asauthorizationpoliciesde-finedbyaninstanceareconstructedfromtheconjunctionofthesessionanddomainpolicies,clausescanbecomerestric-tive.Forexample,considerthecasewherethesessionpol-icyrequires,forsomeaction,thepresentationofanX.509certificate,andadomainpolicyrequirethepresentationofaKerberosticket.Inthiscase,theresultinginstancere-quiresthatbothacertificateandaticketbepresented.Wearecurrentlyinvestigatingwaysinwhichoverly-restrictiveorunsatisfiableauthorizationpoliciescanbedetectedatrec-onciliationtimeoratrun-time.

PolicyDependencies-Theeffectivenessofanalysisispred-icatedonthecorrectconstructionofpolicyassertions.Inpractice,mechanismsandconfigurationshavecomplexre-lationships.Assertionconstructionrequiresacomprehen-siveknowledgeofuseofthecryptographicalgorithms,pro-tocols,andservices.Thisknowledgemustbereflectedin

policyactionpriortotheaccep-tanceofanydomainpolicyandacceptedwheresignedbyADMIN

sourcecodeanddocumentationfortheIsmenelanguage,theaug-mentedAntigonecommunicationsystem,andapplicationsarefreelyavail-ablefromhttp://antigone.eecs.umich.edu/.

5All

thepolicyconstruction.ThissituationisnotuniquetoIs-mene;anypolicyinfrastructuremustensurethatunsafein-stancesarerejected.

7.Conclusions

Inthispaper,wehavepresentedamodelandlanguageforthespecificationandreconciliationofsecuritypolicies.Weshowthatthegeneralproblemofreconciliationisin-tractable.However,byrestrictingthelanguage,weshowthatreconciliationoftwopoliciesbecomestractable.Rec-onciliationofthreeormorepoliciesremainsintractable.Weidentifyheuristicsthatdetectsituationswhereintractabilityislikelytooccurandprioritizepoliciesduringreconcilia-tiontoachieveefficientreconciliation.

Acompliancealgorithmdetermineswhetherapolicyin-stanceisconsistentwithaparticipant’sdomainpolicy.Theanalysisalgorithmdetermineswhethertheprovisioningofasessionadherestoasetofassertionsthatexpresscorrect-nessconstraintsonapolicyinstance.Weidentifyefficientalgorithmsforbothcomplianceandanalysis.Wedemon-stratethatthemoregeneralproblemofdeterminingifanyinstancegeneratedfromapolicycanviolateasetofcorrect-nessassertionsisintractable(incoNP).

Basedonthemodel,wepresentedanoverviewoftheIs-menepolicylanguageanddemonstrateditsexpressivenessandlimitationsthroughtherepresentationofpoliciesde-finedinseveralpolicylanguages.Thelanguagehasbeenimplementedandisbeingusedinseveralnon-trivialappli-cations.

Networksarebecomingmoreopenandheterogeneous.Thisstandsinstarkcontrasttothesingularnatureofcon-temporarysecurityinfrastructures;communicationpartici-pantshavelimitedabilitytoaffectsessionpolicy.Hence,theparticipantsecurityrequirementsareonlyaddressedinasmuchastheyareforeseenbypolicyissuers.Ismene,andworkssimilartoit,seektoexpandthedefinitionandusageofpolicysuchthatrun-timepolicyistheresultoftherequirementsevaluation,ratherthandictatedbythepolicyissuers.

8.Acknowledgments

WewouldliketothankPeterHoneymanforhismanycontributionstothisworkwithintheAntigoneproject.WewouldalsoliketothankAviRubin,SugihJamin,TrentJaeger,PaulResnick,andtheanonymousreviewersfortheremanythoughtfulcomments.

References

[1]D.Balenson,D.Branstad,P.Dinsmore,M.Heyman,and

C.Scace.CryptographicContextNegotiationTemplate.TechnicalReportTISR#07452-2,TISLabsatNetworkAs-sociates,Inc.,February1999.

[2]Y.Bartal,A.J.Mayer,K.Nissim,andA.Wool.Firmato:A

novelfirewallmanagementtoolkit.InIEEESymposiumonSecurityandPrivacy,pages17–31,1999.

[3]S.Bellovin.DistributedFirewalls.;login:,pages39–47,

1999.

[4]M.Blaze,J.Feigenbaum,J.Ioannidis,andA.Keromytis.

TheRoleofTrustManagementinDistributedSystemsSe-curity.InSecureInternetProgramming:IssuesinDis-tributedandMobileObjectSystems,volume1603,pages185–210.Springer-VerlagLectureNotesinComputerSci-enceState-of-the-Artseries,1999.NewYork,NY.

[5]M.Blaze,J.Feigenbaum,andJ.Lacy.DecentralizedTrust

Management.InProceedingsofthe1996IEEESymposiumonSecurityandPrivacy,pages1–173,November1996.LosAlamitos.

[6]M.Blaze,J.Feignbaum,J.Ioannidis,andA.Keromytis.The

KeyNoteTrustManagementSystem-Version2.InternetEngineeringTaskForce,September1999.RFC2704.

[7]D.C.BlightandT.Hamada.Policy-BasedNetworkingAr-chitectureforQoSInterworkinginIPManagement.InPro-ceedingsofIntegratednetworkmanagementVI,DistributedManagementfortheNetworkedMillennium,pages811–826.IEEE,1999.

[8]D.BranstadandD.Balenson.Policy-BasedCryptographic

KeyManagement:ExperiencewiththeKRPProject.InPro-ceedingsofDARPAInformationSurvivabilityConferenceandExposition(DISCEX’00),pages103–114.DARPA,January2000.

[9]L.CholvyandF.Cuppens.AnalyzingConsistancyofSe-curityPolicies.In1997IEEESymposiumonSecurityandPrivacy,pages103–112.IEEE,May1997.Oakland,CA.[10]Y.Chu,J.Feigenbaum,B.LaMacchia,P.Resnick,and

M.Strauss.REFEREE:TrustManagementforWebAp-plications.InProceedingsofFinancialCryptography’98,volume1465,pages254–274,Anguilla,BritishWestIndies,February1998.

[11]S.Cook.TheComplexityofTheorem-ProvingProcedures.

InProceedingsof3thAnnualACMSymposiumonTheoreyofComputing,pages151–158.ACM,1971.

[12]W.DiffieandM.Hellman.NewDirectionsinCryptography.

IEEETransactionsonInformationTheory,IT-22(6):4–654,November1976.

[13]P.Dinsmore,D.Balenson,M.Heyman,P.Kruus,C.Scace,

andA.Sherman.Policy-BasedSecurityManagementforLargeDynamicGroups:AOverviewoftheDCCMProject.InProceedingsofDARPAInformationSurvivabilityConfer-enceandExposition(DISCEX’00),pages–73.DARPA,January2000.HiltonHead,S.C.

[14]D.Durham,J.Boyle,R.Cohen,S.Herzog,R.Rajan,and

A.Sastry.RFC2748,TheCOPS(CommonOpenPolicyService)Protocol.InternetEngineeringTaskForce,January2000.

[15]M.R.GareyandD.S.Johnson.ComputersandIntractibil-ity,AGuidetotheTheoryofNP-Completeness.W.H.Free-manandCo.,NewYork,NY,firstedition,1979.

[16]M.R.Garey,D.S.Johnson,andL.Stockmeyer.SomeSim-plifiedNP-CompleteGraphProblems.TheoreticalCom-puterScience,(1):237–267,1976.

[17]L.GongandX.Qian.TheComplexityandComposabilityof

SecureInteroperation.InProceedingsoftheIEEESympo-siumonResearchinSecurityandPrivacy,pages190–200,Oakland,California,May1994.IEEE.

[18]R.Greenlaw,H.Hoover,andW.Ruzzo.LimitstoParallel

Computation:P-CompletenessTheory.OxfordUniversityPress,firstedition,1995.

[19]D.HarkinsandD.Carrel.TheInternetKeyExchange.In-ternetEngineeringTaskForce,November1998.RFC2409.[20]M.Hiltunen.ConfigurationManagementforHighly-CustomizableSoftware.IEEProceedings:Software,

145(5):180–188,1998.

[21]R.Housley,W.Ford,W.Polk,andD.Solo.InternetX.509

PublicKeyInfrastructureCertificateandCRLProfile.Inter-netEngineeringTaskForce,January1999.RFC1949.

[22]S.Jajodia,P.Samarati,andV.Subrahmanian.ALogical

LanguageforExpressingAuthorizations.InProceedingsofthe1997IEEESymposiumonSecurityandPrivacy,pages31–42,Oakland,CA,March1997.

[23]S.KentandR.Atkinson.SecurityArchitecturefortheIn-ternetProtocol.InternetEngineeringTaskForce,November1998.RFC2401.

[24]T.LeightonandS.Micali.Secret-keyAgreementwithout

Public-KeyCryptography.InProceedingsofCrypto93,pages456–479,August1994.

[25]X.Liu,C.Kreitz,R.vanRenesse,J.Hickey,M.Hayden,

K.Birman,andR.Constable.BuildingReliableHigh-PerformanceCommunicationSystemsfromComponents.InProceedingsof17thACMSymposiumonOperatingSys-temsPrinciples(SOSP’99),volume33,pages80–92.ACM,1999.

[26]P.McDaniel.PolicyManagementinSecureGroupCommu-nication.PhDthesis,UniveristyofMichigan,AnnArbor,MI,August2001.

[27]P.McDaniel,A.Prakash,andP.Honeyman.Antigone:A

FlexibleFrameworkforSecureGroupCommunication.InProceedingsofthe8thUSENIXSecuritySymposium,pages99–114,August1999.

[28]P.McDaniel,A.Prakash,J.Irrer,S.Mittal,andT.Thuang.

FlexiblyConstructingSecureGroupsinAntigone2.0.InProceedingsofDARPAInformationSurvivabilityConfer-enceandExpositionII,pages55–67.IEEE,June2001.[29]T.RyutovandC.Neuman.RepresentationandEvaluation

ofSecurityPoliciesforDistributedSystemServices.InPro-ceedingsofDARPAInformationSurvivabilityConferenceandExposition,pages172–183,HiltonHead,SouthCar-olina,January2000.DARPA.

[30]T.J.Schaefer.TheComplexityofSatisfiabilityProblems.

InProceedingsof10thAnnualACMSymposiumonTheoreyofComputers,pages216–226.ACM,1978.NewYork,NewYork.

[31]T.WooandS.Lam.AuthorizationinDistributedSystems;A

NewApproach.JournalofComputerSecurity,2(2-3):107–136,1993.

[32]T.WooandS.Lam.DesigningaDistributedAuthorization

Service.InProceedingsofINFOCOM’98,SanFrancisco,March1998.IEEE.

[33]J.Zao,L.Sanchez,M.Condell,C.Lynn,M.Fredette,P.He-linek,P.Krishnan,A.Jackson,D.Mankins,M.Shepard,andS.Kent.DomainBasedInternetSecurityPolicyManage-ment.InProceedingsofDARPAInformationSurvuvabilityConferenceandExposition,pages41–53.DARPA,January2000.

AppendixA-UnrestrictedPolicyReconcilia-tion(UPR)

ThefollowingconstructionreducesPositive,ONE-IN-THREE3SATtoUPRinpolynomialtime.Webeginwithdefinitionsthesealgorithms.

Definition1(UnrestrictedPolicyReconciliation(UPR))Given:Asessionpolicy.

Question:Whatisaninstancesatisfyingallconfigurationandpickstatementsin?

Definition2(Positive,ONE-IN-THREE3SAT(13SAT+))

Given:Setvariables,expressiondisjunctionsoversuchthateachhas,nonegatedliterals.Question:Isthereatruthassignmentforsuchthateachclauseinhasexactlyonetrueliteral?

Construction:Assume

.Foreach

.Forexample,,createthepickstatement

wouldgeneratetheexpression

thefollowingpolicy:

Nowassumeapolynomial-timealgorithmforUPRex-ists.AnyinstanceresultingfromUPRmustspecifyex-actlyoneconfigurationfromeachpickstatement.Trivially,suchaninstancerepresentssatisfyingtruthassignmentfor.Hence,because13SAT+isNP-complete[30],soisUPR.

AppendixB-LargestSubsetReconciliation(LSR)

ThefollowingconstructionreducesMAX2SATtoLSRinpolynomialtime.WebeginwithdefinitionsforLSRandMAX2SAT.

Definition3(LargestSubsetReconciliation(LSR))

Given:Asessionpolicyandasetofdomainpoliciestobeconsideredbyreconciliation.Question:Whatisthelargestsuchthatandallpoliciesaresuccessfullyreconciled?

Definition4(MAX2SAT)

Given:Thesetvariables,conjunctionofdisjunctions

oversuchthateach

has,andapositiveinteger.

Question:Isthereatruthassignmentforthatsimultane-ouslysatisfiesatleastoftheclausesin?

Construction:Assume

.Foreach,createthreedomainpolicies:

Notethateachpolicydescribesmandatoryconfigurations

(pickstatementscontainingonlyoneconfiguration).Nega-tivevariablesareinverted.Forexample,thefollowingdo-mainpoliciesaregeneratedfortheexpressionover:

Createthesessionpolicybycreatingapickstatementforeachvariableinasfollows:

Returningtotheexampleabove(where

),

.

Notebythisconstruction,reconciliationwiththesetofalldomainpolicies()satisfiesatmost1oftheclausesassociatedwitheach.Eachdomainpolicyrepresentsthe(mutuallyexclusive)waysinwhicheachclausecanbesatisfied,andthereconciliationofwithissimplyatruthassignmentfor.

AssumeapolynomialtimealgorithmexistsforLSR.An-sweringMAX2SATsimplybecomestheprocessofrec-oncilingthepoliciesresultingfromtheconstruction.If

,thenMAX2SATreturnstrue,andfalseother-wise.Thus,becauseMAX2SATisaknownNPcompleteproblem[16],LSRisNPcomplete.

AppendixC-OfflinePolicyAnalysis(OFPA)

ThefollowingconstructionreducesVALIDITYtoOFPAinpolynomialtime.WebeginwithdefinitionsforVALIDITYandOFPA.

Definition5(OfflinePolicyAnalysis(OFPA))Given:Asessionpolicyandsetofassertions.

Question:Wouldanyreconciliationofwitharbitrarydo-mainpoliciesviolateanassertionin?

Definition6(VALIDITY)

Given:AnarbitraryBooleanexpressiondefinedoverthevariables.Forconvenience,weassumeisinDNF.Question:Isvalid?

Construction:Createbydefiningaprovisionclausecon-tainingthetagconsequence(),andfourclausesforeachvariableasfollows;

Notethatthelastsetofclausesforreferencesatagtotheclausesfor.Foreachconjunct,cre-atetheclause,wheretheconditionalsenumer-atethe(possiblynegated)variablesof,andisaarbi-traryconfiguration.Appendingadefaultclausecontain-ingasingleconfiguration(),andafailclause().Completetheconstructionbycreatingasin-gleassertion().Toillustrate,anexpression

wouldresultinthe

followingand;

arebothtrueor

neitheris,theevaluationalgorithmwillimmediatelydroptotheclausewhichdefinesasinglecondition.Inthiscase,theassertiontestwilltriviallybesatisfiedbythiseval-uation.Ifexactlyoneoftheconditionsand

thentheclausesassociatedwithareconsulted.Thispro-cessrepeatsuntileithertheclauseorthefirstclauseassociatedwithisreached.Ifthefirstclauseisreached,thentheconditionsrepresentalegaltruthassignmentfor.Moreover,itisclearthatnolegaltruthassignmentforarrivesat.

Now,considertheevaluationoftheclausesof.Be-causeisrepresentedinDNF,anytruthassignmentformustsatisfyatleastoneconjunctfortobevalid.Theevaluationofsomeclausewillarriveatconfigurationifanyconjunctissatisfiedbythetruthassignmentfor,andotherwise.Ifisvalid,thefinalclausecanneverbereached(becausealllegaltruthassignmentssatisfyatleastoneconjunctof),andtheassertioncanneverbeviolated.Hence,thenegationoftheanswerreturnedbyOFPAistheanswerforVALIDITY(OFPAreturnsfalse,whereisvalidandtrueotherwise).BecauseVALIDITYisaknowntobeincoNP-complete,soisOFPA.