面向時空特性的社會網絡個性化隱私保護算法

夏秀峰，尹伯陽，劉向宇，2，李佳佳，宗傳玉 ，朱 睿

1(沈陽航空航天大學 計算機學院，沈陽 110036)

2(新西蘭惠靈頓理工學院 信息與商科學院，新西蘭 下哈特 5010)

E-mail：boyang_yin@163.com

1 引 言

隨著社交網絡技術的發(fā)展，人們對社交網絡信息發(fā)布的需求正由“無差異”逐步發(fā)展為“個性化”，具有個性化的簽到數據導致了敏感關系隱私泄露問題.針對具有相同時間和地點的簽到數據，不同用戶對于完全公開、部分公開、還是不公開信息的需求存在巨大差異.由于用戶個體對不同簽到數據的敏感性并不一致，并且對于同一簽到數據，用戶在不同時期的敏感性不同，從而使用戶對于簽到數據的敏感性呈現動態(tài)化特征，會隨著時間的變化而發(fā)生變化.因此，在發(fā)布簽到數據時需要考慮用戶的個性化隱私需求.綜上所述，當前社交網絡隱私保護研究忽視了基于簽到數據的推演攻擊，同時簽到數據的時空特性增加了推演隱私攻擊的難度，這些特點使社交網絡隱私保護變得更加復雜、更具有挑戰(zhàn)性.

k-匿名模型[1，2]經常被用于數據發(fā)布中的信息保護.在用戶使用社交應用時，產生了個人隱私的泄露風險，無論用戶是否具有主動保護個人隱私的想法與需求，大多數用戶本身在隱私泄露面前都是難以察覺或者無法有效處理的.文獻[3]提出攻擊者會將其他方面的背景知識或者根據分析用戶的背景知識，作為隱私攻擊過程中的數據源.文獻[4]考慮到只能防止具有相同背景知識攻擊的單一模型，無法滿足用戶的個性化隱私要求.因此提出了一個基于用戶個人隱私請求的隱私保護服務框架.根據攻擊者逐漸增長的背景知識，定義了3個級別的保護需求.文獻[5]提出了一種具有個性化差異隱私的概率矩陣分解推薦方案(PDP-PMF).文獻[6]提出分別用一個特定區(qū)域和一組位置類型替換用戶的真實位置和查詢目標.文獻[7]根據時間重疊相似性、軌跡方向相似性和軌跡間距離的不確定性，計算兩條軌跡之間的相關性.文獻[8]提出了通過匹配用戶的共享位置與他們的真實移動軌跡，量化移動社交網絡的引發(fā)位置隱私泄漏.文獻[9]通過分析k-匿名模型的缺點，提出l-使用多樣性來加強隱私保護.文獻[10]提出了一種以用戶為中心的混淆方法，稱為KLAP，基于3個基本混淆需求：位置、多樣性和隱私區(qū)域保存.文獻[11]首先總結了k-匿名算法對標準標識符中敏感屬性的影響，然后從匿名數據的隱私性和安全性的角度分析了改進的l-多樣性算法.社交網絡隱私保護常見的技術還包括數據擾動[12]、查詢結果擾動[13]以及在統計學領域提出的其他解決方案.

針對社交網絡中的個性化簽到數據發(fā)布，從而導致用戶的身份隱私泄露的問題，本文提出了一種面向時空特性的社會網絡個性化隱私保護方法.本文研究工作主要分為如下幾個方面：首先，采用泛化技術來防止用戶的身份隱私泄露，避免發(fā)布的時空數據過于稀疏造成數據可用性的降低.通過背景知識的分級，分階段泛化原始時空數據，得到泛化結果；根據泛化結果，結合用戶自身的個性化隱私保護需求，對相應的敏感信息設定不同敏感程度值；采用泛化層次數規(guī)則評估每個敏感地點的敏感程度，實現攻擊者不會通過簽到數據發(fā)布中包含的背景知識匹配出用戶的身份信息，從而保護用戶的身份隱私，滿足用戶的個性化隱私保護需求.

2 時空數據敏感屬性分級及相關定義

2.1 時空簽到數據及相關定義

定義1.(時空簽到數據元組)：給定一個時空簽到數據元組ti，則時空簽到元組ti可以表示為，其中UID表示用戶的標識，t表示該條時空簽到數據的時間戳，(x，y)表示該條時空數據中地點的經緯度，其中x為該位置的經度，y為該位置的緯度，LID表示該條時空簽到數據所在地點的唯一標識，每一個語義標識都對應一個地圖上的地點，例如公園，醫(yī)院等.通過時空簽到數據所在地點的唯一標識，可以獲取該地點的位置名稱信息、地點類別、標記類型等.

定義2.(時空簽到數據屬性)：給定一個時空簽到數據元組ti，則時空簽到元組ti可以表示為，其中UID用戶的標識符，t，(x，y)為該條時空簽到數據的準標識符，LID為該條時空簽到數據所在敏感屬性地點名稱s或非敏感屬性地點.

2.2 時空數據敏感屬性分級及相關定義

定義3.(第1級別時空簽到數據敏感屬性)：若在某用戶已發(fā)布的時空數據表的簽到數據集合中僅存在一條準標識符為的元組，假設攻擊者通過已發(fā)布的時空簽到數據表外的其他途徑獲取某用戶簽到集合中的一條數據作為背景知識，則攻擊者可以確定唯一一個用戶Up匹配，此時用戶Up的標識符屬性泄露，即用戶Up的簽到數據集合泄露.

定義4.(第2級別面向時空特性的數據敏感屬性)：若已經發(fā)布的時空數據表的兩個不同用戶簽到數據集合中分別存在一條標識符為的元組和一條準標識符為的元組，假設攻擊者通過從已經發(fā)布時空簽到數據表外的其他途徑獲取一條數據作為背景知識，即使兩條簽到數據中存在相同的準標識符，則攻擊者可以根據簽到敏感地點的差異性，從而唯一確定一個用戶Up匹配，此時用戶Up的標識符屬性泄露且用戶Up的簽到數據集合泄露.

定義5.(第3級別面向時空特性的數據敏感屬性)：若已經發(fā)布的時空數據表的某用戶簽到數據集合中存在n(n=1，2，3…)個準標識符相同但敏感地點屬性不完全相同的元組，攻擊者通過從已經發(fā)布時空簽到數據表中獲得用戶UP在某一相同地點Ll的簽到次數為m，則攻擊者可以分析出該用戶訪問某一簽到地點Ln的頻率為m/n.若該用戶訪問地點Ln的頻率值過大，則用戶UP的敏感地點偏好泄露.

定義6.(泛化詞分類表)：泛化詞分類表中，所有敏感屬性s組成敏感屬性集合S，按照標記類型 (Type)、地點名稱(LID)和地點類別(Category)之間的語義從屬關系建立.每一個地點名稱LID都會對應地點類別和標記類型，如表1所示.

表1 泛化詞分類示例表Table 1 Generalized word classification

定義7.(第4級別面向時空特性的數據敏感屬性)：若已經發(fā)布的時空數據表的簽到數據集合中存在一條標識符為的元組，用戶可以選擇地點類別或標記類型替代敏感屬性Ln進行發(fā)布.

定義8.(數值型屬性元組間的距離)：令N為有限數值域，元組中任意兩個數值ti，tj∈N之間的標準距離定義為：

(1)

其中|D|表示域D的最大值與最小值的差值.

定義9.(泛化層次距離)：設H為原始數據表中某一分類型屬性可能泛化到的最高層次，其中D1為值域，D2到Dn為泛化域，j和j-1表示值域與泛化域之間的泛化權重.由Dp中的值泛化到Dq值的距離定義為泛化的加權層次距離：

(2)

定義10.(分類型屬性元組間距離)：設t1和t2為同一原始數據表中不同的兩個元組，t12為t1和t1這兩個元組的最近公共泛化元組，則t1和t2兩個元組間的距離可以定義為：

HDist(t1，t2)=HDist(t1，t12)+HDist(t2，t12)

(3)

3 時空數據個性化隱私保護算法

PSTPP算法集成了個性化匿名的兩種機制，能在對敏感屬性設置了相應的約束條件的同時，滿足個人對隱私保護的要求.即用戶可以在系統提供背景知識分級保護的同時，為自己的敏感值設定隱私保護的級別.

3.1 設計思想

算法通過為敏感屬性構造泛化層次樹的方式，允許特定的用戶為自己的敏感屬性值設置隱私保護級別.同時構造泛化詞分類表，依據語義信息把相同類別的敏感地點進行分類，通過層次泛化樹中搜索敏感地點結點的父親結點對該結點進行替換，這樣不但泛化了敏感地點的語義信息，使攻擊者無法準備匹配出用戶的隱私信息，同時保留了簽到數據的語義特征.

那么為敏感屬性s構建一個泛化層次樹GHT(Generalization Hierarchy Tree)，樹中的每一個結點包括根節(jié)點和父親節(jié)點，都有一個敏感地點屬性值SID與其一一對應，如圖1所示.敏感地點屬性的原始值作為樹的葉子節(jié)點，對應的樹層次級別為1.根據泛化查詢層次的偏移量，計算每條數據泛化的平均高度求出信息損失.

圖1 泛化層次樹Fig.1 Generalization hierarchy tree graph

在泛化層次樹中，越接近根節(jié)點，泛化的程度越高.用戶可以在系統提供基于背景知識分級保護的同時，為自己的敏感屬性設定隱私保護敏感值.依據泛化層次數，允許用戶個性化設定敏感屬性的敏感屬性值.

定義11.(個性化敏感屬性值PPL)：給定敏感屬性s和其對應的地點類別和標記類型，每一個敏感地點屬性值都對應SID中唯一的一個敏感屬性值PPL(Privacy Preservation Level).

表2是用戶指定的隱私保護級別表，其中PPL值為空的元組表示用戶沒有為自己的敏感屬性設置個性化敏感屬性值.

表2 個性化敏感屬性值示例表Table 2 Personalized sensitive attribute values

若PPL≤SID，則對敏感值的簽到數據不進行處理，對PPL>SID的數據，則使用泛化層次樹中與PPL的值對應SID所在的原始值的父節(jié)點代替當前的敏感地點屬性.

3.2 算法描述

算法1是對PSTPP的描述.在發(fā)布的簽到數據集滿足隱私保護級別參數約束的前提下，對用戶設置的個性化敏感屬性值進行判定，并對不能同時滿足約束的數據進行相應處理.運用泛化操作，查詢泛化樹中對應的結點，替換原有的敏感屬性信息，使得數據集滿足輸入的參數約束.最后依據個性化的隱私保護規(guī)則，生成可發(fā)布的安全數據集.

算法1.時空數據個性化隱私保護PSTPP算法

輸入：數據集D，匿名參數(k，l，α)，敏感屬性s，等價類C，元組t，敏感地點屬性值SID，GHT，部分用戶指定的個性化敏感屬性值PPL;

輸出：安全發(fā)布的滿足約束條件匿名簽到數據集D′;

1.D←φ;

2.For CreateCforD

3.According totiandtmax，partitionCintoC1，C2

4.SuchC1，C2are more local than T and eitherC1，C2has leastktuples

5.IfC1

6. Recursively partitionC1

7.Else partitionC2

8.For Merge thoseCinD;

9.IfG≠φthenD←Gand return up code then

10.GetD*

11.ElseDgenerateC

12.IftinD*thatPPL>SIDthen

13. Findnodetin GHT thenD′←nodet

14.ElseD*←nodet

15.ReturnD′;

4 實 驗

4.1 實驗環(huán)境設置

本文中的實驗數據來源于現實的Brightkite數據集(Brightkite datasets： Network datasets： Brightkite stanford.edu)，表3給出了實驗數據集的構成.收集了用戶從2008年4月份至2010年10月份的簽到數據，并且通過預處理選出美國加利福尼亞州的數據.Brightkite數據集包含9435名用戶和541169個簽到點.由于數據過多，因此提取Brightkite數據集中2008年4月1日至2009年5月1日的36594條數據，總共包涵622個用戶.將簽到數據集中的簽到位置進行了統一的編號，并通過爬蟲和地理信息API得到了每個位置的名稱和類別.

表3 實驗數據Table 3 Experimental data

4.2 實驗結果及分析

為了驗證PSTPP算法的性能，在相同的實驗條件下將其與k-匿名算法、l-多樣性算法進行比較，所有實驗的l的比值都固定為(l=4，α=0.8).從數據集中隨機抽取數據記錄，并為他們隨機設置隱私保護級別PPL.此外，為數據集中的每一個屬性都構造層次泛化樹.

基于所選擇的實驗數據，從算法的信息損失量、敏感值識別率以及運行時間來驗證PSTPP算法的可行性.

4.2.1 信息損失量分析

定義12.(信息損失量)：設等價類C中的元組個數為n，公共泛化元組為t，其中(A1，A2，…，Ac)是等價類C中的數值型標識屬性，那么元組t在屬性Ac上的信息損失為：

HILAi(C)=n×HDist(t)

(4)

設安全發(fā)布的數據表T中等價類個數為m，表T中所有元組在各個屬性上的信息損失為：

IL(T)=mNILAi(C)+mHILAi(C)

(5)

信息損失通過使用公式(5)進行計算，驗證數據36594條.k取值的分別從3、5、7到10依次遞增.對平均泛化高度產生的信息損失進行歸一化處理后得到的隱私保護算法的信息損失量如圖2所示.

圖2 信息損失量與k值Fig.2 Information loss with different k

由圖2可知，隨著k取值的增加，數據集信息損失量不斷增加，因為k的大小直接影響數據中的等價類的大小.即k值越大，同一個等價類匯總需要泛化的準標識符數據的值的越多，所以信息損失量越大.當k值增加至一定程度時，l-多樣性模型與k-匿名模型信息損失量差異不大，這是因為固定的l的取值在k值增加到一定程度時對數據集的約束不明顯.綜述所述，PSTPP算法的信息損失量相對其他兩種算法更大，這是由于其增加了對敏感值的個性化保護所導致的.

4.2.2 敏感識別率分析

定義13.(敏感屬性值的識別率)：給定數據集D和等價類C，s是等價類C中的某條數據t的敏感屬性值，則C中t的敏感屬性值s的識別率計算公式為：

(6)

其中，|(s，C)|為等價類C中的敏感屬性值s的個數，|C|為等價類的大小，|f(s)|等于敏感屬性泛化層次樹泛化后的父節(jié)點所在子樹的葉節(jié)點個數.若敏感值沒有進行泛化，保留匿名化后元組中原地點名稱，則|f(s)|=1.

數據集的敏感值識別率使用公式(6)進行計算，k取值分別為從3、5、7到10依次遞增.圖3給出了在圖2中相同數據下，當k值變化時，隱私模型的敏感值識別率.

圖3 敏感屬性識別率與k值Fig.3 Recognition rate of sensitive value with different k

如圖3所示，隨著k值的變化，模型的敏感值識別率不斷降低，最終趨近于平緩.其中PSTPP算法相較于其他兩個模型，敏感值識別率是最低的，隱私保護效果最好.

4.2.3 運行時間分析

圖4給出了根據k值變化的模型運行時間.

圖4 運行時間與k值Fig.4 Running time with different k

如圖4所示，當k值變化時，算法的運行時間會有一定的變化.當k=4時，l-多樣性模型與PSTPP算法會隨著隱私參數l和α的設置增加了劃分等價類時的判定時間，因此運行時間較長.而隨著k值的增大，算法的運行時間差別不大，所以PSTPP算法能更好的防止隱私泄露.

4 結束語

針對基于時空特性的社會網絡中敏感屬性的隱私保護問題展開研究，提出了一個時空數據發(fā)布的個性化隱私保護算法(PSTPP)，該算法為敏感屬性構造泛化層次樹，允許特定的用戶為自己的敏感屬性值設置隱私保護級別，滿足用戶的隱私保護需求.同時，按照時空簽到數據敏感屬性對時空數據進行分級保護，允許不同的用戶設置不同的敏感屬性值約束，提高了簽到數據的可用性.最后，基于實際數據集對算法的信息損失量、敏感值識別率以及運行時間進行測試.測試結果表明，提出的算法能夠針對不同層次的敏感屬性泄露應對不同的保護策略，以此來滿足用戶的個性化選擇，證明了該算法的有效性.