基于指紋識別的室內定位中的隱私保護

張釗 華景煜

摘要 基于指紋識別的定位是最流行的室內定位方法.在離線階段，服務器測量指紋，比如來自特定空間已知位置的不同接入點（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