動態(tài)社交網(wǎng)絡(luò)中的數(shù)據(jù)發(fā)布隱私保護(hù)技術(shù)

金凌竹，韓啟龍

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

0 引 言

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

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

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

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ù)進(jìn)行隱私保護(hù)的匯聚，可以在保護(hù)用戶個人數(shù)據(jù)隱私的前提下，實(shí)現(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為點(diǎn)類型的集合，代表所有用戶數(shù)目的集合，V中的每個用戶均由其特有的標(biāo)識vi表示。根據(jù)用戶對消息的隱私設(shè)置策略，將所有的節(jié)點(diǎn)歸納為3種類型：①Vpub，公共節(jié)點(diǎn)類型，代表對消息采用無隱私保護(hù)設(shè)置策略的這類用戶，社交網(wǎng)絡(luò)中所有用戶都能夠獲取到此類用戶發(fā)布在社交網(wǎng)絡(luò)中的消息。Vpub的所有消息都是沒有隱私保護(hù)的;②Vpri，私有節(jié)點(diǎn)類型，代表對消息采用部分隱私保護(hù)設(shè)置策略的這類用戶，社交網(wǎng)絡(luò)中的特定的用戶都能夠獲取到此類用戶發(fā)布在社交網(wǎng)絡(luò)中的消息。Vpri的所有消息都是半隱私保護(hù)的;③Vn，獨(dú)立節(jié)點(diǎn)類型，代表對消息采用嚴(yán)格的隱私保護(hù)設(shè)置策略的這類用戶，社交網(wǎng)絡(luò)中的其他用戶均無法獲取到此類用戶發(fā)布在社交網(wǎng)絡(luò)中的消息。Vn的所有消息都是嚴(yán)格隱私保護(hù)的。

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為陌生人訪問，因?yàn)橛脩鬊為開放的公共節(jié)點(diǎn)類型;⑤Rb-nbr，屏蔽鄰居關(guān)系類型，代表此類型的用戶因被屏蔽無法訪問鄰居節(jié)點(diǎn)信息[5-7]。

用不同的有向帶箭頭線段表示見圖1。關(guān)系表示：如果用戶之間為關(guān)注或被關(guān)注的關(guān)系，均用實(shí)線箭頭連接，箭頭方向指向關(guān)注的對象。行為表示：如果用戶訪問另一個用戶信息，則用點(diǎn)短線箭頭連接，箭頭方向指向被訪問的對象；如果用戶對另一個用戶進(jì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é)點(diǎn)的度數(shù)是非常重要的信息，如v3,因?yàn)榕c其他多個用戶節(jié)點(diǎn)存在連接、度數(shù)高，其本身存在隱私泄露的風(fēng)險也高，并且通過攻擊其節(jié)點(diǎn)和邊信息，也會造成其他節(jié)點(diǎn)的信息泄露[8]。

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

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

通過對節(jié)點(diǎn)之間的邊進(jìn)行量化，定義雙向鄰居權(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)系變化及行為。同時，在隱私保護(hù)中還需要判斷動態(tài)社交網(wǎng)絡(luò)圖中邊的變化導(dǎo)致相應(yīng)節(jié)點(diǎn)度數(shù)變化，對其進(jìn)行相應(yīng)的保護(hù)。

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〉，目標(biāo)用戶t，u對t的決策值表示為

(1)

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

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

(2)

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

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

(3)

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

(4)

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

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

圖4 動態(tài)社交網(wǎng)絡(luò)拓?fù)?/p>

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

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

圖5 敏感興趣點(diǎn)推理攻擊模型

動態(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)系、個人信息等。

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

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

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

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

(5)

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

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

2.1 用戶興趣模型

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

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

(6)

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

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

(7)

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

(8)

(9)

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

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

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

(10)

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

成功率

(11)

式中:Pn為用戶初始的時空隱私數(shù)據(jù)集合;{Pe|Pe=S-TGES(p),p∈Pn}為被成功加密保護(hù)的用戶時空數(shù)據(jù)集合; S-TGES(p)為本文所提出的基于網(wǎng)格加密的時空數(shù)據(jù)隱私保護(hù)方法;|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ā)布隱私保護(hù)方法，該方法不僅考慮了圖結(jié)構(gòu)信息，并加入了對于時空信息的隱私保護(hù)方法。實(shí)驗(yàn)結(jié)果表明，該方法能抵御多種背景知識攻擊，同時對社交網(wǎng)絡(luò)圖結(jié)構(gòu)動態(tài)變化具有較好的適應(yīng)性。