本发明涉及实现起源数据安全分享的起源过滤技术领域，具体涉及一种基于过滤原语的起源过滤框架。
背景技术：
数据起源(dataprovenance，简称起源)也称为数据溯源、数据世系等，记录数据的来源、数据所经历的处理过程以及时间、地点、工具、方法、策略、组织和人员等相关信息，是描述数据演化历史的元数据。起源是评估数据真实性、可信性以及可重现性的重要基础。为实现跨组织的起源数据的发布和共享，w3c相继发布了起源数据模型标准opm和prov-dm，用带标注的有向无环图表示起源信息，如图1所示。起源图的核心结构包括实体、活动、代理等三类起源元素以及它们之间的多种依赖关系。
起源数据记录描述数据演变历史，可能蕴含各种敏感信息。如企业和运输的详细信息，分销商销售的身份信息等，直接发布和共享原始的起源信息可能造成敏感信息泄露，并进而造成严重的后果。原始的起源还往往包含一些用户不需要的冗余细节信息。起源过滤(provenancesanitization)也称为起源校订、起源抽象，在起源数据发布共享之前，对起源图进行改造，选择性地过滤起源图中的敏感或冗余信息，从而得到安全、可用的起源过滤视图(sanitizedprovenanceview)的新技术。起源过滤的最终目的是在保证起源安全的前提下，过滤掉原始起源图中的所有敏感起源信息，同时尽可能保持过滤视图的溯源效用。溯源效用是指过滤视图满足用户溯源需求的程度。
现有的起源过滤技术能过滤起源图中具体的节点和边乃至子图，但仍存在如下不足。首先，一个过滤机制仅能过滤某一特定类型的敏感元素，无法同时实现用户的多种过滤需求，通用性差。其次，现有的过滤机制仅能获取单一的过滤视图，不允许用户根据具体环境下的安全风险和效用需要，选择个性化的过滤方案，可定制性差。
技术实现要素：
为了克服以上技术问题，本发明的目的在于提供一种基于过滤原语的起源过滤框架，以解决现有起源过滤技术的通用性差、过滤方案可定制性差等问题。
为了实现上述目的，本发明采用的技术方案是：
一种基于过滤原语的起源过滤框架，包括以下步骤；
步骤1：定义具体的原语，作为改造起源图的最小操作；
步骤2：形式地定义起源图的结构约束和过滤约束；
步骤3：检查待过滤的起源图，确保其为符合标准化起源模型及其模型约束的有向无环图；
步骤4：声明起源过滤需求，即起源图中待过滤的敏感信息；其中，过滤需求中待过滤的敏感元素用起源图中的节点表示，过滤需求中待过滤的直接或间接依赖关系用起源图中的节点对表示；
步骤5：根据过滤需求，构造过滤策略空间；
步骤6：更新起源图，得到起源过滤视图，并按照已有的起源过滤视图评估模型定量地评估起源过滤视图的效用和安全，生成起源过滤报告。
所述步骤1具体操作为：
(1)deledge(pg,<u,v>)：删除边e＝<u,v>；
(2)delvertex(pg,v)：删除节点v；
(3)addedge(pg,<u,v>)：增加边e＝<u,v>；
(4)addnullvertex(pg,v)：增加空节点v；
(5)anoyvertex(pg,v)：匿名节点v。
所述步骤2具体操作为：
模型约束1：起源图中不允许出现孤立节点；
模型约束2：一个实体不能由两个以上的活动产生；
模型约束3：当一个直接依赖关系可由其它直接依赖关系推理得到时，应在起源图中省略相应的边；
模型约束4：起源图中不允许出现环路，可利用拓扑排序算法检测起源图中是否有环；
过滤约束1：过滤视图不应引入假依赖；
过滤约束2：不应将已过滤的敏感元素恢复。
所述步骤4中声明过滤需求时应注意：
(1)敏感信息为节点时，需要说明节点的标识符或部分属性(attributes)，当节点类型是活动时，还可以指出活动发生的起止时间(starttime和endtime)；
(2)敏感信息为依赖关系时，无论直接依赖关系还是间接依赖关系，均需指明该依赖关系所依附的两个起源元素的标识符或部分属性。
所述构造过滤策略空间具体包括：
步骤5.1：根据过滤需求，选择恰当的过滤原语，如deledge、delvertex、anonyvertex，根据过滤规则，构造敏感信息过滤原语集合p；
步骤5.2：面向溯源需求，选择恰当的恢复原语，如addedge、addnullvertex，根据恢复规则，构造恢复起源图中被意外打断的连通路径的恢复原语集合q；
步骤5.3：构造过滤策略空间pm×qn，检查过滤策略是否符合给定约束，形成合法的过滤策略空间s，其中m表示采用不多于m个过滤原语，n表示采用不多于n个恢复原语，则过滤策略空间中的每条过滤策略，由不多于m n个恢复原语构成，m和n的值由过滤规则和恢复规则确定；
步骤5.4：检查过滤策略空间s中的每条过滤策略是否符合模型约束和过滤约束。
所述步骤5.1过滤规则如表所示：
过滤规则
所述步骤5.2的恢复规则如表所示：
恢复规则
本发明的有益效果：
1.解决了一个过滤机制仅能过滤某一特定类型的敏感元素，无法同时实现用户的多种过滤需求，通用性差的问题，定义了过滤原语，设计了针对每个敏感信息的由过滤原语组装的过滤策略，进而构成过滤策略空间，并将过滤策略空间划分为过滤、恢复和约束检测三个阶段，提出了一种基于原语的起源过滤框架；
2.解决了现有的过滤机制仅能获取单一的过滤视图问题，通过过滤原语框架构造完整的过滤策略空间，每条过滤策略都包含每个敏感信息的不同改造原理，所生成的过滤视图在满足过滤需求的基础上，具有不同的效用和安全，用户在面向不同场景发布过滤视图时可以根据其偏好在过滤策略空间中进行选择，可定制性较高。
附图说明
图1为本发明参考的标准起源模型prov-dm的核心结构图。
图2为本发明的起源过滤框架流程图。
图3为过滤前的原起源图实例。
图4为在过滤需求r1的情况下，使用本发明的方法处理图3得到的过滤视图一。
图5为在过滤需求r1的情况下，使用本发明的方法处理图3得到的过滤视图二。
图6为在过滤需求r2的情况下，使用本发明的方法处理图3得到的其中一张过滤视图。
具体实施方式
下面结合附图对本发明作进一步详细说明。
本发明假定待过滤的起源图具有可追溯的依赖语义，即若任意节点v可以追溯到另一节点u，则u是v发生的部分起因。
实施例参考标准起源模型prov-dm，本发明方法所涉及的相关概念定义如下：
定义1起源图provgraph＝(v,e):
节点集v＝{v1，v2，…，vn}，在起源图中，每个节点v表示一个起源元素，起源元素分为实体(en)，活动(ac)和代理(ag)等三种类型，分别表示数据演化过程中的中间形态制品、所经历的操作活动以及实施相关操作活动的人或组织；
映射
边集e＝{ei＝<u,v>|u∈v；v∈v；i＝1,2,…,m}，在起源图中，边e＝<u，v>是从v到u的有向弧，表示v到u的直接依赖关系，即v是u的直接后果，而u是v的直接起因。
定义2起源元素子集：实体集(entity)、活动集(activity)和代理集(agent)：
根据起源元素的类型可将起源元素集合v可分为三个互不相交的子集：实体集(entity)，活动集(activity)和代理集(agent)，有v＝entity∪activity∪agent。
实体集：
活动集：
代理集：
不同类型的起源元素之间的依赖关系具有不同的语义，可根据相互依赖的起源元素的类型，将起源图中的边划分为不同的子类。
定义3直接依赖关系子集：usage，generation，association，attribution，derivation，communication，delegation：
起源图中的边表示相邻两节点间的因果关系，边集e可分为七个互不相交的子集，e＝usage∪generation∪association∪attribution∪derivation∪communication∪delegation，其中：
usage(使用依赖)＝{<en,ac>|en∈entity,ac∈activity,表示活动ac使用实体en}；
generation(产生依赖)＝{<ac,en>|ac∈activity,en∈entity,表示实体en由活动ac产生}；
association(关联依赖)＝{<ag,ac>|ag∈agent,ac∈activity,表示代理ag在活动ac中承担责任}；
attribution(归属依赖)＝{<ag,en>|ag∈agent,en∈entity,表示代理ag对实体en承担责任}；
derivation(派生依赖)＝{<en1,en2>|en1,en2∈entity,表示实体en2由实体en1派生而来}；
communication(通信依赖)＝{<ac1,ac2>|ac1,ac2∈activity,表示活动ac2使用了由活动ac1产生的实体}；
delegation(代理依赖)＝{<ag1,ag2>|ag1,ag2∈agent,表示代理ag2代表代理ag1，称ag1为ag2的上级代理}。
定义4起源间接依赖：
间接依赖p(u,v)＝{vi|v0＝u；vk＝v；<vi,vi 1>∈e；i＝0,1,…,k-1；k>2}，是起源图中的节点序列，表示节点v对u的间接依赖关系，即v是u的间接后果，u是v的间接起因；
连通路径集pathset(u,v)＝{p(u,v)|u∈v,v∈v}，是节点对u，v之间所有连通路径构成的集合，表示节点v对节点u的间接依赖语义。
在起源图provgraph中，若en1、en2、en3∈entity，ac1、ac2、ac3∈activity，ag1、ag2∈agent，则如下定理表示相关起源依赖关系的传递性和可推理性：
定理1attribution关系具有可推理性：
(1)负责活动ac1的代理ag1对该活动产生的实体en1负责；即，若<ag1,ac1>∈e且<ac1,en1>∈e，则<ag1,en1>成立；
(2)负责代理ag2的上级代理ag1对该代理负责的实体en1负责；即，若<ag1,ag2>∈e且<ag2,en1>∈e，则<ag1,en1>成立。
定理2association关系具有可推理性：
负责代理ag2的上级代理ag1对该代理负责的活动ac1负责；即，若<ag1,ag2>∈e且<ag2,ac1>∈e，则<ag1,ac1>成立。
定理3communication关系具有可推理性：
活动ac1产生的某个实体en1是活动ac2开始并随后产生其它实体的必要条件，则表示这两个实体间存在通信关系；即，若<ac1,en1>∈e且<en1,ac2>∈e，则<ac1,ac2>成立。
定理4communication关系具有传递性：
活动ac1与活动ac2间存在通信关系，活动ac2与活动ac3间存在通信关系，则活动ac3与活动ac1间也存在通信关系；即，若<ac1,ac2>∈e且<ac2,ac3>∈e，则<ac1,ac3>成立。
定理5delegation关系具有传递性：
代理ag2的上级代理是ag1，ag3的上级代理是ag2，则可以说ag1是ag3的上级代理；即，若<ag1,ag2>∈e且<ag2,ag3>∈e，则<ag1,ag3>成立。
定理6derivation关系具有传递性：
若实体en1由实体en2派生而来，实体en2由实体en3派生而来，则从一定程度上可以认为en1由en3派生而来；即，若<en3,en2>∈e且<en2,en1>∈e，则<en3,en1>成立。
为准确地表达过滤操作，下面定义起源过滤的基本操作。
定义5起源过滤基本操作：
(1)getpre(v)：获取节点v的前因节点集合，若u∈getpre(v)，则存在e＝<u,v>∈e，即u是v发生的起因之一；
(2)getsub(v)：获取节点v的后果节点集合，若u∈getsub(v)，则存在边e＝<v,u>∈e，即u是v的发生的后果之一；
定义6不确定的通信边：
起源图pg＝(v,e,ph),m∈v,n∈δpg(m),m，n均为活动节点，且
定义7不确定的派生边：
起源图pg＝(v,e,ph),m∈v,n∈δpg(m),m，n均为实体节点，且
定义8不确定的使用边：
起源图pg＝(v,e,ph),m∈v,n∈δpg(m),m为活动节点，n为实体节点，
定义9不确定的产生边：
起源图pg＝(v,e,ph),m∈v,n∈δpg(m),m为实体节点，n为活动节点，
本发明的一种基于过滤原语的起源过滤框架，处理符合起源标准模型及其约束的有向无环起源图，根据包括待过滤节点和节点对的过滤需求，按照所提出的起源过滤框架中的过滤规则、修复规则以及约束检测规则处理起源图，最后采用起源过滤视图评估模型评估过滤视图的效用，生成起源过滤报告。
步骤1：定义具体的原语，作为改造起源图的最小操作，如下所示：
(1)deledge(pg,<u,v>)：删除边e＝<u,v>；
(2)delvertex(pg,v)：删除节点v；
(3)addedge(pg,<u,v>)：增加边e＝<u,v>；
(4)addnullvertex(pg,v)：增加空节点v；
(5)anoyvertex(pg,v)：匿名节点v。
步骤2：形式地定义起源图的结构约束和过滤约束，如下所示：
模型约束1：起源图中不允许出现孤立节点；
模型约束2：一个实体不能由两个以上的活动产生；
模型约束3：当一个直接依赖关系可由其它直接依赖关系推理得到时，应在起源图中省略相应的边；
模型约束4：起源图中不允许出现环路，可利用拓扑排序算法检测起源图中是否有环。
过滤约束1：过滤视图不应引入假依赖；
过滤约束2：不应将已过滤的敏感元素恢复。
步骤3：检查待过滤的起源数据，确保其为符合标准化起源模型及其模型约束的有向无环图。
步骤4：声明起源过滤需求，即起源图中待过滤的敏感信息；其中，过滤需求中待过滤的敏感元素用起源图中的节点表示，过滤需求中待过滤的直接或间接依赖关系用起源图中的节点对表示。
声明过滤需求时应注意：(1)敏感信息为节点时，需要说明节点的标识符或部分属性(attributes)，当节点类型是活动时，还可以指出活动发生的起止时间(starttime和endtime)；(2)敏感信息为依赖关系时，无论直接依赖关系还是间接依赖关系，均需指明该依赖关系所依附的两个起源元素的标识符或部分属性。
步骤5：根据过滤需求，按照如下步骤构造过滤策略空间。
本发明方法按照过滤、恢复、约束检测的顺序依次处理待过滤对象，需要注意的是，每个阶段均在执行对所有敏感信息的改造操作以后才进入下一阶段，具体流程如图2所示。
首先，根据过滤需求，选择恰当的过滤原语，依次取待过滤的敏感信息eli，判断eli的元素类型，其元素类型不同，对应不同的过滤规则，具体规则如表1所示。其中，nv，nw，ns分别表示节点v，w，s的邻居节点。将敏感信息eli对应的所有过滤原语sp添加到集合tempspi，并将敏感信息集合中的所有敏感信息eli对应的过滤操作集合tempspi中的元素进行笛卡尔积运算，即对过滤原语进行组装，得到过滤原语集合sp1。
表1过滤规则
为了不对起源图造成过度过滤，本申请对于可删除的敏感元素的邻居节点与敏感元素的距离限制在具体数值r范围内。所谓敏感元素的邻居节点与敏感元素之间的距离，指的是以敏感元素为起点，通过起源图中的边到达节点所需的步数。
然后，面向溯源需求，选择恰当的恢复原语，依次取过滤阶段所得集合sp1中的过滤策略sp1i，同时考虑敏感信息集合中的敏感元素，设计融合敏感元素和过滤操作的恢复操作。在过滤阶段产生的由过滤原语集合构成的每条过滤策略sp1i的基础上，恢复阶段执行每个敏感元素的恢复操作，并将各个敏感元素的可执行恢复操作进行笛卡尔积运算，然后与集合sp1i结合得到过滤原语集合表示的过滤策略sp2ij，最终得到整个恢复阶段的过滤原语集合sp2。不同类型的敏感元素对应不同的恢复规则，具体的恢复规则如表2所示。其中节点sv∈sv，集合sv表示节点v的后果节点集合-已删除节点集合dv；节点pv∈pv，集合pv表示节点v的前因节点集合-dv，即pv＝δpg(v)-dv；节点sk∈sk，集合sk表示节点k的后果节点集合-dv；节点pk∈pk，pk＝δpg(k)-dv；节点sm∈sm，集合sm表示节点m的后果节点集合-已删除节点集合dv；节点pt∈pt，集合pt表示敏感路径中被删除元素t的前因节点集合-dv，即pt＝δpg(t)-dv。表中定义的添加边均为根据边的端点类型构建的不确定边。
表2恢复规则
假设sp1表示所有敏感元素在过滤阶段产生的过滤原语集合。恢复阶段算法(algorithmofrepair)如下：
输入：pg,si,sp1
输出：sp2
最后，在过滤和恢复阶段之后，构建过滤约束检测阶段，删除已产生的不合规的过滤策略，保证起源过滤视图的语法有效性，最终将满足约束检测的过滤策略构成过滤策略空间。
实施例中起源原图符合标准化起源模型prov-dm，如图3所示。声明两个不同过滤需求：
r1：敏感信息集合si＝{ac6,<ac4,en5>,p(en2,en4)}
r2：敏感信息集合si＝{en1,<en1,ac1>,p(ac2,ac4)}
采用所提出的起源过滤框架对图3所示的起源图进行处理，实现需求r1得到的部分起源过滤策略空间如下所示：
sscmap＝{1.[anoyvertex(pg,ac6) deledge(pg,<ac4,en5>)
deledge(pg,<ac2,en3>) addedge(pg,<en4,en5>)
addedge(pg,<ac2,ac4>)],
2.[s1 addedge(pg,<en4,en6>) addedge(pg,<ac1,ac3>)],
3.[s1 addedge(pg,<ac3,en5>) addedge(pg,<en0,en3>)],
4.[s1 addedge(pg,<ac3,ac5>) addedge(pg,<ac1,ac3>)],
5.[s1 addedge(pg,<ac3,en6>) addedge(pg,<ac1,en3>)],
6.[delvertex(pg,ac6) delvertex(pg,en5) deledge(pg,<ac2,en3>) addedge(pg,<en7,en3>) addedge(pg,<ac4,ac5>) addedge(pg,<ac2,ac4>)],
7.[s2 addedge(pg,<ac0,en3>) addedge(pg,<ac4,en6>) addedge(pg,<ac1,ac3>)],
8.[delvertex(pg,ac6) delvertex(pg,en7) delvertex(pg,en5) delvertex(pg,ac5) delvertex(pg,ac3) addedge(pg,<ac0,en3>) addedge(pg,<ac4,en6>) addedge(pg,<ac1,en4>)],
9.[s3 addedge(pg,<ac0,ac3>) addnullvertex(pg,acn1) addedge(pg,<ac4,acn1>) addedge(pg,<acn1,en6>) addedge(pg,<ac1,ac4>)],
10.[delvertex(pg,ac0) delvertex(pg,en7) delvertex(pg,ac6) delvertex(pg,en5) delvertex(pg,ac5) delvertex(pg,en6) delvertex(pg,ac3) addedge(pg,<en0,en3>) addedge(pg,<en0,en1>) addnullvertex(pg,acn1) addedge(pg,<ac4,acn1>) addedge(pg,<en0,en4>)],
11.s4 addnullvertex(pg,acn1) addedge(pg,<en0,acn1>) addedge(pg,<acn1,en3>) addedge(pg,<acn1,en1>) addnullvertex(pg,acn2) addedge(pg,<ac4,acn2>) addedge(pg,<ac1,en4>)]}
如以上过滤策略空间所示，为方便描述，将相同的过滤操作以si替代，如策略1的过滤操作为anoyvertex(pg,ac6) deledge(pg,<ac4,en5>) deledge(pg,<en2,ac2>)，策略2的过滤操作与其相同，将其简写为s1，策略6与策略7同理。执行策略1及策略6所得过滤视图分别如图4及图5所示，实现需求r2得到的过滤策略空间其中一张起源过滤视图如图6所示。
步骤6：更新起源图，得到起源过滤视图，并按照已有的起源过滤视图评估模型定量地评估起源过滤视图的效用和安全，生成起源过滤报告。
1.一种基于过滤原语的起源过滤框架，其特征在于，包括以下步骤；
步骤1：定义具体的原语，作为改造起源图的最小操作；
步骤2：形式地定义起源图的结构约束和过滤约束；
步骤3：检查待过滤的起源图，确保其为符合标准化起源模型及其模型约束的有向无环图；
步骤4：声明起源过滤需求，即起源图中待过滤的敏感信息；其中，过滤需求中待过滤的敏感元素用起源图中的节点表示，过滤需求中待过滤的直接或间接依赖关系用起源图中的节点对表示；
步骤5：根据过滤需求，构造过滤策略空间；
步骤6：更新起源图，得到起源过滤视图，并按照已有的起源过滤视图评估模型定量地评估起源过滤视图的效用和安全，生成起源过滤报告。
2.根据权利要求1所述的一种基于过滤原语的起源过滤框架，其特征在于，所述步骤1具体操作为：
(1)deledge(pg,<u,v>)：删除边e＝<u,v>；
(2)delvertex(pg,v)：删除节点v；
(3)addedge(pg,<u,v>)：增加边e＝<u,v>；
(4)addnullvertex(pg,v)：增加空节点v；
(5)anoyvertex(pg,v)：匿名节点v。
3.根据权利要求1所述的一种基于过滤原语的起源过滤框架，其特征在于，所述步骤2具体操作为：
模型约束1：起源图中不允许出现孤立节点；
模型约束2：一个实体不能由两个以上的活动产生；
模型约束3：当一个直接依赖关系可由其它直接依赖关系推理得到时，应在起源图中省略相应的边；
模型约束4：起源图中不允许出现环路，可利用拓扑排序算法检测起源图中是否有环；
过滤约束1：过滤视图不应引入假依赖；
过滤约束2：不应将已过滤的敏感元素恢复。
4.根据权利要求1所述的一种基于过滤原语的起源过滤框架，其特征在于，所述步骤4中声明过滤需求时应注意：
(1)敏感信息为节点时，需要说明节点的标识符或部分属性(attributes)，当节点类型是活动时，还可以指出活动发生的起止时间(starttime和endtime)；
(2)敏感信息为依赖关系时，无论直接依赖关系还是间接依赖关系，均需指明该依赖关系所依附的两个起源元素的标识符或部分属性。
5.根据权利要求1所述的一种基于过滤原语的起源过滤框架，其特征在于，所述构造过滤策略空间具体包括：
步骤5.1：根据过滤需求，选择恰当的过滤原语，如deledge、delvertex、anonyvertex，根据过滤规则，构造敏感信息过滤原语集合p；
步骤5.2：面向溯源需求，选择恰当的恢复原语，如addedge、addnullvertex，根据恢复规则，构造恢复起源图中被意外打断的连通路径的恢复原语集合q；
步骤5.3：构造过滤策略空间pm×qn，检查过滤策略是否符合给定约束，形成合法的过滤策略空间s，其中m表示采用不多于m个过滤原语，n表示采用不多于n个恢复原语，则过滤策略空间中的每条过滤策略，由不多于m n个恢复原语构成，m和n的值由过滤规则和恢复规则确定；
步骤5.4：检查过滤策略空间s中的每条过滤策略是否符合模型约束和过滤约束。
6.根据权利要求5所述的一种基于过滤原语的起源过滤框架，其特征在于，所述步骤5.1过滤规则如表所示：
过滤规则
7.根据权利要求5所述的一种基于过滤原语的起源过滤框架，其特征在于，所述步骤5.2的恢复规则如表所示：
恢复规则
