1  引言

大数据时代，海量数据在网络上产生、传输、存储、演化直至消亡。数据的来源、质量、可信度、以及所经历的处理过程对实际的业务操作至关重要。为了增强数据的可信性，人们提出了数据起源的概念^[1]。数据起源(data provenance)记录数据从产生到消亡的整个生命周期内涉及的数据实体、处理过程以及相关人员和组织^[2]。数据起源通常呈现为由实体、活动、代理节点以及它们之间的因果依赖关系组成的有向无环图^[3]，称为起源图(Provenance Graph)。为便于不同组织共享数据起源，研究者提出了一系列数据起源模型，如OPM模型^[4]、PROV模型^[5]等。

起源图中可能含有各种敏感信息，如银行卡信息中用户的身份证号码和密码信息等。为确保起源图的安全，在发布或者共享起源图之前，需改造起源图，隐藏其中的敏感信息^[6]。

数据起源过滤是通过隐藏、抽象或改变起源图中的部分信息，实现起源安全或简化的典型技术^[7]。起源过滤所得的过滤视图通常服从一定的语法有效性约束，如连通性、无环^[8]、无假依赖^[9]等。过滤视图还必须满足溯源需求，具有一定的溯源效用。过滤视图的溯源效用是指过滤视图蕴含的信息能够满足用户溯源需求的程度。一般认为原始起源图能完全满足用户溯源需求，而过滤视图则因为缺少部分信息可能无法完全满足用户的溯源需求，即存在一定的效用损失。不同过滤技术改造原始起源图所得的过滤视图通常具有不同的溯源效用。

现在研究者对溯源效用尚无一致的理解和定义，无法对过滤视图的溯源效用进行定量评估，更无法基于过滤视图的溯源效用比较不同过滤技术的优劣。现有研究中仅有Blaustein等提出使用节点数和边数度量过滤视图的溯源效用^[10]。其中节点、边的效用分别是由过滤视图中保留原始起源图的节点、边的平均百分比来度量的^[11]。但效用度量的指标过少，没有考虑过滤视图中的路径效用，也没有考虑指标之间的相互影响，度量准确性和可信度不高。因此，本文在深入考察过滤视图与原始起源图结构差异的基础上，提出了一种数据起源过滤视图效用评估模型，支持定量地评估过滤视图的溯源效用。

2  预备知识及起源过滤

本章首先对起源图、过滤视图、过滤视图溯源效用进行形式化定义，其次分析几种典型过滤视图效用的不同，总结影响过滤视图效用的因素。

2.1  起源图、过滤视图和溯源效用

定义1：起源图PG=(V, E, P)

节点集V={v₁, v₂, …, v_n}，表示起源图PG有n个节点；边集E={e_i=<v, u>|vV, uV, i=1, 2, …, m}表示起源图PG有m条有向边，<v, u>表示节点v对节点u的直接依赖，u是e_i的起因节点，v是e_i的结果节点，也称u是v的直接前因节点，v是u的直接后果节点；路径集P={p_i=(v, u)|vV, uV, <v, u>E, i=1, 2, …, z}表示起源图PG有z条路径，(v, u)表示从节点v到节点u的一条单向路径。节点v为p_i的源节点，节点u为p_i的目标节点。路径上节点v、u之间的每个节点都称作节点v的前因节点或节点u的后果节点。每条路径都表示节点v与节点u之间的间接依赖关系。

定义2：过滤视图PS = F(PG, S)

PG为原始起源图；S为PG中的敏感信息集合，包含敏感节点、边或者路径；F表示所采用的过滤技术，则过滤视图PS为原始起源图PG采用过滤技术F过滤敏感信息S后得到的过滤视图。

定义3：溯源效用 U(PG, PS)

原始起源图、过滤视图中节点、边和路径均蕴含着具体的溯源信息，执行过滤技术后，原始起源图PG中的溯源语义在过滤视图PS中的保留度，称为过滤视图PS的溯源效用，可记为：

      (1)

Sem(PG)和Sem(PS)分别表示原始起源图PG和过滤视图PS所蕴含溯源语义信息的信息量，f表示融合原始起源图及过滤视图的统计度量的过滤视图溯源效用度量函数。起源图溯源语义的度量方法及溯源效用度量函数多样。例如，Blaustein等采用原始起源图中节点和边的数量等统计度量表示溯源语义，而溯源效用度量函数则定义为原始起源图中的节点或边在过滤视图中的保留率。

一般地，过滤视图与原始起源图的溯源结果之间差异越小，过滤视图的溯源效用越高。

2.2  典型过滤视图效用损失分析

本节分析典型过滤技术对起源图的改造过程，总结过滤视图与原始起源图的结构差异，为提出效用评估指标奠定基础。

现有的基本过滤技术包括匿名、抽象、删除及删除+修复^{[7, 12, 14]}。图1为符合PROV模型的原始起源图，图中包含实体(Entity)、活动(Activity)和代理(Agent)三类节点，分别由椭圆形、矩形和五边形表示。不同类型节点之间共存在7种依赖关系，如实体与活动之间的产生关系(Generation)，活动与实体之间的使用关系(Usage)，活动之间的通信关系(Communication)，代理与活动之间的负责关系(Attribution)等。图1中节点数为8，边数为7，路径数为16，设e₂节点为敏感节点，现使用这四种典型技术过滤该起源图后分别得到对应的过滤视图如图2，图3，图4和图5所示。

图1 原始起源图

图2 匿名过滤视图

图3 抽象过滤视图

图4 删除过滤视图

图5 删除+修复过滤视图

匿名（Anonymize）：将起源图中敏感节点属性及其所蕴含语义信息全部置空^[11]。图2匿名过滤视图中节点数为8，边数为7，路径数为16。

抽象（Abstract）：用一个新的抽象节点代替一个或一组敏感节点^[9]。图3抽象过滤视图中节点数为5，边数为4，路径数为4。

删除（Delete）：删除起源图中所有的敏感节点以及与其相关联的所有边。图4删除过滤视图中节点数为7，边数为4，路径数为0。

删除+修复（DelRep）：删除操作后，在起源图语法有效性的前提下，引入不确定的边，修复被破坏的非敏感的边或路径^[12]。图5删除+修复过滤视图中节点数为7，边数为6，路径数为10。

原始起源图经不同过滤操作后分别得到不同的过滤视图，过滤视图较原始起源图有所变化：

(1)匿名过滤视图中节点数不变，但引入一个新的匿名类型节点；其余三种过滤视图中节点数均减少。由于节点数量减少和类型发生变化，过滤视图与原始起源图的溯源效用产生差异。

(2)除匿名过滤视图外，其余过滤视图边数均减少；匿名、抽象过滤视图中引入新类型的节点，删除+修复过滤视图中引入不确定边。由于边的数量和类型发生变化，过滤视图和原始起源图的溯源效用产生差异。

(3)匿名过滤视图路径总数不变，其余三种过滤视图路径数均减少；匿名、抽象过滤视图中引入新类型节点，删除+修复过滤视图中引入不确定边，导致过滤视图路径类型改变。由于路径的数量和类型发生变化，过滤视图和原始起源图的溯源效用产生差异。

(4)过滤视图中节点、边、路径的数量和类型往往同时发生变化。如图2抽象过滤视图的结点数量、边数量以及路径数量均有所减少。在对比过滤视图和原始起源图溯源效用差异时，需要综合考虑节点、边、路径的数量和类型的变化。

3  过滤视图效用评估模型

本章基于过滤视图的节点效用、边效用、路径效用等三个主要度量指标构建过滤视图效用评估模型，为定量地评估过滤视图的溯源效用，并进而评价过滤技术的优劣奠定基础。

3.1  节点效用

过滤视图中的节点可分为以下三类：

(1)保留节点：是指从原始起源图中保留下来的未被改造的节点，保留节点无效用损失。设其蕴含的信息量为Λ；

(2)匿名节点：是指对原始起源图中节点进行匿名操作后得到的节点，设其效用损失率为α(0<α<1)，则其蕴含的信息量为Λ*(1-α)；

(3)抽象节点：是指对原始起源图中敏感信息进行抽象操作得到的节点，设其效用损失率为β(0<β<1)，则其蕴含的信息量为Λ*(1-β)。

综上可对过滤视图中的节点建立节点效用评估函数，记φ(v)为节点v的效用，则有：

        (2)

公式2计算了单个节点的效用，过滤视图的节点效用是过滤视图中所有节点的效用之和。

3.2  边效用

过滤视图中的边可分为以下三类：

(1)保留边：是指从原始起源图保留下来的边，保留边无效用损失。设其蕴含的信息量为K；

(2)匿名边：是指连接匿名节点或抽象节点的边，匿名边无效用损失，将其视为保留边，设其蕴含的信息量为Κ；

(3)不确定边：是指通过修复操作而增加的用于修复起源图连通性的边，有一定的效用损失。一般地，起源图中两个节点间隔越远，它们之间存在因果关系的可能性就越低。因此，原始起源图中节点对之间路径上的节点越多，则替代该路径的不确定边的效用损失就越大。设其效用损失率γ(0<γ<1)，每条不确定边所蕴含的信息量为Κ*(1-γ)ⁿ，n为该不确定边的两端点在原始起源图中间隔的节点数。

综上可对过滤视图中的边建立边效用评估函数，记δ(e)为边e的效用，则有：

       (3)

公式3计算了单条边的效用，过滤视图的边效用是过滤视图中所有边的效用之和。

3.3  路径效用

过滤视图中的路径可分为以下四类：

(1)保留路径：是指从原始起源图中保留下来的路径，由保留节点和保留边构成，保留路径无效用损失。设其蕴含的信息量为Μ；

(2)匿名路径：是指含有匿名节点或抽象节点的路径，一般地，路径中含有的匿名节点个数越多，依据该路径可溯源的信息就越少，则该路径的效用越低。设其效用损失率θ(0<θ<1)，每条匿名路径蕴含的信息量为Μ*(1-θ)^ε，ε为该路径中所含匿名节点或抽象节点的个数。

(3)不确定路径：是指含有不确定边的路径。一般地，路径中含有的不确定边的数目越多，依据该路径可溯源的信息就越少，则该路径的效用越低。设其效用损失率μ(0<μ<1)，每条不确定路径蕴含的信息量为Μ*(1-μ)^τ，τ为该路径中所含不确定边的条数。

(4)修复路径：是指既含有匿名或抽象节点又含有不确定边的路径。一般地，路径中匿名或抽象节点以及不确定边的路径的个数越多，该路径效用越低。设其效用损失率λ(0<λ<1)，每条修复路径的效用为Μ*(1-λ)^ψ，ψ为该路径中所含匿名或抽象节点的个数与不确定边的条数之和。

综上可对过滤视图的路径建立路径效用评估函数，记σ(p)为路径p的效用，则有：

      (4)

公式4计算了单条路径的效用，过滤视图的路径效用是过滤视图中所有路径的效用之和。

3.4  过滤视图效用评估

原始起源图的节点效用、边效用、路径效用分别为所有节点、边、路径蕴含的信息量总和。根据原始起源图和过滤视图，可以根据公式1计算出过滤视图的溯源效用。溯源效用度量函数f定义为过滤视图和原始起源图中节点效用、边效用、路径效用的加权比值和，记为：

(5)

|V|，|E|，|P|分别为原始起源图PG的节点数、边数、路径数；V'，E'、P'分别为过滤视图PS的节点集合、边集合、路径集合；φ(v)、δ(e)、σ(p)分别为过滤视图的单节点效用、边效用、路径效用；ω1、ω2、ω3分别为过滤视图节点效用率、边效用率和路径效用率的权重，且ω1+ω2+ω3 =1。

4  过滤视图效用评估算法

本章给出过滤视图效用评估算法并分析其渐进时间复杂度。

4.1  过滤视图效用评估算法分析

过滤视图效用评估算法首先遍历并统计原始起源图的节点数、边数和路径数并计算其效用。其次遍历过滤视图，对图中的节点、边和路径进行分类并统计数量，然后按照公式2、3和4分别计算过滤视图的节点效用、边效用和路径效用，最后依据公式5计算过滤视图的溯源效用。

设原始起源图为PG=(V, E, P)，该起源图的一个过滤视图为PS=(V', E', P')，基于过滤视图效用评估模型设计效用评估算法如下：

输入：PG, PS

输出：U(PG, PS)

1：EvaluateUti(PG, PS)

2：getNum(PG)//获取PG节点数、边数、路径数

3：Sem(PG)//计算PG中节点、边和路径效用

4：for each vV' do

5：  if v是保留节点 then

6：    V'Rem++ //获取PS中保留节点数

7：  if v是匿名节点 then

8：    V'Anm++ //获取PS中匿名节点数

9：  if v是抽象节点 then

10：    V'Abm++//获取PS中抽象节点数

11：end for

12：for each eE' do

13：  if e是保留边或匿名边 then

14：    E'm++ //获取PS中保留边或匿名边数

15：  if e是不确定边 then

16：    E'Unm++//获取PS中不确定边数

17：end for

18：for each pP' do

19：  if p是保留路径 then

20：    P'Rem++ //获取PS中保留路径数

21：  if p是匿名路径 then

22：    P'Anm++ //获取PS中匿名路径数

23：  if p是不确定路径 then

24：    P'Unm++//获取PS中不确定路径数

25：  if p是修复路径 then

26：    P'Repm++//获取PS中修复路径数

27：end for

28：Sem(PS)//计算PS中节点、边和路径效用

29：U(PG, PS)=f(Sem(PS), Sem(PG))

30：Return U(PG, PS)

上述算法中，第2行获取原始起源图中的节点数、边数和路径数；第3行计算原始起源图节点效用、边效用、路径效用；第4~11行遍历过滤视图中的节点；第12~17行遍历过滤视图中的边；第18~27行遍历过滤视图中的路径；第28行计算过滤视图节点效用、边效用、路径效用；第29行根据原始起源图PG和过滤视图PS的效用计算过滤视图溯源效用；第30行返回最终计算结果。

对上述算法分析可知，第2行与第18~27行分别为统计原始起源图和过滤视图的路径数，该操作耗时最长。设原始起源图节点数为n，边数为m，统计起源图连通路径的时间复杂度为O(n+m)。因此上述算法的平均渐进时间复杂度为O(n+m)。

5  实验及结果分析

本章通过模拟实验，对比四种不同过滤技术产生的过滤视图的效用，分析不同过滤技术的优劣，验证评估模型的有效性。首先介绍实验数据集，然后进行实验并分析实验结果。

5.1  实验数据集

实验数据来源于美国印第安纳大学发布的Animation、Gene2life、Nam-wrf等工作流起源数据^[13]，数据仅包含实体和活动两类节点。本次实验采用其中五类工作流起源数据，对应进行五组实验，对原始起源图中的敏感信息分别采用四种不同过滤技术，最后分析不同过滤技术产生的过滤视图的溯源效用，从而比较四种不同过滤技术的优劣性。Nam-wrf工作流类型的起源数据使用Graphviz图形化后所得的部分起源图如图6所示。

图6 Nam-wrf类型部分起源图

5.2  实验内容

首先，实验从Animation、Gene2life、Nam-wrf、Ncfs、Scoop等五类工作流起源数据中选取不同规模的起源数据作为原始起源图，并在这五类原始起源图中选取15%的节点作为敏感信息。其次，对这五类原始起源图分别采用四种不同过滤技术。最后，对得到的不同过滤视图使用效用评估算法并对溯源效用比较结果进行分析。

如图7所示，横坐标对应四种不同的过滤技术，纵坐标表示根据效用评估算法获得的过滤视图溯源效用。通过对实验结果分析可知：

图7 起源过滤视图溯源效用对比图

(1)采用四种过滤技术处理不同实验数据集所得过滤视图的溯源效用分布大致相同，且符合专家对四种过滤视图溯源效用之间关系的预期，表明本评估模型合理可行。

(2)过滤视图的溯源效用均小于1。其中匿名技术对原始起源图改造较少，溯源效用较高，而抽象技术对原始起源图改造较多，溯源效用就较低。此外删除+修复技术比删除技术溯源效用高，是由于删除+修复技术中新引入不确定边用以修复过滤视图中被破坏的路径和边，导致删除+修复过滤视图中边和路径的数量增加，类型发生变化，与原始起源图的差异较小，因此删除+修复技术所得的溯源效用就比单纯应用删除技术所得过滤视图溯源效用高。

溯源效用较高的过滤技术，对原始起源图改造较少，所得过滤视图与原始起源图差异较小，溯源安全性也就较低；相反，溯源效用越低的过滤技术，溯源安全性就越高。因此，需要根据实际场合的性能需求，选择不同的过滤技术。

6  结束语

本文针对不同起源过滤技术产生的过滤视图效用评估问题，提出了一种数据起源过滤视图效用评估模型，给出了过滤视图效用评估算法，通过实验验证该模型的合理性，并采用该模型分析不同过滤技术的优劣，为选用不同的过滤技术提供了参考。

参考文献

[1] MING Hua,ZHANG Yong,FU Xiao-hui.Survey of Data Provenance[J].Journal of Chinese Computer Systems,2012,33(9),1917-1923.

[2] Muniswamy-Reddy K K.Foundations for provenance-aware systems[D].Cambridge:Harvard University,2010.

[3] Luc Moreaua,Paul Grothb,James Cheneyc,et al.The rationale of PROV[J].Web Semantics:Science,Services and Agents on the World Wide Web,2015,Vol.35(4),235-257.

[4] Natalia Kwasnikowska,Luc Moreau,Jan Van Den Bussche.A Formal Account of the Open Provenance Model[J].ACM Transactions on the Web,2015,Vol.9(2).

[5] Missier P,Belhajjame K,Cheney J.The W3C PROV family of specifications for mode-ling provenance metadata[C]//Proc of the 16th Int.Conf.On Extending Database Technology.Genoa,Italy:ACM,2013:773-756.

[6] Davidson S B,Roy S.Provenance:Privacy and Security[M].Encyclopedia of Database Systems.Berlin: Springer,2017.

[7] Cheney J,Perera R.An analytical survey ofprovenance sanitization[C].Proc of the 5th IPAW on Provenance and Annotation of Data and Processes.Cologne:Springer,2014:113-126.

[8] Cheney J,Missier P,Moreau L,et al. Constraints of the PROV data model[R].Southampton: Web&Internet Science.2013.

[9] Missier P,Bryans J,Gamble C,et al.ProvAbs: Model,policy,and tooling for abstracting PROV graphs[C].Proc of the 5th IPAWon Provenance and Annotation of Data and Processes.Cologne:Springer, 2014:3-15.

[10] B.T.Blaustein,A.Chapman,L.Seligman,M.D.Allen, and A.Rosenthal.Surrogate parenthood:Protected and informative graphs.PVLDB,4(8):518–527,2011.

[11] Nagy N,Mokhtar HMO,El-Sharkawi ME.A Comprehensive Sanitization Approach for Workflow Provenance Graphs[C].International Workshop on Privacy and Anonymity in the Information Society.Bordeaux:Springer,2016:22-33.

[12] 王艺星,孙连山,石丽波.一种高效用数据起源过滤机制[J].计算机工程,2018,44(3):144-150.

[13] Cheah Y W,Plale B,Kendall-Morwick J,et al.A Noisy 10GB Provenance Database[M].Business Process Management Workshops.Berlin:Springer, 2012:370-381.

[14] 石丽波,孙连山,王艺星.数据起源安全研究综述[J].计算机应用研究,2017,34(1):1-7.