基于SpaceTwist改进的位置隐私保护方法

杨晓晖，朱烨，胡倩茹

(河北大学 计算机科学与技术学院，河北 保定 071002)



基于SpaceTwist改进的位置隐私保护方法

杨晓晖，朱烨，胡倩茹

(河北大学 计算机科学与技术学院，河北 保定 071002)

移动互联网中基于位置服务的查询质量与位置隐私保护二者的权衡问题是目前研究热点之一.提出一种基于SpaceTwist方案的k匿名增量查询位置隐私保护方法，采用客户-服务器架构，对用户真实位置形成k匿名区并以供应匿名区形心作为锚点，经匿名变换后将真实位置排除于匿名区域外，并以增量形式改变查询范围来返回查询结果集.避免使用第三方服务器使其成为攻击点，在提高查询准确度的同时保证了用户位置隐私的效果.

位置隐私保护；基于位置的服务；k匿名；锚点；匿名变换

移动互联网的飞速发展改变了人们传统的生活方式，其便携性以及实时性使网络的服务模式有了新的起点，而带来的安全和隐私问题却甚于传统互联网，包括用户的身份信息、兴趣信息、位置信息等.基于位置的服务[1](LBS，location-based service)融合了定位技术、移动通信技术、互联网技术以及地理信息系统(GIS)技术，是移动互联网中应用性最强的服务.用户作为需求方，将自己的位置信息发送给LBS提供商(LSP，location-based service provider)来获得相关查询信息，如查询“离我最近的餐厅、5 km范围内的加油站”等兴趣点(POI，point of interest).

随着位置服务的广泛应用，位置隐私的安全问题已经越来越受到用户的重视，形势日益严峻，国内外学者对位置隐私保护问题的研究也日益增多.在用户使用LBS的过程中，LBS必须要首先获得准确的用户位置信息才能够提供相应的满足用户需求的服务，这其中并不是只包含单纯的地理坐标信息，因为攻击者通过对位置的观察分析，同时能够获知用户的身份信息甚至家庭住址、兴趣爱好、健康状况等一系列个人隐私信息，在充分享受位置服务提供的便利的同时，保证用户的隐私安全是当下亟待解决的问题.

1 经典位置隐私保护方法

现存的位置隐私保护方法中，提出最早的，也是最广泛采用的是位置k匿名模型[2]，k匿名模型是基于泛化法[3]的位置隐私保护技术，主要思想是在发布用户的位置信息时，用一个覆盖其他k-1个用户的匿名区域代替用户的真实位置，使得LBS提供者无法从这k个用户中辨别出真实用户的位置.但大多数k匿名模型的研究都依赖于第三方服务器，为了不使自己的精确位置泄露，用户与LSP之间的交流需要第三方服务器来维系，用户将位置信息发送给第三方服务器，再由第三方服务器将匿名区域的k个用户的查询需求发送给位置服务提供商，得到结果集后，第三方服务器再对数据进行分析，把最终筛选出来的结果返回给相应的用户.经典的k匿名有四分法[4]，该方法通过将用户所在区域逐一四分化来形成匿名区域以达到k匿名效果.k匿名模型采用的第三方服务器结构在实际生活中可靠性不高，完全可靠的第三方服务器几乎是不存在的，使第三方担任用户与LSP之间的通信中介会导致依赖性过强，成为攻击热点等问题，其掌握用户的位置信息、身份信息和查询信息等被恶意攻击，后果不堪设想[5].同时第三方服务器效率也将成为LBS的瓶颈.

常见的位置隐私保护方法[6]还包括假位置，掩盖技术，加密技术等，其中假位置的方法利用1个或多个锚点进行位置隐私保护，不同的需求采用不同的假名来模糊真实位置，并且假名需要不断更新，同时保持新、旧假名的连接，使攻击者即便截获数据而得到用户信息也无法精确得出用户是谁的结论，达到保护用户隐私的目的，但这类方法存在结果不精确或开销过大等问题.

Yiu等[7]提出了SpaceTwist方案，主要思想是用户随机选取自己真实位置附近的一个点作为锚点q'，使用该锚点代替用户的真实位置向LBS服务器发送请求，如图1所示，查询开始时，初始化需求空间和供应空间，需求空间是整个空间，供应空间为空，查询过程中需求空间以用户真实位置为圆心，供应空间以锚点为圆心.用户向LBS服务器发送请求搜索附近POI，需求空间不断缩小，同时供应空间不断扩张，直到供应空间完全覆盖需求空间才停止检索，此时查询结束，请求结果返回给用户.

图1 SpaceTwist方案Fig.1 SpaceTwist scheme

SpaceTwist方案虽然摆脱了第三方服务器，但无法达到k匿名，它忽视了一种情况：如果用户所在地点除锚点外恰巧只有一个用户，则攻击者知道用户真实位置的概率为50%，无法很好地满足用户位置隐私保护需求；且SpaceTwist方案选取锚点的方法随机性太强，如果在更恰当的合理范围内选取合适的锚点，能够提高查询的精确度.针对SpaceTwist方案无法实现k匿名的缺陷，孟小峰等[8]提出Coprivacy来弥补不足.而Coprivacy是采用用户之间相互协作的无中间服务器结构的方法，虽然避免了中心服务器造成的黑客集中攻击点以及性能瓶颈问题，但其假定了参与协作的移动用户都是可信的，未考虑不可信用户的情况，如遇恶意用户，隐私泄露问题也难以解决.

肖燕芳等[9]提出了基于匿名区域变换的方法，匿名区域变换与传统匿名区域生成方式不同，其特点是采用变换的方法使用户的真实位置不包含在匿名区域中，该方案形成的匿名区域排除了用户真实位置，降低了位置隐私泄露的概率，但锚点生成阶段仍然存在随机性较大导致查询结果不精确的问题.

因此为了进一步提高查询结果的精确度和位置隐私保护程度，基于SpaceTwist方案提出采用客户-服务器系统架构并结合k匿名以及匿名变换方法来实现LBS查询方面的位置隐私保护，在移动客户端中进行匿名区域生成、锚点选取以及查询处理等工作.

2 系统架构

本文方法采用客户-服务器架构，直接在移动客户端进行匿名区域的生成以及用户需求查询处理的工作，系统架构如图2所示.

图2 系统架构Fig.2 System architecture

整个系统架构包括移动客户端和位置服务提供商，二者由通信网络连接.移动客户端包含位置匿名模块和查询处理模块，位置匿名模块的工作是生成查询过程中的供应匿名区和需求匿名区以及选取锚点，其中匿名转换器是利用匿名区域变换法生成供应匿名区，并把移动用户的k近邻查询转变为供应匿名区内所有节点的范围查询；查询处理模块的工作是在SpaceTwist方案的基础上搜索符合条件的POI，经过分析计算后选出最终结果.

3 匿名区域增量查询位置隐私保护方法

3.1 基于k匿名的锚点选取过程

结合k匿名的思想，将用户真实位置q所在区域通过四分法选取单元格后形成需求匿名区，需求匿名区即匿名变换之前形成的包含用户真实位置信息的匿名区.将该单元格形心作为锚点，如图3所示，图中实心圆为除用户真实位置以及锚点以外的其他用户.具体步骤如下：

1)用户端定位出用户真实位置q的地理位置坐标；

2)用户端根据经纬度，确定用户所在城市，记为G；

3)用户向LBS服务器发出请求，LBS返回该区域的分割结果；

4)LBS服务器采用四分法对整个G区域分割成正方形块区域，逐一递推缩减正方形块的大小，其中每个正方形的边长根据需求拟定参数λ，使数值不大于λ.每个正方形块作为一个单元格.每个单元格对应一个节点.每个节点中存储相应的单元格信息(包括用户ID，中心点O，单元格内的用户数量x)，单元格信息实时更新.

5)对于给定的匿名度k，每划分一次单元格后都要比较x与k的大小关系，当x>k时，则继续分割单元格，重复此过程；当x

6)用户端将真实位置所在单元格的形心作为锚点q'.

该过程基于SpaceTwist方案选取锚点的思想提出了在实现k匿名后的需求匿名区的形心作为锚点，而不是随机选取，可以提高用户查询结果的准确性，同时结合k匿名的思想，保证了用户附近有其他k-1个用户，这将对攻击者产生混淆，保证了用户的位置隐私.

3.2 基于匿名变换的匿名区域生成过程

将用户所在位置设置为原点，运用上文中提到的匿名区域变换法生成供应匿名区.如图4所示，q为用户真实位置，q'为锚点，图4中实心圆为POI点.步骤如下：

1)以用户真实位置q为圆心，建立x-y直角坐标系

2)连接qq'，做过q'的直线垂直于qq'，与y轴相交于点N，以q'为中点的线段NF作为正方形的边长，此正方形即为供应匿名区，在坐标系的第一象限形成.

该过程利用匿名变换形成的匿名区域排除了用户真实位置，相比较传统k匿名模型来说大大降低了位置隐私泄露的概率.

图3 锚点选取Fig.3 Anchor selection

图4 匿名区域变换Fig.4 Anonymous area transformations

3.3 基于SpaceTwist的增量查询过程

图5 增量查询Fig.5 Incremental query

为了使用户享受LBS所带来的便利的同时，又不必担心隐私信息泄露给LSP，就要权衡服务质量与隐私保护程度这2个问题.用户发出LBS请求的过程从根本上说就是一个用户和服务端共享位置信息并获取查询结果的过程.根据位置服务中查询结果的不同可分为2种查询模型[10]，即范围查询和K近邻(KNN)查询.典型的范围查询语言为“距我R范围内所有的电影院”，是以查询距离R作为标准以获得结果.典型的K近邻查询语言为“距我最近的K个电影院”，是以POI数量K作为标准获得结果.基于SpaceTwist的增量查询过程是用户端以供应匿名区作为用户的位置向服务提供商发送查询请求.

如图5所示，POI点记为p1,p2,p3,…,pn，具体增量查询请求过程如下：

1)初始化供应空间和需求空间.供应空间是以锚点q'为圆心的圆形区域，需求空间是以真实位置q为圆心的圆形区域.查询开始，供应空间为空，需求空间为整个空间.

2)匿名区域中的n个节点以增量形式发起n次近邻查询请求，LSP不断返回近邻查询结果集，直到供应空间完全覆盖需求空间；

3)用户端检索返回的查询结果，将LSP返回的结果集进行筛选，根据用户隐私需求定义一个参数m，当dist(q,p)>m时，剔除掉该点，将恰当的POI作为最终结果.

需要说明的是，当用户发出KNN查询请求，返回的POI数量小于K时，则扩大正方形匿名区域边长，继续发送匿名区域内n个节点的查询请求，直到满足K为止.

4 仿真实验

仿真实验主要关注LBS服务查询过程中用户位置安全性、查询精准率、响应时间等指标的变化情况，在模拟数据集上进行，通过与经典位置隐私保护方法进行对比来体现本方法的性能.

算法采用Java语言实现，在window 7系统上运行，硬件环境为3.2 GHz Intel Core i5处理器、4 GB内存.模拟数据集来自Thomas Brinkhoff[11]路网数据生成器，并以城市Oldenburg的交通路网作为输入生成移动对象数据.实验数据参数如表1所示.

表1 实验参数Tab.1 Experimental parameters

随机选择1 000个用户作为查询用户的位置，匿名需求参数k∈[5,25],区域内随机生成.本文相对SpaceTwist方案锚点的选取过程取消了随机方式，为了检验其精准性，实验使用Oldenburg生成的移动对象数据，对比了二者的查询近邻结果数量，即匿名区域中用户向LSP请求得到的近邻结果总数，如图6所示.可见相对SpaceTwist方案来说，实验效果有显著改善，查询结果数量较少，精准率高于SpaceTwist方案.

相对传统匿名方法，采用了客户-服务器结构，不使用第三方服务器，并加入了匿名转换器，即把真实位置放置于匿名区域外.文献[12]中提出的PrivacyGrid方案是一种典型的采用中心服务器结构的位置隐私保护方法，通过匿名成功率来检验其性能，匿名成功率指匿名区域内的用户(即匿名区内用户个数满足匿名度k)占系统中全部用户的比例.而不同用户对k的隐私需求不同，涉及到个性偏好问题[13]，暂时不做深入研究.如图7所示，随着匿名度k的增加，本文方法的匿名成功率相对PrivacyGrid来说略低，这是因为经匿名变换后供应匿名区和需求匿名区的范围稍有出入，但影响并不大，此匿名方法的隐私保护程度更高.

图6 本文方法与SpaceTwist方案查询精准性对比Fig.6 Query accuracy of this method compared with SpaceTwist

图7 本文方法与PrivacyGrid方案匿名成功率对比Fig.7 Anonymous success rate of this method compared with PrivacyGrid

响应时间是指用户端发送近邻查询请求至LSP，LSP返回查询结果并满足用户需求整个过程的所需的时间[14]，其与SpaceTwist方案对比结果如图8所示，可以看出锚点与用户位置距离越大，响应时间越长，这是因为随着二者距离的增加，圆形供应区域半径随之增加，查询区域会因此变大，LSP返回的结果集也会越来越大，从而导致响应时间变长.本文方法较SpaceTwist方案增加了四分法选取锚点过程和匿名变换过程，因此当锚点距离用户真实位置较近时响应时间较SpaceTwist方案略长，随着距离的增大，响应时间较SpaceTwist方案都变小，同时增大幅度较小.响应时间较SpaceTwist方案有所改善，但并未达到预期效果.

图8 本文方法与SpaceTwist方案响应时间对比Fig.8 Response time of this method compared with SpaceTwist

5 结束语

结合客户-服务器架构和SpaceTwist方案的增量近邻查询处理方法的优点，本文工作主要包括以下几个方面：

1)提出了一种采用客户-服务器架构的位置隐私保护方法，不使用第三方服务器，避免出现第三方服务器成为攻击中心的问题.

2)基于SpaceTwist方案来选取一个锚点代替用户真实位置向LSP发送请求，同时采用四分法生成需求匿名区，将需求匿名区中心作为锚点，相对提高了查询结果的精准率.

3)采用匿名变换法生成供应匿名区，将用户真实位置放在匿名区外，相对加大了位置隐私保护的强度.

最后在模拟数据集上进行了实验，证明了其优点，但由于工作量较大，导致响应时间未达到预期效果，未来工作可以在减少响应时间方面进一步开展.

[1] MOKBEL M F.Privacy in location based services:start of the art and research directions[J].2013 IEEE 14th International Conference on Mobile Data Management,Mannheim,2007.DOI:10.1109/MDM.2007.45.

[2] GRUTESER M,GRUNWALD D.Anonymous usage of location-based services through spatial and temporal cloaking[Z].The 1st International Conference on Mobile Systems,Applications and Service,San Frncisco, CO,USA,2003.DOI:10.1145/1066116.1189037.

[3] 王宇航,张宏莉,余翔湛.移动互联网中的位置隐私保护研究[J].通信学报,2015,36(9):230-243.DOI:10.1195/j.issn.1000-436x.2015167. WANG Y H,ZHANG H L,YU X Z.Research on location privacy in mobile internet[J].Journal on Communications,2015,36(9):230-243.DOI:10.11959/j.issn.1000-436x.2015167.

[4] MOKBEL M F,CHOW C Y,AREF W G.The new casper query processing for location services without compromising privacy[Z].The 32nd International Conference on Very Large Data Bases,Seoul,South Korea,2006.

[5] WERNKE M,SKVORTSOV P,DURR F K,et al.A classification of location privacy attacks and approaches[J].Personal and Ubiquitous Computing,2014,18(1):163-175.DOI:10.1007/s00779-012-0633-z.

[6] 李晖,李凤华,曹进,等.移动互联服务与隐私保护的研究进展[J].通信学报,2014,35(11):1-11.DOI:10.3969/j.issn.1000-436x.2014.11.001. LI H,LI F H,CAO J,et al.Survey on security and privacy preserving for mobile internet service[J].Journal on Communications,2014,35(11):1-11.DOI:10.3969/j.issn.1000-436x.2014.11.001.

[7] YIU M L,JENSEN C S,HUANG X,et al.SpaceTwist:managing the trade-offs among location privacy,query performance,and query accuracy in mobile services[C].Data Engineering,ICDE 2008,IEEE 24th Intenational Conference,Cancun,Mexico,2008:366-375.DOI:10.1109/ICDE.2008.4497445.

[8] 黄毅,霍峥,孟小峰.CoPrivacy:一种用户协作无匿名区域的位置隐私保护方法[J].计算机学报,2011,34(10):1976-1985.DOI:10.3724/SP.J.1016.2011.01976. HUANG Y,HUO Z,MENG X F.CoPrivacy:a collaborative location privacy preserving method without cloaking region[J].Chinese Journal of Computers,2011,34(10):1976-1985.DOI:10.3724/SP.J.1016.2011.01976.

[9] 肖燕芳.基于匿名区域变换的位置隐私保护模型与算法研究[D].广州:华南理工大学,2012. XIAO Y F.Research on location privacy protection model and algorithm based on anonymous area scaling[D].Guangzhou:South China University of Technology,2012.

[10] 贾金营,张凤荔.位置隐私保护技术综述[J].计算机应用研究,2013,30(3):641-646.DOI:10.3969/j.issn.1001-3695.2013.03.001. JIA J Y,ZHANG F L.Overview of location privacy protection technology[J].Application Research of Computers,2013,30(3):641-646.DOI:10.3969/j.issn.1001-3695.2013.03.001.

[11] Brinkhoff T.A framework for fenerating network based moving objects[J].GeoInformatica,2002,6(2)153-180.DOI:10.1023/A:1015231126594.

[12] BAMBA B,LIU L,PESTI P,et al.Supporting anonymous location queries in mobile environments with privacygrid[Z].The 17th International Conference on World Wide Web,Beijing,2008.DOI:10.1145/1367497.1367531.

[13] 倪巍伟,陈萧.保护位置隐私近邻查询中隐私偏好问题研究[J].软件学报,2016,27(7):1805-1821.DOI:10.13328/j.cnki.jos.005053. NI W W,CHEN X.User privacy preference support in location privacy-preserving Nearest Neighb-orQuery[J].Journal of Software,2016,27(7):1805-1821.DOI:10.13328/j.cnki.jos.005053.

[14] 周长利,马春光,杨松涛.基于敏感位置多样性的LBS位置隐私保护方法研究[J].通信学报,2015,36(4):125-136.DOI:10.11959/j.issn.1000.436x.2015160. ZHOU C L,MA C G,YANG S T.Research of LBS privacy preserving based on sensitive location diversity[J].Journal on Conmmunications,2015,36(4):125-136.DOI:10.11959/j.issn.1000.436x.2015160.

(责任编辑：孟素兰)

Improved location privacy protection method based on SpaceTwist

YANG Xiaohui，ZHU Ye，HU Qianru
(College of Computer Science and Technology,Hebei University,Baoding 071002,China)

The trade-off between location-based query quality and location privacy protection in mobile internet is one of the current research hotspots.This paper proposes an anonymous incremental query location privacy protection method based on the SpaceTwist scheme.The client-server architecture is used in this paper.Thekanonymous area is formed and the centroid of the anonymous area is used as the anchor point.After anonymous transformation,the real location is excluded in the anonymous area.It changes the query range in the form of incremental and returns the query result set.It avoids using a third-party server or it will become a point of attack,and it improves the accuracy of the query while ensuring the user's location privacy effect.

location privacy protection;location-based service;kanonymous;anchor;anonymous transformation

2017-02-27

国家科技支撑计划项目(2013BAK07B04)；河北省自然科学基金资助项目(F2014201152)

杨晓晖(1975—)，男，河北邢台人，河北大学教授，博士，主要从事分布计算与信息安全等方向研究. E-mail:yxh@hbu.edu.cn

胡倩茹(1979—)，女，河北灵寿人，河北大学讲师，主要从事大数据和数据挖掘方向研究.E-mail:huqr@hbu.edu.cn

10.3969/j.issn.1000-1565.2017.03.011

TP391

A

1000-1565(2017)03-0287-07