基于雙重約束的角色挖掘算法

王靜宇，崔永嬌，譚躍生

(內蒙古科技大學 信息工程學院，內蒙古 包頭 014010)

0 引 言

近年來，基于角色的訪問控制(role-based access control，RBAC)憑借其自身優勢已迅速成為一種流行且有效的訪問控制方式。不同于傳統訪問控制用戶直接獲取權限的方式，在RBAC中用戶是通過角色來獲取權限。由于角色的數量遠小于權限的數量，因此RBAC系統的管理更加靈活有效。為了有效配置RBAC系統，需要從用戶權限關系中定義一組完全、正確、有效的角色。然后根據用戶需求通過組合多個權限分配角色集的過程稱為角色工程[1]。角色工程存在自上而下(top-down)和自下而上(bottom-up)兩種方法。自上而下是細分組織業務流程，根據用戶執行任務所需要的權限將它們劃分為適當角色；自下而上的方法又稱角色挖掘是根據已有的系統配置信息，即用戶-權限關系去定義角色。RBAC的一個重要特征就是能夠實施各種約束，這些約束有助于表達組織安全策略，實現所需的安全目標[2]。目前，關于角色的約束主要集中在最小特權、職責分離、先決條件和基數約束等方面。RBAC系統中存在4種基數約束：①角色-用戶基數約束，一個用戶中可以被指派的最大角色數。②用戶基數約束，一個角色可以被指派的最大用戶數。③權限基數約束，一個角色可以擁有的最大權限數。④角色-權限基數約束，一個權限可以被包含的最大用戶數。

本文以二分圖為基礎，結合圖優化方法，針對權限基數約束和用戶基數約束的角色挖掘，提出一種基于雙重約束的角色挖掘算法。

1 相關工作

當非RBAC系統遷移到RBAC時，首先要概述系統希望執行的各種約束。因此，為了滿足系統的約束，一系列基于約束的角色挖掘算法已經被提出。Sarana等[3]基于二分圖覆蓋的方法，尋找滿足職責分離約束的角色集。Mitra等[4]通過矩陣分解結合貪婪算法，在用戶-角色分配過程中加入時間約束。Blundo等[5]針對角色-用戶基數約束提出一種后處理方法，利用現有的角色挖掘算法得到無約束的角色集，對于不滿足約束的角色進行改進。Jafarian等[6]為優化角色挖掘方法，提出一種滿足約束的角色挖掘框架。到目前為止，提出的都是單一的約束，然而在實際的RBAC系統配置中不可能只存在一種約束，對此，Harika等[7]提出混合基數約束的啟發式解決方案，針對用戶中的角色數量和權限指派的角色數量這兩個方面進行約束。提出后處理框架和并發處理框架兩種不同的解決角色挖掘問題。但未考慮到最小特權原則，挖掘出的角色集也存在冗余。Blundo等[8]則是考慮角色挖掘中的權限基數約束和角色-用戶基數約束，提出預處理和過濾兩種挖掘算法。上述文獻主要是用戶聚類或權限分組的方法得到滿足約束的角色集，但并未考慮到角色間的繼承關系以及角色層次的構建，在實際的應用場景中不具有意義。

2 問題描述

本節主要介紹RBAC模型，二分圖以及基于約束角色挖挖掘的相關定義，另外對于角色挖掘結果的評價標準也做了相關說明。RBAC模型的基本概念：

USERS表示為用戶集合，數量為n；

PERMS表示為權限集合，數量為m；

ROLES表示為角色集合，數量為q；

UA?USERS×RLOES為用戶角色分配關系；

PA?ROLES×PERMS為權限角色分配關系；

UPA?USERS×PERMS為用戶權限分配關系；

RH?ROLES×ROLES為角色繼承關系；

定義1 (二分圖)若G=(V,E)是一個無向圖，G表示圖、V表示圖中的頂點集合、E表示圖中的邊。頂點集V被劃分成兩個不相交的頂點集(U，P)，邊(u,p)均滿足u∈U，p∈P，則稱圖G為一個二分圖。

定義2 (完全二分圖)在二分圖G=(V1,E,V2)中，若V1中的每個頂點都與V2中的每個頂點都有且僅有一條邊相連，則稱G為一個完全二分圖。

UPA轉化成二分圖表示，U表示用戶、P表示權限、(u,p)表示用戶-權限分配關系、一個完全二分圖表示為一個角色。圖1描述二分圖表示的UPA，圖2描述角色挖掘的結果，即用戶-角色和角色-權限分配關系，其中挖掘出來的角色集為{R1，R2}。

圖1 用戶權限關系(UPA)

圖2 角色挖掘的結果

本文定義用戶集U={u1,u2,u3,…,un}，權限集P={p1,p2,p3,…,pn}，角色集R={r1,r2,r3,…,rn}。角色中權限的數量表示為：PermsR(r)，角色中用戶的數量表示為RolesU(r)。

定義3 (DCRM)給定一個用戶權限關系UPA，以及兩個正整數約束值k1、k2。將UPA轉化成二分圖，找到滿足約束的最小完全二分圖覆蓋即滿足約束的角色集。約束條件為：PermsR(r)

定義4 加權結構復雜度(weighted structural complexity，WSC)給定一個四元組W=，表示權重，wr,wu,wp,wh∈Q+∪{∞}；給定一個RBAC系統狀態；系統的復雜度用wsc(γ,W)表示

wsc(γ,W)=wr×R+wu×UA+wp×
PA+wh×RH

根據系統的配置需求，為不同的關系設置不同的權重，以滿足系統的安全原則和組織策略更好的維護系統的安全。

3 基于基數約束的角色挖掘算法

3.1 基于雙重約束的角色挖掘算法(DCRM)

本文提出的算法(簡稱DCRM)將用戶權限關系UPA轉化為二分圖，挖掘滿足權限基數約束和用戶基數約束的最小完全二分圖集合得到初始角色集initRoles，然后調用圖優化算法，優化角色狀態、構建角色層次得到最終的角色集。降低系統的加權結構復雜度，提高管理效率。角色中權限的約束PermsR(r)約束值定義為k1、角色中用戶的約束RolesU(r)約束值定義為k2，其詳細描述如算法1所示：

算法1：基于雙重基數約束的角色挖掘算法(DCRM)

輸入： 用戶權限分配關系UPA、K1、K2

輸出：角色集R

BEGIN

(1) 調用初始角色生成算法生成初始角色集initRoles

(2) While there can be more merges do

(3) 調用角色層次構建算法，構建角色層次

END

3.2 初始角色生成算法

算法2描述了在角色挖掘中使用權限基數約束和用戶基數約束雙重約束生成初始角色。

本文中定義v[u]為頂點用戶u中的權限p,v[p]為頂點權限p中的用戶。UC[u]定義為用戶u中未被覆蓋邊的頂點p，UC[p]定義為權限未被覆蓋邊的用戶頂點u。UserPerms定義為用戶中權限的數量，角色中權限的數量定義為PermsRCount(r)，角色中用戶的數量定義為為RolesUCount(r)。U定義為完全二分圖中選擇的用戶、P定義為選擇的權限，UC[k1]定義為從用戶u中選擇的k1個權限。對于算法的詳細描述如下：

首先將用戶權限二元關系轉化為一個二分圖，在二分圖選擇一個具有最小數量未覆蓋邊的頂點。若選擇的頂點是用戶，則執行Phase1。找到這個用戶的所有未覆蓋的邊即這個用戶未覆蓋的權限UC[u]。如果用戶中未覆蓋權限的數量小于或等于給定的約束值k1,則將這些權限UC[u]加入到P中；如果權限的數量大于k1,則選擇前k1個權限加入到P中。根據選擇的權限P查找其它用戶中未覆蓋邊的頂點是否包含P，如果是則加入到U中，若用戶數量到達k2則停止查找。根據選擇的U和P構成一個滿足約束的完全二分圖。

若選擇的頂點是權限，則執行Phase2。查找包含權限的用戶，并且使得用戶數量不超過制定的約束k2，得到U。然后查找這些用戶共同擁有的未覆蓋的邊的頂點即權限，以及頂點p得到P。若用戶共同擁有的權限數量超過給定的約束k1，則選擇第一個k1個權限。直到二分圖中所有的邊都被覆蓋則停止查找。

算法2： 初始角色生成算法

輸入： 用戶集合U、權限集合P、 用戶權限分配關系UPA， 權限約束k1， 用戶約束k2

輸出： 用戶角色指派關系inintUA、 角色權限指派關系initPA以及初始角色集合initRoles

(1) 至少存在一個頂點存在未覆蓋的邊

(2) Set U=φ,P=φ

PermsRCount(r)=0,

RolesUCount(r)=0

{PHASE 1}

(3) if select vertice is user then //選擇的頂點是用戶

(4) RolesUCount(r)=RolesUCount(r)+1;

(5) if UserPerms[p]≤K1//用戶中的權限數滿足約束

(6) P=UC[u]

(7) else 從UC[u]中取前k1個權限 //用戶中的權限數違反約束

(8) P=UC[k1]

(9) end if

(10) for v≠u do //查找其它包含P權限的用戶

(11) if P ? UC[v] and RolesUCount(r)

//約束角色中用戶的數量

(12) RolesUCount(r)=RolesUCount(r)+1

(13) 將v加入到U

(14) end if

(15) end for

(16) U和P組成一個完全二分圖(biclique)

(17) end if

{PHASE 2}

(18) if select vertice is perm then //選擇的頂點是權限

(19) PermsRCount(r)=PermsRCount(r)+1

(20) for earch v contains p //查找包含指這個權限的所有用戶

(21) if rolesUCount(r)< k2//若角色中的用戶數滿足約束

(22) RolesUCount(r)=RolesUCount(r)+1

(23) 將v加入到U

(24) end if

(25) end for

(25) 查找用戶U共同擁有的未覆蓋邊的權限P

(26) if PermsRCount(r)≤K1//若角色中的權限數滿足約束

(27) P=UC[u]

(28) else 從UC[u]中取前k1個權限 //若角色中的權限數不滿足約束

(29) P=UC[k1]

(30) end if

(31) U和P組成一個完全二分圖(biclique)

(32)end if

3.3 角色層次構建算法

利用二分圖的方法得到的角色集是扁平化的結構未能構建角色層次，這就使得系統的復雜度高，管理花費大，在大型系統應用方面存在致命缺陷，沒有實際應用價值。因此針對上述問題，在初始角色集的基礎上利用圖優化策略，構建系統中的角色間的繼承關系以及角色層次，得到最終完整角色狀態。

本文是在zhang等提出的GO算法[9]的基礎上進行角色層次的構建。GO算法的主要思想：選擇兩個角色，根據角色的權限集之間的關系處理角色，可為分為以下4種情況：

(1)若兩個角色擁有相同的權限集。合并兩個角色，角色中權限集不變，用戶集求并。然后查看合并后的用戶數是是否違反給定的用戶基數約束，若是沒有則更新角色狀態即用戶角色關系，否則取消合并。

(2)若兩個角色的權限集之間存在交集，生成一個包含權限交集的新角色，刪除原角色中的公共權限，在原角色和新角色之間增加一條角色層次線，構建角色間的繼承關系。在本文中，由初始角色生成的新角色，僅包含權限并不包含用戶，因此不會違反用戶基數約束。

(3)若兩個角色中一個角色的權限集是另一個角色權限集的子集或超集。在子集和超集之間增加一條角色層次線。

(4)若兩個角色之間的權限集完全不同，則分別加入構建的角色層次中。

GO算法根據整個RBAC狀態判斷每兩個角色是否進行處理。但是并沒有說明如何選擇兩個角色，本文是根據角色中權限的數量進行降序排序，然后遍歷角色集，根據角色權限集之間的關系，處理角色間的繼承關系、構造角色層次。本文所選用的GO算法是根據角色中的權限數，對角色狀態進行更新，并不會使得分配給用戶的角色發生改變，因此最終的角色集不會違反系統中給定的約束。算法3描述了角色層次構造算法的實現過程。

算法3： 角色層次構建算法

輸入： initRoles

輸出： finallRoles

(1)對于initRoles中的角色按照角色中權限的數量排序orderRoles

(2)calculate optimisation metric = number of edges + number of roles

(3){merge roles until stable}

(4)for erach r ?orderRoles do

(5) Select two Roles

(6) 在不違反系統約束的前提下， 根據角色的權限集之間的關系處理角色 //若是角色合并后， 角色中的用戶數超出系統給定的約束， 則取消合并

(7)calculate new optimisation metric = number of edges + number of roles

(8) If new optimisation metric > optimisation metric then

(9) 取消處理

(10)else

(11) old optimisation metric = new optimisation metric

(12) end if

(13)end for

4 實驗評估

為了檢驗算法的性能與準確性，本文采用9個真實世界的數據集作為測試數據對算法進行實驗分析。這些數據集主要是用于分析各種啟發式角色挖掘算法的性能，在角色挖掘相關的文獻中得到了廣泛的應用。這些真實的數據集可以通過HP Labs在線獲得。真實數據集總結在表1中，U表示用戶數、P表示權限數、UPA表示用戶權限數、R表示無約束條件下生成的最佳角色數，以及分配給用戶的最大權限數max#P、分配給權限的用戶數max#U。

表1 實驗數據集

本文在所有的數據集上都做了實驗測試，實驗結果表明在DCRM算法下得到的角色集都能滿足權限基數約束和用戶基數約束的雙重基數約束。由于篇幅有限選取了Healthcares、Emea數據的實驗結果進行展示，其中分別展示了權限基數約束和挖掘出來的角色數量、加權結構復雜度，用戶基數約束和挖掘出來的角色數量、加權結構復雜度的變化關系。其中CRM算法是Kumar等[10]提出的基于權限基數約束的角色挖掘算法。圖3、圖4分別展示了隨著權限基數約束的變化和挖掘出來的角色數量、加權結構復雜度變化關系，為了更加準確比較算法的性能，在進行角色基數約束方面的比較過程中，不對用戶基數方面進行約束。

圖3 權限基數約束和角色數量

圖4 權限基數約束和加權結構復雜度WSC

圖3中顯示在Healthcare數據集上，DCRM和CRM算法在在權限基數約束方面挖掘出來的角色數上沒有很大差別。但是，從圖4中可以看出，本文所提出的DCRM算法和CRM算法相比是明顯降低了加權結構復雜度。

圖5、圖6則展示了在用戶基數約束方面和挖掘出來角色數量、WSC的變化關系。對于用戶基數約束的實驗本文中是對權限基數約束的值不做約束，DCRM和CRM比較的是用戶基數約束的值。從圖中可以看出本文提出的DCRM算法和Horned等[11]提出的基于用戶基數約束Algorithm1算法相比，有效降低了挖掘出的角色數量和加權結構復雜度。

圖5 用戶基數約束和角色數量

圖6 用戶基數約束和加權結構復雜度

圖7、圖8展示了在EMEA數據上，DCRM和CRM算法在權限基數約束下的變化關系，與Healthcare一樣，對于用戶基數不做約束。從圖中可以看出，本文提出的DCRM算法在角色數量方面不占優勢，但是能夠有效降低加權結構復雜度。

圖7 權限基數約束和角色數

圖8 權限基數約束和加權結構復雜度

圖9、圖10展示了在EMEA數據上，DCRM和Algorithm1算法在用戶基數約束下的變化關系，從圖中可以看出其結果與Healthcare類似，DCRM算法明顯降低了角色數量和加權結構復雜度。

圖9 用戶基數約束和角色數量

圖10 用戶基數約束和加權結構復雜度

通過上述實驗結果可以看出本文提DCRM算法是真實有效的，挖掘出來的角色都能夠滿足權限基數約束和用戶基數約束雙重基數約束，并且能夠有效降低角色數量和加權結構復雜度。

5 結束語

本文提出的權限基數約束和用戶基數約束雙重基數約束角色挖掘算法。首先提出明確的問題定義以及本文中需要用的問題定義，之后詳細描述算法，最后通過實驗驗證算法的真實和有效性。實驗結果表明,本文所提出的算法在滿足雙重基數約束的條件下能夠有效降低角色數和系統管理復雜度，同時有效保證RBAC系統的安全性。在未來的研究工作中，計劃在本文提出的算法中考慮RBAC系統中的其它約束，如最小特權，職責分離等進一步提高系統安全。