王智明
(莆田學(xué)院 機(jī)電與信息工程學(xué)院,福建 莆田 351100)
基于位置的服務(wù)(location based services,LBS)集成了測(cè)繪、衛(wèi)星導(dǎo)航、GIS等技術(shù),為我們提供諸如地圖導(dǎo)航、網(wǎng)約車、廣告推送等各式各樣便利的服務(wù)。然而作為硬幣的另一面,這些海量數(shù)據(jù)中不可避免會(huì)包含一些企業(yè)或個(gè)人的隱私數(shù)據(jù)[1]。早在2002年,SWEENEY提出k-匿名(k-anonymity)模型[2],2006年,MACHANAVAJJHALA[3]對(duì)該模型進(jìn)行改進(jìn),提出了L-diversity,規(guī)定每個(gè)信息屬性等價(jià)類不能少于L個(gè)敏感屬性值。2016年,LI等[4]通過(guò)刪除最遠(yuǎn)足跡的方式提高了LBS服務(wù)質(zhì)量。PALANISAMY等[5]要求用戶離開(kāi)Mixzone區(qū)時(shí)使用假名,以通過(guò)區(qū)域關(guān)聯(lián)性的攻擊。
匿名區(qū)域切換過(guò)程中常見(jiàn)的三種攻擊:(1)中心點(diǎn)攻擊,計(jì)算切換前后匿名區(qū)域的中心點(diǎn),如果重合,則攻擊者認(rèn)為是來(lái)自同一用戶的請(qǐng)求,不重合則放棄攻擊;(2)等比縮放攻擊,攻擊者在服務(wù)器上獲取切換后的匿名區(qū)域,保持中心點(diǎn)不變按前后隱私度k比例進(jìn)行等比縮放,計(jì)算切換前的匿名區(qū)域。(3)線性偏移攻擊,攻擊者在服務(wù)器上對(duì)用戶發(fā)來(lái)的匿名區(qū)域中心點(diǎn)進(jìn)行記錄,通過(guò)一段時(shí)間的觀察,推測(cè)出匿名區(qū)域切換前后的線性關(guān)系,破解線性偏移函數(shù)。
普通匿名區(qū)域生成算法依據(jù)匿名區(qū)域切換前后的隱私度k的比值,保持中心點(diǎn)不變等比縮放原匿名區(qū)域,這樣很容易被中心點(diǎn)攻擊者攻破,而切換前后的匿名區(qū)域存在較大的交集,不能很好對(duì)付對(duì)等比縮放攻擊。線性偏移攻擊雖然前期無(wú)法對(duì)普通匿名區(qū)域生成算法構(gòu)成威脅,但隨著用戶申請(qǐng)次數(shù)的增加,線性偏移方程被破解的可能性加大。綜上,普通匿名區(qū)域生成算法不能很好應(yīng)對(duì)三種類型攻擊。
普通匿名區(qū)域生成算法在切換匿名區(qū)域時(shí),保持區(qū)域中心點(diǎn)不變或簡(jiǎn)單進(jìn)行線性偏移,容易為惡意者所攻擊,不能有效抵御中心點(diǎn)攻擊和線性偏移攻擊,本節(jié)對(duì)普通匿名區(qū)域生成算法進(jìn)行改進(jìn),提出迭代搜索線性偏移區(qū)域切換算法(算法1),具體步驟如下:
(1)將原匿名矩形區(qū)域中心點(diǎn)O作為坐標(biāo)原點(diǎn),將矩形區(qū)域分為I、II、III、IV面積相等的4個(gè)子矩形區(qū)域,從左上子矩形順時(shí)針?lè)较蛞来斡洖镽1、R2、R3、R4,計(jì)算各子矩形的用戶數(shù)Ni=c(Ri),選取Ni值最大的區(qū)域Ri作為迭代矩形,進(jìn)一步劃分為四個(gè)子矩形,直到MAXNi≤3,劃分結(jié)束。
(2)從Ri區(qū)域隨機(jī)選一用戶U,連接O、U兩點(diǎn)的直線y=ax+b作為偏移函數(shù)。如圖1(a)所示,迭代搜索的矩形編號(hào)依此為2、7、10,則從10號(hào)矩形中隨機(jī)選用戶。
(3)依據(jù)切換前后的隱私度k的比值,中心點(diǎn)不變等比例縮放原匿名區(qū)域,生成初步匿名區(qū)域CK1。區(qū)域4個(gè)頂點(diǎn)依次記為(xLeft,yTop)、(xLeft,yBot)、(xRight,yTop)、(xRight,yBot)。
(4)根據(jù)用戶確定的橫坐標(biāo)位移量△x,由偏移方程y=ax+b可得△y=a△x,令xLeft=xLeft+△x、xRight=xRight+△x、yTop=yTop+a△x、yBot=yBot+a△x。
(5)將(xLeft,yTop)、(xLeft,yBot)、(xRight,yTop)、(xRight,yBot)作為四個(gè)頂點(diǎn)分別映射到x、y坐標(biāo)軸,生成線性偏移切換后的區(qū)域CK2,如圖1(b)所示。
圖1 迭代搜索線性偏移區(qū)域切換算法
(6)為匿名區(qū)域CK2構(gòu)建用戶集合U2,并計(jì)算集合用戶數(shù)N=C(U2)。
(7)若N≥k,且CK2的面積SCK2≤Smax,則匿名區(qū)域切換成功,跳到步驟(10)。其中k表示切換后隱私度,Smax表示用戶可接受的最大隱私區(qū)域面積。
(8)若N (9)若SCK2>Smax,則保持區(qū)域中心點(diǎn)不變等比縮小匿名區(qū)域CK2至Smax,即SCK2=Smax,返回步驟(6)重新計(jì)算用戶數(shù)量。 (10) 返回線性偏移后的匿名區(qū)域CK2,算法結(jié)束。 迭代搜索線性偏移區(qū)域切換算法針對(duì)普通匿名區(qū)域生成算法的中心點(diǎn)不變進(jìn)行優(yōu)化,對(duì)等比縮放后的匿名區(qū)域進(jìn)行線性偏移,偏移方向依據(jù)用戶密度具有隨機(jī)性,其區(qū)域偏移的規(guī)律難被攻擊者捕獲,能很好應(yīng)對(duì)中心點(diǎn)和線性偏移的攻擊,系統(tǒng)綜合開(kāi)銷也比較小,但該算法不足是存在被等比縮放攻擊的風(fēng)險(xiǎn)。 迭代搜索線性偏移區(qū)域切換(算法1)基于用戶密度進(jìn)行線性偏移,具有一定動(dòng)態(tài)性和隨機(jī)性,能較好抵抗攻擊,但當(dāng)切換區(qū)域前后偏移位移較小時(shí),仍然存在被等比縮放攻擊的風(fēng)險(xiǎn)。本節(jié)通過(guò)對(duì)算法1改進(jìn),提出分布式匿名區(qū)域外溢切換算法(算法2),具體步驟如下: (1)對(duì)原匿名矩形區(qū)域CK的4個(gè)頂點(diǎn)做兩對(duì)角線,從上矩形邊順時(shí)針?lè)较驅(qū)^(qū)域分為I、II、III、IV四個(gè)三角形子區(qū)域,依次記為T1、T2、T3、T4,四條矩形邊依次相應(yīng)記作L1、L2、L3、L4。計(jì)算T1、T2、T3、T4各區(qū)域內(nèi)的用戶數(shù)Ni=c(Ti),選取用戶密度值ρ=Ni/STi(STi表示Ti區(qū)域面積)最大的兩個(gè)區(qū)域,生成這兩區(qū)域?qū)?yīng)i值的集合{m,n}。分別令i=m、n,重復(fù)執(zhí)行(2)至(12)步驟兩次,最終得到兩個(gè)分散的匿名區(qū)CKm、CKn。如圖2(a)所示。 (3)以Li的中點(diǎn)O作為圓心,r為半徑畫(huà)圓,如圖2(b)所示,以邊Li(包括延長(zhǎng)線)為中線,選取位于匿名區(qū)域外側(cè)的半圓區(qū)域CKr。 圖2 分布式匿名區(qū)域外溢切換算法 (4)初始化空用戶集U={?} ,生成半圓區(qū)域CKr的用戶集U。 (5)將U內(nèi)所有用戶點(diǎn)映射到x、y坐標(biāo)軸,得到區(qū)域邊界用戶點(diǎn)相應(yīng)的x、y軸極值xmin、xmax,ymin、ymax。 (6)以(xmin,ymin)、(xmin,ymax)、(xmax,ymax)、(xmax,ymin)為4個(gè)頂點(diǎn),生成切換后的匿名區(qū)域CKi,計(jì)算集合用戶數(shù)N=c(U)和CKi區(qū)域的面積SCKi。 (12)匿名區(qū)域切換完成,返回匿名區(qū)域CKi,算法結(jié)束。 分布式匿名區(qū)域外溢切換算法利用了用戶的分布密度,同時(shí)對(duì)原匿名區(qū)域做了外溢處理,攻擊者很難獲取用戶真實(shí)地址,區(qū)域切換的成功概率高。切換后的匿名區(qū)域是由兩塊區(qū)域(CK1、CK3)組成如圖2(a),這樣能有效提高用戶的服務(wù)滿意度[6],因?yàn)樵趩文涿麉^(qū)域情況下,如果用戶需要的服務(wù)點(diǎn)剛好落在新匿名區(qū)域中或者靠近原匿名區(qū)附近,用戶可以達(dá)到較高的滿意度;但是如果用戶需要的服務(wù)點(diǎn)落在新匿名區(qū)遠(yuǎn)離原匿名區(qū)那一側(cè),而用戶真實(shí)位置剛好又位于原匿名區(qū)中遠(yuǎn)離新匿名區(qū)的那一側(cè),則服務(wù)質(zhì)量差,用戶滿意度低。 綜上,分布式匿名區(qū)域外溢切換算法能很好應(yīng)對(duì)中心點(diǎn)、線性偏移、等比縮放三類攻擊,安全性和用戶服務(wù)滿意度顯著提升,但算法開(kāi)銷相對(duì)較大。 普通匿名區(qū)域生成算法存在問(wèn)題:當(dāng)用戶請(qǐng)求區(qū)域切換次數(shù)越大時(shí),中心點(diǎn)線性偏移函數(shù)被攻破的壓力就越大;算法2安全性、用戶服務(wù)滿意度高,但算法較復(fù)雜,時(shí)間開(kāi)銷較大。算法1的系統(tǒng)開(kāi)銷與安全性介于上述兩算法之間。因此在LBS的實(shí)際應(yīng)用中,可在用戶請(qǐng)求切換的次數(shù)N值較小時(shí),使用普通匿名區(qū)域生成算法,當(dāng)N值較大時(shí),依據(jù)安全性和用戶服務(wù)質(zhì)量需求選擇算法1或算法2,充分做到揚(yáng)長(zhǎng)避短,具體步驟如下。 PROCEDURE: Ni=c(USERi); IFNi≤5 THEN DO 普通匿名區(qū)域生成算法; IFNi>5 AND RISK(等比縮放攻擊)=0 THEN DO本文算法1; ELSE DO 本文算法2; END PROCEDURE 試驗(yàn)環(huán)境為處理器Intel(R) Core(TM)i3-4170@3.70 GHz CPU,8 GB內(nèi)存,1 TB硬盤,Python 2.7.12。 匿名區(qū)域切換的耗時(shí)會(huì)直接影響到用戶的體驗(yàn),是衡量算法的重要指標(biāo)之一。3種匿名區(qū)域切換算法的耗時(shí)試驗(yàn)結(jié)果見(jiàn)表1。可以看出:普通匿名區(qū)域生成算法耗時(shí)明顯小于另外兩算法,這是由于普通匿名區(qū)域生成算法僅依據(jù)切換前后隱私度k值等比例擴(kuò)大原匿名區(qū)域,算法簡(jiǎn)單,生成新匿名區(qū)域的速度比較快。當(dāng)切換前隱私度k=1時(shí),切換后隱私度k值越大其所對(duì)應(yīng)的耗時(shí)隨之呈增加的趨勢(shì),但并不是呈成正比例增加。耗時(shí)與切換前后△k值變化有關(guān),當(dāng)△k較小時(shí)切換耗時(shí)較少,△k值較大時(shí)迭代搜索線性偏移區(qū)域切換算法和分布式匿名區(qū)域外溢切換算法的耗時(shí)增加較多,但其總耗時(shí)能夠控制在用戶可接受的范圍之內(nèi)[7]。在時(shí)間消耗方面,普通匿名區(qū)域生成算法耗時(shí)最少優(yōu)勢(shì)明顯,然后依次是迭代搜索線性偏移區(qū)域切換算法、分布式匿名區(qū)域外溢切換算法[8]。 表1 不同算法的匿名區(qū)域切換耗時(shí) 由以上結(jié)果可知,在注重時(shí)間效率而對(duì)安全性不敏感的場(chǎng)景下可以優(yōu)先采用普通匿名區(qū)域生成算法進(jìn)行匿名區(qū)域的切換。 匿名區(qū)域切換成功率是生成新匿名區(qū)域的成功概率,它間接影響了用戶位置的泄露概率,是區(qū)域切換算法安全性的重要指標(biāo)之一。在中心點(diǎn)與等比縮放兩種不同攻擊情況下,3種算法區(qū)域切換的成功率分別見(jiàn)表2和表3。可以看出,在兩種攻擊情況下,普通匿名區(qū)域生成算法的切換成功率均維持在[0.00%,0.05%]之間的低水平。這主要?dú)w因于普通匿名區(qū)域生成算法切換前后中心點(diǎn)保持不變,容易遭受中心點(diǎn)和等比縮放攻擊而導(dǎo)致用戶真實(shí)位置泄露[9-10]。 表2 中心點(diǎn)攻擊下不同算法的匿名區(qū)域切換成功率 表3 等比縮放攻擊下不同算法的區(qū)域切換成功率 由表2得知,迭代搜索線性偏移區(qū)域切換算法在中心點(diǎn)攻擊時(shí),能夠保持很高的切換成功率,大多數(shù)情況非常接近100%,這是由于該算法針對(duì)中心點(diǎn)攻擊的特點(diǎn),對(duì)匿名區(qū)域的中心點(diǎn)進(jìn)行了線性偏移[11]。而表3數(shù)據(jù)顯示,在面對(duì)等比縮放攻擊時(shí),該算法的表現(xiàn)就不盡人意,最高的成功率只有34.96%,有的情況只是個(gè)位數(shù),究其因主要是切換前后的隱私區(qū)域存在一定的重疊面積,若用戶真實(shí)位置剛好處于其中,則會(huì)導(dǎo)致位置泄露[12-13]。 由表2、表3看出,分布式匿名區(qū)域外溢切換算法在面對(duì)中心點(diǎn)攻擊和等比縮放攻擊時(shí),都有良好表現(xiàn),切換成功率達(dá)到了100%。這是由于該算法在區(qū)域生成時(shí),按用戶密度來(lái)決定切換后區(qū)域的方位,同時(shí)對(duì)原匿名區(qū)域做了外溢處理來(lái)減少用戶真實(shí)位置泄露的風(fēng)險(xiǎn),所以有效抵御了各類攻擊[14-15]。 隨著LBS服務(wù)應(yīng)用的縱深發(fā)展,個(gè)人位置隱私泄露的風(fēng)險(xiǎn)越來(lái)越大。通過(guò)對(duì)個(gè)人位置隱私保護(hù)技術(shù)的分析和研究,改進(jìn)了普通匿名區(qū)域生成算法,提出的迭代搜索線性偏移區(qū)域切換算法保留了時(shí)間開(kāi)銷小、響應(yīng)速度快的優(yōu)點(diǎn),能有效抵御中心點(diǎn)和線性偏移攻擊;分布式匿名區(qū)域外溢切換算法進(jìn)一步引入了用戶密度與分布式概念,能進(jìn)一步有效抵御等比縮放攻擊。在不同的應(yīng)用場(chǎng)景,依據(jù)用戶申請(qǐng)切換的次數(shù),將兩種算法結(jié)合起來(lái)使用能達(dá)到更好效果。1.2 分布式匿名區(qū)域外溢切換算法(算法2)
1.3 算法1和算法2的綜合應(yīng)用
2 試驗(yàn)和結(jié)果分析
2.1 3種匿名區(qū)域切換算法的耗時(shí)比較
2.2 3種匿名區(qū)域切換算法匿名區(qū)域切換成功率
3 結(jié)語(yǔ)