Gruteserspaceos

ProtectingLocationPrivacythroughSemantics-awareObfuscationTechniquesMariaLuisaDamiani,ElisaBertino,ClaudioSilvestriAbstractThewidespreadadoptionoflocation-basedservices(LBS)raisesincreas-ingconcernsfortheprotectionofpersonallocationinformation.
Toprotectloca-tionprivacytheusualstrategyistoobfuscatetheactualpositionoftheuserwithacoarselocationandthenforwardtheobfuscatedlocationtotheLBSprovider.
Ex-istingtechniquesforlocationobfuscationareonlybasedongeometricmethods.
Westatethatsuchtechniquesdonotprotectagainstprivacyattacksrootedintheknowl-edgeofthespatialcontext.
Wethuspresentanovelframeworkforthesafeguardofsensitivelocationscomprehensiveofaprivacymodelandanalgorithmforthecomputationofobfuscatedlocations1IntroductionLocation-basedservices(LBS)andinparticularGPS-enabledlocationservicesaregainingincreasingpopularity.
Marketstudies[7]forecastthatthenumberofGPS-enabledmobiledevices,includingpersonalnavigationdevices,cellularhandsets,mobilePCs,andavarietyofportableconsumerelectronicsdevices,willgrowfrom180millionunitsin2006to720millionunitsin2011.
Mobileusersequippedwithlocation-awaredevicestypicallyrequestaLBSser-vicebyforwardingtotheserviceprovideraqueryalongwiththeuser'sposition.
Theserviceproviderthenanswersthequerybasedontheposition.
Unfortunately,thecommunicationoftheuser'spositiontotheserviceproviderraisesstrongpri-MariaLuisaDamianiDICO,UniversityofMilan,ViaComelico39,20135Milan(I),e-mail:damiani@dico.
unimi.
itElisaBertinoPurdueUniversity,WestLafayette(US)e-mail:bertino@cs.
purdue.
eduClaudioSilvestriDICO,UniversityofMilan,ViaComelico39,20135Milan(I),e-mail:silvestri@dico.
unimi.
itPleaseusethefollowingformatwhencitingthischapter:Damiani,M.
L.
,Bertino,E.
andSilvestri,C.
,2008,inIFIPInternationalFederationforInformationProcessing,Volume263;TrustManagementII;YücelKarabulut,JohnMitchell,PeterHerrmann,ChristianDamsgaardJensen;(Boston:Springer),pp.
231–245.
vacyconcernsbecauseitmayresultintheunauthorizeddisseminationofpersonallocationdata.
Suchdatamayinturnleadtotheinferenceofsensitiveinformationaboutindividuals.
Forexamplethehealthstatusofaserviceusercanbeinferredfromthenatureoftheclinicsbeingvisited.
Personallocationdatareferstotheassociation(u,p)betweenuseridentieruandpositioninformationp.
Protectinglocationprivacymeansthuspreventinguandpfrombeingbothdisclosedwithouttheconsentoftheuser[2].
Awell-knownapproachtotheprotectionoflocationprivacyistodeliberatelydegradethequalityoflocationinformationandforwardtotheLBSprovideranimpreciseposition.
Imprecisionmayhowevercompromisethequalityofservicebecausetheanswertothequerymayresulttoocoarse.
Therefore,theimprecisepositionmustbedenedataresolutionwhichisacceptablefortheuser.
Werefertoanimpreciseuser'spositionasobfuscatedlocation.
Ingeneral,obfuscatedlocationsarecomputedusingtechniques,suchas(loca-tion)k-anonymity[6,10,8],basedongeometricmethods.
Werefertothesetech-niquesasgeometry-based.
Weclaimthatgeometry-basedobfuscationtechniquesdonotprotectagainstthefollowingsimpleprivacyattack.
LocationprivacyattackAssumethatJohnissuesaLBSrequestfrompositionpinsidehospitalMaggioreinFigure1(a).
Johnhoweverdoesnotwanttodisclosethefactofbeinginsidethehospitalbecausethatmightrevealhehashealthproblems.
Nowassumethatlocationpisobfuscatedbyregionqusingsomegeometry-basedtechnique(Figure1(b)).
WecanobservethatifanadversaryknowsthatJohnisintheobfuscatedlocationqandqisentirelycontainedinthespatialextentofthehospital(thelocationofthehospitalispubliclyknown),thensuchadversarycanimmediatelyinferthatJohnisinthehospital.
Asaresult,sensitiveinformationisdisclosedagainsttheuserconsent.
NotehoweverthatifJohnwouldbeadoctor,suchaprivacyconcernwouldnotarisebecausethelocationwouldberelatedtotheuser'sprofessionalactivity.
Werefertothisprivacyattackasspatialknowledgeattack.
Thespatialknowledgeattackarisesbecausegeometry-basedobfuscationtech-niquesdonotconsidertheactualsemanticsofspace,namelythespatialentitiespopulatingthereferencespaceandtheirspatialrelationships,inothertermsthespatialknowledge.
Thereforethosetechniqueareunabletoprotectagainsttheinfer-encesmadebylinkingthegeometricinformationwiththelocationmeaningwhich,dependingontheperceptionsofuser,mayrepresentsensitiveinformation.
Thepro-tectionoflocationprivacythuscallsfortechniquesabletotakeintoaccountthequalitativecontextinwhichusersarelocatedaswellastheirprivacypreferences.
Toaddressthoserequirements,weproposeanovellocationobfuscationframe-work,thatwerefertoassemantic-awareobfuscationsystem.
Themaincontribution232M.
L.
Damianietal.
Fig.
1Exampleofobfuscatedlocationofthispaperisthedenitionofthecorecomponentsoftheobfuscationsystem,thatis:aprivacymodelsupportingtheobfuscationofsensitivelocationsbasedonuserpreferences;analgorithm,calledSensFlow(i.
e.
SensitivityFlow),implementingtheobfus-cationstrategy.
Theremainderofthepaperisstructuredasfollows.
Nextsectionoverviewsre-latedwork.
Thenwepresenttheoutlineoftheapproachandtheprivacymodel.
TheSensFlowalgorithmandtwoalternativeapproachestospacesubdivisionarediscussedinthesubsequentsection.
Thenalsectionreportingopenissuesandre-searchdirectionsconcludesthepaper.
2RelatedworkRecentworkonprivacymodelsinLBScomprisestwosetsofapproaches,focusedrespectivelyontheprotectionoflocationinformationandontheconceptofk-anonymity.
PrivacymodelsfortheprotectionoflocationinformationTheproblemistohowtoprocessthequerywithoutknowingtheexactlocationoftheuser.
Atallahatal.
[1]haveproposedthreemethodsofvaryingcomplexitytoprocessnearest-neighborqueriessuchasWhereisthenearesthospitalThesim-plestmethodisasfollows:theclientappliesageometrictranslationtotheuser'spositionandforwardstheapproximatedpositiontotheLBSprovider.
ThedatabaseProtectingLocationPrivacythroughSemantics-awareObfuscationTechniques233answersthequeryandreturnsanimpreciseanswer.
Thesecondmethoddoesnotre-sultinanyaccuracylossbutcanpotentiallyrequiremorecommunication.
Theideaistosubdividespaceinagridofcells.
Theclientqueriesthedatabasewiththetilethatcontainstheclient'slocation.
Thedatabaseanswersthequerywithallspatialobjectsthatareclosesttoatleastonepointinthequerytile.
Uponreceivingtheseobjectstheclientdetermineswhichofthemisclosesttotheactualposition.
Thethirdapproachismoreefcientanddoesnotrequireanyobfuscationoftheuser'sposition.
Theideaistodeterminewhethertheuser'spositioniscontainedinacellofaspacesubdivisiondenedasVoronoidiagramwithoutrevealingtothedatabaseanythingotherthantheYes/Noanswertothequestion.
IftheanswerisYesthentheobjectassociatedwiththecellistheoneclosesttotheuser.
Thismechanism,whichusesasecuremulti-partprotocol[4],canbeonlyappliedwheneverspaceispartitioned.
Anotherapproachforprocessingnearest-neighborqueriesisproposedbyDuck-hamandKulik[5].
InsuchapproachtheclientobfuscatespositionpbysupplyingasetPofarbitrarypositionsincludingp.
Thedatabasethenanswersthenearest-neighborquerybydeterminingtheobjectsthatareclosesttoanypointinP.
Then,inthesimplestcase,thedatabasereturnsthewholesetofobjectsleavingtheclienttochooseamongthem.
Protectionofuseridentitythroughk-anonymityAsignicantnumberofproposalsarebasedonk-anonymity.
Theconceptofk-anonymityhasbeenoriginallydenedforrelationaldatabases.
ArelationaltableTisk-anonymouswhenforeachrecordthereareatleast(k-1)otherrecordswhosevalues,overasetofelds,referredtoasquasi-identier,areequal.
Aquasi-identierconsistsofoneormoreattributeswhich,thoughnotcontaininganexplicitreferencetotheindividualsidentity,canbeeasilylinkedwithexternaldatasourcesandinthiswayrevealswhotheindividualis.
K-anonymitycanbeachievedbygen-eralization,thatisreplacingaquasi-identierattributevaluewithalessspecicbutsemanticallyconsistentvalue[13].
Theconceptsofk-anonymityaretransposedintheLBScontextasfollows.
Thelocationattributeistreatedasaquasi-identier.
Hence,arequestislocationk-anonymousiftheuser'slocationisundistinguishableformthelocationofotherk-1individuals.
Finallyageneralizedlocationisaregioncontainingthepositionofkindividuals.
Locationgeneralizationtechniquesgener-ateobfuscatedlocationsindependentofthequerytype.
ThersttechniquehasbeenproposedbyGruteser.
Theideabehindthisschemeistorecursivelysubdividespaceinquadrantsofaquadtree[6].
Thequadtreeisthentraversedtopdown,thusfromthelargestquadrantcoveringthewholespace,untilthesmallestquadrantisfoundwhichincludestherequesterandotherk1users.
Suchanalquadrantconstitutesthegeneralizedlocation.
AnothertechniquebasedonquadtreeshasbeenproposedinthecontextoftheCaspersystem[10].
Ahashtableallowsonetodirectlylocatetheuser.
Suchtablecontainsthepointertothelowest-levelcellinthequadtree-baseddatastructurein234M.
L.
Damianietal.
whicheachuserislocatedandhisprivacyprole.
Aprivacyproleisdenedbythepair(k,AMin)wherekmeansthattheuserwishestobek-anonymous,andAMinistheminimumacceptableresolutionofthegeneralizedlocation.
Thelocationgener-alizationalgorithmworksbottom-up:ifacellorcombinationoftwoadjacentcellsdoesnotsatisfyprivacypreferences,thenthealgorithmisrecursivelyexecutedwiththeparentcelluntilavalidcellisreturned.
Kelnisetal.
in[8]observethatlocationk-anonymityalgorithmsmaycompromiselocationprivacyifanattackerknowsthegeneralizationalgorithm,thevalueofkandthepositionofallusers.
Specically,thishappenswhenageneralizedlocationcanunivocallyassociatedwithauser.
Toaddressthisproblem,Kelnisetal.
presentanewalgorithmbasedontheuseofalinearorderingoflocations.
Recentworkonrelationaldataprivacyhaspointedoutthatk-anonymitydoesnotensureasufcientprotectionagainstanumberofprivacyattacks.
Forexamplek-anonymitycangenerategroupsofrecordsthatleakinformationduetothelackofdiversityinthesensitiveattribute.
Suchaninformationleakiscalledhomogeneityattack.
Againstthisattack,apossiblecounter-measureisl-diversity.
Themainideabehindl-diversityistherequirementthatthevaluesofthesensitiveattributesmustbewellrepresentedineachgroup[9].
Initssimplerform,l-diversitymeansthateachgroupshouldhaveatleastldistinctvalues.
Anothercriticismagainstk-anonymityisthatitdoesnottakeintoaccountper-sonalanonymityrequirementsontheacceptablevaluesofsensitiveattributes.
Toaddressthisrequirement,XianandTao[14]introducestheconceptofpersonalizedanonymity.
Themainideaistoorganizethevaluesofthesensitiveattributeinataxonomyandthenleteachuserspecifythroughaguardingnodethemostspecicvalueoftheattributethattheuserwantstodisclose.
Interestingly,thisapproachattemptstoprotecttheassociationbetweenauserandthemeaningofthesensi-tiveattribute,whichisclosetowhatwepropose.
TheapproachofXianandTao,however,onlyworksforcategoricalattributes.
3OutlineoftheapproachThebasicideaistocollectusers'preferencesaboutsensitiveplacesandthedesireddegreeoflocationprivacyinprivacyprolesandthencarryouttheprocessofloca-tionobfuscationintwosteps.
Suchaprocessisdescribedbelow.
Consideraprivacyprolev.
(1)Therststepistoobfuscatethesensitiveplacesspeciedinvbasedontheuser'sdesireddegreeofprivacy.
Thisoperation,thatwecallobfuscatedspacegenera-tion,resultsinthegenerationofasetofcoarselocationshidingtheactualextentofsensitiveplacesincompliancewithuserpreferences.
WecanabstractlythinkofobfuscatedspacegenerationasthefunctionObf:Obf(v)=sProtectingLocationPrivacythroughSemantics-awareObfuscationTechniques235whichmapsprolevontothesetsofregionsenclosingsensitiveplaces.
(2)Thesecondstepiscarriedoutuponauser'sLBSrequest.
Considerauserwithprivacyprolevinpositionp.
Theoperationthatwecallobfuscationenforce-mentcanbeabstractlyrepresentedbythefunctionOe:Oe(p,v)=qmappingpositionpandprolevontoalocationqwhereq∈Obf(v)ifpiscontainedinqandq=potherwise.
Asaresult,whenthelocationisobfuscated,anadversarycannotinferwithcertaintythattheuserisinsideasensitive(fortheuser)place.
Atmostonecaninferthatthepositionmaybeinasensitiveplace.
AnaiveimplementationofthefunctionObfistodene,foreachsensitiveplace,aregioncontainingtheplaceofinterest.
Thissolutionhashoweverimportantdraw-back:rstifthesensitiveplacehasalargeextent,theobfuscatedlocationmayresulttoobroadandthuscompromisethequalityofservice.
Bycontrast,iftheobfuscatedlocationisnotlargeenoughtheprobabilityofbeinglocatedinsideasensitiveplacemaybeveryhighandthusobfuscationisineffective.
Toovercomethesedrawbackswesubdividesensitiveregionsincells.
Eachcellhasasensitivitywhichdependsontheuserpreferencesintheprivacyprole.
Eachcellisthusobfuscatedsepa-ratelythroughanobfuscationalgorithm.
Torepresentuserpreferences,wedeneaprivacymodel,calledobfuscationmodel,centeredonthefollowingconcepts.
Propertiesofplaces.
Placesasclassiedintotypes.
Usersspecifyintheirprivacyproleswhichtypesofplacesaresensitive,non-sensitiveorunreachable.
Aplaceissensitivewhentheuserdoesnotwanttorevealtobeinit;aplaceisunreachablewhentheusercannotbelocatedinit;aplaceisnon-sensitiveotherwise.
Thelevelofsensitivityquantiesthedegreeofsensitivityofaregionforauser.
Forexamplearegionentirelyoccupiedbyahospitalhasahighlevelofsensitiv-ity,ifhospitalissensitivefortheuser.
Weemphasizethatthelevelofsensitivitydependsontheextentandnatureoftheobjectslocatedintheregionaswellastheprivacyconcernsoftheuser.
Anobfuscatedspaceisasetofobfuscatedlocationsassociatedwithaprivacyprole.
Specically,thelocationsofanobfuscatedspacehavealevelofsensi-tivitylessorequalthanasensitivitythresholdvalue.
Thesensitivitythresholdvalueisthemaximumacceptablesensitivityofalocationfortheuser.
Sincethethresholdvalueisuser-dependent,itsvalueisspeciedintheprivacyprole.
4TheobfuscationmodelWerstintroducethebasicnomenclatureusedintherestofthepaper.
Apositionisapointinatwo-dimensionalspaceS;regionisapolygon;locationbroadlydenotesaportionofspacecontainingtheuser'sposition.
Placesarerepresentedassimplefeatures.
Afeaturehasanuniquename,sayMilano,andauniquefeaturetype,sayCity.
Furthermore,afeaturehasaspatialextentofgeometrictype[12]that,without236M.
L.
Damianietal.
signicantlossofgenerality,consistsofaregion.
Featuresextentsarespatiallydis-joint.
Considerthecaseoftwooverlappingplaces,forexamplearestaurantwithinapark:theextentoftheparkfeaturemustbedenedinsuchawaythatitdoesnotcontaintheextentoftherestaurantfeature.
AnadvantageofourapproachisthatspatialfeaturescanbestoredincommercialspatialDBMSsandeasilydisplayedasmaps.
WedenotewithFTandFrespectivelythesetoffeaturestypesandthesetofcorrespondingfeatures.
Hereinafterwerefertothepair(FT,F)asthegeographicaldatabaseoftheapplication.
SensitiveandunreachablefeaturetypesInaprivacyproleauserspeciesthefeaturetypeswhichareconsideredsensitiveandunreachable.
Afeaturetypeissensitivewhenitdenotesasetofsensitiveplaces.
ForexampleifReligiousBuildingisasensitivefeaturetype,thenDuomodiMilano,aninstanceofReligiousBuilding,isasensitivefeature.
Insteadafeaturestypeisnon-reachablewhenitdenotesasetofplaceswhichforvariousreasons,suchasphysicalimpediment,cannotbeaccessedbytheuser.
Forexample,thefeaturetypeMilitaryZonemaybenon-reachableiftheuserisacommoncitizen.
Afeaturetypewhichisneithersensitiveorunreachableisnon-sensitive.
Inprinciple,ausercandenemultipleprivacyproles.
QuantifyingthelevelofsensitivityofaregionWeintroducersttheconceptofsensitivityscore(simplyscore).
Thescoreofafeaturetypeftisavaluewhichisassignedtofttospecify"howmuchsensitive"ftisfortheuser.
Forexamplethescoreoftherestaurantfeaturetypeistypicallylowerthanthescoreofhospitalbecauseanindividualisusuallymoreconcernedwithprivacyofmedicalinformationthanwithinformationabouthis/herpreferredrestaurants.
Formally,thescoreoffeaturetypeftisdenedbythefunctionScore(ft)rangingbetween0and1:value0meansthatthefeaturetypeisnotsensitiveorunreachablewhileavalue1meansthatthefeaturetypehasthehighestsensitivity.
Theconceptofscorecapturesthesubjectiveperceptionofthedegreeofsensitivity.
Thescoreofeachsensitivefeaturetypeisthusspecieddirectlyintheprivacyprole.
Thescorefunctionisusedforcomputingthesensitivitylevelofaregion.
Thesensitivitylevel(SL)ofaregionr,writtenasSLReg(r),quantieshowmuchsensitiverisfortheuser.
Inparticular,SLisdenedassumoftheratiosofweightedsensitiveareatotherelevantareaintheregion.
Theweightedsensitiveareaisthesurfaceinroccupiedbysensitivefeaturesweightedwithrespecttothesensitiv-ityscoreofeachfeaturetype.
Therelevantareaofristheportionofregionnotoccupiedbyunreachablefeatures.
ToformallydeneSL,weintroducethefollowingnotation:EisthesetofregionsinthereferencespaceProtectingLocationPrivacythroughSemantics-awareObfuscationTechniques237(FT,F)isthegeographicaldatabase,namelythesetoffeaturestypesandfea-turesFTSensFTisthesetofsensitivefeaturetypesandFTNreachFTisthesetofnon-reachablefeatures,withFTNreachFTSens=/0Thefunctions:AreaGeo(r)andAreaFea(r,ft)compute,respectively,thewholeareaofrandtheareaofrcoveredbyfeaturesoftypeft.
Inthelattercase,onlytheportionsoffeatureswhicharecontainedinrareconsidered.
Denition1(Sensitivitylevelofaregion).
Thesensitivitylevelofaregionisde-nedbythefunction:SLReg:E→[0,1]suchthat,givenaregionr:SLReg(r)=ft∈FTSensScore(ft)AreaFea(r,ft)AreaRel(r)whereAreaRel(r)=AreaGeo(r)ft∈FTNreachAreaFea(r,ft).
Ifronlycontainsnon-reachablefeatures,wedeneSLreg(r)=0.
Example1.
Consideraspaceconsistingoffourregionsc0,c1,c2,c3;thesetofsen-sitivefeaturetypesisFTsens={ft0,ft1,ft3}andthesetofnon-reachablefeaturetypesisFTNreach={ft2}.
Table1reports,foreachfeaturetypeftiandregioncj,theareaoccupiedbyftiincj,withi,jrangingover{0,1,2,3}.
Inaddition,therowNSreportsthenon-sensitiveareaineachregion.
Forexample,regionc2includessensitivefeatures(orportion)oftypeft0andoftypeft3bothcoveringanareaof100units;non-reachablefeatures(orportion)oftypeft2coveringanareaof1000units;andanon-sensitiveareaof100units.
TherowTotrelevantreportstherelevantareaineachregion,thatistheareanotcoveredbyunreachablefeatures.
Forexam-pletherelevantareainregionc2hasanextentof300units.
Thelastcolumnontherightreportsthesensitivityscoreassignedtoeachfeaturetype.
Area(c,ft)c0c1c2c3Score(ft)ft0200010000.
5ft1100001000.
7ft23005010004000ft301001001000.
9NS001000-Totrelevant300100300200-SLreg0.
570.
90.
470.
8-Table1AreaandsensitivityscoresoffeaturetypesThesensitivitylevelforregionsc0andc1is:-SLreg(c0)=0.
5·200300+0.
7·100300=0.
57-SLreg(c1)=0.
9·100100=0.
9.
Itresultsthatregionc1ismoresensitivethanc0.
Themotivationisthatuserslocatedinregionc1arecertainlylocatedintheextentofafeatureoftypeft3,whichhasahighsensitivityscore.
238M.
L.
Damianietal.
ObfuscatedspaceFinallyweintroducetheconceptofobfuscatedspace.
Anobfuscatedspaceisaspacepartitionconsistingofregionswhichareprivacy-preserving.
Wesaythataregionrisprivacy-preservingwhenthelevelofsensitivityofr,SLReg(r)isequalorbelowathresholdvalue.
Thethresholdvalueisthemaximumacceptablesensitivityoflocationsfortheuser.
Itsvaluerangesintheinterval(0,1].
Avalueequalto1meansthattheuserdoesnotcareoflocationprivacyinanypointofspace.
Weruleoutthevalue0becauseitwouldbesatisedonlyiftherewerenosensitivelocations(againsttheinitialassumption).
Thethresholdvalueisanotherparameterspeciedintheprivacyprole.
Weformallydenethenotionofobfuscatedspaceandofprivacyproleinthedenitionbelow.
Denition2(Obfuscatedspace).
Let(FT,F)bethegeographicaldatabase.
More-overlet:-FTSensFTbeasetofsensitivefeaturetypes.
-FTNreachFTbeasetofnon-reachablefeaturetypes.
-Scorebethescorefunction.
-qsens∈(0,1)bethesensitivitythresholdvalue.
Then:(1)AnobfuscatedspaceOSisaspacepartitionsuchthat:maxc∈OSSLReg(c)≤qsens(2)TheprivacyproleassociatedwithOSisthetupleExample2.
Withreferencetoexample1,considertheprole:-FTSens={ft0,ft1,ft3}whereft0representsnightclubs,ft1religiousbuildingsandft3clinics.
-FTNreach={ft2}whereft2representsamilitaryzone-Score(ft0)=0.
5,Score(ft1)=0.
7,Score(ft2)=0,Score(ft3)=0.
9-qsens=0.
90123thanqsens.
Thus,thesetofregionsisanobfuscatedspace.
5ComputingtheobfuscatedspacesAfterpresentingtheprivacymodel,thenextstepistodenehowtocomputeanobfuscatedspace.
Ourstrategyconsistsoftwomainsteps:ProtectingLocationPrivacythroughSemantics-awareObfuscationTechniques239(reportedinTable1).
Itcanbenoticedthatsuchvalue,inallcases,islessorequal{c,c,c,c}andthesensitivitylevelofeachofthemConsiderthefourregions1.
Specicationoftheinitialpartition.
Thereferencespaceissubdividedinasetofsmallregions,referredtoascells,whichconstitutetheinitialpartitiondenotedasCin.
Thegranularityoftheinitialpartition,thatis,howsmallthecellsare,isapplication-dependent.
2.
Iterationmethod.
Thecurrentpartitionischeckedtoverifywhetherthesetofcellsisanobfuscatedspace.
Ifnot,itmeansthatatleastonecellisnotprivacypreserving.
Acellcisthusselectedamongthosecellswhicharenotprivacy-preservingandmergedwithanadjacentcelltoobtainacoarsercell.
Theresultisanewpartition.
Thisstepisiterateduntilthesolutionisfound,andthusallprivacypreferencesaresatisedorthepartitiondegeneratesintothewholespace.
Inthefollowingwedescribethesetwosteps,startingfromthelatter.
5.
1TheiterationmethodConsiderapartitionCofthereferencespace.
Giventwoadjacentcellsc1,c2∈C,themergeofthetwocellsgeneratesanewpartitionC′inwhichcellsc1andc2arereplacedbycellc=c1∪Sc2with∪Sdenotingtheoperationofspatialunion.
WesaythatpartitionC′isderivedfrompartitionC,writtenasC′C.
ConsiderthesetPCinofpartitionsderiveddirectlyorindirectlyfromtheinitialpartitionCinthroughsubsequentmergeoperations.
TheposetH=(PCin,)isaboundedlatticeinwhichtheleastelementistheinitialpartitionwhilethegreatestelementisthepartitionconsistingofauniqueelement,thatis,thewholespace(calledmaximalpartition).
Itcanbeshownthatanobfuscatedspace,ifitexists,canbegeneratedbypro-gressivelyaggregatingcellsincoarserlocationsandthusbyderivingsubsequentpartitions.
Thedemonstration,thatweomit,isarticulatedintwosteps.
FirstitisshownthattheSL(i.
e.
sensitivitylevel)ofthecellresultingfromamergeoperationislessorequalthesensitivitylevelofthestartingcells.
Thenitisshownthatthesensitivitylevelofthepartition(i.
e.
themaximumsensitivityvalueofcells)result-ingfromsubsequentmergeoperationsislessorequalthanthesensitivitylevelofthestartingpartition.
ThealgorithmThealgorithmcomputestheobfuscatedspacebyprogressivelymergingadjacentcells.
Ingeneral,forthesameprivacyprole,multipleobfuscatedspacescanbegenerated.
Weconsideroptimaltheobfuscatedspacewiththemaximumcardinality,thuspossiblyconsistingofthenest-grainedregions.
Theproblemofndingtheoptimalobfuscatedspacecanbeformulatedasfollows:GivenaninitialpartitionCin,determine,ifitexists,thesequenceofmergeoper-ationssuchthattheresultingpartitionCistheobfuscatedspacewiththemaximumnumberofcells240M.
L.
Damianietal.
Inthispaper,wepresentanalgorithmwhichcomputesanapproximatedsolutiontotheproblem.
Theideaistoprogressivelyexpandeachcellwhichisnotprivacypreservinguntilaterminatingconditionismet.
Thisapproachraisesanumberofis-sues.
Therstissueishowtochoosethecellstobemerged.
Weadoptthefollowingheuristic:weselecttheadjacentcellwhichdeterminesthemostsensiblereductionofsensitivityoftheaggregatedcell.
Asecondissueconcernsthecriteriafortheex-pansionofcells.
Toaddresssuchissues,wehaveidentiedtwobasicstrategies:therststrategyistoexpandoneover-sensitivecell(i.
e.
anon-privacy-preservingcell)atatime,untilthelevelofsensitivityisbelowthethreshold;thesecondstrategyistoexpand"inparallel"allcellswhichareover-sensitive.
Thesecondstrategyistheonewhichhasbeenadoptedbecauseitallowsonetobettercontrolthesizeoftheaggregatedcells.
InsightsontheSensFlowalgorithmWerepresentaspacepartitionthroughaRegionAdjacencyGraph(RAG)[11].
IngeneralaRAGisdenedfromapartitionbyassociatingonevertexwitheachcellandbycreatinganedgebetweentwoverticesiftheassociatedcellsshareacommonboundary.
Withinthisframework,theedgeinformationisinterpretedaspossibilityofmergingthetwocellsidentiedbytheverticesincidenttotheedge.
Suchamergeoperationimpliestocollapsethetwoverticesincidenttotheedgeintoonevertexandtoremovethisedgetogetherwithanydoubleedgebetweenthenewlycreatedvertexandtheremainingvertices[3].
Theinputparametersofthealgorithmare:1)theinitialRAGbuiltontheini-tialpartition;2)theprivacyprole.
Thealgorithmreturnsanobfuscatedspaceifitexists,anerrorotherwise.
StartingfromtheRAGcorrespondingtotheinitialpar-tition,thealgorithmshrinksthegraphbymergingadjacentcellsuntilallprivacyconstraintsaresatisedorasolutioncannotbefound.
Ateachiteration,thealgo-rithmlooksfornon-privacypreservingcells;theneachofsuchcellsismergedwithatmostoneadjacentcell.
Amongthecellsintheneighborhood,mergingisexe-cutedwiththecellwhichdeterminesthemostsignicantreductioninthesensitivityoftheresultingaggregatedregion.
Afterthemerge,thealgorithmproceedstoscantheremainingcells,andthewholeloopisrepeateduntilnocellismodied.
Thecomplexityofthealgorithm,evaluatedwithrespecttothetwokeyoperations,thatis(a)mergeoperations,(b)numberofedgesanalyzed,isO(n2).
5.
2ThespecicationoftheinitialpartitionTheabovealgorithmisappliedtoaninitialspacepartitionwhichisthenmappedontoagraph.
Nowakeydesignissueistodenehowtobuildtheinitialparti-tionandhowtospecifysensitiveandunreachablecellsinsuchapartition.
Inotherwords,givenamapofspace,whatkindofpartitioncanbegeneratedAndhowProtectingLocationPrivacythroughSemantics-awareObfuscationTechniques241canthesensitivityleveloftheinitialpartitionbecomputedWehaveinvestigatedtwoapproaches:a)Tosubdividespaceintoaregulargridofcells.
Cellshavethusequalshapesandsizes.
b)Tosubdividespaceintoasetofirregulartilesbasedonanaturalsubdivisionofterritory.
Eachtilerepresentsarealworldentity,forexampleacensusblock.
Fig.
2SensitivecellsintheinitialpartitionWenowdiscusstheexperimentscarriedoutusingthesetwoapproaches.
TheadoptedsoftwareplatformconsistsofaJavaimplementationoftheSensFlowal-gorithm,thesystemIntergraphGeomediaforthevisualizationofspatialdataandOracleSpatialfortheconstructionoftheRAG.
Wepresentrsttheexperimentwiththeirregulartessellationofspace.
Seeminglytheadvantageoftheirregulartessellationagainstgridisthattilesmayrepresentphysicalentities.
Therefore,sincesensitiveplaces,suchclinicsorreligiousplaces,havewell-knownboundaries,theylikelycorrespondtotilesandthuscanbemoreeasilyidentied.
Creatingaspacetessellationatveryhighresolutionis,however,extremelycostly.
Amorepracticalsolutionistousepubliclyavailabledatasets,albeitatlowerresolution.
AtypicaldatasetrepresentingaspacepartitionistheUSCensusdata.
WehavethusrunthealgorithmonaninitialpartitionobtainedfromUSCensusBlockdataset.
Thedatasetconsistsof15000polygonsrepresentingCensusBlockGroups,thatis,aggregationofcensusblocks.
Eachpolygonisacellofthepartition.
Weassume:Auniquefeaturetypeftwithscore=1thusatthehighestsensitivity.
Thedensitysofsensitivecellsisaparameteroftheexperiment.
Forexamples=0.
05meansthat5%ofcellscontainsensitivefeatures.
Thepercentageofareawhichissensitiveinacellisassignedrandomly.
Figure2showsaportionoftheinitialpartitionwiths=0.
05:theblackcellsaresensitive,whereasthewhitecellsarenon-sensitive.
242M.
L.
Damianietal.
(a)qsens=0.
3(b)qsens=0.
1Fig.
3VisualrepresentationoftwoobfuscatedspacesrelativetoareainFigure2(s=0.
05)TheSensFlowalgorithmhasbeenrunusingdifferentvaluesofthesensitivitythreshold.
TheexperimentalresultsareshowninthemapsinFigure3.
Thegener-alizedregionsarerepresentedbypolygonsofdifferentcolor,basedonthenumberofaggregations:thecolorisdarkerforthemoreaggregatedregions;whitespacedenotestheoriginalspace.
Wecanobservethatthegranularityoftheobfuscatedspaceiscoarserforlowervaluesofthesensitivitythreshold.
Themainlimitationofthisapproachisthatthepubliclyavailabledatasetisnotsufcientlyprecise.
Cellsaregenerallytoobroad,especiallyinruralareasandthatcompromisesthequalityofservice.
Wehavethusevaluatedthegrid-basedapproachtospacesubdivision.
Spaceissubdividedintoagridofregularcells.
Featuresdonothaveanyphysicalcorrespon-dencewithcells.
Featuresarethuscontainedinacelloroverlapmultiplecells.
Thesensitiveareainthecellresultsfromthespatialintersectionofthefeatureextentwiththecell.
Wehaverunthealgorithmoveragridof100squaredcells,assumingagainauniquefeaturetypewithmaximumscore.
qsens=0.
5qsens=0.
4qsens=0.
3Fig.
4Visualrepresentationofthecellaggregationfordifferentvaluesofthesensitivitythresholdqsens.
MergedcellsareindicatedusingboththesamenumberandthesamecolorFigure4showstheobfuscatedspacesgeneratedfordifferentvaluesofthesen-sitivitythreshold.
Theresultisvisualizedasfollows:adjacentcellswhichhavenotbeenmergedareassigneddifferentgraytones;mergedcellshaveanidenticalgrayProtectingLocationPrivacythroughSemantics-awareObfuscationTechniques243toneandarelabeledbythesamenumber.
Wecanobservehowthegranularityofobfuscatedlocations(i.
e.
asetofcellswithidenticallabel)changesfordifferentvaluesofqsens.
Fromtheexperimentsitturnsoutthatthegrid-basedapproachismoreexiblebecausethegranularityofpartitioncanbedenedbasedonapplica-tionneeds.
Ontheotherhand,thewholeprocessofdiscretizationoffeaturesincellsismuchmorecomplex.
6OpenissuesandconclusionsInthispaperwehavepresentedacomprehensiveframeworkfortheprotectionofprivacyofsensitivelocations.
Becauseofthenoveltyoftheapproachanumberofimportantissuesarestillopen,pertainingvariousaspectsconcerning:theprivacymodel,thecomputationalcomplexityandthesystemarchitecturerespectively.
Asconcernstheprivacymodel,onecouldobservethatthesensitivityofaplacemayvarydependingonthecontext,suchastime.
Indeedinourapproachtheuserisallowedtospecifymultipleprolesandthus,ideally,onecouldselecttheprivacyprolebasedonthecontextualconditions.
Unfortunatelythissolutionmayresultintoanexcessiveburdenfortheuser.
Somemechanismforacontext-drivenselec-tionofprivacyproleswouldthusbedesirable.
Anotherobservationisthatourprivacymodelrequiresdetailedknowledgeoftheextentsofsensitiveplaces,whilesuchaknowledgeisdifcultandcostlytoacquire.
WebelievethatinthenextfewyearshighqualityspatialdatawillbecomeincreasinglyavailableunderthepushofthegrowingLBSmarketandthusthedevelopmentofobfuscationservicesbyLBSprovidersorthirdpartieswillbecomeaffordable.
Ourprivacymodelcanbeimprovedinseveralways.
First,weobservethatthenotionofthresholdvaluemaybenotsointuitivefortheuser.
Asaconsequence,thespecicationoftheprivacyprolemaybecomplex.
Second,inourmodelweassumethatmobileusershaveequalprobabilityofbeinglocatedinanypointoutsideanunreachablearea,whilethatcontrastswiththeevidencethatsomeareasaremorefrequentedthanothersandthusanindividualismorelikelyinthoseplacesthaninothers.
Theinvestigationofaprobabilisticmodelisamajoreffortofthefutureactivity.
Adistinctclassofissuesareaboutthecomputationalcostofobfuscatedmapgeneration.
Thepresentalgorithmhasaquadraticcomplexity.
Foraneffectivede-ploymentofthesystem,amoreefcientalgorithmisneeded.
Arelatedaspectisthedevelopmentofasuitableplatformfortheexperimentalevaluationofthealgorithmsincludingageneratorofinitialpartitions.
Anothermajorclassofissuesconcernsthespecicationofadistributedsystemarchitecture.
Weenvisagetwomainarchitec-turalsolutions.
ThestraightforwardapproachistouseatrustedObfuscationServerasanintermediarybetweentheclientandtheLBSprovider.
TheTOScreatestheob-fuscatedspacesandstoresthemalongwiththeassociatedprivacyproleinalocalrepository.
Atruntime,theuser'srequestisforwardedtotheObfuscationServerwhichappliestheobfuscationenforcement.
Thisschemehasamaindrawbackinthatitrequiresadedicatedandtrustedserver.
Thismayresultintoabottleneck;244M.
L.
Damianietal.
furtherthetrustworthinessoftheserveriscostlytoensure.
Toovercomethislimi-tation,analternativeapproachistobasethearchitectureonthefollowingidea.
TheObfuscatorServerisstillusedbutexclusivelytogenerateobfuscatedmapsuponuser'srequests.
Oncegenerated,themapisthentransferredbacktotherequestingclientwhichstoresitlocally.
Finally,theobfuscationenforcementisthencarriedoutontheclient.
Becauseofthestoragelimitationsofmobiledevices,thegener-atedmapshouldbenotonlygeneratedinanacceptabletimefortheuserbutalsohaveareasonablesize.
AcknowledgementsThisworkhasbeenpartiallyfundedbytheEuropeanCommissionprojectIST-6FP-014915"GeoPKDD:GeographicPrivacy-awareKnowledgeDiscoveryandDelivery(GeoPKDD)"(website:http://www.
geopkdd.
eu),andbytheUSNationalScienceFoundationgrant0712846"IPS:SecurityServicesforHealthcareApplications".
References1.
M.
AtallahandK.
Frikken.
Privacy-preservinglocation-dependentqueryprocessing.
InACS/IEEEIntl.
Conf.
onPervasiveServices(ICPS),2004.
2.
A.
R.
BeresfordandF.
Stajano.
Locationprivacyinpervasivecomputing.
IEEEPervasiveComputing,2(1):46–55,2003.
3.
L.
BrunandW.
Kropatsch.
Containsandinsiderelationshipswithincombinatorialpyramids.
PatternRecognition,39(4),2006.
4.
W.
DuandM.
J.
Atallah.
Securemulti-partycomputationproblemsandtheirapplications:areviewandopenproblems.
InNSPW'01:Proceedingsofthe2001workshoponNewsecurityparadigms,pages13–22,NewYork,NY,USA,2001.
ACM.
5.
M.
DuckhamandL.
Kulik.
Aformalmodelofobfuscationandnegotiationforlocationpri-vacy.
InPervasiveComputing,volume3468ofLectureNotesinComputerScienceLNCS,pages152–170.
SpringerBerlin/Heidelberg,2005.
6.
M.
GruteserandD.
Grunwald.
Anonymoususageoflocation-basedservicesthroughspatialandtemporalcloaking.
InMobiSys'03:Proceedingsofthe1stinternationalconferenceonMobilesystems,applicationsandservices,pages31–42,NewYork,NY,USA,2003.
ACMPress.
7.
In-Stat.
http://www.
instat.
com/press.
aspid=2140&sku=in0703846wt.
Publicationdate:5November2007.
8.
P.
Kalnis,G.
Ghinita,K.
Mouratidis,andD.
Papadias.
Preventinglocation-basedidentityinfer-enceinanonymousspatialqueries.
IEEETransactionsonKnowledgeandDataEngineering,19(12):1719–1733,2007.
9.
A.
Machanavajjhala,J.
Gehrke,D.
Kifer,andM.
Venkitasubramaniam.
l-diversity:Privacybeyondk-anonymity.
In22ndIEEEInternationalConferenceonDataEngineering,2006.
10.
M.
F.
Mokbel,C.
-Y.
Chow,andW.
G.
Aref.
Thenewcasper:queryprocessingforlocationserviceswithoutcompromisingprivacy.
InVLDB'2006:Proceedingsofthe32ndinternationalconferenceonVerylargedatabases,pages763–774.
VLDBEndowment,2006.
11.
M.
Molenaar.
AnIntroductiontotheTheoryofSpatialObjectModellingforGIS.
CRCPress,1998.
12.
OpenGISConsortium.
OpenGISsimplefeaturesspecicationforSQL,1999.
Revision1.
1.
13.
L.
Sweeney.
Achievingk-anonymityprivacyprotectionusinggeneralizationandsuppression.
Int.
J.
Uncertain.
FuzzinessKnowl.
-BasedSyst.
,10(5):571–588,2002.
14.
X.
XiaoandY.
Tao.
Personalizedprivacypreservation.
InSIGMOD'06:Proceedingsofthe2006ACMSIGMODinternationalconferenceonManagementofdata,pages229–240,NewYork,NY,USA,2006.
ACM.
ProtectingLocationPrivacythroughSemantics-awareObfuscationTechniques245