面向空間索引樹的授權機制

張穎君，馮登國，陳愷

(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.