基于指纹识别的室内定位中的隐私保护

张钊 华景煜

摘要 基于指纹识别的定位是最流行的室内定位方法.在离线阶段，服务器测量指纹，比如来自特定空间已知位置的不同接入点（AP）的接收信号强度（RSS），测量后服务器将测量结果保存在数据库中；在线上阶段，用户同时向服务器发送他当前指纹的测量结果以及位置查询请求，服务器将在数据库中查找与测量结果最接近的指纹.虽然这种方法已经被研究了很久，但现有的工作并没有考虑2个隐私要求：供应商希望保护他们花大代价收集的指纹，用户想要对服务器保留他们的指纹测量结果，以避免泄漏位置.为了实现隐私保护，本文提出一种使用加密技术的指纹匹配方案，这个方案在加密情况下计算由用户测量的指纹与服务器存储的指纹的距离，服务器存储的指纹在这一过程中仍处于密文空间.本文证明了这个方案在进行单点定位时能够很好地保证两者的隐私要求.为了减少高昂的时间开销，本文还提出了一个基于网格划分的改进方案，以及以有限的隐私损失为代价的扩展方案.为加强安全性，最后提出了有效对抗特定攻击的对策，在这种攻击中恶意用户可以通过重复定位获得服务器存储的指纹.使用公众 RSS指纹数据集的扩展实验结果显示本文方案足以在实现实时定位的同时保留定位精度.

关键词 基于指纹定位；室内定位；隐私保护

中图分类号O429

文献标志码A

0 引言

室内定位对于众多基于位置的手机应用来说非常关键.在现有的室内定位方法中，Wi-Fi信号指纹由于其高精度最受关注[1].这种方法通常由2个阶段组成：训练阶段和使用阶段.在训练阶段，服务提供商测量指纹，即来自多个接入点（APs）的Wi-Fi信号强度，在空间中进行多个位置采样并将其存储在数据库中.指纹也可能包括其他环境特征，如采样点的声音、光线、颜色等[2-3].在使用阶段，当用户定位自己的时候，同样采集关于他现在位置的指纹，然后要求数据库中最匹配的指纹，并根据返回的指纹来估算他的位置.由于指纹数据库不容易构建，服务者通常把他们作为机密，出于商业利益考量不愿意将这些数据公布于众，因此他们通常将指纹数据库放在他们完全控制的中央服务器上.用户被要求将测量数据上传到服务器而服务商会返回一个最接近的数据给他们，用户没有任何权限来直接访问数据库.然而这种方法虽然保护了服务商的利益，但是由于服务商可以完全跟踪用户的位置轨迹，用户会担忧自己的隐私问题.因此理想的基于指纹识别的方案应该同时保护服务提供商和用户的隐私.这个任务具有挑战性，因为用户隐私和服务商的隐私在大多数时间内是冲突的，据我们所知目前的方案都没有考虑这个问题.在本文中，我们试图提出一种基于加密的高效率的保密方案来填补这方面的空白.主要工作如下：

首先提出了一种基础的保护隐私的指纹匹配方案.这种方案使用ElGamal加密方案[4]经过全同态方案来计算用户测量的指纹和服务器存储的指纹之间的距离，这一过程中服务器的指纹仍然是加密的.

我们随后修改了基本方案，通過损失一点隐私的代价减少时间消耗.我们将原始空间在地理位置上划分为n个大小类似的网格，记录每个网格的中心指纹.用户想要找到自己的时候先通过秘密比对他的指纹和每个中心的指纹来决定他属于哪个网格.由于这个方案不需要与服务器的所有指纹比较，因此时间开销显著降低.此外，因为服务器只知道用户属于这k个区域的某一个，因此只要用户不会频繁发起请求，用户只会丢失有限的隐私.

但是上述2个假设都难以在现实世界中得到保证，所以我们提出进一步的方案来改进这些冲突.使用聚类技术自动分类指纹来代替手工划分网格，可以大大降低定位错误.如果一个用户经常执行定位，并始终使用随机策略选择虚拟网格，恶意服务商可以将他运动的一些特征以及选取的多个定位相关联，在短期内确定他真正的所处的网格.我们提出有效的对策来抵御这种关联攻击.基础方案和改进方案都需要服务商将数据库中的指纹对应位置公开，这可能仍会损害服务商的隐私，因此我们设计了第3个扩展方案来解决这个问题.之后，研究了重复定位攻击，并且提出了一个针对基于聚类的设计方案的改进方案，可使恶意用户很难通过少量的定位来获得服务器的指纹数据.

最后，本文进行了大量的实验来评估方案的表现，使用了大概1 000个真实的公共数据集，展示了改进方案以及基于聚类的改进方案都可以在1 s内完成一次定位，并且指纹集的提升对于时间开销提高不大，因此对于更大的空间具有良好的扩展性.结果显示只要在集合中引入一些重叠，基于聚类的扩展可以正确找到95%以上的最接近指纹.我们还实际测量了对重复定位攻击的影响，实验结果显示了本文方案显著增加了攻击者获得服务器指纹的难度，而付出的定位精度损失可以忽略不计.

本文的其他部分安排如下：第1部分描述相关工作；第2部分给出了基于指纹定位的隐私问题的正式定义；第3部分展示了使用同态加密的基础隐私方案；第4部分提出了权衡效率和隐私的改进方案；第5部分描述了3个扩展；第6部分讲述了重复定位攻击；第7部分展示了实验结果以及评估；第8部分进行了总结.

1 相关工作

定位相关的隐私保护在近几年的研究中成果非常多，然而大多数工作都集中在基于位置的服务（LBS）中的用户位置保护上，而对于用户定位过程没有研究.在这部分我们会总结一下目前在基于位置服务（LBS）中的位置隐私保护机制（LPPMs），这可能会给我们设计保护用户位置的定位系统一些启发.

在基于位置服务中，用户被要求将他的位置提交给服务商，服务商会基于位置提供一些后续服务，比如说常用的地图服务.基于位置服务中的位置隐私保护机制（LPPMs）的目标是在使用户能够使用这些服务的同时尽可能少地暴露位置信息[5]，这与我们允许用户获取服务器的最接近指纹的同时保护用户自身指纹信息的目标很相似.

现在最流行的LPPMs工作是在用户上传位置信息到服务器之前进行混淆[6-9]，这样会导致定位精度有损失，这在对精度要求更高的室内定位中可能难以接受.在另一类的LPPMs工作中通过混淆区域来隐藏用户的位置[10-11]，此种方案的资源开销非常高昂.还有一种类型的LPPMs工作是在实际服务请求发起的同时发起几个虚假请求来干扰恶意服务提供商[12]，这种方法的局限之处在于当用户对于数据库中的指纹结构不能完全了解的情况下，伪造的指纹很容易被攻击者过滤掉虚假请求.最后一种类型的LPPMs采用加密技术隐藏用户隐私[13-15]，该种机制的关键思想是利用一些同态加密来将涉及位置的计算变为密文空间的计算，从而不泄露原始值.本文使用最后一种方法来实现指纹定位中的隐私保护，其最大的挑战是怎样设计一种方法实现模糊指纹从明文空间到密文空间的映射.此外，很多高级匹配算法在密文空间中都无法使用，因此时间开销通常非常高.

在5.2中，我們使用聚类技术来自动对指纹进行分组以此减少需要匹配的指纹数量，这种方法最初由Swangmuang等[16]提出.他们使用这种技术来减少基于指纹的室内定位分析模型的计算量.Altintas等[17]使用聚类来改进定位漏洞，但是都没有涉及本文在5.2中提出的问题.

7 结果评估

在这一部分使用真实的RSS指纹数据集来评估本文基础方案和改进方案的表现.我们使用JCE框架[18]和Bouncy Castle 库（http：∥www.bouncycastle.org/）来实现ElGamal方案，并使用了ICDM07 DMC[19]的公开数据集来作为我们的指纹数据库内容.这个数据集包含了1 400个带位置标签的指纹，这些指纹都由同一个设备在同一建筑的200个不同地点采集.每个位置被划分为1.5 m×1.5 m的网格，每个位置都采集了几个不同的指纹.我们使用了256 bit长度的密钥.

7.1 时间效率

首先计算基础方案、划分网格的改进方案以及基于聚类的改进方案的时间效率.聚类的改进方案中，将所有的指纹聚类结果划分为15个组，每一分组的指纹数量都在40～70之间，每2个分组之间都有大概10个元素的交集.我们在2个实验中都选择了4个混淆网格或者分组.用户指纹都是从数据集中随机提取的，所有的数据都是经过10次实验得出的结果.

分别计算离线阶段和使用阶段服务商和用户的时间开销.离线阶段3个方法的开销都一致，经过实验统计，离线阶段用户的时间消耗大概为1 s，服务器端的时间消耗大概为16 s.因为这是在使用之前部署的，所以这些时间消耗并不重要.图3给出了使用阶段的时间开销，可见改进方案显著提高了时间效率，用户可以在1 s以内使用2个方案获得他的位置，而基础方案需要大约2 s的时间.

为了研究指纹数据库对时间的影响，将数据集从500逐步增加到800，图4给出了新的时间消耗.图4显示这一时间的增加是线性的，这与理论一致.

7.2 定位精度

除了效率以外还对定位精度的影响做了统计，显然决定能否准确定位的因素是能否找到距离用户测量的指纹最接近的数据库指纹.对每个实验都找了一个数据库的指纹当作用户测量的指纹，观察能否准确找到与他最接近的指纹.一开始，在网格的改进方案和聚类的改进方案中都不允许不同的网格或者分组中有交集元素.图5给出了3种方案的准确率，基础方案准确率最高，而基于聚类的方案要优于基于网格的方案，这与我们在基于聚类的方案中所预测的一致.

随后，允许网格或者分组中存在交集元素来改进准确率，我们尝试放宽目标指纹与中心指纹的距离阈值θ来决定一个指纹能否落入一个分组中.图6给出了随着θ的变化基于网格的方案和基于聚类的方案准确率的变化曲线.不过采用这种冗余设计会降低方案的时间效率，可以看到即使不采用这种设计，基于聚类的改进方案仍然有超过95%的准确率.

7.3 对重复定位攻击的防御

第6部分提出了对于重复定位攻击的防御策略，我们在基于聚类的方案中实现了这一策略来评估对于定位精度的真实影响.首先模拟一个知道每个分组的非零特征与这个分组的指纹的攻击者，这个攻击者想要依靠这些信息来获取服务器的指纹.因为他知道每个组的指纹的非零特征，因此他只要知道这些特征的值就可以了.但是通过我们的防守策略，他可能会得到关于这些特征的错误值.

图7给出了使用防御策略后攻击者所需要发起的定位次数与共计有效的数量，发现当p<70%时80%以上的指纹需要攻击者进行100 000以上的定位才能破解，这对于攻击者来说并不现实.

8 总结

基于指纹的信号强度的定位是室内定位中最流行的技术，然而现有的工作并没有解决这个技术带来的隐私性问题：用户必须上传他的信息到服务器，服务器可以轻易定位追踪他.本文使用户可以在保护自己测量指纹数据的前提下借助服务器完成定位，而且在这个过程中服务商也不需要担心自己数据库的指纹泄露.首先提供了一个基础的基于ElGamal加密的方案来使用户和服务商在隐私安全的情况下进行指纹计算和匹配；随后为了减少时间开销和提高准确度，又提出了扩展的解决方案；最后为了加强服务器的安全性，给出了一个有效的针对重复定位攻击的防御方案.实验结果证明了本文方案在使用效率和定位精度上都具有很好的可用性.

参考文献

References

[1] Liu H B，Gan Y，Yang J，et al.Push the limit of WIFI based localization for smartphones[C]∥Proceedings of the 18th Annual International Conference on Mobile Computingand Networking，2012：305-316

[2] Azizyan M，Constandache I，Choudhury R R.Surround sense：Mobile phone localization via ambience fingerprinting[C]∥Proceedings of the 15th Annual International Conference on Mobile Computing and Networking，2009：261-272

[3] Tarzia S P，Dinda P A，Dick R P，et al.Indoor localizationwithout infrastructure using the acoustic backgroundspectrum[C]∥Proceedings of the 9th International Conference on Mobile Systems，Applications，and Services，2011：155-168

[4] ElGamal T.A public key cryptosystem and a signature scheme based on discrete logarithms[M].Berlin：Springer，1984：469-472

[5] Wang T，Yang Y.Location privacy protection from RSS localizationsystem using antenna pattern synthesis[C]∥Proceedings of IEEEINFOCOM，2011：2408-2416

[6] Gruteser M，Grunwald D.Anonymous usage of locationbased services through spatial and temporal cloaking[C]∥International Conference on Mobile Systems，Applicationsand Services，2003：31-42

[7] Gedik B，Liu L.Location privacy in mobile systems：A personalized anonymization model[C]∥IEEE International Conference on Distributed Computing Systems，2005：620-629

[8] Hoh B，Gruteser M，Xiong H，et al.Preservingprivacy in GPS traces via uncertainty-aware path cloaking[C]∥ACM Conference on Computer and Communications Security，2007：161-171

[9] Kalnis P，Ghinita G，Mouratidis K，et al.Preventinglocation-based identity inference in anonymous spatial queries[J].IEEE Transactions on Knowledge and Data Engineering，2007，19（12）：1719-1733

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

[11] Beresford A R，Stajano F.Mix zones：User privacy in locationawareservices[C]∥Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshops，2004：127-131

[12] Chow R，Golle P.Faking contextual data for fun，profit，andprivacy[C]∥ACM Workshop on Privacy in the Electronic Society，2009：105-108

[13] Zhong S，Li L，Liu Y G，et al.Privacy-preserving locationbased services for mobile users in wireless networks[R].Yale Computer Science，Tech.Rep.YALEU/DCS/TR-1297，2004

[14] Popa R A，Blumberg A J，Balakrishnan H，et al.Privacy and accountability for location-based aggregate statistics[C]∥ACM Conference on Computer and Communications Security，2011：653-666

[15] Solanas A，Martinez-Balleste A.Privacy protection inlocation-based services through a public-key privacy homomorphism[C]∥European Conference on Public Key Infrastructure：Theory and Practice，2007：362-368

[16] Swangmuang N，Krishnamurthy P V.On clustering RSS fingerprints for improving scalability of performance predictionof indoor positioning systems[C]∥ACM International Workshop on Mobile Entity Localization and Tracking in GPS-less Environments，2008：61-66

[17] Altintas B，Serif T.Improving RSS-based indoor positioningalgorithm via k-means clustering[C]∥11th European Wireless Conference 2011-Sustainable Wireless Technologies，2011：1-5

[18] Weiss J.Java cryptography extensions：Practical guide for programmers[M].San Francisco，CA：Morgan Kaufmann Publishers Inc.，2004

[19] Yang Q，Pan S J，Zheng V W.Estimating location using wi-fi[J].IEEE Intelligent Systems，2008，23（1）：8-13