构建ADG-H时,需要在DG构建过程的基础上计算节点哈希值,对根节点进行数字签名并为以后验证对象的提取工作做准备,步骤如下:

(1)运用DG构建算法构建ADG-H。与DG不同的是,ADG-H为每个节点增加一个哈希值项。

(2)增加根节点层。ADG-H的顶层现为Layer 1,为方便以后验证对象的提取,在Layer 1前增加一层Layer 0,并为该层增加一个节点 N_root作为整个ADG-H的根节点,Layer 1中所有节点皆为其子节点,该节点各分量的值置为整数或浮点数中的最大值。 N_root及其值为参与运算的各方所共享。

(3)计算哈希值。从ADG-H的最后一层依次向前直至Layer 0,为每层中的每个节点计算哈希值,如果某节点没有子节点,则该节点的哈希值为其值的哈希;如果有子节点,则该节点的哈希值为其值与其所有子节点的哈希值的连接的哈希,连接时按照子节点的序号从小到大排列。

(4)数字签名。对 N_root的哈希值(记为 h_root)进行数字签名,得到 sig(h _root )。

在ADG-H中,当插入、删除、修改等数据更新发生时需要进行数据更新和哈希更新。数据更新按照DG更新算法进行;随后进行哈希更新,重新计算在数据更新阶段受影响的各节点的哈希值。

以插入为例,首先进行数据更新。设要插入的数据为 N₁,首先按照DG的插入算法执行插入:经过搜索, N₁应该插入到Layer d中,将Layer d中受 N₁支配的节点插入到Layer d+1中,对Layer d+1及以后的各层做相同处理,设最终受影响的层为Layer u。简要插入算法见算法1,详见文献^{[ 4]}。

算法1 Insert Algorithm.

输入:DG;要插入的节点N_I;

输出:N_I所在层d;插入到最后一层的节点集合S;最终影响的层编号u;

①初始化:建立两个空集合S和T;

②经过搜索,N_I应该插入到Layer d中;S={N_I};m=d;

③将集合S中每个节点的子节点放到T中;

④将T中的每个节点从Layer m中删除;

⑤将S中的节点插入Layer m中,重新计算Layer m-1和Layer m两层节点间父子关系;

⑥如果T为空,插入过程结束,转⑦;否则,清空S,将T中节点放到S中,m加1,如果m值大于当前DG最后一层的编号,新建一层Layer m,转至③;

⑦插入过程结束,u=m,返回S、d和u。

数据插入完成后进行哈希更新,见算法2。首先计算插入到Layer u中的节点的哈希值,然后计算这些节点的父节点的哈希值,依次向前逐层更新各层中受影响的节点的父节点的哈希值,直至最后到达根节点 N_root,更新 N_root的哈希值。

算法2的时间复杂度在最坏时为 O(| D|),即将ADG-H中每个节点的哈希值重新计算一次,其中 D表示数据集的规模。

算法2 UpdateHash Algorithm.

输入:DG;节点集合S;

输出:根节点的数字签名sig(h_root);哈希值更新过的节点集合U;

①初始化:建立空集合T,U;

②重新计算S中每个节点的哈希值;U=U∪S;

③将S中每个节点的所有父节点放到T中;

④清空S,将T中所有节点放到S中,清空T;

⑤如果S不为空,转至②;

⑥重新计算根节点的数字签名sig(h_root);

⑦哈希值更新过程结束,返回sig(h_root)和U。

ADG-H中的删除和修改与插入的过程类似,首先执行DG中的删除和修改算法,将最后一层中受影响的节点返回,然后执行算法2,更新相关节点的哈希值并重新计算根节点的数字签名。

收到客户端查询请求后,服务提供商端执行查询算法得到查询结果 RS。但是由于服务提供商端可能会遭到攻击,数据可能会被篡改,服务器也可能由于某种原因而没有忠实地执行查询,导致客户端可能收到不正确的查询结果。这就需要服务提供商根据 RS从ADG-H中提取验证对象 VO,以供客户用来对 RS的正确性进行验证。

设 RS为{ N_root, R₁, R₂,…, R_k},为了表达顺畅, RS中的 N _root也记为 R_0,即 RS表示为{ R₀, R₁, R₂ ,…, R_k },从 R₀到 R_k按照得分从高到低排序。在MH-Tree和MR-Tree的查询结果中一定存在叶子节点,而验证支配图的查询结果中则可能不存在叶子节点,因此,ADG-H中验证对象的提取与MH-Tree和MR-Tree相比更为复杂一些。

从验证支配图中提取的验证对象只要能够同时满足真实性和有效性,即可以实现对 的验证。

真实性:对于 R_m∈ RS, m为整数,且0≤ m≤ k, R _m为真实的、来自数据所有者,没有被篡改、不是伪造的。

有效性:对于 R₀∈ RS, R₀为整个支配图中得分最高的点;对于 R_m+1∈ RS, m为整数,且0≤ m≤ k, R _{m +1}为整个支配图中 R _m后得分最高的点。

为满足真实性和有效性要求,经过对验证对象的提取过程进行观察和分析,给出定理1用以指导验证对象的提取。

定理1 对于偏好top- k查询结果 RS中的每个节点 R,将 的所有子节点放到 VO中,可以同时满足真实性和有效性。

证明(真实性) 在验证时,结合 VO从 RS中处于最后一层的节点开始逐层计算各层节点的哈希值,用最终得到的 R₀的哈希值对数字签名进行验证。如果验证通过,表明返回的 RS和 VO中所有节点的值为正确的;否则表明 RS或 VO中存在不正确的节点。证毕。

证明(有效性) 当 m=0时,考虑 R₀。节点 R₀即 N _root的值为参与计算的各方所共知,且 R₀的值是整个支配图中最大的,显而易见,对所有查询 R₀都必然在 RS中。

当 m=1时,考虑 R₁。由于Layer 0中只有一个节点 R₀,则 R₁必然在Layer 1中,且为 R₀的子节点。由于已经将 R₀的所有子节点放到 VO中,可以计算出 R₀的每个子节点的得分,能够表明 R₁为 R₀后整个支配图中得分最高的点。

当 m=2时,考虑 R₂。可以区分为两种情况:① R₂为 R₀的子节点;② R₂为 R₁的子节点。根据支配图的原理,如果某节点在 RS中,则该节点至少有一个父节点在 RS中^{[ 4]}。而在 RS中, R₂前只有 R₀和 R₁, R₂要么为 R₀的子节点,要么为 R₁的子节点,不存在第三种情况。因此,不论 R₂为 R₀或 R₁的子节点,在处理 R₀和 R₁时已经将 R₀和 R₁的所有子节点放到 VO中,所以能够表明 R₂为 R₁后整个支配图中得分最高的点。

当2< m≤ k时,对于 R_m。 R_m必然为{ R_i |0≤i≤ m-1}中某节点的子节点,此 m个节点的子节点都已经放到 VO中,所以能够表明 R_m为 R_m-1后整个支配图中得分最高的点。证毕。

重画的文献^{[ 4]}中的图1如图2所示,其中图2(a)为数据集,图2(b)为增加了根节点 N _root的DG,根节点编号为-1,所在层为Layer 0。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 支配图示例Fig.2 Example of dominant graph

用函数 F=0.6* X+0.4* Y进行top-2查询, RS为{-1,4,6}, VO为{-1(3,4,11),4(1,6),6(2)}。

用函数 F=0.5* X+0.5* Y进行top-4查询, RS为{-1,4,3,6,11}, VO为{-1(3,4,11),4(1,6),3(1,5),6(2),11(1)}。

在ADG-S中,当插入、删除、修改等数据更新发生时,同样需要进行两种类型更新:数据更新和数字签名更新。数据更新按照DG的更新算法执行;数字签名更新重新计算数据更新阶段受影响的节点的数字签名。

以插入为例。首先更新数据。设插入数据为 N_I执行算法1后,得到 N_I 所在层的编号 d、最终影响到的层编号 u和插入到最后一层的节点集合 S。然后更新数字签名,重新计算在插入过程中受影响的节点的数字签名,见算法3。先计算插入到Layer u中的节点的数字签名,然后计算这些节点的父节点的数字签名,逐层计算各层中受影响的节点的父节点的数字签名,直至最后到达Layer d-1,更新 N_I的父节点数字签名,数字签名更新结束。算法3的时间复杂度在最坏情况下为O(|D|),即将验证图中每个节点的数字签名重新计算一次。

算法3 UpdateSignature Algorithm.

输入:Insert算法的返回值 S和d

输出:新计算过数字签名的节点集合 P

①初始化:建立两个空集合P和T,设变量m为S中节点所在层的编号;

②重新计算S中每个节点的数字签名,P=P∪S;

③将S中每个节点的所有父节点放到T中;

④清空S,将T中节点放到S中;

⑤如果m等于d-1,数字签名更新结束,转⑥;否则m减1,转②;

⑥返回集合P。

计算节点 N的数字签名时,如果 N已有数字签名,需将现有的数字签名作为 N值的一部分参与计算。这样,如果多次更新影响到某连续监控的结果或验证对象,但服务器端没有将某次更新发送给用户,客户会检测到。

ADG-S中的删除和修改与插入类似,首先执行删除和修改算法,然后执行算法3,重新计算删除和修改过程中受影响的相关节点的数字签名。

定理1对使用ADG-S时验证对象的提取依然适用。用户注册连续监控后,服务提供商执行查询算法,并提取验证对象,保存查询结果和验证对象,并将查询结果和验证对象发送到Client。在以后的数据更新过程中,如果某次更新影响到某监控的结果或验证对象,则将受影响的节点信息发送到相应的Client,否则不发送任何信息。与ADG-H相比,ADG-S只有在必要时才发送信息,大大减少了不必要的网络传输。

构建实验以DG的构建时间为基准,结果如图3所示。由于MD5的效率较高,选用MD5作为哈希函数构建ADG-H,所用时间略多于DG,只有数据量很大时构建ADG-H所用时间才明显多于DG。构建ADG-S时选用RSA作为数字签名方案,由于RSA数字签名方案代价较高,所用时间明显比DG和ADG-H都多。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 构建时间比较Fig.3 Comparison of construction time

更新实验同样以DG的更新数据为基准,图4为插入所用时间,图5为删除所用时间。可以看出,ADG-H的更新时间比DG多,ADG-S的更新时间最多。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 插入所用时间Fig.4 Wasted time of inserting

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 删除所用时间Fig.5 Wasted time of deleting

图6为不同查询比较,设 k=200, F₁=(0.3,0.7), F₂=(0.9,0.1), F₃=(0.5,0.5)。可以看出,ADG-H中,每一次更新都会影响连续监控的验证对象,从而引起一次网络传输;ADG-S中,只有当本次更新影响到连续监控的结果或验证对象时,才进行一次网络传输,网络传输量明显比ADG-H少得多。图7为不同 k,对 k分别取100、200、500,设 F=(0.5,0.5),可以看出 越大,ADG-S中网络更新次数越多。

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 不同查询比较Fig.6 Comparison of different query

图7

Fig.7

	Figure Option ViewDownloadNew Window
	图7 不同 k比较Fig.7 Comparison of different k