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

王智明

摘 要：為降低個人位置信息在LBS應用過程中的泄露風險，基于普通匿名區(qū)域生成算法提出了迭代搜索線性偏移區(qū)域切換算法與分布式匿名區(qū)域外溢切換算法。迭代搜索線性偏移區(qū)域切換算法對區(qū)域中心點進行線性偏移來提高匿名區(qū)域切換成功率;分布式匿名區(qū)域外溢切換算法根據(jù)區(qū)域用戶分布情況來決定生成區(qū)域的方位，對匿名區(qū)域?qū)嵭蟹植际胶屯庖缣幚?，抵御攻擊效果和服務質(zhì)量明顯增強。試驗表明，在中心點和等比縮放攻擊情況下，兩種改進算法的區(qū)域切換成功率最高能達100%，顯著優(yōu)于普通匿名區(qū)域生成算法。

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

中圖分類號：TP311

文獻標志碼：A

基于位置的服務（location based services，LBS）集成了測繪、衛(wèi)星導航、GIS等技術(shù)，為我們提供諸如地圖導航、網(wǎng)約車、廣告推送等各式各樣便利的服務。然而作為硬幣的另一面，這些海量數(shù)據(jù)中不可避免會包含一些企業(yè)或個人的隱私數(shù)據(jù)[1]。早在2002年，SWEENEY提出k-匿名（k-anonymity）模型[2]，2006年，MACHANAVAJJHALA[3]對該模型進行改進，提出了L-diversity，規(guī)定每個信息屬性等價類不能少于L個敏感屬性值。2016年，LI等[4]通過刪除最遠足跡的方式提高了LBS服務質(zhì)量。PALANISAMY等[5]要求用戶離開Mixzone區(qū)時使用假名，以通過區(qū)域關(guān)聯(lián)性的攻擊。

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

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

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

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

普通匿名區(qū)域生成算法在切換匿名區(qū)域時，保持區(qū)域中心點不變或簡單進行線性偏移，容易為惡意者所攻擊，不能有效抵御中心點攻擊和線性偏移攻擊，本節(jié)對普通匿名區(qū)域生成算法進行改進，提出迭代搜索線性偏移區(qū)域切換算法（算法1），具體步驟如下：

（1）將原匿名矩形區(qū)域中心點O作為坐標原點，將矩形區(qū)域分為I、II、III、IV面積相等的4個子矩形區(qū)域，從左上子矩形順時針方向依次記為R1、R2、R3、R4，計算各子矩形的用戶數(shù)Ni=c（Ri），選取Ni值最大的區(qū)域Ri作為迭代矩形，進一步劃分為四個子矩形，直到MAXNi≤3，劃分結(jié)束。

（2）從Ri區(qū)域隨機選一用戶U，連接O、U兩點的直線y=ax+b作為偏移函數(shù)。如圖1（a）所示，迭代搜索的矩形編號依此為2、7、10，則從10號矩形中隨機選用戶。

（3）依據(jù)切換前后的隱私度k的比值，中心點不變等比例縮放原匿名區(qū)域，生成初步匿名區(qū)域CK1。區(qū)域4個頂點依次記為（xLeft，yTop）、（xLeft，yBot）、（xRight，yTop）、（xRight，yBot）。

（4）根據(jù)用戶確定的橫坐標位移量△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）作為四個頂點分別映射到x、y坐標軸，生成線性偏移切換后的區(qū)域CK2，如圖1（b）所示。

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

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

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

（9）若SCK2>Smax，則保持區(qū)域中心點不變等比縮小匿名區(qū)域CK2至Smax，即SCK2=Smax，返回步驟（6）重新計算用戶數(shù)量。

（10） 返回線性偏移后的匿名區(qū)域CK2，算法結(jié)束。

迭代搜索線性偏移區(qū)域切換算法針對普通匿名區(qū)域生成算法的中心點不變進行優(yōu)化，對等比縮放后的匿名區(qū)域進行線性偏移，偏移方向依據(jù)用戶密度具有隨機性，其區(qū)域偏移的規(guī)律難被攻擊者捕獲，能很好應對中心點和線性偏移的攻擊，系統(tǒng)綜合開銷也比較小，但該算法不足是存在被等比縮放攻擊的風險。

1.2 分布式匿名區(qū)域外溢切換算法（算法2）

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

（1）對原匿名矩形區(qū)域CK的4個頂點做兩對角線，從上矩形邊順時針方向?qū)^(qū)域分為I、II、III、IV四個三角形子區(qū)域，依次記為T1、T2、T3、T4，四條矩形邊依次相應記作L1、L2、L3、L4。計算T1、T2、T3、T4各區(qū)域內(nèi)的用戶數(shù)Ni=c（Ti），選取用戶密度值ρ=Ni/STi（STi表示Ti區(qū)域面積）最大的兩個區(qū)域，生成這兩區(qū)域?qū)猧值的集合{m，n}。分別令i=m、n，重復執(zhí)行（2）至（12）步驟兩次，最終得到兩個分散的匿名區(qū)CKm、CKn。如圖2（a）所示。

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

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

（4）初始化空用戶集U={} ，生成半圓區(qū)域CKr的用戶集U。

（5）將U內(nèi)所有用戶點映射到x、y坐標軸，得到區(qū)域邊界用戶點相應的x、y軸極值xmin、xmax，ymin、ymax。

（6）以（xmin，ymin）、（xmin，ymax）、（xmax，ymax）、（xmax，ymin）為4個頂點，生成切換后的匿名區(qū)域CKi，計算集合用戶數(shù)N=c（U）和CKi區(qū)域的面積SCKi。

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

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

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

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

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

（12）匿名區(qū)域切換完成，返回匿名區(qū)域CKi，算法結(jié)束。

分布式匿名區(qū)域外溢切換算法利用了用戶的分布密度，同時對原匿名區(qū)域做了外溢處理，攻擊者很難獲取用戶真實地址，區(qū)域切換的成功概率高。切換后的匿名區(qū)域是由兩塊區(qū)域（CK1、CK3）組成如圖2（a），這樣能有效提高用戶的服務滿意度[6]，因為在單匿名區(qū)域情況下，如果用戶需要的服務點剛好落在新匿名區(qū)域中或者靠近原匿名區(qū)附近，用戶可以達到較高的滿意度;但是如果用戶需要的服務點落在新匿名區(qū)遠離原匿名區(qū)那一側(cè)，而用戶真實位置剛好又位于原匿名區(qū)中遠離新匿名區(qū)的那一側(cè)，則服務質(zhì)量差，用戶滿意度低。

綜上，分布式匿名區(qū)域外溢切換算法能很好應對中心點、線性偏移、等比縮放三類攻擊，安全性和用戶服務滿意度顯著提升，但算法開銷相對較大。

1.3 算法1和算法2的綜合應用

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

PROCEDURE：

Ni=c（USERi）;

IF Ni≤5

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

IF Ni>5 AND RISK（等比縮放攻擊）=0

THEN DO本文算法1;

ELSE

DO 本文算法2;

END PROCEDURE

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

試驗環(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ū)域切換算法的耗時比較

匿名區(qū)域切換的耗時會直接影響到用戶的體驗，是衡量算法的重要指標之一。3種匿名區(qū)域切換算法的耗時試驗結(jié)果見表1?？梢钥闯觯浩胀涿麉^(qū)域生成算法耗時明顯小于另外兩算法，這是由于普通匿名區(qū)域生成算法僅依據(jù)切換前后隱私度k值等比例擴大原匿名區(qū)域，算法簡單，生成新匿名區(qū)域的速度比較快。當切換前隱私度k=1時，切換后隱私度k值越大其所對應的耗時隨之呈增加的趨勢，但并不是呈成正比例增加。耗時與切換前后△k值變化有關(guān)，當△k較小時切換耗時較少，△k值較大時迭代搜索線性偏移區(qū)域切換算法和分布式匿名區(qū)域外溢切換算法的耗時增加較多，但其總耗時能夠控制在用戶可接受的范圍之內(nèi)[7]。在時間消耗方面，普通匿名區(qū)域生成算法耗時最少優(yōu)勢明顯，然后依次是迭代搜索線性偏移區(qū)域切換算法、分布式匿名區(qū)域外溢切換算法[8]。

由以上結(jié)果可知，在注重時間效率而對安全性不敏感的場景下可以優(yōu)先采用普通匿名區(qū)域生成算法進行匿名區(qū)域的切換。

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

匿名區(qū)域切換成功率是生成新匿名區(qū)域的成功概率，它間接影響了用戶位置的泄露概率，是區(qū)域切換算法安全性的重要指標之一。在中心點與等比縮放兩種不同攻擊情況下，3種算法區(qū)域切換的成功率分別見表2和表3?？梢钥闯?，在兩種攻擊情況下，普通匿名區(qū)域生成算法的切換成功率均維持在[0.00%，0.05%]之間的低水平。這主要歸因于普通匿名區(qū)域生成算法切換前后中心點保持不變，容易遭受中心點和等比縮放攻擊而導致用戶真實位置泄露 [9-10]。

由表2得知，迭代搜索線性偏移區(qū)域切換算法在中心點攻擊時，能夠保持很高的切換成功率，大多數(shù)情況非常接近100%，這是由于該算法針對中心點攻擊的特點，對匿名區(qū)域的中心點進行了線性偏移[11]。而表3數(shù)據(jù)顯示，在面對等比縮放攻擊時，該算法的表現(xiàn)就不盡人意，最高的成功率只有34.96%，有的情況只是個位數(shù)，究其因主要是切換前后的隱私區(qū)域存在一定的重疊面積，若用戶真實位置剛好處于其中，則會導致位置泄露[12-13]。

由表2、表3看出，分布式匿名區(qū)域外溢切換算法在面對中心點攻擊和等比縮放攻擊時，都有良好表現(xiàn)，切換成功率達到了100%。這是由于該算法在區(qū)域生成時，按用戶密度來決定切換后區(qū)域的方位，同時對原匿名區(qū)域做了外溢處理來減少用戶真實位置泄露的風險，所以有效抵御了各類攻擊[14-15]。

3 結(jié)語

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

參考文獻：

[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 & Computation Practice & 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.

（責任編輯：于慧梅）

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

2633500520382