基于職責(zé)分離的角色挖掘算法

王靜宇 崔永嬌

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

0 引 言

在訪問控制系統(tǒng)中，基于角色的訪問控制(Role-based Access Control, RBAC)具有安全、靈活和高效等優(yōu)勢，是目前應(yīng)用研究最廣泛的訪問控制模型。訪問控制是為用戶分配一組權(quán)限，允許用戶去訪問系統(tǒng)中的某些資源，RBAC則是通過角色將權(quán)限組織在不同的集合中，并將角色分配給用戶。由于角色的數(shù)量遠(yuǎn)遠(yuǎn)小于權(quán)限的數(shù)量，因此在企業(yè)中使用RBAC系統(tǒng)能夠有效降低系統(tǒng)管理復(fù)雜度，提高管理效率。定義角色以及分配用戶的過程稱為角色工程[1]，主要有自上而下和自下而上兩種方法。自下而上是專家通過分析和分解企業(yè)的業(yè)務(wù)流程來構(gòu)造角色，但是當(dāng)企業(yè)中用戶和權(quán)限的數(shù)量變得非常大時，使用該方法構(gòu)建RBAC系統(tǒng)則變得費時費力，不再適用。因此，根據(jù)已有的用戶權(quán)限分配關(guān)系采用自動化或半自動化構(gòu)造角色的自下而上的方法應(yīng)運而生，這種方法又稱為角色挖掘，現(xiàn)已成為角色工程領(lǐng)域研究的主要方向[2]。此外，為了更好地配置RBAC系統(tǒng)，還需滿足各種具有約束的策略，例如：基數(shù)、先決條件和職責(zé)分離(Separation of Duty，SoD)。基數(shù)約束是指角色可擁有的用戶或權(quán)限數(shù)有限，權(quán)限可分配的角色數(shù)以及用戶可擁有的角色數(shù)有限。SoD是防止欺詐、保證計算機訪問安全的重要約束，通常是指對于給定的k和n，至少有k個用戶才用完成所給定的包含n個權(quán)限的任務(wù)。SoD是在權(quán)限方面約束用戶集，但在RBAC中通常使用靜態(tài)互斥角色(Statically Mutually Exclusive Roles，SMER)約束來實現(xiàn)。本文以權(quán)限分組為基礎(chǔ)(簡單角色挖掘算法)，結(jié)合靜態(tài)互斥角色約束條件，提出一種滿足靜態(tài)職責(zé)分離的角色挖掘算法。

1 相關(guān)工作

職責(zé)分離(SoD)是防止欺詐行為、保證計算機訪問安全的重要約束策略，也是RBAC系統(tǒng)所必須遵守的安全原則。對此，專家學(xué)者做了相關(guān)研究。熊厚仁等[3]針對RBAC系統(tǒng)中職責(zé)分離策略的冗余、沖突一致性解決問題，提出一種職責(zé)分離策略的一致性分析和判定的方法，但是該方法并未考慮到策略的實現(xiàn)和滿足性等問題。孫偉等[4]利用枚舉法，對互斥權(quán)限約束下的角色挖掘方法進行了優(yōu)化改進，由于該方法使用角色職責(zé)分離驗證安全約束的合理性，缺乏對于具體SoD策略的實施，且時間復(fù)雜度較大，因此在應(yīng)用場景中不具有實際意義。Chen等[5]對于約束集的生成問題進行了相關(guān)研究，定義角色層次結(jié)構(gòu)和一組SMER約束之間的兼容性概念，提出兼容性的必要和充分條件。Lu等[6]提出擴展布爾矩陣分解(EBMD)，是在Lu等[7]提出的矩陣分解(BMD)上進行擴展，允許負(fù)面授權(quán)角色中的否定權(quán)限或用戶中的負(fù)面角色來實施SoD約束。Li等[8]將靜態(tài)職責(zé)分離約束轉(zhuǎn)化為靜態(tài)互斥角色約束來實現(xiàn)，同時表明直接執(zhí)行SoD策略是難以實現(xiàn)的，檢查RBAC狀態(tài)是否滿足SoD策略則是有效的。同樣的，Sarana等[9]針對SoD約束策略的角色挖掘問題，提出SoD-aware和后處理兩種方法，SoD-aware是利用二分圖從在角色挖掘過程中形成可執(zhí)行的SMER，后處理的方法則是針對角色挖掘結(jié)果進行處理，判斷是否滿足約束。Roy等[10]基于圖的最小著色數(shù)方法，提出一種在多個SMER約束下查找最小用戶數(shù)的方法，得到滿足約束的用戶權(quán)限分配關(guān)系，但將SoD約束轉(zhuǎn)化為可強制執(zhí)行的SMER約束實際上是非常具有挑戰(zhàn)性的。因此，本文的目標(biāo)是以用戶權(quán)限矩陣(UPA)和一組SoD約束作為輸入，并找到與其一致的用戶角色(UA)和角色權(quán)限(PA)矩陣以及一組t-t SMER約束，這些約束能夠正確地強制執(zhí)行給定的SoD約束，同時優(yōu)化角色數(shù)量。

2 相關(guān)理論基礎(chǔ)

定義1布爾矩陣(UPA)。用戶-權(quán)限分配關(guān)系形式為定位布爾矩陣即二元0-1矩陣(Binary Matrix)，其中行表示用戶，列表示權(quán)限。UPA矩陣中(ui，pi)值為1，表示用戶ui擁有權(quán)限pi，若沒有則表示為0。因此，角色挖掘就是將給定的用戶-權(quán)限關(guān)系矩陣(UPA)，分解成用戶-角色分配關(guān)系(UA)和角色-權(quán)限分配關(guān)系(PA)布爾矩陣。

定義2RBAC模型。假設(shè)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)系。

定義3k-n職責(zé)分離約束(k-n SoD)。k-n SoD約束定義為sod<{p1,p2,…，pn},K>,其中：1

定義4t-m 靜態(tài)互斥角色(t-m SMER)。t-m SMER約束定義為smer<{r1,r2,…,rm}，t>，其中:1

定義5t-t 靜態(tài)互斥角色(t-t SMER)。t-t SMER約束定義為smer<{r1,r2,…,rt}，t>，其中t≥2，1。SMER約束集合為C={C1∪C2…∪Ci}，Ci=<{r1,r2,…,rm}，t>代表一個SMER約束。

定義5靜態(tài)職責(zé)分離約束下的角色挖掘(SoD-Role Mining Perms，SRMP)。給定一個用戶權(quán)限分配關(guān)系UPA，一組SoD約束E，找到一組角色集R，用戶角色分配關(guān)系UA，角色權(quán)限分配關(guān)系PA，SMER約束集合C，使得C強制執(zhí)行E并且最小化角色數(shù)量|R|。

3 算法設(shè)計

3.1 基于職責(zé)分離的角色挖掘算法(SRMP)

本文提出的滿足靜態(tài)職責(zé)分離的角色挖掘算法(SRMP)，采用布爾矩陣UPA表示系統(tǒng)中的用戶權(quán)限分配關(guān)系，以權(quán)限分組為基礎(chǔ)，在角色挖掘過程中實施t-t SMER約束，強制執(zhí)行SoD約束，得到滿足約束的UA、PA，以及t-t SMER約束集C，同時最小化角色數(shù)量。其詳細(xì)描述如算法1所示。

算法1滿足靜態(tài)職責(zé)分離的角色挖掘算法SRMP

輸入：用戶權(quán)限分配關(guān)系UPA，一組 SoD約束E。

輸出：用戶角色分配關(guān)系UA，角色權(quán)限分配關(guān)系PA，角色SoD約束關(guān)系SA，角色集R，t-t SMER約束集C。

BEGIN

1. 調(diào)用角色生成算法(mineRole)；

2. 判斷約束滿足問題；

3. 調(diào)用t-t SMER 約束生成算法(t-t SMER)；

END

3.2 角色生成算法(MineRole)

MineRole算法是在Blundo 等[11]提出的簡單角色挖掘算法(Simple Role Mining Algorithm)基礎(chǔ)上，采用在矩陣中權(quán)限分組的挖掘方式，生成角色集，同時在挖掘角色的過程中為角色賦予SoD約束信息，同樣采用布爾矩陣表示角色與SoD約束關(guān)系SA。

本文中定義U[p]為用戶u中的權(quán)限P、UC[p]定義為用戶u中未被覆蓋的權(quán)限p。U定義為角色中的用戶、P定義為角色中的權(quán)限、Sei定義為包含一組SoD約束信息的角色集。

首先將用戶權(quán)限關(guān)系轉(zhuǎn)化成布爾矩陣UPA表示，根據(jù)用戶中的權(quán)限數(shù)進行降序排序，然后選擇用戶中具有最少未被覆蓋的權(quán)限的一行，作為新生成角色中的權(quán)限，加入到P中。判斷新角色中的權(quán)限是否是ei中的權(quán)限，如果是則將ei約束信息賦予新生成的角色。根據(jù)所選擇的權(quán)限P，查看其他用戶中未被覆蓋的權(quán)限是否包含P，若是則加入到U中。最后從用戶權(quán)限UPA中刪除已被選擇的權(quán)限即將矩陣中被選擇的(ui,pi)變?yōu)?。其詳細(xì)算法描述如算法2所示。

算法2角色生成算法(MineRole)

輸入：用戶集合U，權(quán)限集合P，用戶權(quán)限分配關(guān)系UPA，k-n SoD約束集E。

輸出：用戶角色分配關(guān)系UA，角色權(quán)限分配關(guān)系PA，角色與SoD約束關(guān)系SA，初始角色集initRoles。

BEGIN：

1.candidateRoles=?,U=?,P=?,Sei=?；

2. while there exists at least one useruwith uncovered perms

//至少存在一個未被覆蓋權(quán)限的用戶

3. do

4. selectuwith minimum number of uncovered perms；

//選擇具有最少權(quán)限的一行

5. newRoleP=select row；

//新生成角色中的權(quán)限

6. candidateRoles=candidateRolesU{newRole}；

//新生成的角色加入候選角色集

7. if newRole having at least one permission inei

//新生成的角色中包含約束ei中的權(quán)限

8.Sei=SeiU{newRole}；

//為角色賦予SoD約束信息

9. end if

10. forv≠u

//查找其他包含P權(quán)限的用戶

11. do

12. ifP?UC[p]

13. newRoleU=U{V}；

14. end if

15. end for

END

3.3 t-t SMER約束生成算法

t-t SMER約束生成算法是根據(jù)上文得到的用戶角色分配關(guān)系UA、角色權(quán)限分配關(guān)系UA、角色與SoD約束關(guān)系SA，以及初始角色集initRoles，進行計算處理得到最終的角色權(quán)限分配關(guān)系UA、最終角色集finalRoles。

t-t SMER約束生成算法，根據(jù)算法1得到的角色與SoD約束關(guān)系SA，找到包含ei約束權(quán)限的角色集Sei，并計算角色的數(shù)|Sei|，若存在一個角色包含ei約束中的所有權(quán)限或角色數(shù)|Sei|小于用戶數(shù)k，則該約束不可執(zhí)行。然后根據(jù)定理1，得到t-t SMER約束中可以設(shè)置的最大約束值t，設(shè)置合理的約束值。同時計算UA中，用戶分配的角色集中包含ei約束的角色數(shù)n，判斷n和t的大小。若n})加入到t-t SMER約束集C；若n>t,則說明該用戶角色分配關(guān)系不滿足約束，選取前t個約束角色分配給用戶，并從剩余角色中刪除約束權(quán)限，生成不包含約束權(quán)限的新角色，重新分配給用戶u和新角色集、UA、PA，得到最終角色集finalRoles、用戶角色分配關(guān)系UA，以及角色權(quán)限分配關(guān)系PA。其詳細(xì)算法描述如算法3所示。

算法3t-t SMER約束生成算法

輸入：用戶角色分配關(guān)系UA，角色權(quán)限分配關(guān)系PA，角色與SoD約束關(guān)系SA，k-n SoD約束E，初始角色集initRoles。

輸出：t-t SMER約束集C，finalRoles，用戶角色分配關(guān)系UA，角色無權(quán)限分配關(guān)系PA。

BEGIN:

1. caculate the number |Sei| formSA

//包含ei約束的角色數(shù)；

//得到最大的t值；

3. for eachrinSei

4. If any role inSeihas all the permission ineithen

//若Sei中存在一個角色包含所有ei中的約束權(quán)限

5. Declareeias not enforceable；

//聲明ei約束不能強制執(zhí)行

6. continue

7. end if

8. if

9. |Sei|

//角色的數(shù)量小于用戶的數(shù)量

10. Declareeias not enforceable；

11. continue

12. end if

13. for each subset of rolesRof sizetfromSei

14. do

15. caculatenthe number of roles ofCiformUA；

//用戶u中包含Ci約束的角色數(shù)

16. if

17.n

//如果用戶中的角色滿足約束

18.C=CU{}

//將該約束加入t-t SoD約束集

19. else

20. Select firstt-1 roles inuand generate new roles；

//選擇前t個角色分配個用戶u，并生成

//新角色，即從剩余角色中刪除約束權(quán)限

21. Declareeias not enforceable；

//聲明ei約束不能強制執(zhí)行

22. updateUA；

//更新UA，為用戶u重新分配不含約束的角色

23. end if

END

3.4 實例分析

用戶集U={u1,u2,…,u7}，權(quán)限集P={p1,p2,…,p7}，一個由7個用戶7個權(quán)限構(gòu)造的用戶權(quán)限關(guān)系矩陣如表1所示，設(shè)定k-n SoD約束集：

表1 用戶權(quán)限關(guān)系矩陣表(UPA)

E={e1,e2}：

e1=<{p1,p3,p4},2>

e2=<{p1,p5,p6},2>

首先根據(jù)用戶中的權(quán)限數(shù)降序排序，選擇包含權(quán)限數(shù)最小的一行即用戶u6，r1分配權(quán)限{p3,p4,p6}，e1、e2約束的權(quán)限分別包括{p3,p6}，用戶{u4,u5,u6}包含r1中的權(quán)限。下一次選擇用戶u5，r2分配權(quán)限{p5}，e2約束的權(quán)限包含{p5},用戶{u1,u2,u3,u4}包含r2中的權(quán)限。r3選擇的用戶為u2,權(quán)限{p1,p4}，e1、e2約束的權(quán)限包含p1,故為r3賦予e1、e2約束信息，用戶{u2,u7}包含r3中的權(quán)限。R4選擇u3，r4分配權(quán)限為{p2,p7}，該角色分配的用戶為{u1,u3}。r5選擇用戶u4,分配權(quán)限為{p1,p3,p6}，e1、e2約束權(quán)限均包含p1，故為r5賦予約束信息e1、e2,分配的用戶為{u4,u5}。得到用戶角色分配關(guān)系UA、角色權(quán)限分配關(guān)系PA以及角色SoD約束信息SA矩陣，分別如表2、表3和表4所示。

表2 用戶角色關(guān)系矩陣(UA)

表3 角色權(quán)限關(guān)系矩陣(PA)

表4 角色與SoD約束關(guān)系矩陣(SA)

根據(jù)上文中得到的角色SoD約束布爾矩陣表，計算t-t SMER約束中t可取的最大值，e1為3，e2為4，本文中均取t值為3，計算用戶中包含約束的角色數(shù)，e1包含的角色為{r1,r3,r5}，轉(zhuǎn)化為 t-t SMER約束為c1={,3}，根據(jù)UA判斷用戶中包含e1約束的角色均滿足c1,因此e1是可執(zhí)行的。e2包含的角色為{r1,r2,r3,r5}，轉(zhuǎn)化為t-tSMER為c1={,3}，c2={,3}，c3={,3}，c4={,3}，同樣根據(jù)UA判斷用戶中包含e2約束的角色均滿足e2,因此e2是可執(zhí)行的。得到最終的3-3 SMER約束集為C={C1∪C2∪C3∪C4}。

4 實驗與結(jié)果分析

為了驗證算法的準(zhǔn)確性與有效性，采用現(xiàn)有的數(shù)據(jù)集對算法進行實驗分析，并與文獻[8]中提出的Naive approach方法進行比較。Naive approach方法是將給定的SoD約束轉(zhuǎn)化為角色級別的靜態(tài)職責(zé)分離(RSSoD)，根據(jù)RSSoD要求生成SMER約束。實驗數(shù)據(jù)集如表5所示。

表5 實驗數(shù)據(jù)集

本文的實驗環(huán)境是：Inter(R)Core(TM)i3-3240 CPU 3.4 GHz,12 GB內(nèi)存，340 GB，Window 10操作系統(tǒng)。在Eclipse開發(fā)環(huán)境下，利用Java語言實現(xiàn)算法。

本文選取2-2 SoD、2-3 SoD、3-5 SoD、3-7 SoD、5-10 SoD 5種不同類型的約束作為參數(shù)進行實驗。對于給定的K和n值，從所有權(quán)限種隨機選擇n個權(quán)限。針對每一種SoD約束的數(shù)量，每次實驗固定選取為20。但由于每次選取的權(quán)限是隨機的，可能存在偏差，因此對于每個SoD實驗重復(fù)20次，選取平均值作為結(jié)果。實驗展示不同類型約束以及不同約束數(shù)量下，SRMP和naive approach算法在生成SMER數(shù)量、運行時間的對比關(guān)系。實驗結(jié)果如圖1和圖2所示。

圖1 t-t SoD和SMER數(shù)變化關(guān)系

圖2 k-n SoD和運行時間變化關(guān)系

從圖1的實驗結(jié)果可以看出，隨著k、n參數(shù)的增加，本文所提出的SRMP算法和Naive approach算法所生成SMER約束數(shù)也不斷增多，雖然差別不大但從總體看SRMP算法生成的SMER數(shù)還是少于Naive approach算法的。從圖2的實驗結(jié)果可以看出，SRMP算法在運行時間上占據(jù)顯著優(yōu)勢，尤其是當(dāng)系統(tǒng)中數(shù)據(jù)量增多、k和n約束值增大時，與Naive approach算法相比，更能體現(xiàn)SRMP算法的運行效率。實驗結(jié)果表明SRMP算法明顯優(yōu)于Naive approach算法。

5 結(jié) 語

本文提出的基于職責(zé)分離的角色挖掘算法，在角色挖掘過程中考慮SoD約束，生成 t-t SMER約束集強制執(zhí)行SoD約束；使用布爾矩陣表示用戶權(quán)限分配關(guān)系，利用權(quán)限分組挖掘角色，同時根據(jù)為角色賦予SoD約束信息；根據(jù)得到的用戶角色、角色SoD約束關(guān)系，生成SMER約束集。實驗結(jié)果表明，該算法能夠有效實施給定的SoD約束生成t-t SMER約束集。未來將在本文算法中考慮其他約束，例如基數(shù)約束、最小特權(quán)等，進一步提高系統(tǒng)安全。