面向空间索引树的授权机制

张颖君，冯登国，陈恺

(1. 中国科学院研究生院 信息安全国家重点实验室，北京100049；2.信息安全共性技术国家工程研究中心，北京 100190)

1 引言

随着空间技术的日益普及，用户通过 Google Earth、MS TerraServer可以访问地球上任意范围的物体，甚至观测到其运动变化；全球定位系统（GPS）和惯性导航系统（INS）等高技术系统相结合的智能型实时地理信息系统使得地理空间数据成为一种实用的工具，即使用户处于陌生的城市，可以通过GPS等设备快速确定自己的位置，查询道路信息等。由此可见，空间技术的需求在不断增长。方便、快捷的空间地理数据的操作方式，一方面满足了用户对空间信息的快速访问，另一方面泄露了用户的隐私信息，给国家、企业和个人造成极大的威胁。因此，空间数据库的安全问题已经成为目前国内外研究的热点问题。

空间数据具有数据量大，空间目标不规则，目标的结构及其关系复杂（相交、相邻、包含、覆盖关系等），空间操作与计算比传统的关系运算代价高的特点，国内外研究人员依据不同空间数据特征构建的空间数据访问控制机制，目前主要分为2大类：一类针对矢量数据，主要是E. Bertino提出了授权窗口概念[1,2]，即用户只能访问给定窗口中的空间对象，但是这种方法不能很好地解决策略冲突问题；另一类是针对栅格数据提出的访问控制模型，具有代表性的是Atluri等在GSAM基础上提出了空间授权索引的方法[3～6]，主要针对空间栅格数据进行区域划分，选择特定的索引树结构，并在相应区域上添加授权信息，使得在对空间数据查找过程中能快速判断其操作的有效性，此类方法在一定程度上提高了访问控制判定效率，比较典型的有RMX-Quadtree[3]和 STAR-Tree[5]。RMX-Quadtree是在四叉树的基础上进行扩展，将每个节点的授权信息在其查找路径上存储多次，这样用户可以在查找过程中进行权限判定，无需达到目标节点即可获取其权限信息。为了节省权限存储空间，提高查询效率和支持时间属性，Atluri等提出STAR-Tree结构。但是这些基于索引的授权模型都不支持对矢量数据的应用，并且不能很好解决肯定授权和否定授权的冲突问题。因此，针对矢量数据和栅格数据的特点，本文实现面向空间索引的授权机制，有效提高空间授权信息变化的效率问题，易扩展到多种空间数据结构和索引方法中。

综上所述，本文通过对空间对象分析，考虑到空间特征和空间操作的复杂性，对空间对象进行归类，利用空间操作的偏序关系，将相关归类信息加载到索引树结构中，构建面向空间索引的授权模型；在模型上构建一种有效的实施机制，实现策略冲突判定，并提高访问请求判定的效率，通过与访问控制中间件形式（MW）、STAR-Tree和RMX-Quadtree中访问请求判定算法的时间和内存复杂度进行比较，SIAM 模型具有更好的时间和空间特性；最后通过实验分析证明授权索引在效率和易扩展性方面都具有明显优势。

本文的主要贡献包括以下几个方面。

1) 本文提出面向空间索引的访问控制模型SIAM。该模型建立了授权归类信息与索引树的关联，兼顾矢量数据与栅格数据等多种空间数据结构，支持肯定/否定授权方式，具有良好的可扩展性。

2) 针对SIAM模型提出有效授权方法，通过将空间授权信息添加到索引结构中，减少索引检索次数，使得用户在查找数据的同时完成权限判定，提高了查询判断的效率；同时解决了策略冲突的问题。

3) 进行了一系列模拟实验，通过与多个模型在访问请求判定时的时间和空间效率进行比较，说明SIAM 模型可同时支持矢量数据和栅格数据，且对空间对象和空间区域的查找具有一定的优势。

本文共分为6节，其中，第2节介绍面向空间索引的授权模型（SIAM），第3节主要是SIAM模型授权实施方法，第4节通过实验验证模型的有效性，第5节是对相关工作的介绍，第6节是结束语。

2 SIAM模型

传统访问控制方法对空间对象实施访问控制存在二次检索问题：一次检索产生于对空间对象授权策略的查找与判定，另一次索引产生于空间对象的获取过程。二次检索直接导致了响应效率的下降，这是空间数据访问控制技术实施的重要障碍之一。本节提出一种面向空间索引的授权模型SIAM，通过将授权信息和空间索引结构相结合，使空间对象和授权信息的获取在一次检索中完成，提高了访问控制实施效率。SIAM 模型中元素及其关系定义如下。

2.1 模型定义

在SIAM模型中主要包括构建索引树T及其授权归类信息I进行描述。本文定义U为用户集，O是访问客体集，P为操作集，A为权限集合，N是自然数集。为了对SIAM模型进行描述，首先定义操作元信息，并通过其描述授权归类信息的定义，在此基础上对SIAM模型进行形式化定义。

定义1 （操作元信息opυ）定义针对空间操作的元信息，方便对用户权限信息的描述。

υop=＜＞，其中，op表示空间操作，δ={+,-}表示肯定/否定授权方式，并采用否定优先的策略。

定义2 （授权归类信息λ）Iλ∈是对授权信息的归类分析。

λ= ＜ϖ, γ, sn,υ＞ ，其中,ϖ∈O表示授权信息对应的空间范围，γ ={γi|i ∈N}表示空间特征分类方式，可以根据不同数据模型做出不同的分类，例如分为点、线、面，或者按照不同图层进行分类；sn= { sni|i ∈N} 表示空间对象统计信息，即一定空间索引树上节点的子节点的个数； υ ={υop}表示操作元信息集，为了描述方便本文只对一种操作元信息进行分析，即 υ =＜ υ+,υ-＞。

定义3 （节点node）节点node分为叶子节点lnode和非叶子节点nnode，root也是node的一种。

其中，mbri表示最小包络矩形，索引树的查找过程主要通过对各个节点空间范围 mbri的比较进行的（主要是包含关系），直到找到匹配的节点（这里对矩形重叠部分不做单独分析）。

定义4 （边edge）表示对2个节点的连接：edge = ＜ n ode1, node2＞。

其中，root只有出边没有入边，lnode只有入边没有出边，其他非叶子节点既有入边也有出边。

定义5 （索引树T） T =＜ r oot, n ode, edge ＞通过树的根、节点和边，对索引树结构进行描述。本文主要对常用的R树、四叉树等进行归纳。

定义6（空间对象包含关系函数ct）c t( oa∶O, ob∶O)→ℑ定义了空间对象 oa和 ob拓扑关系比较函数。其中， ℑ = { εi|0 ≤i≤ 3 }具体实现过程如下：

由此可见，通过空间对象关系函数ct，可以得出空间对象的包含关系，是空间对象授权关系判断的依据。

定义7 （授权归类索引树构建函数f）∶f TI→定义了将T中节点映射到I中授权归类信息λ的过程。具体实现如下：

其中，a rea( node)表示节点对应的空间区域。使用f-1(λ)=node 表示将授权归类信息I映射到T的过程。

定义8 （授权实施模型SIAM）SIAM定义了结合授权信息的索引树结构模型

SIAM = ＜ T , I, f＞,其中，T是空间索引树；I={λ}表示授权归类信息集；f是授权归类信息映射函数，定义了T中节点与I中归类信息λ的映射关系。

以上是对SIAM模型中各个元素的具体定义，可见SIAM模型是空间索引树与授权归类信息结合的过程。空间索引树中的节点对应一定的空间范围，与此空间范围相关的授权信息构成了此节点的授权归类信息，下一节对授权信息添加过程以及访问控制判定过程涉及的基本原理进行介绍。

2.2 SIAM理论

SIAM 模型通过将访问请求中权限判定和空间对象2次索引合并，减少对索引树的遍历次数。同时，可以利用模型中的一些关系对其进行优化，提高权限判定的效率。下面介绍SIAM模型中涉及的基本原理。

定义 9 （授权信息 a）权限信息 a表示为a =＜u, o, p, pt＞其中u∈U表示对数据进行访问的用户，为了实现对大量用户的定义，使用角色的概念对用户进行分类；o∈O表示授权对象，包括空间对象、空间特征和空间区域；p∈P表示操作，包括传统操作和空间操作；pt∈δ是授权方式。

定义10 （操作偏序关系≥p）操作op1和op2之间具有一定的偏序关系，记为 o p1≥pop2，表示对同一个对象，用户具有 op1的权限时也具有 op2的权限。例如 z oom -i n ≥pview，因此如果用户对空间对象o进行放大操作的权限，则同时允许用户进行查看。基于空间操作的偏序关系，可以定义操作对象集之间的偏序关系，并在此基础上定义权限信息之间的条件偏序关系。

定义11 （操作对象集偏序关系≥）操作与对象的权限集合具有一定的偏序关系：

定理1 操作对象集上的≥操作是偏序关系。

证明 目标是证明≥具有自反、反对称和可传递的特性。

自反性：根据定义，(o p, o b) ≥ ( o p, o b)是显然的。

反对称性：

由式（1）、式（2），o p≥pop'且op'≥pop，ct( ob', ob)=ε2且ct( ob, ob')=ε2。而操作op，op'间具有偏序关系；由ct的定义可知ob= o b'，因此，可得：

传递性：

由式（3）、式（4）成立，且因为操作间具有偏序关系；空间包含关系ct操作也具有可传递性，得op ≥pop' ≥pop '', c t( ob', ob )=ε2∧ c t( ob'', ob ')=ε2，即(op, ob ) ≥(op'', ob'')，可知传递性成立。

综上所述，操作对象集上的≥操作具有偏序关系。证毕。

定义12 （权限信息条件偏序关系δ≥）δ≥定义了权限信息之间的不同条件δ下的偏序关系：

表示如果操作（op, ob）和（op', ob'）具有偏序关系，并且此时权限信息中为肯定授权，则权限信息中也具有一致的偏序关系；如果是否定授权，则偏序关系需要进行条件限制，例如不允许用户进行查看区域A，则可以推导出也不允许用户对A区域进行放大/缩小操作，但是此时允许对其他区域进行操作，并不是完全否定所有包含A的大空间范围。因此，称之为条件偏序。

定理2 权限信息之间具有条件偏序关系

空间对象关系同样具有反向性：c t ( A1, A2) =ε2，可知 A2包含 A1区域。但是当否定情况下，用户不允许访问A1，则不允许访问A2。

依据定理 1，易证(o p, o b, +)≥δ(o p', o b',+)→((o p', o b ' ,-)≥δ(o p, o b,-))。证毕。

通过定理 2，可以将操作及对象之间的偏序关系直接体现在SIAM模型的授权归类信息中，因此无需每次进行推理判断，使得权限判定更简单。

综上所述，授权信息之间的条件偏序关系，是空间授权信息添加至授权归类信息集的依据，根据其偏序关系，可以对授权信息的添加、修改进行优化，将相关推导规则加入到授权归类集中，当用户发起访问请求时，可以直接进行判断，无需再进行推导，提高访问请求判定的效率。

3 SIAM模型授权实施方法

本节对模型中授权信息的添加以及访问控制判定等具体操作进行介绍。在授权信息添加至授权归类集过程中，主要依据相关定理对添加信息进行优化；构建好授权信息集后，在实际的访问请求判定中可直接对权限信息进行比较，提高权限判定效率。

3.1 授权信息添加

以上是对SIAM 模型的形式化描述，可以通过模型构建出面向空间索引的通用授权框架。下面会对如何将授权信息添入SIAM框架做一些具体定义。

定义13 （授权归类信息映射函数af） a f( a∶ A)→I，表示将授权信息a映射到授权归类λ∈I中的函数，可以找到权限归类信息中具体的特征类与其匹配。具体实现定义如下：

其中，ft是空间对象特征类函数，表示对空间对象的空间特征类的查找。空间特征类一般在系统中预先定义完成，可以依据多种标准进行特征划分，如：点、线、面方法，或基于图层的方法等（栅格数据则简化为一种空间特征），因此 ft函数的实现需要依据具体系统而定。同时需要满足授权对象和权限归类信息中的空间范围一致性问题。

授权信息映射的过程，即将授权信息添加到索引树对应授权归类信息的过程。考虑到空间索引树中各个节点的空间范围一致，即ϖ相同，因此，更多的关注操作元权限信息。在权限比较过程中，无需采用传统的访问控制列表或矩阵等形式进行比较，而是在索引树查找过程中直接对统计信息进行判断即可。在具体映射过程中规则定义如下。

规则1 对于 T . nodes中的n，当其满足 c t( n, a.o)= ε1时，将权限a加入节点n中。

规则1表示需要对授权信息映射到索引树的节点上，如果授权对象与索引树中某个节点空间范围一致，则可以直接映射。

规则2当授权对象与空间树中多个节点相交，即不能直接映射到某个节点时，需对授权对象进行分解，在节点上对权限进行归类。

∃ n ( n ∈ T . n o des ∧ c t( n, a.o) = ε0)时，则调用对象分解函数 d ec( a.o)，再递归分析。对象分解函数定义如下。

定义14 （空间对象分解函数dec） d ec( o∶ O,t∶ T)→O，这个函数的解集{oi|i∈ [1 ,n]}满足如下条件：

2)∀ oi(oi∈ O → ∃ j ( c t( oi, t. n o dej)= ε1))；

dec函数将空间对象划分为一系列不相交的子集，并且这些空间对象均可以完全映射到索引树中的某个节点上，并且这些节点中不存在一个完整的子树结构，因此，需要将相应的授权信息也添加到分解后的各个节点上，避免对授权信息进行多次存储，造成空间的浪费和效率的降低。

在授权信息添加到各个节点之后，由于权限之间具有条件偏序关系，需要考虑用户所有的权限，否则访问请求判定中用户无法获取合法权限。例如，用户允许对区域A进行放大操作，此时在授权归类信息中如果只对放大操作进行记录，而不处理相应的查看权限，那么当用户进行查看时，则被拒绝。为了解决权限之间的条件偏序关系，依据定理2定义授权信息条件偏序合并算法 PolicyCPartial（如算法1所示）。

算法1 授权信息条件偏序合并算法Policy CParitial PolicyCPartial( n ode)

算法1中首先对树中每个节点上授权归类信息集中涉及的偏序关系进行一定的推导，将可以推得的信息添入；最后使用授权信息合并算法，再对整个树进行合并，形成最终的权限归类信息表示。通过上述算法可以将授权信息映射到授权归类信息集I中，但是为了实现授权信息尽量上移，可以减少权限比较次数的目的，需要对整个索引树的授权信息进行更新。定义如下。

定义 15 （授权归类信息合并操作⊕）将一个节点的子节点授权归类信息进行合并操作，定义如下：

假设λ3有2个子节点λ1,λ2：

其中，3ϖ表示21,ϖ ϖ的最小包络矩形。当3λ有多个子节点时，以此类推。

当节点信息与子节点信息合并发生冲突时，采用否定优先策略，即通过max(a, b)表示最大的否定数值。例如在图1中，节点A与其子节点B、C在授权归类信息中操作元信息发生冲突时，即时，选用其中较大的数值

图1 节点授权信息冲突

规则 3 由叶子节点开始向父节点方向构建整个索引树的授权信息，直到根节点。

由规则 3，父节点 node包含所有子节点（node.childi）授权归类信息之和（如图2所示）。

图2 授权归类信息向上递归过程

根据以上规则可以在索引树中构建完整的授权归类信息集。当授权信息发生变化时，需要从授权信息发生变化的节点开始向上进行更新操作，与上述过程类似，不进行详细介绍。

3.2 访问请求判定

通过以上形式化描述，可以完成面向空间索引树的授权，下面对SIAM模型访问请求判定过程进行介绍。具体定义如下。

定义16 （访问请求req）r e q =＜ u ser,obj, pr＞，其中，user为访问请求用户；obj为请求访问的空间对象，可以通过对象唯一标识符进行指定，或者一类对象（如线对象），也可定义一定的空间范围；pr为相应操作。

由于空间对象可以包含多种形式，因此定义不同规则对其进行处理。

规则 4 若空间索引树中查找空间对象路径上存在完全授权策略，则向下查找过程中无需进行权限比较。

或者

其中，(,,)n pκδ表示节点n上操作p在肯定/否定授权时的数值。

规则 5 若查找区域和索引树节点的空间范围完全一致，则查找该节点权限并返回。

时，返回n的子节点被允许的范围。

规则 6 若查找区域和索引树节点不能完全匹配，则需要对查找区域进行分解。

时，分别对dec(req.obj)进行递归分析。

基于以上的规则，本文定义的面向空间索引的授权机制进行用户访问请求判定过程，是一次查找索引树的过程，具体判定方法如算法2所示。

算法2 访问请求判定算法judge

在访问请求判定过程中，首选需要找到请求对象对应的索引树节点上的授权归类信息，然后通过 judgeNode函数对授权归类信息中用户相应的部分分别做出比较：当用户、操作与空间类型ft( o bj)一致时，需要比较否定对象个数如果为0，肯定授权对象为全部时，则访问通过。算法时间复杂度为O(Clogn)，空间复杂度为O(C'n)，C为查找授权归类信息的时间，C'为授权归类信息的大小。通过理论分析可知，MW方法的时间复杂度为 O(nlogn)，空间复杂度为 O(n+l)，其中，l为授权信息总量；STAR-Tree的时间复杂度为O(mlogn)，空间复杂度为 O(mn+n)，其中，m是每个节点授权信息的平均长度；RMX-Quadtree的时间复杂度为 O(klogn)，空间复杂度为 O(n+llogn)，其中，k为节点平均授权信息的长度。由于RMX-Quadtree中授权信息重复存储，SIAM采用授权归类信息存储方式，因此k＞m＞C。所以，SIAM 不但支持多种类型的空间数据，而且在时间和空间复杂度上也具有良好的特性。

由此可见，SIAM 模型中首先在空间数据库的索引树结构T上进行授权实施扩展，通过函数f实现其映射关系；通过对授权信息进行归类分析，可以在空间对象查找过程中尽早判定其访问权限（即树中较高的层次进行确定），提高权限判定的效率。此外，模型容易扩展到现有空间数据库中，可以对多种索引结构，如R树、四叉树、及其变形等进行相应的扩展。通过实验分析说明其有效性以及效率上的优势。

4 实验分析

4.1 实验方法

为了验证本方法的有效性和性能，对空间数据库操作场景进行模拟。为了描述方便，采用较常用的R树结果作为基础；空间特征分类方式设置为点、线和面，构建相应的策略实施部分（栅格数据只有面特征一种类型）。图 3给出了面向空间索引树授权的示意图，其中，左边为空间对象分布示意图，右边为对应的空间索引R树。R树中已经进行了相应的扩展，为了更直观地表示，采用表的形式对每个节点对应的授权归类信息λ进行说明。表中的每一列分别对应前面的授权归类信息的不同属性。

下面说明遍历一次索引树是如何完成授权和对象查找的2个过程。当用户发起查询Request，这里用虚线表示请求查询的空间范围，则需要对索引树进行遍历，查找与其相交的空间范围。因为Request区域不能直接映射到R树中的某一个节点，所以利用 d ec( R equest. o b j)函数首先将其分解为D、F、Poly1 3个子区域，再分别进行判断。在此遍历过程中，如果 c t( r eq.o bj,λu.ϖ)=ε2，则对其授权归类信息进行具体比较，判断是否具有相应权限。当查找路径中已经具有相应权限，则无需再进行权限判定。例如，用户查找线对象时，在根节点 Root处可知对所有的线对象都具有访问权限，因此直接返回查找对象即可，无需再进行权限判定。权限比较和空间对象查找是在索引树遍历一次的过程中完成的，并不需要对经过的每个节点都进行权限比较，减少了比较的次数，提高了效率。同时对权限判断的过程也进行了优化，无须对每个授权信息进行比较，而是通过对授权信息进行归类进行。例如，点D、F和Poly1中，可以通过权限归类信息快速查出用户对D中所有空间对象没有访问权限（因为D中没有点和线对象，而面对象没有授权），F中所有对象具有访问权限，Poly1对象为肯定授权，因此可以快速返回相应的查询结果，即 Poly1、line2和line3。

通过上述方式说明，SIAM 模型只需一次判定即可确定访问请求的结果，而且判断过程更简单；同时方便用户进行策略定义和查找，提高权限判定的效率。

4.2 实验结果

上面通过实例说明了面向空间索引树的授权机制的有效性及实际实施过程，下面是通过实验结果分析做出进一步论证。

在模拟实验中，通过随机产生一定数量的的点、线、面数据构建R树。在R树上进行扩展，随机产生一定数量的授权信息（主要是针对空间对象进行授权），并将其加入授权归类信息中，实现SIAM模型的原型系统。为了对 SIAM模型效率进行分析，还实现了传统授权模型，即访问控制中间件形式（MW）。在MW模型中，授权信息以链表的形式单独存储，用户查询时需要先对访问请求的空间区域进行判断，允许通过时，返回相应空间信息。将对MW和SIAM模型在空间对象、空间特征和空间区域的查找进行比较。由于 STAR-Tree和 RMXQuadtree只是针对栅格数据实现的，而且STAR-Tree比 RMX-Quadtree效率要高，因此选择 STAR-Tree与SIAM在空间区域查找中进行比较。实验结果如下。

1) 空间对象的查找。由于查看单独一个空间对象，存在的偶然性太强，为了证明模型的有效性，在多个数据集大小构建的R树中，通过查找100个和1 000个空间对象，对SIAM和MW模型进行效率和占用内存的比较，如图4和图5所示。

图3 SIAM模型在R上应用实例

图4 SIAM和MW模型分别查找100个和1 000个空间对象所需时间比较

图5 SIAM和MW模型分别查找100个和1 000个空间对象所需内存比较

从图4可知：同一个模型中查找空间对象数量越多，则需要查找索引树以及权限比较次数增多，因此时间越长；此外，当空间数据集越大时，构建的索引树越大，层次增多，查找时间变长，效率降低；同时，对于SIAM模型和MW模型对比而言，由于 MW 模型中需要先对查询对象的空间范围和授权信息的空间范围进行比较，允许通过时，再次查询索引树，因此需要对索引树进行多次查找，SIAM 模型将授权信息与索引树结合，查找空间对象的过程中同时进行权限比较，如果在路径上已判断出没有权限，则直接返回，无需继续查找，因此，SIAM模型效率比MW模型高。

图5中对内存占用进行分析，由于内存占用主要与索引树和授权信息的大小相关，查找空间对象的个数对其影响基本可以忽略不计，因此只针对2个模型进行分析。从图中可知，空间数据集越大，构建索引树越大，占用内存越多，同时，由于SIAM模型是在索引树上进行简单扩展，记录授权归类信息，而MW模型需要对授权信息进行单独的存储，方便后续比较，因此SIAM模型比MW模型的内存占用要小。

2) 空间特征的查找。对某一特定空间特征（点）进行查找时效率分析。空间特征查找与空间对象查找的不同体现在：空间特征查询，需要对空间区域内所有该特征的对象进行查询，因此需要遍历整个树；而空间对象的查找可能包含多种空间特征，而且是只对其中一定数量的查询，因此无需遍历整个空间区域。

通过表1实验数据可知，空间区域内包含所有点的查找时间随着空间数据的增加而延长。因为对某一空间特征的所有空间对象的查找，需要遍历整个空间范围，所以，当空间数据量大时，遍历所需的时间也长。SIAM 模型在此类情况中，尤其数据量大时，比MW具有优势，因为SIAM模型中的授权归类信息是依据空间特征进行划分的，更为快捷；而MW则需要每次遍历授权信息，所以效率相对较低。内存占用上，SIAM也具有一定优势。由于空间特征点的查询占用资源较多，因此只对1 000～20 000之间的9组数据进行分析，比实验1的范围小（最大达到100 000）。

表1 空间特征（点）查找时间和内存占用比较

3) 空间区域的查找。对给定空间区域中的所有空间对象进行查找。给定的空间区域可以与索引树中的多个节点重叠（即用 dec函数进行分解）。其中，在空间区域查询中（类比与栅格数据情况），还实现了STAR模型[5]进行比较（STAR树也是R树的一种）。

图6所示为3种模型中空间区域查找的时间比较。随着空间数据集的增大所需的时间都会变大。同时空间区域的查找中利用索引树进行优化的效果要优于中间件形式。此外，可以看到 SIAM 比STAR树在空间区域（类似栅格情况）还是具有一定优势的，因为SIAM对R树各子节点授权信息进行了分析归纳，无需每次进行逐一比较匹配。

图6 SIAM、STAR和MW模型查找空间区域时所需时间对比

图7所示为SIAM模型中3种实验的比较，以查询1 000个空间对象所需时间为基准，对其余2种查询方式进行比较，可以看出，空间区域的查找与空间对象的查找效率相当，因为区域的查找也是需要返回区域中包含的空间对象；而空间特征的查询相对时间要长，因为遍历索引树所需的时间远大于空间对象查找的时间。由此可见，SIAM 模型在空间对象和空间区域的查找中效果较好。

图7 SIAM中空间对象、空间特征和空间区域查找所需时间比例

综上所述，从实验中可知，SIAM 模型加入了对空间授权信息的归纳分析，省去了MW中两次查找空间对象的过程，因此在矢量数据中比传统的MW方法具有明显的优势。同时，与STAR在栅格数据的查找中也具有一定的效率优势。

5 相关工作

在空间数据库访问控制模型中，主要是针对矢量数据和栅格数据分别提出的。最早，Atluri等提出针对栅格数据（卫星图像）的空间授权模型GSAM[4,7]。模型是在自主访问控制的基础上进行空间扩展，给出其系统实现框架，同时作者在GSAM模型基础上提出了多种空间授权索引方法[3～6]：文献[3]主要针对空间栅格数据进行区域划分，基于四叉树结构建立索引 RMX-Quadtree，并在相应区域上添加授权信息，使得在对空间数据查找过程中能快速判断其操作的有效性；文献[5]是将文献[3]工作扩展到STAR树结构上，去掉对空间授权区域是正方形的限制，允许空间区域有交集，加入了时间维度，支持多分辨率图像授权索引机制；文献[6, 8]是将带有授权的索引结构扩展到移动数据库基础上，可以对用户基于时间变化的数据进行有效的判定。但是，这些模型都不支持对矢量数据的应用，而且不能很好解决肯定授权和否定授权的冲突问题。

针对矢量数据（地图信息）的研究中，文献[9～11]中作者在 LSDM 数据模型上构建自主访问控制模型，同时引入窗口的概念来解决其有效查询问题。授权窗口定义了用户允许访问的范围，在实际的查询中，只有与窗口相交的对象才能够被访问。通过这样的空间扩展，实现对地图的访问控制。但是由于矢量数据和栅格数据具有不同的数据表示方法，因此并没有提出一个通用的模型。

近年来，国内外工作者针对移动用户，提出大量的基于位置服务的访问控制模型，成为空间数据访问控制的一个新方向[12]。基于位置的服务中，大量的空间访问控制工作主要集中在对RBAC模型的扩展上。在基于空间的访问控制模型中比较完善的模型主要包括GEO-RBAC[13]。GEO-RBAC是一个完整的空间访问控制模型，它在用户位置、角色激活和对象方面都引入了空间位置的概念，使得整个模型的空间表示更完整，且实现了对角色的空间继承，和带约束的RBAC的空间扩展。此外，GEO-RBAC中引入角色模式的概念定义一系列具有相同意义的空间位置粒度和边界的角色，使得角色定义更灵活。文献[14]主要是对RBAC进行时间扩展的经典模型，定义了完善的时间描述方式，是后续文章的基础。在前面工作的基础上，多篇文章针对用户的空间和时间特性进行扩展[14～21]。这些模型大部分通过对RBAC模型的多个集合中加入空间和时间定义，构建更为完整而精确的访问控制模型，但是他们主要关注移动用户，提供基于位置的服务，并非针对空间数据提供访问控制，因此没有提供针对栅格数据和矢量数据的更为有效的访问控制方法。

6 结束语

本文在前人工作的基础上，针对空间索引树结构进行扩展，提出面向空间索引树的授权模型SIAM，该模型适用于矢量数据和栅格数据。并在模型中提出一套有效授权方法。通过将空间授权信息添加到索引结构中，使得权限判定的过程在查找数据时完成，因此仅遍历一次索引树，提高了查询判断的效率。模型中支持肯定/否定授权方式，并且解决了策略冲突的问题。最后，对多种空间数据查询方式进行了实验，结果表明，本文所述方法可同时支持栅格和矢量数据；当数据量大时，SIAM 模型对空间对象和空间区域的查询具有一定优势。

在未来的工作中，将优化SIAM模型，使其适用于更多场景中：如加入多分辨率或比例尺概念，添加时间维度，或应用到移动场景中；针对不同应用场景进行分析，对算法做出改进，提高其效率。

[1] BELUSSI A, BERTINO E, CATANIA B. An authorization model for geographical maps[A]. Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems[C]. 2004. 82-91.

[2] BERTINO E, DAMIANI M L, MOMINI D. An access control system for a Web map management service[A]. Proceedings of 14th International Workshop on Research Issues on Data Engineering∶ Web Services for e-Commerce and e-Government Applications[C]. 2004.33-39.

[3] ATLURI V, MAZZOLENI P. A uniform indexing scheme for geo-spatial data and authorizations[A]. Proc of the Sixteenth Conf on Data and Application Security, IFIP TC11/WG11[C]. 2002.207-218.

[4] ATLURI V, CHUN S A. An authorization model for geospatial data[J].IEEE Transactions on Dependable and Secure Computing, 2004,1(4)∶238-254.

[5] ATLURI V, GUO Q. STAR-tree∶ an index structure for efficient evaluation of spatiotemporal authorizations[A]. Research Directions in Data and Applications Security XVIII∶ IFIP TC 11/WG 11.3 Eighteenth Annual Conference on Data and Applications Security[C]. Sitges, Catalonia, Spain, 2004.

[6] ATLURI V, GUO Q. Unified index for mobile object data and authorizations[A]. ESORICS[C]. 2005. 80-97.

[7] CHUN S A, ATLURI V. Protecting privacy from continuous high-resolution satellite surveillance[A]. Proceedings of the 14th IFIP 11.3 Annual Working Conference on Database Security[C]. 2000.233-244.

[8] ATLURI V, SHIN H, VAIDYA J. Efficient security policy enforcement for the mobile environment[J]. Journal of Computer Security,2008, 16(4)∶ 439-475.

[9] BELUSSI A, CATANIA B, BERTINO E. A reference framework for integrating multiple representations of geographical maps[A]. Geographic Information Systems∶ Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems[C]. 2003. 33-40.

[10] BELUSSI A, BERTINO E, CATANIA B, et al. An authorization model for geographical maps[A]. Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems[C].2004. 82-91.

[11] BERTINO E, DAMIANI M L, MOMINI D. An access control system for a Web map management service[A]. Research Issues on Data Engineering∶ Web Services for e-Commerce and e-Government Applications, Proceedings 14th International Workshop[C]. 2004. 33-39.

[12] BERTINO E, THURAISINGHAM B, GERTZ M. Security and privacy for geospatial data∶ concepts and research directions[A]. Proceedings of the SIGSPATIAL ACM GIS 2008 International Workshop on Security and Privacy in GIS and LBS, SPRINGL 2008[C]. 2008. 6-19.

[13] BERTINO E, CATANIA B, DAMIANI M L. GEO-RBAC∶ a spatially aware RBAC[A]. Proceedings of the Tenth ACM Symposium on Access Control Models and technologies[C].2005. 29-37.

[14] BERTINO E, BONATTI P A, FERRARI E. TRBAC∶ a temporal role-based access control model[J]. ACM Transactions on Information and System Security (TISSEC), 2001,4(3)∶ 191-233.

[15] CHANDRAN S M, JOSHI J B D. LoT RBAC∶ a location and time-based RBAC model[A]. Proceedings of the 6th International Conference on Web Information Systems Engineering (WISE’05)[C].2005. 361-375.

[16] KUMAR M, NEWMAN R E. Strbac-an approach towards spatio-temporal role-based access control[A]. Communication, Network,and Information Security[C]. 2006. 150-155.

[17] AICH S, SURAL S, MAJUMDAR A K. STARBAC∶ spatiotemporal role based access control[A]. Proceedings of the 2007 OTM Confederated International Conference on the Move to Meaningful Internet Systems∶ Coopls, DOA, ODBASE, GADA ,and IS-Volume Part II[C].2007.1567-1582.

[18] ATLURI V, CHUN S A. A geotemporal role-based authorisation system[J]. International Journal of Information and Computer Security,2007, 1(1/2)∶ 143-168.

[19] DAMIANI M L, BERTINO E, PERLASCA P. Data security in location-aware applications∶ an approach based on RBAC[J]. International Journal of Information and Computer Security[C]. 2007, 1(1/2)∶ 5-38.

[20] RAY I, TOAHCHOODEE M. A spatio-temporal role-based access control model[A]. Proceedings of the 21st Annual IFIP WG 11.3 Working Conference on Data and Applications Security, 2007. 211-226.

[21] 张宏, 贺也平, 石志国. 一个支持空间上下文的访问控制形式模型[J].中国科学E辑, 2007, 37(2)∶254-271.ZHANG H, HE Y P, SHI Z G. An access control model based on context[J]. China Science E, 2007, 37(2)∶254-271.