基于推理樹的XML推理控制研究*

徐 錚,陳恭亮,李建華(.上海交通大學信息安全工程學院,上海0040;.上海交通大學電子信息與電氣工程學院,上海0040)

基于推理樹的XML推理控制研究*

徐 錚1,陳恭亮2,李建華2
(1.上海交通大學信息安全工程學院,上海200240;2.上海交通大學電子信息與電氣工程學院,上海200240)

信息安全中的推理問題是指攻擊者根據合法獲得的信息,利用信息之間關聯,推理出不能直接訪問的信息,從而造成敏感信息泄露的一種安全問題。推理控制是對信息間的這種聯系加以控制,防止敏感信息的推理泄露。XML是當前信息技術中最重要的信息載體之一,是Internet中數據交換和傳輸的默認標準,也是傳統關系數據庫的有力競爭者。文中研究了XML數據庫中信息的推理控制問題,定義了信息以及信息的規范化表示,針對XML數據庫中敏感信息的推理泄露,引入了推理樹的概念,提出了一種新的推理通道的刻畫方法,并提出了相應的動態推理控制策略,在保證信息安全的基礎上,使文檔中的信息最大可用。

XML 推理通道 推理控制

0 引 言

從已知信息推理出未知信息,既是日常生活中人們獲取新知識的手段,也是科學領域中一個重要的研究命題。在安全訪問控制技術逐漸成熟的今天,推理技術已經成為威脅信息安全的主要因素之一。如何防止敏感信息的推理泄露,已經成為當今信息安全學科的一個研究重點。

信息本身并不是孤立存在的,不同的信息之間有著內在的聯系,這些聯系可以使得用戶可以根據合法獲得的信息推理出不可訪問的敏感信息。推理來源信息的復雜性使得推理過程具有很大的不確定性,因此推理問題難于刻畫。

推理問題的研究最早應用于傳統關系數據庫。數據庫推理是指用戶根據可以從數據庫中合法獲取的信息和數據庫外部的知識進行推理,得到無訪問權限信息的過程。外部知識的多樣性使得推理的途徑異常復雜,推理控制問題也就異常復雜。數據庫設計者必須面對和解決針對敏感信息的推理攻擊。隨著安全數據庫系統的深入研究,推理同樣作為非法獲取敏感信息的手段,被納入到安全系統評估體系之中,促進了數據庫推理相關研究的發展[1]。

XML是當前信息技術中最重要的信息載體之一,是Internet中數據交換和傳輸的默認標準,也是關系數據庫的有力競爭者,針對XML的安全問題研究成為信息安全的重要研究方向之一,而XML推理控制則是其中的一個重要內容。

類似傳統的關系數據庫,對XML文檔的推理控制依賴于訪問控制。常見的訪問控制模型已成功的移植到了XML中,包括強制訪問控制、基于角色的訪問控制和自主訪問控制等。文獻[2-4]研究并改進了自主訪問控制的安全性和靈活性,文獻[5]把強訪問控制和細粒度訪問控制結合起來,通過細粒度提高了訪問控制的靈活性,文獻[6-8]研究了基于角色的訪問控制。

已有的XML推理研究主要有關聯推理和約束推理等。文獻[9-11]對約束的表現形式和優化等問題進行了研究,提供了XML約束推理控制的基礎。文獻[12-13]對XML文檔中常見的函數依賴進行了細致的研究,并給出了推理規則和算法。Yang[14]分析了XML文檔中三種特別的約束以及它們在推理攻擊中的作用,該文的特點是采用了與或圖[15]來刻畫推理過程,用解圖來解決推理控制問題。與或圖與人類思維的推理過程具有一定的相似性,用來刻畫推理問題非常清晰,但是,與或圖的復雜性對構造與或圖的解圖造成了一定的困難,可以進一步的改進。

推理通道的是刻畫推理過程的一種有效方法,推理控制問題都可以歸納為對推理通道檢測和破壞。本文提出了一種新的推理通道構造方法——推理樹。推理樹是有效推理通道的有機組合,包含了所有可能的推理通道,借助推理樹可以判斷用戶的查詢行為是否會造成敏感信息的泄露。以推理樹為基礎,對用戶的查詢行為進行正向模擬,找出并破壞可能存在的推理通道,對XML文檔進行動態的推理控制。

1 相關技術介紹

1.1 XM L和XM L文檔

XML是描述半結構化數據的一種標記語言, XML文檔是XML數據的基本組織形式。XML文檔由一系列嵌套的元素和值組成,元素由一對表示開始和結束的標記界定,標記可以任意[16]。文檔結構用DTD[17]或XML Schema[18]定義。

XML文檔一般以樹的形式表示,即用(V,E, root)表示文檔的樹狀結構。其中V是XML文檔樹中所有節點的集合,E為XML文檔樹中所有邊的集合,root為XML文檔樹的唯一根節點。樹中節點對應于文檔的元素和值;邊表示節點之間的父子關系。文檔樹中的節點可以通過路徑表達式定位。路徑表達式是一個被‘/'分隔的符號序列,形如/e0/e1/ e2…/en。如果初始元素節點e0為文檔的根節點,則路徑表達式為絕對路徑表達式,否則為相對路徑表達式。由路徑表達式確定的子樹是以en為根節點確定的子樹。XML文檔是XML數據庫的基本存儲單位。

1.2 XPath

Xpath是W3C推薦的查詢XML文檔的通用標準,是一種用于在XML文檔樹中尋找信息的語言,可以用來在XML文檔中對元素和屬性進行遍歷。Xpath使用路徑表達式來選取XML文檔中的節點或節點集。在Xpath中,XML文檔被當作節點樹對待。一個XPath表達式可以通過下面的語法定義:

式中,ε、l和*分別用來表示空路徑、標記和通配符。∪、/和//分別表示并、在當前節點的子節點中查找和在當前節點的子孫節點中查找。p[q]中的q是限定條件,q可以由以下表達式定義:

式中,c是常量,∧、∧和?分別表示合取、析取和非。

2 推理問題的刻畫

推理通道是刻畫推理問題的有效手段之一,信息和推理規則是構成推理通道的兩大要素。信息存在于XML文檔中,是一種數據結構。信息是本次推理控制研究的基本對象,是推理過程中的最小單位。本節先給出了信息的基本定義以及信息的規范化表示,然后對推理規則進行了簡單的介紹,最后提出了推理樹的生成算法。

2.1 信息的定義

推理依賴的來源信息是刻畫推理問題關鍵所在。可用于推理的信息來源可分為兩類:一是XML文檔中包含的信息,二是XML文檔外部的信息。完全控制這兩類信息是不可實現的,但是對于前者,可以通過訪問控制等手段限制用戶對于文檔數據的訪問。因此,推理問題的刻畫一般假設一個前提,即“封閉世界假設”[19]:用于推理的信息來源必須存在與XML文檔中,推理得到的信息必須存在于XML文檔中。

信息是一種結構,在XML文檔樹中以一棵子樹表示,所以信息的定義要能描述結構中的節點以及節點之間的關系,并且能夠定位節點。

定義1(信息)information={PNE,PNA,child, pnr,其中:

1)PNE是信息結構中節點的集合,PNA是信息結構中屬性的集合,pnr沂PNE。

2)pnr是結構樹的根節點。

3)child?PNE×(PNE∪PNA),child描述了信息樹中的二元關系,包括結構中所有的父子關系以及屬性和所屬元素的對應關系。

對于任意pn沂PNE(除了pnr),必存在唯一pn`沂PNE,使得(pn`,pn)?child。

對于任意pn沂PNA,必存在唯一pn`沂PNE,使得(pn`,pn)?child。

4)fe是一個函數,對于任意的pn沂(PNE∪PNA),fe(pn)返回pn的Xpath路徑表達式。

2.2 推理規則和推理通道

XML文檔中信息之間廣泛存在的聯系是推理得以實施的基礎,因此有必要采用統一的方法刻畫這些聯系被用于推理的過程。

推理規則是推理的形式化表示。推理規則的形式類似于A→B,其中A是信息的集合,稱為規則左部,是推理的來源信息;B稱為信息右部,是推理的結果,一般B只是一條信息。推理規則以關聯規則為基礎擴展而成。關聯規則[20]是通過數據挖掘技術獲得的數據間深層次的聯系,這種聯系不易察覺,因此由關聯規則造成的推理泄露更加隱蔽;同時,信息之間還有簡單的蘊含關系,這些關系也會用于推理,但是關聯規則無法覆蓋的這樣的包含關系,所以要對關聯規則擴展才能生成完備的推理規則。

推理通道是是推理規則的組合,形式如f= f1f2f3f4,其中f1、f2、f3和f4都是推理規則。推理通道中相鄰的推理規則之間相互關聯,即后一條推理規則的左部是前一條推理規則右部的信息子集。

2.3 構造推理樹

推理是由攻擊者實施的不確定的行為,不同的來源信息組成不同的推理通道,造成了推理過程的復雜性和多樣性,對于攻擊者可能存在的推理行為以及推理結果,任何安全控制機制都難以捕捉。

盡管推理過程是復雜的,但是攻擊者每一次的推理行為都要通過信息的之間的聯系即推理規則,這就為推理過程的刻畫提供了可行的方法,即根據推理規則集合,預先計算出所有可能推理通道,某些通道可能用到了相同的規則、有相同的部分,這些推理通道的片段是可以合并的。所以全部的有效推理規則生成的推理通道,會覆蓋所有的可能推理通道,這個完備的大推理通道相當于把所有的推理通道有機的組合起來,以樹狀結構表示,被稱為推理樹。每個可能的推理通道都是推理樹的一棵子樹。

算法1 構造推理樹

輸入:敏感信息M,推理規則集合C。輸出:推理樹t。

步驟1:將敏感信息M設為t的根節點。

步驟2:集合S為推理樹t中所有葉子節點的集合,若推理樹中只有根節點,則根節點加入S。變量X遍歷S。

(a)遍歷推理規則集合C,若X為某規則f的右部,則規則f左部的所有信息插入為X節點的子節點。

(b)若推理樹無節點增加,返回t。

步驟3:重復步驟2。

推理樹生成算法的基本思想是反向推理計算所有可能的推理通道,處理過程是首先獲得能夠直接推理出敏感信息的推理規則,然后針對規則的左部信息繼續反向推理。這是一個遞歸的過程。

3 推理控制策略

根據上一節可知,各種不同的推理過程需要的信息來源可能不同,但都可以用推理樹的子樹形式表現。因此,可以以推理樹為依據,進行推理控制。傳統的靜態推理控制策略通過預先隱藏XML文檔中部分信息,破壞了所有的可能通道,但是這種策略對于文檔的可用性有較大影響,由于用戶的需求是多種多樣的,被隱藏的信息可能是用戶需要的唯一信息,而這條信息本身不會造成敏感信息的泄露。因此為了不影響正常用戶的日常使用,需要采用動態的推理控制策略。

在動態的推理控制策略中,模擬推理過程必不可少的部分。推理控制要破壞的是攻擊者用于推理的最后一條信息。推理樹內所有的信息攻擊者都未獲得,當用戶查詢文檔時,先判斷查詢結果包含的信息以及用戶已經掌握的信息是否會造成敏感信息的直接泄露或推理泄露。如果不會造成泄露,則將結果返回,同時對推理樹進行動態更新,保證推理樹的有效性。這樣我們就一直掌握著攻擊者無法獲得的信息,這些信息是攻擊者進行下一輪推理所需要的信息的集合。這樣循環往復,當攻擊需要最后一條信息來推理出敏感信息時,破壞這條信息,阻止敏感信息的泄露。推理樹的更新也能夠防止攻擊者的多次查詢攻擊造成的推理泄露。推理控制的流程如圖1所示。

圖1 推理控制流程Fig.1 Process of inference control

3.1 推理泄露的判斷

首先,要確定泄露的信息是否在推理樹中。如果不在,則該條信息不是控制關心的內容,可以直接返回;如果信息在推理樹中,則要判斷信息是不是敏感信息以及會不會造成敏感信息的推理泄露。

算法2 信息泄露判定

輸入:攻擊者查詢結果中包含的信息M,推理樹t。

輸出:查詢結果是否返回,新的推理樹t。

步驟1:在推理樹中找到所有的信息M(M可能包含在多條規則中,在推理樹內重復出現),集合為S。

步驟2:如果S不為空,從S中任選一個節點A, S=S-{A}。

(a)如果A有兄弟節點,跳到步驟3。

(b)如果A不是敏感信息節點,A=A的父節點,跳到(a),否則跳到(c)。

(c)A是敏感信息節點,推理模擬結束,查詢結果不可返回。

步驟3:重復步驟2。

步驟4:推理模擬結束,查詢結果可以返回,對推理樹中的所有信息M執行刪除算法。

算法2防止了敏感信息的推理泄露,同時步驟2中的(b)保證了敏感信息不會直接泄露。判斷兄弟節點的操作簡單高效,易于實現。

3.2 推理樹的更新

如果用戶查詢的信息被返回,表明用戶掌握的信息有所增加,新增的信息可能會激活新的推理規則,推理出新的信息,循環往復,造成更多信息的泄露;已泄露的信息如果這些信息繼續在推理樹中存在,將會影響到推理控制的效率,所以要對推理樹進行更新。

算法3 推理樹的更新

輸入:被刪除的信息M,推理樹t。

輸出:更新的推理樹t。

步驟1:從推理樹t中獲取所有的信息M節點,組成集合D。

步驟2:如果D不為空,從D中任選一個節點A,D=D-{A}。

(a)如果A有兄弟節點,刪除以A為根節點的子樹。

(b)如果A沒有兄弟節點,A=A的父節點,跳到(a)。

步驟3:重復步驟2。

算法2和算法3保證了敏感信息既不會直接泄露也不會推理泄露,推理樹中保存了攻擊者尚未直接獲得的信息以及根據已掌握的信息無法推理得到的信息,使得攻擊者根據已有信息不會構造出能獲得敏感信息的推理通道。通過推理樹的更新,無用的信息節點和子樹會被刪除,這些信息節點和子樹形成的推理通道不再影響推理控制,刪除后會提高控制的效率。

3.3 推理控制策略分析

本節從完備性和有效性兩個方面對推理控制進行分析。

(1)推理控制的完備性

攻擊者推理出敏感信息的方法有很多種,推理控制的完備性就是要求所有有效的推理通道都都蘊含在了推理樹中,這樣無論攻擊者采用何種推理規則進行推理,都能夠被推理控制阻止。

定理1.推理樹包含了所有有效的推理通道

證明:反證法。假設存在一條推理通道f= f1f2f3f4能夠推理出敏感信息M,但推理通道f不在推理樹T中。由假設可知,推理規則f4的右部是敏感信息M,根據算法1,推理規則f4會被添加到推理樹中,成為推理樹的一條分支,且推理規則f4的左部會成為推理樹的葉子節點。依次類推,f1、f2和f3也會在算法1中被遞歸加入到推理樹中,成為推理樹的一顆子樹,這與假設矛盾,因此假設不成立。

(2)推理控制的有效性

對文檔發起查詢的用戶中,只有一小部分是攻擊者,大部分都是有正常需求的用戶,他們有著不同的需求。推理控制的有效性就是要滿足正常用戶的不同需求,要在保證文檔信息安全的基礎上,使文檔信息最大可用。

推理通道的有效性通過推理樹的更新算法保證,通過對推理樹的更新和刪減,去除無需控制的信息,只在樹中保留繼續推理需要的信息。用戶的查詢結果中包含的信息分為兩種情況:第一種情況中,推理樹中以該信息為根節點的子樹,是一條推理出該信息的推理通道,由于該信息已經泄露,因此攻擊者是否采用推理通道推理出該信息已經不再重要,這棵子樹需要被刪除。第二種情況中,泄露的信息作為推理來源信息,激活新的推理通道,參與推理其他信息,這是一個存在循環往復可能性的行為。算法2和算法3綜合考慮了這兩種情況,保證了推理控制的有效性。

為了驗證推理控制的完備性和有效性,本文設計了相應的驗證試驗。試驗針對某醫院的病例信息數據庫進行。該數據庫記錄了病人的病例信息,對外提供不同的等級的信息查詢服務,例如病人的病癥信息是敏感信息,無法直接訪問,但是可以通過主治醫師、住院信息、用藥信息等合法信息推理出來。試驗中用python實現了推理樹生成模塊(根據算法1)、敏感信息泄露判定模塊(根據算法2)和推理樹更新模塊(根據算法3)。

試驗步驟:

1)對病例信息數據庫進行信息挖掘,找出數據庫中的所有信息,生成信息閉包S。

2)根據信息閉包S和推理規則集合F,生成推理樹T。

3)依據推理通道,模擬推理過程,向數據庫發起查詢請求。

4)觀察推理樹的變化,記錄查詢返回的結果

試驗一通過改變數據庫信息復雜度和推理規則數量,檢測是否存在敏感信息推理泄露,驗證推理控制的完備性,結果如表1所示。

表1 推理控制完備性試驗結果Table 1 Result of Completeness Experiment

試驗二通過采用不同的推理通道進行多次推理攻擊,驗證推理控制的有效性,結果如表2所示。

表2 推理控制有效性試驗結果Table 2 Result of Effectiveness Experiment

由試驗結果可知,推理通道被完全控制,無敏感信息推理泄露,推理控制具有完備性和有效性。

4 結 語

推理活動在為人們帶來新的信息和新的知識的同時,也對信息系統的信息安全造成了嚴重的威脅。本文通過構造完備的推理樹,對攻擊者可能采用的推理過程進行模擬,監測攻擊者的推理行為。通過對推理樹的不斷更新,實現對推理過程的動態控制,在敏感信息推理泄露的最后一個推理環節破壞推理通道,在保證了XML文檔信息安全的同時,使XML文檔中的信息最大可用。文獻[14]中Yang等人采用的與或圖的方法,雖然也能達到推理控制的效果,但是邏輯結構復雜,需要借助布爾表達式判斷敏感信息的泄露。與Yang等人的方法相比,推理樹的方法更簡單直接,推理泄露的判斷和控制集中在樹的操作,這方面的算法更加成熟,也更易于實現。

[1] BREWSTER Keith.Inference and Aggregation Issues In Secure Database Management Systems[R].WilliamsburgVA,USA:NCSC Technical Report,1996.

[2] DAMIANI Ernesto,VIMERCATI Sabrina.,PARABOSCHIStefano,etal.A Fine-Grained Access Control System for XML Documents[J].ACM Transactiongs on Information and System Security,2002,5(2):169-202.

[3] BERTINO Elisa,CASTANO Silvana,FERRARI Elena, et al.Specifying and Enforcing Access Control Policies for XML Document Sources[J].World Wide Web, 2000,3(3):139-151.

[4] BERITINO Elisa,CASTANO Silvana,FERRAI Elena. Securing XML Documents with Author-x[J].IEEE Internet Computing,2001,5(3):21-31.

[5] 李斕,何永忠,馮登國.面向XML文檔的細粒度強制訪問控制模型[J].軟件學報,2004,15(10):1528-1537. LI Lan,HE Yong-zhong,FENG Deng-guo.A Fine-Grained Mandatory Access Control Model for XML Documents[J].Journal of Software,2004,15(10):1528-1537.

[6] CHANDRAMOULI Ramaswamy.Application of XML Tools for Enterprise-Wide RBAC Implementation Tasks [C]//Fifth ACM Workshop on Role-Based Access Control.New York,NY,USA:ACM,2000:11-18.

[7] HITCHENS Michael,VARADHARAJAN Vijay.RBAC for XML document stores[C]//Third International Conference.Berlin,Germany:Springer,2001:131-143.

[8] VUONG N.Nathan,SMITH Geoffrey,DENG Yi.Managing Security Policies in a Distributed Environment Using Extensible Markup Language[C]//The 2001 ACM Symposium on Applied Computing.New York,NV,USA: ACM,2011:405-411.

[9] FRANK Jeremy,JONSSON Ari.Constraint-Based Attribute and Interval Planning[J].Constraints,2003,8 (4):339-364.

[10] BISTARELLI Stefano,MONTANARI Ugo,ROSSI Francesca.Semiring-Based Contraint Satisfaction and Optimization[J].Journal of the ACM,1997,44(2): 201-236.

[11] MADIRAJU Praveen,SUNDERRAMAN Rajshekhar, NAVATHE Shamkant,et al.Semantic Integrity Contraint Checking for Multiple XML Databases[J].Database Management,2006,17(4):1-19.

[12] 談子敬,龐引明,施伯樂.XML上的函數依賴[J].軟件學報,2003,14(09):1564-1570. TAN Zi-jing,PANG Yin-ming,SHIBo-le.Reasoning about Functional Dependency for XML[J].Journal of Software,2003,14(9):1-19.

[13] 殷風麗,趙碩.XML局部函數依賴[J].齊齊哈爾大學學報,2005,21(04):54-55. YIN Li-feng,ZHAO Shuo.Local XML Function Dependencies[J].Journal ofQiqihar University,2005,21 (4):54-55.

[14] YANG Xiao-Chun,LIChen.Secure XML Publishing without Information Leakage in the Presence of Data Inference[C]//The 30th International Conferece on Very Large Data Bases.Toronto,Canada:Morgan Kaufmann,2004:96-107.

[15] NILSSON J.Nils.Principles of Articial Intelligence [M].Tioga Publishing Company.The 1st edition. Berlin,Germany:Springer,1982:99.

[16] BRAY Tim,PAOLI Jean,MALER Eve et al.Extensible Markup Language 1.0 specification[DB/OL].W3C Recommendation,2000(10-06)[2014-11-14].http://www.w3.org/TR/2000/REC-xml-20001006.

[17] BOSAK Jon,BRAY Tim,CONNOLLY Dan et al. Guide to the W3C XML Specification(“XMLspec”) DTD[DB/OL].W3C Recommendation,2000(03-07)[2014-11-14].http://www.w3.org/XML/ 1998/06/xmlspec-report.

[18] THOMPSON S.Henry,BEECH David,MALONEY Murray,MENDELSOHN Noah.XML Schema Part 1: Structures Second Edition[DB/OL].W3C Recommendation,2000(10-06)[2014-11-14].http:// www.w3.org/TR/xmlschema-1/#nonnormative-schemaDTD.

[19] DENNING E.Dorothy.An Intrusion-Detection Model [J].IEEE Transactions on Software Engineering, 1987,13(2):222-232.

[20] Wikipedia contributors.Association Rule learning[DB/ OL].Wikipedia,The Free Encyclopedia,2014(11-29)[2014-11-14].http://en.wikipedia.org/w/index.php?title=Association_rule_learning&oldid= 635909706.

XU Zheng,(1989-),male,graduate student,majoring in information security and ID authentication.

陳恭亮(1961—),男,教授,博士生導師,主要研究方向為身份認證,信息安全,密碼學;

CHEN Gong-liang,(1961-),male,professor,doctoral tutor,mainly engaged in ID authentication,information security and cryptography.

李建華(1965—),男,教授,博士生導師,主要研究方向為信息安全。

LIJian-Hua,(1965-),male,professor,doctoral tutor, mainly engaged in information security.

Inference Control of XM L based on Inference Tree

XU Zheng1,CHEN Gong-liang2,LIJian-hua2
(1.School of Information Security Engineering,Shanghai Jiao Tong University,Shanghai200240,China; 2.School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai200240,China)

Inference in information security is a problem of indirect disclosure of sensitive information,that is,the adversary takes advantage of the correlations among information and deduces the inaccessible information.Inference control aims to control the correlation among information,and further to prevent inference disclosure of sensative information.XML,as one of themost essential information carriers in information technology,is the agreed standard of Internet data exchange and transmission,and also the competative rival of tranditional relational database.Inference control of XML database is studied,information and its standardized expression defined.Aiming at the inference leakage of sensative information in XML database,the concept of inference tree is introduced,a novel inference channel proposed,and a relative dynamic inference control stratagy also suggested to balance the contradiction between security and availability of XML documents.

XML;inference channel;inference control

National Science Foundation of China under Grants No 61271220.

date：2014-09-07;Revised date：2014-01-27

國家自然科學基金項目(No 61271220)

TP393

A

1002-0802(2015)02-0208-06

徐 錚(1989—),男,碩士研究生,主要研究方向為信息安全,身份認證;

10.3969/j.issn.1002-0802.2015.02.019

2014-09-07;

2015-01-27