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

高喜龍，袁 健，許能闖

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

0 引言

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

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

1 相關(guān)工作

當(dāng)前LBS位置隱私保護策略分為基于政策法的位置隱私保護技術(shù)、基于加密法的LBS隱私保護技術(shù)和基于扭曲法的LBS位置隱私保護技術(shù)。

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

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

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

2 MBG算法

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

圖1 MBG算法流程

(1)在當(dāng)前LBS服務(wù)器負(fù)責(zé)區(qū)域內(nèi)，按照Hibert-Curve將當(dāng)前區(qū)域內(nèi)所有用戶排序形成Hibert空間，所有用戶獲得唯一標(biāo)識符。

(2)根據(jù)用戶標(biāo)識符形成基于Chord的用戶自組織網(wǎng)絡(luò)。

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

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

用戶指定的距離參數(shù)ξ應(yīng)滿足Geo-Indistinguishability：

(1)

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

3 實驗分析

從服務(wù)質(zhì)量與隱私保護度對比MobiHide與MBG對用戶位置隱私的保護效果。實驗數(shù)據(jù)來源于舊金山港灣區(qū)，由基于網(wǎng)絡(luò)的移動對象生成器構(gòu)成[9]。本實驗單機環(huán)境為Inter(R) Core(TM) i7 CPU 3.4GHz，8GB內(nèi)存，Window10操作系統(tǒng)。

3.1 實驗評價指標(biāo)

3.1.1 服務(wù)質(zhì)量

隱私保護服務(wù)質(zhì)量由響應(yīng)時間、查詢結(jié)果的準(zhǔn)確性衡量。在相同隱私保護度下，移動對象獲得的服務(wù)質(zhì)量越高,說明隱私保護技術(shù)越好。

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

(2)

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

(3)

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

APOUQ=n

(4)

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

(5)

3.1.2 隱私保護度

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

(6)

3.2 實驗結(jié)果分析

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

表1 算法模型實驗對比使用參數(shù)

3.2.1 服務(wù)質(zhì)量

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

圖2 平均服務(wù)響應(yīng)時間對比

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

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

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

3.2.2 隱私保護度

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

圖4 隱私披露情況統(tǒng)計

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

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

4 結(jié)語

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