基于原語的通用起源過濾框架
2022-01-01 00:00:00孫連山馬勝天陳秀婷
計算機應(yīng)用研究 2022年3期
摘 要：現(xiàn)有起源過濾機制的通用性差，一個過濾機制僅能過濾某一特定類型的敏感元素，處理包含多種類型敏感元素的綜合性起源過濾需求仍然非常困難，為此提出了一種基于原語的通用起源過濾框架。首先，介紹了起源過濾涉及的敏感元素類型以及過濾約束；其次，深入分析已有過濾機制改造起源圖的基本操作和過程，形式地定義了一系列起源過濾原語，描述針對起源圖的最小改造操作，將起源過濾過程劃分為隱藏敏感元素、恢復(fù)有用依賴和驗證過濾約束三個階段，提出了一種基于原語組裝的分階段過濾策略空間構(gòu)造方法；最后設(shè)計并實現(xiàn)了基于原語的通用過濾算法，并在公開數(shù)據(jù)集上驗證了該算法的可行性。
關(guān)鍵詞：數(shù)據(jù)起源； 起源過濾； 過濾原語； 過濾框架； 過濾策略空間
中圖分類號：TP309 文獻標(biāo)志碼：A
文章編號：1001-3695（2022）03-040-0874-05
doi：10.19734/j.issn.1001-3695.2021.08.0348
基金項目：國家自然科學(xué)基金資助項目（61202019）；陜西省自然科學(xué)基礎(chǔ)研究計劃資助項目（2019JM-354）
作者簡介：孫連山（1977-），男，黑龍江佳木斯人，副教授，博士，主要研究方向為軟件工程、信息安全與隱私保護、數(shù)據(jù)溯源技術(shù)及應(yīng)用、區(qū)塊鏈技術(shù)（sunlianshan@sust.edu.cn）；馬勝天（1995-），女，河南三門峽人，碩士研究生，主要研究方向為數(shù)據(jù)起源安全；陳秀婷（1995-），女，山東聊城人，碩士研究生，主要研究方向為數(shù)據(jù)起源安全.
Generic provenance sanitization framework based on primitives
Sun Lianshan， Ma Shengtian， Chen Xiuting
（School of Electronic Information amp; Artificial Intelligence， Shaanxi University of Science amp; Technology， Xi’an 710021， China）
Abstract：The genericity of existing data provenance sanitization mechanisms is very low. One mechanism is usually used to deal with one specific type of sensitive elements. It is still very difficult to deal with comprehensive sanitization requirements including multiple types of sensitive elements in a disciplined manner. To address this issue， this paper proposed a primitive-based generic framework of provenance sanitization. Firstly， this paper introduced the types of sensitive provenance elements and structural constraints that might be involved in data provenance sanitization. Secondly， it thoroughly analyzed existing provenance sanitization mechanisms and formally defined a set of provenance sanitization primitives. Each primitive was a minimal operation for editing a provenance graph. This paper divided the overall process of data provenance sanitization into three stages： hiding sensitive elements， recovering insensitive dependencies， and verifying constraints. Furthermore， it proposed a method for constructing the space of sanitization strategies by selecting and composing possible sanitization primitives stage by stage. Finally， this paper designed and implemented a primitive-based generic provenance sanitization algorithm. The experimental results in public provenance datasets verity the effectiveness of the proposed method.
Key words：data provenance; provenance sanitization; sanitization primitives; sanitization framework; space of sanitization strategies
0 引言
隨著互聯(lián)網(wǎng)、大數(shù)據(jù)等技術(shù)的快速發(fā)展，計算基礎(chǔ)設(shè)施快速普及，不同系統(tǒng)中產(chǎn)生的大量數(shù)據(jù)能夠通過互聯(lián)網(wǎng)進行傳輸和轉(zhuǎn)移[1，2]，實現(xiàn)組織間的數(shù)據(jù)共享。這些數(shù)據(jù)對于各類組織和機構(gòu)制定決策至關(guān)重要。為了驗證數(shù)據(jù)的質(zhì)量和增強數(shù)據(jù)可信性[3]，研究人員提出了數(shù)據(jù)起源（data provenance）的概念[4]。數(shù)據(jù)起源記錄數(shù)據(jù)的歷史狀態(tài)和變化過程[5]，包括數(shù)據(jù)實體、數(shù)據(jù)被處理的過程以及涉及到的代理人員或組織。數(shù)據(jù)起源作為記錄數(shù)據(jù)歷史演變過程的元數(shù)據(jù)，可用于多種領(lǐng)域，如在醫(yī)療健康領(lǐng)域，醫(yī)院通過起源記錄病人的病史及就醫(yī)過程[6]，在出現(xiàn)誤診或病情惡化追因時可迅速定位問題所在之處。
互聯(lián)網(wǎng)世界當(dāng)中，除數(shù)據(jù)可能包含敏感信息外，數(shù)據(jù)起源也可能含有多種敏感信息，如用戶身份、公司機密信息等。為了解決該問題，研究人員提出了起源過濾（provenance sanitization）的概念。起源過濾是一種通過改造起源圖的內(nèi)容或結(jié)構(gòu)實現(xiàn)隱藏敏感信息的起源安全發(fā)布技術(shù)[7，8]。起源過濾所針對的敏感信息集合由用戶聲明，集合中可以聲明節(jié)點、邊或間接依賴中的任意1～3種類型的組合[9]。對原始起源圖進行過濾可以得到起源過濾視圖，過濾視圖和原始起源圖均滿足起源模型結(jié)構(gòu)約束，具備語法有效性和語義可用性。
現(xiàn)有起源過濾機制僅針對一種類型的敏感元素進行過濾，未考慮如何處理多種過濾需求，通用性較差。本文認(rèn)為節(jié)點、邊和間接依賴都可能蘊涵敏感信息并成為過濾對象，針對每種敏感元素的性質(zhì)特點，構(gòu)造了一種能夠綜合處理多種過濾需求的基于原語的通用起源過濾框架。本文的主要貢獻包括三個方面：a）定義了起源過濾原語，描述改造起源圖的基本操作，不同原語組合構(gòu)成不同過濾策略，實現(xiàn)了不同的過濾需求；b）提出了一種基于原語組裝的分階段過濾策略空間構(gòu)造方法，逐步構(gòu)造并篩選有效的過濾策略，允許用戶根據(jù)不同場景下的安全和效用需求，選擇相應(yīng)的過濾策略；c）設(shè)計了一種基于原語的通用過濾算法，實驗結(jié)果表明該算法能夠有效過濾敏感信息并保證起源安全。
1 相關(guān)工作
現(xiàn)有起源過濾機制往往被設(shè)計為僅過濾一種類型的敏感元素，如Dey等人[10]提出的起源過濾框架PROPUB，允許用戶選擇刪除、抽象等機制過濾敏感節(jié)點，得到安全的過濾視圖，但為了保證過濾視圖語法的有效性，存在將非敏感信息過度過濾的問題。Missier等人[11]提出ProvAbs過濾方法，用抽象的節(jié)點代替一組敏感節(jié)點集合，但該方法同時將敏感節(jié)點周圍的非敏感節(jié)點一并隱藏，在一定程度上降低了過濾視圖的效用。Blaustein等人[12]提出起源過濾方法Surrogate，采用泛化技術(shù)，用不同敏感級別的代理節(jié)點和邊替換敏感信息，以提高過濾視圖的效用，并初步定義了起源安全和效用的度量。Nagy等人[13]提出ProvS過濾方法，采用匿名機制過濾敏感節(jié)點，從而提高過濾視圖的安全與效用。Wu等人[14]基于敏感屬性抽象層次定義了一個α-GLprivacy模型，并提出了一個GPPub方法，通過對敏感節(jié)點的分級泛化實現(xiàn)了α-GLprivacy。王藝星等人[15]提出一種高效用的起源過濾機制，定義了不確定的依賴關(guān)系，在刪除敏感元素的基礎(chǔ)上修復(fù)由于刪除敏感信息而被斷開的非敏感依賴關(guān)系，較大程度地保留了起源圖的效用。孫連山等人[16]提出一種面向間接依賴的數(shù)據(jù)起源過濾方法，采用“刪除+修復(fù)”的思想過濾起源圖中的敏感間接依賴，通過刪除邊斷開敏感間接依賴路徑，并添加不確定的通信邊和派生邊修復(fù)被誤斷的間接依賴。
本文提出的基于原語的通用起源過濾框架關(guān)注不同敏感元素的特點，通過過濾原語表示對起源圖的最小改造操作，并將原語組裝成為復(fù)雜的過濾策略，處理多種過濾需求。
2 相關(guān)概念
數(shù)據(jù)起源是記錄數(shù)據(jù)演變過程的元數(shù)據(jù)，通常以有向無環(huán)圖的形式表示，簡稱起源圖[17]。本文采用萬維網(wǎng)聯(lián)盟（W3C）發(fā)布的PROV起源模型作為研究的標(biāo)準(zhǔn)模型，如圖1所示。
圖1中，PROV模型核心結(jié)構(gòu)定義了三種類型的節(jié)點，即實體（entity）、活動（activity）和代理（agent），定義了三種節(jié)點之間的七種關(guān)系，即使用關(guān)系（Used）、產(chǎn)生關(guān)系（WasGenera-tedBy）等。其中三類節(jié)點分別代表數(shù)據(jù)演變的中間數(shù)據(jù)、計算過程以及責(zé)任組織和人員，邊表示節(jié)點之間的因果關(guān)系，箭頭方向表示由當(dāng)前結(jié)果指向過去起因。PROV模型是一種與應(yīng)用無關(guān)的起源模型，當(dāng)應(yīng)用于特定領(lǐng)域時，可以在不違反規(guī)范的情況下對其進行特化。為方便論述，根據(jù)相關(guān)文獻[15，16，18]將起源圖相關(guān)概念形式化地定義如下：
定義1 起源圖PG=（V，E，P）。其中，節(jié)點集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)生原因；路徑集P={pi|pi=（u，v），u∈V，v∈V，i=1，2，…，k}表示圖PG中有k條路徑，（u，v）表示路徑的起始節(jié)點是u，末尾節(jié)點是v。
定義2 過濾視圖PV=f（PG，SI）。其中，PG表示原始起源圖，SI表示敏感信息集合，f表示所采用的過濾策略，過濾視圖PV為原始起源圖PG針對敏感信息SI采用過濾策略f進行過濾所得的安全的起源圖。
定義3 溯源效用U（PG，PV，v0）。溯源效用表示過濾后，原始起源圖PG當(dāng)中節(jié)點v0的溯源信息在過濾視圖PV中的保留程度。本文采用文獻[18]的效用評估模型，利用馬爾可夫鏈建模歷史節(jié)點影響溯源起點v0的因果信度，進而估計不同起源圖中各個歷史節(jié)點影響v0的因果信度分布之間的差異。
定義4 不確定邊。起源圖PG=（V，E，P），m∈V，（m，n）∈P且〈m，n〉E，則〈m，n〉為可引入過濾視圖的不確定邊。起源圖中不同節(jié)點的類型不同，對應(yīng)添加不同類型的不確定邊〈m，n〉，根據(jù)節(jié)點m和n的類型可定義不確定的使用邊、不確定的產(chǎn)生邊、不確定的通信邊及不確定的派生邊等。
定義5 溯源結(jié)果ΔPG（u）。起源圖PG=（V，E，P），對于任意的u∈V，若存在vi∈V使得（u，vi）∈P或〈u，vi〉∈E，i=1，2，…，m，則稱vi為u的歷史節(jié)點，稱ΔPG（u）={vi|（u，vi）∈P或〈u，vi〉∈E}為u的溯源結(jié)果。
3 基于原語的通用起源過濾框架
起源過濾的目標(biāo)是隱藏起源圖中的敏感信息或冗余信息。現(xiàn)有過濾機制具有不同的特點，對起源圖的改造程度也不同。用戶直接采用多種過濾機制實現(xiàn)不同類型的過濾需求時，可能會出現(xiàn)過度過濾以及違反過濾約束的問題。本文定義五個基本過濾原語，深入分析不同過濾機制的核心操作和基本過程，設(shè)計了一種基于原語組裝的分階段過濾策略空間構(gòu)造方法，實現(xiàn)對多種元素類型的過濾以及實現(xiàn)多場景需求。
3.1 過濾原語
定義6 過濾原語SP（PG，e）。其中，PG表示待處理的圖，e表示圖中待過濾的節(jié)點或邊。例如delEdge（PG，e）表示一個名為delEdge的原語，從圖PG中刪除邊e。借鑒基本的圖編輯操作，本文定義基本的過濾原語集合SP={delEdge，delVertex，addEdge，addNullVertex，anoyVertex}，分別表示刪除邊、刪除節(jié)點、添加邊、添加空節(jié)點、匿名節(jié)點等原子級的圖編輯操作，其中匿名節(jié)點表示對節(jié)點中的部分敏感屬性進行泛化。添加邊意味著在起源圖中添加不確定的依賴關(guān)系，從而恢復(fù)起源圖的連通性。為保證圖的語法有效性，刪除節(jié)點也意味著同時刪除與其相關(guān)聯(lián)的邊，若采用過濾原語對圖PG進行改造得到改造過的圖PG′，則可以采用過濾原語對PG′進行進一步的過濾。
過濾原語是改造圖的原子性操作，為了過濾起源圖某個敏感元素并同時保持起源圖的結(jié)構(gòu)有效性，可能需要采用多個過濾原語逐步改造起源圖。本文將逐步實施的過濾原語組合稱為過濾策略，過濾策略可表示為policy=[sp1+sp2+sp3+…+spn]，其中，spi（i=1，2，…，n）表示依次執(zhí)行的n個過濾原語。若將原始起源圖記為PG0，sp1對PG0進行改造將得到PG1，spi對PGi進行改造將得到PGi+1。值得注意的是，PGn是起源過濾的最終結(jié)果，必須符合起源圖的結(jié)構(gòu)有效性約束，而中間結(jié)果PGi有可能不滿足起源圖的結(jié)構(gòu)有效性約束。
3.2 過濾策略空間的構(gòu)造
起源圖擁有者需要采用不同的過濾策略實現(xiàn)不同的過濾需求。本文構(gòu)造可行過濾策略空間，允許用戶靈活地選用恰當(dāng)?shù)倪^濾策略實現(xiàn)不同過濾需求，構(gòu)造過濾策略需要解決過度過濾以及違反過濾約束等問題。本節(jié)分析已有過濾機制的基本操作和過程，將起源過濾過程劃分為隱藏、恢復(fù)和約束驗證三個階段，提出一種基于原語組裝的分階段過濾策略空間構(gòu)造方法。
3.2.1 隱藏敏感節(jié)點
分析現(xiàn)有過濾機制不難發(fā)現(xiàn)，無論敏感元素是節(jié)點還是邊，首先執(zhí)行的均是隱藏敏感信息的操作，如刪除或匿名敏感元素。當(dāng)敏感信息集合中存在不止一種類型的敏感元素時，同樣可以首先滿足用戶隱藏敏感信息的需求，即將所有敏感元素依次隱藏，涉及到的過濾原語為delVertex、delEdge和anoyVertex。
起源圖中敏感信息類型包括節(jié)點、邊和間接依賴。由于刪除節(jié)點會間接刪除邊，在過濾敏感邊時可以通過刪除邊的任一端點達到過濾的目的。有時為了提高過濾視圖安全性，還可以額外隱藏敏感元素的鄰居節(jié)點，即其前因或后果節(jié)點。隱藏單個敏感元素的可能原語如表1所示。其中，邊〈s，t〉是間接依賴P（m，n）上的一條邊，刪除該邊能夠打斷該間接依賴，nv、nw、ns分別表示節(jié)點v、w、s的鄰居節(jié)點。如表1所示，每個敏感元素均有多種可執(zhí)行的隱藏操作，而敏感信息集合中可能會包含多種敏感元素，在隱藏階段將各種敏感元素的所有可執(zhí)行原語構(gòu)成的集合進行笛卡爾積運算，得到過濾策略集合SP1。在多個敏感元素距離較近的情況下，可能會出現(xiàn)隱藏其中一個敏感元素的同時隱藏其余敏感元素的情況，此時會出現(xiàn)重復(fù)的過濾原語，僅保留其中一個即可。例如，若圖2中敏感信息集合SI={a3，〈e6，a2〉，P（e4，a0）}，G表示需要過濾的起源圖或過濾的中間結(jié)果，則部分過濾策略如下：SP11=[delVertex（dag，a3）+delEdge（dag，〈e6，a2〉）+delEdge（dag，〈a1，e1〉）]，該過濾策略覆蓋情況C2、C3和C6；SP12=[anoyVertex（dag，a3）+delVertex（dag，a2）+delVertex（dag，e6）+delVertex（dag，e1）]，此過濾策略覆蓋情況C1、C5和C7；SP13=[delVertex（dag，e6）+delVertex（dag，a3）+delVertex（dag，e7）+delVertex（dag，e1）+delVertex（dag，a1）]，該過濾策略覆蓋情況C2、C4和C8。由于刪除節(jié)點e6可以間接刪除邊〈e6，a2〉，執(zhí)行過濾策略SP13即可滿足用戶的過濾需求。
3.2.2 恢復(fù)非敏感依賴
過濾的目標(biāo)是隱藏敏感信息，但僅采用刪除或匿名原語隱藏敏感元素會導(dǎo)致起源圖被劃分為多個不連續(xù)的子圖或孤立節(jié)點，既違反了起源模型約束，也無法滿足用戶的溯源需求。因此，在執(zhí)行隱藏敏感信息的原語之后需要對起源圖進行修復(fù)，以便修復(fù)隱藏階段被額外過濾的非敏感元素。例如，通過添加被刪除元素的后果節(jié)點集合中的任一節(jié)點與該元素的任一前因節(jié)點之間的邊或通過添加空節(jié)點修復(fù)非敏感的間接依賴。恢復(fù)階段主要涉及到的原語為addEdge和addNullVertex。
恢復(fù)階段可用的具體修復(fù)原語如表2所示。其中，節(jié)點sv∈SV，集合SV表示節(jié)點v的后果節(jié)點集合-已刪除節(jié)點集合DV；節(jié)點pv∈PV，集合PV表示節(jié)點v的前因節(jié)點集合-DV，即PV=ΔPG（v）-DV；節(jié)點sk∈SK，集合SK表示節(jié)點k的后果節(jié)點集合-DV；節(jié)點pk∈PK，PK=ΔPG（k）-DV；節(jié)點sm∈SM，集合SM表示節(jié)點m的后果節(jié)點集合-已刪除節(jié)點集合DV；節(jié)點pt∈PT，集合PT表示敏感路徑中被刪除元素t的前因節(jié)點集合-DV，即PT=ΔPG（t）－DV。表中定義的添加邊均為根據(jù)邊的端點類型構(gòu)建的不確定邊。
針對每類敏感元素有多個可行的恢復(fù)原語，將對各個敏感元素的可能恢復(fù)原語集合進行笛卡爾積運算，得到過濾策略集合SP2，然后與隱藏階段產(chǎn)生的策略集合SP1結(jié)合形成初步的候選過濾策略集合SS。
如圖2所示，待過濾的敏感信息集合為SI={a3，〈e6，a2〉，P（e4，a0）}，若隱藏階段采用策略SP11=[delVertex（dag，a3）+delEdge（dag，〈e6， a2〉）+delEdge（dag，〈a1，e1〉）]，此時集合SV={e7，a4，e9}，PV={e6，a2，e4，e5，a1，e1，e2，e3，a0，e0}，集合SK={e7，a4，e9}，集合SM={a2，e6，e7，a4，e9}，集合SV中任一節(jié)點sv均可與PV中任一節(jié)點連接，同理集合SK中任一節(jié)點sk均可與PK中任一節(jié)點連接，集合SM中任一節(jié)點sm均可與PT中任一節(jié)點連接，則恢復(fù)階段的過濾策略之一可能為SP21=[addEdge（dag，〈e7，e6〉）+addEdge（dag，〈a4，a2〉）+addEdge（dag，〈e6，e1〉）]，此過濾策略符合情況S1、S3、S5。
將隱藏階段的策略SP11和恢復(fù)階段的策略SP21組裝得到一個完整的候選過濾策略SS1= [delVertex（dag，a3）+delEdge（dag，〈e6，a2〉）+delEdge（dag，〈a1，e1〉）+addEdge（dag，〈e7，e6〉）+addEdge（dag，〈a4，a2〉）+addEdge（dag，〈e6，e1〉）]。執(zhí)行過濾策略SS1可得過濾視圖如圖3所示。顯然對于過濾階段的策略SP11，還有其他恢復(fù)策略可與之結(jié)合，本文不再一一列舉。
3.2.3 驗證過濾約束
通過隱藏和恢復(fù)階段原語組合產(chǎn)生的過濾策略集合包含了過濾敏感元素的大部分策略，有一定的完備性。但這些過濾策略可能存在違反起源約束或者不滿足某些應(yīng)用領(lǐng)域特殊約束的問題，因此需進行過濾約束驗證，刪除不合規(guī)的過濾策略，保證起源過濾視圖的語法有效性。在過濾約束驗證階段，主要驗證過濾視圖是否滿足三類約束。
約束1 起源圖中一個實體節(jié)點只能由一個活動節(jié)點產(chǎn)生。可在過濾約束驗證階段通過以下方式進行驗證：對于任意的添加邊〈s， t〉，若邊的類型T（〈s， t〉）=產(chǎn)生，再次檢測節(jié)點s的出度，即OutDegree（s），若OutDegree（s）gt;1，說明該過濾策略違反了起源約束，應(yīng)放棄該條過濾策略。如圖3所示，按照恢復(fù)階段的恢復(fù)要求，過濾階段的原語集合SP11在恢復(fù)階段還可執(zhí)行SP22=[addEdge（dag，〈e7，e6〉）+addEdge（dag，〈e9，a2〉）+addEdge（dag，〈e6，e1〉）]，但該恢復(fù)操作中addEdge（dag，〈e9，a2〉）會導(dǎo)致節(jié)點e9同時由兩個活動a4和a2產(chǎn)生，違反了起源約束，所以該策略應(yīng)被放棄。
約束2 起源圖中不允許存在可以由其他依賴關(guān)系推理出來的依賴關(guān)系。可檢測恢復(fù)階段添加的邊的兩個端點在過濾視圖中是否存在其他路徑，若存在，則說明該過濾策略違反了約束。
約束3 不應(yīng)將已過濾的敏感元素恢復(fù)。恢復(fù)階段采用的添加節(jié)點的操作為添加空節(jié)點，因此已被過濾的起源元素本不應(yīng)被重新生成及使用。可在生成的過濾視圖中檢測敏感元素是否被過濾，不同的敏感元素特點不同，對于敏感節(jié)點v，遍歷過濾視圖的節(jié)點集合，判斷敏感節(jié)點v是否在過濾視圖節(jié)點集合中；對于敏感邊〈k， w〉，遍歷過濾視圖的邊集合，判斷敏感邊是否在過濾視圖邊集合中；對于敏感間接依賴P（u， v），遍歷過濾視圖中節(jié)點u的溯源結(jié)果，判斷節(jié)點v是否在該集合中。
4 基于原語的通用起源過濾算法
下面介紹基于原語的通用起源過濾算法，假設(shè)原始起源圖為pg，SI為敏感信息集合，v0是起源圖的溯源起點，SSC為過濾策略空間，pv為過濾視圖。基于過濾原語的起源過濾算法（primitive-based sanitization algorithm，PBSA）的偽代碼如下：
輸入：pg，SI，v0。
輸出：sscMap。
1 begin PBSA（pg，SI，v0）
2 SP1=AoS（pg，SI）; //調(diào)用隱藏階段算法
3 SP2=AoR（pg，SI，SP1）; //調(diào)用恢復(fù)階段算法
4 SSC=AoCD（pg，SI，SP2）; //調(diào)用約束驗證階段算法
5 for each ss∈SSC do
6 pv=sanitize（ss）; //執(zhí)行過濾原語，得到過濾視圖pv
7 utility=UtilityEvaluate（pg，pv，v0）; //評估pv的溯源效用
8 security=SecurityEvaluate（pg，pv）;//評估pv的安全
9 tempMap.put（utility，security）; //效用和安全值存入集合
10 sscMap.put（pv，tempMap）; //將pv的效用和安全存入集合
11 end for
12 return sscMap;
13 end PBSA（pg，SI，v0）
算法第2～4行分別表示構(gòu)造基于原語的過濾策略空間的三個階段；第5～11行表示對每張過濾視圖進行效用和安全的評估，第6行表示執(zhí)行由過濾原語表示的過濾策略，得到相應(yīng)的過濾視圖；第12行表示返回存有所有的過濾視圖及其對應(yīng)的效用和安全的集合。
算法PBSA主要在第2～4行構(gòu)建過濾策略空間耗時較長。假設(shè)敏感信息集合中有k個敏感元素，每種敏感元素平均有N種過濾操作和M種恢復(fù)操作，被約束刪除的策略可以看做常數(shù)，那么過濾策略空間可以構(gòu)建出Nk×Mk種策略，即算法PBSA的時間復(fù)雜度為O（Nk×Mk）。
5 實驗及結(jié)果分析
5.1 實驗整體設(shè)置
本文實驗采用印第安納大學(xué)發(fā)布的Gene、Ncfs數(shù)據(jù)集[19]和隨機生成的模擬工作流起源圖數(shù)據(jù)集Rgds。其中Gene為模擬生物信息工作流，Ncfs為海洋建模工作流。為了提高可讀性，模擬生成的起源圖忽略了相關(guān)屬性信息，且起源圖僅包括實體和活動兩種類型的節(jié)點[20]。實驗環(huán)境為Dell Inspiron 5548筆記本電腦，Intel Core i5-5200U @2.20 GHz CPU，12 GB內(nèi)存，64位操作系統(tǒng);實驗算法在開源圖處理工具包JGraphT的基礎(chǔ)上使用Java語言實現(xiàn)。本文使用定義3所述的效用評估模型，在效用評估中依據(jù)專家經(jīng)驗參數(shù)設(shè)置直接依賴關(guān)系的可信度α=0.9，不確定依賴關(guān)系β=0.7。
5.2 實驗方案與結(jié)果分析
首先以圖4為例設(shè)置敏感信息集合的過濾實驗，具體說明本文算法的可行性，由于篇幅有限，僅展示出部分過濾策略空間。假設(shè)敏感信息集合SI={a6，〈a4，e5〉，P（e2，e4）}，采用本文算法過濾SI所得部分過濾策略空間sscMap如下：
為方便描述，將相同的過濾操作以Si替代，如策略1的過濾操作為anoyVertex（pg，a6）+delEdge（pg，〈a4，e5〉）+delEdge（pg，〈e2，a2〉），策略2的過濾操作與其相同，將其簡寫為S1，策略6與策略7同理。經(jīng)驗證，以上每條過濾策略均能夠隱藏用戶聲明的所有敏感信息，且能夠滿足起源約束。
本節(jié)在已有數(shù)據(jù)集中聲明包含敏感節(jié)點、敏感邊、敏感間接依賴等三種敏感元素類型，每種元素類型均設(shè)置兩個敏感元素，待處理的過濾需求包含任意兩種、三種敏感元素類型的組合。實驗選取規(guī)模相近的起源圖進行實驗，實驗結(jié)果均為已有數(shù)據(jù)集上的平均結(jié)果，實驗結(jié)果如圖5所示。
其中，R1～R7分別表示敏感信息集合中包含節(jié)點、邊、間接依賴、節(jié)點和間接依賴、節(jié)點和邊、邊和間接依賴、節(jié)點和邊和間接依賴等七類情況。如圖5所示，在規(guī)模相近的起源圖中，隨著敏感信息集合中元素種類的增多，信息集合中敏感元素的數(shù)量也在增多，過濾策略數(shù)量快速增長，如R6與R7。其中情況R5較僅包含節(jié)點R1或僅包含邊R2的情況，其過濾策略數(shù)量并未呈現(xiàn)較大的增長，原因是實驗中存在敏感節(jié)點和邊距離較近的情況，所以對敏感節(jié)點和邊進行過濾時存在交叉過濾的情況，即在過濾節(jié)點的同時間接過濾了敏感邊，就不會再對敏感邊進行處理，得到如圖5所示的結(jié)果。圖5同樣說明了本文算法適用于用戶具有多種敏感元素類型的過濾需求的情況，并且能夠產(chǎn)生多種策略供用戶選擇，靈活性較高。
設(shè)置當(dāng)敏感信息集合中的敏感元素類型均為敏感節(jié)點且數(shù)量均為3時，對比不同規(guī)模的起源圖對過濾策略數(shù)量的影響。其中微型、小型、中型、大型規(guī)模起源圖分別表示起源圖中節(jié)點數(shù)量為10～15、15～20、20～30、30～40個，對邊的數(shù)量無限制。實驗結(jié)果如圖6所示。由圖6可知，在敏感元素數(shù)量一定時，隨著起源圖規(guī)模的不斷增大，過濾策略數(shù)量也隨之增長。這是因為當(dāng)起源圖規(guī)模增大時，敏感節(jié)點或邊的后果節(jié)點集合以及前因節(jié)點集合均會增大，在恢復(fù)階段出現(xiàn)的修復(fù)策略會隨之增加。
通過對以上兩種實驗結(jié)果分析，可得出以下結(jié)論：a）本文提出的過濾算法能夠處理多種類型敏感元素的情況，并且可產(chǎn)生多種過濾策略，用戶可根據(jù)其需求進行選擇，靈活性較強;b）本文提出的過濾算法與敏感信息集合的大小以及起源圖的規(guī)模大小相關(guān)，敏感信息集合越大，起源圖規(guī)模越大，該算法生成的過濾策略數(shù)量越多。
6 結(jié)束語
本文提出了一個基于原語的通用起源過濾框架，能夠處理包含不同類型敏感元素的綜合性過濾需求。該框架定義了五個細(xì)粒度的起源過濾原語，能夠分階段地構(gòu)造由多個原語組合而成的可行過濾策略，允許用戶根據(jù)不同場景的需要選擇恰當(dāng)?shù)倪^濾策略，并在起源開放數(shù)據(jù)集上驗證了通用起源過濾框架的可行性。但本文算法會自動生成大量可行過濾策略，未來工作需要根據(jù)用戶的實際需求快速準(zhǔn)確地篩選過濾策略。
參考文獻：
[1]Huang Gang， Ma Xiaoxing， Tsai W T. A new software paradigm for Internet computing[J].National Science Review，2014（2）：168-169.
[2]Bertolino A， Blake M B， Mehra P， et al. Software engineering for Internet computing： internetware and beyond[J].IEEE Software，2015，32（1）：35-37.
[3]Keshavarz A S， Huynh T D， Moreau L. Provenance for online decision making[C]//Proc of the 5th International Provenance and Annotation Workshop.Cham：Springer，2014：44-55.
[4]明華，張勇，符小輝.數(shù)據(jù)溯源技術(shù)綜述[J].小型微型計算機系統(tǒng)，2012，33（9）：1917-1923.（Ming Hua， Zhang Yong， Fu Xiaohui. Survey of data provenance[J].Journal of Chinese Computer Systems，2012，33（9）：1917-1923.）
[5]劉通，王鳳英.基于OPM的安全起源模型[J].計算機應(yīng)用研究，2013，30（10）：3117-3120.（Liu Tong， Wang Fengying. Security provenance model based on OPM[J].Application Research of Computers，2013，30（10）：3117-3120.）
[6]McClatchey R， Shamdasani J， Branson A， et al. Traceability and provenance in big data medical systems[C]//Proc of the 28th International Symposium on Computer-Based Medical Systems.Washington DC：IEEE Computer Society，2015：226-231.
[7]Cheney J， Perera R. An analytical survey of provenance sanitization[C]//Proc of the 5th International Provenance and Annotation Workshop.Cham：Springer，2014：113-126.
[8]陳叢，周力臻.基于Python爬蟲技術(shù)的虛假數(shù)據(jù)溯源與過濾[J].計算機仿真，2021，38（3）：346-350.（Chen Cong， Zhou Lizhen. Tracing and filtering of fake data based on Python crawler technology[J].Computer Simulation，2021，38（3）：346-350.）
[9]張學(xué)旺，馮家琦，殷梓杰，等.基于區(qū)塊鏈的數(shù)據(jù)溯源可信查詢方法[J].應(yīng)用科學(xué)學(xué)報，2021，39（1）：42-54.（Zhang Xuewang， Feng Jiaqi， Yin Zijie， et al. Trusted query method for data provenance based on blockchain[J].Journal of Applied Sciences，2021，39（1）：42-54.）
[10]Dey S C， Zinn D， Ludscher B. ProPub： towards a declarative approach for publishing customized， policy-aware provenance[C]//Proc of International Conference on Scientific and Statistical Database Management.Berlin：Springer，2011：225-243.
[11]Missier P， Bryans J， Gamble C， et al. ProvAbs： model， policy， and tooling for abstracting PROV graphs[C]//Proc of the 5th International Provenance and Annotation Workshop.Cham：Springer，2014：3-15.
[12]Blaustein B， Chapman A， Seligman L， et al. Surrogate parenthood： protected and informative graphs[J].Proceedings of the VLDB Endowment，2011，4（8）：518-525.
[13]Nagy N， Mokhtar H， El-Sharkawi M E. A comprehensive sanitization approach for workflow provenance graphs[C]//Proc of International Workshop on Privacy and Anonymity in the Information Society.Berlin：Springer，2016：22-33.
[14]Wu Jian， Ni Weiwei， Zhang Sen. Generalization based privacy-preserving provenance publishing[C]//Proc of the 5th International Conference on Web Information Systems and Applications.Cham：Springer，2018：287-299.
[15]王藝星，孫連山，石麗波.一種高效用數(shù)據(jù)起源過濾機制[J].計算機工程，2018，44（3）：144-150.（Wang Yixing， Sun Lianshan， Shi Libo. A data provenance sanitization mechanism for high utility[J].Computer Engineering，2018，44（3）：144-150.）
[16]孫連山，歐陽曉通，徐艷艷.面向間接依賴的數(shù)據(jù)起源過濾方法[J].計算機科學(xué)，2019，46（3）：164-169.（Sun Lianshan， Ouyang Xiaotong， Xu Yanyan.Novel sanitization approach for indirect dependencies in provenance graph[J].Computer Science，2019，46（3）：164-169.）
[17]王芳，趙洪，馬嘉悅，等.數(shù)據(jù)科學(xué)視角下數(shù)據(jù)溯源研究與實踐進展[J].中國圖書館學(xué)報，2019，45（5）：79-100.（Wang Fang， Zhao Hong， Ma Jiayue， et al. Research and practice progress of data pro-venance from the perspective of data science[J].Journal of Library Science in China，2019，45（5）：79-100.）
[18]孫連山，徐艷艷，張永斌.基于馬爾可夫鏈的起源過濾效用評估模型[J].陜西科技大學(xué)學(xué)報，2020，38（2）：172-179.（Sun Lianshan， Xu Yanyan， Zhang Yongbin. An evaluation model of sanitized data based on Markov chain[J].Journal of Shaanxi University of Science amp; Technology，2020，38（2）：172-179.）
[19]Cheah Y W， Plale B， Kendall-Morwick J， et al. A noisy 10 GB provenance database[C]//Proc of International Conference on Business Process Management.Berlin：Springer，2011：370-381.
[20]Missier P， Bryans J， Gamble C， et al. Abstracting PROV provenance graphs：a validity-preserving approach[J].Future Generation Computer Systems，2020，111（5）：352-367.
