2019, Vol. 40
2. 中北大学 软件学院, 山西 太原 030051
2. School of Software, North University of China, Taiyuan 030051, China
空间查询有着广泛的应用, 如环境监测、交通控制、地理定位服务等.但空间数据结构复杂, 存储和处理空间数据需要大量的存储资源和计算资源.将空间数据外包到云计算服务提供商成为用户的最优选择, 即使用户拥有处理数据所需的软硬件资源, 外包数据也能够使数据拥有者从成本开销、网络访问和服务质量等方面受益.将数据远程存储在不完全可信的第三方, 数据所有者失去了对数据的物理控制.第三方可能会返回错误的结果, 包括伪造或篡改的记录, 也可能返回真实结果的一个子集.因此, 查询结果的完整性是亟须解决的安全问题之一.查询用户需要验证查询结果的完整性以确保远程服务器忠实地执行查询.数据外包中的查询完整性包括两个方面:①查询结果中的数据确实来源于数据拥有者, 并且没有被任何人修改; ②符合条件的数据都包含在查询结果中.
为了有效地处理空间查询并提供查询验证, 研究者提出了多种认证空间索引结构, 最流行的空间查询验证结构是MR-tree和MR*-tree[1].但是, MR-tree使用边界矩形进行区域划分从而造成过多的空间重叠并导致了过多的、不必要的磁盘访问.为了进一步提高空间数据查询的效率并降低验证对象的大小以降低通信开销, 本文提出了一个新的、高效的空间查询验证结构VSS-tree(verifiable SS-tree).方案对SS-tree[2]中的每个节点附加验证信息, 利用边界球进行区域划分, 降低了树的高度, 有效避免了不必要的磁盘访问, 从而提高了查询验证效率并降低了网络开销.
1 相关工作在空间数据查询验证中, Cheng等[3]提出了VKD-tree和VR-tree, 分别使用KD-tree和R-tree, 应用“签名链”思想实现多维数据查询结果的完整性验证.为了保护边界数据的隐私, 数据的哈希值由查询用户和服务提供商共同计算, 使得查询用户无需原始数据即可计算出边界数据的哈希值.但多次哈希操作增加了查询用户的验证开销.Yang等[1]提出了外包空间数据库的查询验证方案MR-tree和MR*-tree.MR-tree和MR*-tree将认证信息分别与R-tree和R*-tree相结合.但R-tree采用边界矩形进行区域划分, 过多的区域重叠造成了过多的磁盘访问并降低了查询处理速度.Papadopoulos等[4]提出了利用Hilbert曲线和MBT解决高度动态空间数据库连续范围查询的完整性验证.Ku等[5]采用Hilbert曲线来保护外包数据的隐私性, 并复制和加密部分外包数据以进行查询验证.文献[6-8]中提出了基于位置的空间查询验证方案.利用Voronoi图将整个位置空间划分成不重叠的区域.给定一个移动查询, 服务器返回查询结果和移动查询点对应的安全区域.当查询点移出相应的安全区域时, 返回另一个查询结果和其关联的安全区域以及相应的验证对象.Wang等[9]复制一部分原始数据并使用两个不同的密钥加密.查询用户通过检查返回的重复加密的数据是否一致来判断查询结果的完整性.Xie等[10]将一些伪造的记录插入到外包数据库中.云服务器无法区分哪些记录是伪造的记录.通过分析查询结果中的伪造记录, 查询客户可以实现概率验证查询结果的完整性.
2 系统模型图 1为方案的系统模型.它包括:数据所有者(data owner, DO)、云计算服务提供商(cloud service provider, CSP)和查询用户.
|
图 1 系统模型 Fig.1 System model |
从一个可信密钥分发中心获取密钥对(sk, pk)后, DO构建验证结构并对根节点的摘要值进行签名, 并将数据库和签名一起发布给CSP.CSP托管外包数据库并为用户提供查询服务.系统假设CSP是不完全可信的.CSP能够正确地执行本文提出的方案, 但也可能是不称职的; 它可能错误地处理外包数据导致返回错误的或不完整的查询结果.因此, 响应查询时, CSP将查询结果和对应的验证对象(verification object, VO)一起返回给查询用户.查询用户根据返回的验证对象和公钥pk进行查询结果完整性验证.查询用户仅信任数据所有者发布的签名信息.主要符号如表 1所示.
|
表 1 符号表 Table 1 Symbol list |
MR-tree在R-tree的基础上附加验证信息完成空间查询和验证.MR-tree结构如图 2所示.MR-tree采用R-tree的边界矩形进行区域划分.节点的MBR代表包含所有区域的最小边界矩形.
|
图 2 MR-tree Fig.2 MR-tree (a)—数据点和节点边界矩形；(b)—MR树结构；(c)—叶子节点结构；(d)—内部节点结构. |
SS-tree将n维数据点划分为各向同性的邻域从而提高最近邻查询的性能[5].SS-tree采用边界球来表示区域形状, 结构如图 3所示.
|
图 3 SS-tree结构 Fig.3 Structure of SS-tree |
边界球是由球心和半径决定的, 其存储空间是(n+1)维, 而边界矩形是由每个维的最小值和最大值决定的, 其存储空间是2n维.这使得SS-tree的节点分支数几乎是MR-tree节点分支数的两倍, 从而降低树的高度和磁盘访问次数.VSS-tree为SS-tree中的每个节点附加摘要值, 并对根节点摘要值进行签名.VSS-tree的结构如图 4所示.
|
图 4 VSS-tree结构 Fig.4 Structure of VSS-tree |
VSS-tree的叶子节点定义为
|
式中, m和M分别是叶子节点分支的最小值和最大值.每个条目E包含1个指针和1个n维特征向量.
VSS-tree的中间节点定义为
|
|
其中:C表示包围其第i个孩子所有区域的最小边界球, 由边界球球心和半径来表示; p是指向第i个孩子的指针; w表示以E为根节点的子树中多维数据点的数量; h是其所有孩子节点边界球和摘要值连接的摘要, 即h=h(C1|h1|…|Cf|hf).
边界球的球心x(x1, x2, …, xd)根据式(1)计算:
|
(1) |
其中:Cj表示第j个节点; Cj.xi表示节点Cj球心的第i维坐标; Cj.w表示以Cj为根节点的子树中多维数据点的数量.边界球的半径根据式(2)计算:
|
(2) |
其中:Cj.x和Cj.r分别表示节点Cj边界球的中心和半径; ‖x-Cj.x‖表示该节点的球心到其孩子节点Cj的球心的距离.
3.1 范围查询和验证CSP在VSS-tree上执行一次深度优先遍历进行范围查找并构造VO.所有与查询范围重叠的区域都要被访问.VO由三种类型的对象组成:①标记节点范围的特殊标记对[和]; ②被访问的叶子节点的所有数据对象; ③未被访问的节点的边界球和摘要值对.
查询验证时, 用户从VO中顺序读取对象并验证:① VO中的每个数据对象要么是查询结果, 要么在查询Q范围之外; ② VO中所有边界球和摘要值对与Q不重叠; ③重构的根节点的摘要值和签名相匹配.验证过程见算法1.
算法1 Verification
输入:VO, q
输出:C, Hash
1: str=null, Circle=null, Res=null
2: for each entry E in VO do
3: if E is a data object then
4: if E overlaps with query q then
5: insert E into Res
6: str=str|E
7: recompute Circle to include E
8: if E is [then
9: (C, H)=GetNodeHash(VO)
10: if E is a pair of Circle/Digest(C, H) then
11: recomputed Circle to include E.C
12: str=str|C|H
13: if E is] then
14: Return(C, Hash(str))
3.2 kNN查询和验证k最近邻(k-nearest neighbor, kNN)查询是一种重要的数据库分析操作, 用作独立查询或数据挖掘任务的核心模块.一个kNN查询由一个查询点q和一个正整数k(k≥1)组成.kNN搜索算法的本质是以查询点q为中心逐渐增加搜索半径, 使得搜索区域恰好包含k个数据点, 如果k=1, 则称之为最近邻查询.kNN搜索算法如算法2所示.
算法2 kNNQuery
输入:节点n, 查询点q, 邻居数k
输出:KNNList, VO
1: append [to VO
2: if n is a leaf node then
3: for each entry E in n do
4: Append E to VO
5: if dist(q, E) < MaxDist then
6: KNNList.add(E.id, distance(q, E))
7: else for each entry E in n do
8: insert(BranchList, dist(q, E), E)
9: sort(BranchList)by ascending
10: for each entry E in BranchList do
11: if dist(q, E) < MaxDist then
12: kNNQuery(E.p, q, k)
13: else append(E.C, E.h)to VO
14: Append] to VO
算法2中, KNNList存放kNN候选结果, MaxDist表示查询点和KNNList中数据点距离的最大值.如果列表中的对象数量小于k, 叶子节点中的当前数据点可以直接插入到KNNList, MaxDist定义为+∞, 否则, 只有小于MaxDist的数据点才能插入KNNList.BranchList升序列表用于存放当前访问的中间节点的各条目和查询点的距离.查询算法遍历BranchList, 在访问到的节点上递归调用kNN查询算法.一旦发现某个节点与查询点q的距离大于MaxDist, 该节点和BranchList中的其余节点都将被忽略, 它们的最小边界球和摘要值对插入到VO中.
执行kNN结果验证时, 客户端首先从结果集中获取最大距离MaxDist, 然后扫描VO以验证:①不在结果集KNNList中的多维数据点与查询点q的距离大于MaxDist; ②边界球和摘要值对中的边界球与查询点q的距离大于MaxDist; ③重构哈希值hroot与签名sroot相匹配.kNN查询验证算法如算法3所示.
算法3 kNNVerification
输入:VO, KNNList
输出:Hash
1: str= null, C=null
2: for each entry E in VO do
3: if E is a data object then
4: if E.dist(q) < MaxDist and E.id in KNNList then
5: continue
6: else alarm the client
7: str=str | E
8: if E is[then
9: h=kNNVerification(VO, KNNList)
10: if E is a pair of(C, H) then
11: if C.dist(q) < MaxDist
12: alarm the client
13: str=str|C|H
14: if E is] then
15: Return(Hash(str))
3.3 完整性证明从查询完整性的两个方面证明方案的有效性.
假设1 查询结果中存在伪造或篡改数据.
证明 VSS-tree以自底向上的方式进行构建, 所有数据都参与根节点的哈希值的计算.哈希函数是单向的、冲突抵制的.结果集中若存在篡改数据或伪造数据, 这些数据的哈希值一定与原来的不同或者不存在, 从而造成重构的哈希值无法通过签名验证.因此, 方案能够保证查询结果中的所有数据都是正确的.
假设2 E是叶子节点中Ln的一个多维数据点并是查询结果之一, 但却没有包含在返回的结果集中.
证明 为了使重构的根节点哈希值与签名匹配, VO要么包含Ln中的所有数据, 要么包含Ln的边界球和摘要值对.前一种情况, 验证算法能够检测到E在查询范围之内或者E到查询点的距离比MaxDist小, 能够确定E是查询结果之一.后一种情况, 算法可以检测到该叶子节点边界球与查询范围重叠或者其到查询点的距离小于MaxDist, 但该节点未被访问, 这违反了完整性规则.因此, 方案能够确保查询结果包含所有符合条件的数据.
3.4 动态更新动态操作包括插入、更新和删除.本文采用R*-tree中使用的更新算法.对于删除操作, 首先执行搜索算法来定位包含要删除的数据对象的叶子节点Ln, 然后从该叶子节点中将该数据点删除.如果Ln下溢, 即Ln中包含的数据对象数量小于最小阈值, 则删除Ln, 并将其所有剩余的数据点重新插入到VSS-tree；否则, 自底向上调整受影响的节点.
插入操作比删除操作更复杂.插入新数据对象或节点时, 插入算法必须确定和插入对象最近的节点.当插入节点已满时, 重插入操作将被执行, 如果在重插入之后节点仍然是满的, 则执行分割算法.在将新的对象E插入到某个节点N时有三种情况和对应的操作:①N有空间, E插入到N中; ②N溢出, 距球心最远的部分条目将被删除并重新插入到VSS-tree中; ③在重新插入后N仍然溢出, N将被分裂成两个节点.分割算法根据其子节点的球心计算每个维度上的坐标方差, 并选择具有最大方差的度来分裂节点.
4 性能分析和实验分析首先从理论上分析VSS-tree, 然后进行实验评估来验证VSS-tree的有效性和效率.
4.1 开销分析验证树的主要性能参数有索引尺寸、节点分支数、构建开销、查询处理开销、VO尺寸和验证成本.索引尺寸影响云服务器的存储成本.索引构建成本影响构建索引的实体, 即DO和CSP.查询处理开销影响CSP查询处理的响应速度.VO尺寸影响CSP和查询客户之间的网络传输开销；验证成本只影响查询客户.下面对VSS-tree和MR-tree的上述性能参数进行分析和比较.
首先确定两种验证树的节点分支数, 两种验证结构的叶子节点结构是一样的, 因此, 叶子节点的分支数相同, 可以按照式(3)计算:
|
(3) |
VSS-tree中间节点的分支数为
|
(4) |
而MR-tree节点的分支数为
|
(5) |
式(4), 式(5)中, 只有参数SC和SM大小不同, 边界球SC的存储空间大小等于S(d+1), 而边界矩形SM的存储空间是S2d.因此, VSS-tree中间节点的分支数大于MR-tree中间节点的分支数.
两种验证树的高度按照式(6)计算:
|
(6) |
根据式(6), 在相同数据基数下, VSS-tree的高度小于等于MR-tree的高度.
设根节点在第0层, 已知验证树的高度和节点分支树, 可以计算出验证树的存储开销为
|
(7) |
其中:|D|/f1为叶子节点个数; fij为第j层节点个数.VSS-tree的初始构建开销为
|
(8) |
实验环境为奔腾双核2.60GHz CPU, 内存4.0G, 运行Windows 7系统的PC机. MR-tree和VSS-tree都使用Java语言实现, 磁盘页大小为2K字节.数据采用100次实验结果的平均值.数据基数范围1×104~1×105, 数据点均匀分布.
图 5为验证结构的构建时间图.构建时间包括:文件中读取数据、哈希计算、节点构建和签名计算.在相同条件下, VSS-tree比MR-tree的构建时间略长.因为边界球计算比边界矩形计算复杂.边界球由球心和半径表示, 球心和半径的计算涉及到加法和乘法运算, 而边界矩形只需要比较操作.
|
图 5 不同数据基数和维数下的构建时间 Fig.5 Construction time vs. data cardinality and dimensionality |
图 6显示了两种验证树的索引大小.尽管边界矩形需要的存储空间约为边界球的二倍, MR-tree所需的存储空间略大于VSS-tree.这是因为两种验证结构采用相同的叶子节点结构, 进一步, VSS-tree的每个节点还增加了字段w用于记录多维点数量, 且VSS-tree使用更小的区域直径进行区域划分, 也导致占用更多的存储空间[11].
|
图 6 不同数据基数下的索引尺寸 Fig.6 Index size vs. data cardinality |
图 7显示了kNN(k=3)的查询处理时间.查询处理时间包括查找结果和构建验证对象.VSS-tree的查询时间明显短于MR-tree.原因是使用更小区域的边界球进行区域划分减少了节点之间的重叠区域, 从而减少了不必要的磁盘访问, 提高了查询处理效率.
|
图 7 查询处理时间 Fig.7 Query processing time |
图 8显示了两种验证树下kNN查询的磁盘读取次数.很显然, VSS-tree比MR-tree需要更少的磁盘读取.原因在于使用边界球进行区域划分不仅增大了节点的分支数从而降低了验证树的高度, 而且减少了区域重叠面积从而避免了不必要的磁盘访问.
|
图 8 磁盘访问次数 Fig.8 Numbers of disk access |
图 9显示了VO的尺寸.基于VSS-tree构建的VO比MR-tree构建的小.因为VSS-tree中边界球的存储开销小于MR-tree中边界矩形的存储开销.
|
图 9 不同数据基数下的VO尺寸 Fig.9 VO size vs. data cardinality |
本文提出一种新的验证空间索引结构VSS-tree.VSS-tree使用边界球进行区域划分, 增大节点的分支数并降低验证树的高度, 同时也减少区域重叠面积从而避免不必要的磁盘访问.实验结果表明, VSS-tree在查询处理速度、网络通信开销等方面优于MR-tree.
| [1] |
Yang Y, Papadopoulos S, Papadias D, et al.
Authenticated indexing for outsourced spatial databases[J]. VLDB Journal, 2009, 18(3): 631–648.
DOI:10.1007/s00778-008-0113-2 |
| [2] |
White D A, Jain R.Similarity indexing with the SS-tree[C]//Twelfth International Conference on Data Engineering.New Orleans: IEEE, 1996: 516-523.
|
| [3] |
Cheng W, Pang H H, Tan K L.Authenticating multi-dimensional query results in data publishing[C]//Data and Applications Security Xx, IFIP Wg 11.3 Working Conference on Data and Applications Security.Berlin: Springer, 2006: 60-73.
|
| [4] |
Papadopoulos S, Yang Y, Bakiras S, et al.
Continuous spatial authentication[J]. Lecture Notes in Computer Science, 2009, 5644: 62–79.
DOI:10.1007/978-3-642-02982-0 |
| [5] |
Ku W S, Hu L, Shahabi C, et al.
A query integrity assurance scheme for accessing outsourced spatial databases[J]. Geoinformatica, 2013, 17(1): 97–124.
|
| [6] |
Nutanong S, Zhang R, Tanin E, et al.
The V*-diagram:a query-dependent approach to moving kNN queries[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 1095–1106.
DOI:10.14778/1453856 |
| [7] |
Man L Y, Lo E, Yung D.Authentication of moving kNN queries[C]//International Conference on Data Engineering.Hannover: IEEE, 2011: 565-576.
|
| [8] |
Hu L, Ku W S, Bakiras S, et al.Verifying spatial queries using Voronoi neighbors[C]//Proceeding of the 18th SIGSPATI International Conference on Advances in Geographic Information Systems.San Jose: ACM, 2010: 350-359.
|
| [9] |
Wang H, Yin J, Perng C S, et al.Dual encryption for query integrity assurance[C]//ACM Conference on Information and Knowledge Management.Napa Valley: ACM, 2008: 863-872.
|
| [10] |
Xie M, Wang H, Yin J, et al.Integrity auditing of outsourced data[C]//International Conference on Very Large Data Bases.Vienna: DBLP, 2007: 782-793.
|
| [11] |
Katayama N, Satoh S.
The SR-tree:an index structure for high-dimensional nearest neighbor queries[J]. ACM Sigmod Record, 1997, 26(2): 369–380.
DOI:10.1145/253262 |