基于職責分離的角色挖掘算法

王靜宇 崔永嬌

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

0 引 言

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

1 相關工作

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

2 相關理論基礎

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

定義2RBAC模型。假設USERS表示用戶集合，數量為n；PERMS表示權限集合，數量為m；ROLES表示角色集合，數量為q；UA?USERS×RLOES為用戶角色分配關系；PA?ROLES×PERMS為權限角色分配關系；UPA?USERS×PERMS為用戶權限分配關系；RH?ROLES×ROLES為角色繼承關系。

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

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

定義5t-t 靜態互斥角色(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靜態職責分離約束下的角色挖掘(SoD-Role Mining Perms，SRMP)。給定一個用戶權限分配關系UPA，一組SoD約束E，找到一組角色集R，用戶角色分配關系UA，角色權限分配關系PA，SMER約束集合C，使得C強制執行E并且最小化角色數量|R|。

3 算法設計

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

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

算法1滿足靜態職責分離的角色挖掘算法SRMP

輸入：用戶權限分配關系UPA，一組 SoD約束E。

輸出：用戶角色分配關系UA，角色權限分配關系PA，角色SoD約束關系SA，角色集R，t-t SMER約束集C。

BEGIN

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

2. 判斷約束滿足問題；

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

END

3.2 角色生成算法(MineRole)

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

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

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

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

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

輸出：用戶角色分配關系UA，角色權限分配關系PA，角色與SoD約束關系SA，初始角色集initRoles。

BEGIN：

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

2. while there exists at least one useruwith uncovered perms

//至少存在一個未被覆蓋權限的用戶

3. do

4. selectuwith minimum number of uncovered perms；

//選擇具有最少權限的一行

5. newRoleP=select row；

//新生成角色中的權限

6. candidateRoles=candidateRolesU{newRole}；

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

7. if newRole having at least one permission inei

//新生成的角色中包含約束ei中的權限

8.Sei=SeiU{newRole}；

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

9. end if

10. forv≠u

//查找其他包含P權限的用戶

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約束生成算法是根據上文得到的用戶角色分配關系UA、角色權限分配關系UA、角色與SoD約束關系SA，以及初始角色集initRoles，進行計算處理得到最終的角色權限分配關系UA、最終角色集finalRoles。

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

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

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

輸出：t-t SMER約束集C，finalRoles，用戶角色分配關系UA，角色無權限分配關系PA。

BEGIN:

1. caculate the number |Sei| formSA

//包含ei約束的角色數；

//得到最大的t值；

3. for eachrinSei

4. If any role inSeihas all the permission ineithen

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

5. Declareeias not enforceable；

//聲明ei約束不能強制執行

6. continue

7. end if

8. if

9. |Sei|

//角色的數量小于用戶的數量

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約束的角色數

16. if

17.n

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

18.C=CU{}

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

19. else

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

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

//新角色，即從剩余角色中刪除約束權限

21. Declareeias not enforceable；

//聲明ei約束不能強制執行

22. updateUA；

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

23. end if

END

3.4 實例分析

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

表1 用戶權限關系矩陣表(UPA)

E={e1,e2}：

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

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

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

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

表3 角色權限關系矩陣(PA)

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

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

4 實驗與結果分析

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

表5 實驗數據集

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

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

圖1 t-t SoD和SMER數變化關系

圖2 k-n SoD和運行時間變化關系

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

5 結 語

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