金凌竹，韓啟龍

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

0 引 言

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

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

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

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

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

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

動(dòng)態(tài)社交網(wǎng)絡(luò)根據(jù)時(shí)間劃分為一個(gè)個(gè)快照，以有向圖G=(V,E,R)來表示，V為點(diǎn)類型的集合，代表所有用戶數(shù)目的集合，V中的每個(gè)用戶均由其特有的標(biāo)識(shí)vi表示。根據(jù)用戶對(duì)消息的隱私設(shè)置策略，將所有的節(jié)點(diǎn)歸納為3種類型：①Vpub，公共節(jié)點(diǎn)類型，代表對(duì)消息采用無隱私保護(hù)設(shè)置策略的這類用戶，社交網(wǎng)絡(luò)中所有用戶都能夠獲取到此類用戶發(fā)布在社交網(wǎng)絡(luò)中的消息。Vpub的所有消息都是沒有隱私保護(hù)的;②Vpri，私有節(jié)點(diǎn)類型，代表對(duì)消息采用部分隱私保護(hù)設(shè)置策略的這類用戶，社交網(wǎng)絡(luò)中的特定的用戶都能夠獲取到此類用戶發(fā)布在社交網(wǎng)絡(luò)中的消息。Vpri的所有消息都是半隱私保護(hù)的;③Vn，獨(dú)立節(jié)點(diǎn)類型，代表對(duì)消息采用嚴(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)系類型，代表此類型的用戶能夠相互的獲取對(duì)方的消息;②Ro-nbr，單向鄰居關(guān)系類型，代表此類型的用戶能夠單向的獲取信息。例如，用戶A關(guān)注了用戶B，但是用戶B沒有回關(guān)用戶A，那么用戶A可以收到A的動(dòng)態(tài)而B不會(huì)在首頁(yè)刷到，但是如果用戶B從粉絲列表訪問，可以看到A的主頁(yè)信息。說明用戶形成了鄰居關(guān)系，但是獲取信息是單向的;③Rn-nbr，無鄰居關(guān)系類型，代表此類型的用戶無法獲取其他用戶的消息。用戶可能沒有關(guān)注任何人，也沒有粉絲關(guān)注，賬號(hào)可能為初級(jí)注冊(cè)賬號(hào)或者是不想被他人發(fā)現(xiàn)的小號(hào);④Rs-nbr,陌生鄰居關(guān)系類型，代表此類型的用戶能夠單向的訪問信息。例如：用戶A在廣場(chǎng)搜索信息相關(guān)訪問用戶B主頁(yè)，用戶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)注的對(duì)象。行為表示：如果用戶訪問另一個(gè)用戶信息，則用點(diǎn)短線箭頭連接，箭頭方向指向被訪問的對(duì)象；如果用戶對(duì)另一個(gè)用戶進(jìn)行屏蔽，則用虛線箭頭連接，箭頭方向指向被屏蔽的對(duì)象。由圖1可見，分別為t1,t2,t3時(shí)刻的社交網(wǎng)絡(luò)圖，可通過觀察動(dòng)態(tài)社交網(wǎng)絡(luò)圖變化來分析隱私泄漏問題。

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

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

Vn集合中的每個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)的關(guān)系類型一定是半鄰居關(guān)系類型或者無鄰居關(guān)系類型，即此集合中的節(jié)點(diǎn)只有出度關(guān)系,見圖2。在Vpub集合中的每個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)的關(guān)系類型一般是鄰居關(guān)系類型，即此集合中的節(jié)點(diǎn)同時(shí)擁有入度與出度關(guān)系；而在Vpri集合中的每個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)可能的關(guān)系包括互相鄰居關(guān)系類型、單向鄰居關(guān)系類型或者無鄰居關(guān)系類型中的一種或者多種[9-10]。因此，可得：①在Vn集合中的每個(gè)節(jié)點(diǎn)與Vn集合中的其他節(jié)點(diǎn)的關(guān)系類型一定是無鄰居關(guān)系，與Vpub集合和Vpri集合中節(jié)點(diǎn)的關(guān)系類型可能是是單向或雙向鄰居關(guān)系類型。②在Vpub集合中的每個(gè)節(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è)置策略的動(dòng)態(tài)社交網(wǎng)絡(luò)架構(gòu)

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

1.3 RCACM 模型

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

圖3 RCACM模型

基本元素定義為

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

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

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

定義1 TCACM策略: 隱私策略為一個(gè)二元組S=〈F，D〉，其中F表示用戶關(guān)系中授權(quán)訪問的好友組集合，D表示該組中用戶拒絕訪問的個(gè)別好友集合。例如，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對(duì)t的決策值表示為

(1)

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

根據(jù)動(dòng)態(tài)社交網(wǎng)絡(luò)圖結(jié)構(gòu)，考慮節(jié)點(diǎn)和邊不同的隱私級(jí)別，對(duì)節(jié)點(diǎn)可信度和邊可信度進(jìn)行相應(yīng)的設(shè)定。將節(jié)點(diǎn)可信度r分為3級(jí)，令r∈[0，3]，且r∈Z，其中，0: 陌生，1: 不信任，2: 半信任,3: 完全信任。若令δ為最大信任值，則此時(shí)δ=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對(duì)目標(biāo)用戶t的可信度。當(dāng)授權(quán)訪問，該函數(shù)返回用戶u對(duì)目標(biāo)用戶t的信任度，當(dāng)拒絕訪問，該函數(shù)返回最大信任度，因?yàn)镽u(t)計(jì)算最小平均值，f(u,t)表示為

(4)

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

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

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

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

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

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

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

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

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

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

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

(5)

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

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

2.1 用戶興趣模型

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

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

(6)

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

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

(7)

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

(8)

(9)

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

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

動(dòng)態(tài)社交網(wǎng)絡(luò)時(shí)空隱私保護(hù)算法(Dynamic Social Networking Spatio-Temporal Privacy Algorithm，DSNS-TPA)。令li表示用戶uk在時(shí)刻ti發(fā)布過的時(shí)空興趣點(diǎn)，動(dòng)態(tài)社交網(wǎng)絡(luò)時(shí)空隱私保護(hù)算法首先計(jì)算兩次信息發(fā)布請(qǐng)求時(shí)間間隔Δ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)行了對(duì)比，實(shí)驗(yàn)結(jié)果的評(píng)價(jià)主要有3個(gè)指標(biāo)：成功率、加密數(shù)據(jù)可用率和數(shù)據(jù)處理時(shí)間,結(jié)果見圖6。

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

成功率

(11)

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

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

(12)

4 結(jié) 論

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