位置服务中的隐私保护PPT演示课件

M,1,ICDM2008,Privacy-PreservingLocationServices,MohamedF.MDepartmentofComputerScienceandEngineeringUniversityofMinnesota,2,Tutorial:ICDM2008,M,TutorialOutline,PARTI:PrivacyConcernsoflocation-basedServicesPARTII:RealizingLocationPrivacyinMobileEnvironmentsPARTIII:PrivacyAttackModelsPARTIV:Privacy-awareLocation-basedQueryProcessingPARTV:SummaryandFutureResearchDirections,3,Tutorial:ICDM2008,M,TutorialOutline,PARTI:PrivacyConcernsoflocation-basedServicesLocation-basedServices:Then,Now,WhatisNextLocationPrivacy:WhyNow?UserPerceptionofLocationPrivacyWhatisSpecialaboutLocationPrivacyPARTII:RealizingLocationPrivacyinMobileEnvironmentsPARTIII:PrivacyAttackModelsPARTIV:Privacy-awareLocation-basedQueryProcessingPARTV:SummaryandFutureResearchDirections,4,Tutorial:ICDM2008,M,Location-basedServices:Definition,Inanabstractway,Acertainservicethatisofferedtotheusersbasedontheirlocations,5,Tutorial:ICDM2008,M,Location-basedServices:Then,Limitedtofixedtrafficsigns,HowmanyyearswehaveusedthesesignsastheONLYsourceforLBS,6,Tutorial:ICDM2008,M,Location-basedServices:Now,Location-basedtrafficreports:Rangequery:HowmanycarsinthefreewayShortestpathquery:Whatistheestimatedtraveltimetoreachmydestination,Location-basedstorefinder:Rangequery:WhataretherestaurantswithinfivemilesofmylocationNearest-neighborquery:Whereismynearestfast(junk)foodrestaurant,Location-basedadvertisement:Rangequery:SendE-couponstoallcustomerswithinfivemilesofmystore,7,Tutorial:ICDM2008,M,Location-basedServices:WhyNow?,8,Tutorial:ICDM2008,M,Location-basedServices:WhyNow?,WebGIS,LBS,MobileInternet,MobileGIS,ConvergenceoftechnologiestocreateLBS(Brimicombe,2002),9,Tutorial:ICDM2008,M,Location-basedServices:WhatisNext,10,Tutorial:ICDM2008,M,Location-basedServices:WhatisNext,11,Tutorial:ICDM2008,M,TutorialOutline,PARTI:PrivacyConcernsoflocation-basedServicesLocation-basedServices:Then,Now,WhatisNextLocationPrivacy:WhyNow?UserPerceptionofLocationPrivacyWhatisSpecialaboutLocationPrivacyPARTII:RealizingLocationPrivacyinMobileEnvironmentsPARTIII:PrivacyAttackModelsPARTIV:Privacy-awareLocation-basedQueryProcessingPARTV:SummaryandFutureResearchDirections,12,Tutorial:ICDM2008,M,LocationPrivacy:WhyNow?,Doyouuseanyofthesedevices?,Doyoueverfeelthatyouaretracked?,13,Tutorial:ICDM2008,M,MajorPrivacyThreats,“Newtechnologiescanpinpointyourlocationatanytimeandplace.Theypromisesafetyandconveniencebutthreatenprivacyandsecurity”Coverstory,IEEESpectrum,July2003,YOUARETRACKED!,14,Tutorial:ICDM2008,M,MajorPrivacyThreats,15,Tutorial:ICDM2008,M,MajorPrivacyThreats,http:/technology.guardian.co.uk/news/story/0,1699156,00.html,16,Tutorial:ICDM2008,M,MajorPrivacyThreats,17,Tutorial:ICDM2008,M,TutorialOutline,PARTI:PrivacyConcernsoflocation-basedServicesLocation-basedServices:Then,Now,WhatisNextLocationPrivacy:WhyNow?UserPerceptionofLocationPrivacyWhatisSpecialaboutLocationPrivacyPARTII:RealizingLocationPrivacyinMobileEnvironmentsPARTIII:PrivacyAttackModelsPARTIV:Privacy-awareLocation-basedQueryProcessingPARTV:SummaryandFutureResearchDirections,18,Tutorial:ICDM2008,M,UserPerceptionofLocationPrivacyOneWorldTwoViews,Anadvertisementwhereashopperreceivedacouponforfiftycentsoffadoublenon-fatlatteonhismobiledevicewhilewalkingbythatcoffeeshop,LBS-Industryusethisadasawaytoshowhowrelevantlocation-basedadvertisingcouldbePrivacy-Industryusedthesameadtoshowhowintrusivelocation-basedadvertisingcouldbe,19,Tutorial:ICDM2008,M,UserPerceptionofLocationPrivacyOneWorldTwoViews,Ausersignedacontractwiththecarrentalthathadthefollowingtwosentenceshighlightedinboldtypeasadisclaimeracrossthetop:“Vehiclesdriveninexcessofpostedspeedlimitwillbecharged$150feeperoccurrence.AllourvehiclesareGPSequipped”,Inthatcase,thecarrentalcompanychargedtheuserfor$450forthreespeedviolationsalthoughtheuserhadreceivednotrafficticketsThecarrentalcompanyassumesthattheyhaveaccesstoalluserlocationsanddrivinghabitsTheusersuesthecarcompanyashe“thinks”thathedidnotgrantthecompanytofollowhisroute,20,Tutorial:ICDM2008,M,UserPerceptionofLocationPrivacyOneWorldTwoViews,Location-basedservicesrelyontheimplicitassumptionthatusersagreeonrevealingtheirprivateuserlocationsLocation-basedservicestradetheirserviceswithprivacyIfauserwantstokeepherlocationprivacy,shehastoturnoffherlocation-detectiondeviceand(temporarily)unsubscribefromtheservicePseudonymityisnotapplicableastheuserlocationcandirectlyleadtoitsidentity,21,Tutorial:ICDM2008,M,WHYlocation-detectiondevices?,Location-basedtrafficreportsLetmeknowifthereiscongestionwithin10minutesofmyroute,Location-basedDatabaseServer,Location-basedstorefindersWhereismynearestgasstation,Location-basedadvertisementsSende-couponstoallcarsthatarewithintwomilesofmygasstation,Withallitsprivacythreats,whydousersstilluselocation-detectiondevices?,Widespreadoflocation-basedservices,22,Tutorial:ICDM2008,M,WhatUsersWant,Entertainlocation-basedserviceswithoutrevealingtheirprivatelocationinformation,23,Tutorial:ICDM2008,M,Service-PrivacyTrade-off,Firstextreme:Auserreportsherexactlocation100%serviceSecondextreme:AuserdoesNOTreportherlocation0%service,DesiredTrade-off:Auserreportsaperturbedversionofherlocationx%service,24,Tutorial:ICDM2008,M,Service-PrivacyTrade-off,Example:Whatismynearestgasstation,25,Tutorial:ICDM2008,M,Service-PrivacyTrade-offCaseStudy:Pay-per-UseInsurance,Policy1.Onlyusercumulativedata,notdetailedlocationdata,willbeavailabletotheinsurancecompanyPolicy2.Theinsurancecompanyhasfullaccesstotheuserlocationdatawithoutidentifyinginformation.Onlycumulativedatawouldhavetheidentifyinginformation.Theinsurancecompanyisallowedtosellanonymizeddatatothirdparties.Thispolicyisofferedwithfivepercentdiscount.,26,Tutorial:ICDM2008,M,Service-PrivacyTrade-offCaseStudy:Pay-per-UseInsurance,Policy3.Theinsurancecompanyhasfullaccesstotheuserdrivingandpersonalinformation.Theinsurancecompanyisnotallowedtosharethisdatawithothers.Thispolicyisofferedwithtenpercentdiscount.Policy4.Theinsurancecompanyandthirdpartieswouldhavefullaccesstotheuserdrivingandpersonalinformation.Thispolicyisofferedwithfifteenpercentdiscount.,27,Tutorial:ICDM2008,M,TutorialOutline,PARTI:PrivacyConcernsoflocation-basedServicesLocation-basedServices:Then,Now,WhatisNextLocationPrivacy:WhyNow?UserPerceptionofLocationPrivacyWhatisSpecialaboutLocationPrivacyPARTII:RealizingLocationPrivacyinMobileEnvironmentsPARTIII:PrivacyAttackModelsPARTIV:Privacy-awareLocation-basedQueryProcessingPARTV:SummaryandFutureResearchDirections,28,Tutorial:ICDM2008,M,WhatisSpecialAboutLocationPrivacy,TherehasbeenalotofworkondataprivacyHippocraticdatabasesAccessmethodsK-anonymity,29,Tutorial:ICDM2008,M,WhatisSpecialAboutLocationPrivacy,Thegoalistokeeptheprivacyofthestoreddata(e.g.,medicaldata)Queriesareexplicit(e.g.,SQLqueriesforpatientrecords)ApplicableforthecurrentsnapshotofdataPrivacyrequirementsaresetforthewholesetofdata,Thegoalistokeeptheprivacyofdatathatisnotstoredyet(e.g.,receivedlocationdata)Queriesneedtobeprivate(e.g.,location-basedqueries)ShouldtoleratethehighfrequencyoflocationupdatesPrivacyrequirementsarepersonalized,DatabasePrivacy,LocationPrivacy,30,Tutorial:ICDM2008,M,TutorialOutline,PARTI:PrivacyConcernsoflocation-basedServicesPARTII:RealizingLocationPrivacyinMobileEnvironmentsConceptsforHidingLocationInformationSystemArchitecturesforpreservinglocationprivacyClient-ServerArchitectureThirdTrustedPartyArchitecturePeer-to-peerArchitecturePARTIII:PrivacyAttackModelsPARTIV:Privacy-awareLocation-basedQueryProcessingPARTV:SummaryandFutureResearchDirections,31,Tutorial:ICDM2008,M,ConceptsforLocationPrivacyLocationPerturbation,TheuserlocationisrepresentedwithawrongvalueTheprivacyisachievedfromthefactthatthereportedlocationisfalseTheaccuracyandtheamountofprivacymainlydependsonhowfarthereportedlocationformtheexactlocation,32,Tutorial:ICDM2008,M,ConceptsforLocationPrivacySpatialCloaking,TheuserexactlocationisrepresentedasaregionthatincludestheexactuserlocationAnadversarydoesknowthattheuserislocatedinthecloakedregion,buthasnocluewheretheuserisexactlylocatedTheareaofthecloakedregionachievesatrade-offbetweentheuserprivacyandtheservice,Locationcloaking,locationblurring,locationobfuscation,33,Tutorial:ICDM2008,M,ConceptsforLocationPrivacySpatio-temporalCloaking,InadditiontospatialcloakingtheuserinformationcanbedelayedawhiletocloakthetemporaldimensionTemporalcloakingcouldtolerateaskingaboutstationaryobjects(e.g.,gasstations)Challengingtosupportqueryingmovingobjects,e.g.,whatismynearestpolicecar,X,Y,T,34,Tutorial:ICDM2008,M,Navecloaking,MBRcloaking,ConceptsforLocationPrivacyData-DependentCloaking,35,Tutorial:ICDM2008,M,Fixedgridcloaking,ConceptsforLocationPrivacySpace-DependentCloaking,36,Tutorial:ICDM2008,M,ConceptsforLocationPrivacyk-anonymity,ThecloakedregioncontainsatleastkusersTheuserisindistinguishableamongotherkusersThecloakedarealargelydependsonthesurroundingenvironment.Avalueofk=100mayresultinaverysmallareaifauserislocatedinthestadiumormayresultinaverylargeareaiftheuserinthedesert.,10-anonymity,37,Tutorial:ICDM2008,M,Time,k,Amin,Amax,8:00AM-,5:00PM-,10:00PM-,1,100,1000,_,_,1mile,5miles,3miles,_,ConceptsforLocationPrivacyPrivacyProfile,Eachmobileuserwillhaveherownprivacy-profilethatincludes:K.Auserwantstobek-anonymousAmin.TheminimumrequiredareaoftheblurredareaAmax.ThemaximumrequiredareaoftheblurredareaMultipleinstancesoftheaboveparameterstoindicatedifferentprivacyprofilesatdifferenttimes,38,Tutorial:ICDM2008,M,ConceptsforLocationPrivacyQueryTypes,PrivateQueriesoverPublicDataWhatismynearestgasstationTheuserlocationisprivatewhiletheobjectsofinterestarepublicPublicQueriesoverPrivateDataHowmanycarsinthedowntownareaThequerylocationispublicwhiletheobjectsofinterestisprivatePrivateQueriesoverPrivateDataWhereismynearestfriendBoththequerylocationandobjectsofinterestareprivate,39,Tutorial:ICDM2008,M,ConceptsforLocationPrivacyModesofPrivacy,UserLocationPrivacyUserswanttohidetheirlocationinformationandtheirqueryinformationUserQueryPrivacyUsersdonotmindorobligatedtorevealtheirlocations,however,userswanttohidetheirqueriesTrajectoryPrivacyUsersdonotmindtorevealfewlocations,however,theywanttoavoidlinkingtheselocationstogethertoformatrajecotry,40,Tutorial:ICDM2008,M,ConceptsforLocationPrivacyRequirementsoftheLocationAnonymizationProcess,Accuracy.Theanonymizationprocessshouldsatisfyandbeascloseaspossibletotheuserrequirements(expressedasprivacyprofile)Quality.AnadversarycannotinferanyinformationabouttheexactuserlocationfromthereportedlocationEfficiency.CalculatingtheanonymizedlocationshouldbecomputationallyefficientandscalableFlexibility.Eachuserhastheabilitytochangeherprivacyprofileatanytime,41,Tutorial:ICDM2008,M,TutorialOutline,PARTI:PrivacyConcernsoflocation-basedServicesPARTII:RealizingLocationPrivacyinMobileEnvironmentsConceptsforHidingLocationInformationSystemArchitecturesforpreservinglocationprivacyClient-ServerArchitectureThirdTrustedPartyArchitecturePeer-to-peerArchitecturePARTIII:PrivacyAttackModelsPARTIV:Privacy-awareLocation-basedQueryProcessingPARTV:SummaryandFutureResearchDirections,42,Tutorial:ICDM2008,M,SystemArchitecturesforLocationPrivacy,Client-ServerarchitectureUserscommunicateddirectlywiththesevertodotheanonymizationprocess.PossiblyemployinganofflinephasewithatrustedentityThirdtrustedpartyarchitectureAcentralizedtrustedentityisresponsibleforgatheringinformationandprovidingtherequiredprivacyforeachuserPeer-to-PeercooperativearchitectureUserscollaboratewitheachotherwithouttheinterleavingofacentralizedentitytoprovidecustomizedprivacyforeachsingleuser,43,Tutorial:ICDM2008,M,Client-ServerArchitecture,1:Query+ScrambledLocationInformation,2:CandidateAnswer,44,Tutorial:ICDM2008,M,Client-ServerArchitecture,ClientstrytocheattheserverusingeitherfakelocationsorfakespaceSimpletoimplement,easytointegratewithexistingtechnologiesLowerqualityofserviceExamples:Landmarkobjects,falsedummies,andspacetransformation,45,Tutorial:ICDM2008,M,Client-ServerArchitecture:Landmarkobjects,Insteadofreportingtheexactlocation,reportthelocationofaclosestlandmarkThequeryanswerwillbebasedonthelandmarkVoronoidiagramscanbeusedtoidentifytheclosestlandmark,46,Tutorial:ICDM2008,M,Client-ServerArchitecture:FalseDummies,Ausersendsmlocations,onlyoneofthemistruewhilem-1arefalsedummiesTheserverreplieswithaserviceforeachreceivedlocationTheuseristheonlyonewhoknowsthetruelocation,andhencethetrueanswerGeneratingfalsedummiesshouldfollowacertainpatternsimilartoauserpatternbutwithdifferentlocations,Server,Aseparateanswerforeachreceivedlocation,47,Tutorial:ICDM2008,M,Client-ServerArchitecture:LocationObfuscation,AlllocationsarerepresentedasverticesinagraphwithedgescorrespondtothedistancebetweeneachtwoverticesAuserrepresentsherlocationasanimpreciselocation(e.g.,Iamwithinthecentralpark)TheimpreciselocationisabstractedasasetofverticesTheserverevaluatesthequerybasedonthedistancetoeachvertexofimpreciselocations,48,Tutorial:ICDM2008,M,Client-ServerArchitecture:SpaceTransformation,Userstransformtheirlocationsfromthetwo-dimensionalspacetoanotherspaceusingareversibletransformationThenewspacedoesnothavetohavethesamedimensionalityastheoriginalspace.Thedatabaseserveranswerslocation-basedqueriesinthenewspace.ThiscouldresultinanapproximateanswerTheuserapplyareversetransformationtotransformtheanswertotheoriginalspace,49,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitecture,1:Query+LocationInformation,2:Query+CloakedSpatialRegion,3:CandidateAnswer,4:CandidateAnswer,Thirdtrustedpartythatisresponsibleonblurringtheexactlocationinformation.,50,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitecture,Atrustedthirdpartyreceivestheexactlocationsfromclients,blursthelocations,andsendstheblurredlocationstotheserverProvidepowerfulprivacyguaranteeswithhigh-qualityservicesSystembottleneckandsophisticatedimplementationsExamples:Casper,CliqueCloak,andspatio-temporalcloaking,51,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitecture:MixZones,AmixzoneisdefinedasaconnectedspatialregionofmaximumsizewhereusersdonotregisterforanapplicationUserscanchangetheirpseudonymsoncetheyenterthemixzoneAusermayrefusetosendanylocationupdateifthemixzonehaslessthankusersUponemergingfromthemixzone,anadversarycannotknowwhichoneoftheusershascameout,MixZone,52,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitecture:k-areacloaking,Sensitiveareasarepre-definedThespaceisdividedintoasetofzoneswhereeachzonehasatleastksensitiveareaAlllocationupdatesforauserwithinacertainzonearebufferedUponleavingazone,userlocationsarerevealedonlyiftheusersdidnotvisitanyofthesensitiveareas,53,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitecture:QuadtreeSpatialCloaking,Achievek-anonymity,i.e.,auserisindistinguishablefromotherk-1usersRecursivelydividethespaceintoquadrantsuntilaquadranthaslessthankusers.Thepreviousquadrant,whichstillmeetthek-anonymityconstraint,isreturned,Achieve5-anonmityfor,54,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitecture:CliqueCloakAlgorithm,Eachuserrequests:AlevelofkanonymityAmaximumcloakedareaBuildanundirectedconstraintgraph.Twonodesareneighbors,iftheirmaximumareascontaineachother.,A(k=3),C(k=2),B(k=4),D(k=4),F(k=5),H(k=4),E(k=3),m(k=3),ThecloakedregionistheMBRthatincludestheuserandneighboringnodes.AlluserswithinanMBRusethatMBRastheircloakedregion,Foranewuserm,addmtothegraph.Findthesetofnodesthatareneighborstominthegraphandhaslevelofanonymity=m.k,55,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitecture:Bi-directionalCliqueCloak,Eachuserrequests:AlevelofkanonymityAmaximumcloakedareaAmaximumcloakinglatencyBuildadirectedconstraintgraph.AnedgefromnodeXtonodeYexistsifmaximumareaofXcontainsY.,A(k=3),C(k=2),B(k=4),D(k=4),F(k=5),H(k=4),E(k=3),m(k=3),Foranewuserm,addmtothegraph.Findthesetofnodesthatareoutgoingneighborstominthegraph,ThecloakedregionistheMBRthatincludesoutgoingneighboringnodes.UserswithinanMBRarenottiedtousethesameMBRastheircloakedregion,56,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitecture:Hilbertk-Anonymizing,AlluserlocationsaresortedbasedontheirHilbertorderToanonymizeauser,wecomputestartandendvaluesas:start=ranku-(rankumodku)end=start+ku1AcloakedspatialregionisanMBRofalluserswithintherange(fromstarttoend).Themainideaisthatitisalwaysthecasethatkuuserswouldhavethesanestart,endinterval,A,D,E,F,G,I,H,J,K,L,B,C,57,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitecture:Nearest-Neighbork-Anonymizing,STEP1:DetermineasetScontaininguandk-1usnearestneighbors.STEP2:RandomlyselectvfromS.STEP3:DetermineasetScontainingvandvsk-1nearestneighbors.STEP4:AcloakedspatialregionisanMBRofallusersinSandu.,S,S,Themainideaisthatrandomlyselectingoneoftheknearestneighborsachievesthek-anonymity,ThirdTrustedPartyArchitecture:PrivacyGrid,3,2,1,0,4,0,3,4,4,5,2,4,3,4,6,2,3,4,5,0,2,4,5,6,Anonymitylevel=20,3,Thesystemspaceisdividedintogridcellswhereeachcellmaintainsthenumberofusersinthecell,Toanonymizeauserrequest,westartfromthecellcontainingtheuser,thenweexpandthecellareatoneighboringcellsuntiltheuserprivacyrequirementsissatisfied,58,Tutorial:ICDM2008,M,59,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitecture:BasicPyramidStructure,Eachgridcellmaintainsthenumberofusersinthatcell,Toanonymizeauserrequest,wetraversethepyramidstructurefromthebottomleveltothetopleveluntilacellsatisfyingtheuserprivacyprofileisfound.,Theentiresystemareaisrepresentedasacompletepyramidstructuredividedintogridsatdifferentlevelsofvariousresolution,Scalable.Simpletoimplement.Overheadinmaintainingallgridcells,60,Tutorial:ICDM2008,M,ThirdTrustedPartyArchitec