一種用戶自我感知的位置隱私保護算法

葉吉祥 曹文慧

(長沙理工大學計算機與通信工程學院 湖南 長沙 410076)

0 引 言

日常生活中，用戶可以通過第三方軟件使用基于位置服務(Location based service,LBS)[1]來獲取導航服務、緊急救援服務、娛樂信息服務等[2]。在此過程中，如果攻擊者盜取用戶的位置信息或暴露給不可信任的第三方軟件，必然造成嚴重影響。因此，在享有LBS的同時保證用戶的位置隱私成為當前一個研究熱點。

1 研究概述

位置隱私的概念最早由Beresford等[3]提出，自此，國內外許多學者提出了一系列的解決方案。目前,位置隱私保護措施主要有三類[4]:(1) 位置模糊保護法,主要包括位置的偏移、構造假位置等;(2) 引入密碼學的加密方法,對用戶位置進行加密后發送;(3) 制定隱私保護策略,主要針對服務商進行規范和約束。Gruteser等[5]將K-匿名[6]技術用于位置請求服務的隱私保護中從而達到保護目的。文獻[7-10]將K-匿名算法通過構造不同的幾何形狀，產生不同的匿名區域來完成保護。Kim等[11]在未知的數據訪問的情況下執行數據訪問模式,保證了加密數據和用戶查詢記錄的機密性,但是使用TTP結構不能保證中間匿名服務器絕對的安全,且容易造成系統堵塞,必然會產生新的問題。

在位置隱私保護的過程中，不僅要保護用戶的位置信息，還要防止用戶其他私人信息(姓名、愛好等)泄露。周長利等[12]通過構造真實用戶與鄰居用戶的共同特征來形成匿名區域，采取幾何形心作為基準進行查詢，達到保護的目的。文獻[13-15]根據用戶與高頻興趣點將全局地圖的位置進行單元區別劃分，用戶可根據網格單元中興趣點的分布獲取周圍具體各項興趣點的分布情況，保證匿名區域的多樣性。

上述大多數文獻均在理想環境下，以K-匿名方法作為收集方式，達到匿名效果。在人跡稀疏的情況下，通過假位置方法正好彌補了這一不足，但由用戶根據自身的隱私需求構造假位置，并將這些假位置與真實位置一起發送到服務器，使得攻擊者無法區分用戶的真實位置信息。在生成的假位置的過程中，由于無法判定地形(如湖面、山脈)等因素，因此會影響假位置的可靠性。

針對上述問題，本文提出一種用戶自我感知的位置隱私保護算法(簡稱USA)。用戶自我感知周圍鄰居用戶的分布密度情況，排除地形原因并形成匿名區域，隨后將匿名區域呈多個矩形劃分，最后按所分區域一同將請求內容發送至服務器。與現有方法相比，本文方法能夠提高用戶位置匿名性、可靠性，降低合謀攻擊成功率。

2 系統模型

2.1 系統結構

位置隱私保護方法目前適用于兩種系統結構：中心服務器結構和基于P2P結構。

中心服務器結構中，在移動用戶和位置服務提供商(LSP)之間引入一個可信任的匿名器作為中間體，將用戶位置信息通過匿名服務器模糊，最后發送到LBS服務器完成請求。P2P結構由移動用戶組成與LBS服務器，搭載P2P協議通過單跳或多跳通信產生可靠的匿名區域，各區域間用戶之間相互合作完成保護。

為了方便用戶感知有效的鄰居用戶位置信息，本文采用P2P結構的LBS系統，系統模型如圖1所示。由于本文主要研究的是用戶的位置隱私保護，所以假設在用戶之間、用戶與服務器之間的通信都是安全的。

圖1 位置隱私保護系統模型

2.2 基本思路

如圖2所示，USA算法主要分為四個步驟：(1) 請求使用LBS服務的用戶在有限跳數下感知自身周圍鄰居用戶的分布密度；(2) 將感知到所有鄰居用戶所在位置的整體區域劃分為多個矩形子區域；(3) 在每個矩形子區域中添加偽用戶來均衡矩形內的用戶稀疏分布；(4) 用戶、鄰居用戶和偽用戶共同將請求LBS的用戶的內容發送至服務器，等待回應，當服務器回應給用戶時，對返回結果篩選求精即可得到當前位置信息。

圖2 USA算法步驟演示

3 算法實現

3.1 用戶感知

在連通空間C中，對于用戶u，周圍的鄰居用戶都有特定的用戶群密度ρu，稱為周邊用戶平均密度，即周圍感知用戶個數為n(ρu,h)，當h=1時，即一跳所感應的平均用戶數量(h≥1),ρu以增加h的情況下在自身的ρu上進行迭代更新，此處使用極大似然估計的原理來估計平均用戶數量。

(1)

式中：Cu表示第一跳周邊用戶的總數量。

由于通信傳輸時并不是在理想環境下的傳輸，因此，必須考慮非理想情況下能感知到的用戶總數，因此，加入損耗因子μ，計算方法為：

(2)

因此：

(3)

顯然，h越大，用戶的數量雖然增多，但通信鏈路增多，通信開銷增大，且LBS的準確度降低。

鄰居用戶感知算法中，用戶u在初始化后，在規定的t周期內檢測ρu，當在檢測周期內發現ρu發生改變或有新的鄰居用戶加入時，則向“L”發送攜帶自身ρu和鄰居位置信息；收集完成“L”集合并重新檢測當前鄰居用戶的個數；讀取每條“L”的位置信息并更新ρu。具體算法如下：

輸入：鄰居的“L”位置信息集合。

輸出：ρu以及“L”的信息。

1. 設置ρu的初始值P、時間周期t

2. 初始化鄰居用戶的集合且為空

3. WHILE(t周期)

4. IF(ρu有變化)

5. 產生并發送“L”位置信息

6. END IF

7. 收到“L”的位置信息

8.Pu←P(u,1)；

9. WHILE(“L”中的每一個位置信息)

10. 讀取每個鄰居的ρu

11.ρu更新

12. END WHILE

13. IF(ρu發生變化)

14 ρu←(Σ ρu+Pu)/|Pu|

15. END IF

16. END WHILE

3.2 矩形區域劃分

在區域劃分這一過程中，主要會經歷以下步驟：

(1) 用戶u發出位置請求時，使用上述位置感知算法之后感知周圍的用戶，且收集到至少K-1個用戶節點信息。

(2) 將這K-1個用戶節點開始模糊化去除，使得以用戶為中心的整體區域去重化偏移，提高用戶位置安全性。

(3) 在滿足K匿名的情況下，將用戶及感應到的鄰居用戶形成一個區域，隨后將生成的區域劃分成多個矩形子區域。

(4) 為了使每個矩形子區域內的用戶分布均衡，不失重，在完成矩形子區域劃分之后，通過隨即添加偽用戶來調節，提高用戶位置的模糊性和自我匿名的能力區域劃分的算法如下：

輸入：鄰居用戶節點集合U，用戶初始位置Loc，搜尋節點數Nu，劃分子區域數目n,匿名需求K。

輸出：n個匿名區域Ci(1≤i)。

1. IF(Nu

2. End if

3. 把Loc添加到集合U中

4. 多于節點數目N′=Nu-K+1,IF(N′=0),跳至第7步

5. 將U中節點橫縱坐標按隨機方向排序求出最大與最小的N′個節點，并排序節點集合Ux與Uy

6. 去除Ux中q(q為隨機數，且0≤q≤N)個節點與Uy中前(N′-q)個節點，并將去除的節點放入多余節點集合Ud。若Ud中已經包括去除的節點，則該集合多取一次節點放入Ud集合中,直到Ud里無重復的節點，且個數為N′，U=U-Ud[16]

7.U為隨機選取中的節點，依據節點坐標方向以及坐標值大小進行排序，同時得到排序節點集U′

8. 用戶余數r=K%n，平均用戶個數m=K/n

9. 將集合U′依據順序進行劃分為n個集合，選擇一個集合包含m+r個用戶，另n-1個集合則包含m個用戶

10. 在n個節點集中，計算出每個集合的最小外接矩陣C

11. 返回n個子匿名區域C1,C2,…，Cn

4 性能分析

4.1 匿名成功率

在P2P通信結構下，由于用戶可以與用戶直接傳送信息，沒有中間服務器工作的影響和其他的物理損耗，因此，匿名成功率的本質即可表示為通過查詢用戶本身成功匿名的數目與進行總查詢的用戶數目之間的比值[16]，具體見公式:

SR=Nsuccess/Ntotal

(4)

4.2 合謀攻擊成功率

在完成匿名的用戶區域中，如果攻擊型用戶與用戶u在同一個子區域，此時會增加成功被攻擊的機率。假設區域中有k個用戶，m個攻擊型用戶，矩形子匿名區域有w個用戶，真實用戶在第j個子匿名區域，即用戶u在查詢區域中暴露的概率等于所有子匿名區域受到攻擊的概率之積[15]。公式如下：

(5)

5 仿真與分析

5.1 實驗環境

本文仿真采用Java語言實現,實驗數據來自德國Oldenburg為主的交通路網[17],仿真數據使用參數如表1所示。在此基礎上對USA算法的性能進行仿真,挑選和USA算法在相同空間里和網絡環境下的區域相似性劃分算法(ASDA)和基于用戶均衡性劃分算法(UUDA)以及P2P經典方法，分別在不同場景下進行性能比較。

表1 仿真參數

將整體區域劃分多個子區域是USA算法的關鍵，其性能決定了USA算法對用戶保護的力度。在固定的用戶基數內，劃分的矩形子區域的個數不同所帶來的影響也不同。如圖3所示，當用戶范圍在2 000人時，隨著劃分的子區域個數的增加，用戶被攻擊成功的概率就逐步降低，但是無限劃分子區域將帶來額外的通信開銷，故本文所用的子區域個數均為4。

圖3 合謀攻擊成功率受子區域個數的影響

5.2 算法性能分析

圖4為P2P經典算法和ASDA算法與USA算法進行比較的示意圖。對于P2P經典算法來說，沒有子區域的劃分，用戶直接通過K值的大小在整體范圍把請求的內容發送至服務器，造成被攻擊的概率大幅度提高，而ASDA算法和USA算法在劃分子區域的基礎上，用戶被攻擊的概率明顯降低。由于USA算法提前感知用戶周圍用戶分布密度，繼而通過添加偽用戶的調和，進一步降低了被攻擊的概率。

圖4 劃分子區域對合謀攻擊率的影響

圖5為相同的環境下在不同算法中，用戶數對平均匿名時間的影響?？梢钥闯?，在經典P2P算法當中，用戶所需要的平均匿名時間是最少的，ASDA算法次之。盡管如此，經典P2P算法在安全性上對比時間上微小的毫秒差距用戶是可以忍受的，而UUDA算法和USA算法雖然平均匿名時間比經典P2P算法高，但安全性大大提高。由于ASDA算法中沒有對匿名區域內的用戶進行失重調整，因此其平均匿名時間較低。而USA算法與UUDA算法在匿名區域中都使用了添加偽用戶的過程。在平均匿名時間的性能上，USA算法略低于UUDA算法，提高了用戶使用位置服務的時間，同時也提高了位置隱私保護方法的質量。

圖5 用戶對平均匿名時間的影響

圖6為在USA算法中不同的K值對于匿名成功率的影響的對比圖。隨著用戶數量的增多，匿名成功率整體上漲。當K值越小，用戶的數量越多時，匿名成功率越大；當K值越大，用戶數量越少，匿名成功率越小，可能會導致匿名失敗。因此，在一定范圍內選擇合適的K值是至關重要的。

圖6 K值對匿名成功率的影響圖

6 結 語

針對LBS中存在的位置隱私泄露問題，提出了一種用戶自我感知的位置隱私保護算法，通過用戶提前感知自身周圍用戶分布疏密的情況，排除因地形因素影響位置隱私保護方法效果不佳的原因，再使用區域劃分的方法主動降低被攻擊型用戶攻擊的概率，在一定程度上加強保護用戶位置隱私的力度。下一步將通過把用戶位置隱私保護的方法放在不同的生活場景下進行深入探索，比如社交網絡等，同時也會融入密鑰保護等手段與增強隱私安全度結合來提高位置隱私的保護效率。