葉吉祥 曹文慧

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

0 引 言

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

1 研究概述

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

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

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

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

2 系統(tǒng)模型

2.1 系統(tǒng)結(jié)構(gòu)

位置隱私保護(hù)方法目前適用于兩種系統(tǒng)結(jié)構(gòu)：中心服務(wù)器結(jié)構(gòu)和基于P2P結(jié)構(gòu)。

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

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

圖1 位置隱私保護(hù)系統(tǒng)模型

2.2 基本思路

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

圖2 USA算法步驟演示

3 算法實現(xiàn)

3.1 用戶感知

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

(1)

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

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

(2)

因此：

(3)

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

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

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

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

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

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

3. WHILE(t周期)

4. IF(ρu有變化)

5. 產(chǎn)生并發(fā)送“L”位置信息

6. END IF

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

8.Pu←P(u,1)；

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

10. 讀取每個鄰居的ρu

11.ρu更新

12. END WHILE

13. IF(ρu發(fā)生變化)

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

15. END IF

16. END WHILE

3.2 矩形區(qū)域劃分

在區(qū)域劃分這一過程中，主要會經(jīng)歷以下步驟：

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

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

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

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

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

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

1. IF(Nu

2. End if

3. 把Loc添加到集合U中

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

5. 將U中節(jié)點橫縱坐標(biāo)按隨機(jī)方向排序求出最大與最小的N′個節(jié)點，并排序節(jié)點集合Ux與Uy

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

7.U為隨機(jī)選取中的節(jié)點，依據(jù)節(jié)點坐標(biāo)方向以及坐標(biāo)值大小進(jìn)行排序，同時得到排序節(jié)點集U′

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

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

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

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

4 性能分析

4.1 匿名成功率

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

SR=Nsuccess/Ntotal

(4)

4.2 合謀攻擊成功率

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

(5)

5 仿真與分析

5.1 實驗環(huán)境

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

表1 仿真參數(shù)

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

圖3 合謀攻擊成功率受子區(qū)域個數(shù)的影響

5.2 算法性能分析

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

圖4 劃分子區(qū)域?qū)现\攻擊率的影響

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

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

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

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

6 結(jié) 語

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