寧雪莉，羅永龍，邢 凱，鄭孝遙

(1.安徽師范大學 數(shù)學計算機科學學院，安徽 蕪湖 241002； 2.網(wǎng)絡與信息安全安徽省重點實驗室(安徽師范大學)，安徽 蕪湖 241002)

0 引言

地理社交網(wǎng)絡(GeoSocial Network, GSN)本質(zhì)上是具有地理位置坐標特性的社交網(wǎng)絡，從社交網(wǎng)絡如Facebook、Twitter到基于位置的社交網(wǎng)絡如Foursquare，用戶通過帶有定位功能的移動設備簽到并彼此分享位置，同時利用這些地理位置信息，可以獲取更多個性化定制服務，如導航、興趣點推薦、智能交通等，因此分析并發(fā)布用戶位置數(shù)據(jù)信息很有應用意義。然而用戶頻繁簽到的位置可能包含用戶極其敏感的個人信息，簡單發(fā)布這些數(shù)據(jù)會導致用戶個人身份和其他敏感信息泄露，因此，用戶頻繁位置的隱私保護是目前一個重要的研究熱點。

社交網(wǎng)絡中用戶身份信息泄露已經(jīng)得到廣泛研究[1-5]，然而由于地理社交網(wǎng)絡中涉及用戶的位置信息，若將上述隱私保護方法直接應用到地理社交網(wǎng)絡中仍然存在一些弊端。如攻擊者了解目標用戶在某一個時刻頻繁訪問某個或某幾個位置，而在這個時刻只有一個用戶在該位置簽到，那么攻擊者就可以根據(jù)了解的背景知識將用戶和頻繁位置唯一匹配，推測出用戶身份信息，導致用戶身份以及其他和位置有關的敏感信息泄露。

為解決上述問題，本文提出了一個(k,c)-anonymity算法。首先根據(jù)用戶訪問位置的頻次設置頻繁位置集合；然后將這些頻繁位置的子集組合成超邊，把不滿足匿名參數(shù)k的超邊進行重組，通過該算法泛化用戶頻繁訪問位置；最后發(fā)布地理社交網(wǎng)絡數(shù)據(jù)信息，并且通過Brightkite和Gowalla數(shù)據(jù)集進行實驗驗證，結(jié)果表明在保證安全性的同時降低了用戶的信息損失率。

1 相關工作

多數(shù)位置隱私保護技術都是基于k匿名實現(xiàn)的[6-9]。文獻[6]提出時空匿名保護技術：New Caper算法，通過空間索引技術組織各個移動對象來提高位置泛化和查詢功能。文獻[7]使用網(wǎng)格進行k匿名，并在此基礎上增加位置多樣性，進而提高隱私保護的程度。文獻[8]根據(jù)位置服務查詢結(jié)果的相似性來構造匿名區(qū)域?qū)崿F(xiàn)位置隱私保護。文獻[9]針對現(xiàn)有位置隱私保護機制忽略隱式收集時空數(shù)據(jù)而導致隱私泄漏的問題，提出基于時空數(shù)據(jù)發(fā)布中隱式隱私保護方法。上述研究主要是解決基于位置服務的匿名查詢問題，僅僅針對用戶單點位置進行隱私保護且與地理社交網(wǎng)絡中數(shù)據(jù)匿名方式不同。文獻[10-11]提出基于區(qū)域的偽裝(Region-based Cloaking, CR)算法，該算法的核心是使CR盡可能小以提高服務質(zhì)量，對于每個查詢可信匿名服務器生成一個至少包含k個真實用戶位置的CR。在文獻[12]中指出連續(xù)查詢服務需要生成較大的CR，導致服務質(zhì)量降低，同時基于CR方法的問題也在于潛在k匿名范式易受到背景知識攻擊，尤其在地理社交網(wǎng)絡中對于時刻簽到的用戶，攻擊者可以用某些特殊位置重構用戶身份，進而導致用戶身份泄露。

文獻[13]介紹一種基于地理社交網(wǎng)絡的頻繁位置Lk-anonymity模型，該模型認為攻擊者了解目標用戶所有的頻繁位置，但這種假設與實際情況不符。文獻[14]提出并定義一種以表格方式處理數(shù)據(jù)的(k,l)-anonymity模型，該模型數(shù)據(jù)的處理格式與地理社交網(wǎng)絡數(shù)據(jù)格式不同，且沒有把頻繁位置作為用戶敏感信息的一部分來處理，因此這種方式不能直接應用于地理社交網(wǎng)絡。文獻[15]提出(k,m)-anonymity頻繁位置模型，利用地理社交網(wǎng)絡特性，引入社交網(wǎng)絡超邊重新組合思想構造匿名，這種方式有效地減弱了背景知識攻擊以及用戶身份泄露風險，但其隨機的超邊重組機制導致用戶偏離度以及位置偏離度較大，使得數(shù)據(jù)有效性較低。

為此，本文根據(jù)地理社交網(wǎng)絡特性設計一種頻繁位置匿名模型，并提出一個新的隱私保護算法(k,c)-anonymity算法，首先針對地理社交網(wǎng)絡中用戶頻繁位置隱私泄露問題，構建一個基于用戶頻繁位置的隱私保護模型，利用(k,c)-anonymity算法泛化用戶頻繁訪問位置，采用超邊相交機制和最近距離決定超邊重組策略對用戶頻繁訪問位置進行匿名，從而實現(xiàn)對用戶簽到信息進行局部抑制操作。通過實驗證明，該算法降低了用戶和位置的偏離度，減少了信息損失，提高了地理社交網(wǎng)絡發(fā)布數(shù)據(jù)的有效性。

2 相關定義

定義1 位置差異性。位置li與位置lj之間的距離遠近程度稱為位置差異性，其中l(wèi)i坐標為(lati,loni)，lj坐標為(latj,lonj)，由歐氏距離公式表示如下：

(1)

定義2 頻繁位置。 用戶在一定時間內(nèi)多次訪問同一個位置，并根據(jù)用戶訪問位置的頻次，對訪問超過一定次數(shù)的位置稱為頻繁位置。對于用戶頻繁訪問的位置本文設定為敏感信息，需要保護的對象。

定義3 頻繁位置矩陣。V={v1,v2,…,vm}表示所有用戶的集合，L={l1,l2,…,ln}表示用戶所訪問的位置集合，那么用戶的頻繁位置矩陣表示為VLm×n，如表1中用戶-位置矩陣表示。

定義4 頻繁位置選擇。對于一個位置li屬于用戶vi的m個頻繁訪問的位置Lm={l1,l2,…,lm}，當且僅當：

(2)

如果用戶vi在一定時間內(nèi)訪問位置li的次數(shù)超過系統(tǒng)設定的value值則認為li是用戶vi的頻繁位置。頻繁位置的選擇也是數(shù)據(jù)集處理的一種方式，采用何種方式處理數(shù)據(jù)集并不會影響匿名效果。通過式(2)，可將表1中的VL矩陣處理成表2中的頻繁位置矩陣。

表1 用戶訪問位置次數(shù)Tab. 1 User check-in location frequency

表2 頻繁位置轉(zhuǎn)換Tab. 2 Frequent location conversion

定義5 將地理社交網(wǎng)絡定義為GSN(V,L,HE,fv,c),其中：V表示用戶節(jié)點集合，L表示位置集合，HE表示所有超邊集合，fv表示由V→L的映射關系，c表示攻擊者了解目標用戶的頻繁位置即背景知識。

定義6 身份重構。在一個GSN中，對于一個用戶v的超邊eh在整個地理社交網(wǎng)絡中是唯一的，那么用戶v的身份可以被攻擊者唯一識別，稱為身份重構。

由表2頻繁位置矩陣得到地理社交網(wǎng)絡圖1(a)，假設c=2即攻擊者知道目標用戶的兩個頻繁位置l1和l5，由于訪問這兩個頻繁位置的用戶只有v3，那么v3的身份被重構，即被攻擊者識別。同理，用戶v4和v5也可以用同樣的方式重構。

定義7 超邊。用戶頻繁位置的子集組成的邊稱為超邊。

定義8 超邊相交。一個超邊eh1和另一超邊eh2之間有相同的頻繁訪問位置點，稱為超邊相交，記為eh1∩eh2。

定義9 超邊重組。為抵御身份重構的攻擊，需要將超邊個數(shù)達到匿名參數(shù)k值，超邊之間的重新組合，稱為超邊重組。

定義10 (k,c)-anonymity。對于一個GSN(V,L,HE,fv,c)，使得每個用戶的超邊eh個數(shù)都不少于匿名參數(shù)k值，稱為(k,c)-anonymity。

鑒于圖1(a)中出現(xiàn)的身份重構現(xiàn)象，如構造(2,2)-anonymity方式抵御背景知識攻擊，v3的超邊{l1,l5}和v4的超邊{l1,l4}相交于位置l1，將v4的頻繁位置l4轉(zhuǎn)變l5，通過超邊重組v4的超邊為{l1,l5}，同理v5的超邊為{l3,l5}，由此處理可得表3匿名之后的頻繁位置矩陣以及圖1(b)。

表3 匿名的頻繁位置Tab. 3 Anonymous frequent location

圖1 地理社交網(wǎng)絡 Fig. 1 Geosocial network

3 隱私保護算法

3.1 (k,c)-anonymity算法描述

在處理地理社交網(wǎng)絡存在的身份重構時，(k,m)-anonymity算法[15]的步驟主要是：首先將超邊思想引入地理社交網(wǎng)絡中，尋找不滿足匿名參數(shù)k的超邊；其次是隨機選擇兩個或者多個不滿足條件的超邊進行隨機組合；最后計算隨機組合超邊個數(shù)，使其達到k匿名目的。由于該算法并沒有考慮超邊相交和重組機制，并且每次搜尋超邊都需要掃描超邊集合中所有的邊，這樣使得用戶位置信息偏離原始數(shù)據(jù)的程度增大，而且若對用戶所有超邊每次進行掃描，導致數(shù)據(jù)的有效性降低，花費的時間代價較大。

因此，本文提出一種改進的(k,c)-anonymity算法(具體見算法1)：首先輸入部分地理社交網(wǎng)絡數(shù)據(jù)以及給定匿名參數(shù)k，將所有用戶存儲到V集合中，所有訪問位置存儲到L集合中，所有超邊存儲到HE集合中，這樣減少了每次遍歷集合中元素的時間，然后再根據(jù)定義7統(tǒng)計不滿足匿名參數(shù)k的超邊個數(shù)(見算法1第4～7行)，并將不滿足超邊個數(shù)k存儲到一個集合M中，從M中隨機選擇一個超邊作處理，由于HE元素個數(shù)大于M，從而在每次遍歷用戶超邊時不需要訪問HE集合降低了時間代價；其次根據(jù)定義8和9優(yōu)先考慮有共同交點的超邊，若|eh∩eh2|>1說明超邊之間有交點，那么將超邊進行重組直到滿足參數(shù)k(見算法1第8～15行)，若|eh∩eh2|=0即它們之間沒有公共點，將按照dmin=d(eh,eh2)計算超邊之間的位置差異，d的值越小那么位置偏離越小，數(shù)據(jù)的有效性越高(見算法1第17行)。這樣可以保證重組的代價最小以及位置信息損失率最低，最后將兩個超邊重新組合(見算法1第20～21行)，最終數(shù)據(jù)有效性得到提高。具體描述如下。

算法1 (k,c)-anonymity。

輸入:GSN(V,L,HE,fv,c)以及匿名參數(shù)k值；

輸出:GSN′(V,L′,HE′,fv′,c)。

1)

V←{v1,v2,…,vn};

2)

L←{l1,l2,…,ln};

3)

HE({eh1,eh2,…,ehn};

4)

if(|V|>k&& |L|>c)

5)

count← number of hyperedges set that less than parameterk

6)

ifcount=0

7)

break

8)

M← all of hyperedges which rank less thankput into a set

9)

eh← select a hyperedge fromMrandomly

10)

eh1=null

11)

foreh2inM

12)

ifeh=eh2

//表示超邊自身重組

13)

continue

14)

if(0< |eh∩eh2|≤c-1)

15)

mergeehandeh2

16)

else

17)

dmin=d(eh,eh2)

18)

end if

19)

end for

20)

eh1←eh2

21)

mergeehandeh1

22)

return GSN′(V,L′,HE′,fv′,c)

23)

end if

3.2 復雜度分析

算法1的運行時間主要用于處理超邊選擇和超邊重組，超邊重組過程實際是兩個位置集合的泛化過程。該算法每次迭代的過程需要從M集合中隨機選擇一個超邊與該集合中另外一條超邊重新組合，超邊重組過程的時間復雜度為O(n*n)，直到滿足匿名參數(shù)k值時停止迭代操作，因此，算法1整體的時間復雜度為O(k*n2)。

3.3 衡量標準

信息損失率是衡量數(shù)據(jù)發(fā)布有效性的重要指標?；谀壳暗乩砩缃痪W(wǎng)絡對用戶空間數(shù)據(jù)挖掘處理時，導致用戶以及位置信息損失較大問題，本文將從用戶偏離度和位置偏離度[15]這兩個方面衡量(k,c)-anonymity算法的數(shù)據(jù)有效性。

1)用戶偏離度：

(3)

其中：rank(eh)表示匿名之前地理社交網(wǎng)絡中超邊eh的個數(shù)，同理rank′(eh)表示匿名之后eh的個數(shù)。Zub值越小，表明用戶偏離度越小，和原始數(shù)據(jù)集的相似度越大，得到的數(shù)據(jù)有效性越高。

2)位置偏離度：

(4)

其中：f(v)表示匿名之前的地理社交網(wǎng)絡中用戶頻繁位置集合，同理f′(v)表示匿名之后的頻繁位置集合。若Zlb值越小表明用戶頻繁訪問的位置偏離度越小，用戶滿意度越高，并且用戶要求服務時，獲取的服務質(zhì)量就越高。

4 實驗

4.1 實驗數(shù)據(jù)集

實驗算法環(huán)境為Intel Core2 Quad CPU Q9500 2.83 GHz,4 GB內(nèi)存，操作系統(tǒng)為Microsoft Windows 7，算法使用Java語言實現(xiàn)。實驗采用兩個地理社交網(wǎng)絡數(shù)據(jù)集Brightkite和Gowalla，由于數(shù)據(jù)具有無法避免的稀疏特性，對該原始數(shù)據(jù)進行處理，選擇頻繁位置個數(shù)大于c的用戶，按照定義(2)中頻繁位置選擇機制處理這兩個數(shù)據(jù)集，選擇合理的頻繁位置，使得該數(shù)據(jù)集分別包含556個用戶和1 087個用戶，及分別包括1 451和1 403個頻繁位置。

4.2 實驗結(jié)果與分析

基于3.3節(jié)的用戶偏離度和位置偏離度衡量標準，本文對(k,c)-anonymity算法與(k,m)-anonymity算法進行比較，圖2～3表明兩個算法在不同的簽到數(shù)據(jù)集分別在兩個衡量標準的對比結(jié)果。

圖2 不同數(shù)據(jù)集的用戶偏離度 Fig. 2 Bias of user on different dataset

圖3 不同數(shù)據(jù)集的位置偏離度 Fig. 3 Bias of location on different dataset

圖2分別表示在Brightkite和Gowalla數(shù)據(jù)集中用戶偏離度的表現(xiàn)，在背景知識不同、k值不同情況下用戶偏離度的對比情況。從圖2第1列中可以看出，當背景知識為1時，近似演變?yōu)槲恢胟匿名的情況，僅對單一位置進行隱私保護，得到用戶偏離度較(k,m)-anonymity算法相比仍然很低；同時從圖2第3列中也可以看出在同一個背景知識c=3的情況下，隨著k值的不斷增大，整體趨勢表明用戶偏離度不斷增大，但和文獻[15]中的m=3背景知識相比，本文用戶偏離度明顯降低，尤其當k=5時用戶偏離度下降最為顯著。這是由于本文考慮超邊重組時超邊之間的相交現(xiàn)象，優(yōu)先重組超邊之間有交點的情況，這樣可以縮減用戶偏離度。同樣，當k值相同的情況下，由圖2可以看出隨著背景知識不斷的增大(c=1,c=2,c=3)，用戶偏離度也不斷增大，這是由于為了抵御背景知識攻擊，需要將不滿足匿名參數(shù)k的其他用戶放入一個匿名組中，因此，導致用戶偏離度增大，損失率會增大的表現(xiàn)。

從圖3的1～3列中可以分別看出，在同一個背景知識條件下，隨著k值不斷增大，用戶位置偏離度也呈現(xiàn)出增大的趨勢，這是由于隨著k值不斷增大，用戶必須將不滿足匿名參數(shù)的超邊進行重組，導致用戶位置偏離度增大。同樣，也可以看出在同一個k值條件下，隨著背景知識的增大(c=1,c=2,c=3)，位置偏離度也在增大，這是由于攻擊者掌握目標用戶的背景知識越多，那么為了抵御這種攻擊得到k匿名的結(jié)果，導致一些頻繁位置重新組合，因此，導致了位置偏離度增大。 (k,c)-anonymity算法從兩個方面考慮超邊之間的重組標準：一是超邊之間的有無共同交點即決定了位置差異性的大小；另一個則是超邊重組之后位置偏離度標準，總是尋找最近位置即決定發(fā)布之后數(shù)據(jù)的可用性標準。相比(k,m)-anonymity算法，進行匿名時忽略了這兩個因素，僅僅把花費最小代價考慮在其范圍內(nèi)，導致位置偏離度較大的現(xiàn)象。

綜上，實驗結(jié)果表明，本文提出的一種基于頻繁位置的隱私保護算法——(k,c)-anonymity，在用戶偏離度以及位置偏離度兩個衡量標準上，與(k,m)-anonymity算法比較均有較好的表現(xiàn)。

5 結(jié)語

本文針對地理社交網(wǎng)絡中以用戶頻繁訪問位置為背景知識進行攻擊而導致用戶身份泄露問題，提出一種基于地理社交網(wǎng)絡的頻繁位置隱私保護算法——(k,c)-anonymity，該算法避免了用戶和位置偏離度較大的超邊重組，從而提高了數(shù)據(jù)的有效性。實驗結(jié)果表明，通過改變c值和k值，(k,c)-anonymity算法在用戶偏離度以及位置偏離度衡量標準上均優(yōu)于(k,m)-anonymity算法。未來擬開展隱私保護的數(shù)據(jù)挖掘研究，并與地理社交網(wǎng)絡中的個性化推薦方法相結(jié)合，在提高服務質(zhì)量的同時也可以保護用戶隱私。

參考文獻(References)

[1] BHATTACHARYA M, MANI P. Preserving privacy in social network graph withK-anonymize degree sequence generation [C]// Proceedings of the 2015 9th International Conference on Software, Knowledge, Information Management and Applications. Piscataway, NJ: IEEE, 2016: 1-7.

[2] DAS S, EGECIOGLU O, ELABBADI A. Anónimos: an LP-based approach for anonymizing weighted social network graphs [J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(4): 590-604.

[3] PARRIS I, HENDERSON T. Privacy-enhanced social-network routing [J]. Computer Communications, 2012, 35(1): 62-74.

[4] MITTAL P, PAPAMANTHOU C, SONG D. Preserving link privacy in social network based systems [EB/OL]. [2017- 03- 01]. http://www.princeton.edu/～pmittal/publications/link-privacy-ndss13.pdf.

[5] SWEENEY L.k-anonymity: a model for protecting privacy [J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570.

[6] MOKBEL M F, CHOW C Y, AREF W G. The new Casper: query processing for location services without compromising privacy [C]// VLDB ’06: Proceedings of the 32nd International Conference on Very Large Data Bases. Seoul, Korea: VLDB Endowment, 2006: 763-774.

[7] BAMBA B, LIU L, PESTI P, et al. Supporting anonymous location queries in mobile environments with privacygrid [C]// WWW ’08: Proceedings of the 17th International Conference on World Wide Web. New York: ACM, 2008: 237-246.

[8] 葉阿勇,李亞成,馬建峰,等.基于服務相似性的k-匿名位置隱私保護方法[J].通信學報,2014,35(11):162-169.(YE A Y, LI Y C,MA J F, et al. Location privacy-preserving method ofk-anonymous based-on service similarity [J]. Journal on Communications, 2014, 35(11): 162-169.)

[9] 王璐,孟小峰,郭勝娜.時空數(shù)據(jù)發(fā)布中的隱式隱私保護[J].軟件學報,2016,27(8):1922-1933.(WANG L, MENG X F, GUO S N. Preservation of implicit privacy in spatio-temporal data publication [J]. Journal of Software, 2016, 27(8): 1922-1933.)

[10] GEDIK B, LIU L. Location privacy in mobile systems: a personalized anonymization model [C]// ICDCS ’05: Proceedings of the 25th International Conference on Distributed Computing Systems. Washington, DC: IEEE Computer Society, 2005: 620-629.

[11] KALNIS P, GHINITA G, 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.

[12] CHOW C Y, MOKBEL M F. Enabling private continuous queries for revealed user locations [C]// SSTD ’07: Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases. Berlin: Springer, 2007: 258-275.

[13] MASOUMZADEH A, JOSHI J. Top location anonymization for geosocial network datasets [J]. Transactions on Data Privacy, 2013, 6(1):107-126.

[14] STOKES K. On computational anonymity [C]// PSD ’12: Proceedings of the 2012 International Conference on Privacy in Statistical Databases. Berlin: Springer, 2012: 336-347.

[15] LI Y, LI Y, XU G. Protecting private geosocial networks against practical hybrid attacks with heterogeneous information [J]. Neurocomputing, 2016, 210: 81-90.

This work is partially supported by the National Natural Science Foundation of China (61672039, 61370050, 61772034), the Natural Science Foundation of Anhui Province (KJ2017A327), the Wuhu Science and Technology Project (2015cxy10).

NINGXueli, born in 1993, M. S. candidate. Her research interests include information security,privacy preserving.

LUOYonglong, born in 1972, Ph. D., professor. His research interests include spatial data processing, information security,privacy preseving.

XINGKai, born in 1985, M. S. candidate. His research interests include information security,privacy preserving.

ZHENGXiaoyao, born in 1981, Ph. D. candidate, associate professor. His research interests include information security, personalized recommendation.