王 聰，李瑞軒，辜希武，湯俊偉

華中科技大學 計算機科學與技術學院，武漢 430074

1 引言

在面向云計算服務的分布式應用環(huán)境中，XML（extensible markup language）對安全訪問控制起著越來越重要的作用[1]，安全策略廣泛使用可擴展的訪問控制標記語言（extensible access control markup language，XACML）進行表示。XACML是一種基于XML的開放標準語言，它設計用于描述安全政策以及對網(wǎng)絡服務、數(shù)字版權管理（digital rights management，DRM）和企業(yè)安全應用信息進行訪問的權限。XACML在2003年2月由結構化信息標準促進組織（OASIS）批準，開發(fā)用于標準化XML的訪問控制。XACML有時也稱可擴展的訪問控制語言（extensible access control language，XACL）。

XACML提供了一種基于屬性的訪問控制（attribute based access control，ABAC）方法[2]，其以實體屬性為核心，訪問決策基于主體、資源、操作、環(huán)境等實體屬性，能夠解決復雜信息系統(tǒng)中的細粒度訪問控制和大規(guī)模用戶動態(tài)擴展問題，為開放網(wǎng)絡提供更為靈活和安全的訪問控制技術[2]。

然而，由于XACML的高靈活性，安全策略定義的屬性區(qū)間之間更有可能產(chǎn)生交集，導致安全策略之間沖突發(fā)生得更為頻繁，安全策略的維護以及對于訪問請求的決策更為困難。盡管XACML本身提供了幾種合并算法來處理策略沖突，如允許優(yōu)先（permit-overrides algorithm）、拒絕優(yōu)先（deny-overrides algorithm）等，但是大量的沖突策略和冗余策略直接影響了策略決策的效率，預先檢測和消解策略沖突以及冗余能極大地減少策略決策所需處理的策略數(shù)。因此，XACML安全策略的沖突檢測與消解已經(jīng)成為一個亟待解決的問題。

本文從策略的描述語言XACML出發(fā)，分析了目前基于XACML的策略沖突檢測與沖突消解算法存在的不足。基于已有的策略沖突檢測算法，提出了一系列改進措施，包括建立規(guī)則索引和使用屬性值集合來統(tǒng)一描述XACML中靈活多變的目標條件定義。對于沖突檢測的結果，本文提出了一種新的一次性策略沖突消解算法。該算法采用有向無環(huán)圖（directed acyclic graph，DAG）的拓撲排序來計算規(guī)則合并優(yōu)先級，將所有規(guī)則映射成N維空間中的一個區(qū)域，然后按照優(yōu)先級由高到低的順序依次獲取沖突消解之后每條規(guī)則所決定的區(qū)域，一次性完成沖突消解。

本文組織結構如下：第1章對研究的問題和方法進行了概述；第2章介紹相關背景知識以及研究現(xiàn)狀；第3章介紹了沖突消解算法以及相應的改進；第4章詳細描述了沖突消解算法；第5章通過一系列實驗分析了沖突檢測以及沖突消解算法的性能以及影響算法性能的因素；第6章總結全文，并對未來的工作進行展望。

2 相關工作

XACML已經(jīng)被產(chǎn)業(yè)界廣泛采用，并成為工業(yè)界標準，目前已經(jīng)有多種投入應用的策略評估模型。XACML策略包含3個主要組件：Target（目標）、Rule（規(guī)則）和Rule CombineAlgorithm（規(guī)則合并算法）。

（1）Target定義了一組對于實體屬性的條件，這些條件描述了策略或規(guī)則能適用的請求集合。

（2）Rule主要由Target、Condition和Effect組成。Target和Condition共同定義了規(guī)則適用的請求集合，Condition的分析比較復雜，目前還沒有考慮Condition的沖突檢測研究，而Condition也不在本文的研究范圍內。Effect定義了這些適用的請求是被允許（Permit）還是拒絕（Deny）。

（3）Rule Combine Algorithm描述了當多條規(guī)則對同一個請求同時適用，并且評估結果產(chǎn)生沖突時，如何解決這些沖突的方法，也作為沖突消解的依據(jù)。主要有允許優(yōu)先、拒絕優(yōu)先等。

XACML通過多種屬性類型的細粒度刻化定義訪問控制策略，但同時也容易導致比較復雜和隱蔽的策略規(guī)則沖突類型。XACML自身提供了規(guī)則的合并算法，用戶在使用過程中大量沖突的產(chǎn)生和消解過程被屏蔽，用戶只用關心最終的評估結果即可，降低了模型的使用難度。然而，這種機制也存在一定的問題。首先，XACML將沖突處理的過程屏蔽，使得管理人員不易發(fā)現(xiàn)系統(tǒng)的安全漏洞，不能從管理視圖的角度分析沖突的位置和細節(jié)；另外，大量重疊的規(guī)則使得訪問控制策略評估請求時需要評估的規(guī)則數(shù)增加，影響對請求評估的效率，發(fā)現(xiàn)并預先消解沖突利于提升策略評估引擎的性能。

安全策略沖突分析的研究主要包括沖突（和冗余）檢測和沖突消解兩部分。目前對于沖突檢測方法的研究主要分為4類：（1）基于SAT技術；（2）基于描述邏輯；（3）基于策略描述語言；（4）基于本體推理。下面分別介紹4類沖突檢測方法與其存在的問題。

目前有一類研究采用SAT-solver技術對策略分析問題進行討論，然而這些研究都只能處理策略沖突檢測的問題，并不能解決沖突消解[3]。Lupu等人[4]提出的模態(tài)沖突模型根據(jù)模態(tài)符號將策略沖突定義為正向授權/負向授權沖突、正向職責/負向職責沖突、正向職責/負向授權沖突3種類型，借助模態(tài)符號沖突分析對安全策略進行靜態(tài)檢測。Moffett等人[5]研究了策略之間的關系，并且實現(xiàn)了一個策略檢驗工具在一個新策略加入到策略庫之前對策略進行檢查。McDaniel等人[6]在多條策略之間自動調和問題上進行了理論研究，并且證明了該問題是一個NP完全問題。

Wang等人[7]對XACML策略中的規(guī)則冗余進行了相關研究，其運用描述邏輯對XACML形式化，然后采用一些已有邏輯分析工具研究了策略冗余的問題。文獻[8]提出了一種基于描述邏輯的訪問控制策略沖突檢測方法，文獻[9]引入可廢止描述邏輯（defeasible description logics，DDL）來建模XACML中的策略，將得到的知識庫作為輸入，使用Pellet推理機對XACML策略進行冗余分析。上述研究都采用了基于形式邏輯的沖突檢測方法，該類方法通過邏輯推理檢測出語義沖突，但不易實現(xiàn)，在實際應用中需要開發(fā)相應的推理驗證工具。

也有一些研究基于策略描述語言的特點進行沖突檢測。文獻[10]分析了XACML中基于主體屬性和資源屬性層次關系的策略沖突，給出了算法的思想，但是算法復雜度較高，并且只進行了沖突和冗余檢測的研究，并沒有提出沖突消解的方法。類似地，文獻[11]研究了基于資源層次關系的策略沖突檢測，該研究采用有向無環(huán)圖表示資源之間層次關系，采用符號化模型檢驗的方法進行沖突檢測。文獻[12]將策略屬性歸一化為幾種基本類型，并相應地提出了沖突檢測的詳細算法。該研究提出了一種消解一個策略沖突對的算法，但是只能一次消解一對沖突，并不能從全局上考慮，進行一次性消解。劉江等人[13]提出了一種基于策略屬性分解的沖突檢測方法，然而該算法的性能有待提升。文獻[14]提出了一種基于多維整數(shù)空間的安全策略沖突檢測與消解方法。該方法將每個條件字段映射到一個整數(shù)集合，然后運用整數(shù)集合運算來進行沖突檢測與消解。然而并不是所有的條件字段都能一一映射到整數(shù)集合，該方法的適用范圍有所限制。

文獻[15]提出的基于對立屬性推理和文獻[16]提出的基于分離類推理的安全策略沖突檢測方法都屬于基于本體推理的沖突檢測方法，構建領域本體是應用該類方法的前提，而本體構建是一個難點。

上述研究主要針對沖突檢測提出了各種各樣的解決方案，然而上述研究中大多數(shù)并未涉及沖突消解的問題，只有少量研究針對其沖突檢測的方法提出了一些沖突消解的思路。文獻[13]從算法層面上提出了較為完整的沖突消解方法，然而該方法只能一次消解一對沖突，并不能實現(xiàn)大量沖突自動的一次性消解。文獻[14]基于多維整數(shù)空間的沖突消解與其沖突檢測的方案一樣，適用范圍有所限制。除此之外，還有少量專門針對沖突消解問題的研究。文獻[17]提出了一種訪問控制策略非一致性沖突消解方法，該方法把策略非一致性沖突的消解問題規(guī)約為一個SAT問題，并采用一種基于策略優(yōu)先級的方法消解沖突。文獻[18]提出了一種面向軟件定義網(wǎng)絡的訪問控制策略實時沖突檢測與解決方法，主要針對OpenFlow協(xié)議的無狀態(tài)性，提出一種基于FlowPath的實時動態(tài)策略沖突檢測與解決方法。

總體來說，安全策略沖突分析一直都是策略分析關注的一個重點問題，基于XACML的安全策略模型的研究很豐富，然而大多數(shù)XACML策略沖突分析研究工作從理論層面上提出各自的解決方案，并未深入到算法的層面。另外，現(xiàn)有的絕大部分沖突分析的研究著重于策略沖突檢測，對策略沖突消解的算法研究并不多，即使部分研究提到，也僅僅涉及到兩條規(guī)則之間沖突的消解，并未從全局上考慮所有沖突的一次消解。

針對上述問題，本文從算法的角度，在對現(xiàn)有的策略沖突檢測算法進行改進的同時，提出了一種全新的一次消解大量XACML策略沖突的算法。該算法并不依賴于現(xiàn)有各種沖突檢測算法的結構，可消解任何符合條件的策略沖突，適用范圍廣，靈活性也比較強。

3 沖突與冗余檢測

3.1 沖突檢測問題描述及算法思路

3.1.1 沖突與冗余定義

定義1如果存在一個請求使得兩條XACML規(guī)則做出的評估結果相反，則說這兩條規(guī)則之間存在沖突。

定義2對于某一條XACML規(guī)則R，如果對于R適用的所有請求，存在一條規(guī)則R′，使得R做出的評估結果始終與R′相同，則稱規(guī)則R冗余。

例如，對于下列5條規(guī)則：

R1:if((1≤x≤4)AND(2≤y≤5))→Permit

R2:if((1≤x≤4)AND(1≤y≤4))→Permit

R3:if((2≤x≤3)AND(5.5≤y≤7))→Deny

R4:if((3.5≤x≤6)AND(3≤y≤6))→Deny

R5:if((2≤x≤3)AND(3≤y≤4))→Permit

對于規(guī)則R2與R4，當請求內容為(x=3.5 ANDy=3.5)時，R2的評估結果為Permit，R4的評估結果為Deny，故規(guī)則R2與R4存在沖突。事實上當請求符合條件((3.5≤x≤6)AND(3≤y≤4))時，規(guī)則R2與R4都將做出相反的結果，將上述條件稱為沖突對(R2,R4)的沖突區(qū)域。一個沖突規(guī)則對除了包含產(chǎn)生沖突的兩條規(guī)則之外，還應包含如下信息：兩條規(guī)則Target的交集（沖突區(qū)域）以及交集的類型，沖突的規(guī)則合并算法。

對于規(guī)則R5，其適用的所有請求都適用于規(guī)則R1，并且規(guī)則R1與之做出的評估結果都相同(Permit)，故規(guī)則R5為冗余規(guī)則，稱規(guī)則R1為冗余規(guī)則R5的覆蓋規(guī)則。上述覆蓋規(guī)則R1和冗余規(guī)則R5構成一個冗余規(guī)則對(R1,R5)。

對于規(guī)則R1和R2，雖然存在請求同時適用于兩條規(guī)則，但此時兩條規(guī)則做出的評估結果是相同的，故規(guī)則R1和R2之間不存在沖突。規(guī)則R3與R1、R2的條件在屬性x上存在重疊，但在屬性y上沒有，故R3與R1、R2都不可能同時適用于某一請求，不存在沖突。圖1在二維空間中描述了上述例子中的沖突和冗余。

需要說明的是，XACML標準中一個Target可以有多個Subject構成一個Subjects，這些Subject之間是或的關系，只需要滿足一個Subject定義的條件即滿足Subjects標簽的條件，Resource等類似。然而，對于這樣的Target總能分解成若干個只包含一個Subject、Resource、Action和Environment標簽的簡單Target，因此下文只描述這種簡單Target沖突的檢測與消解。

Fig.1 Policy conflict and redundancy圖1 策略沖突和冗余

定義3一條規(guī)則R的Target對某一個屬性Α所定義的條件對應的屬性值集合稱為該Target或該規(guī)則在屬性Α上的投影，記為RA。

例如上述例子中，{1 ≤x≤4}為規(guī)則R1和R2在屬性x上的投影。

3.1.2 算法的目標與基本思想

首先，將規(guī)則的Target映射到一個N維空間，每一個維度表示Target中的一個屬性，每一條規(guī)則根據(jù)Target的適用條件表示成為空間中的一個區(qū)域。每一個規(guī)則的空間區(qū)域會在各個坐標軸上形成投影，這個投影表示規(guī)則的Target在該屬性上的條件，用該屬性上的一個集合表示。這樣Target在每一個屬性維度上表示成一個集合，形成一個屬性到屬性值集合的映射。對于Target沒涉及到的屬性，即認為Target沒有進行規(guī)定，相應屬性值集合為全集。

然后，尋找空間中存在重疊的區(qū)域，并且判斷空間重疊的類型：完全相等、包含或相交。如果重疊的兩個規(guī)則Effect相反，則兩條規(guī)則之間存在沖突；如果重疊的兩個規(guī)則Effect相同，當重疊的類型為完全相等或包含時，被包含的區(qū)域為冗余規(guī)則。兩個空間區(qū)域存在重疊的充分必要條件是兩個空間區(qū)域在每個屬性坐標軸上的投影都存在重疊。一個空間區(qū)域包含另一個空間區(qū)域的充分必要條件是前者在每個屬性坐標軸上的投影都包含后者在該坐標軸上的投影。因此尋找空間中存在的重疊，即計算屬性坐標軸中投影集合的交集以及投影相交的類型。兩個Target在N維空間中的重疊區(qū)域，稱為兩個Target的交集。

根據(jù)以上思想，得到規(guī)則沖突與冗余檢測算法，見算法1。用3.1.1小節(jié)中描述的沖突規(guī)則對和冗余規(guī)則對分別表示一對沖突和冗余。其中計算兩個Target交集在算法2中詳細描述。

算法1沖突檢測算法

輸入：Rule rule，要檢測沖突的規(guī)則。

輸出：Listconflicts，與規(guī)則rule沖突的沖突規(guī)則對列表；Listredundancies，涉及規(guī)則rule冗余規(guī)則對列表。

//到R-A索引中獲得與R有沖突可能的規(guī)則列表

3.2 R-A規(guī)則索引

規(guī)則的Target中，屬性被劃分為4類：主體（Sub-ject）、資源（Resource）、操作（Action）和環(huán)境（Environment）。只有4類屬性對應的條件同時被滿足時，該條規(guī)則才適用。也就是說，沖突和冗余規(guī)則檢測時，只有涉及對相同的資源做相同的操作的規(guī)則之間才可能存在沖突。假設一條規(guī)則針對文件file1是否允許被讀取，另一條規(guī)則針對文件file2是否允許修改，那么這樣的兩條規(guī)則之間檢測沖突是沒有意義的。只有當兩條規(guī)則涉及到相同的資源和相同的操作時，才對其檢測沖突和冗余。

為此，本文設計了一個資源-操作二級規(guī)則索引（resource-action，R-A規(guī)則索引），索引中一級索引為資源屬性，二級索引為操作屬性，其結構如圖2所示。只需要對位于同一條索引記錄的規(guī)則，即涉及到相同資源屬性和操作屬性的規(guī)則檢測沖突和冗余。

Fig.2 Two-level index structure of R-Arule圖2 R-A規(guī)則二級索引結構

3.3 基于屬性值集合的沖突檢測算法

3.1節(jié)提到，判斷兩個Target映射的n維空間區(qū)域是否存在重疊，需要判斷其在每一個屬性坐標軸上的投影是否存在重疊。首先將屬性的數(shù)據(jù)類型統(tǒng)一轉化為Integer、Long、Double、String，XACML規(guī)范定義的所有數(shù)據(jù)類型都可以映射到上述4種基本類型。

屬性坐標軸上的投影可以表示成為一個集合。根據(jù)該屬性在Target中Match函數(shù)的不同，集合可以采用單值集合、區(qū)間和正則集3種形式統(tǒng)一表示。單值集合表示只包含一個值的集合，用于表示Equal函數(shù)；區(qū)間由一個上界和下界表示，用于表示Greater than和Less than之類的比較函數(shù)，上下界都既可能是開區(qū)間也可能是閉區(qū)間；正則集用一個有限自動機來表示，用于表示正則式匹配的函數(shù)。另外，字符串忽略大小寫的相等函數(shù)也用正則集來表示。

為了表示和運算的簡便，在用有限自動機表示正則集合時，做了一點優(yōu)化。用字符區(qū)間代替原有的單個字符作為有限自動機中狀態(tài)轉換函數(shù)的條件，這樣做大大減少了狀態(tài)轉換函數(shù)的數(shù)目，也極大減少了有限自動機的交集運算。例如：表示正則集[b-/uffff][/d/D]*，該正則式表示所有大于等于“b”的字符串，簡化前后的有限自動機如圖3所示，其中圖3（a）為簡化前的自動機，圖3（b）為簡化后的自動機。

Fig.3 Simplified representation of finite automata圖3 有限自動機簡化表示

這樣，規(guī)則沖突與冗余檢測算法的核心也就是對各屬性值集合求交集。3種屬性值集合之間求交集存在下列情形。

情形1單值集合與3種集合中的任意一種求交集。

這種情況下，只需要判斷另外一個集合中是否包含該單值集合包含的值。若包含，則判斷另外一個集合包含元素的個數(shù)，如果大于1則為包含關系，否則為相等關系。

情形2區(qū)間與區(qū)間求交集。

這種情況下，可以通過比較區(qū)間的端點與端點的開閉狀態(tài)，直接判斷出交集以及相交的類型。

情形3正則集與正則集求交集。

可以利用有限自動機求交集的算法，該算法已經(jīng)有了豐富的研究，文獻[12]中也有詳細描述。

情形4正則集與區(qū)間求交集。

此處的區(qū)間必然是字符串區(qū)間。將字符串區(qū)間轉化為有限自動機表示的正則集，并利用正則集之間的交集算法求得交集。將字符串區(qū)間轉化為有限自動機的算法在相關文獻[12]中已有表述，本文不做詳細敘述。

對屬性值集合求交集運算并得出相交類型之后，得出計算兩個Target交集的算法，見算法2。

算法2Target交集算法

輸入：Targett1,t2，要計算交集的兩個Target。

輸出：Target intersection，兩個Target的交集，依然是Target形式；type，交集的類型，無交集，相等，t1包含t2，t1是t2子集或t1和t2部分相交。

//建立兩個Target的屬性集合映射

4 沖突消解

4.1 沖突消解問題描述與算法思路

由第3章的沖突檢測算法可得到一系列的沖突規(guī)則對，每個沖突規(guī)則對的兩條規(guī)則Target之間存在一定的重疊，沖突消解的任務就是根據(jù)重疊部分規(guī)則的合并規(guī)則（允許優(yōu)先或拒絕優(yōu)先等），選擇一條覆蓋的規(guī)則，并在被覆蓋的規(guī)則中把重疊部分除去。例如，圖4中R1和R2為兩條規(guī)則，其存在的沖突如圖4（a）所示，按照合并規(guī)則，在重疊部分R2將覆蓋掉R1，那么沖突消解之后，將R1的重疊部分從原規(guī)則中除去，形成新的兩條無沖突的規(guī)則，如圖4（b）所示。

Fig.4 Conflict resolution圖4 沖突消解

上面描述了在兩個屬性x、y上兩條規(guī)則沖突的情況，對于多個屬性以及多條規(guī)則沖突的情形類似。每一個屬性都對應一個維度，假設總共有N個屬性，那么每一條規(guī)則的Target都對應一個N維的超矩體空間，K條規(guī)則將空間劃分成許多個小區(qū)域，每一個小區(qū)域都是一條或多條規(guī)則的重疊。多條規(guī)則同時適用于重疊區(qū)域的條件，當其中有規(guī)則的Effect不同時，即產(chǎn)生了沖突，規(guī)則的合并算法決定了重疊區(qū)域最終具有決定權的規(guī)則。于是，沖突消解的問題轉化成為每一塊重疊區(qū)域找到其最終具有決定權的規(guī)則。下面以4條規(guī)則、3個屬性為例，描述沖突消解算法的總體思路，規(guī)則例子如表1所示。

根據(jù)3.1節(jié)的描述，沖突檢測的結果包含了沖突規(guī)則對和冗余規(guī)則對；首先對存在的冗余進行處理，即刪除冗余的規(guī)則；另外，每個沖突規(guī)則對還記錄了沖突的類型，包括完全覆蓋和僅存在交集等，對于一個規(guī)則被完全覆蓋并且根據(jù)規(guī)則合并算法也不優(yōu)先保留該規(guī)則的情況，也只需要刪除被覆蓋的規(guī)則即可。以上兩種情況不多敘述，在進行沖突消解之前進行預處理，下面直接描述每對沖突規(guī)則之間存在交集但不完全覆蓋的情況。

Table 1 Rule examples表1 規(guī)則示例

每塊區(qū)域具有決定權規(guī)則的選擇依據(jù)為事先設定好的規(guī)則合并算法，規(guī)則合并算法描述的是當兩條規(guī)則同時適用于一個請求時，如何合并兩條規(guī)則各自的評估結果，算法主要有允許優(yōu)先、拒絕優(yōu)先等。根據(jù)每一對沖突的規(guī)則合并算法，所有沖突規(guī)則對可以產(chǎn)生一個有向圖，根據(jù)有向圖的拓撲排序決定的規(guī)則優(yōu)先級來選擇。

每一個重疊區(qū)域在各個坐標軸上會投影成一個片段（Split），這些片段對每個坐標軸進行了劃分。例如上述例子中x軸、y軸和z軸劃分的片段如圖5所示。

Fig.5 Attribute axis division圖5 屬性軸劃分

為了簡便，圖5中沒有區(qū)別每個區(qū)間的開閉情況，而具體實現(xiàn)的時候需要考慮。每個片段中間的規(guī)則表示所有投影到該片段的規(guī)則集合，這些規(guī)則成為該片段的投影規(guī)則。單個點也能形成一個片段，如z軸只有z=read和z=write兩個片段。

這樣，在每個坐標軸上選取一個片段就能對應一個三維空間的區(qū)域，而覆蓋這個區(qū)域的規(guī)則由每個片段中投影到的規(guī)則集合求交集求得。例如圖中x-y平面的左下角區(qū)域，x軸和y軸上片段投影規(guī)則集合求交集之后為(A,C)，若在選取z軸上的read片段，則覆蓋該三維區(qū)域的規(guī)則依然有A和C，決定該區(qū)域的規(guī)則即為A、C之間優(yōu)先級高者；而對于x-y平面的右上角區(qū)域，x軸和y軸上片段投影規(guī)則集合求交集之后為空集，表示無論z軸選取哪個片段，所確定的區(qū)域都沒有任何規(guī)則覆蓋到。

確定了每個坐標軸的劃分之后，根據(jù)規(guī)則優(yōu)先級由高到低依次確定該規(guī)則決定的區(qū)域，完成沖突消解的過程。采用了一種稱作空間區(qū)域選擇樹的數(shù)據(jù)結構來確定每條規(guī)則決定的空間區(qū)域。

4.2節(jié)詳細介紹沖突的有向圖表示以及拓撲排序決定規(guī)則優(yōu)先級，4.3節(jié)詳細介紹屬性軸劃分的算法，4.4節(jié)詳細介紹構建空間區(qū)域選擇樹的算法以及優(yōu)化。

4.2 有向無環(huán)圖與規(guī)則優(yōu)先級

上一節(jié)中提到，任何一個沖突對的兩條沖突規(guī)則之間根據(jù)規(guī)則合并算法存在覆蓋與被覆蓋的關系，即覆蓋的優(yōu)先級。把每一條規(guī)則作為一個結點，每一個沖突對的覆蓋關系作為一條有向邊，由覆蓋的規(guī)則指向被覆蓋的規(guī)則，這樣就得到了一個全局的沖突有向圖。

例如，圖6（a）中表示了4條規(guī)則A、B、C、D之間的重疊關系。于是，圖中表示了(A,B)、(A,D)、(C,D)、(B,C)4個沖突規(guī)則對。

假如，4對沖突的覆蓋關系分別為A→B、B→C、C→D、A→D，那么可以得到一個有向圖，如圖6（b）所示。然而，注意到當4對沖突的覆蓋關系分別為A→B、B→C、C→D、D→A時，得到有向圖如圖6（c）所示。圖中由于存在有向環(huán)，無法確定重疊區(qū)域的覆蓋優(yōu)先級，從而這種情況無法進行一次性沖突消解，只能手動選擇一對沖突消解，打破環(huán)路之后才能繼續(xù)進行。

對于沖突的有向無環(huán)圖，可根據(jù)其拓撲排序來確定規(guī)則的覆蓋優(yōu)先級，環(huán)路檢測可以在拓撲排序過程中進行。需要說明的是，有些結點之間并不存在直接或間接有向路徑連接，對于這樣的結點，拓撲順序的先后對于沖突消解的結果沒有任何影響，原因如下：

Fig.6 Representation of conflicting directed graphs圖6 沖突的有向圖表示

（1）若兩個結點代表規(guī)則的Effect相同，那么兩者重疊部分無論哪條規(guī)則優(yōu)先級更高，Effect都是一樣的；

（2）若兩個結點代表規(guī)則的Effect不同，那么兩條規(guī)則必然不存在重疊區(qū)域，否則兩條規(guī)則之間存在沖突，兩個結點之間將有一條直接的有向邊決定其拓撲順序。

在實際情況中，沖突對應的DAG可能存在若干個互相不連通的弱聯(lián)通子圖，這些子圖分別代表了各自獨立的沖突規(guī)則序列，可以將這些獨立的弱聯(lián)通子圖分離出來各自獨立消解。而DAG弱聯(lián)通分量的檢測可以在沖突檢測累積沖突對的過程中完成。

4.3 屬性軸劃分

在4.1節(jié)中，根據(jù)規(guī)則在各個坐標軸上投影的重疊對坐標軸進行了劃分。例如，對于4.1節(jié)中的例子，x軸被劃分出如圖7所示的片段。

Fig.7 xattribute axis division圖7 x屬性軸劃分

在第3章沖突檢測中，把對屬性的各種條件歸納成了3種集合：屬性值區(qū)間、單值集合和正則集。對于單值集合可以看作上下界相等的屬性值區(qū)間，而對于有限的正則集，可以用多個單值集合的并集來枚舉表示，可以把屬性值區(qū)間、單值集合、有限正則集統(tǒng)稱為可劃分的集合；而無限正則集稱為不可劃分的集合，因為如果對其劃分將產(chǎn)生無限多個片段。對于沖突消解中的一個屬性，如果所有規(guī)則在該屬性上的條件對應的集合都是可劃分的，則該屬性即為可劃分的，否則該屬性不可劃分。

對于可劃分的屬性，每個片段都可以用起始位置和終止位置來表示，而起始點和終止點除了要記錄具體的值，還要記錄是開區(qū)間還是閉區(qū)間。注意到當所有片段在坐標軸上有序排列之后，每個片段的結束位置與下一個片段的起始位置是成對出現(xiàn)的，它們位于坐標軸上同一點，如果某片段起始是閉區(qū)間，則其上一個片段的終止是開區(qū)間，反之亦然。因此，確定了所有片段的起始點和開閉狀態(tài)后，所有的片段也就確定了。例如圖7中，x軸的起始點列表為(2,close)、(3,close)、(4,open)、(5,open)、(6,open)、(7,open)，其中close表示閉區(qū)間，open表示開區(qū)間。確定的片段分別為(-∞,2)、[2,3)、[3,4]、(4,5]、(5,6]、(6,7)、[7,+∞)。

對屬性軸劃分的過程就是對所有起始點排序，每兩個相鄰起始點之間自然就形成了一個小段。起始點比較的規(guī)則如下：首先比較兩個點值的大小，若不相等則返回比較結果；若相等則作為閉區(qū)間的起始點小于作為開區(qū)間的起始點。單個屬性的屬性軸劃分算法見算法3。

算法3屬性軸劃分算法

輸入：MapruleList，規(guī)則ID→Range(startPoint,endPoint)的映射。

輸出：Map>splits，起始點→規(guī)則集合的映射,記錄每個起始點對應區(qū)間的規(guī)則集合；Listpoints，起始點的升序排列列表。

//獲得所有起始點

對于不可劃分的屬性，即條件中含有無限正則集的屬性，無法用上述方法進行劃分，本文的做法是并不顯式地對該屬性進行劃分，只是在后面建立空間區(qū)域選擇樹時才局部進行劃分，在4.4節(jié)中進行描述。

4.4 建立空間區(qū)域選擇樹消解沖突

對屬性軸進行分段之后，根據(jù)規(guī)則優(yōu)先級由高到低的順序，對每條規(guī)則建立空間區(qū)域選擇樹。其目的是選擇出每條規(guī)則在空間中決定的區(qū)域，即該規(guī)則覆蓋的區(qū)域中，其優(yōu)先級最高的部分。對于優(yōu)先級最高的規(guī)則，其內容將會被完全保留，不需要對其構建空間區(qū)域選擇樹。

空間區(qū)域選擇樹是一個N+1層的有序樹，根結點表示進行選擇的規(guī)則R，樹的每一層表示在一個屬性上進行的一次選擇，每一個非根結點表示R在該層對應屬性上投影的一個分段，每一條從根結點到非根結點的路徑代表了在各個屬性軸上選擇屬性對應條件的過程，也是逐步細化空間區(qū)域的過程。當每一個屬性上都選擇了一個條件之后，該路徑即確定了一個規(guī)則R覆蓋的子區(qū)域，只需要判斷R是否是該區(qū)域中優(yōu)先級最高的規(guī)則即可。為此，每一個非根結點中還記錄一個高優(yōu)先級規(guī)則集合字段，該字段表示選擇到該結點時對應的空間區(qū)域中，比R優(yōu)先級更高的規(guī)則集合，若該字段為空集(?)，則該區(qū)域由規(guī)則R決定。

4.1節(jié)描述的例子中，假設規(guī)則優(yōu)先級由高到低為A→B→C→D，以x、y、z的順序依次選擇屬性條件，規(guī)則C的空間區(qū)域選擇樹構造過程如圖8（a）所示，圖中加粗的路徑即確定了兩個由規(guī)則C決定的區(qū)域。由空間區(qū)域選擇樹的構建過程可知，決定一條路徑是否被選中的因素是葉子結點的高優(yōu)先級規(guī)則集合字段，因此對于每一層中該字段相同的兄弟結點可以合并成一個結點，上面的空間區(qū)域選擇樹經(jīng)合并之后的選擇樹如圖8（b）所示。另外，當一個非葉結點的高優(yōu)先級規(guī)則集為空集時，其子孫結點該字段也必然為空，因此從該節(jié)點往下直到葉子，每個結點都只有一個孩子結點，每個結點的分段字段即為規(guī)則R在對應屬性上的條件。

Fig.8 Spatial area selection tree圖8 空間區(qū)域選擇樹

重復上面的過程，對每一條規(guī)則進行空間區(qū)域選擇樹的構造，即可選出所有消解之后的規(guī)則。注意，若某一條規(guī)則構造選擇樹之后，沒有一條路徑可以被選中，這表示該規(guī)則覆蓋到的所有區(qū)域都被優(yōu)先級更高的規(guī)則覆蓋了，當構造優(yōu)先級更低的規(guī)則的選擇樹時，可以在規(guī)則集合字段中忽略該條規(guī)則。

4.3節(jié)提到了條件中含有無限正則集的屬性不顯式的劃分。假設存在這樣的屬性w，需要構造規(guī)則R的選擇樹，優(yōu)先級比R高的規(guī)則集合為{P1,P2,…}，則對屬性軸w中R投影的部分R_w做局部劃分，劃分方法如下：

（1）將R_w劃分成R_w∩P1_w和R_w-P1_w得到兩個集合，注意當交集結果為空集時，差集等于R_w，無需計算，下面每一步都同樣。

（2）對步驟（1）中得到的兩個集合與P2_w分別取交集和差集，得到最多4個集合。

（3）對每一個Pi做同樣的劃分，最后最多會得到2(n-1)個集合。當然這是最壞的情況，實際情況中會得到很多空集。

上述劃分中得到的每一個集合都作為屬性w這一層的一個結點，并且不用進行結點的合并。為了避免每次構造分類樹時重復計算，可以把這些交集與差集緩存起來，其中交集的緩存在沖突檢測時即可建立。

由空間區(qū)域選擇樹的構造方法上看，當屬性數(shù)目更多，沖突涉及的規(guī)則更多時，屬性選擇的順序對選擇樹的結點數(shù)會有一定影響。對于一個特定的規(guī)則R，屬性選擇的順序最好綜合考慮以下兩個原則：（1）屬性軸片段數(shù)少的屬性優(yōu)先；（2）R在屬性軸的每個片段中，重疊規(guī)則數(shù)目較少者優(yōu)先。為了簡便起見，并沒有為每條規(guī)則制定特定的屬性選擇順序，而是根據(jù)屬性軸劃分情況，對每個屬性軸計算權重，制定全局的屬性選擇順序。對于一個屬性x，Xi為x的一個片段，Ri為片段Xi中投影規(guī)則的數(shù)目，屬性x的權重計算方式如下：

而對于不可劃分的屬性，權重為無窮大。權重的計算可以在屬性軸劃分的同時完成。根據(jù)權重由低到高的順序選擇屬性。規(guī)則R的空間區(qū)域選擇樹構建算法見算法4。

算法4空間區(qū)域選擇樹構建算法

輸入：AttrList，按權重升序排列的屬性列表；RuleId，要構造的規(guī)則R的Id；PrevRuleSet，比規(guī)則R優(yōu)先級高的規(guī)則ID集合。

5 模擬實驗及性能分析

為了測試本文提出的策略沖突檢測與消解算法的正確性、完備性以及算法性能等，本文根據(jù)XACML規(guī)范定義策略庫作為數(shù)據(jù)集，利用Java語言實現(xiàn)了算法，在AMD A6-3420M四核處理器，內存DDR3 4 GB 1 333 MHz，運行Windows 7系統(tǒng)的PC機上進行實驗。實驗模擬了大規(guī)模策略集合沖突和冗余檢測以及沖突消解的過程，并對實驗結果進行了正確性分析和算法性能分析。

5.1 模擬實驗

為了檢驗算法的正確性與完備性，本文模擬了一個對遠程文件系統(tǒng)進行訪問控制的安全策略集，將文件的操作權限設置為read、write、execute共3種。假定用IP地址來標識訪問文件系統(tǒng)的用戶，用一個整數(shù)類型的屬性privilege來衡量用戶的權限（0～4），值越大表示權限越高。所有的訪問控制策略以XACML標準描述，訪問控制策略全集Q如表2所示，規(guī)則合并算法采用允許優(yōu)先（permit-overrides）。

Table 2 Full set of access control strategies表2 訪問控制策略全集

表2中的規(guī)則r2表示允許IP地址符合192.168.*.*且權限privilege不小于2的用戶讀取文件file1；規(guī)則r7中的“?”表示對集合取反；而r8表示拒絕任何權限和IP的用戶執(zhí)行文件file1，all-user和all-privilege在XACML策略文件中分別表現(xiàn)為對應的Subject中沒有IP地址和權限屬性的限制，即沒有對應該屬性的標簽。

（1）沖突檢測

在沖突檢測實驗中，檢測結果如下：

① 沖突規(guī)則 7 對：(r1,r2)，(r1,r9)，(r1,r11)，(r10,r2)，(r10,r9)，(r10,r11)，(r5,r8)。

② 冗余規(guī)則4對：(r2,r11)，(r9,r11)，(r4,r3)，(r7,r6)（后面為冗余規(guī)則）。

檢測時間為876 ms。

（2）冗余處理和沖突消解預處理

首先，對沖突檢測結果進行冗余處理，刪除冗余規(guī)則r3、r6、r11，還要刪除r11對應的沖突規(guī)則對。

然后，在剩余沖突規(guī)則對中找出那些Target交集類型存在包含或相等關系的沖突對，刪除存在直接覆蓋關系的沖突規(guī)則。在實驗中，Target存在包含關系的沖突對有(r10,r9)和(r5,r8)。實驗中規(guī)則合并算法采用允許優(yōu)先，因此沖突對中優(yōu)先保留的規(guī)則分別為r10和r8。對于沖突對(r10,r9)，盡管r10的Target被完全包含在r9中，但在消解時優(yōu)先保留r10的內容，因此其不能被直接刪除，沖突消解時需要將r9中與r10重疊的部分去除。而對于沖突規(guī)則對(r5,r8)，完全被覆蓋，并且其也不是優(yōu)先保留的規(guī)則，因此可以被直接刪除。

這樣經(jīng)過冗余處理和沖突消解預處理之后，剩余的4個沖突規(guī)則對為(r1,r2)，(r1,r9)，(r10,r9)，(r10,r2)。

（3）沖突消解

剩余的4對沖突中涉及4條規(guī)則，根據(jù)規(guī)則合并算法生成沖突的DAG，通過拓撲排序確定規(guī)則的優(yōu)先級。上述沖突的DAG如圖9所示。規(guī)則的優(yōu)先級順序從高到低依次為r1、r10、r2、r9。

確定規(guī)則優(yōu)先級后，按照規(guī)則優(yōu)先級從高到低的順序依次構建空間區(qū)域選擇樹，構建時間如表3所示?？梢钥闯?，規(guī)則優(yōu)先級越低，構造空間區(qū)域選擇樹的時間越長，這是由于規(guī)則優(yōu)先級越低，在構建選擇樹的時候要考慮的高優(yōu)先級規(guī)則越多，選擇樹的結點數(shù)也隨之增長。而對于優(yōu)先級最高的規(guī)則r1，保留原有規(guī)則即可，不需要構建選擇樹。

Fig.9 Conflicting DAG圖9 沖突有向無環(huán)圖

Table 3 Build-time of space area selection tree表3 空間區(qū)域選擇樹構建時間

注意到，在模擬實驗的例子中，選擇了IP地址和權限兩個主體屬性，其中IP地址使用了正則式，對應的正則集可以視為無限正則集，該屬性是不可劃分的。而對于權限屬性采用整數(shù)類型表示，是可劃分的屬性。而資源屬性（文件名），操作屬性都是字符串枚舉類型，同樣是可以劃分的。這些可劃分屬性的屬性軸劃分在構建空間區(qū)域選擇樹之前預先進行，而IP地址的劃分在空間區(qū)域選擇樹構建過程中動態(tài)劃分。

經(jīng)過沖突消解之后，優(yōu)先級最高的規(guī)則直接保留，剩余3條規(guī)則被消解。其中r10去除了與r1重疊的部分；r2去除與r1和r10相沖突的部分生成兩條規(guī)則，分別用r2_1和r2_2表示；r9去除相沖突的部分之后被r2完全覆蓋，消解之后沒有產(chǎn)生任何規(guī)則。最終得到的規(guī)則如表4所示。包括冗余處理和沖突消解預處理在內，沖突消解總共花費的時間為626 ms。

5.2 沖突檢測算法性能評估

Table 4 Conflict resolution results表4 沖突消解結果

實驗1沖突檢測性能與規(guī)則數(shù)目之間的關系。

沖突檢測的性能與規(guī)則索引中規(guī)則的密集程度，即索引中每個索引項對應的規(guī)則數(shù)密切相關，為了更好地檢驗規(guī)則數(shù)目以及規(guī)則索引密集程度對沖突檢測性能的影響，預先控制了每個索引項對應的規(guī)則數(shù)目C，在不同的密集程度下對不同規(guī)則數(shù)目檢驗沖突檢測算法的性能，這樣實際的規(guī)則總數(shù)R相當于索引項數(shù)目E與C值的乘積。圖10展示了C值分別為10、20、30時，索引項E從10增加到50的沖突檢測時間。

圖10中在固定每個索引項對應規(guī)則數(shù)目的條件下，沖突檢測時間隨索引項數(shù)目（或規(guī)則數(shù)）線性增長是可以預見的。雖然兩條規(guī)則之間的沖突檢測與規(guī)則的具體結構以及涉及屬性的數(shù)目相關，但在一個索引項中進行沖突檢測時，大體上時間與索引項中包含規(guī)則數(shù)正相關，而固定C值之后，該時間幾乎為定值，檢測時間自然隨索引項數(shù)目線性增長。

Fig.10 Experiment 1 of conflict detection performance圖10 沖突檢測性能實驗1

實驗2沖突檢測性能與規(guī)則在索引中密集程度的關系。

固定規(guī)則的數(shù)目R，改變密集程度C值，檢驗沖突檢測算法的性能。圖11展示了R分別取600、1 200和1 800時，C由10增長到60，沖突檢測時間與沖突規(guī)則對數(shù)目的變化趨勢圖。圖11（b）中沖突規(guī)則對數(shù)目統(tǒng)計的是每一次檢測到的沖突規(guī)則對與冗余規(guī)則對數(shù)目總和。很明顯可以看出，沖突檢測時間和沖突規(guī)則對數(shù)目在一定的規(guī)則總數(shù)下隨規(guī)則在索引中的密集程度線性增長。

5.3 沖突消解算法性能評估

在5.2節(jié)沖突檢測實驗2的基礎上，對檢測到的沖突進行消解，并檢驗了沖突規(guī)則對數(shù)目與沖突消解時間之間的關系，如圖12所示。從圖12（a）可以看出，從整體上看，沖突消解時間隨沖突規(guī)則對數(shù)目的增長呈線性增長的趨勢，然而從局部上看，沖突消解時間與沖突規(guī)則對數(shù)目的關系則不甚明顯。經(jīng)過分析，認為規(guī)則沖突的密集程度對沖突消解時間會有比較大的影響，對于相同數(shù)目的沖突規(guī)則對，若涉及到的規(guī)則數(shù)不同，沖突消解的時間會有差別。一方面，涉及規(guī)則數(shù)越多，需要構造的空間選擇樹越多；另一方面，涉及的規(guī)則數(shù)越多，每個屬性軸的分片數(shù)量越多，構造的空間選擇樹的結構就越復雜。

為了驗證這一想法，用沖突數(shù)與規(guī)則數(shù)的比值λ衡量沖突的密集程度。在每一組規(guī)則數(shù)R相同的實驗中，統(tǒng)計了λ與沖突消解時間的關系，如圖12（b）所示。很明顯，在一定的規(guī)則集規(guī)模下，沖突消解時間與沖突密集程度成正比關系。

Fig.11 Experiment 2 of conflict detection performance圖11 沖突檢測性能實驗2

6 結束語

本文對基于XACML規(guī)范的ABAC策略的沖突檢測與消解展開了深入研究，改進了傳統(tǒng)的策略沖突檢測算法，并提出了一種新的一次性消解沖突的算法。在模擬實驗環(huán)境中實現(xiàn)了該算法，并對算法的性能與影響算法性能的因素進行了實驗與分析。實驗結果表明，策略沖突檢測與沖突消解算法能有效地對策略沖突進行檢測和消解，并且在有大量沖突的數(shù)據(jù)集上，能達到比較好的性能。

Fig.12 Conflict resolution performance圖12 沖突消解性能

將XACML規(guī)范中的數(shù)據(jù)類型和函數(shù)類型統(tǒng)一成幾種簡單的形式，具有良好的擴展性，支持XACML中Target標簽的所有形式的沖突與冗余的檢測與消解。然而，目前算法并不支持XACML中Condition標簽的沖突檢測，這將是下一步主要的研究方向之一。另外，在算法的性能上，若能合理地利用緩存，并在沖突檢測與沖突消解之間建立方便的數(shù)據(jù)共享機制，算法的性能還有提高的空間。

[1]Li Xiaodong,Zhu Hao,Yang Weidong.XML keywords search based on secure access control[J].Journal of Frontiers of Computer Science and Technology,2010,4(1):73-81.

[2]Wang Xiaoming,Fu Hong,Zhang Lichen.Research process attribute-based access control[J].Chinese Journal of Electronics,2010,38(7):1660-1667.

[3]Lin Dan,Rao P,Bertino E,et al.EXAM:a comprehensive environment for the analysis of access control policies[J].International Journal of Information Security,2010,9(4):253-273.

[4]Lupu E C,Sloman M.Conflicts in policy-based distributed systems management[J].IEEE Transactions on Software Engineering,1999,25(6):852-869.

[5]Moffett J D,Sloman M S.Policy conflict analysis in distributed system management[J].Journal of Organizational Computing and Electronic Commerce,1994,4(1):1-22.

[6]McDaniel P,Prakash A.Methods and limitations of security policy reconciliation[J].ACM Transactions on Information and System Security,2006,9(3):259-291.

[7]WangYazhe,Feng Dengguo.Aconflict and redundancy analysis method for XACML rules[J].Chinese Journal of Computers,2009,32(3):516-530.

[8]Huang Feng,Huang Zhiqiu,Liu Linyuan.A DL-based method for access control policy conflict detecting[C]//Proceedings of the 1st Asia-Pacific Symposium on Internetware,Beijing,Oct 17-18,2009.New York:ACM,2009:16.

[9]Kolovski V,Hendler J,Parsia B.Formalizing XACML using defeasible description logics,TR-233-11[R].University of Maryland,2006.

[10]Xia Xiaofeng.A conflict detection approach for XACML policies on hierarchical resources[C]//Proceedings of the 2012 International Conference on Green Computing and Communications,Conference on Internet of Things,and Conference on Cyber,Physical and Social Computing,Besancon,Nov 20-23,2012.Washington:IEEE Computer Society,2012:755-760.

[11]Huonder F.Conflict detection and resolution of XACML policies[D].Rapperswil University of Applied Sciences Rapperswil,2010.

[12]Agrawal D,Giles J,Lee K W,et al.Policy ratification[C]//Proceedings of the 6th International Workshop on Policies for Distributed Systems and Networks,Stockholm,Jun 6-8,2005.Washington:IEEE Computer Society,2005:223-232.

[13]Liu Jiang,Zhang Hongqi,Dai Xiangdong,et al.A static ABAC policy conflict resolution algorithm[C]//Proceedings of the 4th International Conference on Multimedia Information Networking and Security,Nanjing,Nov 2-4,2012.Piscataway:IEEE,2012:83-86.

[14]Wang Yongliang,Chen Xingyuan,Wu Bei,et al.Security policy conflict detection and resolution based on multidimensional integer space[J].Computer Engineering,2009,35(4):134-136.

[15]Calero J M A,Pérez J M M,BernabéJ B,et al.Detection of semantic conflict in ontology and rule-based information systems[J].Data&Knowledge Engineering,2010,69(11):1117-1137.

[16]Campbell G A.Ontologies for resolution policy definition and policy conflict detection,CSM-1722007[R].Stirling:University of Stirling,2007.

[17]Li Ruixuan,Lu Jianfeng,Li Tianyi,et al.An approach for resolving inconsistency conflicts in access control policies[J].Chinese Journal of Computers,2013,36(6):1210-1223.

[18]Wang Juan,Wang Jiang,Jiao Hongyang,et al.A method of OpenFlow-based real-time conflict detection and resolution for SDN access control policies[J].Chinese Journal of Computers,2015,38(4):872-883.

附中文參考文獻:

[1]李曉東,朱皓,楊衛(wèi)東.安全訪問控制的XML關鍵字檢索[J].計算機科學與探索,2010,4(1):73-81.

[2]王小明,付紅,張立臣.基于屬性的訪問控制研究進展[J].電子學報,2010,38(7):1660-1667.

[7]王雅哲,馮登國.一種XACML規(guī)則沖突及冗余分析方法[J].計算機學報,2009,32(3):516-530.

[14]王永亮,陳性元,吳蓓,等.基于多維整數(shù)空間的安全策略沖突檢測與消解[J].計算機工程,2009,35(4):134-136.

[17]李瑞軒,魯劍鋒,李添翼,等.一種訪問控制策略非一致性沖突消解方法[J].計算機學報,2013,36(6):1210-1223.

[18]王鵑,王江,焦虹陽,等.一種基于OpenFlow的SDN訪問控制策略實時沖突檢測與解決方法[J].計算機學報,2015,38(4):872-883.