徐紅云 許雋 龔羽菁 徐夢(mèng)真

(華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006)

隨著基于位置服務(wù)(LBS)［1］的日益推廣，針對(duì)LBS 的攻擊也應(yīng)運(yùn)而生.攻擊者可以從LBS 查詢(xún)信息中推斷出用戶(hù)的生活習(xí)慣、宗教信仰、政治傾向、疾病史等隱私信息，造成用戶(hù)隱私信息的泄露［2］，從而給用戶(hù)的聲譽(yù)甚至是人身安全帶來(lái)威脅，因此，LBS 中隱私信息保護(hù)的研究對(duì)LBS 的進(jìn)一步普及和推廣具有十分重要的意義.

現(xiàn)有的位置隱私保護(hù)技術(shù)主要包括:①假名隱私保護(hù)法［3］，即用一個(gè)虛假的用戶(hù)名替換真實(shí)用戶(hù)身份標(biāo)識(shí)來(lái)提出服務(wù)請(qǐng)求;②標(biāo)識(shí)對(duì)象法［4］，即用距離用戶(hù)位置一定范圍內(nèi)的其他位置提出服務(wù)請(qǐng)求;③虛假地址法［5］，即發(fā)送一個(gè)包含用戶(hù)本身以及其他虛假地址的集合給LBS 服務(wù)器，提出服務(wù)請(qǐng)求;④空間匿名法［6］，即發(fā)送一塊包含用戶(hù)位置的區(qū)域向LBS 服務(wù)器提出服務(wù)請(qǐng)求.

不同的用戶(hù)(如平民百姓與政府要員)有不同的隱私保護(hù)需求，同一用戶(hù)在不同時(shí)刻(如上班和下班時(shí)間)也有不同的隱私保護(hù)要求，因此，一個(gè)可靠、安全的LBS 系統(tǒng)應(yīng)能提供個(gè)性化的隱私保護(hù)功能.目前，實(shí)現(xiàn)個(gè)性化隱私保護(hù)的主要技術(shù)有k-匿名［7-8］和L-多樣性［9］.k-匿名是指將用戶(hù)的準(zhǔn)確位置信息替換成一個(gè)包含k 個(gè)用戶(hù)的空間區(qū)域，使得提出服務(wù)請(qǐng)求的用戶(hù)在該空間區(qū)域內(nèi)至少不能與其他的k－1 個(gè)用戶(hù)區(qū)別開(kāi)來(lái).L-多樣性是指匿名集中的每個(gè)等價(jià)類(lèi)的敏感值滿(mǎn)足多樣性需求，以提高敏感值與其所屬用戶(hù)的鏈接難度.匿名集中的等價(jià)類(lèi)是指在所有準(zhǔn)標(biāo)識(shí)符屬性上取值相同的用戶(hù)集合.空間混淆隱私保護(hù)法［10］、團(tuán)混淆的位置隱私保護(hù)法［8］是兩個(gè)典型的實(shí)現(xiàn)個(gè)性化位置隱私保護(hù)的算法，它們的核心思想是:每個(gè)用戶(hù)根據(jù)隱私保護(hù)程度(簡(jiǎn)稱(chēng)隱私度)要求和周?chē)欢▍^(qū)域內(nèi)的用戶(hù)組成互惠區(qū)域，在同一個(gè)區(qū)域內(nèi)的用戶(hù)提出具有相同隱私度的服務(wù)請(qǐng)求時(shí)，均使用同一個(gè)位置隱私區(qū)域提出服務(wù).這兩個(gè)算法都是通過(guò)調(diào)整隱私度k 的大小來(lái)實(shí)現(xiàn)位置隱私的個(gè)性化，但在隱私度切換過(guò)程中容易被惡意觀察者攻擊.因?yàn)楣粽咄ㄟ^(guò)獲取切換前后的位置隱私區(qū)域大小等敏感信息可推斷出用戶(hù)所在位置，從而使隱私度切換失敗.

為解決上述問(wèn)題，文中基于空間混淆位置隱私保護(hù)法提出了兩種隱私度切換時(shí)位置隱私區(qū)域的生成算法，即初級(jí)形心偏移法和高級(jí)形心偏移法.初級(jí)形心偏移法在切換前位置隱私區(qū)域基礎(chǔ)上，根據(jù)周?chē)脩?hù)的分布情況生成切換后的位置隱私區(qū)域，進(jìn)而提出服務(wù)請(qǐng)求.高級(jí)形心偏移法將切換后位置隱私區(qū)域的形心移出切換前位置隱私區(qū)域外，再根據(jù)周?chē)脩?hù)的分布情況生成與切換前位置隱私區(qū)域無(wú)重疊的位置隱私區(qū)域，進(jìn)而提出服務(wù)請(qǐng)求.

1 相關(guān)工作

1.1 空間混淆位置隱私保護(hù)

現(xiàn)有的空間混淆位置隱私保護(hù)法均利用了空間混淆技術(shù)［11-21］，特別是k-匿名［7-8］，即一塊混淆區(qū)中至少存在包括服務(wù)提出者在內(nèi)的k 個(gè)用戶(hù)，通過(guò)k的變化來(lái)實(shí)現(xiàn)隱私度的個(gè)性化，k 越大，隱私度越高，反之，隱私度越低.

在用戶(hù)呈均勻分布的歐幾里得空間中，用戶(hù)首次提出位置服務(wù)請(qǐng)求時(shí)，可信第三方使用k-匿名法組建位置隱私區(qū)域［6］，在某個(gè)時(shí)刻要切換隱私度時(shí)，一般采取以下步驟［1］:①去除用戶(hù)標(biāo)識(shí)，給信息編號(hào)，定義最長(zhǎng)的等待服務(wù)返回時(shí)間、最小位置隱私區(qū)域、最大位置隱私區(qū)域;②根據(jù)切換前后的隱私度比值，線性的等比放大或縮小切換前的位置隱私區(qū)域，若達(dá)到最大位置隱私區(qū)域后仍不滿(mǎn)足k-匿名，則用啞元［22-23］進(jìn)行填充，生成切換后的位置隱私區(qū)域;③可信第三方服務(wù)器將第①和第②步的信息打包發(fā)送給LBS 服務(wù)器，提出服務(wù)請(qǐng)求.

以上實(shí)現(xiàn)個(gè)性化隱私保護(hù)的位置隱私區(qū)域切換方法簡(jiǎn)單，易于實(shí)現(xiàn)，直接在切換前的位置隱私區(qū)域上做擴(kuò)展，運(yùn)算速度快，開(kāi)銷(xiāo)小，但前后兩次個(gè)性化的切換并不獨(dú)立，服務(wù)器上的惡意觀察者可以通過(guò)記錄切換前的位置隱私區(qū)域來(lái)計(jì)算得到位置隱私區(qū)域的中心.用戶(hù)切換隱私度后生成、發(fā)送新的位置隱私區(qū)域，攻擊者再次觀察獲取并計(jì)算新位置隱私區(qū)域中心，中心重合則認(rèn)為是同一個(gè)用戶(hù)的請(qǐng)求，隱私度切換失敗.

由于空間混淆位置隱私保護(hù)法的適用環(huán)境是用戶(hù)呈均勻分布的歐幾里得空間，故位置隱私區(qū)域的中心就是請(qǐng)求區(qū)域的形心，呈非均勻分布時(shí)位置隱私區(qū)域的中心即為請(qǐng)求區(qū)域的質(zhì)心，文中采用形心來(lái)表示位置隱私區(qū)域的中心.

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

文中使用兩個(gè)指標(biāo)來(lái)對(duì)提出的算法的服務(wù)質(zhì)量進(jìn)行評(píng)價(jià).

(1)切換成功率.文中參照匿名成功率［24］來(lái)定義切換成功率，即成功的隱私度切換請(qǐng)求數(shù)占總隱私度切換請(qǐng)求數(shù)的百分比，是衡量位置隱私區(qū)域生成算法性能的指標(biāo)之一.設(shè)總的切換請(qǐng)求數(shù)為n，成功的隱私度切換請(qǐng)求數(shù)為n'，且n'≤n，則切換成功率Rs為

(2)服務(wù)結(jié)果可靠度.服務(wù)結(jié)果可靠度定義為真實(shí)最佳(如離用戶(hù)最近)查找對(duì)象到用戶(hù)的距離和LBS 返回的最佳對(duì)象到用戶(hù)的距離的比值，是評(píng)價(jià)采用隱私區(qū)域生成算法提供位置隱私保護(hù)的LBS的指標(biāo)之一.設(shè)p 為用戶(hù)所在位置，真實(shí)查找最佳對(duì)象位于p1，位置服務(wù)器返回的最佳對(duì)象位于p2，則服務(wù)結(jié)果可靠度Rr為

2 攻擊模型

2.1 中心點(diǎn)攻擊

中心點(diǎn)攻擊的核心思想是根據(jù)隱私度切換前后位置隱私區(qū)域的中心是否重合來(lái)發(fā)起攻擊，重合則縮小位置隱私區(qū)域到切換前的大小，從而使用戶(hù)的隱私度切換失敗.中心點(diǎn)攻擊步驟如下:①攻擊者開(kāi)始觀察.②當(dāng)發(fā)現(xiàn)有用戶(hù)提交隱私度為k1的查詢(xún)請(qǐng)求時(shí)，記錄其位置隱私區(qū)域Ck1.③當(dāng)發(fā)現(xiàn)用戶(hù)切換隱私度為k2(k2＞k1)時(shí)，記錄其新的位置隱私區(qū)域Ck2.④計(jì)算Ck1和Ck2的中心O1和O2.將Ck1分別映射到x、y 軸上，得到左、右邊界的值分別為xk1_l和xk1_r，上、下邊界的值分別為yk1_t、yk1_b，同理得到Ck2的4 個(gè) 值(xk2_l，xk2_r，yk2_t，yk2_b)，則O1= ((xk1_l+xk1_r)/2，(yk1_t+yk1_b)/ 2)，O2= ((xk2_l+xk2_r)/ 2，(yk2_t+ yk2_b)/2).⑤若O1和O2重合，則輸出Ck1，位置隱私區(qū)域縮小到切換前的大小，隱私度切換失敗;否則輸出Ck2，隱私度切換成功.

采用普通位置隱私區(qū)域生成法生成的隱私區(qū)域的O2將與切換前隱私區(qū)域的O1重合，隱私度切換失敗.

2.2 形心偏移攻擊

攻擊者在服務(wù)器上觀察用戶(hù)發(fā)來(lái)的位置隱私區(qū)域，若隱私度切換前、后的形心O1和O2滿(mǎn)足

則認(rèn)為這兩個(gè)隱私請(qǐng)求來(lái)自同一用戶(hù)，即可將位置隱私區(qū)域縮小到切換前的大小，從而使用戶(hù)的隱私度切換失敗.其中A 和B 為參數(shù).

形心偏移攻擊步驟如下:①攻擊者開(kāi)始觀察.②當(dāng)發(fā)現(xiàn)有用戶(hù)提交具有隱私保護(hù)的查詢(xún)請(qǐng)求時(shí)，記錄其位置隱私區(qū)域，并計(jì)算該區(qū)域的形心.③根據(jù)收集到的數(shù)據(jù)計(jì)算參數(shù)A 和B，得到形心偏移函數(shù)(即式(3)).④攻擊者開(kāi)始攻擊，計(jì)算Ck1、Ck2的O1和O2.⑤若O1和O2滿(mǎn)足式(3)，則輸出Ck1，隱私度切換失敗;否則輸出Ck2，隱私度切換成功.

采用普通位置隱私區(qū)域生成法生成的隱私區(qū)域的O2將與切換前隱私區(qū)域的O1重合，即滿(mǎn)足式(3)(A 為1、B 為0)，隱私度切換失敗.

2.3 無(wú)差別攻擊

無(wú)差別攻擊的核心思想是對(duì)隱私度切換后的位置隱私區(qū)域，根據(jù)切換前后隱私度的比值等比縮小，并認(rèn)為縮小后的區(qū)域就是用戶(hù)切換前的位置隱私區(qū)域.無(wú)差別攻擊步驟如下:①攻擊者開(kāi)始觀察.②當(dāng)發(fā)現(xiàn)有用戶(hù)切換隱私度時(shí)記錄位置隱私區(qū)域Ck2.③將Ck2分別映射到x、y 軸上，得到左、右邊界的值分別為xk2_l和xk2_r，上、下邊界的值分別為yk2_t、yk2_b，則Ck2的形心為O2=((xk2_l+xk2_r)/2，(yk2_t+yk2_b)/2).④等比縮小Ck2，求出縮小后區(qū)域的4 個(gè)頂點(diǎn)，構(gòu)建平行于坐標(biāo)軸的矩形Ck.設(shè)，則有xk_l= xk2_l+L/2，xk_r= xk2_r-L/2，yk_b= yk2_b+L/2，yk_t= yk2_t-L/2.⑤輸出Ck.當(dāng)服務(wù)提出者包含于Ck中時(shí)，攻擊成功.

對(duì)于采用普通位置隱私區(qū)域生成法生成的位置隱私區(qū)域Ck2，經(jīng)該算法計(jì)算后得到的Ck將與切換前的位置隱私區(qū)域重合，隱私度切換失敗.

3 個(gè)性化位置隱私區(qū)域生成算法

為克服普通位置隱私區(qū)域生成法(算法1)對(duì)中心點(diǎn)攻擊防御弱的缺陷，需要對(duì)切換后的隱私區(qū)域形心進(jìn)行偏移，但不能直接對(duì)形心進(jìn)行操作，因?yàn)榉?wù)器上的惡意觀察者可能會(huì)利用形心偏移攻擊來(lái)獲得形心偏移函數(shù)，從而使形心偏移失效，用戶(hù)的隱私度切換不成功.故文中提出了初級(jí)形心偏移法(算法2)和高級(jí)形心偏移法(算法3).

3.1 初級(jí)形心偏移法

初級(jí)形心偏移法是一種改進(jìn)的基于空間混淆位置隱私保護(hù)的位置隱私區(qū)域生成法，它能保證一定的隱私度切換成功率，用于實(shí)現(xiàn)個(gè)性化的隱私保護(hù).該算法的核心思想是:為防御中心點(diǎn)攻擊，降低攻擊者的成功率，將切換前、后的位置隱私區(qū)域的形心進(jìn)行偏移.

初級(jí)形心偏移法以切換前隱私區(qū)域的4 個(gè)頂點(diǎn)為圓心，以用戶(hù)輸入?yún)?shù) 為擴(kuò)展步長(zhǎng)，r 為半徑畫(huà)圓，在原位置隱私區(qū)域的基礎(chǔ)上擴(kuò)展出新的位置隱私區(qū)域，統(tǒng)計(jì)新位置隱私區(qū)域內(nèi)的用戶(hù)數(shù)，如果用戶(hù)數(shù)滿(mǎn)足切換后的隱私度k 要求，則切換成功.初級(jí)形心偏移法的具體步驟如下:①全局變量r= ，初始化用戶(hù)集合U.②分別以Ck1的4 個(gè)頂點(diǎn)為圓心、r 為半徑畫(huà)圓.③統(tǒng)計(jì)圓內(nèi)所有的用戶(hù)數(shù)并將用戶(hù)加入U(xiǎn).④U 加上Ck1中用戶(hù)組成新的集合U'.⑤將U'中的點(diǎn)分別映射到x 和y 軸上，得到左、右邊界的值分別為xl、xr，上、下邊界的值分別為yt、yb，以(xl，0)、(xr，0)、(0，yt)、(0，yb)為頂點(diǎn)構(gòu)建矩形Ck2.⑥若Ck2中用戶(hù)數(shù)(Nu)小于k 且Ck2的面積(S(Ck2))小于用戶(hù)可接受的最大隱私區(qū)域大小(Smax)，則r=r+ ，返回步驟②.⑦若Nu≥k 且S(Ck2)＜Smax，則轉(zhuǎn)步驟⑨.⑧若S(Ck2)＞Smax，則根據(jù)Smax和S(Ck2)之比值等比縮小Ck2;若Nu＜k，則用啞元填充，直到Nu=k 為止.⑨返回Ck2.

初級(jí)形心偏移法的時(shí)空復(fù)雜度與步驟②到步驟⑥重復(fù)執(zhí)行的次數(shù)n 成正比，即時(shí)空復(fù)雜度為O(n)，故該算法簡(jiǎn)單、效率高.

初級(jí)形心偏移法最后輸出的Ck2的形心位置和Ck2中包含的用戶(hù)集合U 有關(guān)，由于U 中的點(diǎn)為用戶(hù)提出服務(wù)請(qǐng)求時(shí)周?chē)渌脩?hù)的位置，每次用戶(hù)提出請(qǐng)求時(shí)點(diǎn)的分布均不相同，故隱私區(qū)域Ck2的形心位置是隨機(jī)的，形心偏移量是個(gè)隨機(jī)數(shù).由于初級(jí)形心偏移法對(duì)形心進(jìn)行了偏移，且偏移量是一個(gè)隨機(jī)數(shù)，因此，初級(jí)形心偏移法對(duì)中心點(diǎn)攻擊和形心偏移攻擊的防御效果較好.

初級(jí)形心偏移法對(duì)切換后的位置隱私區(qū)域的形心進(jìn)行了偏移，但切換前的位置隱私區(qū)域仍然包含在切換后的位置隱私區(qū)域內(nèi)，故攻擊者可以采用無(wú)差別攻擊算法實(shí)施攻擊.

圖1 無(wú)差別攻擊后用戶(hù)位置泄露情況Fig.1 Situation of user location disclosure after indiscriminate attack

如圖1 所示，實(shí)線小矩形框?yàn)榍袚Q前的隱私區(qū)域，虛線矩形框?yàn)楣粽卟捎脽o(wú)差別攻擊后推斷出的用戶(hù)隱私區(qū)域，兩者重疊部分用黑色填充框表示.當(dāng)用戶(hù)真實(shí)位置在黑色填充框內(nèi)時(shí)，用戶(hù)位置隱私泄露，隱私度切換失敗.

3.2 高級(jí)形心偏移法

高級(jí)形心偏移法的核心思想是在初級(jí)形心偏移法的基礎(chǔ)上，將切換后的位置隱私區(qū)域形心移到切換前的位置隱私區(qū)域外部，且切換后的位置隱私區(qū)域和切換前的位置隱私區(qū)域無(wú)交集.高級(jí)形心偏移法用到了位置隱私區(qū)域延長(zhǎng)區(qū)，如圖2 所示，延長(zhǎng)區(qū)被分為4 個(gè)區(qū)，這4 個(gè)區(qū)平分切換前位置隱私區(qū)域的外部區(qū)域.

圖2 位置隱私區(qū)域的延長(zhǎng)區(qū)Fig.2 Extending area of location privacy area

高級(jí)形心偏移法的步驟如下:

(1)初始化全局變量r= ;

(2)以Ck1的形心O1為圓心、r 為半徑畫(huà)圓;

(3)從O1出發(fā)向圓內(nèi)的每個(gè)用戶(hù)點(diǎn)做連線;

(4)選取線段長(zhǎng)度最長(zhǎng)的用戶(hù)點(diǎn)，若有相同長(zhǎng)度的，則隨機(jī)選擇其中一個(gè)用戶(hù)，將非O1的一端設(shè)為O2;

(5)判斷O2是否落在某一隱私區(qū)域的延長(zhǎng)區(qū)中，若是，則轉(zhuǎn)步驟(7);

(6)將O2設(shè)為O1，r= ，以O(shè)1為圓心、r 為半徑畫(huà)圓，返回步驟(3);

(7)建立空的用戶(hù)集合U;

(8)以O(shè)2為圓心、r 為半徑畫(huà)圓;

(9)若圓內(nèi)的用戶(hù)位于O2所在的位置隱私區(qū)域的延長(zhǎng)區(qū)內(nèi)，則將該用戶(hù)加入U(xiǎn) 中;

(10)將U 中用戶(hù)所構(gòu)成的區(qū)域與切換前位置隱私區(qū)域相連邊上的用戶(hù)加入到U 中，形成新的用戶(hù)集合U';

(11)將U'中的點(diǎn)分別映射到x 和y 軸上，得到x 的最小和最大值分別為xl、xr，y 的最大和最小值分別為yt、yb，以(xl，0)、(xr，0)、(0，yt)、(0，yb)為頂點(diǎn)建立新的隱私區(qū)域Ck2;

(12)若Nu＜k 且S(Ck2)＜Smax，則r= r + ，返回步驟(8);

(13)若Nu≥k 且S(Ck2)＜Smax，則轉(zhuǎn)步驟(16);

(14)若S(Ck2)＞Smax，則以Smax和S(Ck2)之比值來(lái)等比縮小Ck2;

(15)若Nu＜k，則用啞元填充，直至Nu=k 為止;

(16)返回Ck2.

高級(jí)形心偏移法的時(shí)空復(fù)雜度與步驟(3)到步驟(5)重復(fù)執(zhí)行的次數(shù)m 以及步驟(8)到步驟(11)重復(fù)執(zhí)行的次數(shù)n'成正比，即時(shí)空復(fù)雜度為O(m+n' )，故該算法的效率較高.

高級(jí)形心偏移法最后輸出的Ck2在隱私度切換前位置隱私區(qū)域Ck1的外部，Ck2和Ck1沒(méi)有交集，故對(duì)中心點(diǎn)攻擊、形心偏移攻擊和無(wú)差別攻擊均有很好的防御效果，隱私度切換成功率高.

4 實(shí)驗(yàn)和結(jié)果分析

實(shí)驗(yàn)環(huán)境如下:CPU Intel (R)Core (TM)i3-2310M 2.10 GHz，內(nèi)存6 GB，Ubuntu 12.04.1，Python 2.7.3，Bash shell 4.2.24.

4.1 切換成功率分析

保證隱私度切換成功的目的是實(shí)現(xiàn)用戶(hù)個(gè)性化位置隱私.切換后的用戶(hù)隱私度泄露率P 定義為

式中，Rs為切換成功率，k1、k2分別為切換前、后的隱私度.

在中心點(diǎn)攻擊和無(wú)差別攻擊下3 種算法的切換成功率如表1 所示.在中心點(diǎn)攻擊下，不管隱私度如何切換，普通位置隱私區(qū)域生成法的切換成功率均非常低，幾乎為0，這是因?yàn)椴捎闷胀ㄎ恢秒[私區(qū)域生成法生成的隱私區(qū)域與切換前的隱私區(qū)域的中心重合，所以容易遭受中心點(diǎn)攻擊，使隱私度切換失敗;初級(jí)形心偏移法和高級(jí)偏移法的切換成功率較高，在某些情況下甚至接近100%.在無(wú)差別攻擊下，不論隱私度如何切換，普通位置隱私區(qū)域生成法的切換成功率均很低;初級(jí)形心偏移法的切換成功率在小范圍內(nèi)隨著切換幅度的增加而增加，切換幅度超過(guò)一定范圍后切換成功率反而下降，極端情況下切換可能不成功;高級(jí)形心偏移法的切換成功率非常高，均達(dá)到了100%.

表1 3 種算法的切換成功率Table 1 Success rates of switching of three algorithms

表2 3 種算法的用戶(hù)隱私度泄露率Table 2 Disclosure rates of user privacy of three algorithms

在中心點(diǎn)攻擊和無(wú)差別攻擊下3 種算法的用戶(hù)隱私度泄露率如表2 所示.在中心點(diǎn)攻擊和相同的切換幅度下，初級(jí)形心偏移法和高級(jí)形心偏移法大幅降低了用戶(hù)的隱私度泄露率，達(dá)到了隱私度切換的目的;高級(jí)形心偏移法的隱私度泄露率比初級(jí)形心偏移法低.

由于初級(jí)形心偏移法和高級(jí)形心偏移法對(duì)位置隱私區(qū)域的形心進(jìn)行了偏移，故在中心點(diǎn)攻擊下的防御效果較好，切換成功率較高，改善了普通位置隱私區(qū)域生成法對(duì)中心點(diǎn)攻擊防御效果差的缺陷.

在無(wú)差別攻擊和相同的切換幅度下，普通位置隱私區(qū)域生成法的切換成功率非常低，幾乎不成功，隱私度泄露率最大;初級(jí)形心偏移法在隱私度切換幅度較大的情況下，切換成功率不理想，隱私度提高不多，用戶(hù)隱私度泄露率較高;高級(jí)形心偏移法的切換成功率高，用戶(hù)隱私度泄露率低.這是由于無(wú)差別攻擊是對(duì)切換后的隱私區(qū)域等比縮小到切換前隱私區(qū)域的大小，故形心點(diǎn)位置沒(méi)有變化的普通位置隱私區(qū)域生成法的隱私度切換成功率低，用戶(hù)隱私度泄露率高;初級(jí)形心偏移法對(duì)形心進(jìn)行了偏移，但切換前的隱私區(qū)域仍然包含在切換后隱私區(qū)域內(nèi)，且在用戶(hù)均勻分布的歐幾里得空間中，隱私度的切換幅度達(dá)到某一值后，切換幅度越大，用戶(hù)整體分布越均勻，故形心偏移量越小，隱私度切換成功率越小，用戶(hù)隱私度泄露率越大;高級(jí)形心偏移法切換前后的隱私區(qū)域無(wú)交集，故隱私度切換成功率大，隱私度泄露率小.

4.2 服務(wù)結(jié)果可靠度分析

采用3 種位置隱私區(qū)域生成法實(shí)現(xiàn)個(gè)性化位置隱私保護(hù)的LBS 的服務(wù)結(jié)果可靠度如表3 所示.普通位置隱私區(qū)域生成法對(duì)切換前隱私區(qū)域進(jìn)行等比放大，因此采用此方法實(shí)現(xiàn)個(gè)性化位置隱私保護(hù)的LBS 質(zhì)量下降不多.初級(jí)形心偏移法對(duì)切換前隱私區(qū)域進(jìn)行少量偏移，因此采用初級(jí)形心偏移法實(shí)現(xiàn)個(gè)性化位置隱私保護(hù)的LBS 質(zhì)量保持在可接受的范圍內(nèi).高級(jí)形心偏移法將切換后位置隱私區(qū)域移到切換前位置隱私區(qū)域的外部，移動(dòng)幅度隨著切換前位置隱私區(qū)域面積的增大而增大，因此移動(dòng)幅度越大，采用高級(jí)形心偏移法實(shí)現(xiàn)個(gè)性化位置隱私保護(hù)的LBS 質(zhì)量下降越多，當(dāng)切換前隱私度為1 000時(shí)，服務(wù)結(jié)果可靠度下降到50%左右.

表3 3 種算法的服務(wù)結(jié)果可靠度Table 3 Reliability of service results of three algorithms

4.3 隱私度切換討論

從表2 可以看出，在中心點(diǎn)攻擊和無(wú)差別攻擊下，采用3 種算法生成切換后的隱私區(qū)域時(shí)，切換前后的隱私度與隱私度泄露率有一定的關(guān)系:切換前的隱私度較小，且切換前后的隱私度差別較小時(shí)，隱私度泄露率較高;切換前后的隱私度相差較大或切換前的隱私度很高時(shí)，切換后的隱私度泄露率較低.

從表1－3 可以看出:普通位置隱私區(qū)域生成法的服務(wù)結(jié)果可靠度較高，但其切換成功率低，隱私度泄露率高;初級(jí)形心偏移法的切換成功率、隱私度泄露率和服務(wù)結(jié)果可靠度介于普通位置隱私區(qū)域生成法和高級(jí)形心偏移法之間;采用高級(jí)形心偏移法生成切換后的隱私區(qū)域時(shí)，若用戶(hù)的隱私度已足夠大(如1000)且還要切換到一個(gè)稍高一點(diǎn)的隱私度(如1001)，雖然隱私度泄露率低，但服務(wù)結(jié)果的可靠度下降得很快，因此，只有當(dāng)用戶(hù)的隱私度由較小值切換到較大值時(shí)，采用高級(jí)形心偏移法生成切換后的隱私區(qū)域才可以獲得較高的服務(wù)結(jié)果可靠度和較低的隱私度泄露率.

5 結(jié)論

文中基于空間混淆位置隱私保護(hù)方法研究了隱私度切換時(shí)的位置隱私區(qū)域生成算法.首先提出了初級(jí)形心偏移法，該算法繼承了普通位置隱私區(qū)域生成法簡(jiǎn)單、開(kāi)銷(xiāo)小的優(yōu)點(diǎn)，提高了對(duì)中心點(diǎn)攻擊和形心偏移攻擊的防御能力，同時(shí)也保持了較高的隱私度切換成功率.接著，提出了高級(jí)形心偏移法，該算法在初級(jí)形心偏移法的基礎(chǔ)上進(jìn)行改進(jìn)，增加了對(duì)無(wú)差別攻擊的防御能力，進(jìn)一步提高了隱私度切換的成功率，降低用戶(hù)隱私度泄露率.但高級(jí)形心偏移法是以犧牲LBS 服務(wù)結(jié)果的可靠度為代價(jià)來(lái)提高隱私度切換成功率的，故下一步的工作重點(diǎn)是基于空間混淆位置隱私保護(hù)方法，研究安全、高效的個(gè)性化位置隱私區(qū)域生成算法，進(jìn)一步改善提供良好個(gè)性化位置隱私保護(hù)功能的LBS 的服務(wù)質(zhì)量.

［1］Gedik Bugra，Liu Ling.Protecting location privacy with personalized k-anonymity:architecture and algorithms［J］.IEEE Transactions on Mobile Computing，2008，7(1):1-18.

［2］Puttaswamy Krishna P N，Zhao Ben Y.Preserving privacy in location-based mobile social applications ［C］∥Proceedings of the Eleventh Workshop on Mobile Computing Systems ＆ Applications.Annapolis:ACM，2010:1-6.

［3］Beresford Alastair R，Stajano Frank.Location privacy in pervasive computing ［J］.IEEE Pervasive Computing，2003，2(1):46-55.

［4］Hong Jason I，Landay James A.An architecture for privacy sensitive ubiquitous computing ［C］∥Proceedings of the 2nd International Conference on Mobile Systems，Applications，and Services.Boston:ACM，2004:177-189.

［5］Pfitamann A，Kohntopp M.Anonymity，unobservability，and pseudonymity:a proposal for terminology［C］∥Designing Privacy Enhancing Technologies.Berlin/Heidelberg:Springer-Verlag，2001:1-9.

［6］Gruteser M，Grunwald D.Anonymous usage of location-based services through spatial and temporal cloaking［C］∥Proceedings of the 1st International Conference on Mobile Systems，Applications and Services.San Francisco:ACM，2003:31-42.

［7］Bamba B，Liu L.PrivacyGrid:supporting anonymous location queries in mobile environments［R］.Atlanta:College of Computing，Georgia Institute of Technology，2007:28-36.

［8］Gedik Bugra，Liu Ling.Location privacy in mobile systems:a personalized anonymization model［C］∥Proceedings of the 25th IEEE International Conference on Distributed Computing Systems.Columbus:IEEE，2005:620-629.

［9］Machanavajjhala A，Gehrke J，Kifer D，et al.L-diversity:privacy beyond k-anonymity ［C］∥Proceedings of the 22nd International Conference on Data Engineering.Atlanta:IEEE，2006:24-36.

［10］Shin Heechang，Atluri Vijayalakshmi，Vaidya Jaideep.A profile anonymization model for privacy in a personalized location based service environment［C］∥Proceedings of the Ninth International Conference on Mobile Data Management.Beijing:IEEE，2008:73-80.

［11］Duri Sastry，Gruteser Marco，Liu Xuan，et al.Framework for security and privacy in automotive telematics［C］∥Proceedings of the 2nd International Workshop on Mobile Commerce.Atlanta:ACM，2002:25-32.

［12］Xu Toby，Cai Ying.Location-anonymity in continuous location-based services［C］∥Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems.Seattle:ACM，2007:1-8.

［13］Kalnis Panos，Ghinita Gabriel，Mouratidis K，et al.Preventing location-based identity inference in anonymous spatial queries ［J］.IEEE Transactions on Knowledge and Data Engineering，2007，19(12):1719-1733.

［14］Truong Q C，Truong Anh T，Dang Tran K.Privacy preserving through a memorizing algorithm in location-based services［C］∥Proceeding of the 7th International Conference on Advances in Mobile Computing and Multimedia.Kuala Lumpur:ACM，2009:146-153.

［15］Ghinita G，Zhao K，Papadias D，et al.A reciprocal framework for spatial k-anonymity［J］.Journal of Information Systems，2010，35(3):299-314.

［16］Ghinita G，Damiani M L，Cilvestri C，et al.Preventing velocity-based linkage attacks in location-aware applications［C］∥Proceedings of ACM International Symposium on Advances in Geographic Information Systems.Seattle:ACM，2009:246-255.

［17］Ge Zhong，Hengartner Urs.Toward a distributed k-anonymity protocol for location privacy［C］∥Proceedings of the 7th IEEE International Conference on Pervasive Computing and Communications.Galveston:IEEE，2009:255-262.

［18］Sweeney Latanya.k-anonymity:a model for protecting privacy［J］.International Journal on Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，2002，10(5):557-570.

［19］Freudiger Julien，Manshaei Mohammad Hossein，Hubaux Jean-Pierre，et al.Non-cooperative location privacy［J］.IEEE Transactions on Dependable and Secure Computing，2013，10(2):84-98.

［20］Hossain Amina，Hossain Al-Amin，Jang Sung-Jae，et al.Privacy-aware cloaking technique in location-based services［C］∥Proceedings of IEEE the First International Conference on Mobile Services.Honolulu:IEEE，2012:9-16.

［21］Shokri Reza，Papadimitratos Panos，Theodorakopoulos George，et al.Collaborative location privacy ［C］∥Proceedings of IEEE the Eighth International Conference on Mobile Ad-Hoc and Sensor Systems.Valencia:IEEE，2011:500-509.

［22］Lu Hua，Jensen C S，Yiu M L.PAD:privacy-area aware，dummy-based location privacy in mobile services［C］∥Proceedings of the Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access.New York:ACM，2008:16-23.

［23］Kido H，Yanagisawa Y，Satoh T.An anonymous communication technique using dummies for location-based services［C］∥Proceedings of 2005 IEEE International Conference on Pervasive Services.Santorini:IEEE，2005:88-97.

［24］Du Jing，Xu Jianliang，Tang Xueyan，et al.iPDA:supporting privacy-preserving location-based mobile services［C］∥Proceeding of the 8th International Conference on Mobile Data Management.Mannheim:IEEE，2007:212-214.