LBS中位置隐私保护关键技术分析与方案探究

◆邓密文

LBS中位置隐私保护关键技术分析与方案探究

◆邓密文

（四川大学网络空间安全学院，四川成都 610065）

本文对LBS位置隐私保护体系结构类型进行列举，包括独立式、集中式、分布式与混合式四种，并对各自的优缺点进行对比，然后分析LBS位置隐私保护中的关键技术，如伪码法、区域混淆法、假位置干扰法、加密法等，在用户敏感位置选择基础上最后提出生成假位置的位置保护方案，力求在保障用户信息安全的情况下，为用户提供优质的服务，使用户位置隐私得到切实保护。

LBS；位置隐私保护；敏感位置；匿名集

基于位置的服务（LBS）是通过移动运营商的无线电通信网络或外部定位方式对移动终端用户位置信息进行获取，在GIS平台支持下，为用户提供相应服务的增值业务[1]。这项业务可以给用户带来各种各样的便利，但也存在隐私暴露问题，并且隐私暴露已成为风险因素的主要来源。基于此，本文总结了位置隐私保护体系结构的类型，主要对位置隐私保护的关键技术展开分析，并提出位置保护方案，力求在保障服务质量的同时，使用户个人隐私得到保护。

1 LBS位置隐私保护体系结构

1.1 独立式结构

该结构主要包括用户端与LBS服务器两个方面，用户端直接与LBS服务器连接，实现通信，它是最早的位置隐私保护结构。主要保护流程如下：用户通过具有定位功能的移动端获取自身位置，根据实际需求对位置进行匿名保护，再将查询请求传达给LBS服务器，然后LBS服务器会将查询结果集反馈给用户，最后由用户端求精结果集。该结构操作简单，不受第三方的安全限制，其缺陷在于客户端只对自身进行匿名处理，未对周边环境与其他用户位置进行处理，仍然有受到攻击的可能，此外该结构对移动端的硬件存储、处理能力的要求严格。

1.2 集中式结构

该结构是在客户端和LBS服务器之间添加第三方可信匿名服务器，以第三方可信匿名服务器为核心，用户借助移动终端向第三方可信匿名服务器发送查询请求，获取结果反馈的框架。第三方可信匿名服务器包含匿名处理模块，匿名处理模块可对移动终端提出的位置隐匿请求进行处理，使用户的隐私度得到充分保护。经过匿名处理后，第三方可信匿名服务器会把客户端的请求转发给LBS服务器，接着第三方可信匿名服务器中求精模块会把LBS服务器返回的结果集进行求精，最后把求精后的结果传递到移动终端。该结构具有较为良好的服务质量，隐私性好，但缺点在于第三方可信匿名服务器容易成为攻击目标，可能成为系统处理瓶颈，实用性受限。

1.3 分布式结构

该结构主要包括用户组与LBS服务器两个方面，主要特点为：任意移动端均具备较强的计算和存储能力，可与其他匿名组进行合作处理。该结构的位置隐私保护流程为：

（1）用户借助通信基础设施与其他用户建立匿名组，当组内用户提出位置查询请求时，用户可以与组内其他用户相互合作，利用与其他用户位置信息建立匿名集；

（2）当组中的任何用户发出请求时，可以通过自身或者匿名组中的头节点提交请求到LBS服务器；

（3）LBS服务器会将查询结果集反馈给用户，用户对查询结果集进行求精，但LBS服务器也可以将查询结果集反馈给头节点，由组的头节点对查询结果集进行求精并发送给用户；

与独立式结构相比，该结构首先要在用户间建立匿名组，包含区域范围内的全局信息，具有较强的隐蔽性。但缺陷在于匿名、查询等功能均在设备中完成，增加通信与计算处理开销。此外，当组内用户数量较多时，无法确保其他用户的信任度，当组内用户数量较少时，又很难实现匿名功能。

1.4 混合式结构

该结构主要包括移动终端、LBS服务器以及第三方可信匿名服务器，用户在发送请求LBS服务时，首先建立匿名组的广播信息，将满足要求的用户聚集在一起，建立匿名组。当组内用户数量达到一定要求时，组内全部用户均可进行匿名请求，即分布式处理方案；当用户数量较少时，可直接向第三方可信匿名服务器发送匿名请求，即集中式处理方案。与上述三种结构相比，混合式结构具有较强个性化特点，当用户分布较为集中时，可通过匿名组方法，减少终端位置更新导致的第三方可信匿名服务器负荷，使第三方可信匿名服务器与用户之间处于平衡状态[2]；当用户分布较为分散时，无法组建匿名组，第三方可信匿名服务器保证了服务质量，但这种结构的缺点是结构复杂，参数众多，影响了实用性[3-4]。

1.5 结构对比

通过对上述四种隐私保护体系的分析，分别对不同结构的优缺点进行对比，具体如下表1所示。

表1 隐私保护体系结构对比

2 LBS位置隐私保护的关键技术

LBS应用成功部署条件不仅要保证用户服务质量，还需保护其隐私。目前，保护用户的位置隐私已经成为基于位置的服务需首要解决的问题。基于位置的服务中，位置隐私保护方法主要涉及伪码法、区域混淆法、假位置干扰法、加密法等技术。

2.1 伪码法

该方法也被称为假名法，在应用过程中，LBS服务器只注重是否有用户向其发送请求，而不注重是哪位用户，因此请求可采用伪码的方式来替代用户真实身份。但单一的伪码无法对用户位置信息进行保护，因为一些特定位置，不法人员可将单一伪码与用户身份相关联。例如，A早晨经常会在相同的位置发送LBS服务请求，此时不法人员便可利用该位置推测A的居住地址，将用户与伪码相关联，从而挖掘出用户的真实身份。对此，在单一伪码的基础上衍生出烦琐伪码，即在特定的位置或时间段，将用户伪码进行更改，且与之前伪码不相关联，以此来保护用户隐私。例如，在Mix zones方法中[5]，通常在混合区域内进行伪码变换，此种方式虽然可为用户提供定位服务，提高服务质量，但该方式的隐私保护度与用户数量具有较大关联，一旦该区域内用户数量较少，即便对伪码进行更换，也仍然会被不法分子进行关联，使隐私保护度大大降低。

2.2 区域混淆法

该方法中最为典型的便是位置k-匿名[6]。位置k-匿名借助用户周围邻居位置对用户自身位置进行替代，将用户与周围k-1个邻居混合起来，使得用户被攻击者的识别率为1/k，以此提高位置隐私程度。假设k的数值为4，F、G、H均为邻居，用户E向服务器发送的位置区域用（[x1，y1]，[x2，y2]）来表示，[x1，y1]，[x2，y2]分别表示区域的左下角、右上角坐标，区域中包含用户E、F、G、H，可见当k的数值越高，位置保护性也就越强，但服务质量将会随之降低，且服务器的查询、处理时间也将随之延长。当用户周围环境较为稀疏时，例如，邻居数量不足k-1时，则难以满足以上位置隐蔽条件。

2.3 假位置干扰法

此种方式以假位置信息进行位置混淆，从而对用户真实位置进行保护[7]。一般情况下，用户会向LBS服务器发送诸多位置信息，但只有一个是真实的，这样即便服务器中的位置信息被不法分子截获，也无法从大量信息中找出真实的一个，但此种方式在无形中使服务与通信的开销增加。与匿名法相比来看，假位置干扰在稀疏环境下的应用效果更佳，主要体现在两个方面，一是匿名法对邻居量具有严格要求，必须在保障邻居量至少k-1时才可使用，无法在稀疏环境下使用，而假位置干扰法则没有此方面的限制，可弥补该方式在应用中存在的不足，二是稀疏环境中，通信与服务器查询的开销较低，又可为用户位置提供良好的安全保护。

2.4 加密法

该技术对用户位置和请求信息进行加密，因此LBS服务器获得的用户信息处于完全保密的状态。加密技术一般采用分布式系统结构，利用移动终端对用户信息进行加密，实现匿名保护，应用较为频繁的技术包括信息检索技术和空间转换技术。

（1）信息检索技术

PIR检索技术是首先对数据进行了加密处理，再在服务器中对相关信息进行查询，因而服务器无法获取用户查询的真实内容。其分为基于计算能力与信息论两种方法。由于基于计算能力的PIR方法，会产生大量计算与通信量，采用较少。基于信息论PIR方法主要是在其他位置设置相同请求，从而保护用户隐私。例如，用户在对要去的目的地发送信息请求时，可能在去的途中发出多次请求，但每次访问请求都会导致不同数量的PIR访问。因此，就可以采用在不同位置设置相同PIR访问次数的方法，这样不法分子就无法通过在不同位置具有相同的PIR访问频率来推测用户的真实位置，从而达到保护用户隐私的效果。

（2）空间转换技术

该技术是当用户发送请求过程中，将自身位置与请求信息一同进行空间转换后，传递给LBS服务器，接着将LBS服务器的反馈信息再进行一次空间转换，最后对所需信息进行筛选。文献[8]基于集中式结构提出一种位置隐私保护法，首先将空间旋转一定角度，再使用密钥构造Hilbert曲线，然后会由第三方可信匿名服务器利用Hilbert曲线加密用户位置和请求信息并传输到LBS服务器，最后第三方可信匿名服务器再将查询结果处理并反馈给用户，以此来保障用户的位置安全，最后一步涉及第三方可信匿名服务器对LBS服务器返回的查询结果进行解码，使原始信息得以恢复。

3 基于用户敏感位置选择的假位置生成方案

3.1 设计思路

当某范围内用户数量较少时，无法满足有效构建匿名集的要求。对此，本节提出基于用户敏感位置选择的假位置生成方案，在第三方可信匿名服务器中生成假位置，即在用户敏感位置语义与最具不可区分性的位置信息等方面综合分析，选取出满足用户匿名等级的假位置，构建安全匿名集。由第三方可信匿名服务器向LBS服务器发送请求获取位置服务，再由第三方可信匿名服务器对结果进行筛选后反馈给用户。本方案的设计思路为：利用历史位置信息生成假位置，首先根据用户位置信息对敏感位置进行清除，此外判断周围用户所处的区域位置，通常查询频率与真实位置越接近，与真实位置组合后越具有不可区分性，这样就可以保护自身隐私安全，确保不被不法分子所攻击。

3.2 生成假位置

考虑到当用户处在较为稀疏的路段中时，周围用户数量可能较少，无法有效的构建匿名集，此时可以利用历史信息作为假位置进行匿名集构建。与常规假位置生成方案相比，可有效降低湖泊、山脉等不可达语义位置被不法分子识别的概率。用户在发送请求时利用第三方可信匿名服务器，对周围历史查询信息进行收集、分析和整理，并对发送请求次数相近之处生成假位置信息，具体的生成方案如下：

（1）采集用户周围历史位置，对周围区域进行划分，最终形成网格；

（2）对与用户敏感位置语义相同位置进行删除，对网格范围的历史位置概率进行计算；

（3）按照用户设置的匿名等级，对假位置从相似概率值等方面进行筛选，最后选择与用户距离较近且语义各不相同的位置并构建匿名集；

将用户周围区域划分为不同的网格，格内数字表示历史信息在该点发送的服务请求频率次数，初始值为0，没有标注数字的定位频率次数为0。例如，当用户发送请求时自己负责设置匿名等级，第三方可信匿名服务器将根据以下公式对格内历史位置的出现频率次数进行计算，并对假位置概率值等方面进行分析，构建安全匿名集。历史查询概率通过如下公式计算。

3.3 安全性分析

本文采用可信的第三方服务器结构，即集中式结构且假设第三方服务器可信，LBS服务商无法直接从可信第三方服务器中对用户的真实定位与请求进行采集，假设不法分子可从LBS服务器中采集用户的匿名集与请求信息，也可采集到该区域的历史位置信息。第三方可信匿名服务器不但将真位置传递给LBS服务器，同时也将假位置一并传输。当用户在稀疏环境下发送请求时，利用历史位置信息生成假位置，这样就避免不法分子可运用地理知识，将与用户位置不相关的信息，即不可达位置进行筛除。

另外，当用户在教堂、医院、湖泊、酒吧与学校等敏感位置定位时，一旦周围定位为也为相同的敏感位置则可能向不法分子传递有用信息。而第三方可信匿名服务器会将周围定位信息属于与用户位置语义相同的敏感位置信息点全部删除且最后生成的匿名集各位置语义不相同，这样避免语义相似性，即便不法分子拥有用户的匿名信息，也无法推测出用户所处的具体位置与类别，同时，假位置查询频率与真实位置接近，与真实位置组合后具有不可区分性，加大了被识别难度，从而使用户的个人位置隐私得到充分保护。

3.4 实验分析

（1）实验环境配置

本文实验代码利用Java语言编写，运行在配置处理器为Inter（R） Core（TM） i5-8250U 1.6GHz，8GB内存的64位Windows 10操作系统中，数据集来源于微软GeoLifeGPS Trajectorier[9-11]中的182名用户在历时超过五年的移动轨迹，将用户轨迹作为历史信息位置，共计17621条，1~5秒更新一次，主要活动地点为北京，通过部分数据进行方案验证。

（2）实验性能与结果分析

本文采用集中式隐私保护体系结构，第三方可信匿名服务器除了向LBS服务器转发请求以及查询结果求精外，还需要通过历史查询信息进行相同语义位置删除以及概率计算等操作，得到假位置，最后组成匿名集。假位置集生成所需时间反映了假位置生成方案的性能。从图1可以看出，用户请求中设置的匿名级别k与假位置集的生成时间呈现出正相关，也就表明了，随着用户请求中设置的匿名级别k的增加，生成假位置集所需的时间也会增加。这是由于随着用户要求的匿名等级k的提高，所需要生成的假位置就会增多，通过进行相同敏感位置删除以及查询概率比较等操作选取的假位置所用时间会增加。但是还可以从图1中看到，每次所需的总时间相对较小，服务质量基本不会受到影响。

此外，本方案从位置熵值来度量隐私保护。根据以下公式可对位置熵值进行计算，且位置熵值越小，被攻破的概率越高，安全性越无法得到保障；反之，位置熵值越大，被攻破的概率越低，匿名效果也就越理想，公式为：

在本次实验结果中，从图2可以看出，随着用户隐私匿名等级k值的增加，生成匿名集的位置熵值升高，进而说明用户隐私匿名等级k值越大，位置熵值越大，用户真实位置被攻破的概率越低。从实验结果可以很明显地看出，本方案对位置隐私保护有较好的效果。

图2 匿名等级k和位置熵的关系

4 结论

综上所述，本文对LBS服务结构进行概括，并对比分析各自的优缺点，对现有隐私保护的关键技术进行分类整理，从而提出更加安全可靠的位置隐私保护方案。在将来的工作中将研究连续查询情况下的位置隐私保护，同时，在未来的发展中，隐私保护技术水平将不断完善优化，保护效果更加理想，有效抵御非法攻击，使用户的隐私安全得到切实保障。

[1]维基百科.基于位置的服务[EB/OL].[2019-1-11].https：//zh.wikipedia.org/wiki/基于位置的服务.

[2]Zhang CY，Huang Y.Cloaking locations for anonymous location based services：A hybrid approach.Geoinformatica，2009，13（2）：159-182.

[3]张学军，桂小林，伍忠东.位置服务隐私保护研究综述[J].软件学报，2015，26（09）：2373-2395.

[4]罗健.基于位置服务的位置隐私保护[D].2016.

[5]Beresford A R，Stajano F.Location privacy in pervasive computing[J]. IEEE Pervasive Computing，2003，2（1）：46-55.

[6]GRUTESER M，GRUNWAL D.Anonymous usage of location based services through spatial and temporal cloaking[C].Proceedings of the International Conference on Mobile Systems，Applications，and Services，2003：163-168.

[7]Kido H，Yanagisawa Y，Satoh T.An anonymous communication technique using dummies for location-based services[C].Proceedings of the International Conference on Pervasive Services，2005：88-97.

[8]Khoshgozaran A，Shahabi C.Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy.Spatial and Temporal Databases，2007，49（6）：239-257.

[9]Yu Zheng，Lizhu Zhang，Xing Xie，Wei-Ying Ma.Mining interesting locations and travel sequences from GPS trajectories.In Proceedings of International conference on World Wild Web（WWW 2009），Madrid Spain.ACM Press：791-800.

[10]Yu Zheng，Quannan Li，Yukun Chen，Xing Xie，Wei-Ying Ma.Understanding Mobility Based on GPS Data.In Proceedings of ACM conference on Ubiquitous Computing（UbiComp 2008），Seoul，Korea.ACM Press：312-321.

[11]Yu Zheng，Xing Xie，Wei-Ying Ma，GeoLife：A Collaborative Social Networking Service among User，location and trajectory.Invited paper，in IEEE Data Engineering Bulletin.33，2，2010，pp.32-40.