孫連山，陳秀婷，馬勝天

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

在信息時代，時刻有成千上萬條數(shù)據(jù)產(chǎn)生，這些數(shù)據(jù)對于各類組織和機(jī)構(gòu)制定決策至關(guān)重要。但數(shù)據(jù)來源多樣，人們在使用這些數(shù)據(jù)之前須驗證數(shù)據(jù)的質(zhì)量和可信性，可通過數(shù)據(jù)起源來實(shí)現(xiàn)該需求[1]。數(shù)據(jù)起源（Data Provenance）記錄數(shù)據(jù)的歷史狀態(tài)和變化過程[2]，通常呈現(xiàn)為有向無環(huán)圖，簡稱起源圖[3]。起源圖基本結(jié)構(gòu)包括由邊相連的數(shù)據(jù)實(shí)體節(jié)點(diǎn)和活動節(jié)點(diǎn)，其中節(jié)點(diǎn)代表數(shù)據(jù)歷史變化的原子過程[4-6]，邊表示歷史數(shù)據(jù)之間的因果關(guān)系。用戶在使用數(shù)據(jù)制定決策之前，可沿起源圖的依賴路徑進(jìn)行數(shù)據(jù)溯源[7]，即根據(jù)起源圖驗證數(shù)據(jù)的來源和演化過程，增強(qiáng)數(shù)據(jù)的可信性[8]。顯然，數(shù)據(jù)溯源依賴于起源圖的連通性，即起源圖不包含孤立節(jié)點(diǎn)。

起源圖中可能含有多種敏感信息，敏感信息泄露可能造成嚴(yán)重的后果，如核心技術(shù)設(shè)計圖稿、用戶身份等信息的泄露會對公司造成利益損失。因此，為保證起源安全，在發(fā)布起源圖之前需對其過濾，隱藏其中的敏感信息[9]。

起源過濾是在不破壞起源圖連通性的前提下，對節(jié)點(diǎn)、邊或間接依賴進(jìn)行改造，從而得到安全的過濾視圖的新興技術(shù)[10]。起源過濾不但應(yīng)滿足起源安全，同時還應(yīng)保持溯源效用，即能夠滿足用戶的溯源需求。起源安全表示惡意用戶根據(jù)已發(fā)布的過濾視圖發(fā)現(xiàn)或推斷被隱藏的敏感信息的難度[11]。溯源效用表示起源過濾前后，原始起源圖中的溯源語義在過濾視圖中的保留程度。

現(xiàn)有起源過濾研究大多關(guān)注起源圖中敏感節(jié)點(diǎn)的過濾。例如，Missier 等[12]提出ProvAbs 過濾方法，用抽象的實(shí)體或活動節(jié)點(diǎn)代替一組敏感節(jié)點(diǎn)集合，但該方法同時將敏感節(jié)點(diǎn)周圍的非敏感節(jié)點(diǎn)一并隱藏，降低了過濾視圖的效用；Blaustein 等[13]提出起源過濾方法Surrogate，采用抽象原理，用不同敏感級別的代理節(jié)點(diǎn)和邊替換敏感信息，以提高過濾視圖的效用。Nagy等[14]提出ProvS過濾方法，采用匿名機(jī)制過濾敏感節(jié)點(diǎn)，來提高過濾視圖的安全與效用指標(biāo)。Wu等[15]提出一種綜合考慮起源圖敏感節(jié)點(diǎn)屬性以及輸入輸出映射關(guān)系的隱私保護(hù)方法GPPub，以保證起源圖的效用和安全；事實(shí)上，直接依賴（邊）和間接依賴均可能蘊(yùn)含敏感的起源語義。王藝星等[16]提出一種高效用起源過濾機(jī)制，解決敏感邊的過濾問題。孫連山等[17]提出一種面向間接依賴的數(shù)據(jù)起源過濾方法，通過刪除邊斷開敏感間接依賴路徑以及添加不確定的通信邊和派生邊修復(fù)被誤斷的間接依賴。上述研究均采用“刪除+修復(fù)”的方法實(shí)現(xiàn)依賴關(guān)系過濾，但修復(fù)過程中引入了不確定的通信邊和派生邊，違反了起源圖的基本結(jié)構(gòu)約束。部分研究者甚至明確地將這兩類邊當(dāng)作非法結(jié)構(gòu)[18]。上述方法雖然在一定程度上提升了溯源效用，但溯源效用仍然不高。

總之，現(xiàn)有的起源過濾研究大多關(guān)注敏感節(jié)點(diǎn)和邊的過濾，對間接依賴的過濾研究較少，且已有的間接依賴過濾方法違反了起源圖的基本結(jié)構(gòu)約束，并且過濾視圖的溯源效用不高。本文針對上述問題，首先分析并證明引入不確定的使用邊修復(fù)被誤斷的間接依賴的可行性，進(jìn)而提出一種基于不確定使用邊的間接依賴過濾方法，該方法一方面滿足了過濾視圖的基本結(jié)構(gòu)約束，另一方面保持了過濾視圖的溯源效用。

圖1 部分文檔起源圖PG

1 相關(guān)概念和問題描述

本章形式化定義起源圖的相關(guān)概念，并介紹間接依賴過濾問題及基本的間接依賴過濾策略。

數(shù)據(jù)起源記錄數(shù)據(jù)的歷史演變信息，表現(xiàn)為有向無環(huán)圖，又稱起源圖。如圖1 所示，記錄文檔File4的生成過程，其中橢圓形表示實(shí)體，如Word、File1等，矩形表示使用或產(chǎn)生實(shí)體的處理過程，如Compose、Revise等。節(jié)點(diǎn)之間的關(guān)系包括實(shí)體與活動之間的產(chǎn)生（generation）關(guān)系和活動與實(shí)體之間的使用（usage）關(guān)系等。

為方便論述，起源圖相關(guān)概念可形式化地定義如下。

定義1 起源圖PG=(V,E,Ph)。

V={v1,v2,…,vn} 表示圖PG中有n個節(jié)點(diǎn)；邊E={ei|ei=＜u,v＞,u∈V,v∈V,i=1,2,…,m} 表示圖PG中有m條有向邊，邊＜u,v＞表示v是u的直接產(chǎn)生原因；路徑集Ph={phi|phi=(u,v),u∈V,v∈V,i=1,2,…,k}表示圖PG中有k條路徑。

定義2 過濾視圖PV=f(PG,SI)。

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

定義3 溯源結(jié)果ΔPG(u)。

起源圖PG=(V,E,Ph)，對于任意的u∈V，若存在vi∈V使得ph(u,vi)∈Ph或＜u,vi＞∈E,i=1,2,…,m，稱vi為u的歷史節(jié)點(diǎn)，ΔPG(u)={vi|ph(u,vi)∈Ph或＜u,vi＞∈E}稱為u的溯源結(jié)果。如圖1所示，ΔPG(File2)={Revise,File1,Compose,Word}.

定義4 溯源效用U(PG,PV,v0)。

U表示起源過濾前后，原始起源圖PG 的溯源語義在過濾視圖PV的保留程度。本文采用文獻(xiàn)[19]的效用評估模型，利用馬爾科夫鏈建模歷史節(jié)點(diǎn)通過溯源路徑對溯源起點(diǎn)v0的影響，得到歷史節(jié)點(diǎn)影響v0的因果信度分布，如式（1）所示：

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

相對熵KLD=DKL(KPG,v0||KPV,v0)越大，過濾視圖和原始視圖的差異也越大。本文用U=e-KLD表征效用，其取值范圍為[0，1]。溯源效用U與相對熵的大小成反比，即過濾視圖和原始視圖的差異越小，溯源效用U越高。

定義5 起源安全S(PG,PV,SI)。

S表示過濾視圖PV=(V′,E′,Ph′)對于原始起源圖PG=(V,E,Ph)中的敏感信息SI的隱藏程度。本文借鑒Blaustein 等[13]提出的不透明度（opacity）來評估過濾視圖的安全。不透明度是衡量攻擊者推理出過濾視圖不存在而原起源圖中存在的一條邊所面臨的難度，由于推理出邊的存在可間接推理出間接依賴的存在，因此可用不透明度表征敏感間接依賴的安全，如式（3）所示：

其中節(jié)點(diǎn)n1,n2∈V,為其在PV 中對應(yīng)的節(jié)點(diǎn)，V′、E′為過濾視圖PV中的節(jié)點(diǎn)集和邊集，θ主要依賴于兩個因素FP與pc，如式（4）所示：

其中FP為攻擊者對節(jié)點(diǎn)的關(guān)注度，取值范圍為[0，1]，對度為1的節(jié)點(diǎn)關(guān)注度較大，pc為節(jié)點(diǎn)n1′,n2′在原起源圖中存在邊的可能性，取值范圍為[0，1]。通過過濾視圖PV推斷出PG中存在邊的可能性pc越小，敏感間接依賴的不透明度越大，起源安全程度越高。

間接依賴P(u,v)為起源圖中有路徑存在但無邊直接相連的節(jié)點(diǎn)對，蘊(yùn)含豐富的因果語義，可用于追溯影響當(dāng)前數(shù)據(jù)對象的歷史節(jié)點(diǎn)數(shù)據(jù)。起源圖中路徑長度大于1 的任意節(jié)點(diǎn)對之間均存在間接依賴關(guān)系。間接依賴同樣會存在敏感信息。

定義6 間接依賴過濾。

間接依賴過濾要求在滿足過濾約束的基礎(chǔ)上斷開P(u,v)的依賴關(guān)系。研究者將間接依賴過濾問題形式化地表述為以下帶約束目標(biāo)優(yōu)化問題[17]，如式（5）所示：

其中，f(PG,P(u,v))為過濾策略f對起源圖PG中敏感間接依賴P(u,v)過濾所得過濾視圖，V′和Ph′分別為過濾視圖中的邊集和路徑集，過濾策略f應(yīng)保證敏感間接依賴被隱藏，即過濾視圖應(yīng)具有一定的安全性。目標(biāo)函數(shù)表示使用過濾策略f過濾敏感間接依賴，使過濾視圖在保證安全的前提下，效用達(dá)到最大。

現(xiàn)有間接依賴過濾SID（Sanitizing Indirect Dependency）[17]算法采用“刪除+修復(fù)”的過濾策略，在刪除邊的基礎(chǔ)上，引入不確定的通信邊或派生邊進(jìn)行修復(fù)，最終在所有過濾視圖中通過計算選擇出其中效用最高的過濾視圖。如圖2所示，若敏感間接依賴為P(en1,en3)，則可以先刪除邊＜ac1,en2＞或者＜en2,ac2＞，再添加不確定的通信邊＜ac0,ac3＞進(jìn)行修復(fù)。該方法闡明了引入不確定邊提高過濾視圖效用的可行性，但該方法引入了不確定的通信邊和派生邊，違反了起源圖的基本結(jié)構(gòu)約束[18]，實(shí)用性不高。

本文在課題組前期工作的基礎(chǔ)上，進(jìn)一步擴(kuò)展“刪除+修復(fù)”的方法，研究一種基于不確定使用邊的間接依賴過濾方法，在遵守起源圖基本結(jié)構(gòu)約束的前提下，實(shí)現(xiàn)間接依賴過濾并保持過濾視圖的溯源效用。

2 間接依賴過濾

2.1 基本原理

定義7 不確定的使用邊。

起源圖PG=(V,E,Ph) ，m∈V，n∈ΔPG(m) ，m為活動節(jié)點(diǎn)，n為實(shí)體節(jié)點(diǎn)，＜m,n＞?E，則＜m,n＞為可引入過濾視圖的不確定的使用邊。

如圖2，可通過刪除一條原始的使用邊＜ac1,en2＞隱藏敏感間接依賴P(en1,en3)，但同時某些非敏感間接依賴的連通路徑也可能被中斷，如P(ac0,en2)。此時可通過添加不確定的使用邊＜ac0,en2＞修復(fù)非敏感間接依賴P(ac0,en2)等。

分析發(fā)現(xiàn)，在刪除邊斷開敏感間接依賴的過程中，通常應(yīng)選擇使用邊作為被刪除的邊。如圖2所示，若通過刪除產(chǎn)生邊＜en2,ac2＞隱藏敏感間接依賴P(en1,en3)，則可能無法引入不確定的使用邊修復(fù)某些節(jié)點(diǎn)到活動節(jié)點(diǎn)ac2的非敏感間接依賴，如P(en0,ac2)和P(ac0,ac2)等。這時，也不能直接引入＜en0,ac2＞等不確定的產(chǎn)生邊修復(fù)相關(guān)的非敏感間接依賴，否則將違反起源圖中的實(shí)體節(jié)點(diǎn)不能由兩個活動節(jié)點(diǎn)生成的基本結(jié)構(gòu)約束[18]。因此不宜通過刪除產(chǎn)生邊來中斷敏感間接依賴，也不宜引入不確定的產(chǎn)生邊修復(fù)被誤斷的非敏感間接依賴。

圖2 起源圖示例

事實(shí)上，起源圖是活動類型節(jié)點(diǎn)和實(shí)體類型節(jié)點(diǎn)構(gòu)成的二部圖，則對任意一個被誤斷的非敏感間接依賴P(m,n)來說，均可遵循如下規(guī)則，引入恰當(dāng)?shù)牟淮_定的使用邊對其進(jìn)行修復(fù)。

（1）若m是活動節(jié)點(diǎn)，而n是實(shí)體節(jié)點(diǎn)，則可直接引入不確定使用邊＜m,n＞修復(fù)P(m,n)；

（2）若m,n均為實(shí)體節(jié)點(diǎn)，則可引入不確定使用邊＜pam,n＞修復(fù)P(m,n)的連通性，其中pam∈ΔPG(m)；

（3）若m,n均為活動節(jié)點(diǎn)，則可引入不確定使用邊＜m,sen＞修復(fù)P(m,n)的連通性，其中n∈ΔPG(sen)且sen∈ΔPG(m)；

（4）若m是實(shí)體節(jié)點(diǎn)且n是活動節(jié)點(diǎn)，則可引入不確定使用邊＜pam,sen＞修復(fù)P(m,n)的連通性，其中n∈ΔPG(sen) 且sen∈ΔPG(m)。

可應(yīng)用上述規(guī)則之一修復(fù)的非敏感間接依賴稱為可修復(fù)的間接依賴，否則稱為不可修復(fù)的間接依賴。容易證明所有長度等于2 的非敏感間接依賴均是不可修復(fù)的。此外，所有引入的不確定使用邊的兩個端點(diǎn)不能同時出現(xiàn)在某一條敏感間接依賴的連通路徑上，即引入不確定的使用邊不應(yīng)恢復(fù)被中斷的敏感間接依賴。

實(shí)際過濾時，可引入不同的不確定的使用邊修復(fù)一對非敏感間接依賴；而引入一條不確定的使用邊往往能夠修復(fù)多對非敏感間接依賴。因此，為了避免對起源圖的過度改造，通常不為修復(fù)每一對非敏感間接依賴而專門引入一條新的不確定的使用邊。若將所有需要修復(fù)的非敏感間接依賴的集合記為SP，將通過引入不確定的使用邊e而修復(fù)的間接依賴集合記為R(e)，R(e)?SP，被引入的所有不確定使用邊的集合記為UE。本文將探索最小代價法，引入盡可能少的不確定使用邊修復(fù)盡可能多的非敏感間接依賴，即求使得|UE|最小的集合，滿足SP??R(e),e∈UE且R(ei)?R(ej)，，ei∈UE，ej∈UE。

定理假設(shè)刪除邊后所得過濾視圖為PV，PV中任意兩對待修復(fù)的非敏感間接依賴P(a,b)和P(m,n)，若m∈ΔPV(a)且b∈ΔPV(n)，若存在不確定使用邊e，滿足P(m,n)∈R(e)，則必有P(a,b)∈R(e)。

證明令e=＜s,t＞，因為P(m,n)∈R(e)，即s∈ΔPV(m)，n∈ΔPV(t) ；一 方 面，因 為m∈ΔPV(a) ，則ΔPV(m)?ΔPV(a)，所以s∈ΔPV(a)；另一方面，因為b∈ΔPV(n)且n∈ΔPV(t) ，則b∈ΔPV(t)；綜合兩個方面的結(jié)論可知，s∈ΔPV(a)且v∈ΔPV(t)，因此P(a,b)∈R(e)。證畢。

定理表明引入不確定的使用邊修復(fù)間接依賴具有傳遞性。

推論若所有需要修復(fù)的非敏感間接依賴集合為SP，若存在P(m,n)∈SP，且對任意非敏感間接依賴P(vi,vj)∈SP，均滿足m∈ΔPG(vi)且vj∈ΔPG(n)，則能夠修復(fù)P(m,n)的不確定的使用邊e必定能夠修復(fù)所有P(vi,vj)，此時={e}。

該定理及推論是設(shè)計過濾策略的理論基礎(chǔ)。容易證明在過濾視圖中引入不確定的使用邊除了滿足定理所述的間接依賴修復(fù)的傳遞性之外，還能夠保證過濾視圖符合“連通”“無環(huán)”“無假依賴”等典型的起源結(jié)構(gòu)約束[18]。

2.2 過濾策略

本節(jié)提出一種基于不確定使用邊的間接依賴過濾策略，首先刪除敏感路徑中的某條使用邊，其次添加若干不確定的使用邊修復(fù)起源圖的連通性，在滿足基本結(jié)構(gòu)約束的前提下提升溯源效用。

2.2.1 刪除

為了減少不可修復(fù)的非敏感間接依賴數(shù)量，本文選擇使用邊進(jìn)行刪除，同時為了在修復(fù)階段減少不確定的使用邊所代替的路徑長度，選取敏感路徑中距離敏感間接依賴節(jié)點(diǎn)u最近的使用邊＜s,t＞作為刪除邊，從而斷開敏感間接依賴。

2.2.2 修復(fù)

根據(jù)定義4，為降低過濾視圖與原起源圖因果信度分布的相對熵，保持過濾視圖的溯源效用，對于?vi∈ΔPG(s)，s為刪除邊的端點(diǎn)，需修復(fù)由于刪除邊而被誤斷的非敏感間接依賴P(v0,vi)，某些情況下，為滿足起源結(jié)構(gòu)約束，還需修復(fù)P(s,vj)，vj∈ΔPG(t)-ph(u,v)，即SP={P(v0,vi)?P(s,vj)，vi∈ΔPG(s)，vj∈ΔPG(t)-ph(u,v)}，并且需要盡可能地減少不確定的使用邊所代替的路徑長度。根據(jù)定理及推論，可用一條或多條不確定的使用邊修復(fù)非敏感間接依賴集合SP，在滿足起源圖基本結(jié)構(gòu)的同時提升溯源效用，具體過濾策略如表1所示。表中＜s,t＞為離敏感節(jié)點(diǎn)u最近的使用邊，節(jié)點(diǎn)s、t是邊的兩端點(diǎn)，sau為敏感間接依賴P(u,v)中離u最近的后果活動節(jié)點(diǎn)，sau∈ph(v0,u)，pet為距離s最近的前因?qū)嶓w節(jié)點(diǎn)，且pet∈ΔPG(t)-ph(u,v)。

表1 間接依賴過濾策略

如表1 所示，修復(fù)時首先判斷節(jié)點(diǎn)s在原起源圖中的出度是否大于1，若大于1，即節(jié)點(diǎn)s使用了k(k＞1)個實(shí)體節(jié)點(diǎn)，僅需添加不確定的使用邊修復(fù)sau與實(shí)體節(jié)點(diǎn)t，使得={＜sau,t＞}，從而修復(fù)溯源起點(diǎn)與圖中任意節(jié)點(diǎn)之間的間接依賴關(guān)系且過濾視圖滿足基本結(jié)構(gòu)；若節(jié)點(diǎn)s在原起源圖的出度等于1，則說明s僅使用了一個實(shí)體節(jié)點(diǎn)，即已刪除邊的端點(diǎn)t，此時首先添加不確定的使用邊＜sau,t＞，然后添加不確定的使用邊＜s,pet＞進(jìn)行修復(fù)，即={＜sau,t＞,＜s,pet＞} 。實(shí)際起源圖中可能出現(xiàn)sau或pet不存在的情況，該情況為不可修復(fù)的間接依賴，需要放棄修復(fù)。

如圖2 中敏感間接依賴為P(en1,en3)，首先刪除邊＜ac1,en2＞，由于ac1的出度為1，距離ac1最近的非敏感前因節(jié)點(diǎn)是en6，因此需要在修復(fù)＜ac0,en2＞的基礎(chǔ)上修復(fù)＜ac1,en6＞，即={＜ac0,en2＞,＜ac1,en6＞}。所得過濾視圖如圖3所示。

圖3 過濾視圖

上述過濾策略僅適用于敏感間接依賴對應(yīng)一條路徑的情況。而實(shí)際起源圖中，一對敏感間接依賴可能會對應(yīng)多條路徑。根據(jù)這些路徑是否存在公共邊，敏感間接依賴的對應(yīng)路徑可分為獨(dú)立型和共有型兩類。對于多路徑獨(dú)立型間接依賴，首先將兩條路徑分別進(jìn)行單路徑間接依賴過濾，然后對單路徑過濾得到的策略進(jìn)行笛卡爾積運(yùn)算；對于多路徑共有型間接依賴，首先記錄所有公共使用邊出現(xiàn)的次數(shù)，找到出現(xiàn)次數(shù)最多的公共使用邊并將其刪除，然后根據(jù)單路徑過濾中的修復(fù)方式對其進(jìn)行修復(fù)。

如圖4所示，若敏感間接依賴是P(ac2,ac3)，則該節(jié)點(diǎn)對之間存在兩條路徑，且互相獨(dú)立，為多路徑獨(dú)立型間接依賴過濾，在刪除邊＜ac2,en3＞的同時也要將＜ac2,en7＞一并刪除，然后修復(fù)＜ac1,en3＞，＜ac1,en7＞和＜ac2,en4＞；若敏感間接依賴是＜ac1,ac3＞，兩節(jié)點(diǎn)之間有兩條路徑，且存在1 條公共使用邊＜ac1,en2＞，此時只需刪除＜ac1,en2＞，然后修復(fù)＜ac0,en2＞和＜ac1,en4＞即可。

圖4 起源圖示例

3 間接依賴過濾算法

本章介紹單路徑間接依賴過濾算法，可根據(jù)需要多次調(diào)用該算法實(shí)現(xiàn)多路徑間接依賴過濾。假設(shè)原始起源圖為PG，過濾視圖為PV，P(u,v)為敏感間接依賴。單路徑間接依賴過濾算法（SanitizingIndirectDepen-dencyforSinglePath）如下：

算法1 單路徑間接依賴過濾

輸入：PG,u,v

輸出：PV

1.SID(PG,u,v)

2.PV=PG//初始化過濾視圖

3.ph(u,v)=getPath(PG,u,v) //獲取原起源圖中u,v之間的路徑

4.sau=getUFirstAct(u)//獲取u的最近后果活動節(jié)點(diǎn)

5.PE(t)=ΔPG(t)-ph(u,v) //獲取t的非敏感前因節(jié)點(diǎn)集合

6.minLength1=MAX//初始化最小長度

7. foreach ＜sj,tj＞∈ph(u,v)do

8.m=getLabel(PG,＜sj,tj＞)//獲?。約j,tj＞的類型

9. ifm=“u”then //判斷是否是使用邊

10.phLength(sau,tj)=getPathLength(PG,sau,tj)//獲取PG中sau,tj之間的路徑長度

11. ifminLength1 ＞phLength(sau,tj)then

12.minLength1=phLength(sau,tj)//確定最短路徑

13. ＜s,t＞=＜sj,tj＞

14. endif

15. endif

16. endfor

17.delEdge(PV,＜s,t＞) //刪除邊＜s,t＞

18.Outdegree=getOutgoingDegreeOf(s)//獲取s的出度

19. ifoutdegree＞1 then

20. addEdge(PV,＜sau,t＞)//修復(fù)被斷開的非敏感間接依賴

21. else

22.minLength2=MAX//初始化最小長度

23. foreachpetk∈PE(t) do

24.phLength(s,petk)=getPathLength(PG,s,petk)//獲取PG中s，petk之間的路徑長度

25. if minLength 2 ＞phLength(s,petk)then

26.minLength2=phLength(s,petk)//確定最短路徑

27.pet=petk

28. endif

29. endfor

30. addEdge(PV,＜sau,t＞)

31. addEdge(PV,＜s,pet＞)

32. endif

圖5 隨機(jī)生成起源圖示例

33. returnPV

34. endSID

算法1 中第2、3 行初始化過濾視圖，并獲取原起源圖中的路徑；第4、5行獲取敏感間接依賴節(jié)點(diǎn)u的后果活動節(jié)點(diǎn)與t的非敏感前因?qū)嶓w節(jié)點(diǎn)集合；第6～32行獲取敏感路徑中的使用邊將其刪除，并根據(jù)所刪除邊的端點(diǎn)的度的大小進(jìn)行不同的修復(fù)；其中第6～17 行判斷敏感路徑中的邊是否為距離sau最近的使用邊，然后將其刪除；第18～32行在不同情況下修復(fù)刪除邊后所斷開的非敏感間接依賴。

算法1 在遍歷敏感間接依賴路徑中的邊進(jìn)行刪除時會有所耗時，若敏感間接依賴路徑中存在n條邊，需要循環(huán)執(zhí)行n次尋找最短路徑操作；而在計算路徑長度phLength的時間復(fù)雜度為O(n)，因此算法1 的時間復(fù)雜度為O(n2)。該算法僅需要通過尋找最短路徑來確定所要刪除的邊，確定了所要刪除的邊便可以間接確定要修復(fù)的不確定使用邊的端點(diǎn)，因此該算法可在耗時較少的情況下完成對敏感間接依賴的過濾。

4 實(shí)驗及結(jié)果分析

本章首先介紹過濾算法所使用的數(shù)據(jù)集、實(shí)驗環(huán)境和參數(shù)設(shè)置，其次設(shè)計不同實(shí)驗對比本文算法與經(jīng)典的起源過濾算法所得過濾視圖的效用與安全，以及算法性能。最后分析實(shí)驗結(jié)果，說明本文算法在滿足結(jié)構(gòu)約束的同時保持過濾視圖溯源效用的優(yōu)勢。

4.1 實(shí)驗整體設(shè)置

本文實(shí)驗采用印第安納大學(xué)發(fā)布的Gene、Ncfs 數(shù)據(jù)集[20]和模擬工作流隨機(jī)生成的起源圖數(shù)據(jù)集。起源圖僅包含實(shí)體和活動兩種類型的節(jié)點(diǎn)。模擬數(shù)據(jù)集可通過起源圖的層數(shù)和每層的節(jié)點(diǎn)數(shù)量等參數(shù)隨機(jī)生成，可通過調(diào)整參數(shù)的大小來調(diào)整起源圖的規(guī)模，進(jìn)而模擬出不同領(lǐng)域內(nèi)典型的數(shù)據(jù)處理過程，如5層起源圖可模擬校園請假處理流程等。本文將活動及其產(chǎn)生的實(shí)體看作一層，活動使用實(shí)體的關(guān)系看作層與層之間的聯(lián)系，每層產(chǎn)生的活動與實(shí)體節(jié)點(diǎn)和邊的數(shù)量隨機(jī)，且邊的指向隨機(jī)。若活動節(jié)點(diǎn)所在層為第i層，那么其使用的實(shí)體節(jié)點(diǎn)為第i-1 層。值得注意的是，第一層僅包括實(shí)體節(jié)點(diǎn)。本文采用的隨機(jī)生成數(shù)據(jù)集中規(guī)模較大的起源圖可達(dá)50 層，每層節(jié)點(diǎn)數(shù)在10～12 之間，最小規(guī)模的起源圖層數(shù)至少為5層，每層節(jié)點(diǎn)數(shù)在2～4左右，從而保證數(shù)據(jù)在模擬不同領(lǐng)域典型數(shù)據(jù)處理過程的真實(shí)性。隨機(jī)生成的起源圖如圖5所示，該起源圖包括5層，每層節(jié)點(diǎn)數(shù)量分別為2、3、4、2、2，如第一層對應(yīng)節(jié)點(diǎn)en0、en1，第二層對應(yīng)節(jié)點(diǎn)ac2、en3、en4。

實(shí)驗環(huán)境為Dell Inspiron 5548 筆記本電腦，Intel-Core i5-5200U @2.20 GHz CPU，12 GB內(nèi)存，64位操作系統(tǒng)。實(shí)驗算法在開源圖處理工具包JGraphT 的基礎(chǔ)上，使用Java語言實(shí)現(xiàn)。本文使用定義4所述的效用評估模型以及定義5所述的安全評估模型，在效用評估中依據(jù)專家經(jīng)驗參數(shù)設(shè)置為α=0.9，α表示直接依賴關(guān)系的可信度，在安全評估中參數(shù)選取現(xiàn)有研究常用的典型參數(shù)，即FP=0.8，pc=0.8。

4.2 實(shí)驗方案與結(jié)果分析

現(xiàn)有的起源過濾機(jī)制可分為抽象[12]、匿名[14]以及刪除+修復(fù)[17]三類，本節(jié)首先采用本文算法與以上經(jīng)典算法對Gene、Ncfs 數(shù)據(jù)集和隨機(jī)生成的起源圖數(shù)據(jù)集設(shè)置不同路徑類型的敏感間接依賴進(jìn)行實(shí)驗，過濾操作重復(fù)執(zhí)行1 000次，過濾視圖的溯源效用結(jié)果如表2所示。

表2 不同路徑類型間接依賴過濾的平均效用結(jié)果

其中U1、U2、U3、U4 分別為采用本文算法、SID算法、抽象算法、匿名算法得到的過濾視圖的平均溯源效用。由表2可知，過濾不同路徑類型的敏感間接依賴所得過濾視圖U1 均明顯高于U2、U3、U4。原因在于本文算法通過最小代價修復(fù)被誤斷的非敏感間接依賴集合，并且不確定的使用邊所替代的原起源圖中的路徑長度較短，從而過濾視圖與原起源圖的因果信度相對熵較小，效用更高。而SID算法在修復(fù)時引入的不確定邊所替代的路徑長度過長，且未完全修復(fù)由于刪除邊而被打斷的節(jié)點(diǎn)與溯源起點(diǎn)的路徑連通性，導(dǎo)致效用損失較大。抽象和匿名算法所得過濾視圖的效用顯著低于本文算法，是因為抽象算法會抽象所有路徑，導(dǎo)致過濾視圖與原起源圖的節(jié)點(diǎn)差過大，匿名算法將敏感節(jié)點(diǎn)匿名同樣會存在節(jié)點(diǎn)差，相比于本文算法與SID算法針對邊的過濾操作來說，效用損失較大。過濾視圖的安全結(jié)果如表3所示。

表3 不同路徑類型間接依賴過濾的平均安全結(jié)果

表3中S1、S2、S3、S4 分別為采用本文算法、SID算法、抽象算法、匿名算法得到的過濾視圖的平均起源安全結(jié)果。由表3可知，本文算法所得過濾視圖的起源安全S1 比S2 高，比S3、S4 算法所得過濾視圖的安全略低，但同樣可隱藏敏感間接依賴。由于匿名與抽象算法會將敏感節(jié)點(diǎn)置空，無原敏感節(jié)點(diǎn)在過濾視圖中出現(xiàn)，因此可保證完全安全。本文算法與SID 算法均為針對邊的操作，將敏感節(jié)點(diǎn)保留在過濾視圖中，所以起源安全略低，但由于本文在刪除邊處進(jìn)行修復(fù)，并未增加攻擊者的關(guān)注度FP，所需計算的節(jié)點(diǎn)對之間存在邊的可能性pc也并未提升，所以仍比SID 算法所得過濾視圖的安全性略高。為提高過濾視圖的安全性，在制定過濾策略時也可根據(jù)本文思想，修改過濾策略，添加更多的不確定使用邊，使得不同節(jié)點(diǎn)的度趨于平均，提高過濾視圖的安全性。對這些問題的深入研究和詳細(xì)論述超出了本文的范圍。

其次分別使用本文算法與SID、抽象和匿名算法對Gene、Ncfs 和隨機(jī)生成的數(shù)據(jù)集進(jìn)行實(shí)驗，每張起源圖分別設(shè)置不同路徑長度PL的敏感間接依賴進(jìn)行過濾，路徑類型隨機(jī)，重復(fù)執(zhí)行1 000次，記錄其生成過濾視圖的平均溯源效用、安全及運(yùn)行時間。過濾視圖的溯源效用和安全實(shí)驗結(jié)果如表4、5所示。

表4 過濾視圖的平均效用結(jié)果

表5 過濾視圖的平均起源安全結(jié)果

表4 中U1、U2、U3、U4 以及表5 中的S1、S2、S3、S4 分別為采用本文算法、SID算法、抽象算法、匿名算法得到的過濾視圖的平均溯源效用和平均安全結(jié)果。對比表4 中數(shù)據(jù)可知，本文算法所得過濾視圖比SID 算法所得過濾視圖的效用平均高達(dá)10.4%，比抽象算法所得過濾視圖的效用高達(dá)49.9%，比匿名算法所得過濾視圖的效用高23.4%。隨著敏感間接依賴路徑長度的增加，效用優(yōu)勢較SID與抽象算法更加明顯，這是由于當(dāng)路徑變長時，SID 算法在修復(fù)時不確定邊所替代的路徑變長，使過濾視圖與原起源圖中節(jié)點(diǎn)的因果信度分布相對熵變大，從而導(dǎo)致效用損失增加。而抽象算法會將敏感間接依賴路徑中的節(jié)點(diǎn)一并抽象，會造成更多的效用損失。由表5可知，本文算法在過濾不同路徑長度的敏感間接依賴所得起源安全均比SID高，比完全安全的抽象和匿名算法略低，綜合表4、5可說明本文算法在保證安全的同時提升效用的優(yōu)勢。

在性能上的對比如圖6 所示。橫軸代表敏感間接依賴路徑長度，縱軸表示重復(fù)執(zhí)行1 000 次過濾操作后的耗時。實(shí)驗結(jié)果表明，本文算法比SID、經(jīng)典的抽象、匿名算法總體耗時少，說明本文算法的可行性以及性能上的優(yōu)勢。

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

5 結(jié)束語

本文針對現(xiàn)有起源間接依賴過濾不滿足起源圖基本結(jié)構(gòu)約束的問題，提出了一種基于不確定使用邊的間接依賴過濾方法。實(shí)驗結(jié)果表明，本文所提的過濾方法在滿足起源圖基本結(jié)構(gòu)的同時有效過濾敏感間接依賴，且能夠保持較高的溯源效用。今后工作包括過濾方法的優(yōu)化以及根據(jù)用戶的安全和效用偏好快速選擇過濾策略。