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

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

1 引言

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

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

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

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

2 背景知識

XACML 3.0標準中規(guī)定了兩種模型：數(shù)據(jù)流模型和語言模型。

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

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

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

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

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

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

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

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

Req=(subject，resource，action，environment)

其中，subject是主體屬性，resource是資源屬性，action是操作屬性，environment是環(huán)境屬性。

3 評估模型

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

3.1 評估模型框架

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

圖2 PDPCR評估模型框架

3.2 規(guī)則聚類

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

3.2.1 計算相似度

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

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

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

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

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

3) 數(shù)值區(qū)間類型。設數(shù)值區(qū)間1為A，數(shù)值區(qū)間2為B，則

(1)

定義6(規(guī)則相似度，RuleSimilarity)：設有規(guī)則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中，訪問請求中的屬性是與規(guī)則中的subject、resource、action、condition元素順序進行匹配的，當有一個元素屬性不匹配時，則剩余的元素屬性不再進行比較。所以根據(jù)XACML中的規(guī)則元素匹配特性，設置w1，w2，w3，w4為遞減的。

3.2.2 基于DBSCAN的規(guī)則聚類算法

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

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

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

(3)

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

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

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

(4)

其中R為所有規(guī)則的集合。

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

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

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

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

1)r∈NEps(r′)

2) |NEps(r′)|≥MinPts

即滿足r’是核心規(guī)則并且r在r’的Eps領域半徑內(nèi)。

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

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

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

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

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

根據(jù)以上定義，有如下定理。

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

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

規(guī)則聚類算法步驟如下：

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

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

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

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

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

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

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

算法 1：規(guī)則聚類

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

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

function clusterRules(R，∈，MinPts)

標記所有規(guī)則的 clusterId 為 0；

標記所有規(guī)則為 unvisited；

while存在 unvisited 的規(guī)則

隨機選擇一個 unvisited 的規(guī)則 r；

標記 r 為 visited；

k=1；

if r 為核心規(guī)則then

r.clutserId=k；

令 N 為 r 的∈鄰域內(nèi)的規(guī)則集合

for rule ∈N

if rule 是 unvisited then

標記 rule 為 visited；

endif

if rule 為核心規(guī)則then

for r’∈rule的∈鄰域半徑內(nèi)的規(guī)則

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 計算簇心

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

3.3 簇內(nèi)規(guī)則重排序

為了提高訪問請求與簇內(nèi)規(guī)則的匹配速度，提出了基于規(guī)則優(yōu)先度的簇內(nèi)規(guī)則重排序優(yōu)化技術。

定義16(規(guī)則優(yōu)先度，RulePriority)規(guī)則r的優(yōu)先度為

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

(5)

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

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

算法2：規(guī)則重排序

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

輸出：R’：重排序后的規(guī)則簇

function reorderRules(R，f)

for r ∈R

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

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

endfor

returnp

end function

4 實驗與分析

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

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

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

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

圖3 SunPDP評估時間

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

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

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

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

圖5 規(guī)則比較次數(shù)對比

5 結束語

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

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