摘 要：针对大数据时代中，用户的个人位置隐私安全面临极大威胁的问题，依据位置大数据的理论，从用户的移动智能终端角度分析研究了现有位置隐私保护技术的缺点与不足。提出在现有的加密扭曲算法模型的基础上，引入了坐标转换方法，增加对用户位置请求信息的碎片化处理，改进优化了哑元、假名两个技术。仿真实验中，利用模拟软件生成大量的用户移动轨迹，研究比对改进前后的算法各自的信息熵以证明优化算法的优越性。分析实验结果验证了改进后的加密扭曲算法实现了对个人位置隐私信息更有效地保护。
关键词：位置大数据；基于位置服务；位置隐私保护；加密扭曲算法
DOI：10.15938/j.jhust.2018.02.011
中图分类号： TP311.13
文献标志码： A
文章编号： 1007-2683（2018）02-0058-07
Abstract：To solve the problems of users′ personal location privacy are facing great threat in the era of big data， according to the theory of location big data， the shortcomings of existing location privacy protection technology are analyzed from the perspective of users′ mobile intelligent terminals. Based on the existing encryption and distortion algorithm models，it introduces a coordinate transformation method，increases fragmentation of user location information，and optimizes the technologies of dummies and false-name. In simulation experiments， a large number of user trajectories are generated by simulation software， and the information entropy of improved and original algorithm is studied to demonstrate the superiority of the improved algorithm. The experimental results verify that the improved encryption and distortion algorithm is more effective to protect personal location privacy information.
Keywords：location big data； location-based Service； location privacy protection； encryption distortion algorithm
0 引 言
21世o是新技术的时代，是大数据的时代。世界预测大师、未来学家约翰・奈斯比特（John Naisbitt）在他的著作《Megstrends：Ten new directions transforming our live》一书中曾提到。我们现在大量生产信息，正如过去我们大量生产汽车一样[1]。而这种体量巨大（Volume）、增长迅速（Velocity）、类型多样（Variety）的信息，我们便称其为大数据。人们可以从中利用那些看似杂乱无章的数据，辅以各种现代科学技术手段，去提取知识、分析规律、预测趋势、挖掘价值，并且会将这些价值应用到日后的生产生活中以便谋取更高的经济利益。但是，同时也会有一些人动了歪心思，利用挖掘出的有效信息谋取非法的利益。由此可见，大数据可以说是一把双刃剑，一方面可以给企业带来商机，另一方面也可能给人带来无限的困扰[2]。
大数据要是想真正成为时代的弄潮儿，是万万离不开传统行业和实体经济的，它们之间连接的纽带其实就是“位置大数据”。正是位置大数据，把几乎所有的人、事、物紧密地联系在了一起。我们可以用这样一个公式来表示，位置数据+时间数据+事件数据+场所数据+人物行为数据+…=大数据的无限演绎。例如，我们可以通过人出现的时间和位置，推测出这些人所从事的职业或特征。大数据虽然是散乱抽象的，但是通过一定手段联系起来就很容易得到有价值的信息。
位置数据的获取渠道有很多很多：除了GIS（geo-information system，GIS）系统，还有手机基站指令、WIFI连接情况、IP地址、网卡信息等抓取，甚至我们安装在智能手机的APP签到功能都会泄露我们的位置隐私[3]。在美国，一家零售公司通过分析一个女孩经常出没在超市母婴专区，推测出了该女孩很有可能是怀孕了，后来证明结论是正确的，甚至连女孩的父母都对此不知情。
本文主要是针对大数据时代的个人隐私，尤其是位置隐私的保护方法进行研究，特别是关于LBS（location-based service，LBS）隐私保护方法进行研究并改进，实现突破，以便提高位置隐私保护程度，增强安全性，更有效地保护用户的个人位置隐私信息。
1 相关工作
根据中国互联网络信息中心（China Internet Network Information Center，CNNIC）于 2016 年 10 月发布的 《中国移动互联网调查研究报告》[4]，截止2015年12月，我国手机网民规模高达6.2亿，95.9%的手机网民在2015年遭遇手机安全事件，个人隐私泄露占比26.4%。用户会利用手机地图进行实时定位；使用微信上传位置信息查找附近的人；通过大众点评网提交地理位置信息来换取服务等。另根据Future X 未来智库、互联网数据中心（Data Center of China Internet，DCCI）与360安全中心联合发布的 《2016年中国Android手机隐私安全报告》[5]：相比2015年，2016年获取“位置信息”权限的非游戏类App比例由76.8%增加到91.7%。大量的这类APP 收集了大量用户的位置信息，并发送给服务提供者或发布到网络上，这无疑成为了个人隐私的重要威胁。由此可见，对位置隐私进行有效的保护已刻不容缓。 因此，研究出切实有效的基于位置的服务的隐私保护方法已经成为重中之重。LBS 系统由移动终端、定位系统、通信网络和 LBS 服务器 4 部分组成：移动终端向 LBS 服务器发送包含用户位置的 LBS 查询；定位系统实时获取移动终端发送 LBS 查询时的位置；通信网络传输 LBS 查询和从服务器返回的查询结果；LBS 服务器响应用户的查询，并返回定制结果。目前，智能终端以及多种智能穿戴设备中嵌入了各种各样的传感器，它们可以做到实时地记录使用者出现过的位置和运动轨迹、移动速度等等，并且利用我们手中的手机等移动智能终端设备上传给服务器[6]。虽然一方面，这样做使得我们可以享受到更加精准的服务，但另一方面也大大地增加了我们个人位置隐私信息泄露的风险。假如一旦某个设备供应商刻意的通过收集这些数据分析人们的特点以便改进其产品，我们的个人数据就会面临着巨大的威胁[7]。
据卡耐基梅隆大学的计算机科学家们调查， Android 系统中的大部分 App 都会收集手机的位置信息，这些通过 GPS 定位所得到的位置信息在 50 米内具有相当高的精确度。在进行该项研究的2个星期中，每一名试验志愿者平均都被收集位置信息高达 6 200 次，也就是约每 3 min这些志愿者的定位信息就要被 App 上传一次。频繁地收集位置并及时地上传到服务器可以提升服务质量，但是也会增加位置隐私泄露的风险。目前，主要应用基于博弈论的隐私保护方法来解决隐私保护程度与服务质量权衡的相关问题。Freudiger等[8]考虑到了自私节点对于位置隐私的影响，以博弈论为基础分析了非合作情况下的位置隐私保护。Reza 等[9]提出了博弈论框架使得设计者能够从给定的服务中寻找出最优位置隐私保护机制。Reza所提出的框架是以用户为核心的，因此笔者认为该方法可很好地被应用到智能移动终端位置隐私保护与LBS服务质量间的权衡机制中。
另外，传统的隐私保护模型除了博弈论，还有 k-匿名与差分隐私模型。k-匿名模型最早是由Samarati和Sweeney于1998年提出[10]，它实现了对个体与数据库中具体对象间的联系的断开，从而保护了敏感数据。Marco Gruteser[11]最先将k-匿名模型应用到了位置隐私保护上，提出位置k-匿名（Location k-Anonymity）的概念。如图1所示，为k=5情况，即存在A、B、C、D、E共计5个用户，其中用户A进行位置请求，且c其他4人共同组成一个空间区域。该空间区域内的用户坐标都用这块区域来表示，造成LBS服务器无从知晓究竟是区域内的哪个用户提出的位置请求，从而提升匿名程度，达到保护用户个人位置隐私的目的。
差分隐私模型最早是由Dwork在2006年提出[12]。该模型主要通过为原始数据添加噪声的方式来起到保护个人位置隐私的目的，使非法的信息截取者即使拦截或窃听到了包含用户位置信息请求的信息，也很难从中提取出有效的隐私信息。对于一个严格定义下的攻击模型，具备添加噪声少、隐私泄露风险低、破解难度相对较高等优势。位置隐私保护技术是指让LBS提供商和非法人员不能或者无法轻易获得用户的真实位置相关信息的防护方法，当前可以大致分为3 类 ：位置模糊、身份隐藏和信息加密[13]。现将不同种类的传统保护技术的分析结果列在表1中，供读者参考，这里不再赘述。
但是，这些传统的经典位置隐私保护技术在这个时代，面对着大数据、社会网络等新兴技术的冲击时面临着许多新的危机和挑战。目前比较流行的主要有三类技术：政策法、扭曲法和加密法。基于政策法的技术实现简单，服务质量高，但隐私保护效果差；基于扭曲法的技术效率较高，在服务质量和隐私保护上取得了较好的平衡，但位置信息或服务属性存在一定的不准确性，易遭受具有完全背景知识的攻击；基于加密法的技术能够完全保证数据的准确性和安全性，可以提供更严格的隐私保护，但需要额外的硬件和复杂的算法支持，计算和通信开销很大[14]。本文主要选择相对适中的扭曲法中的加密扭曲法进行研究并改进。
2 加密扭曲法的LBS隐私保护算法
近几年来，基于扭曲法的 LBS 隐私保护技术已成为 LBS 隐私保护社区最活跃的研究方向[15]。它是指对 LBS 查询中（ u 代表用户身份标签，loc 是用户在t时刻提交查询的位置，Upoi是指服务质量）的原始数据进行必要的扰动，以避免攻击者轻易地获得用户的真实数据，同时要能保证用户不受妨碍地获得服务。采用的技术主要包括假名（删除或用一个临时的标识代替用户身份）、随机化（添加哑元）、模糊化（泛化或扰动查询中的时空信息）和隐蔽化（对攻击者隐蔽整个查询）。
加密扭曲法算法模型是指用户向LBS服务器进行地理位置信息查询数据请求，而服务器对时间、空间等信息或服务项目属性进行查询，之后适当地进行扭曲、加密与改正，以致于服务器无法获得准确的服务项目和地理位置信息属性[16]。算法模型如图2所示。
2.1 假名技术
它通过技术手段隐藏或修改原有用户身份标识，并使用一个假名来进行地理位置请求，从而切断了用户的身份与查询请求之间的联系。假名只是一个对象的标识而非真实的用户名，不包含用户能被识别的信息，从而实现了对用户位置隐私的保护。
2.2 用户地理位置的随机化
随机化是指在进行 LBS 查询时加入随机哑元（哑元既可以是虚假的位置也可以是虚假的用户），并将哑元查询请求和真实的查询请求一起发送给 LBS 服务器[17]。用户在移动用户终端上产生哑元查询，并将其和真实查询一起提交给LBS服务器，LBS服务器会响应所有的查询并向用户返回所有结果，再由用户终端进行一定的算法处理，过滤掉哑元查询并提取出真实查询请求结果。如图3所示，A为用户u所处的真实位置，现用户u要向LBS服务器进行查询请求，找到附近的饭店。此时，用户终端会随机产生哑元位置B、C，并将A、B、C三个位置一并提交给服务提供商，收到反馈结果后再在终端运行过滤算法，得到饭店位置。 2.3 用户地理位置的模糊化
用户地理位置模糊化是指在进行地理位置查询的过程中，对请求数据中的时间元素和位置元素进行适当地泛化（以可控的方式降低查询中时空元素的精确度）与扰动（在位置元素中以一定的算法有意地添加部分错误），使得非法入侵者即使窃取到了请求信息，也无法得知用户的确切位置。具体可分为集中式和分布式两种方式的隐私保护技术。
2.3.1 集中式隐私保护技术
是由可信的匿名服务器负责对用户位置数据进行泛化和扰动，并将LBS服务器反馈回来的由模糊化的数据得到的查询结果转换为用户需要的准确地理位置信息。空间泛化技术通常采用上文提到的位置 k-匿名方式，即由可信的第三方匿名服务器将用户所提交的精确位置点模糊为一个包含至少 k 个不同用户的“隐形”区域。但是，一旦这个可信的匿名服务器被黑客攻破，便会造成大范围的用户隐私引息泄露。
2.3.2 分布式隐私保护技术
集中式结构暴露出的缺点使得现在的隐私保护技术越来越朝着分布式结构发展。分布式结构，顾名思义就是将集中式结构中的泛化和扰动操作从第三方匿名服务器移动到了用户终端中来进行。该技术所采用的时空泛化方法为经过一些研究者改进过的基于k-匿名的模糊化隐私保护技术。同时也出现了基于非 k-匿名的分布式技术，如Space Twist[18]随机选择锚点取代用户的真实位置向LBS服务器发起多轮增量近邻查询，每个用户根据自己的真实位置和增量近邻查询结果在移动终端上计算得到精确的查询结果。
2.4 用户地理位置的隐蔽化
隐蔽化是指通过从 LBS 服务器上完全删除和隐藏用户的信息或是 LBS 查询以达到保护用户隐私的目的。核心思想为：用户请求 LBS 时不时向 LBS 服务器发送查询，而是向自己附近的其他终端或代理请求位置查询信息，从而对 LBS 服务器实现了隐蔽查询，最大化了用户的位置隐私。文献[19]首先提出了隐蔽化方法，即将自己具体的地理位置信息发送给其他正在进行类似操作的物理地址最近的终端。在信息有效期内，可以经过多次转发，用户可以通过无线P2P、有线方式等多种通讯传输方式进行多次交互。但因未充分考虑用户的移动模型，而造成其实用性大打折扣。最近，他们使用位置区域集合上的离散隐马尔可夫链形式化了用户的移动模型，极大地提高了方法的实用性[20]。[蔽化技术采用分布式结构，使用攻击者的期望估计误差来量化位置隐私。
3 加密扭曲算法的改进
原有加密扭曲算法都是把用户的完整地理位置信息上传给LBS服务器用于解析数据，或是LBS服务器把完整的反馈信息传送给用户。这样都会给用户的个人位置隐私信息带来巨大的安全隐患，黑客一旦截取到用户的地理位置请求信息或是LBS服务器反馈给用户的信息，通过一些技术手段进行破解后都会获取到用户完整的个人位置隐私信息。
3.1 利用优化后的坐标转换方法处理源信息
本文决定引入坐标转换方法对用户地理位置坐标进行处理。其核心思想为：基于传统的k-匿名方法，在现有 LBS 系统结构的基础上，增加一个坐标转换机制，将用户发送给服务器端的地理位置信息全部经过坐标变换。LBS服务器接收到用户发送的经过坐标转换后的地理位置后，将相应的应答反馈给用户的移动终端。坐标变换参数由用户的个人终端随机产生，也就只有用户自己可以反向计算得出真实坐标，而匿名服务器因不知道坐标变换参数，故无法反向计算出用户的真实坐标，从而提高了系统的安全性[21]。坐标转换公式为以下式（1），其中x，y分别代表用户真实位置横纵坐标，x′，y′分别代表转换后的横纵坐标：
原算法中参数发生器为固定时间更新，如设定3 min为更新频率，这样存在很大的安全隐患，一旦黑客破解了坐标转换算法并获取到了更新频率，则该加密方法将形同虚设，白白浪费大量的性能开销。而且原算法是由第三方可信的匿名服务器负责坐标转换，仍然存在泄密可能。
因此，本文提出优化后的用户地理位置坐标转换方法。坐标转换算法改在用户终端上运行，并且在原参数发生器中添加时间参数t，时间参数t是由用户终端产生的随机数，其决定着参数发生器下次更新时间。改进后的参数发生器为，黑客即便掌握了参数发生器的参数产生算法，但由于无从得知关键参数t，因而无法破解LBS信息得到用户真实地理位置坐标。
3.2 用户位置请求信息碎片化处理
在用户的移动终端向LBS服务器进行地理位置请求之前，把用户的位置信息进行碎片化处理，并将碎片进行打包处理合成为一个看似完整的位置信息发送给不同的LBS服务器。每个LBS服务器仅仅可以获取到部分用户位置，例如：LBS服务器所实际得到的是用户所在的某个模糊区域Si，每个区域Si 中都包含有用户的确切位置区域loc的部分信息，却无法确认用户所在精确位置坐标。当LBS服务器将用户的地理位置区域信息回传给用户终端后，用户终端负责合成这些区域Si，剔除掉重叠、无用的未知区域信息，提取有用的用户位置信息碎片并进行合成，从而得到用户的精确定位的地理位置。该方法的优点首先是提高了安全性，即使黑客攻陷了一个LBS服务器或截取到一条用户的位置请求信息，只会得到错误的位置坐标或是一个模糊的区域；另外就是用户的地理位置信息是由多个LBS服务器共同得出来的，这样可以提高定位精度，避免LBS服务器的错误反馈信息。
3.3 哑元方式的隐私保护技术的优化
哑元应该由用户终端根据后台规则库中的规则随机产生哑元，规则库会时常进行更新，防止被他人破解。每个哑元将仅仅被使用一次，使用完毕后将被销毁作废，以防被恶意跟踪。并且，每个哑元都可以作为独立的用户地理位置请求与用户真实的地理位置请求共同发送给LBS服务器，LBS服务器无法判断该请求的来源是哑元，还是真实的用户，因此进一步提高了用户位置随机化方法的安全性。 3.4 假名技术的改进
哑元以及真实的用户地理位置请求都将会使用假的用户标签，以便隐藏真实的用户身份。这些假的用户标签是有后台中专门的用户标签库随机产生，经过用户终端的一些处理，会随机替换覆盖掉原有真实的用户标签（用户名、登录账号、IP地址、MAC地址等），再发送给LBS服务器。这些用户标签使用完毕后立即作废，并且回收到后台标签库之中继续供其他用户使用。
4 仿真实验与结果分析
本文算法主要采用C++语言实现，实验的硬件环境为3.40GHz的 Intel Core i5 CPU，8GB RAM，操作系统为 Microsoft Windows 7。
在本次实验中，主要使用的是Thomas Brinkhoff的Network-based Generator of Moving Object用于在地图上产生用户移动的轨迹，地图数据使用的是德国的oldenburgGen城市的地图数据，研究节点分布密度及运行轨迹情况和虚假位置节点与原真实节点间距离d（q，q′）以检验算法的安全性能。如图4所示为模拟生成的节点运行轨迹，其中移动对象最大级别为100，最大移动速度为200，其余采用默认值。
本文先后选取了节点数目100、200、500、1000、5000、10000、50000，作为实验参数进行了仿真实验，运行了算法，计算了虚假位置节点与原真实节点间距离d（q，q′），实现了对原坐标的扭曲与坐标转换，选取适量锚点进行分析，“节点”轨迹发生了偏移。假设攻击者成功截取到了某一时刻用户的位置请求信息，但是得到的只是经过转换的位置坐标，且不同时间的坐标是不同的，增加了追踪难度。如表2所示，为经过坐标转换后t1，t2时刻的坐标及真实位置坐标的实验结果。可见坐标发生偏移，如果对同一个节点连续追踪，可以发现节点较真实轨迹发生较大偏移。
式（2）用于度量位置隐私保护的效果。熵值越大，则攻击者判断出用户的准确位置的不确定性程度越大，即隐私保护效果越好[22]。设攻击者判断出匿名集中每个用户i的位置请求信息的概率为Pi，k表示匿名用户数，则可表示为
如图6所示，为改进后与原算法的实验结果分析的图表。
由图可直观看出，经改进后，信息熵较原算法相比增大，即攻击者判断出用户准确位置的不确定性增大，对用户的位置隐私保护程度优于原算法。
5 结 论
介绍了几种传统的个人位置隐私保护方法，并结合大数据时代的特点，分析了时下比较流行的政策法、扭曲法、加密法各自的缺点，对相对适中的加密扭曲算法进行了详细的介绍。笔者通过分析加密扭曲位置隐私保护技术的缺陷与不足之处，在原算法的基础上从引入坐标转换方法、碎片化用户地理位置请求信息和对哑元技术与假名技术的改进这四个方面进行了适当地优化和改进。改进后的算法进一步加强了对用户个人位置隐私的加密与保护，增加了破解难度，提高了用户地理位置坐标的准确性，而且通过仿真实验验证了改进后的个人位置隐私保护方法的有效性与优越性。
参 考 文 献：
[1]NAISBITT J. Megatrends： Ten New Directions Transforming Our Lives[J]. Houston Lawyer， 1984.
[2]刘雅辉， 张铁赢， 靳小龙，等. 大数据时代的个人隐私保护[J]. 计算机研究与发展， 2015， 52（1）：229-247.
[3]赵君. 基于最远距离到达时间差的手机室内定位方法[J]. 哈尔滨理工大学学报， 2017， 22（4）：34-39.
[4]中国互联网络信息中心. 2015 年中国手机网民网络安全状况报告 [EB/OL]. [2016-10-12].http：//www.cnnic.net.cn/hlwfzyj/hlwxzbg/ydhlwbg/201610/P020161012494271880676.pdf
[5]DCCI互联网数据中心. 2016年中国Android手机隐私安全报告 [EB/OL]. http：//www.dcci.com.cn/media/download/2716b7369ac4a744c842683ec1a89e718c74.pdf
[6]CHRISTIN D， REINHARDT A， KANHERE S S， et al. A Survey on Privacy in Mobile Participatory Sensing Applications[J]. Journal of Systems & Software， 2011， 84（11）：1928-1946.
[7]陈宝远， 孙宇思， 陈光毅，等. 一种基于卡尔曼滤波的动态目标GPS定位算法[J]. 哈尔滨理工大学学报， 2016， 21（4）：1-6.
[8]FREUDIGER J， MANSHAEI M H， HUBAUX J P， et al. On Non-cooperative Location Privacy： a Game-theoretic Analysis[C]// ACM Conference on Computer and Communications Security. ACM， 2009：324-337.
[9]SHOKRI R， REZA A， THEODORAKOPOULOS G， et al. Protecting Location Privacy： Optimal Strategy Against Localization Attacks[J]. Ccs， 2015：617-627.
[10]SAMARATI P， SWEENEY L. Generalizing Data to Provide Anonymity When Disclosing Information （abstract）[C]// Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM， 1998：188. [11]GRUTESER M， GRUNWALD D. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking[C]// International Conference on Mobile Systems. 2003：31-42.
[12]DWORK C. Differential Privacy： A Survey of Results[M]// Theory and Applications of Models of Computation. Springer Berlin Heidelberg， 2008：1-19.
[13]杜瑞颖， 王持恒， 何琨，等. 智能移动终端的位置隐私保护技术[J]. 中兴通讯技术， 2015（3）：23-29.
[14]张学军， 桂小林， 伍忠东. 位置服务隐私保护研究综述[J]. 软件学报， 2015， 26（9）：2373-2395.
[15]SHOKRI R， THEODORAKOPOULOS G， DANEZIS G， et al. Quantifying Location Privacy： The Case of Sporadic Location Exposure[M]// Privacy Enhancing Technologies. Springer Berlin Heidelberg， 2011：57-76.
[16]周丽丽， 王金玉， 孙晶. 大数据中位置服务的隐私保护方法的研究[J]. 自动化技术与应用， 2016， 35（8）：37-42.
[17]HAN J. Mining Frequent Patterns Without Candidate Generation[J]. Acm Sigmod Record， 2000， 29（2）：1-12.
[18]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[J]. Icde， 2008：366-375.
[19]SHOKRI R， PAPADIMITRATOS P， THEODORAKOPOULOS G， et al. Collaborative Location Privacy[C]// 2011 Eighth IEEE International Conference on Mobile Ad-Hoc and Sensor Systems. IEEE Computer Society， 2011：500-509.
[20]SHOKRI R， THEODORAKOPOULOS G， PAPADIMITRATOS P， et al. Hiding in the Mobile Crowd： LocationPrivacy Through Collaboration[J]. IEEE Transactions on Dependable & Secure Computing， 2014， 11（3）：266-279.
[21]林少， 叶阿勇， 许力. 基于坐标变换的k匿名位置隐私保护方法[J]. 小型微型计算机系统， 2016， 37（1）：119-123.
[22]赵大鹏， 梁磊， 田秀霞，等. LBS的隐私保护：模型与进展[J]. 华东师范大学学报（自然科学版）， 2015（5）：28-45.
