基于聚類和重排序的XACML策略評估優化方法

鄭 楷，田秀霞，盧官宇，張玉秀

(上海電力大學計算機科學與技術學院，上海 200090)

1 引言

訪問控制是目前安全服務中的重要機制。在眾多訪問控制模型中，基于屬性的訪問控制模型[1](ABAC)適用于開放式環境，對于訪問主客體統一使用屬性來描述，實現授權的細粒度化。策略決策點(PDP)是ABAC中的重要組件，負責對于訪問請求的評估。OASIS組織推出的可擴展的訪問控制標記語言(eXtensible Access Control Markup Language，XACML)適用于ABAC模型，使用XML的方式描述訪問請求、策略和響應。XACML標準[2]通過檢查用戶的訪問請求是否匹配策略，進而給出決策結果。

分布式資源共享、webservice等場景都需要制定大量XACML策略對資源進行細粒度化訪問控制，但是隨著訪問請求的增加和策略規則規模的擴大，策略評估性能成為影響授權系統性能的瓶頸。

SUN公司在OASIS組織指定XACML標準后，推出了策略訪問控制評估原型系統SUNXACML[3]。在PDP模塊，SUNPDP采用的暴力的方式在策略庫中檢索適用于訪問請求的規則。在策略規模較小的場景下，暴力逐條檢索的方式對于評估性能來說影響不是很大。然而當系統中策略規則達到成千上萬條的時候，評估時延、系統開銷不容忽視。目前關于提高PDP評估性能方面的工作主要圍繞優化大規模策略集[4]-[9]以及提出新的評估模型[10]-[16]展開。王雅哲等[4]利用狀態覆蓋思想分析造成規則冗余的原因，并給出了不同規則合并算法下的冗余判定定理。戚湧等人[5]結合規則壓縮消除規則間的冗余規則，并將文本屬性映射為數字屬性，使用HashMap存儲映射關系。S. Marouf等人[6]提出了一個基于自適應重排序和聚類的PDP框架，先對規則按主體屬性分類，進一步對于主體屬性使用K-means算法對規則進行聚類；并且根據評估歷史，基于規則的成功命中率對規則進行重排序。通過聚類可以減少訪問請求比較的規則個數，然而K-means算法需要提前指定簇的數量，而簇的數量事先并不知曉。Zhang等人[7]對于策略使用ACO算法進行分類，稱ACO的分類效果優于K-means。韓道軍等[8]提出基于屬性與或矩陣和類型分析的XACML策略查詢方法，計算出每個規則屬性的區分度，利用區分度和屬性與或矩陣篩選掉與當前訪問請求無關的規則。Deng等人[10]針對每個屬性建立了屬性位圖存儲含有該屬性的規則，通過對屬性位圖的邏輯與運算，確定適用于訪問請求的規則。Liu等人[11]提出的評估引擎XEngine將XACML策略的屬性數值化為數字連續區間，將嵌套遞歸的策略結構標準化為扁平結構。數字區間的匹配效率高于字符串匹配，然而屬性必須是連續區間，對于屬性是不連續區間的情況，方案沒有給出說明。Mourad等人[12]基于集合代數提出了新的XACML框架：SBA-XACML，該框架將XACML策略/請求轉化為SBA-XACML策略/請求，評估模塊對轉化后的請求進行評估，性能上優于XEngine。Deng等人[16]提出了一種類似于數組的數據結構規則字典，使用規則字典快速確定規則的索引；另外，使用bitmap存儲策略集中規則的effect，節約存儲空間。然而規則屬性值變更的話，需要更新規則字典的內容結構和文本結構。位圖存儲的只是規則的effect，然而規則還是存儲在類似于四維數組的規則字典里；規則多的情況下，內存開銷大。

以上提升PDP評估性能的方案存在一些局限性。通過解決策略間的沖突、檢測并減少策略間的冗余，從而優化大規模復雜策略集的方案不夠高效。另外，以上提出的新的評估模型并沒有結合優化大規模策略集，評估性能有待提升。本文在研究XACML策略優化方法的同時，也基于提出的兩種優化方法，設計了一個包含計算中心、規則匹配器的優化評估模型PDPCR(Policy Decision Point based on Clustering and Reordering)，達到減少匹配運算量、提高匹配速度的目的。

2 背景知識

XACML 3.0標準中規定了兩種模型：數據流模型和語言模型。

XACML數據流模型主要由策略執行點(Policy Enforcement Point，PEP)、策略決策點(PolicyDecisionPoint，PDP)、策略管理點(Policy Administration Point，PAP)、策略信息點(Policy Information Point，PIP)、上下文處理器(Context Handler)組成。

PAP負責為PDP提供策略/策略集。PIP負責收集主體屬性、資源屬性、環境屬性，提供給上下文處理器。PEP主要負責訪問請求的轉發、響應的接收。PDP主要負責對訪問請求的評估。上下文處理器主要是起到PEP和PDP之間、PDP和PIP之間的中間人作用。

數據流模型簡化執行過程如下：PEP接受來自訪問請求者的訪問請求，將其發送給上下文處理器；上下文處理器將訪問請求構建為XACML格式，并將其發送給PDP；PDP負責接收來自上下文處理器的訪問請求，結合策略/策略集對訪問請求進行評估，并將響應上下文返回給上下文處理器；上下文處理器將響應上下文轉化為PEP本地響應格式，并將其發送給PEP；PEP根據響應結果決定是否授予給對資源的訪問權限。

XACML語言模型主要由策略集(Policy Set)、策略(Policy)、規則(Rule)三部分組成，以一種樹狀結構嵌套定義訪問權限，如圖1所示。

定義1(策略集，PolicySet)：策略集是XACML策略文件的根元素，用四元組表示PS=(id，T，P，PC)。其中，id是策略集的編號；T是策略集的目標元素，規定了可以適用于該策略集的主體屬性、資源屬性、操作屬性；P是策略集中的所有策略的集合，P=(p1，p2，…，pn)；PC是策略合并算法，用來解決策略集中發生的策略沖突或缺失。

定義2(策略，Policy)：策略是策略集的子元素，用四元組表示P=(id，T，R，RC)。其中，id是策略的編號；T是策略的目標元素，規定了可以適用于該策略的主體屬性、資源屬性、操作屬性；R是策略中的所有規則的集合R=(r1，r2，…，rn)；RC是規則合并算法，用來解決策略中發生的規則沖突或缺失。

定義3(規則，Rule)：規則是策略的子元素，用四元組表示R=(id，T，e，c)。其中，id是規則的編號；T是規則的目標元素，規定了可以適用于該規則的主體屬性、資源屬性、操作屬性；e是規則的決策結果，e∈{Permit，Deny}；c是規則的condition元素，通常是一個布爾函數，進一步地限定訪問請求。

定義4(訪問請求，AccessRequest)：訪問請求用四元組表示為

Req=(subject，resource，action，environment)

其中，subject是主體屬性，resource是資源屬性，action是操作屬性，environment是環境屬性。

3 評估模型

本節詳細介紹PDPCR評估模型。先給出PDPCR模型的體系結構和功能部件組成；然后介紹PDPCR中使用的策略優化技術，即聚類和重排序。

3.1 評估模型框架

PDPCR評估模型框架由兩部分組成，策略預處理和策略評估，如圖2所示。策略預處理是將策略/策略集中的規則抽取出來，對于大規模的規則集合基于規則相似度進行聚類，基于規則優先度對簇內規則進行重排序。策略評估是指評估模型中的計算中心接收訪問請求，計算出該訪問請求最適用的規則簇；規則匹配器在小規模的指定規則簇中遵循“首次出現優先”的規則合并算法尋找該訪問請求適用的規則，對訪問請求進行評估，同時評估記錄會被寫入評估日志；最后評估模型給出評估響應。

圖2 PDPCR評估模型框架

3.2 規則聚類

從原始XACML策略中抽取出規則，先計算規則間的相似度；然后基于DBSCAN算法對規則集進行聚類，形成規則簇；最后計算規則簇的簇心。

3.2.1 計算相似度

規則的組成元素為：subject，resource，action，condition。計算規則間的相似度，實則計算規則對應屬性間的相似度[17]。

定義5(屬性相似度，Attribute Similarity)：在實際中，屬性類型主要分為三種：字符串類型、數值類型、數值區間類型。針對不同類型的屬性，采用不同的方法計算屬性相似度。

相同元素的屬性間的相似度表示為AS(attr1，attr2)。

1) 字符串類型。若2個字符串值相等，則這2個字符串屬性相似度為1，否則為0。

2) 數值類型。若2個數值相等，則這2個數值類型屬性相似度為1，否則為0。

3) 數值區間類型。設數值區間1為A，數值區間2為B，則

(1)

定義6(規則相似度，RuleSimilarity)：設有規則r1、r2，兩者相似度為

RS(r1，r2)=w1*AS(r1.subject，r2.subject)

+w2*AS(r1.resource，r2.resource)

+w3*AS(r1.action，r2.action)

+w4*AS(r1.condition，r2.condition)

(2)

這里w1，w2，w3，w4為不同元素間的相似度權重。在XACML中，訪問請求中的屬性是與規則中的subject、resource、action、condition元素順序進行匹配的，當有一個元素屬性不匹配時，則剩余的元素屬性不再進行比較。所以根據XACML中的規則元素匹配特性，設置w1，w2，w3，w4為遞減的。

3.2.2 基于DBSCAN的規則聚類算法

在評估訪問請求的過程中，為了避免全量遍歷策略庫，提出了一種基于DBSCAN[18]的規則聚類算法。DBSCAN(Density Based Spatial Clustering of Applications with Noise)算法是一種著名的基于密度的聚類算法，該算法可以找出樣本點的全部密集區域，并把這些密集區域當做聚類簇。DBSCAN算法可以發現任意形狀的聚類簇，無需提前設定聚類簇的數量，適合于對較低維度數據進行聚類。下面是規則聚類算法的一些定義。

定義7 (規則間距離，RuleDistance)：設r1、r2為2條規則，則兩者間的距離為：

RD(r1，r2)=1-RS(r1，r2)

(3)

其中RS(r1，r2)為規則r1和r2間的相似度。

定義8(規則r的Eps領域半徑，Eps-neighborhood)：指規則r的Eps領域半徑內的規則集合。符號表示為

NEps(r)={r′∈R|RS(r，r′)≤Eps}

(4)

其中R為所有規則的集合。

定義9(核心規則，CoreRule)：若規則r的鄰域半徑Eps內的規則個數大于等于鄰域密度閾值MinPts，即，NEps(r)≥MinPts時，規則r是核心規則。

定義10(邊界規則，BorderRule)：若規則r的鄰域半徑ε內的規則個數<鄰域密度閾值MinPts，但是r在其它核心規則的領域半徑內，那么規則r是邊界規則。

定義11(噪聲規則，NoiseRule)：既不是核心規則也不是邊界規則的規則。

定義12(直接密度可達，directly density-reachable)：若規則r是從規則r’直接密度可達的，則滿足以下兩個條件

1)r∈NEps(r′)

2) |NEps(r′)|≥MinPts

即滿足r’是核心規則并且r在r’的Eps領域半徑內。

定義13(密度可達，density-reachable)：對于規則r1，r2，…，rn，如果ri+1是從ri直接密度可達的，則稱rn從r1密度可達。

定義14(密度相連，density-connected)：存在規則r1，r2，r3，如果r1和r3都從r2密度可達，則稱r1和r3密度相連。

定義15(規則簇，Rule Cluster)：設R是所有規則的集合，一個規則簇C是R的一個非空子集滿足以下條件：

1)?r，r’：如果r∈C，r’從r密度可達，則r’∈C

2)?r，r’∈C：r和r’是密度連接的

根據以上定義，有如下定理。

定理1：設規則r為規則集合R中的一個核心規則，那么集合O={o|o∈Rando從r密度可達}是一個規則簇。

定理2：設R為規則簇，規則r為R中的任意一個核心規則，那么規則簇R可以表示為集合O={o|o從r密度可達}

規則聚類算法步驟如下：

1) 將所有規則標記為unvisited，標記所有規則的clusterId為0，計數器k初始化為1；

2) 隨機選擇一個未訪問的規則r，標記r為已訪問；如果不存在未訪問的規則，算法結束；

3) 如果r是核心規則，則將設置r的clusterId為k，將r的鄰域半徑內的規則放入集合N；

4) 對于N的每個規則rule，標記其為已訪問，并更新其clusterId為k；如果rule為核心規則，則將rule的鄰域半徑內的所有規則添加進N；重復執行步驟4)，直到N中的每個規則都已訪問；

5) 計數器k自增1，進入步驟2)。

上述過程的偽代碼描述如算法1所示。

規則聚類算法需要三個輸入參數：單值規則集合R、鄰域半徑∈、鄰域密度閾值MinPts。輸出是含有k+1個規則簇的集合C。算法首先是利用基于密度的思想將規則集合進行聚類，標記好每個規則的clusterId；然后基于clutserId進行規則分類，相同clusterId的規則歸為一類。噪聲規則的cluserId為0。聚類算法的時間復雜度是O(|R|*找出某規則鄰域半徑內的規則所需的時間)，其中找出某規則鄰域半徑內的規則采用的是遍歷比較的方式，所以聚類算法的時間復雜度是O(|R|2)。基于clutserId進行規則分組算法的時間復雜度是O(|R|)。所以算法1總的時間復雜度是O(|R|2)。

算法 1：規則聚類

輸入：R：單值規則集合；∈：鄰域半徑； MinPts：鄰域密度閾值

輸出：S：含有 k+1 個規則簇的集合 {C0，C1，C2，…，Ck}

function clusterRules(R，∈，MinPts)

標記所有規則的 clusterId 為 0；

標記所有規則為 unvisited；

while存在 unvisited 的規則

隨機選擇一個 unvisited 的規則 r；

標記 r 為 visited；

k=1；

if r 為核心規則then

r.clutserId=k；

令 N 為 r 的∈鄰域內的規則集合

for rule ∈N

if rule 是 unvisited then

標記 rule 為 visited；

endif

if rule 為核心規則then

for r’∈rule的∈鄰域半徑內的規則

N.append(r′)；

end for

end if

if rule.clutserId==0 then

rule.clutserId=k；

end if

end for

k++；

end if

end while

S=groupByClusterId(R)；

returnS

end function

3.2.3 計算簇心

簇心規則是能夠代表規則簇的規則。通過計算訪問請求與簇心的相似度，可以快速確定訪問請求最有可能適用的規則簇。簇心規則也是由subject屬性、resource屬性、action屬性、condition屬性組成。其中每個屬性是簇內所有規則中出現頻率最高的屬性。比如規則簇C1所有規則中subject屬性出現頻率最高的是學生，那么規則簇C1的簇心規則的subject屬性為學生。

3.3 簇內規則重排序

為了提高訪問請求與簇內規則的匹配速度，提出了基于規則優先度的簇內規則重排序優化技術。

定義16(規則優先度，RulePriority)規則r的優先度為

RP(r)=w1*f(r.action)+w2*f(r.resource)

(5)

其中，f(attribute)為系統中屬性的使用頻率，f(attribute)∈[0，1]。w1，w2分別為action屬性、resource屬性的權重，權重大小可以根據不同應用場景進行調整。因為訪問控制策略主要功能是對資源(resource)上的操作(action)進行規定與約束，所以規則優先度由資源屬性和操作屬性來衡量。屬性使用頻率表由系統管理員來維護，具體的屬性使用頻率可以由評估日志分析得出。簇內規則重排序算法如算法2所示。

通過計算簇內規則的優先度，將優先度大的規則置于規則簇前端，優先度小的規則置于規則簇后端。比如在訪問請求中含有大量查詢屬性的應用場景中，將含有查詢屬性的規則置于簇內前端。這樣當訪問請求在某規則簇中順序搜索適用的規則時，只需遍歷少量規則即可得到決策結果，提高了決策效率。

算法2：規則重排序

輸入：R：規則簇；f：屬性使用頻率表

輸出：R’：重排序后的規則簇

function reorderRules(R，f)

for r ∈R

r.RP=w1*f(r.action)+w2*f(r.resource)

p.insert(r) //p為優先隊列

endfor

returnp

end function

4 實驗與分析

本節實驗的目的是驗證本文提出的方法，并與SUNPDP、SBA-XACML比較評估性能，給出量化結果。實驗分為三部分進行，第一部分分析SUNXACML的評估時間，第二部分分析不同優化方法對評估時間的影響，第三部分分析不同優化方法下與訪問請求比較的平均規則個數。實驗環境為：Intel 2.60GHz 8核CPU，8G內存，Windows 10操作系統，JavaRuntime Environment 1.8.0。

實驗中的3個訪問控制策略集來自實際系統：VMS[19](Virtual Meeting System)策略集、LMS[20](Library Management System)策略集、ASMS[21](AuctionSale Management System)策略集。對三個策略集加以修改和擴展，擴展后分別含有3072、6160、9000條規則。

訪問請求的構造基于策略集規則中的屬性。解析策略集，得到subject屬性集合、resource屬性集合、action屬性集合、condition屬性集合。對這四個集合進行笛卡爾乘積，便可得到訪問請求。然而，為了模擬真實環境中的訪問請求的分布，基于評估日志中的屬性使用頻率，控制訪問請求中的屬性的滿足一定條件。比如LMS系統中，訪問請求action屬性中的借書和還書使用頻率比較高，那么在批量構造出的LMS訪問請求中，大部分訪問請求的action屬性是借書和還書。

首先測量SUNPDP在三個策略集下的評估時間，訪問請求數分別為2000、4000、6000、8000、10000。圖3實驗結果表明SUN PDP對于同一策略集，隨著訪問請求數的增加，評估時間相應增加；對于不同策略集，訪問請求數相同的情況下，含有規則數多的策略集評估時間更長。SUNPDP對于每個訪問請求，在含有數千條規則的策略庫中遍歷匹配規則，時延開銷大，到達了104ms的數量級。

圖3 SunPDP評估時間

接著分別對三個策略集使用規則聚類、規則聚類+重排序的優化方法，對比評估時間的差異。使用規則聚類優化技術后，VMS中3072條規則生成了12個規則簇，平均每個簇256條規則；LMS中6160條規則生成了28個規則簇，平均每個簇220條規則；ASMS中9000條規則生成了45個規則簇，平均每個規則簇200條規則。

為了盡量減小誤差，評估時間的測量進行3次，取平均值。在PDPCR評估模型中，策略預處理部分，即規則聚類和重排序的時間不包含在評估時間的測量中，評估時間包括計算中心中訪問請求尋找最適用的規則簇的時間以及規則匹配器中訪問請求尋找適用的規則的時間。對于SBA-XACML評估模型，評估時間的測量不包含將XACML策略/訪問請求轉化為SBA-XACML策略/訪問請求的時間，僅包含對SBA-XACML訪問請求評估的時間。VMS策略集、LMS策略集、ASMS策略集的實驗效果如圖4所示。實驗結果表明使用了規則聚類優化技術之后，訪問請求的評估時間明顯降低，相對于SUNPDP提升了2.5個數量級；同時使用規則聚類和重排序兩種優化技術后，訪問請求的評估時間進一步降低，相對于SUNPDP提升了3個數量級。

圖4 不同策略集評估時間對比

最后分析不同優化方法下訪問請求平均比較的規則個數。訪問規則聚類將原始規模較大的策略集分解為多個小規模的規則簇，目的在于減少訪問請求與規則的比較次數。圖5實驗結果表明，原始數千條規則的策略集，在規則聚類之后，訪問請求僅需與規則簇中的規則比較100多次，即可得到判決結果，相對于SUNPDP效率提升了約1倍。在簇內規則重排序之后，高優先級的規則置于簇前端，訪問請求的比較次數進一步減少。

圖5 規則比較次數對比

5 結束語

本文從XACML評估效率低下問題出發，從兩個方面對XACML策略進行了優化處理，并基于兩種優化方法設計了一個新的評估引擎。首先是運用規則聚類優化方法，將大規模的策略集分解聚類為多個規模較小的規則簇，縮減了策略規模，減少了匹配運算量，提升了匹配速度。通過使用規則聚類優化技術，相對于SUN PDP，平均規則比較次數減少了60%，訪問請求評估時間減少了約2.5個數量級。同時，為了進一步提高簇內規則的匹配速度，提出了簇內規則重排序的優化方法，基于規則優先度調整簇內規則的順序。通過使用規則重排序優化技術，訪問請求評估時間能在規則聚類優化技術的基礎上繼續減少約0.4個數量級。實驗結果表明，基于兩種優化方法的評估引擎PDPCR的評估性能明顯高于其它同類系統。

未來的工作中，進一步研究含有多值屬性的規則間的相似度計算方法以及精化策略集，減少策略的冗余規則，優化PDP評估性能。