王靜宇，崔永嬌，譚躍生

(內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010)

0 引 言

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

本文以二分圖為基礎(chǔ)，結(jié)合圖優(yōu)化方法，針對(duì)權(quán)限基數(shù)約束和用戶基數(shù)約束的角色挖掘，提出一種基于雙重約束的角色挖掘算法。

1 相關(guān)工作

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

2 問題描述

本節(jié)主要介紹RBAC模型，二分圖以及基于約束角色挖挖掘的相關(guān)定義，另外對(duì)于角色挖掘結(jié)果的評(píng)價(jià)標(biāo)準(zhǔn)也做了相關(guān)說明。RBAC模型的基本概念：

USERS表示為用戶集合，數(shù)量為n；

PERMS表示為權(quán)限集合，數(shù)量為m；

ROLES表示為角色集合，數(shù)量為q；

UA?USERS×RLOES為用戶角色分配關(guān)系；

PA?ROLES×PERMS為權(quán)限角色分配關(guān)系；

UPA?USERS×PERMS為用戶權(quán)限分配關(guān)系；

RH?ROLES×ROLES為角色繼承關(guān)系；

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

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

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

圖1 用戶權(quán)限關(guān)系(UPA)

圖2 角色挖掘的結(jié)果

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

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

定義4 加權(quán)結(jié)構(gòu)復(fù)雜度(weighted structural complexity，WSC)給定一個(gè)四元組W=，表示權(quán)重，wr,wu,wp,wh∈Q+∪{∞}；給定一個(gè)RBAC系統(tǒng)狀態(tài)；系統(tǒng)的復(fù)雜度用wsc(γ,W)表示

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

根據(jù)系統(tǒng)的配置需求，為不同的關(guān)系設(shè)置不同的權(quán)重，以滿足系統(tǒng)的安全原則和組織策略更好的維護(hù)系統(tǒng)的安全。

3 基于基數(shù)約束的角色挖掘算法

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

本文提出的算法(簡稱DCRM)將用戶權(quán)限關(guān)系UPA轉(zhuǎn)化為二分圖，挖掘滿足權(quán)限基數(shù)約束和用戶基數(shù)約束的最小完全二分圖集合得到初始角色集initRoles，然后調(diào)用圖優(yōu)化算法，優(yōu)化角色狀態(tài)、構(gòu)建角色層次得到最終的角色集。降低系統(tǒng)的加權(quán)結(jié)構(gòu)復(fù)雜度，提高管理效率。角色中權(quán)限的約束PermsR(r)約束值定義為k1、角色中用戶的約束RolesU(r)約束值定義為k2，其詳細(xì)描述如算法1所示：

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

輸入： 用戶權(quán)限分配關(guān)系UPA、K1、K2

輸出：角色集R

BEGIN

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

(2) While there can be more merges do

(3) 調(diào)用角色層次構(gòu)建算法，構(gòu)建角色層次

END

3.2 初始角色生成算法

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

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

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

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

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

輸入： 用戶集合U、權(quán)限集合P、 用戶權(quán)限分配關(guān)系UPA， 權(quán)限約束k1， 用戶約束k2

輸出： 用戶角色指派關(guān)系inintUA、 角色權(quán)限指派關(guān)系initPA以及初始角色集合initRoles

(1) 至少存在一個(gè)頂點(diǎn)存在未覆蓋的邊

(2) Set U=φ,P=φ

PermsRCount(r)=0,

RolesUCount(r)=0

{PHASE 1}

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

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

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

(6) P=UC[u]

(7) else 從UC[u]中取前k1個(gè)權(quán)限 //用戶中的權(quán)限數(shù)違反約束

(8) P=UC[k1]

(9) end if

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

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

//約束角色中用戶的數(shù)量

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

(13) 將v加入到U

(14) end if

(15) end for

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

(17) end if

{PHASE 2}

(18) if select vertice is perm then //選擇的頂點(diǎn)是權(quán)限

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

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

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

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

(23) 將v加入到U

(24) end if

(25) end for

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

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

(27) P=UC[u]

(28) else 從UC[u]中取前k1個(gè)權(quán)限 //若角色中的權(quán)限數(shù)不滿足約束

(29) P=UC[k1]

(30) end if

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

(32)end if

3.3 角色層次構(gòu)建算法

利用二分圖的方法得到的角色集是扁平化的結(jié)構(gòu)未能構(gòu)建角色層次，這就使得系統(tǒng)的復(fù)雜度高，管理花費(fèi)大，在大型系統(tǒng)應(yīng)用方面存在致命缺陷，沒有實(shí)際應(yīng)用價(jià)值。因此針對(duì)上述問題，在初始角色集的基礎(chǔ)上利用圖優(yōu)化策略，構(gòu)建系統(tǒng)中的角色間的繼承關(guān)系以及角色層次，得到最終完整角色狀態(tài)。

本文是在zhang等提出的GO算法[9]的基礎(chǔ)上進(jìn)行角色層次的構(gòu)建。GO算法的主要思想：選擇兩個(gè)角色，根據(jù)角色的權(quán)限集之間的關(guān)系處理角色，可為分為以下4種情況：

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

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

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

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

GO算法根據(jù)整個(gè)RBAC狀態(tài)判斷每兩個(gè)角色是否進(jìn)行處理。但是并沒有說明如何選擇兩個(gè)角色，本文是根據(jù)角色中權(quán)限的數(shù)量進(jìn)行降序排序，然后遍歷角色集，根據(jù)角色權(quán)限集之間的關(guān)系，處理角色間的繼承關(guān)系、構(gòu)造角色層次。本文所選用的GO算法是根據(jù)角色中的權(quán)限數(shù)，對(duì)角色狀態(tài)進(jìn)行更新，并不會(huì)使得分配給用戶的角色發(fā)生改變，因此最終的角色集不會(huì)違反系統(tǒng)中給定的約束。算法3描述了角色層次構(gòu)造算法的實(shí)現(xiàn)過程。

算法3： 角色層次構(gòu)建算法

輸入： initRoles

輸出： finallRoles

(1)對(duì)于initRoles中的角色按照角色中權(quán)限的數(shù)量排序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) 在不違反系統(tǒng)約束的前提下， 根據(jù)角色的權(quán)限集之間的關(guān)系處理角色 //若是角色合并后， 角色中的用戶數(shù)超出系統(tǒng)給定的約束， 則取消合并

(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 實(shí)驗(yàn)評(píng)估

為了檢驗(yàn)算法的性能與準(zhǔn)確性，本文采用9個(gè)真實(shí)世界的數(shù)據(jù)集作為測(cè)試數(shù)據(jù)對(duì)算法進(jìn)行實(shí)驗(yàn)分析。這些數(shù)據(jù)集主要是用于分析各種啟發(fā)式角色挖掘算法的性能，在角色挖掘相關(guān)的文獻(xiàn)中得到了廣泛的應(yīng)用。這些真實(shí)的數(shù)據(jù)集可以通過HP Labs在線獲得。真實(shí)數(shù)據(jù)集總結(jié)在表1中，U表示用戶數(shù)、P表示權(quán)限數(shù)、UPA表示用戶權(quán)限數(shù)、R表示無約束條件下生成的最佳角色數(shù)，以及分配給用戶的最大權(quán)限數(shù)max#P、分配給權(quán)限的用戶數(shù)max#U。

表1 實(shí)驗(yàn)數(shù)據(jù)集

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

圖3 權(quán)限基數(shù)約束和角色數(shù)量

圖4 權(quán)限基數(shù)約束和加權(quán)結(jié)構(gòu)復(fù)雜度WSC

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

圖5、圖6則展示了在用戶基數(shù)約束方面和挖掘出來角色數(shù)量、WSC的變化關(guān)系。對(duì)于用戶基數(shù)約束的實(shí)驗(yàn)本文中是對(duì)權(quán)限基數(shù)約束的值不做約束，DCRM和CRM比較的是用戶基數(shù)約束的值。從圖中可以看出本文提出的DCRM算法和Horned等[11]提出的基于用戶基數(shù)約束Algorithm1算法相比，有效降低了挖掘出的角色數(shù)量和加權(quán)結(jié)構(gòu)復(fù)雜度。

圖5 用戶基數(shù)約束和角色數(shù)量

圖6 用戶基數(shù)約束和加權(quán)結(jié)構(gòu)復(fù)雜度

圖7、圖8展示了在EMEA數(shù)據(jù)上，DCRM和CRM算法在權(quán)限基數(shù)約束下的變化關(guān)系，與Healthcare一樣，對(duì)于用戶基數(shù)不做約束。從圖中可以看出，本文提出的DCRM算法在角色數(shù)量方面不占優(yōu)勢(shì)，但是能夠有效降低加權(quán)結(jié)構(gòu)復(fù)雜度。

圖7 權(quán)限基數(shù)約束和角色數(shù)

圖8 權(quán)限基數(shù)約束和加權(quán)結(jié)構(gòu)復(fù)雜度

圖9、圖10展示了在EMEA數(shù)據(jù)上，DCRM和Algorithm1算法在用戶基數(shù)約束下的變化關(guān)系，從圖中可以看出其結(jié)果與Healthcare類似，DCRM算法明顯降低了角色數(shù)量和加權(quán)結(jié)構(gòu)復(fù)雜度。

圖9 用戶基數(shù)約束和角色數(shù)量

圖10 用戶基數(shù)約束和加權(quán)結(jié)構(gòu)復(fù)雜度

通過上述實(shí)驗(yàn)結(jié)果可以看出本文提DCRM算法是真實(shí)有效的，挖掘出來的角色都能夠滿足權(quán)限基數(shù)約束和用戶基數(shù)約束雙重基數(shù)約束，并且能夠有效降低角色數(shù)量和加權(quán)結(jié)構(gòu)復(fù)雜度。

5 結(jié)束語

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