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

華中科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430074

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

文獻(xiàn)[15]提出的基于對(duì)立屬性推理和文獻(xiàn)[16]提出的基于分離類推理的安全策略沖突檢測(cè)方法都屬于基于本體推理的沖突檢測(cè)方法，構(gòu)建領(lǐng)域本體是應(yīng)用該類方法的前提，而本體構(gòu)建是一個(gè)難點(diǎn)。

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

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

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

3 沖突與冗余檢測(cè)

3.1 沖突檢測(cè)問題描述及算法思路

3.1.1 沖突與冗余定義

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

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

例如，對(duì)于下列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

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

對(duì)于規(guī)則R5，其適用的所有請(qǐng)求都適用于規(guī)則R1，并且規(guī)則R1與之做出的評(píng)估結(jié)果都相同(Permit)，故規(guī)則R5為冗余規(guī)則，稱規(guī)則R1為冗余規(guī)則R5的覆蓋規(guī)則。上述覆蓋規(guī)則R1和冗余規(guī)則R5構(gòu)成一個(gè)冗余規(guī)則對(duì)(R1,R5)。

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

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

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

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

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

3.1.2 算法的目標(biāo)與基本思想

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

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

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

算法1沖突檢測(cè)算法

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

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

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

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

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

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

Fig.2 Two-level index structure of R-Arule圖2 R-A規(guī)則二級(jí)索引結(jié)構(gòu)

3.3 基于屬性值集合的沖突檢測(cè)算法

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

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

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

Fig.3 Simplified representation of finite automata圖3 有限自動(dòng)機(jī)簡(jiǎn)化表示

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

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

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

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

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

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

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

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

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

對(duì)屬性值集合求交集運(yùn)算并得出相交類型之后，得出計(jì)算兩個(gè)Target交集的算法，見算法2。

算法2Target交集算法

輸入：Targett1,t2，要計(jì)算交集的兩個(gè)Target。

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

//建立兩個(gè)Target的屬性集合映射

4 沖突消解

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

由第3章的沖突檢測(cè)算法可得到一系列的沖突規(guī)則對(duì)，每個(gè)沖突規(guī)則對(duì)的兩條規(guī)則Target之間存在一定的重疊，沖突消解的任務(wù)就是根據(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 沖突消解

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

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

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

每塊區(qū)域具有決定權(quán)規(guī)則的選擇依據(jù)為事先設(shè)定好的規(guī)則合并算法，規(guī)則合并算法描述的是當(dāng)兩條規(guī)則同時(shí)適用于一個(gè)請(qǐng)求時(shí)，如何合并兩條規(guī)則各自的評(píng)估結(jié)果，算法主要有允許優(yōu)先、拒絕優(yōu)先等。根據(jù)每一對(duì)沖突的規(guī)則合并算法，所有沖突規(guī)則對(duì)可以產(chǎn)生一個(gè)有向圖，根據(jù)有向圖的拓?fù)渑判驔Q定的規(guī)則優(yōu)先級(jí)來選擇。

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

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

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

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

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

4.2節(jié)詳細(xì)介紹沖突的有向圖表示以及拓?fù)渑判驔Q定規(guī)則優(yōu)先級(jí)，4.3節(jié)詳細(xì)介紹屬性軸劃分的算法，4.4節(jié)詳細(xì)介紹構(gòu)建空間區(qū)域選擇樹的算法以及優(yōu)化。

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

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

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

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

對(duì)于沖突的有向無環(huán)圖，可根據(jù)其拓?fù)渑判騺泶_定規(guī)則的覆蓋優(yōu)先級(jí)，環(huán)路檢測(cè)可以在拓?fù)渑判蜻^程中進(jìn)行。需要說明的是，有些結(jié)點(diǎn)之間并不存在直接或間接有向路徑連接，對(duì)于這樣的結(jié)點(diǎn)，拓?fù)漤樞虻南群髮?duì)于沖突消解的結(jié)果沒有任何影響，原因如下：

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

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

（2）若兩個(gè)結(jié)點(diǎn)代表規(guī)則的Effect不同，那么兩條規(guī)則必然不存在重疊區(qū)域，否則兩條規(guī)則之間存在沖突，兩個(gè)結(jié)點(diǎn)之間將有一條直接的有向邊決定其拓?fù)漤樞颉?/p>

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

4.3 屬性軸劃分

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

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

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

對(duì)于可劃分的屬性，每個(gè)片段都可以用起始位置和終止位置來表示，而起始點(diǎn)和終止點(diǎn)除了要記錄具體的值，還要記錄是開區(qū)間還是閉區(qū)間。注意到當(dāng)所有片段在坐標(biāo)軸上有序排列之后，每個(gè)片段的結(jié)束位置與下一個(gè)片段的起始位置是成對(duì)出現(xiàn)的，它們位于坐標(biāo)軸上同一點(diǎn)，如果某片段起始是閉區(qū)間，則其上一個(gè)片段的終止是開區(qū)間，反之亦然。因此，確定了所有片段的起始點(diǎn)和開閉狀態(tài)后，所有的片段也就確定了。例如圖7中，x軸的起始點(diǎn)列表為(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,+∞)。

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

算法3屬性軸劃分算法

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

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

//獲得所有起始點(diǎn)

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

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

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

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

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

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

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

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

（1）將R_w劃分成R_w∩P1_w和R_w-P1_w得到兩個(gè)集合，注意當(dāng)交集結(jié)果為空集時(shí)，差集等于R_w，無需計(jì)算，下面每一步都同樣。

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

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

上述劃分中得到的每一個(gè)集合都作為屬性w這一層的一個(gè)結(jié)點(diǎn)，并且不用進(jìn)行結(jié)點(diǎn)的合并。為了避免每次構(gòu)造分類樹時(shí)重復(fù)計(jì)算，可以把這些交集與差集緩存起來，其中交集的緩存在沖突檢測(cè)時(shí)即可建立。

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

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

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

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

5 模擬實(shí)驗(yàn)及性能分析

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

5.1 模擬實(shí)驗(yàn)

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

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

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

（1）沖突檢測(cè)

在沖突檢測(cè)實(shí)驗(yàn)中，檢測(cè)結(jié)果如下：

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

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

檢測(cè)時(shí)間為876 ms。

（2）冗余處理和沖突消解預(yù)處理

首先，對(duì)沖突檢測(cè)結(jié)果進(jìn)行冗余處理，刪除冗余規(guī)則r3、r6、r11，還要?jiǎng)h除r11對(duì)應(yīng)的沖突規(guī)則對(duì)。

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

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

（3）沖突消解

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

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

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

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

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

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

5.2 沖突檢測(cè)算法性能評(píng)估

Table 4 Conflict resolution results表4 沖突消解結(jié)果

實(shí)驗(yàn)1沖突檢測(cè)性能與規(guī)則數(shù)目之間的關(guān)系。

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

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

Fig.10 Experiment 1 of conflict detection performance圖10 沖突檢測(cè)性能實(shí)驗(yàn)1

實(shí)驗(yàn)2沖突檢測(cè)性能與規(guī)則在索引中密集程度的關(guān)系。

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

5.3 沖突消解算法性能評(píng)估

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

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

Fig.11 Experiment 2 of conflict detection performance圖11 沖突檢測(cè)性能實(shí)驗(yàn)2

6 結(jié)束語

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

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

將XACML規(guī)范中的數(shù)據(jù)類型和函數(shù)類型統(tǒng)一成幾種簡(jiǎn)單的形式，具有良好的擴(kuò)展性，支持XACML中Target標(biāo)簽的所有形式的沖突與冗余的檢測(cè)與消解。然而，目前算法并不支持XACML中Condition標(biāo)簽的沖突檢測(cè)，這將是下一步主要的研究方向之一。另外，在算法的性能上，若能合理地利用緩存，并在沖突檢測(cè)與沖突消解之間建立方便的數(shù)據(jù)共享機(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.

附中文參考文獻(xiàn):

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

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

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

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

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

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