位置个人信息泄露的危害

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2014,25(4):693712[doi:10.
13328/j.
cnki.
jos.
004551]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel/Fax:+86-10-62562563位置大数据隐私保护研究综述王璐,孟小峰(中国人民大学信息学院,北京100872)通讯作者:王璐,E-mail:luwang@ruc.
edu.
cn摘要:大数据时代移动通信和传感设备等位置感知技术的发展形成了位置大数据,为人们的生活、商业运作方法以及科学研究带来了巨大收益.
由于位置大数据用途多样,内容交叉冗余,经典的基于"知情与同意"以及匿名的隐私保护方法不能全面地保护用户隐私.
位置大数据的隐私保护技术度量用户的位置隐私,在信息论意义上保护用户的敏感信息.
介绍了位置大数据的概念以及位置大数据的隐私威胁,总结了针对位置大数据隐私的统一的基于度量的攻击模型,对目前位置大数据隐私保护领域已有的研究成果进行了归纳.
根据位置隐私的保护程度,可以把现有方法总结为基于启发式隐私度量、概率推测和隐私信息检索的位置大数据隐私保护技术.
对各类位置隐私保护技术的基本原理、特点进行了阐述,并重点介绍了当前该领域的前沿问题:基于隐私信息检索的位置隐私保护技术.
在对已有技术深入分析对比的基础上,指出了未来在位置大数据与非位置大数据相结合、用户背景知识不确定等情况下保护用户位置隐私的发展方向.
关键词:大数据;位置大数据;位置隐私保护技术中图法分类号:TP311文献标识码:A中文引用格式:王璐,孟小峰.
位置大数据隐私保护研究综述.
软件学报,2014,25(4):693712.
http://www.
jos.
org.
cn/1000-9825/4551.
htm英文引用格式:WangL,MengXF.
Locationprivacypreservationinbigdataera:Asurvey.
RuanJianXueBao/JournalofSoftware,2014,25(4):693712(inChinese).
http://www.
jos.
org.
cn/1000-9825/4551.
htmLocationPrivacyPreservationinBigDataEra:ASurveyWANGLu,MENGXiao-Feng(SchoolofInformation,RenminUniversityofChina,Beijing100872,China)Correspondingauthor:WANGLu,E-mail:luwang@ruc.
edu.
cnAbstract:Developmentofmobilecommunicationandsensingtechnologiesformslocationbasedbigdata,bringingrevolutiontohuman'sliving,businesspatternandscientificresearch.
Diversityofusagepatternsandredundancyamongvarioussourcesoflocationbasedbigdatamakeitimpossibleforclassicallocationpreservationmethodstoprotectprivacysystemically.
Privacypreservationforlocationbasedbigdatameasuresuser'slocationprivacyinallpossibleaspectsandthereforeprotectsuser'sprivacyininformationtheorysemantic.
Startingwithanintroductiontotheconceptoflocationbasedbigdata,itsassociatedprivacythreatsandauniversalmeasurement-basedattackmodel,thispapersurveysthestateoftheartofprivacypreservationtechniquesforlocationbasedbigdata.
Basedondifferentprivacyprotectingstrength,variousbigprivacypreservationtechniquescanbecategorizedintoheuristicprivacymeasurement,probabilitydeductionandprivateinformationretrievalbasedtechnologies.
Theprinciples,mechanismsandcharacteristicsofvarioustechniquesaredescribedindetail,withspecialemphasisonaproceedingresearchtopic:Privateinformationretrievalbasedtechnology.
Followingacomprehensiveanalysisandcomparisonofexistingtechniques,privacyprotectingforlocationbasedbigdata基金项目:国家自然科学基金(61379050,91224008);国家高技术研究发展计划(863)(2013AA013204);高等学校博士学科点专项科研基金(20130004130001)收稿时间:2013-08-13;定稿时间:2013-12-05;jos在线出版时间:2014-01-13CNKI网络优先出版:2014-01-1314:11,http://www.
cnki.
net/kcms/doi/10.
13328/j.
cnki.
jos.
000012.
html694JournalofSoftware软件学报Vol.
25,No.
4,April2014undersituationslikecombinationoflocationinformationandnonlocationinformationandattacker'sarbitrarybackgroundknowledgeishighlightedasfutureresearchdirections.
Keywords:bigdata;locationbasedbigdata;locationprivacy-preserving大数据时代,移动通信和传感设备等位置感知技术的发展将人和事物的地理位置数据化.
移动对象中的传感芯片以直接或间接的方式收集移动对象的位置数据:一方面,内置在手机、车载导航等移动设备中的GPS,WiFi等定位设备可以直接获得移动对象任意时刻准确的位置信息,并经过各种途径发布这些采集的位置信息,比如,移动社交网络的一些新型应用可以发布任意时刻用户所处的位置信息[1];另一方面,近期得到广泛应用的可穿戴设备等传感设备采集到的加速度、光学影像等数据经过处理后也可以准确地确定使用者的位置信息[24].
传感器自动采集位置信息的速度和规模远远超过现有系统的处理能力.
根据统计,每个移动物体平均15s提交一次当前位置,这样,全球上亿手机、车载导航设备等移动对象每秒钟提交的位置信息超过1亿条[5].
未来,移动传感设备的进步和通信技术的提升会更频繁地产生位置信息.
大数据时代,这样的产生速度和数据规模为人们的生活、企业的运作以及科学研究带来巨大的变革[6].
我们称这类由于包含位置信息且具有规模大、产生速度快、蕴含价值高等满足被普遍认可的大数据的特点[7]的数据为位置大数据.
位置大数据在人们的生产与生活中有诸多运用:一方面,从个人生活层面上说,通过推测一个人居住的地点和每天常去的地方,可以为他提供便捷的服务.
例如:文献[8,9]利用人们大量的历史活动轨迹数据,为每个人的出行和旅游给出路线推荐;文献[10]根据当前的交通流量情况,为用户推荐可以乘坐的公共交通;总部位于亚特兰大的AirSage公司每天通过处理来自上百万手机用户的150亿条位置信息,为超过100个美国的城市提供实时交通信息[11].
当前,这些基于位置大数据的新型服务逐渐形成了一个正在迅速增长的市场.
一份来自PyramidResearch的调查报告显示,2010年,诸如导航或移动社交网络等基于位置的服务已具有28亿美元的市场.
到2015年,这一数字将达到103亿美元[12];更重要的是,位置大数据改变了商业运作方式并为科学研究提供了新的方法.
例如,传统的车险业通过考虑一个群体的平均风险确定车险定价,当保险公司通过获得的车辆出行时间、常见行驶地点和实际行驶过程等位置大数据后,转变为对每个用户个性化的分析定价,改变了车险业的运作方式[13].
与此同时,联合包裹运输公司(unitedparcelserviceincorporation)收集自己旗下运输车辆的行驶信息,为它们提供最佳行车路线以减少燃油、故障成本,在商业模式上取得了巨大成功.
仅2011年,UPS公司旗下的车辆就节省了4828万公里的路程、1136万升的燃料和3万吨二氧化碳的排放,同时减少了容易出事故的路线[14].
此外,无线数据科技公司(Jana)使用来自100多个国家的、超过200个无线运营商提供的、覆盖了拉丁美洲、非洲、欧洲的大约35亿人口的手机数据,试图回答疾病如何传播以及城市如何繁荣这样重大的科学问题[15].
位置大数据在带给人们巨大收益的同时,也带来了泄露个人信息的危害.
这是因为位置大数据既直接包含用户的隐私信息,又隐含了用户的个性习惯、健康状况、社会地位等其他敏感信息.
位置大数据的不当使用,会给用户各方面的隐私带来严重威胁.
已有的一些案例说明了隐私泄露的危害,例如:某知名移动应用由于不注意保护位置大数据,导致根据三角测量方法可以推断出用户的家庭住址等敏感位置,已引发多起犯罪案件[16].
同时,某著名移动设备厂商在未获得用户允许的情况下大量收集用户的位置数据[17,18],攻击者可以通过这些位置数据推测用户的身体状况等个人敏感信息[1921].
而在为用户提供了合适的位置隐私保护后,更多的人愿意将自己的移动数据提交给智能交通、智能城市等分析系统,进而为人们的日常生活提供更多的便利.
经典的位置隐私保护技术经过较长时间的发展,从最早将位置数据视为一般数据使用"知情与同意"[22]等访问控制方法发展到针对单个位置数据的匿名化隐私保护方法,再进一步完善到对轨迹数据的匿名化隐私保护方法.
但是,"知情与同意"以及匿名化等经典的位置隐私保护方法在大数据时代不能有效地保护用户隐私:(1)大数据尚未想到的用途无法提前告诉用户,企业也无法承担发现位置大数据的创新性用途后通知每王璐等:位置大数据隐私保护研究综述695个用户并请求用户同意再进行使用的成本.
因此,"知情与同意"等保护方法要么限制了对位置大数据价值的挖掘,要么无法保护个人隐私;(2)由于位置大数据来源众多,这些数据之间可以相互补充,最近的研究对精心匿名的位置数据进行了成功的反匿名化[23].
大数据时代,经典位置隐私保护方法不能解决的主要问题是:攻击者可以从多种途径获得各个角度关于用户的位置数据或非位置数据,这些数据可以直接或者间接地重构出用户希望保护的位置隐私.
比如:(1)单纯针对位置数据.
用户在服务A中保护起来的数据可能在服务B中被泄露,如果攻击者同时获得服务A和服务B中的数据,就可以重构出用户的准确数据;(2)考虑位置与非位置数据相结合的情况.
位置数据与非位置数据由于是同一用户产生,因此,用户的某些个性就成为了位置数据与非位置数据之间的联系.
攻击者根据这些个性可以区分不同用户的位置数据,进而对用户的身份等敏感信息进行推测.
位置大数据隐私保护技术面对这两种威胁全面地控制用户位置信息的泄露.
位置大数据隐私保护技术可以保证针对用户不同的隐私需求进行信息论意义上的全面保护.
因此,位置大数据隐私保护技术需要考虑以下3个具有挑战性的问题:(1)如何度量用户的敏感信息的泄露程度;(2)如何实现对位置大数据隐私全面的保护;(3)如何兼顾隐私保护的程度和基于位置服务的可用性.
传统的位置隐私保护方法(如基于加密的方法等)没有考虑对用户敏感信息泄露的度量问题,也不能实现对位置隐私的全面保护,因此无法在隐私的保护程度和可用性之间做出权衡.
当前,位置大数据隐私保护技术主要针对不同程度的隐私需求,权衡隐私保护效果和服务可用性.
本文综述位置大数据隐私保护技术的最新进展:一方面,介绍位置大数据的基本概念以及总结出针对位置大数据隐私的统一的基于度量的攻击模型等研究背景;另一方面,以统一的攻击模型为依据,根据不同隐私保护技术在隐私保护程度和服务可用性之间的权衡情况,分类阐述位置大数据的隐私保护技术,分析不同技术的优缺点、适用场景等.
其中,重点介绍当前该领域的前沿问题、基于隐私信息检索的隐私保护技术.
本文在对位置大数据的隐私保护技术进行综合对比和分析后,探讨了位置大数据未来的研究方向.
考虑到大数据时代的攻击者可以获得和位置数据相关的非位置数据[24],可以从其他角度获得或者分析用户的历史位置数据得到有关用户的背景知识,本文认为,位置大数据与非位置大数据结合产生的隐私问题将是未来的研究热点之一.
其中,作为位置数据与非位置数据结合的特例,移动社交网络由于天然地将位置数据与非位置数据结合起来,将成为未来的研究热点之一.
本文在未来工作中介绍了一种通用的位置数据与非位置数据结合后的位置隐私保护方法,同时介绍了移动社交网络中的隐私保护方法.
除此以外,由于位置大数据隐私的统一的基于度量的攻击模型与攻击者具有的背景知识有关,而差分隐私由于其对背景知识不敏感,在量化隐私时具有重要意义,本文认为,将差分隐私应用到位置大数据隐私保护中,也是未来的研究热点.
本文第1节介绍位置大数据的隐私保护的概念和统一的基于度量的攻击模型等背景知识.
第2节对位置大数据的隐私保护技术的分类和评估方法进行介绍.
第3节~第5节分别对3大类位置大数据的隐私保护技术:基于启发式隐私度量、基于概率推测和基于隐私信息检索的位置大数据隐私保护技术进行阐述.
第6节~第7节对各类技术进行对比分析,并指出未来的研究方向.
第8节为全文结语.
1位置大数据隐私与隐私度量1.
1位置的表示与定位技术位置是指移动对象在某一时刻的经纬度,通常由三元组经度x,纬度y,时刻t表示.
文献[25]总结了目前对移动对象进行定位的5种常用方法以及攻击者获得移动对象位置信息常用的3种方法.
其中,移动对象获得自己的位置常用以下5种方法:(1)全球定位系统部署的卫星与移动设备经过通信,根据多个卫星与同一移动设备之696JournalofSoftware软件学报Vol.
25,No.
4,April2014间通信时在时间上的延迟,使用三角测量方法得到目前最为精准的移动物体的经纬度[26],目前常见的GPS设备可以实现5m以下的精度;(2)因为WiFi访问点与它们的准确位置之间的对应关系,可以从类似文献[27]的数据库中查找到,当移动物体连接到某个WiFi访问点时,用户的位置也可以较精确地对应到一个经纬度[28];(3)当移动设备位于3个手机基站的信号范围内时,三角测量同样可以获得用户的经纬度[29],这种方法和方法(2)都避免了GPS系统无法在建筑物内进行定位的缺点;(4)移动设备接入互联网时会被分配一个IP地址,IP地址的分配是和地域有关的,利用已有的IP地址与地区之间的映射关系,可以将移动物体的位置定位到一个城市大小的地域[30];(5)目前的很多研究显示,通过传感器捕获的加速度、光学影像等信息,可以用于识别用户的位置信息[24].
移动用户使用上述方法获得自己的位置信息以后,攻击者通常使用以下3种方法获得移动用户的位置信息:(1)攻击者发布恶意的基于位置的应用,当移动用户使用这些应用请求基于位置的服务时,这些应用会向攻击者报告用户的当前位置,当前,手机应用中流行的移动社交网络的签到应用和导航应用等都有可能被攻击者利用;(2)一些网站,例如文献[31],可以通过用户的IP地址获取用户的位置信息,当移动设备访问这些网络信息时,自己的位置就可能暴露给攻击者;(3)用户在使用移动设备浏览网页时,会因为响应一些网页中的请求将当前的位置信息发送给网页指定的攻击者[32,33],这种方法与方法(2)类似,但攻击者不需要掌握从IP地址到位置的映射方法.
1.
2位置大数据的隐私威胁类似一般的隐私定义[34],我们认为,位置大数据的隐私是移动对象对自己位置数据的控制.
大数据时代,位置数据的来源极为广泛,位置大数据中包含的移动对象不同时刻的位置信息与背景知识结合,会泄露用户的健康状况、行为习惯、社会地位等敏感信息.
比如:观察到用户出现在医院附近,可以推测出用户大致的健康状况;考虑用户轨迹开始和结束的地点,可以推测出用户的家庭住址等信息[20].
此外,加速度传感器等收集到的只包含部分位置的信息,也可以让攻击者有效推测用户的行为模式[35].
攻击者利用类似上述各种数据推测用户某时刻的隐私,在传统的位置隐私保护工作中通常被称为观察攻击[3638]或者关联攻击[39,40],但这些攻击模型不能概括大数据时代用户的位置隐私面对全方面推测的威胁.
我们将使用各种类型的数据推测用户位置隐私的行为总结成位置大数据的隐私攻击模型:模型包括攻击者获得的数据D以及攻击者希望据此推测出的攻击对象U在t′时刻处于位置i的概率{|}tiPUD′.
由于前文提到"知情与同意"、匿名等经典的隐私保护策略在大数据时代均失效,如何防止攻击者利用收集到的各方面数据推测用户的隐私信息,成为大数据时代亟待解决的位置大数据的隐私保护问题.
位置大数据隐私保护技术研究的早期,并没有专门针对位置大数据的保护手段,研究者仅简单通过用户对数据进行分类,并提供访问控制列表或者数据使用列表等隐私控制策略,避免不可信对象对用户敏感位置数据的获得[4144]以及数据的不正当应用[22].
之后,针对位置大数据隐私保护的研究集中在如何避免向攻击者发布移动对象某一时刻的精确位置,同时获得基于位置大数据的服务,这类技术的典型方法包括位置k匿名等基于单点位置的启发式隐私度量的方法[4549].
随着位置大数据隐私保护技术的发展,人们开始注意到轨迹信息包含用户的移动在时间上的相关性[28,5052],于是,保护用户的轨迹信息的方法受到重视.
由于位置之间在时间上的相关性难以把握,一些基于轨迹的启发式的隐私度量方法(比如将位置数据随机化的方法、对空间数据的模糊化方法和对时间数据的模糊化方法)被提了出来.
但在大数据时代,提供可以量化的位置大数据的隐私保护效果是十分重要的[53],因此,基于概率推测的位置大数据隐私保护方法从信息论的角度给出位置隐私完整的度量方式,量化每个位置数据暴露的用户隐私.
同时,基于隐私信息检索的位置大数据隐私保护技术提供了完美隐私(见下文定义1中相关内容).
1.
3位置大数据隐私的攻击模型位置大数据隐私的攻击模型使用统一的度量方法描述对位置大数据隐私的攻击效果.
不同攻击方法的效果由根据发布后的位置大数据能够提供给攻击者多少用户处于某敏感位置的信息增益来刻画.
攻击者收集的用户的位置数据是包含了用户的时空数据的集合{r:r=p,t},其中,r代表攻击者收集到的一条位置数据,p代表王璐等:位置大数据隐私保护研究综述697用户的位置信息,t代表收集到这条数据的时刻.
那些可能暴露用户隐私的敏感位置也组成一个集合{s1,…,sn},其中,si代表将敏感位置编号后的第i个敏感位置.
根据收集到的位置数据,攻击者可以通过推测用户在t时刻处于某个敏感位置si的概率P{用户在时刻t的位置为si|攻击者收集到的用户的历史位置序列},从而推测用户的隐私信息.
为了量化攻击效果,我们定义任意时刻用户发布的位置数据不泄露用户处于某一敏感位置的θ隐私.
定义1(位置大数据的θ隐私).
在任意时刻t′,用{}tiPU′表示用户在t′时刻处于位置si的概率,用Lt表示攻击者收集到的用户在时刻t之前发布的位置数据,则,ttitiPULPUθ′′≤,其中,θ是用户给定的隐私需求,也是攻击者能够获得的最大攻击效果;{|}titPUL′表示攻击者收集到用户t时刻之前的位置数据后推测用户在t′时刻处于敏感位置si的后验概率;P{Ui}是攻击者推测用户处于敏感位置si的先验概率.
定义1的含义是:攻击者收集到的用户的位置数据为攻击者推测用户的敏感位置带来的信息量不能超过θ,即,获得用户位置序列后推测用户某一时刻处于某个敏感位置的后验概率与先验概率之差小于θ.
按照信息论的定义[42],在任何时刻t′,攻击者掌握的用户所处位置的先验信息量为{}log{}ttiiiPUPU′′∑.
用户的位置大数据暴露给攻击者用户所处位置的信息量可以如下计算:{}loglog{|}.
ttttiiititiiPUPUPULPUL′′′′∑∑根据定义1,满足θ隐私的保护方法可以保证对位置大数据隐私的攻击方法的效果nθ,其中,n是敏感位置的个数.
显然,如果用户需要保证发布位置数据不泄露用户处于任意敏感位置的θ隐私,只需在每个时刻都满足定义1中的θ/n隐私.
在给定时刻,具有强隐私需求的用户可以将θ设置为0,这时称为完美隐私.
以上的位置大数据隐私攻击模型针对单一数据类型的位置数据,但在第7节对未来工作的展望中我们可以看到,面对位置大数据的隐私,未来将位置数据与非位置数据结合的研究方向,该攻击模型同样适用.
总的来说,位置大数据的攻击模型采用统一的基于度量的方法将位置数据对用户隐私的披露风险使用定义1进行量化.
从定义1我们可以看出,用户在任意时刻t′的位置隐私与攻击者收集的t时刻之前的位置数据集Lt有关,由于攻击者可以持续收集位置数据集Lt以至于t>>t′,用户任意时刻的位置隐私实际上与t′时刻前和t′时刻后都有关.
特别地,当定义1中的θ为0时,这样的隐私保护技术称为完美隐私技术.
2位置大数据隐私保护技术分类及性能评估2.
1位置大数据隐私保护技术的分类不同的位置大数据隐私保护技术都以定义1为统一的攻击模型,但出于不同的隐私保护需求以及实现的原理不同,在实际应用中各有优缺点.
本文将位置大数据隐私保护技术分为3类:(1)基于启发式隐私度量的位置大数据隐私保护技术.
在定义1中,任意时刻t′的位置信息发布后,暴露的用户敏感信息与攻击者收集到的时刻t′之前和之后的位置数据都有关,针对这些完整的数据攻击和保护用户的位置隐私代价很大.
对于一些隐私保护需求不严格的用户,基于启发式隐私度量的位置大数据隐私保护技术假设用户在t′时刻的位置信息只与当前时刻攻击者收集到的数据有关.
相应的方法包括经典的基于单点或轨迹的位置隐私保护技术,如针对位置或轨迹的k匿名[54]、l多样性[55]、t紧密性[56]、p敏感性[57]、m不变性[58]或空间匿名框等方法.
直接应用这些方法会遭受针对数据特征的攻击.
比如:经过空间匿名框处理以后的数据,在考虑移动物体的移动速度以后,某时刻发布的匿名框的一部分由于移动物体从上一时刻的匿名框中无法到达从而导致匿名失败.
为此,这类方法针对常见的攻击手段,如考虑匿名框的面积等技术,对发布的位置数据进行处理,以降低攻击者推测出用户敏感位置的可能性.
(2)基于概率推测的位置大数据隐私保护技术.
这类方法严格按照定义1量化攻击模型的效果,并进而限制任意时刻t′发布的位置数据包含的信息量.
基于概率推测的隐私保护技术假设攻击者具有全部背景知识,并由此对每个发布的位置数据计算其披露风险,判断698JournalofSoftware软件学报Vol.
25,No.
4,April2014发布当前的位置数据是否违反用户的隐私要求.
因此,这种位置大数据的隐私保护技术可以在攻击者具有完全的背景知识的情况下,在统一的位置大数据攻击模型下,定量地保护用户的位置隐私.
(3)基于隐私信息检索的位置大数据隐私保护技术.
当用户要求定义1中的完美隐私时,由于发布位置信息或多或少地会为攻击者带来一些信息,这时会导致没有数据可以发布,因而无法获得基于位置大数据的服务.
基于隐私信息检索的位置大数据保护技术,可以在任何情况下完全地保护移动用户的隐私.
基于隐私信息检索的方法与加密方法类似,都是为了完全保护用户的隐私.
但在位置大数据上的应用服务中,由于用户查询本身包含位置信息,很长时间内都不存在可以在不解密用户查询的情况下回答复杂的基于位置的查询的加密算法.
尽管最近的研究结果发现,基于同态映射的加密方法[59]可以在不暴露用户位置隐私的情况下返回正确的查询结果,但最新的结果显示,因为高效的数据访问方法暴露了数据之间的顺序,可以提供完美隐私的高效加密方法是不存在的[60].
这3类技术各有自己的优势和缺陷:基于启发式隐私度量的隐私保护技术效率通常比较高,但位置信息存在一定程度的不准确性,另外也易遭受研究者没有考虑到的针对数据特点的攻击;基于隐私信息检索的位置大数据隐私保护技术正相反,可以完全保证数据的准确性和安全性,但预计算开销和运行时计算开销比较大;而基于概率推测的位置大数据隐私保护技术则可以提供相对平衡的隐私保护程度和运行效率.
在第3节~第5节,本文将分别深入地阐述这3类位置大数据隐私保护技术.
2.
2位置大数据隐私保护技术的性能评估位置大数据隐私保护技术需要在保护用户位置隐私的同时兼顾服务的可用性以及开销.
本文从以下3个方面度量位置大数据隐私保护技术的性能:(1)隐私保护程度.
这通常由隐私保护技术的披露风险来反映,定义1中的θ就是用户可以接受的最大披露风险.
披露风险θ越小,隐私保护程度越高;(2)服务的可用性.
这是指发布位置信息的准确度和及时性,它反映通过隐私保护技术处理后用户获得的基于位置数据的服务质量.
通常,服务的可用性与隐私保护程度之间具有一个权衡,提高隐私保护程度有时会降低服务的可用性;(3)开销.
位置大数据隐私保护技术的开销包括预计算和运行时发生的存储和计算代价.
存储代价主要发生在预计算时.
预计算的代价在现有技术中通常可以接受,并在选择隐私保护技术时被忽略.
运行时的计算代价根据位置大数据隐私保护技术的特点一般利用CPU时间以及文件块访问次数的时间复杂度进行度量.
比如,基于启发式隐私度量和基于概率推测的位置大数据隐私保护技术一般使用时间复杂度来度量开销,基于隐私信息检索的位置大数据隐私保护技术通常使用文件块的访问次数的时间复杂度来度量开销.
3基于启发式隐私度量的位置大数据隐私保护技术定义1中,t′时刻的位置数据发布后的后验概率与攻击者收集到的用户的全部历史数据有关,因此,计算后验概率是计算量很大的一项任务.
文献[61]仅考虑连续提交的位置数据中包含的速度信息暴露给攻击者的信息量,但这样依然导致计算上过于复杂,最终将连续取值的位置数据离散化.
即使不要求定义1中的完美隐私,一些为了避免攻击者考虑到用户移动速度造成的匿名失败的隐私保护方法也面临求解NP问题[62].
因此,早期的位置大数据隐私保护技术通常保护启发式的隐私度量,假设用户在t′时刻所处的敏感位置只与当前时刻发布的位置数据有关.
这样,同时满足直觉上的隐私需求,提供较为高效的隐私保护算法和较快响应的基于位置的服务.
直到人们开始深入地研究人的移动模式,高效地满足定义1中信息论意义上完整的隐私条件的隐私保护技术才相继出现(见第5节).
启发式的隐私度量主要包括让用户提交不真实的位置数据来避免攻击者获得用户的真实位置数据,采取的主要技术包括随机化、空间模糊化和时间模糊化技术.
这些技术一般假设在移动用户和服务器之间存在一个可信任的第三方服务器来将用户的位置数据转换成不真实的位置数据,以及将对模糊数据的查询结果转化成王璐等:位置大数据隐私保护研究综述699用户需要的结果.
3.
1随机化随机化是在原始位置数据中加入随机噪声.
可信任的第三方服务器在接收到用户的准确位置以后,将噪音和准确位置都发送给服务提供商,并根据用户的真实数据过滤服务提供商返回的查询结果,并将过滤后的结果返回给用户.
文献[63]首先提出了随机化方法,在每一时刻,都根据上一时刻的位置按照随机的速度和随机的方向进行移动,并将获得的随机位置点加入到原始数据中进行发布.
然而,这些位置点组成的历史数据中的移动特征与真实的移动对象的特征具有很大差别,甚至提交的位置可能是一些实际上不可达的位置,因此很容易被攻击者区分.
为此,文献[64]在产生随机位置数据的时候加入了路网、移动速度等对移动的约束条件.
文献[63,64]都假设物体在不停地移动;文献[65]考虑到移动对象不会不停地移动,根据移动对象的周围环境等因素让移动对象随机地产生停顿,以进一步防止攻击者区分这些噪声.
3.
2空间模糊化空间模糊化在一定程度上通过降低发布的位置数据的精度以满足用户的隐私需求,同时,没有妨碍地获得服务.
空间模糊化的隐私保护技术通常将用户提交的位置精度从一个点模糊到一个区域,直至任一用户提交的位置数据都包含其他若干用户使得攻击者无法获得某个用户清晰的位置.
图1(a)是某一时刻A到E这6个移动用户在空间中的位置.
空间被Quad-tree等技术划分成若干区域,用户希望每次发布的位置数据不要准确到区域中只有自己一个用户.
于是,用户A(B,C)在发布自己的位置时,可以发布左下角阴影区域作为自己的位置,用户D(E,F)可以发布右上角阴影区域作为自己的位置.
每个用户的近邻查询会向服务提供商发送自己所在的阴影区域,服务提供商需要根据计算包含阴影区域中任何一点的最近邻的区域,返回其中包含的全部用户.
对于包含右上角阴影区域的近邻查询,服务器只需要返回阴影区域和黑色区域包含的全部用户,发起查询的用户就可以自行计算出自己的近邻.
实际上,用户D(E,F)发出的近邻查询不需要返回整个右上角4个区域中的全部用户,只需要返回与右上角的浅色区域相近的若干用户即可,这样就显著减少了需要传输的数据量,提升了服务的可用性.
利用三角形两边之和大于第三边的性质,可以求出与右上角浅色区域相近用户距离浅色区域的边界的最大值.
这样,传输更小的区域中包含的全部用户给发起查询的用户也是正确的[47].
文献[66]考虑到隐私需求应当保证两个连续提交的区域间在速度上是可达的,并根据用户的实际速度修正前面方法提交的区域.
这种隐私需求在文献[48,49]中得到扩展,允许每个用户具有不同的模糊要求.
比如,A可以要求提交的区域中至少具有两个不同对象,B可以要求提交的区域中至少具有3个不同对象.
这种方法用图1(b)表示每一时刻各个用户之间的关系,其中,考虑到速度因素后依然可以保护隐私的用户间有边相连.
为了应对个性化的隐私需求,每个用户都维护图中包含自己的最大团.
如果团的大小大于区域中用户要求的最少用户个数,那么包含这个团的区域可以直接作为用户的提交区域.
由于在图中寻找最大团是一个NP-hard问题,文献[49]增量地维护每个用户的最大团,缩短了用户请求的响应时间.
(a)(b)Fig.
1Illustrationforspacevagueness图1空间模糊化示意图DEFABCACDEB700JournalofSoftware软件学报Vol.
25,No.
4,April20143.
3时间模糊化时间模糊化通过增加位置数据的时间域的不确定性,以减少位置数据的精度.
一个简单的时间模糊的例子如图2所示:图2(a)是两个移动物体在路网上移动的示意图,物体1的移动轨迹用黑色表示,物体2的移动轨迹用灰色表示.
没有经过时间模糊时,他们要提交的位置信息如图2(b)前两行所示.
假设用户希望t2时刻在黑色框内的用户不唯一,经过时间模糊后的位置数据如图2(b)后两行所示.
在t2时刻,黑色框内物体1和物体2同时在C出现,达到了用户的隐私要求.
(a)(b)Fig.
2Illustrationfortimevagueness图2时间模糊化示意图由于时间模糊易于操作且实际应用通常不需要很大程度的模糊,它被广泛应用在隐私保护中.
考虑到移动对象在某些敏感位置在时间上具有特征,比如在交通路口,当红色交通信号灯亮时,附近的移动对象会较长时间没有位置上的变化.
对这些位置数据的时间域进行模糊,能够避免攻击者察觉到用户处于交通路口这一事件的发生[67].
同时,有时满足用户隐私要求的区域不存在,这时,使用时间模糊化可以实现用户的隐私需求[48,49,66].
4基于概率推测的位置大数据隐私保护技术由于实现位置大数据的完美隐私代价较高,早期基于启发式隐私度量的方法只考虑当前时刻的位置信息是否会暴露用户的敏感位置信息.
因此,用户的隐私信息可能会由于数据在时间和空间上的关系而泄露.
根据定义1,隐私保护的目标是限制攻击者收集到用户的历史位置数据以后在某一时刻推测用户处于某敏感位置的概率的信息增益,即,知道用户的历史位置数据后计算出的用户某一时刻处于某敏感位置的后验概率与用户处于同一敏感位置的先验概率之差.
计算某一时刻用户处于敏感位置的概率需要把握用户的位置数据在时间和空间上的关系.
最新的研究成果显示:用户在未经保护的情况下,位置数据在时间和空间上的关系可以通过多种模型来刻画.
当前主要使用隐马尔可夫模型[68]及其一般化模型图模型[69]刻画用户的位置数据在时间和空间上的关系.
满足隐私定义1的一种平凡的方法是抑制所有位置数据的发布,但是:(1)这样做无法获得基于位置的服务;(2)当用户放松隐私保护需求时,这样做在服务的性能上没有收益.
另一方面,仅仅发布非敏感位置并不能有效地保护位置大数据的隐私,这是因为攻击者会根据自己掌握的模型推测当用户发布的数据为抑制时,用户处于一些特定的敏感位置.
因此,可行的方法是为用户所处的每个可能的位置关联一个发布位置数据的概率,这些概率形成一个发布概率向量,用户在每个位置根据其关联的概率值对自己的位置进行发布或抑制发布.
这样,攻击者无法区分敏感位置和非敏感位置,从而无法以较高的后验概率推测出用户处于哪个敏感位置.
4.
1基于隐马尔可夫模型进行概率计算图3是将用户移动模式用隐马尔可夫模型建模的示意图,用户从每天的起始位置开始移动,以后的各个时刻会根据上一时刻用户位置的不同转移到各个其他位置,其中一些位置是敏感位置,在图中用浅色阴影表示.
转移的概率由模型建立时形成的参数确定.
攻击者推测用户处于敏感位置的先验概率是0.
2,假设无论用户处于敏感位置或非敏感位置都以0.
5的概率发布位置,但攻击者接收到抑制发布的位置信息时,根据贝叶斯公式,其推测用户处于敏感位置的后验概率为物体1A,t1,C,t2,E,t3物体2B,t0,C,t1,D,t2物体1A,[t1,t2],C,[t2,t3],E,[t3,+∞]物体2B,[t0,t2],C,[t1,t3],E,[t3,+∞]王璐等:位置大数据隐私保护研究综述701()0.
20.
5()0.
2.
()0.
20.
50.
80.
5PPP*===*+*用户处于敏感位置且发布位置信息用户处于敏感位置|发布位置信息用户发布位置信息若用户要求定义1中θ=0.
1的位置大数据隐私,则当前以向量(0.
5,0.
5)为发布概率向量就可以满足要求.
Fig.
3IllustrationforhiddenMarkovmodelofuser'smovingpattern图3用户移动的隐马尔可夫模型示意图目前,由于隐马尔可夫模型具有模型简单且捕捉到的用户的位置数据在时间和空间上的关系较准确的特点[70],基于隐马尔可夫模型进行概率推测的位置大数据的隐私保护技术受到重视[71].
隐马尔可夫模型认为,用户发布的位置数据只与其当前所处的位置有关,因此,用户当前所处的位置对能否安全地发布位置数据具有很大的影响.
比如:不敏感的当前位置对用户的位置隐私威胁很小因而容易被发布;同时,考虑到历史数据暗示了用户当前位置是否敏感,因此,用户在当前时刻前发布的历史数据也对当前位置是否能够安全地发布具有很大影响.
总之,当前时刻所处的位置和当前时刻前发布的历史数据对是否发布位置数据直接影响了基于位置服务的可用性.
为此,文献[71]提出了两种不同的抑制位置信息的方法,它们针对各自的用户群体具有各自适宜的服务可用性:第1种方法首先针对用户的隐马尔可夫模型进行各个位置的发布概率向量p=(p1,…,pn)的预计算,其中,pi表示将各个位置编号后,用户处于第i个位置的时候以pi的概率发布当前位置.
预计算分为两个阶段:第1个阶段生成一个候选的发布概率向量,第2个阶段判断这个发布概率向量是否能保护用户的位置隐私.
这两个阶段都涉及到计算量大的问题.
在第1个阶段中,因为每个概率值是一个实数,枚举全部可能的概率向量是不可行的.
注意到,发布概率的降低一定会保证更好的隐私以及发布概率的提高一定会保证更好的服务可用性,预计算从不发布全部位置信息开始,即,p=(0,…,0),利用贪心优化方法MONDFRIAN[72]和ALGPR[73]逐渐调整各个位置发布的概率,并检查在当前发布概率向量p是否能在任何情况下满足隐私保护的要求.
面对第1个阶段每次生成的一个候选的发布概率向量,第2个阶段需要考虑按照这个发布概率向量进行发布后,攻击者能够收集到的位置数据是否满足用户的位置隐私需求,即,没有泄露超过用户指定的信息量阈值.
发布概率向量p确定以后,给定某个移动轨迹,用户在该轨迹下各个时刻发布的位置数据序列的概率很容易计算;反过来,利用贝叶斯公式可以根据用户发布的位置数据计算用户在某时刻处于某个位置的概率.
利用这一点,根据攻击者可能获得的位置数据,计算用户属于敏感位置的概率(后验概率);同时,根据用户的移动模式已经建立起来的隐马尔可夫模型可以计算每个时刻用户处于某个敏感位置的概率(先验概率).
根据后验概率与先验概率之差,判断p是否满足隐私需求.
不断地修改p中各个元素的值,最终p会收敛.
在实际运行中,系统按照收敛后的发布概率向量在各个位置发布用户的位置信息.
第2种方法省去了预计算过程,根据用户在当前时刻前的历史位置数据,计算用户当前位置处于各个敏感位置的先验概率;然后,考虑未来所有可能的位置发布,计算发布当前位置以后用户在各个时刻处于各个敏感位置的后验概率;根据这两个概率之差,判断发布当前位置是否破坏隐私需求,在线地决定是否发布当前位置信息.
文献[74]将"考虑未来所有可能的位置发布"这样一项时间复杂度极高的任务,简化成多项式时间内可完成的任务.
702JournalofSoftware软件学报Vol.
25,No.
4,April20144.
2基于图模型进行概率计算隐马尔可夫模型在对人的移动模式进行建模时,假设人下一时刻移动到的位置只与当前位置有关,而与曾经的位置无关.
这样的假设有利于模型的高效创建,但对用户在某时刻处于某位置的概率计算并不十分准确.
图模型是对隐马尔可夫模型的一般化,它允许用户在某时刻处于某位置与历史位置数据有关.
文献[75,76]使用图模型对用户的移动模式进行建模,获得了更为准确的位置数据在时间和空间上的关系,其先验概率和后验概率的计算与隐马尔可夫模型的计算是类似的,采用的均是教科书中标准的高效算法.
5基于隐私信息检索的位置大数据隐私保护技术上面的两类方法通过发布不精确的位置数据和抑制发布位置数据达到对位置大数据隐私保护的目的.
然而,当用户的隐私需求较高或者需要完美隐私时,这两类方法都面临要么发布非常不精确的位置要么无法发布当前位置,因此,用户无法获得基于位置大数据的服务.
基于隐私信息检索(PIR)的位置大数据隐私保护技术在确保服务可用的情况下不会泄露任何用户的位置信息,实现了完美隐私.
5.
1隐私信息检索方法简介隐私信息检索理论最早被应用于访问网络中的外包数据,用户可以检索一个不可信的服务器上的任意数据项而不暴露用户检索的数据项信息[77].
实现PIR的方法可以按照隐私保护的强弱分为基于信息论的PIR方法和基于计算能力的PIR方法.
基于信息论的PIR方法保证攻击者无论拥有怎样的计算能力,都不能区分用户对不同数据项的访问;基于计算能力的PIR方法假设攻击者不具有计算求解某个难题的能力而保证攻击者不能区分用户对不同数据项的访问.
基于信息论的PIR方法有且只有一个平凡的解法:将全部信息都发送给客户端[78],这需要的传输代价是O(n),其中,n是数据库的大小.
因此,当前通常采用基于计算能力的PIR方法.
目前常用的PIR方法有两种:一种基于一个难解的二次剩余假设问题[79],另一种基于伪随机函数的可实现性[80].
这两种方法通常被硬件实现,安装在服务器端以消除查询中多个PIR访问间客户端与服务器之间的通信代价.
利用二次剩余假设问题的难解性实现PIR的原理如下:假设m是一个正整数,如果存在一个整数x,满足x2=amodm,则整数a被称作模m的"二次剩余(QR)";否则,a称为模m的"非二次剩余(QNR)".
二次剩余假设认为:在不给定m的因式分解的情况下,识别一个数a是否是模m的二次剩余,是一个NP问题.
如图4所示(br是非二次剩余,根据矩阵中每一列的值计算出的Pi如果是二次剩余,则说明元素Xri为0,否则说明元素Xri为1),基于计算能力的PIR方法将数据库看成一个矩阵[xij],假设用户对xij感兴趣,用户预先计算好s1个模m的二次剩余a1,.
.
.
,ai1,ai+1,.
.
.
,as和一个非二次剩余bi,并将向量(a1,.
.
.
,ai1,bi,ai+1,.
.
.
,as)发往服务器端.
服务器由于计算能力有限,无法区分哪个是二次剩余,哪个不是二次剩余,因此,服务器将这个向量看作(u1,.
.
.
,us),然后根据下述方法计算一个向量(p1,.
.
.
,ps):pi是根据矩阵的第i列计算出来的,它是那些值为1的xri对应的ur的乘积.
例如,如果第i列的x值都为1,那么1.
sijjpu==∏如果xij为0,那么pi是那些二次剩余的乘积,因此pi仍是一个二次剩余;反之,如果xij为1,那么pi的乘积中有一项非二次剩余,因此pi是非二次剩余.
客户端通过这个性质来知道xij的值,而不暴露自己想查哪个位置的值.
Fig.
4IllustrationforquadraticresiduebasedPIRmethod图4基于二次剩余方法的PIR示意图X11Xs1X1sXssP1PiPsa1(QR)br(QNR)as(QR).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
王璐等:位置大数据隐私保护研究综述703利用伪随机函数实现PIR的基本方法如下:首先,定义随机排列:对于有n个元素的数据库DB,其上的一个随机排列按照以下对应规则π将DB转换成DBπ:DB[i]=DB[π[i]].
例如,对于数据库DB={o1,o2,o3},如果排列π是[2,3,1],则DBπ[1]=DB[π[1]]=DB[2]=o2,DBπ[2]=DB[π[2]]=DB[3]=o3,DBπ[3]=DB[π[3]]=DB[1]=o1.
因此,DBπ={o2,o3,o1}.
当应用PIR方法时,首先对数据库中的数据块进行加密重排处理.
之后,每当查询到来时,选取处理后的数据块返回客户端,并将获取的数据块再次与其他数据块混合重排.
另外,控制每一个查询都访问相同次数的页面,从而保证服务器所有的查询都是不能区分的[81].
尽管不同的PIR方法具有不同的通信代价和计算量,但对基于隐私信息检索的位置大数据隐私保护方法来说,通过PIR访问服务器端数据的方法都是通过提供一个数据块编号的方法向服务器安全地获取这个数据块的内容.
5.
2基于隐私信息检索方法保护位置大数据隐私的框架将隐私信息检索方法应用到位置大数据隐私保护上时,其流程如图5所示.
用户在本地进行计算,计算所需的数据使用PIR方法向服务器端获取,于是,服务器不知道用户的位置数据就给出了用户查询结果,这是实现完美隐私的基础.
但是仅仅保护每一次获取数据时的隐私,不能保证用户完全的隐私.
用户的一个查询通常需要多次访问才能获得查询结果,比如导航应用中,不同的起始点和目的地需要的PIR访问次数也不相同.
由于用户不同的位置会导致一个查询中不同的PIR访问次数,攻击者可以对用户的当前位置进行推测[82].
因此,基于PIR的方法需要通过访问一些无用的数据块让用户在不同位置提交的查询都具有相同的PIR的访问次数,以避免攻击者的推测.
然而,PIR方法每次不泄露信息的访问带来性能上很大的开销,为了避免这些性能上的开销,有些工作通过对原始数据进行预处理来加速服务的访问.
Fig.
5IllustrationforworkflowofPIRbasedprivacypreservationoflocationbasedbigdata图5使用PIR方法实现位置大数据的隐私保护流程示意图根据用户不同的查询目的,当前,基于PIR的方法主要针对两类被广泛应用的查询:最短路径计算以及近邻查询.
5.
3最短路径计算中基于PIR的方法最短路径的计算,是众多位置大数据上的应用服务需要使用的技术.
在最短路径的计算中,用户需要提供自己当前的位置,这存在暴露位置隐私的风险.
基于PIR的方法既可以保护用户的位置隐私,还可以保证得到正确的结果.
最短路径的计算基于Dijkstra算法[83]或A*搜索算法[84],PIR提供的访问接口可以看作实现了完美隐私的对传统存储介质(内存或磁盘)的访问.
用户使用任何已有的最短路径计算方法将其中访问存储的接口改为使用PIR的访问接口,就可以获得正确的结果.
但是,由于不同的起点和终点对(S,T)在计算最短路径时需要的访问次数不同,比如距离较近的起点终点对需要的PIR访问次数较少,而距离较远的需要访问的次数较多,为了避免不同起点和终点对之间PIR访问次数不同导致的位置隐私泄露,使用PIR方法的查询计划需要保证每次请求相同次数的PIR访问请求.
包含位置信息的查询请求移动用户包含查询结果的数据多轮交互对某数据块的PIR请求对某数据块PIR请求的回应位置服务提供商.
.
.
704JournalofSoftware软件学报Vol.
25,No.
4,April2014一种平凡的保护隐私的方法是:针对任何一个起点、终点对(S,T),服务器都预计算并保存S到T的最短距离,当用户请求S到T的最短距离时,可以只进行一轮访问一个存储位置S*Max+T(其中,Max是任何点编号中的最大值)的PIR请求,就可以完成最短路径的计算.
但这种方法要求用户发起查询的位置是静态的,为了服务大数据时代任何位置的用户,文献[82]将平凡的保护方法中预计算的粒度由点扩大到区域.
空间被划分成若干区域,如图6所示,路网被划分成了8个不同的区域.
每个起点、终点对之间的最短距离由它们所在区域间所有最短路径经过的区域来表示.
其中,区域R1与区域R7之间的最短路径经过的区域由S1,7表示.
在图6中,R1和R7之间只有两条最短路径,分别用实线折线和虚线折线表示,即S1,7={R3,R4}.
用户在请求R1中的点与R7中的点的最短路径时,使用PIR接口获取R3和R4的数据,结合同样使用PIR接口获得的R1和R7中包含的数据,在本地构建出包含所求最短路径的子图,通过运行已有的最短路径计算方法得到查询结果.
由于不同的Si,j具有不同的集合大小,为了对任何查询都使用相同次数的PIR访问磁盘块,所有Si,j的大小都等于Si,j中最大的.
Fig.
6IllustrationforPIRbasedshortestpathcalculation图6利用PIR计算最短路径示意图5.
4近邻查询中基于PIR的方法用户除了查询自己与目的地之间的最短路径以外,还会查询自己周围有哪些物体,近邻查询同样具有最短路径计算中的隐私问题.
现有的工作逐渐解决了保证完美隐私的最近邻查询问题[85]和k最近邻查询问题[81,86].
最近邻的查询问题分为近似最近邻的寻找和精确最近邻的寻找.
近似最近邻用于那些需要实时查询自己周围有哪些物体的用户,但并不保证获取的位置一定是用户请求位置的最近邻.
图7(a)是近似最近邻查询的一个示意图,服务器为每个数据点用希尔伯特曲线进行降维,比如,A(B,C)的希尔伯特值分别为3(2,0),在查询某个点的近似最近邻时,只需要向服务器查询与要查询点的希尔伯特值最接近的希尔伯特值对应的空间位置.
比如,A点的近似最近邻是B点,因为B的希尔伯特值为2,与A的希尔伯特值3最接近.
服务器将各空间点的希尔伯特值组织成一棵B树,由于B树是平衡的,查询与任何点最接近的希尔伯特值就可以通过相同次数的PIR访问来完成.
因此,攻击者区分用户的不同查询,进而无法推测用户的位置隐私.
对于那些需要准确结果的用户,服务器将空间按照网格的方式划分成若干区域,用户保存这个划分结果,对于某个空间点的k近邻查询,用户首先在网格中定位该空间点,然后寻找近似最近邻,以这两个点之间的距离为半径、以待查询的空间点为圆心画圆,圆形与网格重叠的格子里一定包含最近邻[81].
此外,为了进一步降低PIR的访问次数,服务器为空间中的点计算维诺图[87],每个位置点都存在于一个多边形区域中,每个网格区域与若干包含位置点的多边形区域重叠,如图7(b)所示.
根据维诺图的定义,每一个多边形区域只包含一个位置点,若某个要查询最近邻的位置被包含于某个多边形区域,这个点的最近邻一定是这个多边形区域对应的那个位置点.
每一个空间划分后的网格区域都记录与其有重叠的多边形区域,其中每个网格区域最多与Pmax个多边形区域产生重叠,Pmax在预计算过程中确定.
比如在图7(b)中,A所在的网格区域只包含一个维诺区域,而图7(b)中第4行第3列的网格区域则包含3个维诺区域,因此Pmax=3.
这样,当最近邻查询请求到来时,首先通过一次PIR访问获得查询点所在的区域,然后使用Pmax次PIR访问获得所有可能的最近邻.
这样,任何精确最近邻查询都使用Pmax+1次PIR访问获得查询结果,没有泄露用户的任何隐私.
一般的k近邻查询也被众多服务请求,比如,根据位置进行附近商家的推荐.
文献[81,86]分别通过寻找距离查询点最近的k个希尔伯特值对应的空间点,以这些空间点中与查询点的最远距离为半径、以查询点为圆心画圆,圆圈与网格区域相交的部分一定包含了查询点的k近邻.
R1R8R7R6R5R4R3R2王璐等:位置大数据隐私保护研究综述705(a)(b)Fig.
7IllustrationforPIRbasedknearestneighborcalculation图7利用PIR计算近邻示意图从PIR方法的两个不同类型的应用可以看出,PIR方法的关键在于查询计划如何使不同位置的查询不可区分.
概括来说,现有方法使用空间划分和预计算的方式为不同的位置确定PIR接口需要访问次数的上限,对于无需访问这么多位置的查询,则提交相应数量的无用查询.
6总结位置大数据隐私保护技术具有广泛的应用,是近年来学术界新兴的研究方向.
本文对位置大数据隐私保护研究现状进行了综述.
本文介绍了位置大数据的概念以及位置大数据的隐私威胁,总结了针对位置大数据隐私的统一的基于度量的攻击模型,并以此为依据,对目前位置大数据隐私保护领域已有的研究成果进行了归纳,介绍了基于启发式隐私度量、概率推测以及隐私信息检索(PIR)的3大类隐私保护技术,特别是对当前位置大数据隐私保护的研究前沿问题"基于隐私信息检索的位置大数据隐私保护技术"进行了比较详尽的阐述与分析.
容易看出,每类位置大数据隐私保护技术都有不同的特点,针对不同的应用需求,我们将各种隐私保护技术的分析比较结果列在表1中,从表1中可以看出,它们的适用范围、性能表现等不尽相同.
当对位置数据的隐私程度要求较高且对计算开销要求较高时,基于概率推测的位置大数据隐私保护技术更适合;当关注位置信息的完美隐私保护时,则应考虑基于隐私信息检索的位置大数据隐私保护技术,这时,计算量以及响应时间上的代价较高.
基于启发式隐私度量的位置大数据隐私保护技术能以较低的计算开销实现对一般隐私需求的保护,表2对位置大数据隐私保护技术作了进一步的对比分析.
Table1Performanceevaluationforprivacypreservationoflocationbasedbigdata表1位置大数据的隐私保护技术性能评估隐私保护度运行时开销预计算开销数据缺失基于启发式隐私度量的位置大数据隐私保护技术中中低中基于概率推测的位置大数据隐私保护技术中高低高中基于隐私信息检索的位置大数据隐私保护技术高高高低Table2Comparisonandanalysisforprivacypreservationoflocationbasedbigdata表2位置大数据的隐私保护技术对比分析主要优点主要缺点代表技术基于启发式隐私度量的位置大数据隐私保护技术计算开销中等,实现简单位置解析度失真,会受到基于数据特征推测的攻击k匿名技术[62]匿名框技术[47,48]考虑数据特征的方法[49]基于概率推测的位置大数据隐私保护技术计算开销小,位置发布准确数据缺失,服务可用性降低,预计算开销大,依赖于位置数据模型,不同的模型需设计不同的算法基于隐马尔可夫模型[71,74]基于图模型[75]基于隐私信息检索的位置大数据隐私保护技术完全隐私保护,服务可用性高预计算代价大,运行时代价大,需要针对应用设计优化方法针对最短路径[82]针对最近邻[85,88]针对k近邻[86,88]BCA0321BCADU706JournalofSoftware软件学报Vol.
25,No.
4,April20147未来展望在大数据时代,获取信息的渠道越来越多,获取到的位置信息也越来越多样化,类型也不限于第2节中介绍的单一的位置数据.
下面从位置数据与非位置数据相结合、移动社交网络以及背景知识攻击这3个方面介绍未来的位置大数据的隐私保护技术.
7.
1位置数据与非位置数据结合的位置大数据的隐私保护技术大数据时代,攻击者可以从多种渠道获得用户和位置数据相关的其他类型数据,并结合位置数据共同推测用户的隐私信息.
此时,位置数据与非位置数据之间使用用户的个性或者行为模式进行匹配,成为联系位置数据与非位置数据的通用方法.
位置数据与非位置数据相结合的位置大数据隐私可以如下定义[20]:设P={p1,…,pn}为从某个角度对用户个性的度量,比如,P可以是从对商品喜好角度对用户个性的度量,这时,pi表示一个用户对编号为i的物品的喜好程度.
同时,L={l1,…,lm}为攻击者收集的用户的位置数据,考虑一个偏好函数F将某个用户的L映射为对用户个性的度量P.
如果攻击者可以收集到相同角度度量用户个性的数据X={x1,…,xn},其中,这个例子中xi表示某个用户对编号为i的商品的喜好程度.
这种攻击方式一样可以纳入第1节中介绍的位置大数据的统一攻击模型.
用tiU′表示某个用户i在t′时刻的位置数据与xi匹配成功,用tiL表示用户i到t时刻为止发布的位置数据,在任一时刻t,为了避免攻击者获得用户位置信息后推测用户的敏感信息(比如身份),与第1节中针对单一位置数据类型的攻击模型一样,位置数据与非位置数据相结合的位置大数据隐私一样可以类似定义1来定义:tttiiiPULPUθ′′≤其中,先验概率与后验概率的计算除了第1节中提到的与攻击者收集到的用户的历史数据有关外,还与由用户的位置信息映射成的个性向量与用户的位置信息构成的个性向量之间的匹配难度有关.
根据文献[89]提出的基于信息论的匹配方法,匹配成功的难度取决于攻击者收集到不同用户的位置数据的差异性,可以由以下公式定义:dmin=minpi,pj∈P|{k|pi,k!
=pj,k,k∈(1,|pi|)}|,其中,dmin表示任意不同用户的位置数据映射到用户个性向量pi和pj不同的元素个数的最小值,它代表了最接近的两个向量的差异程度.
显然,dmin较大时,不同的用户之间很好区分;而当dmin较少时,区分就会变得困难甚至不可能.
根据以上介绍,位置数据与非位置数据相结合后进行隐私保护的研究还有许多重要问题需要解决.
在大数据时代,含有多种类型的位置大数据包含了用户的行为模式信息,它们会导致用户位置大数据隐私的泄露.
例如,超市的购物数据包含了用户对各种商品的喜好,攻击者可以根据这些喜好匹配一些明显的行为模式.
文献[20]借鉴Narayanan等人将NetFlix发布的匿名数据集[90]通过与购物数据相关联进行反匿名化的方法,提出了将用户的位置数据集合{Li:Li=[l1,…,ln]},其中,lj代表匿名用户i在时刻j的位置映射为该用户对各种商品的喜好程度P={p1,…,pn}(其中,pi表示该用户对编号为i的商品的喜好程度),并结合使用由商场购物信息得到的用户的偏好向量集合{Xi:Xi=[x1,…,xn]}来确定每个匿名用户与商场购物信息中的用户的匹配程度,其中,xij表示用户i对商品j的偏好程度.
为了进行匹配,计算每个用户经过位置数据映射后的个性向量与攻击者收集到的不同用户的个性向量之间的差异度.
差异度最小的匿名用户数据与商场购物数据匹配成功.
如果若干匿名用户的个性向量之间差异不可区分,则匹配失败.
为了保护位置数据与非位置数据结合后位置大数据的隐私,我们认为,位置大数据隐私保护方法的设计者应研究用户位置与行为模式之间的映射关系,以设法降低攻击者根据从匿名用户位置推测出的个性向量与攻击者收集到的不同用户之间的个性向量的匹配程度.
我们认为,这与以下两个因素有关:(1)匿名用户的位置数据增多后,其映射成的偏好程度向量会变得准确;反之,偏好程度向量会变得模糊;(2)匿名用户偏好程度的向量变得准确,有利于与攻击者收集到的个性向量进行匹配,且映射后不可区分的个性向量会变少;反之,不可区分的匿名数据数量会增多.
王璐等:位置大数据隐私保护研究综述707因此,我们认为保护用户的位置大数据隐私的关键是:在确保服务可用的前提下,尽量让映射后的个性向量变得模糊.
这可以从两个方面入手:(1)减少用户发布的位置数据的数量,这相当于减少了映射后的个性向量的信息量,因此映射出的个性向量应更模糊;(2)降低用户的位置数据中的元素映射成有效个性向量中元素的能力.
但是,针对不同应用的特点,如何在减少位置数据规模的同时保持基于位置服务的准确性,是一个具有挑战性的问题.
7.
2移动社交网络中位置大数据的隐私第7.
1节中介绍的领域相关的映射方法将位置数据与非位置数据关联,不同的领域需要相应的领域专家设计各自的映射方法.
大数据时代的新应用移动社交网络,为位置数据与文本、图片和用户个人信息进行了自然的结合,为攻击者和隐私保护者提供了新问题.
在移动社交网络中,用户的位置信息与用户的身份信息显式地结合,比如在移动社交网络的签到服务中,用户使用带有定位功能的移动设备将自己的位置和自己的标识发布在社交网络中.
移动社交网络上,位置大数据的隐私保护问题是前面提到的位置数据与非位置数据结合的位置大数据隐私问题的特例,因此,其上的隐私同样可以使用统一的θ隐私来度量.
当前,移动社交网络上位置大数据的隐私保护的研究还处于初级阶段,当前的保护手段主要是通过对数据进行隐私等级的分类,然后使用访问控制策略防止攻击者访问敏感位置数据[91].
此外,最新的研究试图将单一位置大数据隐私保护方法应用到移动社交网络中,提出了k匿名的轨迹隐私保护方法[92]以及概率推测的方法[93].
这些方法的提出顺序与单一位置数据进行保护的方法的发展过程类似,从使用访问控制策略的方法到对单点的位置保护,逐渐发展到对历史位置数据的保护.
其采用的技术大多是已有方法的变种,但由于研究时间短,还有大量针对单一位置数据的位置大数据的隐私保护方法没有在移动社交网络中得到应用.
我们认为,针对移动社交网络的位置大数据的隐私保护技术是未来位置大数据的隐私保护技术的重要组成部分,考虑移动社交网络中用户相关的位置数据与非位置数据之间的关系,并防止攻击者利用该关系推测用户的敏感信息,是未来位置大数据的隐私保护技术的研究方向.
7.
3针对背景知识的位置大数据隐私保护技术现有的基于概率推测的位置大数据隐私保护技术假设攻击者对用户的背景知识的掌握是固定的,但在大数据时代,攻击者可以持续地收集用户的历史数据从而具备学习用户的背景知识的能力.
这时,现有的基于概率推测的位置大数据隐私保护技术不能有效地保护用户的位置隐私[71].
差分隐私是迄今为止针对攻击者的先验知识进行普遍保护的最有效的技术,尽管目前差分隐私主要针对离线数据,不能直接应用于位置大数据的隐私保护,但我们认为,将差分隐私保护技术应用到位置大数据隐私保护技术中,是未来有潜力的研究方向.
差分隐私同样遵循定义1中位置大数据的攻击模型:如果Lt是攻击者收集到t时刻之前的历史位置数据,tiU′表示用户在t′时刻处于敏感位置Si,按照差分隐私的定义[94],如果{},|e}/{ttiitPUPULε′′≤那么当前位置数据满足差分隐私条件可以被发布;否则,不能直接发布或需要经过某种变换机制才能进行发布.
注意到,只要令ε=log(θ),差分隐私即满足定义1中位置大数据的隐私中的θ隐私.
当前,差分隐私的研究主要集中在如何添加假数据干扰分析结果,主要的技术包括针对数据类型是整数的Laplace机制[95]、针对数据类型是浮点数的exponential机制[96]以及它们在性能上的改进geometric机制[97].
差分隐私在数据分析上的应用很多,但还没有针对位置大数据的研究.
尽管目前为止差分隐私的研究已经涉及到与位置数据有关的特定多维索引四叉树,但我们认为,还没有提出能够满足位置大数据的隐私保护技术.
由于差分隐私对于攻击者背景知识的假设十分保守,同时,大数据时代攻击者获取背景知识的渠道和途径十分广泛,我们认为,将差分隐私保护技术应用到位置大数据隐私保护中是具有广阔前景的研究方向.
8结束语大数据时代用户的位置数据会从不同的视角和渠道被收集.
位置大数据在给人们的生活、商业运作方式以及科学研究带来巨大收益的同时,由于其中蕴含了人们的行为模式、习惯偏好和敏感信息等隐私信息,为人们708JournalofSoftware软件学报Vol.
25,No.
4,April2014带来了严重的隐私威胁.
由于经典的基于"知情与同意"以及匿名的位置隐私保护方法不能全面地保护用户的位置隐私,目前的研究者已在位置大数据的隐私保护方面做了大量的工作.
本文对位置大数据隐私保护技术的研究成果进行了回顾和总结,综述了位置大数据隐私保护技术研究的现状,总结位置大数据隐私统一的基于度量的攻击模型,并以此为依据,分析和对比了基于启发式隐私度量、概率推测和隐私信息检索的位置大数据隐私保护方法,指出各种方法适宜的情况和特点.
最后,对未来位置数据与非位置数据相结合等位置大数据的隐私保护研究方向进行了探讨.
总之,位置大数据隐私保护技术属于大数据带来的新兴研究领域,仍然有大量关键问题需要深入而细致的研究.
致谢在此,我们向对本文的工作给予支持和建议的同行表示感谢.
References:[1]JabeurN,ZeadallyS,SayedB.
Mobilesocialnetworkingapplications.
CommunicationsoftheACM,2013,56(3):7179.
[doi:10.
1145/2428556.
2428573][2]SousaM,TechmerA,SteinhageA,LauterbachC,LukowiczP.
Humantrackingandidentificationusingasensitivefloorandwearableaccelerometers.
In:Proc.
oftheIEEEInt'lConf.
onPervasiveComputingandCommunications(PerCom).
SanDiego,2013.
166171.
[doi:10.
1109/PerCom.
2013.
6526728][3]UgolottiR,SassiF,MordoniniM,CagnoniS.
Multi-Sensorsystemfordetectionandclassificationofhumanactivities.
JournalofAmbientIntelligenceandHumanizedComputing,2013,4(1):2741.
[doi:10.
1007/s12652-011-0065-z][4]AnguelovD,DulongC,FilipD,FruehC,LafonS,LyonR,OgaleA,VincentL,WeaverJ.
Googlestreetview:Capturingtheworldatstreetlevel.
Computer,2010,43(6):3238.
[doi:10.
1109/MC.
2010.
170][5]CivilisA,JensenCS,PakalnisS.
Techniquesforefficientroad-network-basedtrackingofmovingobjects.
IEEETrans.
onKnowledgeandDataEngineering,2005,17(5):698712.
[doi:10.
1109/TKDE.
2005.
80][6]Mayer-SchnbergerV,CukierK.
BigData:ARevolutionthatWillTransformhowWeLive,Work,andThink.
EamonDolan/HoughtonMifflinHarcourt,2013.
102105.
[7]DijcksJP.
Oracle:BigDatafortheEnterprise.
WhitePaper.
Oracle,2012.
[8]ZhengK,ShangS,YuanNJ,YangY.
Towardsefficientsearchforactivitytrajectories.
In:Proc.
ofthe29thIEEEInt'lConf.
onDataEngineering(ICDE2013).
Brisbane,2013.
230241.
[doi:10.
1109/ICDE.
2013.
6544828][9]AbowdG,AtkesonC,HongJ,LongS,KooperR,PinkertonM.
CyberGuide:Amobilecontext-awaretourguide.
WirelessNetworks,1997,3(5):42143.
[doi:10.
1023/A:1019194325861][10]NextBusInc.
2004.
http://www.
nextbus.
com/[11]SmithCW,etal.
Systemandmethodforprovidingtrafficinformationusingoperationaldataofawirelessnetwork.
CI:G08G1/01.
USPat10/243,589,2002.
[12]SythoffJ,MorrisonJ.
Location-Basedservices.
2011.
http://www.
pyramidresearch.
com/store/Report-Location-Based-Services.
htm[13]LitmanT.
Distance-Basedvehicleinsurance:Feasibility,costsandbenefits.
ComprehensiveTechnicalReport,VictoriaTransportPolicyInstitute,2011.
[14]BacheldorB.
UPSslashedthetimeittakestodeterminetheleast-expensiveroutefrommonthstodaystohoursandwantstomakethatinformationavailableinrealtime.
2004.
http://www.
informationweek.
com/breakthrough/d/d-id/1023066[15]HillS,BanserA,BerhanG,EagleN.
RealityminingAfrica.
In:Proc.
oftheAAAISpringSymp.
onArtificialIntelligenceforDevelopment.
2010.
http://ai-d.
org/pdfs/Hill.
pdf[16]ChiHB.
Threecircleatthreelocation:Weibocanlocate.
2013.
http://www.
fawan.
com.
cn/html/2013-07/03/content_442649.
htm[17]WilliamsC.
Appleunderpressureoveriphonelocationtracking.
2011.
http://www.
telegraph.
co.
uk/technology/apple/8466357/Apple-underpressureover-iPhone-location-tracking.
html[18]ChengJ.
Howappletracksyourlocationwithoutyourconsentandwhyitmatters.
2011.
http://arstechnica.
com/apple/news/2011/04/how-appletracks-your-location-without-your-consent-and-why-it-matters.
ars王璐等:位置大数据隐私保护研究综述709[19]HansellS.
AOLremovessearchdataonvastgroupofWebusers.
2006.
http://query.
nytimes.
com/gst/fullpage.
htmlres=9504E5D81E3FF93BA3575BC0A9609C8B63[20]WickerSB.
Thelossoflocationprivacyinthecellularage.
CommunicationsoftheACM,2012,55(8):6068.
[doi:10.
1145/2240236.
2240255][21]NarayananA,ShmatikovV.
Robustde-anonymizationoflargesparsedatasets.
In:Proc.
oftheIEEESymp.
onSecurityandPrivacy.
Oakland,2008.
111125.
[doi:10.
1109/SP.
2008.
33][22]BeresfordAR,RiceA,SkehinN,SohanR.
MockDroid:Tradingprivacyforapplicationfunctionalityonsmartphones.
In:Proc.
ofthe12thWorkshoponMobileComputingSystemsandApplications.
ACMPress,2011.
4954.
[doi:10.
1145/2184489.
2184500][23]BeresfordAR,StajanoF.
Locationprivacyinpervasivecomputing.
PervasiveComputing,IEEE,2003,2(1):4655.
[doi:10.
1109/MPRV.
2003.
1186725][24]AgrawalD,BernsteinP,BertinoE,DavidsonS,DayalU,FranklinM,GehrkeJ,HaasL,HalevyA,HanJ,JagadishHV,LabrinidisA,MaddenS,PapakonstantinouY,PatelJM,RamakrishnanR,RossK,ShahabiC,SuciuD,VaithyanathanS,WidomJ.
Challengesandopportunitieswithbigdata—AcommunitywhitepaperdevelopedbyleadingresearchersacrosstheUnitedStates.
2012.
http://cra.
org/ccc/docs/init/bigdatawhitepaper.
pdf[25]TsaiJ,KelleyP,CranorL,SadehN.
Location-Sharingtechnologies:Privacyrisksandcontrols.
2009.
http://papers.
ssrn.
com/sol3/papers.
cfmabstract_id=1997782[26]SadehN.
M-Commerce:Technologies,Services,andBusinessModel.
Wiley,2002.
[27]GlassJ.
Shyhoodislocation.
2014.
http://www.
skyhookwireless.
com/[28]KimM,FieldingJJ,KotzD.
RisksofusingAPlocationsdiscoveredthroughwardriving.
PervasiveComputing,2006,3968:6782.
[doi:10.
1007/11748625_5][29]FrommerD.
Looptlocationtoupdateinthebackgroundoniphone.
2009.
http://www.
businessinsider.
com/loopt-to-run-in-the-background-on-iphone-2009-6[30]RobertsP,ChallinorS.
IPaddressmanagement.
BTTechnologyJournal,2000,18(3):127136.
[doi:10.
1023/A:1026749131441][31]Loki.
http://loki.
com/[32]FireEagle.
http://info.
yahoo.
com/privacy/us/yahoo/fireeagle/[33]Googlelatitude.
http://www.
google.
com/latitude/apps/badge[34]ZhouSG,LiF,TaoYF,XiaoXK.
Privacypreservationindatabaseapplications:Asurvey.
ChineseJournalofComputers,2009,32(5):847861(inChinesewithEnglishabstract).
[doi:10.
3724/SP.
J.
1016.
2009.
00847][35]FitzpatrickM.
Mobilethatallowsbossestosnooponstaffdeveloped.
BBCNews.
2010.
http://news.
bbc.
co.
uk/2/hi/technology/8559683.
stm[36]DeckerM.
Locationprivacy—Anoverview.
In:Proc.
ofthe7thInt'lConf.
onMobileBusiness.
Barcelona,2008.
221230.
[doi:10.
1109/ICMB.
2008.
14][37]NgaiECH,RodheI.
Onprovidinglocationprivacyformobilesinksinwirelesssensornetworks.
WirelessNetworks,2013,19(1):115130.
[doi:10.
1007/s11276-012-0454-z][38]WernkeM,SkvortsovP,DürrF,RothermelK.
Aclassificationoflocationprivacyattacksandapproaches.
PersonalandUbiquitousComputing,2014,18(1):163175.
[doi:10.
1007/s00779-012-0633-z][39]BonchiF.
Privacypreservingpublicationofmovingobjectdata.
In:BettiniC,etal.
,eds.
Proc.
ofthePrivacyinLocation-BasedApplications.
Berlin,Heidelberg:Springer-Verlag,2009.
190215.
[doi:10.
1007/978-3-642-03511-1_9][40]FungB,CaoM,DesaiBC,XuH.
PrivacyprotectionforRFIDdata.
In:Proc.
ofthe2009ACMSymp.
onAppliedComputing.
Honolulu,2009.
15281535.
[doi:10.
1145/1529282.
1529626][41]BertinoE,CataniaB,DamianiML,PerlascaP.
Geo-RBAC:AspatiallyawareRBAC.
In:Proc.
ofthe10thACMSymp.
onAccessControlModelsandTechnologies.
Stockholm,2005.
2937.
[doi:10.
1145/1063979.
1063985][42]GunterCA,MayMJ,StubblebineSG.
Aformalprivacysystemanditsapplicationtolocationbasedservices.
In:Proc.
ofthe4thInt'lWorkshoponPrivacyEnhancingTechnologies.
Toronto,2004.
256282.
[doi:10.
1007/11423409_17][43]MylesG,FridayA,DaviesN.
Preservingprivacyinenvironmentswithlocation-basedapplications.
PervasiveComputing,2003,2(1):5664.
[doi:10.
1109/MPRV.
2003.
1186726]710JournalofSoftware软件学报Vol.
25,No.
4,April2014[44]SnekkenesE.
Conceptsforpersonallocationprivacypolicies.
In:Proc.
ofthe3rdACMConf.
onElectronicCommerce.
Tampa,2001.
4857.
[doi:10.
1145/501158.
501164][45]YiuML,JensenCS,MllerJ,LuH.
Designandanalysisofarankingapproachtoprivatelocation-basedservices.
ACMTrans.
onDatabaseSystems(TODS),2011,36(2):10.
[doi:10.
1145/1966385.
1966388][46]GruteserM,GrunwaldD.
Anonymoususageoflocation-basedservicesthroughspatialandtemporalcloaking.
In:Proc.
ofthe1stInt'lConf.
onMobileSystem,Application,andServices.
SanFrancisco,2003.
3142.
[doi:10.
1145/1066116.
1189037][47]MokbelMF,ChowCY,ArefWG.
ThenewCasper:Queryprocessingforlocationserviceswithoutcompromisingprivacy.
In:DayalU,ed.
Proc.
ofthe32ndInt'lConf.
onVeryLargeDataBases.
NewYork:ACMPress,2006.
763774.
[48]GedikB,LiuL.
Protectinglocationprivacywithpersonalizedk-anonymity:Architectureandalgorithms.
IEEETrans.
onMobileComputing,2008,7(1):118.
[doi:10.
1109/TMC.
2007.
1062][49]PanX,XuJ,MengX.
Protectinglocationprivacyagainstlocation-dependentattacksinmobileservices.
IEEETrans.
onKnowledgeandDataEngineering,2012,24(8):15061519.
[doi:10.
1109/TKDE.
2011.
105][50]XuT,CaiY.
Exploringhistoricallocationdataforanonymitypreservationinlocation-basedservices.
In:Proc.
ofthe27thIEEEInt'lConf.
onComputerCommunications.
Phoenix,2008.
547555.
[doi:10.
1109/INFOCOM.
2008.
103][51]ChowCY,MokbelMF.
Trajectoryprivacyinlocation-basedservicesanddatapublication.
ACMSIGKDDExplorationsNewsletter,2011,13(1):1929.
[doi:10.
1145/2031331.
2031335][52]NergizME,AtzoriM,SayginY.
Towardstrajectoryanonymization:Ageneralization-basedapproach.
In:Proc.
oftheSIGSPATIALACMGIS2008Int'lWorkshoponSecurityandPrivacyinGISandLBS.
Irvine,2008.
5261.
[doi:10.
1145/1503402.
1503413][53]MachanavajjhalaA,ReiterJP.
Bigprivacy:Protectingconfidentialityinbigdata.
XRDS:Crossroads.
TheACMMagazineforStudents,2012,19(1):2023.
[doi:10.
1145/2331042.
2331051][54]HuoZ,MengXF.
Asurveyoftrajectoryprivacy-preservingtechniques.
ChineseJournalofComputers,2011,34(10):18201830(inChinesewithEnglishabstract).
[doi:10.
3724/SP.
J.
1016.
2011.
01820][55]LiuF,HuaKA,CaiY.
Queryl-diversityinlocation-basedservices.
In:Proc.
ofthe10thInt'lConf.
onMobileDataManagement.
Taipei,2009.
436442.
[doi:10.
1109/MDM.
2009.
72][56]BambaB,LiuL,PestiP,WangT.
Supportinganonymouslocationqueriesinmobileenvironmentswithprivacygrid.
In:HuaiJ,ed.
Proc.
ofthe17thInt'lConf.
onWorldWideWeb.
NewYork:ACMPress,2008.
237246.
[57]ChenJ,XuH,ZhuL.
InternetofThings.
Berlin,Heidelberg:Springer-Verlag,2012.
157165.
[58]LiuL.
Fromdataprivacytolocationprivacy:Modelsandalgorithms.
In:KochC,ed.
Proc.
ofthe33rdInt'lConf.
onVeryLargeDataBases.
NewYork:ACMPress,2007.
14291430.
[59]GentryC.
Afullyhomomorphicencryptionscheme[Ph.
D.
Thesis].
Stanford:StanfordUniversity,2009.
[60]LiFF,XiaoXK.
Securenearestneighborrevisited.
In:Proc.
ofthe29thIEEEInt'lConf.
onDataEngineering.
Brisbane,2013.
733744.
[doi:10.
1109/ICDE.
2013.
6544870][61]XuJ,TangX,HuH,DuJ.
Privacy-Consciouslocation-basedqueriesinmobileenvironments.
IEEETrans.
onParallelandDistributedSystems,2010,21(3):313326.
[doi:10.
1109/TPDS.
2009.
65][62]GedikB,LiuL.
Acustomizablek-anonymitymodelforprotectinglocationprivacy.
TechnicalReport,GeorgiaInstituteofTechnology,2004.
https://smartech.
gatech.
edu/bitstream/handle/1853/100/git-cercs-04-15.
pdf;jsessionid=FC0FA9422D52E947651B4E565E690BE1.
smart1sequence=1[63]KidoH,YanagisawaY,SatohT.
Protectionoflocationprivacyusingdummiesforlocation-basedservices.
In:Proc.
ofthe21stInt'lConf.
onDataEngineering.
Tokyo,2005.
12481248.
[doi:10.
1109/ICDE.
2005.
269][64]SuzukiA,IwataM,AraseY,HaraT,XieX,NishioS.
Auserlocationanonymizationmethodforlocationbasedservicesinarealenvironment.
In:Proc.
ofthe18thACMSIGSPATIALInt'lSymp.
onAdvancesinGeographicInformationSystems.
SanaJose,2010.
398401.
[doi:10.
1145/1869790.
1869846][65]KatoR,IwataM,HaraT,SuzukiA,AraseY,XieX,NishioS.
Adummy-basedanonymizationmethodbasedonusertrajectorywithpauses.
In:Proc.
ofthe20thACMSIGSPATIALInt'lConf.
onAdvancesinGeographicInformationSystems.
Redondo,2012.
249258.
[doi:10.
1145/2424321.
2424354]王璐等:位置大数据隐私保护研究综述711[66]YigitogluE,DamianiML,AbulO,SilvestriC.
Privacy-Preservingsharingofsensitivesemanticlocationsunderroad-networkconstraints.
In:Proc.
ofthe13thIEEEInt'lConf.
onMobileDataManagement(MDM).
Bengaluru,2012.
186195.
[doi:10.
1109/MDM.
2012.
48][67]PalanisamyB,LiuL.
Mobimix:Protectinglocationprivacywithmix-zonesoverroadnetworks.
In:Proc.
ofthe27thInt'lConf.
onDataEngineering(ICDE).
Hannover,2011.
494505.
[doi:10.
1109/ICDE.
2011.
5767898][68]EddySR.
HiddenMarkovmodels.
CurrentOpinioninStructuralBiology,1996,6(3):361365.
[doi:10.
1016/S0959-440X(96)80056-X][69]LaffertyJ,McCallumA,PereiraFCN.
Conditionalrandomfields:Probabilisticmodelsforsegmentingandlabelingsequencedata.
In:BrodleyCE,ed.
Proc.
ofthe18thInt'lConf.
onMachineLearning.
SanFrancisco:MorganKaufmannPublishers,2001.
282289.
[70]KimE,HelalS,CookD.
Humanactivityrecognitionandpatterndiscovery.
PervasiveComputing,2010,9(1):4853.
[doi:10.
1109/MPRV.
2010.
7][71]GtzM,NathS,GehrkeJ.
MaskIt:Privatelyreleasingusercontextstreamsforpersonalizedmobileapplications.
In:Proc.
ofthe2012ACMSIGMODInt'lConf.
onManagementofData.
Scottsdale,2012.
289300.
[doi:10.
1145/2213836.
2213870][72]ManniniA,SabatiniAM.
Accelerometry-BasedclassificationofhumanactivitiesusingMarkovmodeling.
ComputationalIntelligenceandNeuroscience,2011,15(11):110.
[doi:10.
1155/2011/647858][73]ArasuA,GtzM,KaushikR.
Onactivelearningofrecordmatchingpackages.
In:Proc.
ofthe2010ACMSIGMODInt'lConf.
onManagementofData.
Indianapolis,2010.
783794.
[doi:10.
1145/1807167.
1807252][74]GoetzM,NathS,GehrkeJ.
MaskIt:Privatelyreleasingusercontextstreamsforpersonalizedmobileapplications.
TechnicalReport,MSR-TR-2012-29,MicrosoftResearch,2012.
[doi:10.
1145/2213836.
2213870][75]ParateA,ChiuMC,GanesanD,MarlinBM.
Leveraginggraphicalmodelstoimproveaccuracyandreduceprivacyrisksofmobilesensing.
In:Proc.
ofthe11thAnnualInt'lConf.
onMobileSystem,Applications,andServices.
Taipei,2013.
8396.
[doi:10.
1145/2462456.
2464457][76]KuenzerA,SchlickC,OhmannF,SchmidtL,LuczakH.
Anempiricalstudyofdynamicbayesiannetworksforusermodeling.
2001.
http://www.
research.
rutgers.
edu/~sofmac/ml4um/mirrors/ml4um-2001/papers/AK.
pdf[77]ChorB,GoldreichO,KushilevitzE,SudanM.
Privateinformationretrieval.
JournaloftheACM,1998,45(6):965981.
[doi:10.
1145/293347.
293350][78]ChorB,GoldreichO,KushilevitzE,SudanM.
Privateinformationretrieval.
In:Proc.
ofthe36thAnnualSymp.
onFoundationsofComputerScience.
Piscataway:IEEE,1995.
4150.
[79]KushilevitzE,OstrovskyR.
Replicationisnotneeded:Singledatabase,computationally-privateinformationretrieval.
In:Proc.
ofthe38thAnnualSymp.
onFoundationsofComputerScience.
MiamiBeach,1997.
364373.
[doi:10.
1109/SFCS.
1997.
646125][80]GoldreichO,GoldwasserS,MicaliS.
Howtoconstructrandomfunctions.
JournaloftheACM,1986,33(4):792807.
[doi:10.
1145/6490.
6503][81]GoldreichO,OstrovskyR.
SoftwareprotectionandsimulationonobliviousRAMs.
JournaloftheACM,1996,43(3):431473.
[doi:10.
1145/233551.
233553][82]MouratidisK,YiuML.
Shortestpathcomputationwithnoinformationleakage.
Proc.
oftheVLDBEndowment,2012,5(8):692703.
[83]DijkstraEW.
Anoteontwoproblemsinconnexionwithgraphs.
NumerischeMathematik,1959,1(1):269271.
[doi:10.
1007/BF01386390][84]HartPE,NilssonNJ,RaphaelB.
Aformalbasisfortheheuristicdeterminationofminimumcostpaths.
IEEETrans.
onSystemsScienceandCybernetics,1968,4(2):100107.
[doi:10.
1109/TSSC.
1968.
300136][85]GhinitaG,KalnisP,KhoshgozaranA,ShahabiC,TanKL.
Privatequeriesinlocationbasedservices:Anonymizersarenotnecessary.
In:Proc.
ofthe2008ACMSIGMODInt'lConf.
onManagementofData.
Vancouver,2008.
121132.
[doi:10.
1145/1376616.
1376631][86]PapadopoulosS,BakirasS,PapadiasD.
Nearestneighborsearchwithstronglocationprivacy.
Proc.
oftheVLDBEndowment,2010,3(1-2):619629.
712JournalofSoftware软件学报Vol.
25,No.
4,April2014[87]BergMD,CheongO,KreveldMV,OvermarsM.
ComputationalGeometry.
Berlin,Heidelberg:Springer-Verlag,2008.
147170.
[88]KhoshgozaranA,ShahabiC,Shirani-MehrH.
Locationprivacy:GoingbeyondK-anonymity,cloakingandanonymizers.
KnowledgeandInformationSystems,2011,26(3):435465.
[doi:10.
1007/s10115-010-0286-z][89]ShannonCE.
Communicationtheoryofsecrecysystems.
BellSystemTechnicalJournal,1949,28(4):656715.
[doi:10.
1002/j.
1538-7305.
1949.
tb00928.
x][90]Netflixprizerules.
http://www.
netflixprize.
com//rules[91]ChengY,ParkJ,SandhuR.
Preservinguserprivacyfromthird-partyapplicationsinonlinesocialnetworks.
In:LeslieC,edal.
,eds.
Proc.
ofthe22ndInt'lConf.
onWorldWideWebCompanion.
NewYork:ACMPress,2013.
723728.
[92]HuoZ,MengXF,HuangY.
PrivateCheckIn:Trajectoryprivacy-preservingcheck-inservicesinMSNS.
ChineseJournalofComputers,2013,36(4):716726(inChinesewithEnglishabstract).
[93]HuoZ,MengXF,ZhangR.
Feelfreetocheck-in:PrivacyalertagainsthiddenlocationinferenceattacksinGeoSNs.
In:Proc.
ofthe18thInt'lConf.
onDatabaseSystemsforAdvancedApplications.
Wuhan,2013.
377391.
[doi:10.
1007/978-3-642-37487-6_29][94]YangY,ZhangZ,MiklauG,WinslettM,XiaoXK.
Differentialprivacyindatapublicationandanalysis.
In:Proc.
ofthe2012ACMSIGMODInt'lConf.
onManagementofData.
Scottsdale,2012.
601606.
[doi:10.
1145/2213836.
2213910][95]DworkC.
Differentialprivacy.
In:BugliesiM,ed.
Proc.
oftheAutomata,LanguagesandProgramming.
Berlin,Heidelberg:Springer-Verlag,2006.
112.
[96]McSherryF,TalwarK.
Mechanismdesignviadifferentialprivacy.
In:Proc.
ofthe48thAnnualIEEESymp.
onFoundationsofComputerScience.
Providence,2007.
94103.
[doi:10.
1109/FOCS.
2007.
41][97]GhoshA,RoughgardenT,SundararajanM.
Universallyutility-maximizingprivacymechanisms.
SIAMJournalonComputing,2012,41(6):16731693.
[doi:10.
1137/09076828X]附中文参考文献:[34]周水庚,李丰,陶宇飞,肖小奎.
面向数据库应用的隐私保护研究综述.
计算机学报,2009,32(5):847861.
[54]霍峥,孟小峰.
轨迹隐私保护技术研究.
计算机学报,2011,34(10):18201830.
[92]霍峥,孟小峰,黄毅.
PrivateCheckIn:一种移动社交网络中的轨迹隐私保护方法.
计算机学报,2013,36(4):716726.
王璐(1986-),女,河北邢台人,博士生,主要研究领域为位置隐私保护.
E-mail:luwang@ruc.
edu.
cn孟小峰(1964-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为Web数据管理,移动数据管理,XML数据管理,云数据管理.
E-mail:xfmeng@ruc.
edu.
cn