關(guān)于 LBS(P，L，K)匿名模型及其算法的探索
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
作者：鄭曉敏
近年來，位置服務(wù)中隱私保護(hù)技術(shù)的研究主要從以下三個方面著手：假名技術(shù)、加密技術(shù)、基于位置的匿名方法。其中基于位置的匿名方法是使用最普遍的方法。該方法用包括該位置所在的一個區(qū)域來代替用戶的真實位置發(fā)出查詢，大大降低了用戶位置信息被泄露的概率。同時在此基礎(chǔ)上加上匿名時間限制來控制用戶查詢信息的匿名有效時間，從而從時間和空間上對匿名集區(qū)域進(jìn)行了約束，更好地保護(hù)用戶信息。
在LBS隱私保護(hù)領(lǐng)域中出現(xiàn)了基于算法和策略的保護(hù)機(jī)制�；谒惴ǖ谋Ｗo(hù)機(jī)制是在請求用戶和服務(wù)提供商之間通過設(shè)計算法來實現(xiàn)隱私保護(hù)，這也是目前大多數(shù)學(xué)者研究的主要方向；而基于策略保護(hù)機(jī)制是通過策略和約束規(guī)則決定股務(wù)提供商何時何地可以獲得自己的位置信息。2002年，Langheinrich M首先提出基于策略的保護(hù)方法，文獻(xiàn)[7-10]對該方法進(jìn)行了更深一步的研究，但是該方法的缺點是查詢用戶必須時刻更新自己的策略，一旦查詢用戶忘記更新隱私策略，就會出現(xiàn)隱私泄露的風(fēng)險。2003年，假名機(jī)制的提出可以更好地保護(hù)用戶隱私，其思想是將空間劃分成混合區(qū)域( mix zone)和應(yīng)用區(qū)域（application zone），在混合區(qū)域內(nèi)用戶不發(fā)出任何請求，但是可以更改自己的ID，而在應(yīng)用區(qū)域內(nèi)，通過更換后的假名進(jìn)行查詢請求而不使用真實ID，這樣就斷開了同一個用戶在不同時間連續(xù)兩次服務(wù)請求之間的聯(lián)系，假名機(jī)制的缺點是用戶處在混合區(qū)域不能隨時隨地地享受服務(wù)。同年，在位置隱私保護(hù)中，G，utese。和Grunwald首次提出了K匿名模型，并且在此基礎(chǔ)上提出基于四分樹的隱私保護(hù)方法，其主要思想是對空間進(jìn)行四叉樹迭代劃分，直到某次迭代劃分后，查詢用戶所在的象限匿名條件不滿足K匿名條件，則返回上一次迭代的結(jié)果作為用戶的匿名區(qū)域。它雖然可以解決大量移動用戶高效尋找匿名集問題，但是該方法是以假定用戶擁有統(tǒng)一K匿名需求為前提，并且得到的匿名區(qū)域往往過大。針對這些問題，在2005年，Gedik和Liu提出了一種CliqueCloak（小集團(tuán)）匿名方法，該算法中的每個用戶均可以根據(jù)自身的情況定義不同的K匿名要求，通過逐個結(jié)合互為匿名團(tuán)的用戶來滿足自己的K匿名要求，該方法的優(yōu)點是可以滿足不同用戶的不同的匿名要求，但最大的缺點是只適合于K值很小的情況（如5—10），當(dāng)K值較大時效果很差，實際用途不大。在K匿名方法的基礎(chǔ)上，闞瑩瑩提出一種新的模型即多樣化K匿名模型，該模型的主要貢獻(xiàn)是對用戶敏感屬性進(jìn)行分類，避免其分布不均衡，有效地保護(hù)了隱私。牛紅衛(wèi)提出了增強(qiáng)的匿名模型，并且在該模型基礎(chǔ)上針對現(xiàn)有匿名空間查找算法冗余空間過大問題，提出了基于網(wǎng)格和密度的匿名空間查找算法，在用戶分布密度最大的范圍內(nèi)尋找滿足匿名模型的最小匿名空間，但是缺點是容易遭到中心位置攻擊。為解決這些問題，Bamba等人提出鄰接網(wǎng)格擴(kuò)展匿名算法，典型的算法有Bottom-up cloaking算法、Top-down cloaking算法和Hybrid cloaking算法。這些算法允許用戶自行定義隱私需求參數(shù)，實現(xiàn)個性化隱私保護(hù)，同時，該參數(shù)可以彌補(bǔ)僅有K匿名參數(shù)而引起的隱私泄露。但是這種方法查詢服務(wù)質(zhì)量還有待提高。
迄今為止，大多數(shù)隱私位置匿名算法匿名時間較長，匿名域較大，匿名不成功的可能性較高，并且對包含更多隱私信息的查詢隱私?jīng)]有做到更好的保護(hù)。本文提出LBS(P，L，K)匿名模型，并在此基礎(chǔ)上，確定一種基于網(wǎng)格和假用戶來劃分空間位置的匿名算法，該算法建立在目前比較成熟的網(wǎng)格技術(shù)應(yīng)用基礎(chǔ)上，對空間進(jìn)行網(wǎng)格劃分，通過考慮用戶的分布情況來尋找查詢用戶的鄰域，同時生成假用戶來發(fā)送假請求以滿足LBS(P，L，K)匿名模型，實現(xiàn)對查詢隱私保護(hù)的目的。
1網(wǎng)格和假用戶匿名算法設(shè)計
1.1相關(guān)概念
定義l（K匿名）在所有用戶匿名查詢中，位置服務(wù)商按照某種策略得到包含查詢用戶在內(nèi)的匿名區(qū)域R中至少包含K個不同用戶位置，稱此匿名滿足K匿名。
定義2（敏感度）假設(shè)一個用戶在某個時刻請求查詢Q(id，g)中，為查詢內(nèi)容g設(shè)定敏感級別，將其數(shù)值化后的值為這個查詢內(nèi)容的敏感度，記作Sid。敏感度越大表示被保護(hù)的程度越高。
定義3（P敏感約束）假設(shè)匿名區(qū)域中所有匿名查詢Q(id，g)中，查詢內(nèi)容g的敏感度為Sid的數(shù)目所占查詢數(shù)目總數(shù)比例不超過Po其中，|(R，Sid)|為匿名區(qū)域R中查詢內(nèi)容的敏感度為Sid的查詢數(shù)目。P為用戶定義的參數(shù)(0<P<1)，滿足P敏感約束的充分必要條件是當(dāng)且僅當(dāng)|(R，Sid)|/|(R)|≤P。
定義4（L覆蓋性約束）在匿名區(qū)域中，查詢內(nèi)容的敏感度Sid不同值個數(shù)不小于L。
定義5( LBS(P，L，K)匿名模型）滿足匿名模型定義1、定義3、定義4稱為LBS(P,L，K)匿名模型。
定義6（相鄰網(wǎng)格）用Si,j來表示當(dāng)前用戶所處網(wǎng)格的空間位置，則坐標(biāo)為Si±1j或者Sij±1的網(wǎng)格為當(dāng)前用戶所在網(wǎng)格的相鄰網(wǎng)格。
定義7（鄰域）當(dāng)前網(wǎng)格和其相鄰網(wǎng)格集合構(gòu)成當(dāng)前網(wǎng)格的鄰域，S '={Sxy|i-l≤x≤i+1,j-l≤x≤j+l}。
定義8（臨時匿名區(qū)域）若空間S滿足匿名要求，對S進(jìn)行網(wǎng)格劃分之后，用戶u的鄰域空間所包含的用戶個數(shù)小于匿名要求，則稱空間S是用戶u的臨時匿名區(qū)域。
1.2算法分析描述
本文算法分成兩個階段，第一階段為網(wǎng)格區(qū)域擴(kuò)充算法，第二階段是假用戶生成算法。網(wǎng)格區(qū)域擴(kuò)充算法中，將整個空間S分為MxM的網(wǎng)格，每個網(wǎng)格單元用相應(yīng)的坐標(biāo)Sij表示。根據(jù)當(dāng)前查詢用戶所在網(wǎng)格坐標(biāo)可以計算出該用戶的鄰域空間S’和S'所對應(yīng)的用戶數(shù)目分布矩陣C，用Is表示空間內(nèi)所對應(yīng)的用戶數(shù)目，若IS'I>K，則令S'=S，對劃分網(wǎng)格進(jìn)行迭代，直到若|s'|≤K為止，此時的空間S即為臨時匿名空間。為防止匿名區(qū)域過大會降低用戶服務(wù)質(zhì)量，而過小則可能會遭遇中心位置攻擊，故對匿名區(qū)域空間設(shè)置最小粒度Amin和最大粒度Amax。接下來對臨時匿名空間S的冗余邊緣進(jìn)行刪除，首先根據(jù)臨時匿名空間S的用戶數(shù)目分布矩陣刪除用戶數(shù)目最小的行或列，直到得到的匿名區(qū)域面積在(Amin，Amax)之間。在假用戶生成階段，首先計算臨時匿名區(qū)域的用戶數(shù)目矩陣，分別在用戶數(shù)目最少的單元網(wǎng)格內(nèi)生成一個假用戶，判斷是否滿足敏感約束P和覆蓋性約束條件L，重復(fù)此過程直至滿足LSB(P,L，K)匿名模型。算法符號及其含義如表1所示。
算法偽代碼如下。
第一階段：
輸入：隱私度參數(shù)K，應(yīng)用空間S，匿名空間粒度Amin，Amax。
輸出：最小匿名區(qū)域Smin。
Clocking(K,S,Amin,Amax)
Begin:
(1) while(|S|>K&&Area(S)≥Amin&&Area(S)≤Amax）
{
(2)Sm=S;
(3)根據(jù)定義7計算出S的鄰域空間S'；
(4)S=S'；
(5)}//while
(6)Smin=Sm;mint i=l；
(7) while(|S|>K&&Area(S)≥Amin&&Area(S)≤Amax）
{
(8)根據(jù)用戶分布數(shù)目矩陣查找Smin中用戶數(shù)目最少的第i個邊緣；
(9)Smin=Sm,in-Si；
( 10) i++；}//while
( 11) Return Smin
End
第二階段：
輸入：隱私度參數(shù)K，敏感約束P，覆蓋性約束L。
輸出：最小匿名區(qū)域Smin。
Generate_fake_users(K.P.L,Smin)
Begin:
(1)計算P'=max(|(R，Sid)|/|R|)，L'；//pr與L'為最小匿名區(qū)域中的敏感約束和覆蓋性約束。
(2) int i=l：
(3) while( |S|<K IIP'>PIIL'>L){
(4)計算Smin的用戶分布數(shù)目矩陣，據(jù)此查找用戶數(shù)目最少的第i個邊緣網(wǎng)格，在此網(wǎng)格內(nèi)生成一個假用戶和其查詢內(nèi)容的敏感度。
(5)計算P'=max(I(R,Sid)l/IRI),L'；
(6)i++：
(7)}//while
算法實例分析如下：
假設(shè)在時刻f，初始空間為S，用戶4在該時刻發(fā)出查詢五元組為（P，L，K，Amin,Amax），其中P=0.4，K=4，L=2，Amin=6，Amax=9。首先，對初始空間S劃分為5x5的網(wǎng)格，用戶u所在網(wǎng)格為第二行第三列，故其網(wǎng)格坐標(biāo)為U2.3，根據(jù)定義7得到其鄰域空間為[(1—4)，(2—5)]，根據(jù)用戶數(shù)目分布矩陣C計算|S'|>4，則令S'=S迭代劃分網(wǎng)格，直到Is'I≤4，則此時的S2即是臨時匿名區(qū)域迭代過程。如表2所示，最終結(jié)果為二次迭代空間S2。
接下來由遠(yuǎn)及近依次刪除用戶數(shù)目最小的行或列，如圖l所示，依次刪除冗余邊A，B，C，D，剩下的匿名區(qū)域為滿足條件的最小匿名區(qū)域。
該時刻用戶提交的部分查詢信息如表3所示。
通過計算可得I(R，0)l/IRl=0.75>0.5，I(R，1)l/IRl=0<0.5，I（R,2）l/IRl=0.25<0.5，L，-3>2。由于I(R，0)l/IRI不滿足條件，尋找滿足用戶數(shù)目最少的邊緣網(wǎng)格，生成一個假用戶u，其查詢內(nèi)容設(shè)置為“拘留所”，其敏感度為2，這樣就可以滿足LBS(P,L，K)匿名模型。
2模擬實驗
本文實驗仿真的硬件環(huán)境是INTEL CORE 13-4150 3.6 GHz處理器，4G內(nèi)存， 編程環(huán)境是ECLIPSE+HIBERNATE+MICROSOFT SQL SERVER 2008,算法均使用Java語言編寫。實驗在產(chǎn)生用戶位置坐標(biāo)和LBS請求時，采用THOMAS BRINKHOFF基于路網(wǎng)的移動對象生成器來模擬生成5000個用戶，以算法執(zhí)行100次仿真的平均值作為本次實驗的結(jié)果，同時參數(shù)Amin取值為一個單元格，Amax為9個單元格。
為平衡用戶隱私保護(hù)和服務(wù)質(zhì)量之間的關(guān)系，本文從匿名時間、匿名成功率、匿名代價等指標(biāo)方面對基于網(wǎng)格和假用戶匿名算法( Grid-fake users)進(jìn)行驗證，以討論本文有效性。其中，匿名時間是觸發(fā)提出查詢請求到匿名成功所需要的時間，匿名成功率是指匿名成功的查詢請求個數(shù)與所有查詢請求個數(shù)的比值，其值越大則表示服務(wù)質(zhì)量
越好，匿名代價用匿名空間的大�。茨涿臻g的面積）來表示，相同匿名度條件下，匿名空間越小，則匿名代價就越低。
圖2給出了基于網(wǎng)格和假用戶匿名算法、Bottom-up匿名算法和Grid_divide算法的時間消耗隨K值變化關(guān)系圖。從圖2可以看出，三種算法的匿名時間隨K值的增加而不斷增加，這是因為隨K值的增加，每個查詢用戶需要更多的時間處理、等待才能匿名成功。同時與Bottom-up匿名算法、Grid-divide算法相比，基于網(wǎng)格和假用戶匿名算法因參數(shù)上有更高的要求使得其時間消耗相對較高。
采用匿名區(qū)域面積來表示匿名代價。由圖3可知匿名區(qū)域面積隨K值的增加呈現(xiàn)遞增趨勢，這是因為K值的增加必然要求更多的用戶，更大的空間來滿足K匿名。在基于Grid_divide位置匿名算法中，若當(dāng)前網(wǎng)格面積S≥Amin,只有該網(wǎng)格內(nèi)的用戶數(shù)量滿足(P，L，K)模型時，才返回匿名區(qū)域，否則計算與當(dāng)前網(wǎng)格相鄰的四個單元格中的用戶數(shù)目，選擇數(shù)目最多的網(wǎng)格單元與該網(wǎng)格合并，作為該用戶的匿名區(qū)域，面積設(shè)為S，遞歸循環(huán)該過程，直S≥Amin，并且滿足K匿名模型。而本文提出的基于網(wǎng)格和假用戶匿名算法是將用戶密度考慮進(jìn)去，對空間進(jìn)行迭代，然后求得匿名區(qū)域，此時匿名區(qū)域已經(jīng)確定，通過生成假用戶和假請求來滿足(P,L，K)模型，所以該算法比Grid-divide算法生成的匿名區(qū)域面積要小，實驗結(jié)果如圖3所示。
綜上所述，相對于其他算法，新算法能夠以犧牲較少的時間消耗來明顯降低匿名代價，同時引入假用戶來滿足敏感約束P和覆蓋性約束L條件，能夠更好地保護(hù)用戶隱私信息。
3結(jié)束語
針對位置服務(wù)隱私保護(hù)的大多數(shù)研究只考慮了位置隱私保護(hù)方面，而沒有更好地保護(hù)查詢隱私，本文提出了LBS(P，L，K)匿名模型，將匿名集中的查詢接照敏感度進(jìn)行分類，并使得每個匿名集中不同敏感度的查詢所占比例不超過P，不同敏感度的個數(shù)不小于L，通過參數(shù)P和L來實現(xiàn)保護(hù)用戶查詢內(nèi)容的目的。尋找匿名集是匿名模型要解決的關(guān)鍵問題，在此基礎(chǔ)上，文章提出基于網(wǎng)格和假用戶匿名算法，在用戶分布數(shù)目最多的范圍內(nèi)來尋找滿足隱私要求的最小匿名空間，解決了位置服務(wù)中匿名算法存在的匿名區(qū)域大問題。該算法在匿名區(qū)域面積最小的基礎(chǔ)上，通過增加假用戶，設(shè)置假請求來滿足匿名模型，大大增加了攻擊的難度。通過實驗表明，改進(jìn)后的算法匿名區(qū)域更小，相對匿名度更高，更有利于保護(hù)用戶的位置隱私和查詢隱私。
4摘要：
目前，大多數(shù)位置匿名算法會出現(xiàn)匿名區(qū)域較大、匿名時間較長、匿名不成功的可能性較高等問題，并且對包含更多隱私信息的查詢隱私?jīng)]有做到更好的保護(hù)。為解決這些問題，文章提出一種基于敏感度的個性化LBS( P,L,K)匿名模型，該模型在K匿名基礎(chǔ)上，通過對查詢內(nèi)容設(shè)置不同的敏感度來滿足P敏感約束和L覆蓋性約束，達(dá)到保護(hù)查詢隱私的目的，從而實現(xiàn)匿名隱私保護(hù)的個性化需求。同時，文章在該模型基礎(chǔ)上提出基于網(wǎng)格和假用戶匿名算法，該算法將整個匿名空間劃分成mxn的網(wǎng)格，通過迭代尋找查詢用戶所在網(wǎng)格的鄰域空間進(jìn)而找到該用戶的臨時匿名空間，然后根據(jù)用戶分布矩陣對臨時匿名空間進(jìn)行邊緣剝離，直至滿足用戶面積約束條件。從對比實驗結(jié)果可知，在滿足用戶個性化要求條件下，該方法匿名區(qū)域面積更小，從而提高了相對匿名度和用戶的查詢服務(wù)質(zhì)量。
