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

摘 要：為降低個(gè)人位置信息在LBS應(yīng)用過程中的泄露風(fēng)險(xiǎn)，基于普通匿名區(qū)域生成算法提出了迭代搜索線性偏移區(qū)域切換算法與分布式匿名區(qū)域外溢切換算法。迭代搜索線性偏移區(qū)域切換算法對(duì)區(qū)域中心點(diǎn)進(jìn)行線性偏移來提高匿名區(qū)域切換成功率;分布式匿名區(qū)域外溢切換算法根據(jù)區(qū)域用戶分布情況來決定生成區(qū)域的方位，對(duì)匿名區(qū)域?qū)嵭蟹植际胶屯庖缣幚恚钟粜Ч头?wù)質(zhì)量明顯增強(qiáng)。試驗(yàn)表明，在中心點(diǎn)和等比縮放攻擊情況下，兩種改進(jìn)算法的區(qū)域切換成功率最高能達(dá)100%，顯著優(yōu)于普通匿名區(qū)域生成算法。

關(guān)鍵詞：基于位置的服務(wù);隱私保護(hù);匿名區(qū)域;區(qū)域切換

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)志碼：A

基于位置的服務(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)不變或簡(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í)針方向依次記為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）所示。

（6）為匿名區(qū)域CK2構(gòu)建用戶集合U2，并計(jì)算集合用戶數(shù)N=C（U2）。

（7）若N≥k，且CK2的面積SCK2≤Smax，則匿名區(qū)域切換成功，跳到步驟（10）。其中k表示切換后隱私度，Smax表示用戶可接受的最大隱私區(qū)域面積。

（8）若Nlt;k，且SCK2≤Smax，則用啞元填充至N=k，匿名區(qū)域切換完成，跳到步驟（10）。

（9）若SCK2gt;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）所示。

（2）原匿名區(qū)域長(zhǎng)寬記作la、lb，計(jì)算與原匿名區(qū)域等面積圓對(duì)應(yīng)的半徑r值，令la lb=πr2，即r=la lbπ。

（3）以Li的中點(diǎn)O作為圓心，r為半徑畫圓，如圖2（b）所示，以邊Li（包括延長(zhǎng)線）為中線，選取位于匿名區(qū)域外側(cè)的半圓區(qū)域CKr。

（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。

（7）若N=k2，且SCKi≤Smax2，則匿名區(qū)域切換成功，跳到步驟（12）。其中k表示切換后隱私度，Smax表示用戶可接受的最大隱私區(qū)域總面積。

（8）若Ngt;k2，且SCKi≤Smax2，從區(qū)域最左側(cè)起依次剔除（N=k2）個(gè)用戶，如果若干用戶x坐標(biāo)值一樣，按y坐標(biāo)值從大到小依次選取用戶剔除，生成新用戶集U，返回步驟（5）。

9）若Nlt;k2，且SCKi≤Smax2，則擴(kuò)大用戶搜索半徑r，令r=（1+a）r，0lt;alt;1，返回步驟（3）重構(gòu)區(qū)域CKr。

（10）若SCKigt;Smax2，則等比縮小匿名區(qū)域CKi面積至Smax2，即SCKi=Smax2，返回步驟（5）。

（11）若Nlt;k2，則用啞元填充至N=k2。

（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)長(zhǎng)避短，具體步驟如下。

PROCEDURE：

Ni=c（USERi）;

IF Ni≤5

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

IF Nigt;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ū)域，算法簡(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]。

由以上結(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?？梢钥闯觯趦煞N攻擊情況下，普通匿名區(qū)域生成算法的切換成功率均維持在[0.00%，0.05%]之間的低水平。這主要?dú)w因于普通匿名區(qū)域生成算法切換前后中心點(diǎn)保持不變，容易遭受中心點(diǎn)和等比縮放攻擊而導(dǎo)致用戶真實(shí)位置泄露 [9-10]。

由表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é)語(yǔ)

隨著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á)到更好效果。

參考文獻(xiàn)：

[1]HUO Z， MENG X F. A trace data publishing method for differential privacy[J]. Journal of Computer Science， 2018，" 41（2）： 401-411.

[2] SWEENEY L. K-anonymity： a model for protecting privacy[J]. International Journal on Uncertainty， Fuzziness and Knowledge-based Systems， 2002， 10（5）： 557-570.

[3] MACHANAVAJJHALA A， KIFER D， GZHRKE J， et al. L-diversity： Privacy beyond k-anonymity[J]. ACM Transactions on Knowledge Discovery from Data， 2007， 1（1）： 63-66.

[4] LI X H， WANG E M， YANG W D， et al. DALP： a demand-aware location privacy protection scheme in continuous location-based services[J]. Concurrency amp; Computation Practice amp; Experience， 2016， 28（4）： 1219-1236.

[5] PALANISAMY B， LIU L. Attack-resilient mix-zones over road networks： architecture and algorithms[J]. IEEE Transactions on Mobile Computing， 2015， 14（3）： 495-508.

[6] YANG S， SHAO Y F， ZHANG K. An effective method for solving multiple travelling salesman problem based on NSGA-II[J]. Systems Science Control Engineering， 2019， 7（2）： 108-116.

[7] KOMISHANI E G， ABADI M， DELDAR F. PPTD： preserving personalized privacy in trajectory data publishing by sensitive attribute generalization and trajectory local suppression[J]. Knowledge Based Systems， 2016， 94（2）： 43-59.

[8] KOMISHANI E G， ABADI M. A generalization based approach for personalized privacy preservation in trajectory data publishing[C]//Proceedings of the 2012 IEEE Sixth International Symposium on Telecommunications， Piscatway， NJ： IEEE， 2012.

[9] ZHANG B， MOHAMMED N， DAVE V， et al. Feature selection for classification under anonymity constraint[J]. Transactions on Data Privacy， 2017， 10（1）： 1-25.

[10]LI J， CHENG K， WANG S， et al. Feature selection： a data perspective[J]. ACM Computing Surveys（CSUR）， 2017， 50（6）： 1-45.

[11]WANG S L， HU Q， SUN Y C， et al. Privacy preservation In location-based services[J]. IEEE Communications Magazine， 2018， 56（3）： 134-140.

[12]DARGAHI T， AMBROSIN M， CONTI M， et al. ABAKA： a novel attribute-based k-anonymous collaborative solution for LBSs[J]. Computer Communications， 2016， 85（1）： 1-13.

[13]LIU B， HENGARTNER U. Privacy-preserving social recommendations in geosocial networks[C]//PST 2013： Proceedings of the 11th International Conference on Privacy， Security and Trust.Washington，DC： IEEE Computer Society， 2013.

[14]FAWAD H S， MUHAMMAD H. A k-means based co-clustering（kCC）algorithm for sparse， high dimensional data [J]. Expert Systems with Applications， 2019， 118（3）： 20-34.

[15]MADAN S， GOSWAMI P. K-DDD measure and MapReduce based anonymity model for secured privacy preserving big data publishing[J]. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2019， 27（2）： 177-199.

（責(zé)任編輯：于慧梅）

Improved Algorithm Based on Common Anonymous

Region Generation

WANG Zhiming*

（College of Electromechanical and Information Engineering， Putian University， Putian 351100 ， China）

Abstract：

In order to reduce the risk of personal location information disclosure in LBS application， an iterative search linear offset region switching algorithm and a distributed anonymous region overflow switching algorithm are proposed based on the ordinary anonymous region generation algorithm. The iterative search linear offset region switching algorithm linearly offsets the region center to improve the success rate of anonymous region switching. The distributed anonymous region overflow switching algorithm determines the location of the generated region according to the distribution of regional users， and implements distributed and overflow processing for the anonymous region， which significantly enhances the anti-attack effect and service quality. Experiments show that in the case of center point and proportional scaling attacks， the region switching success rate of the two improved algorithms can reach 100%， which is significantly better than the ordinary anonymous region generation algorithm.

Key words：

location-based services; privacy protection; anonymous area; area switching