基于普通匿名區(qū)域生成的改進(jìn)算法

王智明

(莆田學(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]通過刪除最遠(yuǎn)足跡的方式提高了LBS服務(wù)質(zhì)量。PALANISAMY等[5]要求用戶離開Mixzone區(qū)時(shí)使用假名，以通過區(qū)域關(guān)聯(lián)性的攻擊。

匿名區(qū)域切換過程中常見的三種攻擊：(1)中心點(diǎn)攻擊，計(jì)算切換前后匿名區(qū)域的中心點(diǎn)，如果重合，則攻擊者認(rèn)為是來自同一用戶的請(qǐng)求，不重合則放棄攻擊；(2)等比縮放攻擊，攻擊者在服務(wù)器上獲取切換后的匿名區(qū)域，保持中心點(diǎn)不變按前后隱私度k比例進(jìn)行等比縮放，計(jì)算切換前的匿名區(qū)域。(3)線性偏移攻擊，攻擊者在服務(wù)器上對(duì)用戶發(fā)來的匿名區(qū)域中心點(diǎn)進(jìn)行記錄，通過一段時(shí)間的觀察，推測(cè)出匿名區(qū)域切換前后的線性關(guān)系，破解線性偏移函數(shù)。

普通匿名區(qū)域生成算法依據(jù)匿名區(qū)域切換前后的隱私度k的比值，保持中心點(diǎn)不變等比縮放原匿名區(qū)域，這樣很容易被中心點(diǎn)攻擊者攻破，而切換前后的匿名區(qū)域存在較大的交集，不能很好對(duì)付對(duì)等比縮放攻擊。線性偏移攻擊雖然前期無法對(duì)普通匿名區(qū)域生成算法構(gòu)成威脅，但隨著用戶申請(qǐng)次數(shù)的增加，線性偏移方程被破解的可能性加大。綜上，普通匿名區(qū)域生成算法不能很好應(yīng)對(duì)三種類型攻擊。

1 基于普通匿名區(qū)域生成的兩種改進(jìn)算法

1．1 迭代搜索線性偏移區(qū)域切換算法(算法1)

普通匿名區(qū)域生成算法在切換匿名區(qū)域時(shí)，保持區(qū)域中心點(diǎ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í)針方向依次記為R1、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)綜合開銷也比較小，但該算法不足是存在被等比縮放攻擊的風(fēng)險(xiǎn)。

1．2 分布式匿名區(qū)域外溢切換算法(算法2)

迭代搜索線性偏移區(qū)域切換(算法1)基于用戶密度進(jìn)行線性偏移，具有一定動(dòng)態(tài)性和隨機(jī)性，能較好抵抗攻擊，但當(dāng)切換區(qū)域前后偏移位移較小時(shí)，仍然存在被等比縮放攻擊的風(fēng)險(xiǎn)。本節(jié)通過對(duì)算法1改進(jìn)，提出分布式匿名區(qū)域外溢切換算法(算法2)，具體步驟如下：

(1)對(duì)原匿名矩形區(qū)域CK的4個(gè)頂點(diǎn)做兩對(duì)角線，從上矩形邊順時(shí)針方向?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為半徑畫圓，如圖2(b)所示，以邊Li(包括延長線)為中線，選取位于匿名區(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ù)滿意度顯著提升，但算法開銷相對(duì)較大。

1．3 算法1和算法2的綜合應(yīng)用

普通匿名區(qū)域生成算法存在問題：當(dāng)用戶請(qǐng)求區(qū)域切換次數(shù)越大時(shí)，中心點(diǎn)線性偏移函數(shù)被攻破的壓力就越大；算法2安全性、用戶服務(wù)滿意度高，但算法較復(fù)雜，時(shí)間開銷較大。算法1的系統(tǒng)開銷與安全性介于上述兩算法之間。因此在LBS的實(shí)際應(yīng)用中，可在用戶請(qǐng)求切換的次數(shù)N值較小時(shí)，使用普通匿名區(qū)域生成算法，當(dāng)N值較大時(shí)，依據(jù)安全性和用戶服務(wù)質(zhì)量需求選擇算法1或算法2，充分做到揚(yáng)長避短，具體步驟如下。

PROCEDURE:

Ni=c(USERi)；

IFNi≤5

THEN DO 普通匿名區(qū)域生成算法；

IFNi>5 AND RISK(等比縮放攻擊)=0

THEN DO本文算法1；

ELSE

DO 本文算法2；

END PROCEDURE

2 試驗(yàn)和結(jié)果分析

試驗(yàn)環(huán)境為處理器Intel(R) Core(TM)i3-4170@3.70 GHz CPU，8 GB內(nèi)存，1 TB硬盤，Python

2.7.12。

2．1 3種匿名區(qū)域切換算法的耗時(shí)比較

匿名區(qū)域切換的耗時(shí)會(huì)直接影響到用戶的體驗(yàn)，是衡量算法的重要指標(biāo)之一。3種匿名區(qū)域切換算法的耗時(shí)試驗(yàn)結(jié)果見表1?？梢钥闯觯浩胀涿麉^(qū)域生成算法耗時(shí)明顯小于另外兩算法，這是由于普通匿名區(qū)域生成算法僅依據(jù)切換前后隱私度k值等比例擴(kuò)大原匿名區(qū)域，算法簡單，生成新匿名區(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ū)域的切換。

2．2 3種匿名區(qū)域切換算法匿名區(qū)域切換成功率

匿名區(qū)域切換成功率是生成新匿名區(qū)域的成功概率，它間接影響了用戶位置的泄露概率，是區(qū)域切換算法安全性的重要指標(biāo)之一。在中心點(diǎn)與等比縮放兩種不同攻擊情況下，3種算法區(qū)域切換的成功率分別見表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í)，按用戶密度來決定切換后區(qū)域的方位，同時(shí)對(duì)原匿名區(qū)域做了外溢處理來減少用戶真實(shí)位置泄露的風(fēng)險(xiǎn)，所以有效抵御了各類攻擊[14-15]。

3 結(jié)語

隨著LBS服務(wù)應(yīng)用的縱深發(fā)展，個(gè)人位置隱私泄露的風(fēng)險(xiǎn)越來越大。通過對(duì)個(gè)人位置隱私保護(hù)技術(shù)的分析和研究，改進(jìn)了普通匿名區(qū)域生成算法，提出的迭代搜索線性偏移區(qū)域切換算法保留了時(shí)間開銷小、響應(yīng)速度快的優(yōu)點(diǎn)，能有效抵御中心點(diǎn)和線性偏移攻擊；分布式匿名區(qū)域外溢切換算法進(jìn)一步引入了用戶密度與分布式概念，能進(jìn)一步有效抵御等比縮放攻擊。在不同的應(yīng)用場(chǎng)景，依據(jù)用戶申請(qǐng)切換的次數(shù)，將兩種算法結(jié)合起來使用能達(dá)到更好效果。