2. 内蒙古科技大学 网络中心, 内蒙古 包头 014010
2. Information and Network Center, Inner Mongolia University of Science and Technology, Baotou Nei Mongol 014010, China
对于数据库外包服务或云计算服务, 数据所有者 (Data Owner, DO) 失去对数据的直接操作和控制的能力, 随之产生诸多的数据安全隐患问题[1]。例如, 在基于位置服务 (Location-Based Service, LBS) 查询应用中, 服务提供商 (Services Provider, SP) 是不可信的, 商家为了赢得更多利益, 在用户 (Client) 不知情的情况下, 与服务提供商相互勾结, 篡改用户的查询结果或返回不完整的结果, 损害用户的权益。因此, 如何向用户提供真实结果以及验证结果的正确性和可靠性显得尤为重要。
目前, 已经存在的查询验证方法主要分为两类[2-12]:基于数字签名技术和基于Merkle哈希树 (Merkle Hash Tree, MHT)。Pang等[3-4]提出了签名链的方法, 将相邻数值连接形成一个签名, 通过重新计算结果集里每个数值的签名并与标记的该数值签名匹配, 实现完整性的验证。值得注意的是, 数字签名的方法在构建、存储和更新数据索引时会造成较大的计算开销。为了解决这个问题, Narasimha等[5]提出数字签名聚合和链接的方法。由于传统签名验证的方法都是验证一维数据的可靠性, Cheng等[6]提出了基于空间分割的VKD-tree (Verifiable KD-tree) 和基于数据分割的VR-tree (Verifiable R-tree) 用于验证多维数据库查询; MHT最广泛的应用就是与其他索引结构相结合。对于一维数据查询验证, Li等[7]提出了MB-tree, 通过在原始B+-tree的基础上, 每个节点上都包含了一个hash值, hash值的计算与MHT相似。为了进一步减小验证对象 (Verification Object, VO) 的大小, Li等[7]又提出了MB-tree的变形EMB-tree。而针对多维数据查询验证, Yang等[8-9]在MHT和R*-tree的基础上提出了MR-tree。相对于VR-tree, MR-tree在索引构建时间、存储空间消耗、查询处理和查询验证等性能方面都有了较大的提升。与此同时, Mouratidis等[10]提出了一种部分实体化摘要的策略 (Partially Materialized Digest, PMD), 可以与多种索引验证结构结合, 既可以应用于一维的数据查询验证, 同时也适用于多维空间查询验证。谢晴晴等[11]利用PDM策略改进了MHT, 实现了数据流范围查询验证。除此之外, Hu等[12]实现了在进行范围查询验证时, 对查询数据的隐私保护。
本文在MR-tree的研究基础上, 主要的工作包括以下三个方面:1) 提出了一种改进的验证方案, 通过建立一种新的MGR-tree验证索引结构, 提升了MR-tree在验证时间以及验证对象大小等方面的性能;2) 在此基础上, 提出了一种优化的索引结构MHGR-tree, 通过用Hilbert曲线遍历Grid-tree, 降低了搜索空间的维度, 从而加快了查询和验证的过程;3) 基于Hilbert曲线一维线性的特性, 提出一种优化的过滤策略, 进一步加快了验证的过程。
1 背景知识定义1 单向哈希函数。给定哈希函数H(·), 其作用于任意长度的字符串消息M, 并返回固定长度的输出H(M)。它满足两个性质:1) 单向性。给定H(·) 和H(M), 反向计算M是不可行的。2) 无碰撞性。给定M, 找到消息M′满足H(M)=H(M′) 是不可行的。
例如, 目前最常用的哈希函数是SHA1, 其固定输出160 bit字符串消息。
定义2 数字签名。签名者产生一对密钥 (私有密钥和公有密钥), 数据所有者利用私有密钥对数字消息签名, 并将公有密钥公开发布, 消息接收者利用公有密钥对接收到的消息进行可靠性验证。
例如, 目前最常用的公钥加密算法是RSA (Rivest、Shamir和Adleman), 其产生128 B的消息签名。
定义3 Merkle哈希树 (MHT)。MHT [2]是一棵二叉树, 通过分层的自底向上计算所有节点的哈希值, 并对根节点的哈希值进行数字签名。
MHT的结构如图 1所示, 其中涵盖了四条数据记录d1~d4, MHT的节点哈希值计算如下:1) 如果节点N是叶子节点, 其哈希值为H(dN), dN是数据记录。2) 如果节点N是非叶子节点, 其哈希值为H(dL|dR), dL和dR分别为节点N的左、右孩子节点的哈希值, “|”为字符串连接符。对于给定的范围查询Q(如图 1中矩形框所示), 覆盖数据记录d1和d2, 且d1和d2分别为范围的左右边界。VO (图 1中深色节点) 包含了从根节点到左 (右) 边界的路径上节点的所有兄弟节点的摘要 (如图节点N2)。通过VO和查询结果重新构建根节点的哈希值, 如果与数据所有者签名的哈希值匹配, 则查询结果是正确的, 没有被篡改。
本章主要介绍了MGR-tree和MHGR-tree索引结构的构建算法, 并描述了在MHGR-tree上的查询和验证的过程。
2.1 MGR-tree在构建R-tree时, 不同节点间的最小边界矩形 (Minimum Bound Rectangle, MBR) 会出现相交的情况;而且随着数据量增大, 节点间的MBR相交数目会增多。因此在执行范围查询时, 会访问不必要的节点, 影响查询的效率。若R-tree的结构比较大时, 其产生的验证对象VO也比较大, 影响验证的效率。而VO的大小是系统最重要的评价准则, 它衡量了服务提供商到客户端的传输代价, 是系统性能的决定因素。通过实验观察, 把R-tree拆分成多棵结构较小的R-tree时, 对产生的验证对象的大小有明显的影响, 结果如图 2所示 (其中, 数据基数为2×106, 26×26和27×27表示分别将R-tree拆分成26×26和27×27棵小的R-tree)。
从图 2中看出, 随着查询范围的增大, 验证对象VO包含的节点数目不断增加。当查询范围大于5%时, 基于拆分方法产生VO的大小很大程度上小于MR-tree的方法, 并且随着拆分的分辨率越高, 产生的VO越小。基于上述的实验事实, 提出了一种新的验证索引结构MGR-tree, 该索引结构结合了Grid-tree和R-tree的结构特点, 实现了对R-tree的有效划分。MGR-tree的索引结构如图 3所示。
MGR-tree首先利用Grid-tree将搜索空间划分网格, 并将空间数据点映射到相应的网格内, 然后用R-tree索引相应网格内的数据点。MGR-tree节点摘要的计算方法同文献[7]相似, 不同的是对Grid-tree节点摘要的处理。对于叶子节点, 将节点内嵌套R-tree根节点摘要直接作为叶子节点摘要; 而对于非叶子节点, 则是将该节点的孩子节点摘要和节点网格区域连接, 并利用哈希函数H(·) 计算摘要。MGR-tree的构建过程如算法1所示。
算法1 MGR-tree的构建算法。
输入:空间区域R、空间数据点集P。
输出:MGR-tree索引。
1) 将空间区域进行网格划分 (h为预设最大层数), 设置整个空间区域为根节点。
2) for (Grid-tree的层数≤h) //在区域网格上建立Grid-tree
3) 依次将每个未划分的节点区域分层。
4) 将空间数据点依次映射到相应的网格内 (Grid-tree的叶子节点内)。
5) if节点内的点的数目不为0
6) 在每个网格对应的节点内嵌入R-tree。
7) 从MGR-tree的叶子节点层开始, 直至根节点, 计算每个节点的摘要。
8) 返回MGR-tree索引。
2.2 MHGR-tree虽然MGR-tree在VO的大小和验证效率等方面的性能都有了提高,尤其是减小的VO, 不仅缩短了查询验证时间, 同时也降低了传输开销。但是, 客户端在验证时, 仍然要遍历VO中所有节点的MBR或节点的网格区域判断是否与查询范围相交。而且, 随着空间维度的增加, 查询判断和验证的代价都将增大。于是, 在MGR-tree的基础上, 提出了优化的MHGR-tree索引结构。MHGR-tree是结合了MGR-tree和Hilbert曲线的一种索引结构, 主要是通过将空间网格用Hilbert曲线遍历, 把Hilbert值映射到Grid-tree的每个节点, 并在Grid-tree的每个非空叶子节点中嵌入一棵R-tree。MHGR-tree的索引结构如图 4所示。
MHGR-tree通过Hilbert曲线将Grid-tree的多维空间降低到一维空间, 并且通过Hilbert曲线的遍历, 每个节点都与相应的网格区域Hilbert值对应。如图 4所示, MHGR-tree的根节点对应网格区域为整个空间, 即映射的Hilbert值区间为[0, 15];Grid-tree的叶子节点对应最小网格划分 (如N33), 其Hilbert值区间为[10, 10]。
当创建MHGR-tree时, 在Grid-tree的基础上, 计算每个节点的Hilbert值范围 (Node Hilbert Range, NHR), 与MGR-tree不同的是摘要的计算。对MHGR-tree节点摘要的计算分为两个部分:Grid-tree和R-tree。其中, R-tree中的节点摘要计算方法与MGR-tree相同。对Grid-tree的叶子节点L, 其摘要DigL计算为:
$ Di{g_L} = H\left( {Dig\left( {{\rm{Root}}} \right)|Hil\left( L \right)} \right) $ |
其中:Dig(Root) 为叶子节点内嵌入R-tree根节点的摘要, Hil(L) 为叶子节点L所覆盖网格的Hilbert值范围。对Grid-tree的非叶子节点, 其摘要DigI计算为:
$ Di{g_I} = H\left( {Di{g_1}\left| \ldots \right|Di{g_4}|Hil\left( I \right)} \right) $ |
其中:Dig1~Dig4表示该非叶子节点的孩子节点的摘要; Hil(I) 表示非叶子节点I所覆盖网格的Hilbert值范围。在迭代计算到根节点后, 利用数据所有者的私有密钥对根节点的摘要进行签名。
2.3 查询处理基于MHGR-tree进行多维范围查询时, 主要考虑两个部分:Grid-tree和R-tree的查询过程。分别在两棵树上利用栈进行深度优先遍历, 判断是否与查询范围相交, 并将查询结果和验证时所必需的信息返回。VO的计算是在查询的过程中进行的。VO中主要包含了在查询过程与查询范围不相交的节点信息 (对于Grid-tree, VO包含了节点摘要和Hilbert值范围; 对于R-tree, 则包含了节点摘要和MBR)。具体过程如算法2所示。
算法2 MHGR-tree的查询和创建VO算法。
输入:空间查询范围R, MHGR-tree索引结构。
输出:查询结果集Result Set和VO。
1) 将空间查询范围R映射为Hilbert值范围 (Hilbert Range, HR)
2) 将MHGR-tree根节点入栈S
3) While S非空
4)S.pop (); //出栈
5) if Grid-tree节点是非叶子节点
6) if Grid-tree节点的NHR与HR相交
7)S.push (节点的孩子节点); //入栈
8) else将节点的摘要和NHR加入VO中
9) if Grid-tree节点是叶子节点
10)S.push (R-tree根节点) //入栈
11) if R-tree节点是非叶子节点
12) if节点MBR与范围R相交
13)S.push (节点的孩子节点); //入栈
14) else将节点的摘要和MBR加入VO中
15) if R-tree节点是叶子节点
16) if节点MBR与范围R相交
17) 将包含于范围R内的点P加入Result Set
18) else将范围外的点P的摘要和MBR加入VO中
19) Return Result Set and VO
算法2描述了范围查询的完整过程, 首先将查询范围R映射为Hilbert范围 (第1) 行), 从MHGR-tree的根节点开始判断是否与查询范围相交 (第2)~4行))。在Grid-tree上, 通过判断节点的Hilbert值范围NHR与查询范围HR是否相交 (第6) 行), 相对于多维属性的相交判断, 一维Hilbert值的比较可以在一定程度上加快查询。若相交, 则将该节点的孩子节点入栈 (第7) 行); 否则, 将该节点的摘要和NHR加入VO (第8) 行)。在R-tree上, 则通过判断节点的MBR是否与查询范围R相交。若与非叶子节点相交, 则将该节点的孩子节点入栈 (第11)~13) 行); 否则, 将该节点的摘要和MBR加入VO (第14) 行)。若与叶子节点相交, 则将包含于范围R内的所有点加入结果集Result Set (第15)~17) 行); 否则, 将位于范围R外的所有点的摘要和MBR加入VO中。以图 4为例, 查询Q从MHGR-tree的根节点开始迭代的访问与深色矩形范围框相交的节点{N, N3, N33, N34, R1, R2, R5, R6}(注:图中只标记了与Q相交的一棵R-tree, 未标记的R-tree的访问节点未列举)。访问结束后, 验证对象VO包括{(N1.H, N1.NHR), (N2.H, N2.NHR), (N4.H, N4.NHR), (N31.H, N31.NHR), (N32.H, N32.NHR), (R3.H, R3.MBR), (R4.H, R4.MBR)}和结果集{P5, P6, P7, P8}。服务提供商将VO、Result Set和根节点摘要签名传输给客户端。
2.4 查询验证在验证查询结果时, 客户端需要对结果进行可靠性验证, 主要包括以下两个方面:1) 完整性。所有被查询范围覆盖的点P都包含在结果集Result Set中, 没有被遗漏。2) 健壮性。返回的结果集中所包含的结果都是真实的结果, 且没有被篡改。客户端借助验证对象VO对查询结果进行上述两方面的验证。
算法3 VO验证算法。
输入:Result Set和VO。
输出:Verification Result。
1) for (从R-tree的叶子层开始至R-tree根节点所在层)
2) 计算R-tree每一层的节点的摘要至根节点
3) for (从Grid-tree的叶子层开始至Grid-tree根节点所在层)
4) 计算Grid-tree每一层的节点的摘要至根节点
5) 利用DO的公钥密匙解密MHGR-tree根节点摘要的签名
6) if (计算的根节点摘要与DO签名的摘要匹配)
7) return true
8) else return false
算法3描述了查询结果健壮性验证的过程。以图 3和图 4为例, 客户端首先扫描VO和Result Set, 从R-tree的叶子层开始, 通过{P5, P6}和{P7, P8}可以得到R5和R6的摘要和MBR。依次向上, 通过VO中的{R3, R4}和计算的R5和R6可以得到R1和R2的摘要和MBR。最后计算得出R-tree根节点的摘要。在Grid-tree上, 计算方法与R-tree类似, 将R-tree节点的MBR用Grid-tree节点的Hilbert值范围NHR替代, 然后迭代计算MHGR-tree根节点的摘要, 并与数据所有者签名的摘要进行匹配。而在完整性验证时, 需要判断:1) Result Set中的每个点都在查询范围R内;2) VO中的节点的NHR或MBR都不与查询范围R相交。
在验证查询结果的完整性和健壮性时, 如果对于Result Set中的一点P被篡改, 而P是计算根节点摘要时的组成部分, 如果P的值是错误的, 根据哈希函数的无碰撞性, 计算得到的MHGR-tree根节点摘要与DO签名的摘要必然不匹配, 故不满足健壮性。如果对于一点P, P包含于查询范围R内, 但Result Set不包含P, 在满足健壮性前提下, P包含于VO中, 故不满足完整性验证的条件。若P不包含于查询范围R内, 但Result Set包含P, 故也不满足完整性验证的条件。
3 优化策略在验证查询结果的可靠性时, 需要判断VO中的Grid-tree的节点NHR不与查询范围的HR相交。如图 5所示, 查询Q所覆盖网格对应的Hilbert值范围为[27, 28], 查询产生的Grid-tree上的验证对象VO为集合{N4, N34, N33, N324, N323, N322, N313, N314, N311, N2, N1}中每个节点的摘要和NHR, 客户端需要依次判断节点NHR是否与查询Q的HR相交。实际中, 查询范围只覆盖了少数的几个网格, 因此VO中包含了较多的冗余节点, 而造成验证时间变长和验证效率下降。
于是, 本文提出了一种优化的过滤策略, 通过该策略可以减少客户端的比较次数, 缩短验证时间。从图 5可看出, 每个空间网格都被Hilbert曲线遍历并被赋予一个Hilbert值, 从而将具有空间位置关系的网格转换为一维线性位置关系的网格。在判断节点与查询Q是否相交时, 将空间坐标的判断转换为一维Hilbert值的比较, 从而也加快了比较的速度, 缩短了验证时间。值得注意的是, 通过Hilbert曲线的映射, 每个空间网格间都具有一种线性关系, 例如N4、N3和N2的Hilbert值范围分别为[0, 15]、[16, 31]和[32, 47], 它们之间的线性关系为N4 < N3 < N2。而在产生的验证对象中, N322和N313的Hilbert值范围分别为[26, 26]和[29, 29], 介于查询Q的Hilbert值范围[27, 28]的两端, 且它们之间的线性关系为N322.NHR < HRmin < HRmax < N313.NHR, 即N322.NHR和N313.NHR分别为下界和上界。若VO中节点的NHR小于N322。NHR, 则该节点NHR一定小于HRmin; 反之, 若VO中节点NHR大于N313.NHR, 则该节点的NHR一定大于HRmax。那么可以验证, N322。NHR < HRmin, 即N322.NHR不与查询范围HR相交, 故VO中所有节点NHR小于N322.NHR且都不与HR相交; 反之, HRmax < N313.NHR, 即N313.NHR不与查询范围HR相交, 故VO中所有节点的NHR大于N313.NHR且都不与HR相交。在验证过程中, 通过该过滤策略, 没有必要再验证位于上界和下界之外的节点NHR与查询范围HR是否相交, 因此可以减少比较次数, 从而有效缩短验证时间。
4 实验与分析为了评价提出的MGR-tree和MHGR-tree的表现, 本文在一个真实的数据集CAR[7]上进行测试, 其中CAR为California的道路分割, 包含了2 096 702个不同位置的坐标点。在实验中, 将这些坐标点当作不同物体的位置。实验在配置为Intel Core 2 Duo CPU E7500 2.93 GHz和8 GB内存的Windows XP系统上运行。系统代码用Java编写, 哈希函数采用160 bit的SHA1算法, 数字签名采用128 B的RSA算法。在构建MGR-tree和MHGR-tree时, Grid-tree的默认的树的高度为7, 查询范围默认为10%的空间覆盖率, R-tree的节点大小设置为4 096 B。
实验中, 主要针对如下两个方面进行测试:1) 查询范围对系统性能的影响; 2) 数据集大小对系统系能的影响;并且系统性能主要包含了VO的大小和验证时间等方面。
实验主要与文献[7]方法 (简称MR) 进行对比, 将本文提出的方法称为MGR和MHGR。
随着用户查询范围的改变, 系统性能会发生变化。实验中测试了当查询范围在整个空间的1%至20%之间变化时, VO大小和验证时间的变化, 其中Grid-tree树高h=7, 数据量大小为2×106。从图 6可以看出, 当查询范围很小时, MGR和MHGR较MR表现出了一定的优势, 随着查询范围的增大, 这种优势更加明显。尤其是, 当查询范围发生变化时, MR的VO大小和验证时间发生明显改变, 而MGR和MHGR与之相反。例如, 当查询范围分别为1%和20%时, MR的VO大小和验证时间的差值分别为756 KB和114 ms, 而MHGR仅为474 KB和16 ms。值得注意的是, 在最好情况下, MHGR的VO大小和验证时间仅为MR的63%和19%。
如图 7所示, 当数据量比较小时, MGR和MHGR在查询时间、VO大小和验证时间等方面已经明显比MR要好。当数据量很大时, MGR和MHGR的优势更加明显, 都保持了较低的水平。尤其是当数据量为400 000时, MHGR的VO大小和验证时间仅为MR的33%和26%。
随着移动互联网络的普及和高速发展, 例如4G网络等, 极大地推动了基于位置服务 (LBS) 的进展。而面对客户日益复杂的查询服务需求, 数据所有者已无法满足要求。为了更好地解决这个矛盾, 将数据库外包给LBS提供商成为了必然的选择。但是, 在LBS提供商给客户提供更高级的查询服务的同时, 由于LBS提供商是不受信任的, 为了提供可靠的查询服务, LBS服务商应以一种可验证的方式提供查询服务, 即客户可以对查询结果进行可靠性验证。在大数据的背景下, 如何快速响应查询服务请求, 以较小的数据传输代价给客户提供更可靠的查询结果变得至关重要。针对上述问题, 提出新的索引结构MGR-tree, 结合了Grid-tree和R-tree的特点, 极大地改善了VO过于庞大的问题, 降低了服务提供商和客户之间的传输消耗, 并且有效地缩短了验证时间;在此基础上, 通过Hilbert的降维特性, 还提出了优化的MHGR-tree, 并提出了一种过滤策略, 有效地改善了系统性能。实验结果表明, 在数据量和查询范围都比较大时, MGR-tree和MHGR-tree在VO大小和验证时间等方面都表现出了明显的优势。
[1] | DEVANBU P, GERTZ M, MARTEL C, et al. Authentic third-party data publication[M]//THURAISINGHAM B, VAN DE RIET R, DITTRICH K R, et al. Data and Application Security. Berlin: Springer, 2000: 101-112. |
[2] | MERKLE R C. A certified digital signature[C]//CRYPTO 1989: Proceedings on Advances in Cryptology. Berlin: Springer, 1989: 218-238. http://www.springerlink.com/index/dyxfp2kd5n6t7fvl.pdf |
[3] | PANG H H, TAN K L. Authenticating query results in edge computing[C]//Proceedings of the 20th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2004: 560-571. http://ieeexplore.ieee.org/abstract/document/1320027/ |
[4] | PANG H H, JAIN A, RAMAMRITHAM K, et al. Verifying completeness of relational query results in data publishing[C]//SIGMOD 2005: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2005: 407-418. http://dl.acm.org/citation.cfm?id=1066204 |
[5] | NARASIMHA M, TSUDIK G. DSAC: integrity of outsourced databases with signature aggregation and chaining[C]//CIKM 2005: Proceedings of the 14th ACM International Conference on Information and Knowledge Management. New York: ACM, 2005: 235-236. http://dl.acm.org/citation.cfm?id=1099604 |
[6] | CHENG W, PANG H H, TAN K. Authenticating multi-dimensional query results in data publishing[C]//DBSEC 2006: Proceedings of the 20th IFIP WG 11.3 Working Conference on Data and Applications Security. Berlin: Springer, 2006: 60-73. http://link.springer.com/chapter/10.1007/11805588_5 |
[7] | LI F, HADJIELEFTHERIOU M, KOLLIOS G, et al. Dynamic authenticated index structures for outsourced databases[C]//SIGMOD 2006: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2006: 121-132. http://dl.acm.org/citation.cfm?id=1142488 |
[8] | YANG Y, PAPADOPOULOS S, PAPADIAS D, et al. Authenticated indexing for outsourced spatial databases[J]. The VLDB Journal, 2009, 18 (3) : 631-648. doi: 10.1007/s00778-008-0113-2 |
[9] | YANG Y, PAPADOPOULOS S, PAPADIAS D, et al. Spatial outsourcing for location-based services[C]//ICDE 2008: Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2008: 1082-1091. http://ieeexplore.ieee.org/abstract/document/4497517/ |
[10] | MOURATIDIS K, SACHARIDIS D, PANG H H. Partially materialized digest scheme: an efficient verification method for outsourced databases[J]. The VLDB Journal, 2009, 18 (1) : 363-381. doi: 10.1007/s00778-008-0108-z |
[11] | 谢晴晴, 王良民. 基于PMD的外包数据流范围查询验证方案[J]. 计算机科学与探索, 2015, 9 (10) : 1209-1218. ( XIE Q Q, WANG L M. Data stream range query authentication scheme based on PMD in outsourced database[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9 (10) : 1209-1218. ) |
[12] | HU H, XU J, CHEN G, et al. Authenticating location-based services without compromising location privacy[C]//SIGMOD 2012: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2012: 301-312. http://dl.acm.org/citation.cfm?id=2213871 |