金凌竹，韓啟龍

(哈爾濱工程大學(xué) 計算機科學(xué)技術(shù)學(xué)院，哈爾濱 150001)

0 引 言

隨著網(wǎng)絡(luò)的快速發(fā)展，國內(nèi)外的社交網(wǎng)絡(luò)應(yīng)用層出不窮，如Facebook、微博等。這些應(yīng)用在促進人們社交生活的同時，也在收集社交網(wǎng)絡(luò)數(shù)據(jù)進行分析和挖掘。然而數(shù)據(jù)中含有大量的個人隱私信息，直接發(fā)布會造成用戶隱私泄露。為了防止社交網(wǎng)絡(luò)中個人信息、個體之間的隱私聯(lián)系等信息暴露。在保證整個網(wǎng)絡(luò)結(jié)構(gòu)有用性的前提下，如何以最小的信息丟失代價實現(xiàn)信息隱藏已成為當前社交網(wǎng)絡(luò)隱私保護研究領(lǐng)域一個重要課題。時空隱私信息可界定為用戶不愿意被外部知曉的時空信息，將這些時空信息稱為隱私興趣點。在社交網(wǎng)絡(luò)中，用戶自行設(shè)置時空信息的訪問權(quán)限，用戶的隱私需求具有個性化、動態(tài)化的特點[1-2]。如一些用戶將學(xué)校視為隱私興趣點，認為可能泄露他的學(xué)校信息；但另一些用戶卻愿意在學(xué)校共享自己的位置，以便于與校友互動交流。

由此，引入可信度來形式化地描述用戶的隱私需求，度量隱私泄露的風險程度，提出一種動態(tài)的時空隱私保護框架，將時空信息、社交關(guān)系、個人信息引入到知識構(gòu)建算法中以計算興趣點之間的相關(guān)性，并利用該相關(guān)性及時空信息實時判斷發(fā)布當前位置是否滿足用戶的隱私需求，實現(xiàn)隱私保護與服務(wù)質(zhì)量間的平衡。

1 動態(tài)社交網(wǎng)絡(luò)隱私保護

1.1 動態(tài)社交網(wǎng)絡(luò)中的隱私信息

在移動互聯(lián)網(wǎng)時代，動態(tài)社交網(wǎng)絡(luò)中的用戶可以使用移動設(shè)備快速、連續(xù)地收集數(shù)據(jù)，例如個人簽到數(shù)據(jù)、個人軌跡數(shù)據(jù)等。同時，網(wǎng)絡(luò)中的數(shù)據(jù)收集者需要得到所有用戶數(shù)據(jù)的匯聚結(jié)果，但是數(shù)據(jù)收集者并不是完全可信的，數(shù)據(jù)收集者會根據(jù)自身所掌握的信息，來推測其他用戶的隱私數(shù)據(jù)[3]。對這些數(shù)據(jù)進行隱私保護的匯聚，可以在保護用戶個人數(shù)據(jù)隱私的前提下，實現(xiàn)數(shù)據(jù)的有效利用[4]。動態(tài)社交網(wǎng)絡(luò)的隱私主要分為用戶隱私，位置隱私，軌跡隱私，社交關(guān)系隱私。

1.2 動態(tài)社交網(wǎng)絡(luò)圖

動態(tài)社交網(wǎng)絡(luò)根據(jù)時間劃分為一個個快照，以有向圖G=(V,E,R)來表示，V為點類型的集合，代表所有用戶數(shù)目的集合，V中的每個用戶均由其特有的標識vi表示。根據(jù)用戶對消息的隱私設(shè)置策略，將所有的節(jié)點歸納為3種類型：①Vpub，公共節(jié)點類型，代表對消息采用無隱私保護設(shè)置策略的這類用戶，社交網(wǎng)絡(luò)中所有用戶都能夠獲取到此類用戶發(fā)布在社交網(wǎng)絡(luò)中的消息。Vpub的所有消息都是沒有隱私保護的;②Vpri，私有節(jié)點類型，代表對消息采用部分隱私保護設(shè)置策略的這類用戶，社交網(wǎng)絡(luò)中的特定的用戶都能夠獲取到此類用戶發(fā)布在社交網(wǎng)絡(luò)中的消息。Vpri的所有消息都是半隱私保護的;③Vn，獨立節(jié)點類型，代表對消息采用嚴格的隱私保護設(shè)置策略的這類用戶，社交網(wǎng)絡(luò)中的其他用戶均無法獲取到此類用戶發(fā)布在社交網(wǎng)絡(luò)中的消息。Vn的所有消息都是嚴格隱私保護的。

R為社交網(wǎng)絡(luò)中用戶關(guān)系類型的集合。按照相互獲取消息能力的權(quán)限，R能夠歸納成5種類型：①Rnbr，雙向鄰居關(guān)系類型，代表此類型的用戶能夠相互的獲取對方的消息;②Ro-nbr，單向鄰居關(guān)系類型，代表此類型的用戶能夠單向的獲取信息。例如，用戶A關(guān)注了用戶B，但是用戶B沒有回關(guān)用戶A，那么用戶A可以收到A的動態(tài)而B不會在首頁刷到，但是如果用戶B從粉絲列表訪問，可以看到A的主頁信息。說明用戶形成了鄰居關(guān)系，但是獲取信息是單向的;③Rn-nbr，無鄰居關(guān)系類型，代表此類型的用戶無法獲取其他用戶的消息。用戶可能沒有關(guān)注任何人，也沒有粉絲關(guān)注，賬號可能為初級注冊賬號或者是不想被他人發(fā)現(xiàn)的小號;④Rs-nbr,陌生鄰居關(guān)系類型，代表此類型的用戶能夠單向的訪問信息。例如：用戶A在廣場搜索信息相關(guān)訪問用戶B主頁，用戶A為陌生人訪問，因為用戶B為開放的公共節(jié)點類型;⑤Rb-nbr，屏蔽鄰居關(guān)系類型，代表此類型的用戶因被屏蔽無法訪問鄰居節(jié)點信息[5-7]。

用不同的有向帶箭頭線段表示見圖1。關(guān)系表示：如果用戶之間為關(guān)注或被關(guān)注的關(guān)系，均用實線箭頭連接，箭頭方向指向關(guān)注的對象。行為表示：如果用戶訪問另一個用戶信息，則用點短線箭頭連接，箭頭方向指向被訪問的對象；如果用戶對另一個用戶進行屏蔽，則用虛線箭頭連接，箭頭方向指向被屏蔽的對象。由圖1可見，分別為t1,t2,t3時刻的社交網(wǎng)絡(luò)圖，可通過觀察動態(tài)社交網(wǎng)絡(luò)圖變化來分析隱私泄漏問題。

圖1 動態(tài)社交網(wǎng)絡(luò)圖變化

通過觀察動態(tài)社交網(wǎng)絡(luò)圖變化，發(fā)現(xiàn)在社交網(wǎng)絡(luò)中，用戶節(jié)點的度數(shù)是非常重要的信息，如v3,因為與其他多個用戶節(jié)點存在連接、度數(shù)高，其本身存在隱私泄露的風險也高，并且通過攻擊其節(jié)點和邊信息，也會造成其他節(jié)點的信息泄露[8]。

Vn集合中的每個節(jié)點和其他節(jié)點的關(guān)系類型一定是半鄰居關(guān)系類型或者無鄰居關(guān)系類型，即此集合中的節(jié)點只有出度關(guān)系,見圖2。在Vpub集合中的每個節(jié)點和其他節(jié)點的關(guān)系類型一般是鄰居關(guān)系類型，即此集合中的節(jié)點同時擁有入度與出度關(guān)系；而在Vpri集合中的每個節(jié)點與其他節(jié)點可能的關(guān)系包括互相鄰居關(guān)系類型、單向鄰居關(guān)系類型或者無鄰居關(guān)系類型中的一種或者多種[9-10]。因此，可得：①在Vn集合中的每個節(jié)點與Vn集合中的其他節(jié)點的關(guān)系類型一定是無鄰居關(guān)系，與Vpub集合和Vpri集合中節(jié)點的關(guān)系類型可能是是單向或雙向鄰居關(guān)系類型。②在Vpub集合中的每個節(jié)點與Vpub集合中其他節(jié)點的關(guān)系類型都是鄰居關(guān)系類型，與Vpri集合中的節(jié)點可能具有鄰居關(guān)系類型。③Vpri集合中的節(jié)點與Vpub集合中的節(jié)點或者Vpri集合中的其他節(jié)點可能具有雙向鄰居關(guān)系或者單向鄰居關(guān)系，并能夠從具有此類關(guān)系的節(jié)點中獲取到信息。此外，此類節(jié)點允許與其具有雙向鄰居關(guān)系或者單向鄰居關(guān)系的節(jié)點獲取此節(jié)點的信息。

圖2 基于隱私設(shè)置策略的動態(tài)社交網(wǎng)絡(luò)架構(gòu)

通過對節(jié)點之間的邊進行量化，定義雙向鄰居權(quán)重為2，單向鄰居關(guān)系權(quán)重為1。發(fā)生屏蔽行為權(quán)重-1，發(fā)生訪問行為權(quán)重+1。t1時刻社交網(wǎng)絡(luò)中用戶關(guān)系的量化結(jié)果見表1。根據(jù)不同時刻觀察邊的數(shù)值變化，可以發(fā)現(xiàn)用戶之間的關(guān)系變化及行為。同時，在隱私保護中還需要判斷動態(tài)社交網(wǎng)絡(luò)圖中邊的變化導(dǎo)致相應(yīng)節(jié)點度數(shù)變化，對其進行相應(yīng)的保護。

1.3 RCACM 模型

為了兼顧動態(tài)中涉及的利益相關(guān)者的時空隱私，防止不可信用戶攻擊，使用一種基于可信度的合作訪問控制模型(Reliability-based Cooperative Access Control Model，RCACM)，見圖3。

圖3 RCACM模型

基本元素定義為

U={u1,u2,…,un}表示內(nèi)容中涉及的用戶集合，通常包括一個數(shù)據(jù)發(fā)布者和多個信息相關(guān)者。

Ru={R1,R2,…,Rn}表示用戶關(guān)系分組集合，例如，Ra={Rb-nbr，Ro-nbr}。

Su={s1,s2,…,sn}表示用戶設(shè)置的隱私控制策略集合。

定義1 TCACM策略: 隱私策略為一個二元組S=〈F，D〉，其中F表示用戶關(guān)系中授權(quán)訪問的好友組集合，D表示該組中用戶拒絕訪問的個別好友集合。例如，SAmy=〈Ro-nbr,{Bob}〉表示Amy授權(quán)Ro-nbr分組中好友可見，除了Bob。

定義2 決策向量:規(guī)定給定的隱私策略執(zhí)行的操作有1(授權(quán)訪問)和0(拒絕訪問)。給定用戶u∈U，分組集合Su，u的隱私策略Su=〈F，D〉，目標用戶t，u對t的決策值表示為

(1)

定義3 可信度r：本模型通過隱私策略的嚴格程度來度量可信度，用戶對該信息設(shè)置的訪問控制策略越嚴格，隱私度越高，而隱私策略的嚴格程度往往與該目標用戶所在分組以及與該目標用戶的可信度有關(guān)。

根據(jù)動態(tài)社交網(wǎng)絡(luò)圖結(jié)構(gòu)，考慮節(jié)點和邊不同的隱私級別，對節(jié)點可信度和邊可信度進行相應(yīng)的設(shè)定。將節(jié)點可信度r分為3級，令r∈[0，3]，且r∈Z，其中，0: 陌生，1: 不信任，2: 半信任,3: 完全信任。若令δ為最大信任值，則此時δ=3。給定用戶節(jié)點vi∈V，分組節(jié)點集合Rvi，u的隱私策略Su，用戶u的節(jié)點隱私度表示為

(2)

其中，Ru(t)為分組的隱私策略嚴格度，也表示分組t能夠訪問內(nèi)容的最小可信度

Ru(t)=minr∈Rvif(u,t)

(3)

其中，f(u,t)為基于用戶u對目標用戶t的可信度。當授權(quán)訪問，該函數(shù)返回用戶u對目標用戶t的信任度，當拒絕訪問，該函數(shù)返回最大信任度，因為Ru(t)計算最小平均值，f(u,t)表示為

(4)

1.4 動態(tài)社交網(wǎng)絡(luò)圖中時空屬性

定義4 隱私興趣點。興趣點(POI, point of interest)是電子地圖上某個地標，用以標示該地所代表的政府部門、商業(yè)機構(gòu)、旅游景點、交通設(shè)施等。利用興趣點標示用戶位置，將興趣點記為Ii，興趣點集合記為L；將需要隱私保護的興趣點記為隱私興趣點pi,這種興趣點的集記為P，其中，P?L見圖4。

圖4 動態(tài)社交網(wǎng)絡(luò)拓撲

定義5 移動軌跡H。給定用戶u，在動態(tài)社交網(wǎng)絡(luò)圖中表示為節(jié)點v，其在時刻t1和tn之間的移動軌跡可以表示為一個按時間排列的序列Hv={(I1,t1),(p2,t2),(I3,t3), …,(pi-1,ti-1),(Ii,t1),…,(In,tn)},(I1,t1)是序列Hv中的一個元素，表示用戶u在時刻ti訪問過興趣點Ii，(pi-1,ti-1)表示用戶u在時刻ti-1訪問過隱私興趣點pi-1。其中Pu={(p1,t1),(p2,t2),(p3,t3),…,(pi-1,ti-1),(p1,ti),…,(pn,tn)}為用戶u訪問過的隱私移動軌跡。

隱私興趣點推理攻擊模型見圖5。Pu={(l1,t1),(pj,tj),(li+1,ti+1)}。設(shè)用戶u在t時刻發(fā)布興趣點li，在ti+1時刻發(fā)布興趣點li+1。令λ=|ti+1-ti|。如果λ遠大于從li移動到li+1所需的正常時間間隔，則攻擊者可推理出用戶在ti到ti+1間訪問過其他興趣點。當攻擊者具有一定的背景知識時，如大部分用戶遵循(li→sj→li+1)的移動規(guī)律，即使用戶未發(fā)布隱私興趣點pj，攻擊者也可推理出用戶u可能訪問過pj。

圖5 敏感興趣點推理攻擊模型

動態(tài)社交網(wǎng)絡(luò)中用戶的身份信息和時空信息相互關(guān)聯(lián)，時空信息可沿著鄰居關(guān)系在動態(tài)社交網(wǎng)絡(luò)中傳播，因此假設(shè)攻擊者具有以下背景：①用戶的移動軌跡H；軌跡由用戶一段時間內(nèi)多個簽到信息構(gòu)成；②動態(tài)社交網(wǎng)絡(luò)中的其他信息F，F(xiàn)包括用戶的社交關(guān)系、個人信息等。

攻擊者可利用上述背景知識推理用戶隱藏的敏感興趣點SI,如果存在一個位置點Pi∈P，當攻擊者推理出的用戶已訪問或?qū)⒃L問隱私興趣點Pi的可信度R(Pi|F,H,λ)>γi時，用戶的隱私被破壞。

在動態(tài)社交網(wǎng)絡(luò)中，用戶自行決定是否發(fā)布簽到等時空信息，共享時空信息可獲得更優(yōu)質(zhì)的服務(wù)，但面臨隱私泄露帶來的安全威脅，需要通過合理的計算來平衡服務(wù)的可用性與用戶的隱私需求。

2 動態(tài)社交網(wǎng)絡(luò)中時空信息隱私保護方案

動態(tài)社交網(wǎng)絡(luò)中時空信息中興趣點之間相關(guān)性的計算式為

(5)

其中，support(li,lj,li+1)為相關(guān)性的支持度計數(shù)，即依次包含興趣點li、lj和li+1的移動軌跡數(shù)。由于移動軌跡H帶有方向性，因此support(li,li+1)≠support(li+1,li)。

通過分析用戶移動軌跡H得到用戶對已訪問興趣點的隱式評價，進而發(fā)現(xiàn)與其具有相似興趣的用戶，并基于最近鄰居計算用戶對未訪問時空興趣點的評分，進而得出對于該用戶(li,li+1→lj)相關(guān)性的可信度。

2.1 用戶興趣模型

設(shè)動態(tài)社交網(wǎng)絡(luò)中存在兩個集合：①用戶的集合U，總數(shù)是m；②時空興趣點的集合L，總數(shù)是n。現(xiàn)將這兩個集合合并起來，排成一個m×n階矩陣R，行向量是用戶集合U，列向量是時空興趣點集合L,矩陣中的元素數(shù)是m×n。給定用戶uk，其興趣向量可以表示為Ruk=<(l1,rk1),…,(li,rki),…,(ln,rkn)>，rki為興趣點li的權(quán)重，即用戶uk對興趣點li的評分。

rki可以通過統(tǒng)計用戶對興趣點li的重復(fù)訪問次數(shù)得出。受信息檢索中加權(quán)技術(shù)TF-IDF的啟發(fā)，本文將時空興趣點li視為“單詞”，將用戶的移動軌跡Huk視為“文檔”，rki的計算式為

(6)

其中，counti為用戶訪問興趣點的次數(shù);U為所有用戶的集合。

矩陣R建立初期可能是一個稀疏矩陣。用戶對未訪問時空興趣點的評分可由用戶的最近鄰居得出。用Jaccard系數(shù)計算用戶社交關(guān)系之間的相似性，用余弦相似度計算用戶時空興趣的相似性。用戶相似度sim(ui,uj)的計算式為

(7)

其中，Ni和Nj分別為ui和uj鄰居的集合;α為常數(shù)，0<α<1。尋找最近鄰的目標就是對每個用戶u，在用戶空間中查找用戶集合U′={u1,u2,…,uk}，使得u?U′，并且u1與u的相似性sim(u1,u)最高，u2與u的相似性sim(u2,u)次之，依此類推。令lj是用戶uk未訪問的時空興趣點。rkj可由uk的近鄰用戶對時空興趣點lj的評分得出，表示為

(8)

(9)

其中，support(li,lj,li+1)與式中的定義相同，β為常數(shù)，0<β<1。

2.2 動態(tài)社交網(wǎng)絡(luò)時空隱私保護算法

動態(tài)社交網(wǎng)絡(luò)時空隱私保護算法(Dynamic Social Networking Spatio-Temporal Privacy Algorithm，DSNS-TPA)。令li表示用戶uk在時刻ti發(fā)布過的時空興趣點，動態(tài)社交網(wǎng)絡(luò)時空隱私保護算法首先計算兩次信息發(fā)布請求時間間隔Δt=ti+1-ti，如果Δt

(10)

其中，P(pi|li,li+1)可由式(5)或式(9)得出。當Pi

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

實驗中與流行的k-匿名算法[11]進行了對比，實驗結(jié)果的評價主要有3個指標：成功率、加密數(shù)據(jù)可用率和數(shù)據(jù)處理時間,結(jié)果見圖6。

圖6 成功率、數(shù)據(jù)可用率及處理時間實驗結(jié)果

成功率

(11)

式中:Pn為用戶初始的時空隱私數(shù)據(jù)集合;{Pe|Pe=S-TGES(p),p∈Pn}為被成功加密保護的用戶時空數(shù)據(jù)集合; S-TGES(p)為本文所提出的基于網(wǎng)格加密的時空數(shù)據(jù)隱私保護方法;|Pn|-|{Pe|Pe=S-TGES(p),p∈Pn}|為通過去加密化方法，成功再復(fù)現(xiàn)出用戶的初始時空數(shù)據(jù)以及其他相關(guān)的數(shù)據(jù)。

數(shù)據(jù)可用率

(12)

4 結(jié) 論

本文通過對動態(tài)社交網(wǎng)絡(luò)中數(shù)據(jù)發(fā)布隱私安全問題的研究分析，提出了動態(tài)圖發(fā)布隱私保護方法，該方法不僅考慮了圖結(jié)構(gòu)信息，并加入了對于時空信息的隱私保護方法。實驗結(jié)果表明，該方法能抵御多種背景知識攻擊，同時對社交網(wǎng)絡(luò)圖結(jié)構(gòu)動態(tài)變化具有較好的適應(yīng)性。