基于不確定使用邊的間接依賴過濾方法

孫連山，陳秀婷，馬勝天

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

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

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

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

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

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

圖1 部分文檔起源圖PG

1 相關概念和問題描述

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

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

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

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

V={v1,v2,…,vn} 表示圖PG中有n個節(jié)點；邊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進行過濾所得的起源圖。

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

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

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

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

其中，ΔPG(v0)為溯源起點v0的溯源結果，(vi)表示起點v0的溯源結果集中節(jié)點vi的置信度向量。進而可利用相對熵計算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é)點n1,n2∈V,為其在PV 中對應的節(jié)點，V′、E′為過濾視圖PV中的節(jié)點集和邊集，θ主要依賴于兩個因素FP與pc，如式（4）所示：

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

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

定義6 間接依賴過濾。

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

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

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

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

2 間接依賴過濾

2.1 基本原理

定義7 不確定的使用邊。

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

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

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

圖2 起源圖示例

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

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

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

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

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

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

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

定理假設刪除邊后所得過濾視圖為PV，PV中任意兩對待修復的非敏感間接依賴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)；綜合兩個方面的結論可知，s∈ΔPV(a)且v∈ΔPV(t)，因此P(a,b)∈R(e)。證畢。

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

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

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

2.2 過濾策略

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

2.2.1 刪除

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

2.2.2 修復

根據(jù)定義4，為降低過濾視圖與原起源圖因果信度分布的相對熵，保持過濾視圖的溯源效用，對于?vi∈ΔPG(s)，s為刪除邊的端點，需修復由于刪除邊而被誤斷的非敏感間接依賴P(v0,vi)，某些情況下，為滿足起源結構約束，還需修復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ù)定理及推論，可用一條或多條不確定的使用邊修復非敏感間接依賴集合SP，在滿足起源圖基本結構的同時提升溯源效用，具體過濾策略如表1所示。表中＜s,t＞為離敏感節(jié)點u最近的使用邊，節(jié)點s、t是邊的兩端點，sau為敏感間接依賴P(u,v)中離u最近的后果活動節(jié)點，sau∈ph(v0,u)，pet為距離s最近的前因實體節(jié)點，且pet∈ΔPG(t)-ph(u,v)。

表1 間接依賴過濾策略

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

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

圖3 過濾視圖

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

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

圖4 起源圖示例

3 間接依賴過濾算法

本章介紹單路徑間接依賴過濾算法，可根據(jù)需要多次調(diào)用該算法實現(xiàn)多路徑間接依賴過濾。假設原始起源圖為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é)點

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

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＞)//修復被斷開的非敏感間接依賴

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 隨機生成起源圖示例

33. returnPV

34. endSID

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

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

4 實驗及結果分析

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

4.1 實驗整體設置

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

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

4.2 實驗方案與結果分析

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

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

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

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

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

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

表4 過濾視圖的平均效用結果

表5 過濾視圖的平均起源安全結果

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

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

圖6 性能對比結果

5 結束語

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