張釗 華景煜

摘要 基于指紋識別的定位是最流行的室內(nèi)定位方法.在離線階段，服務(wù)器測量指紋，比如來自特定空間已知位置的不同接入點（AP）的接收信號強(qiáng)度（RSS），測量后服務(wù)器將測量結(jié)果保存在數(shù)據(jù)庫中；在線上階段，用戶同時向服務(wù)器發(fā)送他當(dāng)前指紋的測量結(jié)果以及位置查詢請求，服務(wù)器將在數(shù)據(jù)庫中查找與測量結(jié)果最接近的指紋.雖然這種方法已經(jīng)被研究了很久，但現(xiàn)有的工作并沒有考慮2個隱私要求：供應(yīng)商希望保護(hù)他們花大代價收集的指紋，用戶想要對服務(wù)器保留他們的指紋測量結(jié)果，以避免泄漏位置.為了實現(xiàn)隱私保護(hù)，本文提出一種使用加密技術(shù)的指紋匹配方案，這個方案在加密情況下計算由用戶測量的指紋與服務(wù)器存儲的指紋的距離，服務(wù)器存儲的指紋在這一過程中仍處于密文空間.本文證明了這個方案在進(jìn)行單點定位時能夠很好地保證兩者的隱私要求.為了減少高昂的時間開銷，本文還提出了一個基于網(wǎng)格劃分的改進(jìn)方案，以及以有限的隱私損失為代價的擴(kuò)展方案.為加強(qiáng)安全性，最后提出了有效對抗特定攻擊的對策，在這種攻擊中惡意用戶可以通過重復(fù)定位獲得服務(wù)器存儲的指紋.使用公眾 RSS指紋數(shù)據(jù)集的擴(kuò)展實驗結(jié)果顯示本文方案足以在實現(xiàn)實時定位的同時保留定位精度.

關(guān)鍵詞 基于指紋定位；室內(nèi)定位；隱私保護(hù)

中圖分類號O429

文獻(xiàn)標(biāo)志碼A

0 引言

室內(nèi)定位對于眾多基于位置的手機(jī)應(yīng)用來說非常關(guān)鍵.在現(xiàn)有的室內(nèi)定位方法中，Wi-Fi信號指紋由于其高精度最受關(guān)注[1].這種方法通常由2個階段組成：訓(xùn)練階段和使用階段.在訓(xùn)練階段，服務(wù)提供商測量指紋，即來自多個接入點（APs）的Wi-Fi信號強(qiáng)度，在空間中進(jìn)行多個位置采樣并將其存儲在數(shù)據(jù)庫中.指紋也可能包括其他環(huán)境特征，如采樣點的聲音、光線、顏色等[2-3].在使用階段，當(dāng)用戶定位自己的時候，同樣采集關(guān)于他現(xiàn)在位置的指紋，然后要求數(shù)據(jù)庫中最匹配的指紋，并根據(jù)返回的指紋來估算他的位置.由于指紋數(shù)據(jù)庫不容易構(gòu)建，服務(wù)者通常把他們作為機(jī)密，出于商業(yè)利益考量不愿意將這些數(shù)據(jù)公布于眾，因此他們通常將指紋數(shù)據(jù)庫放在他們完全控制的中央服務(wù)器上.用戶被要求將測量數(shù)據(jù)上傳到服務(wù)器而服務(wù)商會返回一個最接近的數(shù)據(jù)給他們，用戶沒有任何權(quán)限來直接訪問數(shù)據(jù)庫.然而這種方法雖然保護(hù)了服務(wù)商的利益，但是由于服務(wù)商可以完全跟蹤用戶的位置軌跡，用戶會擔(dān)憂自己的隱私問題.因此理想的基于指紋識別的方案應(yīng)該同時保護(hù)服務(wù)提供商和用戶的隱私.這個任務(wù)具有挑戰(zhàn)性，因為用戶隱私和服務(wù)商的隱私在大多數(shù)時間內(nèi)是沖突的，據(jù)我們所知目前的方案都沒有考慮這個問題.在本文中，我們試圖提出一種基于加密的高效率的保密方案來填補(bǔ)這方面的空白.主要工作如下：

首先提出了一種基礎(chǔ)的保護(hù)隱私的指紋匹配方案.這種方案使用ElGamal加密方案[4]經(jīng)過全同態(tài)方案來計算用戶測量的指紋和服務(wù)器存儲的指紋之間的距離，這一過程中服務(wù)器的指紋仍然是加密的.

我們隨后修改了基本方案，通過損失一點隱私的代價減少時間消耗.我們將原始空間在地理位置上劃分為n個大小類似的網(wǎng)格，記錄每個網(wǎng)格的中心指紋.用戶想要找到自己的時候先通過秘密比對他的指紋和每個中心的指紋來決定他屬于哪個網(wǎng)格.由于這個方案不需要與服務(wù)器的所有指紋比較，因此時間開銷顯著降低.此外，因為服務(wù)器只知道用戶屬于這k個區(qū)域的某一個，因此只要用戶不會頻繁發(fā)起請求，用戶只會丟失有限的隱私.

但是上述2個假設(shè)都難以在現(xiàn)實世界中得到保證，所以我們提出進(jìn)一步的方案來改進(jìn)這些沖突.使用聚類技術(shù)自動分類指紋來代替手工劃分網(wǎng)格，可以大大降低定位錯誤.如果一個用戶經(jīng)常執(zhí)行定位，并始終使用隨機(jī)策略選擇虛擬網(wǎng)格，惡意服務(wù)商可以將他運(yùn)動的一些特征以及選取的多個定位相關(guān)聯(lián)，在短期內(nèi)確定他真正的所處的網(wǎng)格.我們提出有效的對策來抵御這種關(guān)聯(lián)攻擊.基礎(chǔ)方案和改進(jìn)方案都需要服務(wù)商將數(shù)據(jù)庫中的指紋對應(yīng)位置公開，這可能仍會損害服務(wù)商的隱私，因此我們設(shè)計了第3個擴(kuò)展方案來解決這個問題.之后，研究了重復(fù)定位攻擊，并且提出了一個針對基于聚類的設(shè)計方案的改進(jìn)方案，可使惡意用戶很難通過少量的定位來獲得服務(wù)器的指紋數(shù)據(jù).

最后，本文進(jìn)行了大量的實驗來評估方案的表現(xiàn)，使用了大概1 000個真實的公共數(shù)據(jù)集，展示了改進(jìn)方案以及基于聚類的改進(jìn)方案都可以在1 s內(nèi)完成一次定位，并且指紋集的提升對于時間開銷提高不大，因此對于更大的空間具有良好的擴(kuò)展性.結(jié)果顯示只要在集合中引入一些重疊，基于聚類的擴(kuò)展可以正確找到95%以上的最接近指紋.我們還實際測量了對重復(fù)定位攻擊的影響，實驗結(jié)果顯示了本文方案顯著增加了攻擊者獲得服務(wù)器指紋的難度，而付出的定位精度損失可以忽略不計.

本文的其他部分安排如下：第1部分描述相關(guān)工作；第2部分給出了基于指紋定位的隱私問題的正式定義；第3部分展示了使用同態(tài)加密的基礎(chǔ)隱私方案；第4部分提出了權(quán)衡效率和隱私的改進(jìn)方案；第5部分描述了3個擴(kuò)展；第6部分講述了重復(fù)定位攻擊；第7部分展示了實驗結(jié)果以及評估；第8部分進(jìn)行了總結(jié).

1 相關(guān)工作

定位相關(guān)的隱私保護(hù)在近幾年的研究中成果非常多，然而大多數(shù)工作都集中在基于位置的服務(wù)（LBS）中的用戶位置保護(hù)上，而對于用戶定位過程沒有研究.在這部分我們會總結(jié)一下目前在基于位置服務(wù)（LBS）中的位置隱私保護(hù)機(jī)制（LPPMs），這可能會給我們設(shè)計保護(hù)用戶位置的定位系統(tǒng)一些啟發(fā).

在基于位置服務(wù)中，用戶被要求將他的位置提交給服務(wù)商，服務(wù)商會基于位置提供一些后續(xù)服務(wù)，比如說常用的地圖服務(wù).基于位置服務(wù)中的位置隱私保護(hù)機(jī)制（LPPMs）的目標(biāo)是在使用戶能夠使用這些服務(wù)的同時盡可能少地暴露位置信息[5]，這與我們允許用戶獲取服務(wù)器的最接近指紋的同時保護(hù)用戶自身指紋信息的目標(biāo)很相似.

現(xiàn)在最流行的LPPMs工作是在用戶上傳位置信息到服務(wù)器之前進(jìn)行混淆[6-9]，這樣會導(dǎo)致定位精度有損失，這在對精度要求更高的室內(nèi)定位中可能難以接受.在另一類的LPPMs工作中通過混淆區(qū)域來隱藏用戶的位置[10-11]，此種方案的資源開銷非常高昂.還有一種類型的LPPMs工作是在實際服務(wù)請求發(fā)起的同時發(fā)起幾個虛假請求來干擾惡意服務(wù)提供商[12]，這種方法的局限之處在于當(dāng)用戶對于數(shù)據(jù)庫中的指紋結(jié)構(gòu)不能完全了解的情況下，偽造的指紋很容易被攻擊者過濾掉虛假請求.最后一種類型的LPPMs采用加密技術(shù)隱藏用戶隱私[13-15]，該種機(jī)制的關(guān)鍵思想是利用一些同態(tài)加密來將涉及位置的計算變?yōu)槊芪目臻g的計算，從而不泄露原始值.本文使用最后一種方法來實現(xiàn)指紋定位中的隱私保護(hù)，其最大的挑戰(zhàn)是怎樣設(shè)計一種方法實現(xiàn)模糊指紋從明文空間到密文空間的映射.此外，很多高級匹配算法在密文空間中都無法使用，因此時間開銷通常非常高.

在5.2中，我們使用聚類技術(shù)來自動對指紋進(jìn)行分組以此減少需要匹配的指紋數(shù)量，這種方法最初由Swangmuang等[16]提出.他們使用這種技術(shù)來減少基于指紋的室內(nèi)定位分析模型的計算量.Altintas等[17]使用聚類來改進(jìn)定位漏洞，但是都沒有涉及本文在5.2中提出的問題.

7 結(jié)果評估

在這一部分使用真實的RSS指紋數(shù)據(jù)集來評估本文基礎(chǔ)方案和改進(jìn)方案的表現(xiàn).我們使用JCE框架[18]和Bouncy Castle 庫（http：∥www.bouncycastle.org/）來實現(xiàn)ElGamal方案，并使用了ICDM07 DMC[19]的公開數(shù)據(jù)集來作為我們的指紋數(shù)據(jù)庫內(nèi)容.這個數(shù)據(jù)集包含了1 400個帶位置標(biāo)簽的指紋，這些指紋都由同一個設(shè)備在同一建筑的200個不同地點采集.每個位置被劃分為1.5 m×1.5 m的網(wǎng)格，每個位置都采集了幾個不同的指紋.我們使用了256 bit長度的密鑰.

7.1 時間效率

首先計算基礎(chǔ)方案、劃分網(wǎng)格的改進(jìn)方案以及基于聚類的改進(jìn)方案的時間效率.聚類的改進(jìn)方案中，將所有的指紋聚類結(jié)果劃分為15個組，每一分組的指紋數(shù)量都在40～70之間，每2個分組之間都有大概10個元素的交集.我們在2個實驗中都選擇了4個混淆網(wǎng)格或者分組.用戶指紋都是從數(shù)據(jù)集中隨機(jī)提取的，所有的數(shù)據(jù)都是經(jīng)過10次實驗得出的結(jié)果.

分別計算離線階段和使用階段服務(wù)商和用戶的時間開銷.離線階段3個方法的開銷都一致，經(jīng)過實驗統(tǒng)計，離線階段用戶的時間消耗大概為1 s，服務(wù)器端的時間消耗大概為16 s.因為這是在使用之前部署的，所以這些時間消耗并不重要.圖3給出了使用階段的時間開銷，可見改進(jìn)方案顯著提高了時間效率，用戶可以在1 s以內(nèi)使用2個方案獲得他的位置，而基礎(chǔ)方案需要大約2 s的時間.

為了研究指紋數(shù)據(jù)庫對時間的影響，將數(shù)據(jù)集從500逐步增加到800，圖4給出了新的時間消耗.圖4顯示這一時間的增加是線性的，這與理論一致.

7.2 定位精度

除了效率以外還對定位精度的影響做了統(tǒng)計，顯然決定能否準(zhǔn)確定位的因素是能否找到距離用戶測量的指紋最接近的數(shù)據(jù)庫指紋.對每個實驗都找了一個數(shù)據(jù)庫的指紋當(dāng)作用戶測量的指紋，觀察能否準(zhǔn)確找到與他最接近的指紋.一開始，在網(wǎng)格的改進(jìn)方案和聚類的改進(jìn)方案中都不允許不同的網(wǎng)格或者分組中有交集元素.圖5給出了3種方案的準(zhǔn)確率，基礎(chǔ)方案準(zhǔn)確率最高，而基于聚類的方案要優(yōu)于基于網(wǎng)格的方案，這與我們在基于聚類的方案中所預(yù)測的一致.

隨后，允許網(wǎng)格或者分組中存在交集元素來改進(jìn)準(zhǔn)確率，我們嘗試放寬目標(biāo)指紋與中心指紋的距離閾值θ來決定一個指紋能否落入一個分組中.圖6給出了隨著θ的變化基于網(wǎng)格的方案和基于聚類的方案準(zhǔn)確率的變化曲線.不過采用這種冗余設(shè)計會降低方案的時間效率，可以看到即使不采用這種設(shè)計，基于聚類的改進(jìn)方案仍然有超過95%的準(zhǔn)確率.

7.3 對重復(fù)定位攻擊的防御

第6部分提出了對于重復(fù)定位攻擊的防御策略，我們在基于聚類的方案中實現(xiàn)了這一策略來評估對于定位精度的真實影響.首先模擬一個知道每個分組的非零特征與這個分組的指紋的攻擊者，這個攻擊者想要依靠這些信息來獲取服務(wù)器的指紋.因為他知道每個組的指紋的非零特征，因此他只要知道這些特征的值就可以了.但是通過我們的防守策略，他可能會得到關(guān)于這些特征的錯誤值.

圖7給出了使用防御策略后攻擊者所需要發(fā)起的定位次數(shù)與共計有效的數(shù)量，發(fā)現(xiàn)當(dāng)p<70%時80%以上的指紋需要攻擊者進(jìn)行100 000以上的定位才能破解，這對于攻擊者來說并不現(xiàn)實.

8 總結(jié)

基于指紋的信號強(qiáng)度的定位是室內(nèi)定位中最流行的技術(shù)，然而現(xiàn)有的工作并沒有解決這個技術(shù)帶來的隱私性問題：用戶必須上傳他的信息到服務(wù)器，服務(wù)器可以輕易定位追蹤他.本文使用戶可以在保護(hù)自己測量指紋數(shù)據(jù)的前提下借助服務(wù)器完成定位，而且在這個過程中服務(wù)商也不需要擔(dān)心自己數(shù)據(jù)庫的指紋泄露.首先提供了一個基礎(chǔ)的基于ElGamal加密的方案來使用戶和服務(wù)商在隱私安全的情況下進(jìn)行指紋計算和匹配；隨后為了減少時間開銷和提高準(zhǔn)確度，又提出了擴(kuò)展的解決方案；最后為了加強(qiáng)服務(wù)器的安全性，給出了一個有效的針對重復(fù)定位攻擊的防御方案.實驗結(jié)果證明了本文方案在使用效率和定位精度上都具有很好的可用性.

參考文獻(xiàn)

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