基于ＮＦＡ異構數據庫集成系統的查詢優化

摘要：XML文檔信息容量的增長、數據敏感程度的增加，對異構數據源集成系統提出了新的挑戰。為了降低查詢復雜度、提高查詢效率、增強數據庫文檔信息的安全性，本文采用感知情景因素的RBAC擴展模型，用一種新的基于XML的訪問控制描述語言描述異構數據庫集成系統中的訪問控制策略，并使用查詢優化技術，構造不確定性自動機（NFA）對用戶查詢進行重寫。通過這些技術，最終過濾掉異構數據庫集成系統中不符合安全策略的查詢，實現細粒度的訪問控制。

關鍵詞：NFA；XML；訪問控制策略；策略規范；查詢重寫

中圖分類號：TP311.13文獻標識碼：A 文章編號：1009-3044(2008)20-30211-04

Query Optimization for Heterogeneous Database Systems Based on NFA

XIAO Ye

(College of Software Engineering，Southeast University，Nanjing 210096，China )

Abstract:The increase of information capacity and data sensitiveness in XML documents has posed new challenges for heterogeneous database systems， such as how to minimize the complexity of query， how to promote efficiency， and how to preserve information security for database documents. To meet these challenges， this paper adopts an extended context-aware RBAC model， describes the access control policies in heterogeneous database systems using an XML-based access control language， and rewrites customer query by constructing NFA and using the optimized query technology. Through these technologies， we are able to prune any query that violates the security policy for fine-grained access control.

Key words: NFA; XML; access control policy; policy specification; query rewriting

1 引言

隨著XML文檔的信息容量日益增長，信息內容的敏感程度越來越強，對異構數據源集成系統提出了新的挑戰：如何降低查詢的復雜度、提高查詢效率、確保關鍵信息的安全性。目前，XML文檔訪問控制的方法可分成三大類[1]：文檔粒度的訪問控制算法、基于視圖的算法、依賴XML數據庫自身安全支持的方法。上述三類均存在缺陷：文檔級別算法，訪問控制的粒度太粗；基于視圖的算法，視圖的建立和維護成本太高；依賴XML數據庫自身安全支持的方法，應用范圍有限，不適用于層次數據庫、關系數據庫、面向對象數據庫。

針對這些不足，出現了一種既不基于視圖、也不依賴XML數據庫支持的細粒度訪問控制方法。Qfilter[1]將過濾器的概念應用到安全控制領域，通過對Xpath描述的訪問控制規則構造NFA不確定性自動機，過濾不符合安全策略的查詢。然而，Qfilter沒有給出訪問規則的具體描述形式，也沒有對情景因素提供支持。本文在Qfilter的基礎上，進一步改進過濾器，采用感知情景因素的RBAC擴展模型，使用XML[4]來描述安全策略，從而增強了系統的可維護性和通用性。另外，結合學校背景下的學生綜合信息查詢系統，建立過濾系統，通過對查詢語句的過濾和改寫，實現查詢優化。

2 系統架構

本系統屬于預處理性的過濾器，在查詢語句執行前，除去不符合訪問控制策略的查詢。系統主要包含XML策略庫、策略分析器、核心過濾器、Xpath解析器組件（如圖1）。用戶輸入的查詢條件經過Xpath查詢解析器解析，到達核心過濾器，立即觸發執行NFA不確定性自動機。自動機過濾掉不符合策略的查詢并通過改寫查詢，輸出安全的查詢。

圖1 查詢過濾器系統

2.1 策略分析器

在查詢過濾器系統中，策略分析器的作用是解析XML策略庫策略、連接XML策略庫和核心過濾器。首先定義為訪問控制規則四元組。策略分析器通過對XML策略庫中的策略文件的分析，提取出策略中角色、情景因素、客體對象、操作類型等信息，即訪問控制規則四元組，作為核心過濾器的輸入。

從策略入手，設計XPRM分析器和XPS分析器分別處理XPRM和XPS文件。XPRM分析器的輸入為XPRM文件，經過處理，輸出為三元組。每個XPRM文件包含多組授權操作（prm），分析器逐行掃描該文件，分析每一組授權操作信息（prm），每組都會包含一固定屬性（唯一的prm_id標識），以及選擇性地包含以下子元素中的一個或多個：授權操作涉及的角色名稱role_name，具體的授權許可標識符perm_id以及情景因素condition。下面給出具體算法：

XPRM分析器算法：XPRMAnalysis（XPRM.xml）

輸入：XPRM xml文件

輸出：XPRMResultSet集合

（1）XPRMResultSet＝1; XPRMResult＝1;

（2）for every prm in xprm//在xprm文檔中依次掃描prm

（3）{permId=perm_id element’s value in prm’ subelement;//獲取perm_id元素值

（4） roleName=role_name element’s value in prm’ subelement;//獲取role_name元素

（5） condition=condition element’s value in prm’ subelement;//獲取condition元素值

（6） wrap permId， roleName， condition in XPRMResult;//

（7） put XPRMResult in collection XPRMResultSet; //

（8）}

XPRM分析器分析過程結束后，將perm_id、role_name、condition記錄下來。

XPS分析器直接根據perm_id號，從XPS許可文件中關聯到相應的許可項。每條許可項包含實體對象的相關信息（object），如Xpath路徑；以及操作信息（operation）。XPS分析器結束，記錄object、operation。

XPS分析器算法：XPSAnalysis（XPRMResultSet，XPS.xml）

輸入：XPRMResultSet集合，XPS xml 文件

輸出：ResultSet集合

（1）for every XPRMResult in XPRMResultSet;

（2）{ if (perm_id in xps == permId in XPRMResult)

（3） { object=object element’s value in permission’s subelement;

（4） operation=operation element’s value in permission’s subelement;

（5） roleName=roleName in XPRMResult;

（6） condition=condition in XPRMResult;

（7） wrap permId， roleName， condition in Result;

（8） put Result in collection ResultSet;

（9） }

（10）}

最終，獲取了策略的訪問控制規則四元組群。在每一個四元組中，object是最主要的資源信息，我們利用該信息構建不確定性自動機（NFA），然后將＜rolename，condition，operation＞信息關聯到接受狀態信息中。

2.2 核心過濾器

核心過濾器以策略分析器輸出的訪問控制規則四元組作為輸入，其中object以Xpath形式描述了資源的信息。首先根據object，構建NFA不確定性自動機的主體，而后再將＜rolename，condition，operation＞信息關聯到接受狀態集合中，完成NFA的構造。

Xpath有四種基本定位路徑：/x、/*、//x、//*，其中“x”是用來表示定義的所有元素，*為通配符。對應于每個基本定位路徑，可建立相應的NFA碎片[1]（見圖2）。

圖2 基本定位路徑的NFA碎片

對一個完整的Xpath表達式，根據表達式中的每一個基礎定位路徑，先建立獨立的NFA碎片，而后按照定位路徑的先后順序將一個個NFA碎片拼接起來，即可得到該條Xpath語句的NFA。對于訪問控制模型中的多條策略，先根據單條策略構建NFA，而后，再將系統中由策略構建好的所有NFA組合起來，合并相同的狀態得到一個完整的NFA。通過增量構造算法來構造NFA，該算法在初始狀態下，NFA僅有一root狀態，以策略信息四元組P作為構造參數，具體描述如下：

算法：增量構造NFA算法IncNFAFun(NFA，P，root);

輸入：NFA初始狀態root，策略信息四元組P，NFA

輸出：NFA

(1)current =root ; next =1 ;Ai=1; F=1;

(2)for each Pi (＜ rolename，codition，object， operation ＞)in P

(3) {

(4) for each location step ls in ＜object＞ ofPi

(5) {if(current.containTransition(ls))

(6)next=current.move(ls);

(7)elsenext=current.creatEdge(ls);

(8)current=next;

(9) }

(10) if (final state k doesn’t belong to the acceptable states)

(11) { Ai =k; F=F∪Ai;}

(12) put ＜ rolename，codition，operation ＞ into Ai’s union

(13)}

將此算法應用到異構數據源集成系統中，來構造策略NFA。該系統以學校環境作為背景：以學生、老師、院系、課程、財務等基本信息內容為主要的客體對象，對這些信息，學校內不同部門、不同角色有各自的訪問權限，如，學生可以看到自己的基本信息、選修課程的具體信息、院系的基本介紹等。授課老師可以看到授課班級學生的基本信息、可讀寫課程成績。這些安全策略由XML文件來描述，經策略分析器分析處理后，可得到一個包含rolename、condition、object、operation元素的四元組，根據這些四元組中的object路徑通過IncNFAFun構造算法構造NFA自動機（如圖3）。

圖3 學生綜合信息查詢系統

當用戶的一條查詢語句Q作為系統的輸入時，系統執行自動機，建立相應的狀態表，該表包括三項內容：步驟、新查詢語句和狀態。讀取查詢語句中的每一步元素，根據元素類型，NFA查找匹配的轉換：

（1）確定性路徑：/x: 和一般的NFA一樣，查詢或者被接受或者被拒絕。

（2）不確定性路徑：Q中只有一個直接子表達式，除了確定性變換外還有“*”，“ε”變換。在NFA中，追蹤所有的變換類型。其中，//x，//*狀態需要進行迭代處理。

（3） 通配符“*”的重寫：一個帶有通配符的查詢Q常常匹配多個狀態變換。

（4）對“//”的重寫：對查詢Q中的“//x”和“//*”表示從當前的狀態轉換到其所有的后續狀態，在每個后續狀態處，查詢繼續向前，多條分支進行。對于//x/或者//*，首先重寫第一個“/”，寫出當前狀態到目標狀態的路徑（即將要繼續被執行的分支）。執行的每一個分支則從第二個“/”處重新開始。

3 性能分析

本過濾系統采用基于XML的訪問控制語言描述訪問控制策略。由于策略分析器在核心過濾器之前，就對XML策略文件進行解析，因而不影響NFA的構造時間。另外和Qfilter不同的是，本系統引入了角色的概念，并增加情境約束條件。構造NFA時，需在其葉子節點（即可接受狀態）上創建相應的關聯集合。

3.1 計算復雜度

本系統根據策略分析器提取的ACR規則建立NFA，構造的復雜度主要由如下因素決定：ACR的XPath路徑數與終態關聯集合中關聯的角色、情境因素、操作集合的數目，即與狀態數目和關聯集合數目有關。

過濾器的計算復雜度分為兩個部分：過濾器的創建、過濾器的實現的復雜度。本過濾器創建的復雜度為O(q+i)，其中q是策略的XPath語句的子路徑數，i為已建NFA的可接受狀態數。

過濾器的執行分為三種情況討論：當查詢語句不包括“/*”與“//”路徑時，計算復雜度為O(l+p)，其中l為查詢語句的子路徑數，p為關聯集合中元素的數量；當查詢語句包含“/*”路徑時，計算復雜度為O(n+p)，n為NFA的轉換數；當查詢語句包含“//”時，運行復雜度為O(m*n1*n2*…* nk*p )，其中m是查詢語句的子路徑，k是查詢語句“//”的數目，ni是當遇到第i個“//”時，當前狀態下子NFA的轉換數。

3.2 性能比較

查詢的執行情況可根據不同查詢按5種情況來比較與Qfilter的性能差別：

（1）當查詢語句同時被Qfilter與本系統接受時，本系統的執行時間將稍稍大于Qfilter。增加的時間為比較終態關聯集合中的角色與情境元素的時間。

（2）當查詢語句被Qfilter接受但被本系統拒絕，也就是說查詢語句已經到達了NFA的終態，但是不符合關聯集合中的約束條件，那么Qfilter中將無法過濾，而本系統中則過濾，不再查詢數據庫。因此在犧牲了關聯集合中關聯的小部分時間后，節省了查詢數據庫的大量時間。因此，在這種情況下本系統比Qfilter減少了查詢時間。

（3）當查詢語句同時被Qfilter與本系統重寫時，本系統的執行時間大于Qfilter。

（4）當查詢語句被Qfilter重寫但被本系統拒絕，本系統的執行時間小于Qfilter。

（5）當查詢語句同時被Qfilter與本過濾器拒絕，兩者消耗的時間一樣。

由此可見，用戶查詢時的安全環境越惡劣，本過濾系統性能的優越性就越強。

3.3 過濾粒度比較

與Qfilter相比，由于引入了角色概念，增加了情境約束條件，一些被Qfilter接受或者重寫的不安全查詢，可被本系統捕獲并拒絕這些惡意查詢。隨機生成100條查詢語句，比較Qfilter與本系統的查詢執行結果（見圖4）。由圖可知，本系統與Qfilter相比進一步細化訪問控制的粒度，提高了安全性。

圖4 本系統與Qfilter訪問控制粒度比較

4 結束語

本文基于擴展的RBAC訪問控制模型，考慮了情景感知因素，并使用XML文檔來描述模型，通過構造不確定性自動機，對用戶的查詢進行重寫，過濾掉不符合安全策略的查詢，實現了細粒度的存取控制。

參考文獻：

[1] Luo B， Lee D G.. Qfilter: Fine-grained run-time XML access control via NFA-based query rewriting [A].In: CIKM 2004[C]. Washington D C: Conference on Information and Knowledge Management， 2004.543-552.

[2] Diao Y， Franklin M J. High-performance XML filtering: An overview of Y filter [J].ICDE， 2003， 26(1):41-48.

[3] Ferraiolo David F. Proposed NIST standard for role-based access control [J].ACM Transactions on Information and System Security， 2001， 4(3):224-274.

[4] Rafae Bhatti， Elisa Bertino， Arif Ghafoor， et al. XML-Based Specification for Web Services Document Security [J]. IEEE Computer Society， April 2004.41-49.

[5] Murata M， Tozawa A， Kudo M. XML Access Control Using Static Analysis [J]. ACM Transactions on Information and System Security， 2006， 9(3):292–324.

[6] Andreas， Schaad. The Role-Based Access Control System of a European Bank: A Case Study and Discussion [J].ACM Symposium on Access Control Models and Technologies， 2001.

[7] Ramaswamy Chandeamouli. Application of XML Tools for Enterprise-Wide RBAC Implementation Tasks. In: SIGSAC ed. Proc. of the 5th ACM Workshop on Role-Based Access Control[C]， Berlin: ACM Press， 2000.

[8] Murata M， Tozawa A， Kudo M. XML Access Control Using Static Analysis. In: CCS’03[C]， Washington D ， USA， 2003.

[9] 劉國海，虞慧群，杜麗萍.一種基于NFA查詢重寫的XML過濾技術[J].華東理工大學學報(自然科學版)，2006，32(8):970-975.

[10] 李斕，何永忠，馮登國.向XML文檔的細粒度強制訪問控制模型[J].軟件學報，2004，15(10):1530-1536.