基于節(jié)點聚類的數(shù)據(jù)起源安全方法研究

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

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

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

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

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

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

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

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

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

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

數(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é)點主要有實體節(jié)點，如節(jié)點e3，e4；活動節(jié)點，如 p2，p3；代理節(jié)點，如 L1。 起源圖中的依賴關(guān)系有 7種，即生成（generation）、使用（usage）、派生（derivation）、通信（communication）、歸屬（attribution）、關(guān)聯(lián)（association）和委托（delegation）［9－10］。 不同類型的邊代表不同節(jié)點之間的依賴關(guān)系，例如使用邊是由實體節(jié)點指向活動節(jié)點，記作used；產(chǎn)生邊為活動節(jié)點指向?qū)嶓w節(jié)點，記作wgb；代理節(jié)點與活動節(jié)點之間相連的邊為關(guān)聯(lián)邊，記作waw。

圖1 某藥品配方起源圖

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

定義1（起源圖 PG＝（V，E，Ph））節(jié)點 V＝｛v1，v2，…，vn｝表示起源圖 PG 中的 n個節(jié)點的集合；邊 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針對敏感信息SI采用過濾策略f進行過濾所得到的起源圖。

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

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

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

1.2 層次聚類

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

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

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

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

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

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

圖2 年齡層次聚類樹

1.3 節(jié)點泛化

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

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

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

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

2.1 安全威脅

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

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

圖3 原起源圖子圖PG

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

圖5 已公開起源圖子圖PGi

2.2 推理方式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖6 word2vec算法示例

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

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

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

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

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

圖7 簡單起源圖

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

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

3.3 泛化節(jié)點集的計算

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

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

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

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

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

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

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

4 敏感節(jié)點隱私保護算法

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

該算法的基本思想如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.2 評價標(biāo)準(zhǔn)

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

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

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

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

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

5.3 實驗方案與結(jié)果分析

本文的實驗?zāi)康氖菍λ岢龅陌踩Ｗo方法進行實證和分析。通過與現(xiàn)有的方法作對比，說明本文方法的優(yōu)勢。

5.3.1 應(yīng)用場景對比

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

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

5.3.2 算法性能對比實驗

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

圖8 不同數(shù)據(jù)集上運行時間對比

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

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

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

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

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

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

6 結(jié)束語

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