孫連山，馬勝天，王 荔，陳秀婷

（陜西科技大學(xué)電子信息與人工智能學(xué)院，陜西西安 710021）

信息時(shí)代蓬勃發(fā)展，數(shù)據(jù)在互聯(lián)網(wǎng)上傳播和共享的過程中，攜帶了各種各樣的信息，其中不乏用戶的個(gè)人敏感信息。數(shù)據(jù)在公開共享之前，敏感信息的隱私保護(hù)成為多行業(yè)的重點(diǎn)關(guān)注問題［1］。數(shù)據(jù)起源（Data Provenance）領(lǐng)域的隱私保護(hù)問題也是學(xué)者們一直以來的研究重點(diǎn)和難點(diǎn)［2］。

數(shù)據(jù)起源描述了參與生產(chǎn)、影響或交付一條數(shù)據(jù)或一件事物的實(shí)體、活動(dòng)、人或機(jī)構(gòu)。通常呈現(xiàn)為有向無環(huán)圖，簡(jiǎn)稱起源圖［3－4］。 特別來說，數(shù)據(jù)的來源對(duì)于決定信息是否可信，如何與其他的信息源集成以及在重用信息時(shí)是否能信任信息至關(guān)重要。

起源圖中通常包含很多隱私數(shù)據(jù)，如職業(yè)、收入、銀行卡號(hào)等，所以在公開發(fā)布數(shù)據(jù)起源之前需要對(duì)數(shù)據(jù)信息中的敏感數(shù)據(jù)進(jìn)行遮蔽或改造。起源過濾是通過改造起源圖，達(dá)到隱藏敏感信息的一種新型技術(shù)。Dey等［5］提出一種可以定制發(fā)布的PROPUB起源過濾框架，允許用戶分別指定起源圖中需要保留、隱藏、匿名或抽象的部分。王藝星等［6］提出“刪除＋過濾”的高效用的過濾機(jī)制，刪除敏感節(jié)點(diǎn)或邊，在保證溯源結(jié)果不增加的情況下，引入不確定依賴關(guān)系。Missier等［7］提出一種基于抽象的起源圖過濾方法，將起源圖中的敏感節(jié)點(diǎn)與其周圍的一些節(jié)點(diǎn)組合在一起，用一個(gè)抽象的節(jié)點(diǎn)代替。

總的來說，現(xiàn)有針對(duì)敏感信息的過濾方法都會(huì)改變起源圖的結(jié)構(gòu)，但起源圖的結(jié)構(gòu)蘊(yùn)含著數(shù)據(jù)之間的依賴關(guān)系，破壞起源圖的結(jié)構(gòu)會(huì)對(duì)起源圖的溯源效用產(chǎn)生影響；另外，現(xiàn)有的過濾方法僅僅關(guān)注當(dāng)前起源圖的改造，沒有考慮已經(jīng)公開發(fā)布的起源圖與當(dāng)前起源圖之間的關(guān)聯(lián)，攻擊者可能結(jié)合已公開起源圖，對(duì)當(dāng)前起源圖的敏感信息進(jìn)行推理，從而導(dǎo)致敏感信息泄露。

因此，本文結(jié)合研究現(xiàn)狀和數(shù)據(jù)起源的特點(diǎn)，提出一種基于節(jié)點(diǎn)聚類的數(shù)據(jù)起源安全保護(hù)方法，在不改變起源圖結(jié)構(gòu)的基礎(chǔ)上，構(gòu)建起源圖節(jié)點(diǎn)的層次聚類樹，設(shè)計(jì)過濾視圖的威脅和安全評(píng)估模型，依據(jù)用戶對(duì)敏感節(jié)點(diǎn)的要求，對(duì)起源圖節(jié)點(diǎn)進(jìn)行泛化，泛化不同的節(jié)點(diǎn)數(shù)能夠滿足用戶不同的起源發(fā)布偏好。實(shí)驗(yàn)結(jié)果表明，該方法能夠在對(duì)敏感信息進(jìn)行隱私保護(hù)的同時(shí)，保證過濾視圖的溯源效用。

1 相關(guān)知識(shí)介紹

1.1 數(shù)據(jù)起源

本節(jié)結(jié)合實(shí)例介紹數(shù)據(jù)起源等相關(guān)概念，并介紹節(jié)點(diǎn)聚類策略和泛化的定義。

數(shù)據(jù)起源記錄數(shù)據(jù)生產(chǎn)、轉(zhuǎn)換過程的中間數(shù)據(jù)和相關(guān)人員、組織信息。根據(jù)W3C于2013年發(fā)布的數(shù)據(jù)起源模型（PROV?DM）及其相關(guān)模型的標(biāo)準(zhǔn)［8］，數(shù)據(jù)起源通常呈現(xiàn)為如圖1所示的有向無環(huán)圖。起源圖中的節(jié)點(diǎn)主要有實(shí)體節(jié)點(diǎn)，如節(jié)點(diǎn)e3，e4；活動(dòng)節(jié)點(diǎn)，如 p2，p3；代理節(jié)點(diǎn)，如 L1。 起源圖中的依賴關(guān)系有 7種，即生成（generation）、使用（usage）、派生（derivation）、通信（communication）、歸屬（attribution）、關(guān)聯(lián)（association）和委托（delegation）［9－10］。 不同類型的邊代表不同節(jié)點(diǎn)之間的依賴關(guān)系，例如使用邊是由實(shí)體節(jié)點(diǎn)指向活動(dòng)節(jié)點(diǎn)，記作used；產(chǎn)生邊為活動(dòng)節(jié)點(diǎn)指向?qū)嶓w節(jié)點(diǎn)，記作wgb；代理節(jié)點(diǎn)與活動(dòng)節(jié)點(diǎn)之間相連的邊為關(guān)聯(lián)邊，記作waw。

圖1 某藥品配方起源圖

為便于論述，形式地定義起源圖如下。

定義1（起源圖 PG＝（V，E，Ph））節(jié)點(diǎn) V＝｛v1，v2，…，vn｝表示起源圖 PG 中的 n個(gè)節(jié)點(diǎn)的集合；邊 E ＝ ｛ei｜ei＝ ＜u，v＞， u∈V，v∈V， i ＝1， 2，…，m｝表示圖PG有m條有向邊。路徑集Ph＝｛Phi＝ （u， v）， u∈V，v∈V， i＝ 1，2，…，r｝表示圖PG中有r條路徑。

定義2（過濾視圖PV＝f（PG，SI）） PG表示原始起源圖，SI為敏感信息集合，f表示所采用的過濾策略，過濾視圖PV為原始起源圖PG針對(duì)敏感信息SI采用過濾策略f進(jìn)行過濾所得到的起源圖。

定義3（直接前因節(jié)點(diǎn)集preN（PG，v））在起源圖PG中存在由節(jié)點(diǎn)v指向節(jié)點(diǎn)u的邊，且節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的路徑長(zhǎng)度為1，稱節(jié)點(diǎn)u是節(jié)點(diǎn)v的直接前因節(jié)點(diǎn)，preN（PG，v）表示節(jié)點(diǎn)v的直接前因節(jié)點(diǎn)集。如圖1所示，節(jié)點(diǎn)e3和節(jié)點(diǎn)e4是節(jié)點(diǎn)p2的直接前因節(jié)點(diǎn)，則 preN（PG， p2）＝ ｛e3， e4｝。 節(jié)點(diǎn)e3，e4與節(jié)點(diǎn)p2之間的連通邊類型為使用邊，則也可記作 preNused（PG， p2）＝ ｛e3， e4｝。

定義4（直接后果節(jié)點(diǎn)集 subN（PG，v））在起源圖PG中存在由節(jié)點(diǎn)u指向節(jié)點(diǎn)v的邊，且節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的路徑長(zhǎng)度為1，稱節(jié)點(diǎn)u是節(jié)點(diǎn)v的直接后果節(jié)點(diǎn)，subN（PG，v）表示節(jié)點(diǎn)v的直接后果節(jié)點(diǎn)集合。如圖1所示，節(jié)點(diǎn)p2和節(jié)點(diǎn)p3是節(jié)點(diǎn)e4的直接后果節(jié)點(diǎn)，則 subN（PG， e4）＝ ｛p2， p3｝。 節(jié)點(diǎn)p2和節(jié)點(diǎn)p3與節(jié)點(diǎn)e4之間的連通邊類型為使用邊，則也可記作 subNused（PG， e4）＝ ｛p2， p3｝。

定義5（節(jié)點(diǎn)向量Vec）起源圖中的節(jié)點(diǎn)數(shù)據(jù)以文檔形式存儲(chǔ)，為便于計(jì)算節(jié)點(diǎn)之間的距離，需將節(jié)點(diǎn)用向量表示，本文采用word2vec算法將節(jié)點(diǎn)轉(zhuǎn)化為向量，對(duì)于任意節(jié)點(diǎn)vi∈V，其向量化表示為Vec。

1.2 層次聚類

層次聚類（Hierarchical Clustering）是聚類算法的一種，通過計(jì)算兩類數(shù)據(jù)點(diǎn)間的相似性，對(duì)所有數(shù)據(jù)點(diǎn)中最為相似的兩個(gè)數(shù)據(jù)點(diǎn)進(jìn)行組合，并反復(fù)迭代這一過程［11－12］。

定義6（簇間距離）設(shè)有兩個(gè)簇Ci和Cj，類簇之間的相似度用簇間距離評(píng)估，本文采用式（1）平均距離計(jì)算簇間距離。

其中， Xi，Xj為類簇中任取的樣本，｜Ci｜為類簇 Ci中的樣本數(shù)量，｜Cj｜為類簇Cj中的樣本數(shù)量。

定義7（節(jié)點(diǎn)相似度）起源圖PG中同類型的任意兩個(gè)節(jié)點(diǎn)之間的相似程度。本文采用式（2）余弦距離計(jì)算樣本節(jié)點(diǎn)間的距離。

其中，vi和vj為起源圖PG中任意兩個(gè)節(jié)點(diǎn)。

定義8（層次聚類樹）將所有樣本層次聚類的結(jié)果以樹狀圖的形式展示。圖2是年齡的聚類層次樹，原始樣本點(diǎn)位于樹的底層，也就是葉子結(jié)點(diǎn)；樹的頂層是一個(gè)聚類的根節(jié)點(diǎn)，包含所有原始樣本的信息。

圖2 年齡層次聚類樹

1.3 節(jié)點(diǎn)泛化

在數(shù)據(jù)處理過程中，用模糊的、范圍的取值取代精確取值的過程被稱為數(shù)據(jù)泛化［13］。結(jié)合數(shù)據(jù)泛化的定義，節(jié)點(diǎn)泛化也就是將與敏感節(jié)點(diǎn)的取值相近的多個(gè)節(jié)點(diǎn)的值進(jìn)行泛化概括，取代敏感節(jié)點(diǎn)的精確值，達(dá)到隱藏敏感信息的目的。

定義 9（泛化結(jié)果簇 RPG（vi））節(jié)點(diǎn) vi根據(jù)層次聚類樹，選擇一個(gè)合適的類簇進(jìn)行泛化，該簇就是節(jié)點(diǎn)vi的泛化簇集。如圖3所示，若要對(duì)年齡“23”進(jìn)行泛化，其泛化簇集可能為｛“23”，“26”，“29”｝、｛“10”，“15”，“23”，“26”，“29”｝或｛“10”，“15”，“23”，“26”，“29”，“38”，“40”，“43”，“49”｝，對(duì)應(yīng)泛化后的年齡取值為“23－29”，“10－29”或“10－49”。

2 數(shù)據(jù)起源安全威脅與評(píng)估

數(shù)據(jù)起源隱私保護(hù)的安全性與其所面臨的威脅密切相關(guān)。本節(jié)闡述數(shù)據(jù)起源所面對(duì)的安全威脅和攻擊者可以采用的推理方式，通過計(jì)算敏感節(jié)點(diǎn)的安全性對(duì)過濾視圖進(jìn)行安全評(píng)估。

2.1 安全威脅

定義10（已公開起源圖集PubPG）將PubPG＝｛PG1，PG2，…，PGl｝，其中 PG1，PG2，…，PGl是已經(jīng)公開發(fā)布的起源圖。起源圖PGi（1≤i≤l）為采用不同的過濾技術(shù)進(jìn)行敏感信息過濾的起源圖。

不同階段或不同偏好下發(fā)布的起源圖存在密切的關(guān)聯(lián)，已經(jīng)公開的起源圖數(shù)據(jù)可能對(duì)當(dāng)前需要公開的起源圖數(shù)據(jù)存在安全威脅。例如，圖3是需要公開發(fā)布的原起源圖的部分子圖，其中，敏感信息是節(jié)點(diǎn)e1，泛化節(jié)點(diǎn)e1為節(jié)點(diǎn)e，得到其過濾視圖PV如圖4所示。而圖5是已經(jīng)公開發(fā)布過的一張起源圖的子圖，顯然，節(jié)點(diǎn)e1是操作p2使用實(shí)體e3所產(chǎn)生的，攻擊者可由此推理出在圖4過濾視圖中的節(jié)點(diǎn)e有二分之一的可能性是節(jié)點(diǎn)e1，進(jìn)而導(dǎo)致敏感節(jié)點(diǎn)e1泄露。

圖3 原起源圖子圖PG

圖4 起源圖子圖PG的過濾視圖PV

圖5 已公開起源圖子圖PGi

2.2 推理方式

攻擊者獲得過濾視圖后，首先需要確定待推理節(jié)點(diǎn)，也就是敏感節(jié)點(diǎn)。不同的過濾技術(shù)所得到的過濾視圖具有不同的特點(diǎn)，如匿名［14］或者抽象［15］方法所得到的過濾視圖中會(huì)出現(xiàn)空節(jié)點(diǎn)［16］；本文所提出的泛化方法所得到的過濾視圖中會(huì)出現(xiàn)某些節(jié)點(diǎn)數(shù)值模糊的情況。攻擊者可以根據(jù)過濾視圖中的節(jié)點(diǎn)特征確定待推理節(jié)點(diǎn)。另外，已公開起源圖集PubPG與當(dāng)前公開發(fā)布的過濾視圖PV之間可能有多種多樣的關(guān)聯(lián)，攻擊者可以通過這些關(guān)聯(lián)對(duì)當(dāng)前過濾視圖中的敏感節(jié)點(diǎn)進(jìn)行推理。

攻擊者確定待推理節(jié)點(diǎn)后，對(duì)待推理節(jié)點(diǎn)的推理有多種方式，主要分為3類：?jiǎn)喂?jié)點(diǎn)推理、多節(jié)點(diǎn)融合推理和節(jié)點(diǎn)級(jí)聯(lián)推理。

定義11（待推理節(jié)點(diǎn)的推理結(jié)果集resN（PV，v））過濾視圖PV中，節(jié)點(diǎn)v是待推理節(jié)點(diǎn)，攻擊者將已有起源圖作為攻擊背景，對(duì)當(dāng)前過濾視圖的待推理節(jié)點(diǎn)進(jìn)行推理，推理結(jié)果通常為已公開起源圖中已有的節(jié)點(diǎn)的集合。resN（PV，v）表示攻擊者采用任一推理方式獲得待推理節(jié)點(diǎn)v在已公開起源圖中可能的取值節(jié)點(diǎn)，記作 resN（PV，v） ＝ ｛v1，v2，…，vm｝，其中 v1，v2，…，vm∈ PG1∪ PG2∪ … ∪ PGl。

（1）單節(jié)點(diǎn)推理。假設(shè)過濾視圖PV中待推理節(jié)點(diǎn)v只存在一個(gè)直接前因節(jié)點(diǎn)prev（后果節(jié)點(diǎn)subv），且該前因（后果）節(jié)點(diǎn)未被泛化，將待推理節(jié)點(diǎn)與其前因（后果）節(jié)點(diǎn)之間的邊類型記作epre（或esub）。若存在節(jié)點(diǎn)s為與前因節(jié)點(diǎn)prev（或后果節(jié)點(diǎn)subv）相似度最高的節(jié)點(diǎn)，其中節(jié)點(diǎn)s∈PGi且起源圖PGi∈PubPG，在起源圖PGi中與節(jié)點(diǎn)s相連的邊類型為esub（或 epre） 的節(jié)點(diǎn)集為 esub（s）＝ ｛v1， v2，…， vn｝（或epre（s）＝ ｛v1， v2，…， vn｝），則將節(jié)點(diǎn)集 esub（s）或 epre（s）中的節(jié)點(diǎn)與待推理節(jié)點(diǎn)v的相似度按從大到小的順序排列的結(jié)果，即為待推理節(jié)點(diǎn)v的推理結(jié)果集。

（2）多節(jié)點(diǎn)融合推理。假設(shè)過濾視圖PV中待推理節(jié)點(diǎn)v的直接前因節(jié)點(diǎn)集preN（PG，v）和直接后果節(jié)點(diǎn)集subN（PG，v）中的節(jié)點(diǎn)有多個(gè)，如圖4所示。 待推理節(jié)點(diǎn)為節(jié)點(diǎn) e，其 perN（PV， e）＝ ｛p2｝，subN（PV， e）＝ ｛p1｝，其中節(jié)點(diǎn) p1和節(jié)點(diǎn) p2均未被泛化。此時(shí)，攻擊者可以結(jié)合多個(gè)節(jié)點(diǎn)，即多個(gè)證據(jù)對(duì)待推理節(jié)點(diǎn)進(jìn)行融合推理。攻擊者可以將多個(gè)單節(jié)點(diǎn)推理方式下同一個(gè)節(jié)點(diǎn)與待推理節(jié)點(diǎn)的相似度取和，作為多節(jié)點(diǎn)融合推理的結(jié)果集。

（3）節(jié)點(diǎn)級(jí)聯(lián)推理。假設(shè)過濾視圖PV中有多個(gè)泛化節(jié)點(diǎn)，某待推理節(jié)點(diǎn)的直接前因節(jié)點(diǎn)或直接后果節(jié)點(diǎn)也是泛化節(jié)點(diǎn)，此時(shí)對(duì)待推理節(jié)點(diǎn)的推理需要通過級(jí)聯(lián)推理的方式完成推理。如圖4所示，若節(jié)點(diǎn)e0、p1為泛化節(jié)點(diǎn)，當(dāng)要對(duì)節(jié)點(diǎn)e0進(jìn)行推理時(shí)，其直接前因節(jié)點(diǎn)p1也為泛化節(jié)點(diǎn)，此時(shí)，對(duì)節(jié)點(diǎn)e0的推理需要采用級(jí)聯(lián)推理的方式完成。

以上3種推理方式在攻擊者的實(shí)際應(yīng)用中通常不是單獨(dú)使用的，對(duì)同一節(jié)點(diǎn)的推理可能需要同時(shí)用到3種推理方式。采用的推理方式越多，攻擊者推測(cè)出敏感節(jié)點(diǎn)的可能就越大，攻擊者可以對(duì)多種推理方式所得到的推理結(jié)果對(duì)比分析得出最終的推理結(jié)果。

2.3 敏感節(jié)點(diǎn)安全性

不同情況下，攻擊者推理出敏感信息的難度不同，本文將攻擊者最終確定的待推理節(jié)點(diǎn)的推理結(jié)果節(jié)點(diǎn)與原始敏感節(jié)點(diǎn)的相似性作為敏感節(jié)點(diǎn)安全性的評(píng)價(jià)指標(biāo)，記作Q，形式化地表示為

其中，過濾視圖 PV中被泛化的節(jié)點(diǎn)數(shù)為 k。resN（PV，vt） ＝｛v1，v2，…，vm｝ 為攻擊者采用單節(jié)點(diǎn)推理方式獲得的待推理節(jié)點(diǎn)vt的推理結(jié)果，m為節(jié)點(diǎn)集resN（PV，vt）中節(jié)點(diǎn)的個(gè)數(shù)。攻擊者將節(jié)點(diǎn)vi（1≤i≤m）作為待推理節(jié)點(diǎn)vt的最終推理節(jié)點(diǎn)值，而v0表示待推理節(jié)點(diǎn)v真實(shí)的原始敏感節(jié)點(diǎn)中的取值。

顯然，0≤Q≤1，Q的值越大，表示攻擊者最終確定的待推理節(jié)點(diǎn)的最終推理節(jié)點(diǎn)與真實(shí)的敏感節(jié)點(diǎn)的相似度越高，則敏感信息的泄露概率就越大，過濾視圖中敏感信息的安全性就越低。

3 基于節(jié)點(diǎn)聚類的數(shù)據(jù)起源安全保護(hù)方法

首先，提取原起源圖和已公開起源圖中所有實(shí)體節(jié)點(diǎn)、活動(dòng)節(jié)點(diǎn)和代理節(jié)點(diǎn)的信息，應(yīng)用word2vec算法思想將節(jié)點(diǎn)信息轉(zhuǎn)換為嵌入向量［17］；通過計(jì)算嵌入向量間的相似度，采用聚類算法分別構(gòu)造實(shí)體節(jié)點(diǎn)、活動(dòng)節(jié)點(diǎn)和代理節(jié)點(diǎn)的聚類層次樹；根據(jù)用戶指定的敏感節(jié)點(diǎn)更新泛化節(jié)點(diǎn)集，對(duì)泛化節(jié)點(diǎn)集中的節(jié)點(diǎn)，結(jié)合其所在的聚類層次樹進(jìn)行泛化，并且計(jì)算敏感節(jié)點(diǎn)的泄露概率，將該概率值與用戶的期望值相比較，若小于用戶期望值，則泛化完成，輸出過濾視圖；否則更新泛化節(jié)點(diǎn)集，即將敏感節(jié)點(diǎn)的關(guān)聯(lián)節(jié)點(diǎn)更新到泛化節(jié)點(diǎn)集中，繼續(xù)泛化，直至實(shí)際的敏感節(jié)點(diǎn)泄露概率值小于用戶期望值。

3.1 層次聚類樹的構(gòu)造

起源圖中節(jié)點(diǎn)數(shù)據(jù)通常以文本形式存儲(chǔ)，要想對(duì)其進(jìn)行聚類，須將其轉(zhuǎn)換成可計(jì)算的結(jié)構(gòu)化數(shù)據(jù)，即向量形式。本文應(yīng)用word2vec算法實(shí)現(xiàn)文本到向量的轉(zhuǎn)換［18－19］，如圖 6 所示。

圖6 word2vec算法示例

從起源圖原始數(shù)據(jù)表中獲得節(jié)點(diǎn)屬性值，組合為文本數(shù)據(jù)構(gòu)成語料庫(kù)，使用word2vec算法獲得起源圖所有節(jié)點(diǎn)的向量表示。

使用層次聚類算法，通過計(jì)算節(jié)點(diǎn)向量間的距離，分別形成實(shí)體節(jié)點(diǎn)、活動(dòng)節(jié)點(diǎn)和代理節(jié)點(diǎn)的層次聚類樹。層次聚類算法是基于簇間相似度進(jìn)行的，每個(gè)簇類中包含了一個(gè)或者多個(gè)樣本點(diǎn)，通常用距離評(píng)價(jià)簇間或者樣本間的相似度，即距離越小相似度越高，距離越大相似度越低［20］。

3.2 基于層次聚類樹的節(jié)點(diǎn)泛化策略

起源圖中的敏感節(jié)點(diǎn)通常是由起源圖所有者指定，當(dāng)所有者指定敏感節(jié)點(diǎn)后，首先依據(jù)該節(jié)點(diǎn)所在的層次聚類樹，對(duì)敏感節(jié)點(diǎn)進(jìn)行泛化。

由于起源圖的產(chǎn)生方式多種多樣，其中具有多種依賴關(guān)系，攻擊者可能會(huì)根據(jù)起源圖的依賴關(guān)系對(duì)敏感節(jié)點(diǎn)進(jìn)行推理，很大可能會(huì)造成敏感信息泄露，所以僅僅泛化敏感節(jié)點(diǎn)是不夠的，而需要結(jié)合起源圖的結(jié)構(gòu)信息，也就是節(jié)點(diǎn)間的依賴關(guān)系，對(duì)敏感節(jié)點(diǎn)的關(guān)聯(lián)節(jié)點(diǎn)進(jìn)行泛化，以實(shí)現(xiàn)更高程度的隱私保護(hù)。如圖7所示，節(jié)點(diǎn)A與節(jié)點(diǎn)B相關(guān)，而節(jié)點(diǎn)B又與節(jié)點(diǎn)C相關(guān)。若節(jié)點(diǎn)B為敏感節(jié)點(diǎn)，在泛化時(shí)不能僅僅泛化節(jié)點(diǎn)B，還需要對(duì)節(jié)點(diǎn)A和節(jié)點(diǎn)C進(jìn)行泛化，從而保證節(jié)點(diǎn) B的敏感信息不被關(guān)聯(lián)推理。

圖7 簡(jiǎn)單起源圖

因此，節(jié)點(diǎn)的泛化主要分為敏感節(jié)點(diǎn)的泛化和敏感節(jié)點(diǎn)關(guān)聯(lián)節(jié)點(diǎn)的泛化。

定義 12（泛化節(jié)點(diǎn)集 HPG，v）PG 為起源圖，v為敏感節(jié)點(diǎn)，則泛化節(jié)點(diǎn)集HPG，v表示在起源圖PG中，當(dāng)敏感節(jié)點(diǎn)是v時(shí)，需要進(jìn)行泛化的節(jié)點(diǎn)集合。

3.3 泛化節(jié)點(diǎn)集的計(jì)算

節(jié)點(diǎn)泛化分為敏感節(jié)點(diǎn)和關(guān)聯(lián)節(jié)點(diǎn)的泛化，但若是泛化敏感節(jié)點(diǎn)的所有關(guān)聯(lián)節(jié)點(diǎn)，會(huì)造成泛化過度和過濾視圖的效用低下，故本文引入敏感節(jié)點(diǎn)的泄露概率的概念，作為泛化節(jié)點(diǎn)集更新和泛化停止的標(biāo)志。

敏感節(jié)點(diǎn)泄露概率分為實(shí)際值pcact和期望值pcexp。期望值由起源圖所有者指定，代表對(duì)起源圖敏感信息的安全程度的要求；實(shí)際值由本方法給出，每次泛化節(jié)點(diǎn)集中的節(jié)點(diǎn)泛化完成后，計(jì)算敏感節(jié)點(diǎn)的泄露概率，與用戶的期望值相比較，當(dāng)實(shí)際值小于等于用戶的期望值時(shí)，結(jié)束泛化，此時(shí)起源圖中被泛化節(jié)點(diǎn)的數(shù)量記為K。

在當(dāng)前起源圖中，已泛化節(jié)點(diǎn)為v，通過查看該節(jié)點(diǎn)所在的聚類層次樹可知，節(jié)點(diǎn)v的泛化結(jié)果簇為 RPG（v）＝ ｛v1， v2，…， vt，…， vn｝，其中 v1， v2，…，vn∈PG1∪PG2∪…∪PGl，vt為原起源圖 PG 中的敏感節(jié)點(diǎn)。節(jié)點(diǎn) v的直接前因節(jié)點(diǎn)集preN（PG，v）＝｛pre1v， pre2v， …， premv ｝， 直 接 后 果 節(jié) 點(diǎn) 集subN（PG，v）＝ ｛sub1v， sub2v，…， subkv ｝。 以下以pre1v為例，計(jì)算節(jié)點(diǎn)v與節(jié)點(diǎn)pre1v之間敏感節(jié)點(diǎn)的泄露概率。首先，在公開起源圖集 PubPG＝｛PG1，PG2，…，PGl｝中查找與pre1v相似度最高的節(jié)點(diǎn)pre1v′，pre1v′所在的起源圖記作 PGi（1≤i≤l），節(jié)點(diǎn) pre1v與節(jié)點(diǎn)pre1v′之間的相似度采用式（2）計(jì)算得到，記作C。其次，由于節(jié)點(diǎn)v是節(jié)點(diǎn)pre1v的后果節(jié)點(diǎn)，則起源圖PGi中獲取節(jié)點(diǎn)pre1v′的直接后果節(jié)點(diǎn)集 subN（PGi， pre1v′） ＝ ｛v1， v2，…， vs｝，其中 v1，v2，…， vs∈PGi。 最后，采用式（4）計(jì)算節(jié)點(diǎn)集 RPG（v）＝ ｛v1， v2，…， vn｝ 中節(jié)點(diǎn)與節(jié)點(diǎn)集 subN（PGi，pre1v′）＝ ｛v1， v2，…， vs｝中節(jié)點(diǎn)的相似度，則

其中，v0為起源圖 PG中的敏感節(jié)點(diǎn)。vi∈ RPG（v），i＝ 1，2，…，m。 vi∈ subN（PGi，pre1v′），j＝ 1，2，…，s。C為節(jié)點(diǎn)pre1v與節(jié)點(diǎn)pre1v′之間的相似度。

采用式（4）來計(jì)算泛化節(jié)點(diǎn)與其未泛化的前因節(jié)點(diǎn)或后繼節(jié)點(diǎn)之間的敏感節(jié)點(diǎn)泄露概率。當(dāng)有多條路徑可以對(duì)敏感節(jié)點(diǎn)的泛化節(jié)點(diǎn)進(jìn)行推理時(shí)，敏感節(jié)點(diǎn)的實(shí)際泄露概率取所有路徑上敏感節(jié)點(diǎn)泄露概率的最大值；當(dāng)被泛化節(jié)點(diǎn)的前因節(jié)點(diǎn)或者后果節(jié)點(diǎn)也被泛化時(shí)，采用級(jí)聯(lián)推理的方式，從一個(gè)未泛化節(jié)點(diǎn)為推理起點(diǎn)，完成對(duì)敏感節(jié)點(diǎn)的泛化節(jié)點(diǎn)的推理。

一次泛化完成后，比較敏感節(jié)點(diǎn)泄露概率的實(shí)際值pcact和起源圖所有者給定的敏感節(jié)點(diǎn)泄露概率期望值 pcexp，當(dāng)pcact≤pcexp時(shí)，結(jié)束泛化；否則，查看泛化節(jié)點(diǎn)集中是否有未泛化節(jié)點(diǎn)，若有，則對(duì)其進(jìn)行泛化，否則查找當(dāng)前泛化節(jié)點(diǎn)集中第一個(gè)存在未被泛化的直接前因節(jié)點(diǎn)或后果節(jié)點(diǎn)的節(jié)點(diǎn)，并將其未被泛化的直接前因節(jié)點(diǎn)或后果節(jié)點(diǎn)的節(jié)點(diǎn)加入泛化節(jié)點(diǎn)集中繼續(xù)泛化，直至敏感節(jié)點(diǎn)泄露概率的實(shí)際值pcact小于等于起源圖所有者給定的敏感節(jié)點(diǎn)泄露概率期望值pcexp。

當(dāng)完成泛化節(jié)點(diǎn)集HPG，v中所有節(jié)點(diǎn)的泛化，并且滿足敏感節(jié)點(diǎn)泄露概率的實(shí)際值pcact小于等于起源圖所有者給定的敏感節(jié)點(diǎn)泄露概率期望值pcexp后，提取泛化節(jié)點(diǎn)集HPG，v中每一個(gè)節(jié)點(diǎn)的泛化結(jié)果簇RPG（v）中節(jié)點(diǎn)的共有特征，作為預(yù)發(fā)布起源圖PV中對(duì)應(yīng)節(jié)點(diǎn)的屬性信息。

4 敏感節(jié)點(diǎn)隱私保護(hù)算法

針對(duì)已經(jīng)公開的起源圖集對(duì)當(dāng)前起源圖具有安全威脅這一場(chǎng)景，以及現(xiàn)有隱私保護(hù)方法改變起源圖結(jié)構(gòu)的問題，本文提出一種基于節(jié)點(diǎn)聚類的數(shù)據(jù)起源安全保護(hù)方法。該方法通過節(jié)點(diǎn)聚類分析并建立已有起源圖中節(jié)點(diǎn)與當(dāng)前起源圖節(jié)點(diǎn)之間的關(guān)聯(lián)，以此作為節(jié)點(diǎn)泛化的依據(jù)，結(jié)合用戶對(duì)過濾視圖中敏感節(jié)點(diǎn)泄露概率的要求，對(duì)起源圖進(jìn)行不同程度的泛化，達(dá)到隱私保護(hù)的目的。

該算法的基本思想如下：

（1）應(yīng)用word2vec算法思想，獲取已公開起源圖與當(dāng)前起源圖中的節(jié)點(diǎn)的向量化表示。

（2）計(jì)算同類型節(jié)點(diǎn)之間的相似度，應(yīng)用層次聚類算法獲取同類型節(jié)點(diǎn)，即實(shí)體節(jié)點(diǎn)、活動(dòng)節(jié)點(diǎn)以及代理節(jié)點(diǎn)的層次聚類樹。

（3）根據(jù)用戶指定的敏感節(jié)點(diǎn)和期望的敏感節(jié)點(diǎn)泄露概率值對(duì)起源圖進(jìn)行泛化。為了保證過濾視圖的溯源效用，選擇敏感節(jié)點(diǎn)所在的最小簇作為其泛化結(jié)果。

（4）每一次泛化完成后，計(jì)算敏感節(jié)點(diǎn)的實(shí)際泄露概率值，若實(shí)際值小于用戶的期望值，則完成泛化輸出過濾視圖，否則，更新泛化節(jié)點(diǎn)集，繼續(xù)泛化。

基于節(jié)點(diǎn)聚類的敏感節(jié)點(diǎn)隱私保護(hù)算法（PrivacyProtectionAlgorithmforSensitiveNodes， PPA）的偽代碼如下。

輸入：當(dāng)前起源圖PG，已公開起源圖集 PubPG＝｛PG1，PG2，…，PGl｝，敏感節(jié)點(diǎn)v，敏感節(jié)點(diǎn)泄露概率期望值pcexp

輸出：過濾視圖PV，敏感節(jié)點(diǎn)泄露概率實(shí)際值pcact

PPA算法包括節(jié)點(diǎn)聚類和節(jié)點(diǎn)泛化兩部分，因此，對(duì)算法的安全性分析從這兩部分進(jìn)行。

定理1已知樹 Ten，Tact，Tag是根據(jù)已公開起源圖PubPG和當(dāng)前起源圖PG，采用PPA算法分別得到的實(shí)體節(jié)點(diǎn)、活動(dòng)節(jié)點(diǎn)和代理節(jié)點(diǎn)的層次聚類樹，則攻擊者無法重建樹 Ten，Tact，Tag。

證明：層次聚類算法的選擇不唯一，且同一個(gè)層次聚類算法中，參數(shù)設(shè)置不同，如簇類中最大樣本數(shù)、簇類合并的臨界距離等，都會(huì)對(duì)層次聚類樹的形狀產(chǎn)生巨大的影響。攻擊者無法準(zhǔn)確獲得PPA算法中的參數(shù)設(shè)置，故無法重建PPA算法中生成的層次聚類樹Ten、Tact、Tag，也就無法依據(jù)層次聚類樹獲得泛化節(jié)點(diǎn)的準(zhǔn)確信息。

定理2已知圖PV是起源圖 PG＝｛V，E，Ph｝由PPA算法得到的過濾視圖，則當(dāng)攻擊者以已公開起源圖 PubPG＝｛PG1，PG2，…，PGl｝為背景知識(shí)時(shí)，從過濾視圖PV中識(shí)別出敏感節(jié)點(diǎn)的概率為1／K。

證明：由3.3節(jié)泛化節(jié)點(diǎn)集的計(jì)算可知，當(dāng)泛化至滿足用戶期望的敏感信息泄露概率時(shí)，被泛化節(jié)點(diǎn)數(shù)為K，即在過濾視圖PV中包含K個(gè)被泛化的節(jié)點(diǎn)，因此攻擊者從被泛化節(jié)點(diǎn)中識(shí)別出敏感節(jié)點(diǎn)的概率不大于1／K。

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

現(xiàn)有針對(duì)數(shù)據(jù)起源的隱私保護(hù)方法主要有3類：匿名［14］、抽象［15］以及刪除＋修復(fù)［6］。 其中匿名和抽象是主要針對(duì)敏感信息是節(jié)點(diǎn)的情況；而刪除＋修復(fù)針對(duì)的是敏感的間接依賴，即敏感信息是起源圖中節(jié)點(diǎn)間的依賴關(guān)系，該方法首先刪除一條敏感邊，然后添加一條邊來修復(fù)由于刪除邊誤斷的非敏感間接依賴。綜上，本文提出的PPA算法與經(jīng)典算法抽象和匿名相同，主要針對(duì)敏感信息是節(jié)點(diǎn)的情況，而刪除＋修復(fù)主要針對(duì)敏感信息是間接依賴的情況。因此，本節(jié)設(shè)計(jì)實(shí)驗(yàn)對(duì)比本文提出的PPA算法與經(jīng)典的匿名和抽象算法在應(yīng)用場(chǎng)景、性能和過濾視圖的效用方面的差異，最后分析實(shí)驗(yàn)結(jié)果，說明本算法的優(yōu)勢(shì)。

為了驗(yàn)證本文提出的PPA隱私保護(hù)算法的各項(xiàng)性能，在實(shí)驗(yàn)部分選取了3個(gè)數(shù)據(jù)集進(jìn)行測(cè)試，主要進(jìn)行了兩方面的實(shí)驗(yàn)：（1）對(duì)自身算法進(jìn)行性能分析；（2）本文分別以3類數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)，將本文算法與抽象和匿名經(jīng)典算法進(jìn)行對(duì)比分析。

本文所提算法和對(duì)比算法的實(shí)驗(yàn)環(huán)境為DELL Inspiron5598 筆記本電腦，Intel Core i5?10210U 2.11 GHz，8 GB內(nèi)存，Window10的64位操作系統(tǒng)，所有代碼用Python語言實(shí)現(xiàn)。

5.1 數(shù)據(jù)集

所選數(shù)據(jù)集是來自W3C起源數(shù)據(jù)模型的公開起源圖數(shù)據(jù)集，分別為來自ProvStore的SmartHome、Article?prov和 Final。 數(shù)據(jù)集的詳細(xì)情況如表 1所示。

表1 數(shù)據(jù)集詳細(xì)情況

5.2 評(píng)價(jià)標(biāo)準(zhǔn)

數(shù)據(jù)溯源是起源圖的基本用途，它是根據(jù)已知起源圖，對(duì)可能影響特定數(shù)據(jù)節(jié)點(diǎn)當(dāng)前狀態(tài)的歷史信息進(jìn)行追溯分析的過程［21］。溯源效用是用來定量衡量過濾視圖滿足用戶溯源需求的程度，進(jìn)而評(píng)價(jià)不同的隱私保護(hù)技術(shù)優(yōu)劣的一個(gè)重要指標(biāo)［22］。

定義13（溯源結(jié)果ΔPG（v0）） 起源圖PG＝（V，E， Ph）中，對(duì)于任意 v0∈V，若存在 vi∈V 使 Ph（v0，vi）∈Ph 或＜v0， vi＞∈E， i＝1， 2， …， m，稱節(jié)點(diǎn)vi為節(jié)點(diǎn) v0的歷史節(jié)點(diǎn)， ΔPG（v0）＝｛vi｜Ph（v0，vi） ∈Ph或 ＜v0，vi＞∈E｝稱為節(jié)點(diǎn)u的溯源結(jié)果。

本文采用文獻(xiàn)［23］中提出的效用評(píng)估模型，利用馬爾科夫鏈建模歷史節(jié)點(diǎn)通過溯源路徑對(duì)溯源起點(diǎn)v0的影響，得到歷史節(jié)點(diǎn)影響v0的因果信度分布，如式（5）所示。

其中，ΔPG（v0）為溯源起點(diǎn) v0的溯源結(jié)果， Iv0PG（vi） 表示起點(diǎn)v0的溯源結(jié)果集中節(jié)點(diǎn)vi的置信度向量。進(jìn)而可利用相對(duì)熵計(jì)算原起源圖PG與過濾視圖PV的因果信度分布之間的相似度，如式（6）所示。

相對(duì)熵 DKL（KPG，v‖KPV，v） 的值越大，則過濾視圖PV與原始視圖PG之間的差異就越大。本文用U ＝e－DKL來表征效用，其取值范圍為［0，1］。 溯源效用U與相對(duì)熵的值成反比，即原始起源圖與過濾視圖之間的差異越小，溯源效用越高。

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

本文的實(shí)驗(yàn)?zāi)康氖菍?duì)所提出的安全保護(hù)方法進(jìn)行實(shí)證和分析。通過與現(xiàn)有的方法作對(duì)比，說明本文方法的優(yōu)勢(shì)。

5.3.1 應(yīng)用場(chǎng)景對(duì)比

對(duì)比本文提出的PPA算法與抽象和匿名兩種經(jīng)典算法在應(yīng)用場(chǎng)景上的差異，如表2所示。本文提出的PPA方法和已有的匿名和抽象經(jīng)典算法相比，匿名和抽象兩種方法無法滿足用戶定制發(fā)布的需求。當(dāng)需要對(duì)一個(gè)或多個(gè)敏感節(jié)點(diǎn)進(jìn)行隱私保護(hù)時(shí)，匿名方法會(huì)直接將節(jié)點(diǎn)信息置空，這種做法會(huì)使數(shù)據(jù)損失度較大；抽象方法會(huì)將敏感節(jié)點(diǎn)連同其周圍的非敏感節(jié)點(diǎn)一并隱藏，無法滿足用戶保留非敏感節(jié)點(diǎn)的需求，無法定制發(fā)布。

表2 PPA與匿名、抽象的應(yīng)用場(chǎng)景比較

5.3.2 算法性能對(duì)比實(shí)驗(yàn)

采用 SmartHome、Article?prov 和 Final三個(gè)數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)，每一次隨機(jī)指定1個(gè)敏感節(jié)點(diǎn)，使用3個(gè)算法各自重復(fù)執(zhí)行1 000次，對(duì)比3個(gè)算法最終生成過濾視圖的時(shí)間消耗，結(jié)果如圖8所示。抽象算法的時(shí)間消耗要高于本文的PPA算法和匿名算法，這是因?yàn)槌橄蠓椒ㄐ枰啻伪闅v起源圖，獲取敏感節(jié)點(diǎn)周圍的結(jié)構(gòu)信息，進(jìn)而選取和敏感節(jié)點(diǎn)合并抽象的節(jié)點(diǎn)，然后再將所選節(jié)點(diǎn)抽象后與起源圖中其他節(jié)點(diǎn)相連，時(shí)間消耗較大。同時(shí)實(shí)驗(yàn)結(jié)果顯示，在不同的數(shù)據(jù)集上，PPA算法與匿名算法的時(shí)間消耗相差無幾，但匿名算法的時(shí)間消耗略低于本文的PPA算法，這是因?yàn)槟涿惴ㄖ皇菍⒚舾泄?jié)點(diǎn)內(nèi)的數(shù)據(jù)置空，而不需要遍歷起源圖。

圖8 不同數(shù)據(jù)集上運(yùn)行時(shí)間對(duì)比

另外，當(dāng)起源圖中敏感節(jié)點(diǎn)的數(shù)量不同時(shí)，過濾視圖的溯源效用也會(huì)產(chǎn)生較大的差異。由于起源圖節(jié)點(diǎn)數(shù)目的限制以及領(lǐng)域?qū)＜业慕?jīng)驗(yàn)，起源圖中敏感節(jié)點(diǎn)的數(shù)量一般不超過10個(gè)，因此本文選取Article?prov數(shù)據(jù)集為例，比較本文算法與匿名和抽象算法在性能上的差異，結(jié)果如圖9所示。

圖9 性能對(duì)比結(jié)果

由圖9可知，抽象算法由于需要多次選取抽象多個(gè)節(jié)點(diǎn)，消耗時(shí)間最多；匿名算法和本文所提算法總體來說差異較小，但本文算法所需的運(yùn)行時(shí)間平均略低于匿名算法。

綜合分析圖8和圖9可知，當(dāng)敏感節(jié)點(diǎn)的數(shù)量較少時(shí)，PPA算法、抽象算法和匿名算法在性能上的差異很小，但當(dāng)起源圖中敏感節(jié)點(diǎn)的數(shù)量較多時(shí)，本文所提的PPA算法更具優(yōu)勢(shì)。5.3.3 過濾視圖效用對(duì)比實(shí)驗(yàn)

由不同敏感節(jié)點(diǎn)下的算法性能實(shí)驗(yàn)可知，當(dāng)敏感節(jié)點(diǎn)數(shù)為1、2、3時(shí)，3種算法的運(yùn)行時(shí)間大致相同。在算法運(yùn)行時(shí)間大致相同的情況下，本文設(shè)計(jì)實(shí)驗(yàn) 1、2、3，分別為選取數(shù)據(jù)集 SmartHome、Final和Article?prov為實(shí)驗(yàn)數(shù)據(jù)，采用本文提出的PPA方法、匿名和抽象3種隱私保護(hù)方法，當(dāng)敏感節(jié)點(diǎn)的數(shù)量分別為1、2、3時(shí)的過濾視圖的效用結(jié)果對(duì)比，如圖10所示。由圖10可知本文提出的PPA方法與匿名和抽象方法相比，能夠有效地保證過濾視圖的溯源效用。與抽象相比，本文方法能夠在隱藏敏感信息的基礎(chǔ)上不改變起源圖的結(jié)構(gòu)，抽象方法會(huì)將起源圖中的敏感節(jié)點(diǎn)周圍的非敏感節(jié)點(diǎn)與敏感節(jié)點(diǎn)一并隱藏，降低過濾視圖的溯源效用；與匿名相比，匿名雖然也不改變起源圖的結(jié)構(gòu)，但匿名會(huì)把敏感節(jié)點(diǎn)的信息完全置空，這樣會(huì)造成信息損失，當(dāng)起源圖中的敏感節(jié)點(diǎn)數(shù)量越多時(shí)，信息損失就越大，過濾視圖的溯源效用就越低?？偟膩碚f，本文提出的隱私保護(hù)方法與抽象和匿名相比，能夠更加有效地保持過濾視圖的溯源效用。

圖10 過濾視圖效用對(duì)比結(jié)果

6 結(jié)束語

本文針對(duì)現(xiàn)有數(shù)據(jù)起源隱私保護(hù)方法未考慮已公開起源圖對(duì)當(dāng)前起源圖的關(guān)聯(lián)推理的現(xiàn)狀，提出了基于節(jié)點(diǎn)聚類的數(shù)據(jù)起源安全保護(hù)方法。實(shí)驗(yàn)結(jié)果表明，本文提出的方法能夠滿足數(shù)據(jù)起源發(fā)布者不同的發(fā)布需求，而且能夠在保護(hù)敏感數(shù)據(jù)的同時(shí)更好地保持過濾視圖的溯源效用。未來工作包括本隱私保護(hù)方法的優(yōu)化，研究安全與效用能夠達(dá)到平衡的綜合過濾方法。