基于噪聲匿名組的LBS位置隱私保護算法

高喜龍，袁 健，許能闖

(上海理工大學 光電信息與計算機工程學院，上海 200093)

0 引言

移動應用技術發展給人們帶來了眾多便利，基于位置的服務(location based service,LBS)[1]日益受到歡迎。但由于請求LBS時，用戶位置等敏感信息需要向服務商提交，若被不法分子獲取，則可利用成熟的數據處理技術獲得用戶住址、興趣愛好等信息，對LBS用戶造成不可估計的損失[2]。因此，最大限度保護LBS用戶個人信息一直是隱私保護領域的重點研究內容。

為解決LBS的位置隱私問題，產生了以k-匿名[3]為代表的傳統算法模型，然而大量研究證明該類算法無法有效估計攻擊者所擁有的背景知識，因而無法設計出適用于各種場景下的位置隱私保護模型[1]。較新的差分隱私保護[4]無視背景知識，很好地彌補了K匿名在該方向上的缺陷。然而差分隱私在該領域應用較少。文獻[5]以差分隱私為基礎提出的Geo-Indistinguishability算法，是差分隱私在該領域較新的嘗試 ，但其存在對隱私預算[4]過度依賴的問題。針對現有算法無法有效抵抗背景知識攻擊和過度依賴隱私預算現狀，本文提出基于差分隱私的匿名組LBS位置隱私保護算法MBG(MobiHide Based on Geo-Indistinguishability,MBG)。該算法在形成匿名組時，首先經過差分隱私的噪聲過濾，只有滿足差分隱私的用戶才能進入匿名組提交，從而提高了用戶隱私保護效果。

1 相關工作

當前LBS位置隱私保護策略分為基于政策法的位置隱私保護技術、基于加密法的LBS隱私保護技術和基于扭曲法的LBS位置隱私保護技術。

基于政策法的LBS位置隱私保護技術，通過制定一些常用的隱私管理規則和可信任的隱私協定，約束服務提供商公平、安全地使用用戶LBS查詢中的位置信息，如IETF的GeoPriv[6]和W3C的P3P[7]。基于加密法的LBS位置隱私保護技術，通過使用加密技術使用戶查詢信息中的位置信息對LBS服務器不可見，從而達到位置隱私保護目的。如基于隱私信息檢索的LBS隱私保護技術[8]，其實現方法依賴于特定的用戶數據以及復雜的算法及硬件支持；全同態加密技術[9]可在不揭密用戶查詢的前提下返回正確的查詢結果，但其效率很低。因而如何平衡隱私保護與隱私保護實現所需代價間的關系，成為該類算法需要考慮的重點。

基于扭曲法的LBS位置隱私保護技術指在LBS查詢暴露給LBS服務器之前，事先對查詢中的時空信息進行適當的修改或扭曲，使LBS服務器無法獲得精確的位置信息。這類技術的實現往往依賴于攻擊者的先驗知識，易遭受具有數據分布特征等背景知識的攻擊。差分隱私[4]對背景知識不夠敏感，可設計出能夠抵御具有任意背景知識攻擊的隱私保護框架[5,10]。基于扭曲法的LBS位置隱私保護技術與差分隱私概念相結合成為研究熱點。

文獻[11]提出的MobiHide模型以K匿名為基礎，同時為了加快請求服務時的處理速度，參照一種基于希爾伯特曲線[12]的用戶劃分空間[13]，使用戶自組織形成一個基于Chord[14]的自組織網絡，其匿名組的形成仍參照傳統K匿名思想。為提高隱私保護效果，引入差分隱私概念，在形成匿名組時由用戶指定的距離參數過濾用戶組，僅允許符合要求的用戶進入最終的匿名查詢組，從而提升用戶隱私保護效果。

2 MBG算法

為修正傳統以K匿名為基礎的LBS位置隱私保護算法的不足，提出基于差分隱私的用戶位置特性[15]的MBG算法。該算法以傳統的K匿名算法為核心，在形成匿名組時先由用戶指定的隱私保護參數ξ過濾，ξ為差分隱私相關的位置隱私參數。MBG算法流程如圖1所示。

圖1 MBG算法流程

(1)在當前LBS服務器負責區域內，按照Hibert-Curve將當前區域內所有用戶排序形成Hibert空間，所有用戶獲得唯一標識符。

(2)根據用戶標識符形成基于Chord的用戶自組織網絡。

(3)LBS用戶發起LBS請求，若查詢用戶為新用戶，返回步驟(1)；否則，按照K匿名要求形成匿名組。

(4)根據用戶指定的距離參數ξ過濾匿名組內用戶，不符合要求的用戶將被排除，直至達到K個用戶形成匿名組，提交以獲取服務。

用戶指定的距離參數ξ應滿足Geo-Indistinguishability：

(1)

其中，S為攻擊者擁有的背景知識，x為真實用戶，x′為距真實用戶距離不超過ξ的匿名組用戶。公式(1)表達的實際內容為：假定攻擊者可獲得ξ范圍外的當前用戶的所有背景知識，其獲知背景知識前后推斷出用戶真實身份的概率相差值應在與ξ相關的參數因子范圍內。

3 實驗分析

從服務質量與隱私保護度對比MobiHide與MBG對用戶位置隱私的保護效果。實驗數據來源于舊金山港灣區，由基于網絡的移動對象生成器構成[9]。本實驗單機環境為Inter(R) Core(TM) i7 CPU 3.4GHz，8GB內存，Window10操作系統。

3.1 實驗評價指標

3.1.1 服務質量

隱私保護服務質量由響應時間、查詢結果的準確性衡量。在相同隱私保護度下，移動對象獲得的服務質量越高,說明隱私保護技術越好。

(1)響應時間。響應時間指從用戶發出LBS請求至用戶獲取服務的時間，任意選取n位用戶，記用戶Ui的響應時間為ti，對任意算法模型的平均響應時間MT(Mean Time,簡稱MT)，應有：

(2)

(2)查詢結果的準確性。用fi表示用戶的查詢結果，若符合預期標準，即返回的查詢結果與用戶所期望的興趣點一致，記fi=true；否則fi=false；以resulti作為當前用戶查詢結果的統計量，以CROUQ(Coincident Result Of User Query，簡稱CROUQ)表示滿足用戶查詢的興趣點結果，即：

(3)

以APOUQ(Actual Point of User Query,簡稱APOUQ)表示實際用戶請求的興趣點，即實際查詢用戶數目n：

APOUQ=n

(4)

以符合率CP(Coincident Probability，簡稱CP)描述每種算法的最終結果，則：

(5)

3.1.2 隱私保護度

隱私保護度反應LBS隱私保護技術披露隱私多寡的程度，披露風險越小，隱私保護度越高。披露風險與隱私保護算法和攻擊者掌握的背景知識相關。假設攻擊者可以獲得除查詢用戶外的所有信息，以Ui表示用戶查詢結束后攻擊者是否推斷為實際查詢用戶，若攻擊者推斷出用戶真實身份，則Ui=true；否則Ui=false。以Ti作為查詢結果統計量，設每組樣本實際查詢用戶數為n，對于N組樣本，披露風險DR(Disclosure Risk)計算如下：

(6)

3.2 實驗結果分析

表1為3種隱私保護模型的服務質量與隱私保護效果所使用的系統參數：MobiHide[19]是基于k-匿名的位置隱私保護算法的一種，對于地理位置信息上的隱私保護范圍沒有明顯界限。MBG算法參照K匿名思想與由差分隱私擴展而來的Geo-indistinguishability,故額外制定隱私保護距離ξ。此外，為了保證算法的適用性，分別指定k=21,22,…,30，對不同K值的實驗結果采用均值比較。

表1 算法模型實驗對比使用參數

3.2.1 服務質量

(1)響應時間。實驗采用系統參數如表1所示，在不同K值下取10 000位用戶的LBS請求時間統計，按照公式(2)計算兩種位置隱私保護模型的MT，如圖2所示。

圖2 平均服務響應時間對比

(2)查詢結果的準確性。根據公式(5)計算兩種模型的LBS用戶查詢結果，準確性如圖3所示。

圖3 查詢結果與用戶興趣點吻合程度

圖2和圖3結果表明，在不同K值下用戶的服務質量，新提出的MBG算法與原有的MobiHide算法相比，基本滿足用戶的服務需求。

3.2.2 隱私保護度

圖4為根據公式(6)，按照表1給定的實驗參數，MobiHide與MBG對用戶發起LBS查詢時用戶隱私的披露統計情況。

圖4 隱私披露情況統計

從圖4可以看出，在不同K值下，引入了差分隱私的基于MobiHide的MBG算法對于用戶隱私的披露風險，明顯小于使用傳統K匿名思想的匿名組方法。

綜合以上結果，MBG算法在LBS位置隱私保護方面，在保證用戶服務質量的前提下，相較于傳統的K匿名方法，對用戶的位置隱私保護程度明顯提升。

4 結語

本文立足于具有明顯定位優勢的K匿名隱私保護系統，結合差分隱私的相關做法，提出了以克服K匿名無法有效估計攻擊者背景知識缺陷為目的的MBG算法模型。該算法吸取了差分隱私無視攻擊者背景知識的特點，通過設置距離參數以過濾匿名組中不符合該特性的用戶，從而提升隱私保護效果。MBG算法是結合差分隱私在LBS位置隱私保護領域較新的嘗試，但差分隱私在該領域的應用較少，更為完善有效的隱私保護模型尚待研究。