基于枚舉法的角色挖掘及其約束性研究

孫偉++蘇輝

摘要：針對現有角色挖掘結果存在冗余、缺乏約束性等問題，結合RBAC系統狀態安全性等方面的研究，提出一種基于子集枚舉的角色挖掘研究方法，給出了枚舉角色挖掘的算法描述。該方法使用職責分離約束限制完成任務所需的最小用戶數，利用互斥角色約束限制用戶允許擁有的最大角色數，并給出了最小約束構造算法及其正確性證明，能夠滿足系統的安全性與約束性要求。

關鍵詞：角色挖掘 子集枚舉 安全性 約束性

中圖分類號：TP309 文獻標識碼：A 文章編號：1007-9416（2016）12-0064-02

基于角色的訪問控制（RBAC）是當前主流的訪問控制機制之一。為了在傳統非RBAC系統中實施RBAC策略，需要構造合適的角色集并輔助構建RBAC系統，稱之為角色工程。通常存在自頂向下與自底向上兩種角色工程方法[1-2]。自頂向下方法從工程用例的需求分析出發，根據執行任務所需的不同權限設計角色系統[3-4]。自上而下的方法得出的角色集雖然更加符合企業和組織的實際情況，但是該方法需要大量的專家對業務邏輯進行分析，而這種成本對中小型企業也許是無法承擔的，一旦組織內的業務和職能有所變化就需要重新進行業務分析得到新的角色集以適應這種變化。相比于自頂向下實施起來非常困難、容易出錯、成本代價高的缺點，自底向上方法從底層的用戶-權限分配關系出發，利用數據挖掘技術提取滿足已有訪問模式的不同權限而形成角色系統，并稱此方法為角色挖掘。與自頂向下的人工處理方式相比，角色挖掘能夠自動、快速地構建或輔助構建RBAC系統，現已成為角色工程技術的主要研究方向[5]。

現有角色挖掘方法按輸出結果可分為兩類：第一類僅輸出挖掘角色集，不考慮角色層次關系，這類算法包括Complete Miner（CM）、Fast Miner（FM）等；第二類輸出構建的系統狀態，允許存在角色層次，這類算法包括ORCA、Graph Optimization（GO）、HP Role Minimization（HPRM）、HP Edge Minimization（HPEM）、Hierarchical Miner（HM）。本文結合RBAC系統狀態安全性等方面的研究，提出一種基于子集枚舉的角色挖掘研究方法，以滿足應用系統的約束性要求。

1 基于子集枚舉的角色挖掘

文獻[6]通過枚舉底層的不同權限子集挖掘角色，并允許角色重疊，提出完全挖掘和快速挖掘兩種算法。前者雖能從用戶-權限分配關系中窮舉所有待選角色集，但時間復雜度為指數級，挖掘效率低；后者改進挖掘過程，統計關聯角色的用戶數，雖未能窮舉所有角色，但挖掘效率優于前者。

為了體現枚舉挖掘的高效性與完整性，基于枚舉法的角色挖掘基本思想：對于給定的訪問控制矩陣（M（UPAoriginal）），根據哈希映射規則將M（UPAoriginal）轉換為原始用戶-權限關聯（UPAoriginal）；將分配給用戶的不同權限集作為整體視為角色，確立原始角色集（InitRoles），并計算關聯不同角色的用戶數；結合集合論的枚舉法，通過二重循環將任意兩原始角色做交集，產生新角色（NewRole），確定候選角色集（CandRoles），進而構建URAoriginal和PRAoriginal。以下給出枚舉挖掘法的算法（EBRM Algorithm）描述。

EBRM Algorithm

輸入：M（UPA）

輸出：URA，Cand_Roles

1）根據哈希映射規則將M（UPA）轉換為UPA

2）創建Init_Roles

Begin

初始化Init_Roles=（；

for（UPA中的任意用戶u）

if（assigned_permissions（u）（Init_Roles） then

Init_Roles=Init_Roles（{assigned_permissions（u）}；

End

3）創建New_role，Cand_Roles，并指派URA

Begin

初始化New_role=null，Cand_Roles=（，URA=（；

for（Init_Roles的任意角色ri）

{Init_Roles= Init_Roles＼{ri}；

Cand_Roles=Cand_Roles（{ri}；

for（Init_Roles的任意角色rj）

{New_role= ri（rj；

if（（New_role（Cand_Roles）（（New_role！=rj）） then

{Cand_Roles=Cand_Roles（{New_role}（{rj}；

；

}

else if（New_role（Cand_Roles） then

；

else if（New_role==rj） then

；

}

}

End

2 系統狀態的安全性

隨著信息技術的不斷發展和大規模應用，系統的安全性備受關注。RBAC系統的安全性受角色工程方法的影響，而角色結果又取決于互斥約束的設置，不同的挖掘結果可能破壞系統安全。角色職責分離（k-n RSSOC）和互斥角色約束（t-m SMER）[7]是保證狀態（安全的兩項基本策略，能夠檢測不符合要求的角色。借助職責分離研究如何設置互斥約束，可以保證系統的安全性。以下給出兩命題。

命題1 當t=2時，c1=smer<{r1，r2，…，rn}，t>可準確實施e1=rssoc<{r1，r2，…，rn}，n>。

4 結語

本文提出的研究方法基于子集枚舉思想，給出了一種EBRM算法，并通過職責分離與互斥角色挖掘滿足約束要求的角色結果。然而，本文方法未能體現RBAC機制的權限分配勢約束要求，存在局限性。因此，如何優化角色挖掘，以滿足系統對權限所分配角色數的限制要求，進一步增強挖掘結果的可解釋性及系統的安全性是下一步需要研究的問題。

參考文獻

[1]Li R，Li H，Gu X，et al.Role Mining Based on Cardinality Constraints[J].Concurrency and Computation：Practice and Experience，2015，27（12）：3126-3144.

[2]Lu H，Hong Y，Yang Y，et al.Towards User-oriented RBAC Model[J].Journal of Computer Security，2015，23（1）：107-129.

[3]Lu H，Vaidya J，Atluri V.An Optimization Framework for Role Mining[J].Journal of Computer Security，2014，22（1）：1-31.

[4]Neumann G，Strembeck M.A Scenario-driven Role Engineering Process for Functional RBAC Roles[C]//Proceedings of the 7th ACM Symposium on Access Control Models and Technologies.New York：ACM Press，2002：33-42.

[5]馬曉普，李瑞軒，胡勁緯.訪問控制中的角色工程[J].小型微型計算機系統，2013，34（6）：1301-1306.

[6]Vaidya J，Atluri V，Warner J.Role Miner：Mining Roles Using Subset Enumeration[C]//Proceedings of the 13th ACM Conference on Computer and Communications Security.Alexandria：ACM press，2006：144-153.

[7]Li N，Tripunitara M V，Bizri Z.On Mutually Exclusive Roles and Separation of Duty[J].ACM Transaction on Information and System Security，2007，10（2）：42-51.