基于互斥權限約束的角色挖掘優(yōu)化方法

孫 偉,蘇 輝,李艷靈

(信陽師范學院a.計算機與信息技術學院;b.網(wǎng)絡信息與計算中心,河南信陽464000)

基于互斥權限約束的角色挖掘優(yōu)化方法

孫 偉a,蘇 輝b,李艷靈a

(信陽師范學院a.計算機與信息技術學院;b.網(wǎng)絡信息與計算中心,河南信陽464000)

現(xiàn)有自底向上的角色工程方法挖掘規(guī)模龐大,挖掘結果存在冗余,且不能反映系統(tǒng)功能的安全需求。為優(yōu)化角色結果,針對角色優(yōu)化中的互斥約束問題,結合枚舉角色挖掘,提出一種基于互斥權限約束的角色挖掘優(yōu)化方法。利用用戶聚類元組及互斥約束優(yōu)化角色挖掘過程,通過角色職責分離對安全約束的合理性進行分析,采用矩陣分析法調整已挖掘權限的矩陣單元值,挖掘優(yōu)化角色以覆蓋所有權限。實驗結果表明,通過權限覆蓋分析法輔助挖掘的優(yōu)化角色結果能夠保證挖掘過程的完整性;與枚舉挖掘法相比,該方法能夠保證信息系統(tǒng)的安全性,降低角色結果的冗余度。

基于角色的訪問控制;角色工程;角色挖掘;角色優(yōu)化;互斥權限約束;訪問控制矩陣

1 概述

基于角色的訪問控制(Role-based Access Control,RBAC)系統(tǒng)具有管理方便、操作簡單、靈活而穩(wěn)定等優(yōu)點,是大規(guī)模企業(yè)等組織建立系統(tǒng)應用的首選機制。從企業(yè)組織的功能需求出發(fā),構建能準確反映其功能特征的RBAC系統(tǒng)關鍵在于設計合適的角色集。為此,研究者們提出了角色工程技術以及自頂向下和自底向上2種基本方法。與采用人工處理、耗時費力的自頂向下方法相比,自底向上方法［1］從已經(jīng)存在的用戶-權限分配關系出發(fā),利用數(shù)據(jù)挖掘技術自動、快速地構造角色集,以輔助構建RBAC系統(tǒng)。該方法又稱角色挖掘,現(xiàn)已成為角色工程技術的主要研究方向［2］。不同角色之間可以包含若干相同權限,角色結果也可以通過組合不同權限得到不同的角色集合,而在實際系統(tǒng)的構建與管理中存在以下問題:一方面,隨著構建系統(tǒng)的推廣應用,某些角色可能沒有指派或只指派給了少數(shù)用戶,未被頻繁使用,即挖掘結果存在冗余;另一方面,對于組織內部的若干個權限,系統(tǒng)往往約定共同擁有這些權限所需的最少角色數(shù),而挖掘角色的可解釋性較差,不能合理地反映系統(tǒng)功能的安全需求,存在安全隱患。基于此,對挖掘的角色集合或系統(tǒng)狀態(tài)進行優(yōu)化處理,以增強系統(tǒng)簡潔性與可解釋性的角色優(yōu)化技術應運而生［3］,其能夠為構建滿足實際應用需求的RBAC系統(tǒng)提供優(yōu)秀的解決方案。因此,如何進一步優(yōu)化角色挖掘,并評價角色結果的冗余性以及系統(tǒng)狀態(tài)的安全性很具挑戰(zhàn)性,是一項熱點研究課題。

本文以枚舉挖掘法為基礎,結合角色優(yōu)化中的互斥約束問題,提出一種基于互斥權限約束的角色挖掘優(yōu)化方法。

2 相關研究

文獻［4］針對挖掘角色缺乏語義性,利用形式化概念格表示角色的語義特征,設計屬性挖掘算法表征用戶的相關屬性信息,優(yōu)化角色挖掘以反映系統(tǒng)的功能需求,能夠增強挖掘結果的可解釋性。文獻［5］通過圖優(yōu)化算法減少圖中用戶與角色、權限與角色頂點之間邊的數(shù)目,優(yōu)化RBAC模型以減輕管理員進行角色分配的工作量,進而優(yōu)化RBAC系統(tǒng),但該方法未對挖掘結果的冗余性作進一步研究。針對該問題,文獻［6］基于圖論的思想并采用貪心算法,尋求反映用戶-權限分配關系且含盡可能少數(shù)目的優(yōu)化角色集合,能夠降低挖掘結果的冗余度。文獻［7］定義給出了基本角色挖掘問題,它將角色挖掘轉化為矩陣分解問題,以挖掘覆蓋用戶-權限分配關系的最小角色集,但在實際應用中很難提取到可用的最優(yōu)角色組合。隨后,該文獻又提出了δ-近似角色挖掘問題,即在滿足系統(tǒng)設定的冗余閾值情況下,挖掘允許具有一定冗余性的次優(yōu)角色組合。這是容易實現(xiàn)的,并具有實際應用價值。然而,以上角色優(yōu)化研究方法均未體現(xiàn)RBAC機制的約束思想。如果一個構建好的RBAC系統(tǒng)缺少必要的約束機制,那么系統(tǒng)的一系列安全需求將難以實現(xiàn)。為此,文獻［8］定義了一系列約束,并通過頻繁項集挖掘算法生成權限組與權限組、角色組與角色組之間的互斥約束規(guī)則,優(yōu)化角色挖掘以滿足系統(tǒng)的安全性要求。為防止角色權力過大,文獻［9］提出一種啟發(fā)式角色挖掘算法,以限制挖掘角色擁有不超過系統(tǒng)約定的權限數(shù),但角色權力過小,挖掘結果既存在冗余也不實用。

3 研究基礎及問題描述

定義1 角色工程元素

使用標準RBAC模型的用戶集(U)、角色集(R)、權限集(P)、用戶-角色關聯(lián)(URA)、權限-角色關聯(lián)(PRA),不考慮角色層次,并用UPA擴展表示用戶-權限關聯(lián)。p(u)、r(p(u))分別表示在角色工程中分配給用戶u的權限集以及包含此權限集的角色,可形式化表示為:

定義2 訪問控制矩陣

如果m,n分別表示用戶數(shù)(|U|)和權限數(shù)(|P|),那么 UPA的二維布爾矩陣表示為M(UPA)m×n。矩陣中的元素稱為單元,用cell(i,j)表示第i行、第j列單元,其在計算機中的存儲形式為:

3.1 基于枚舉法的角色挖掘

文獻［10］通過枚舉底層的不同權限子集挖掘角色,并允許角色重疊,提出完全挖掘和快速挖掘2種算法。前者雖能從用戶-權限分配關系中窮舉所有待選角色集,但時間復雜度為指數(shù)級、挖掘效率低;后者改進挖掘過程,統(tǒng)計關聯(lián)角色的用戶數(shù),雖未能窮舉所有角色,但挖掘效率高于前者。為了體現(xiàn)枚舉挖掘的高效性與完整性,本文給出挖掘過程,描述如下:

(1)對于給定的訪問控制矩陣(M(UPAoriginal)),根據(jù)哈希映射規(guī)則將M(UPAoriginal)轉換為原始用戶-權限關聯(lián)(UPAoriginal)。

(2)將分配給用戶的不同權限集作為整體視為角色,確立原始角色集(InitRoles),并計算關聯(lián)不同角色的用戶數(shù)。

(3)結合集合論的枚舉法,通過二重循環(huán)將任意2個原始角色做交集,產(chǎn)生新角色(NewRole),確定候選角色集 (CandRoles),進而構建 URAoriginal和PRAoriginal。

3.2 角色優(yōu)化中的互斥約束問題

互斥約束包括靜態(tài)約束與動態(tài)約束,而基于挖掘現(xiàn)存UPA的角色工程技術通過實施約束限制,進一步優(yōu)化挖掘過程,不存在會話。因此,角色優(yōu)化中互斥約束問題的求解過程是靜態(tài)的,以下給出互斥權限約束的描述。

定義3 互斥權限約束(Mutually Exclusive Permissions Constraints,MEPC)

角色挖掘中任意角色擁有{p1,p2,…,pm}的權限數(shù)都不能多于 t個,表示為 mepc＜{p1,p2,…, pm},t＞,其中1＜t≤m。

4 基于互斥權限約束的角色挖掘優(yōu)化

定義4 用戶聚類元組

用四元組 ＜c,InitRoles(c),Count_Users(c), Count_Unvisitedperms(c)＞表示具有相同權限集的用戶群及相關屬性信息。若c為某用戶聚類,并用C表示所有用戶聚類的集合,則InitRoles(c)表示c的原始角色集;Count_Users(c)表示c包含的用戶數(shù);Count_Unvisitedperms(c)表示c的未被訪問權限數(shù)。

基于枚舉法挖掘的步驟(1)和步驟(2),結合互斥權限約束的描述,優(yōu)化角色挖掘過程。

4.1 用戶聚類的創(chuàng)建及排序

為了降低挖掘規(guī)模,將擁有相同操作權限的用戶群聚成一類,給出用戶聚類創(chuàng)建算法(UsersClusters_Creating Algorithm),描述如下。其中,p(c)表示用戶聚類c關聯(lián)的權限集,r(p(c))表示包含c所關聯(lián)權限集的角色。

算法1 UsersClusters_Creating Algorithm

輸入 數(shù)據(jù)集D=＜U,P＞,UPA,InitRoles,C

輸出 四元組＜c,InitRoles(c),Count_Users(c), Count_Unvisitedperms(c)＞,c∈C,InitRoles(c)∈InitRoles

4.2 優(yōu)化角色挖掘

為了優(yōu)化角色結果,對于算法1生成的聚類元組及給定的互斥約束mepc＜{p1,p2,…},t＞,給出優(yōu)化角色挖掘算法(OptimRoles_Mining Algorithm),描述如下:

算法2 OptimRoles_Mining Algorithm

輸入 用戶聚類集C,聚類元組＜c,InitRoles(c), Count_Users(c),Count_Unvisitedperms(c)＞,約束值t

輸出 角色結果OptimRoles

5 合理性與完整性分析

通過臨時創(chuàng)建用戶聚類集并考慮互斥約束,優(yōu)化角色挖掘過程,容易從底層UPA中挖掘滿足約束要求的角色結果。隨著信息技術的不斷發(fā)展和大規(guī)模應用,系統(tǒng)的安全性備受關注。RBAC系統(tǒng)的安全性受角色工程方法的影響,而角色結果又取決于互斥約束的設置,不同的挖掘結果可能破壞系統(tǒng)安全。角色職責分離(Role Separation of Duty,RSOD)是保證系統(tǒng)安全的一項基本策略［11］,它能夠檢測不符合要求的角色。因此,有必要借助職責分離研究如何設置互斥約束,以保證系統(tǒng)的安全性。

5.1 互斥約束的合理設置

定義5 角色職責分離

對于系統(tǒng)資源的若干訪問權限p1,p2,…,至少需要k個角色,而任意(k-1)個角色都不能覆蓋{p1,p2,…},并稱系統(tǒng)是安全的;否則,系統(tǒng)是不安全的。用rsod＜{p1,p2,…},k＞表示覆蓋{p1,p2,…}最少需要k個角色,其中1＜k≤|{p1,p2,…}|。rsod＜{p1,p2,…},k＞下系統(tǒng)狀態(tài)描述為:

違反系統(tǒng)的安全性要求。假設不成立,定理得證。

5.2 優(yōu)化角色的完整挖掘

根據(jù)優(yōu)化挖掘的結果并結合與其關聯(lián)的用戶聚類,為避免重復挖掘,需要刪除其他聚類中已被挖掘的角色,并修改聚類中未被訪問的權限,直至所有權限被訪問。由于系統(tǒng)資源的多樣性以及資源訪問的多變性,算法2中使用直接刪除聚類權限的傳統(tǒng)計數(shù)方法非常繁瑣,且難以保證統(tǒng)計結果的完整性。計算機科學中的二維布爾矩陣是存儲與表示規(guī)模級UPA的一種有效方法,其根據(jù)挖掘角色動態(tài)地調整不同行矩陣的單元值,直至所有矩陣單元的值為0。因此,有必要研究如何計算矩陣中值為1的剩余單元數(shù),以輔助統(tǒng)計未被訪問的權限。

為了使挖掘結果覆蓋所有權限,保證角色挖掘的完整性,結合優(yōu)化挖掘過程及布爾矩陣的存儲,給出未被訪問權限的統(tǒng)計方法(Unvisitedperms_ Counting Algorithm),描述如下:

算法3 Unvisitedperms_Counting Algorithm

輸入 權限集P,算法1的用戶聚類C,算法2挖掘的角色or,or∈OptimRoles

輸出 算法2的Count_Unvisitedperms(ci),ci∈C

5.3 應用實例

圖1(a)給出一個由15個用戶、4個權限構造的原始矩陣M(UPAoriginal)15×4。按照用戶關聯(lián)權限數(shù)的降序形式,圖1(b)表示與M(UPAoriginal)15×4對應的排列矩陣M(UPAsorted)13×4。為了降低挖掘規(guī)模,通過調用算法1,容易得到M(UPAsorted)13×4的聚類矩陣M(CPAsorted)4×4及聚類元組結構分別如圖1(c)、表1所示。

圖1 訪問控制矩陣

表1 用戶聚類元組

根據(jù)表1的聚類結果并設置約束值t=2,通過算法 2得到OptimRoles={{p4},{p2,p3},{p1,p2}},過程如表2所示。

表2 挖掘過程

結合以上的循環(huán)挖掘,算法3將已挖掘角色對應的矩陣單元值修改為0,并將第ci行中值為1的剩余單元賦予Count_Unvisitedperms(ci)。基于M(CPAsorted)4×4,依次挖掘{p4},{p2,p3},{p1,p2}后的聚類矩陣分別如圖2(a)、圖2(b)、圖2(c)所示。實例結果表明,OptimRoles能夠覆蓋所有權限。

圖2 權限覆蓋過程

結合以上挖掘的3個角色,將職責分離描述為rsod＜{p1,p2,p3,p4},3＞,即在構建RBAC系統(tǒng)時至少需要3個角色,那么在角色工程中當互斥約束設置為mepc＜{p1,p2,p3,p4},2＞時,容易驗證系統(tǒng)是安全的。然而,從表3給出的優(yōu)化前后角色關聯(lián)結果可以看出,在枚舉法挖掘的6個角色中,{p1,p2,p4}與{p2,p3}、{p1,p2,p4}與{p2,p3,p4}均不滿足rsod＜{p1,p2,p3,p4},3＞要求,且角色數(shù)高于本文方法挖掘結果。

表3 角色挖掘關聯(lián)比較

6 實驗與結果分析

為了進一步驗證本文方法的有效性,實驗選用部分組織機構的真實數(shù)據(jù)集［12］進行測試與分析,并與枚舉挖掘法進行比較。給出實驗前的相關數(shù)據(jù)準備如表4所示。

表4 數(shù)據(jù)集描述

6.1 實驗設置及測試環(huán)境

實驗對約束值t變化在區(qū)間(1,|P|］的不同矩陣進行測試,評估挖掘的角色數(shù)|OptimRoles|。相關測試環(huán)境包括:奔騰雙核E5400CPU 2.70 GHz,2 GB內存,160 GB硬盤,Window XP操作系統(tǒng);在Java中實現(xiàn)算法1和算法2,通過二重循環(huán)構造原始矩陣M(UPA)及聚類矩陣M(CPA);使用角色挖掘器Rminer［13］。

6.2 結果分析及比較

隨t值的變化,挖掘結果如圖3所示。其中,x軸表示t值,y軸表示|OptimRoles|值。

以M(UPAoriginal1)為例,從圖3(a)的實驗結果可以看出:當t=1時,由互斥約束mepc＜|P|,1＞可知,需要設置315個角色,且每個角色只含一個權限,這是不實用的;當2≤t＜6,隨著t值的增大, |OptimRoles|值呈顯著下降趨勢,從48變化到18;當6≤t≤21,隨著t值的增大,|OptimRoles|值呈平緩下降趨勢,變化不明顯且始終保持在14～20之間;當t＞21,隨著t值的增大,|OptimRoles|值趨于平穩(wěn)。這是因為t值越小,約束性就越弱,滿足約束要求的角色數(shù)就越多,在t值達到6之前|OptimRoles|值明顯比較大,角色冗余度也就越高。t值越大,約束性越強,滿足約束要求的角色數(shù)越少,在t值超過6之后|OptimRoles|值逐漸減小,角色冗余度就越低。盡管在t值超過21之后|OptimRoles|值趨于穩(wěn)定,根據(jù)互斥約束設置的合理性論證,一旦t取值過大,系統(tǒng)是不安全的。

因此,當t值變化在區(qū)間［6,21］時, |OptimRoles|取值在區(qū)間［14,20),能夠保證系統(tǒng)的安全性。基于上述分析方法,挖掘M(UPAoriginal2),M(UPAoriginal3),M(UPAoriginal4)的優(yōu)化角色數(shù)區(qū)間分別是［34,40),［20,25),［66,71),結果分別如圖3(b)、圖3(c)及圖3(d)所示。從表5給出的實驗結果可以看出,枚舉法挖掘的角色數(shù)明顯高于本文方法。

圖3 不同t值下的角色挖掘結果

表5 挖掘結果比較

7 結束語

本文提出的角色優(yōu)化方法使用聚類元組表示用戶群及其屬性信息,利用互斥權限約束挖掘滿足約束要求的優(yōu)化角色,并通過職責分離及權限覆蓋分析法論證挖掘過程的合理性與完整性。應用實例與實驗分析結果表明,該方法挖掘的優(yōu)化角色數(shù)少于枚舉挖掘結果,可保證系統(tǒng)的安全性,增強挖掘角色的簡潔性與可解釋性,對于角色工程實踐具有一定的理論參考價值。下一步工作是引入RBAC機制的互斥角色約束思想,進一步增強挖掘結果的可解釋性,以滿足系統(tǒng)對分配給用戶角色數(shù)的約束要求以及職責分離的安全需求。

［1］ Kuhlmann M,ShohatD,SchimpfG.RoleMiningrevealing Business Roles for Security Administration Using Data Mining Technology［C］//Proceedings of the 8th ACM Symposium on Access Control Models and Technologies.Como,Italy:ACM Press,2003:179-186.

［2］ 馬曉普.角色工程中的角色與約束生成方法研究［D］.武漢:華中科技大學,2011.

［3］ 馬曉普,李瑞軒,胡勁緯.訪問控制中的角色工程［J］.小型微型計算機系統(tǒng),2013,34(6):1301-1306.

［4］ Molloy I,Chen Hong,Li Tiancheng,et al.Mining Roles with Semantic Meanings［C］//Proceedings of the 13th ACM Symposium onAccessControlModelsand Technologies.Estes Park,USA:ACM Press,2008:21-30.

［5］ Zhang Dana,Ramamohanarao K,EbringerT.Role Engineering Using Graph Optimization［C］//Proceedings of the 12th ACM Symposium on Access Control Models and Technologies.Sophia Antipolis,France:ACM Press, 2007:139-144.

［6］ Ene A,Horne W,Milosavljevic N,et al.Fast Exact and Heuristic MethodsforRoleMinimization Problems［C］//Proceedings of the 13th ACM Symposium on Access Control Models and Technologies.Estes Park, USA:ACM Press,2008:1-10.

［7］ Vaidya J,Atluri V,Guo Qi.The Role Mining Problem: Finding a Minimal Description Set of Roles［C］// Proceedings of the 12th ACM Symposium on Access Control Models and Technologies.Sophia Antipolis, France:ACM Press,2007:175-184.

［8］ Ma Xiaopu,Li Ruixuan,Lu Zhengding,et al.Mining Constraints in Role-based Access Control［J］.Mathematical and Computer Modelling,2012,55(1): 87-96.

［9］ Kumar R,Sural S,Gupta A.Mining RBAC Roles Under Cardinality Constraint［C］//Proceedings ofthe 6th International Conference on Information Systems Security.Gandhinagar,India:Information Systems Security Press, 2010:171-185.

［10］ Vaidya J,Atluri V,Warner J.RoleMiner:Mining Roles Using Subset Enumeration［C］//Proceedings of the 13th ACM Conference on Computer and Communications Security.Alexandria,USA:ACM Press,2006:144-153.

［11］ Li Ninghui,Tripunitara M V,Bizri Z.On Mutually Exclusive Roles and Separation of Duty［J］.ACM Transactions on Information and System Security,2007, 10(2):42-51.

［12］ Ma Xiaopu,Li Ruixuan,Lu Zhengding.Role Mining Based on Weights［C］//Proceedings of the 15th ACM Symposium on Access Control Models and Technologies.Pittsburgh,USA:ACM Press,2010:65-74.

［13］ Li Ruixuan,Li Huaqing,Wang Wei,et al.Rminer:A Tool Set for Role Mining［C］//Proceedings of the 18th ACM Symposium on Access Control Models and Technologies.Amsterdam,Holland:ACM Press,2013:193-196.

編輯 金胡考

Optimization Method of Role Mining Based on Mutually Exclusive Permissions Constraints

SUN Weia,SU Huib,LI Yanlinga
(a.School of Computer and Information Technology;b.Network Information and Computing Center, Xinyang Normal University,Xinyang 464000,China)

Mining roles in large scale organizations are very redundant and can not reflect system security requirements in existing approaches to bottom-up role engineering.In order to discover optimal roles,this paper proposes an optimization method for role mining,which is based on the enumeration approach to role mining.The method utilizes mutually exclusive permissions constraints to optimize the role mining process by clustering users.It analyzes the correctness of secure constraints by using separation of duty,and cells'values of mining permissions are adjusted in access control matrix.The method mines roles that cover all permissions.Experimental results show that the set of optimal roles can ensure the completeness of role mining.Compared with the enumeration method,the optimization method can reduce the redundancy of roles and ensure system security.

Role-based Access Control(RBAC);role engineering;role mining;role optimization;mutually exclusive permissions constraints;access control matrix

1000-3428(2014)11-0205-06

A

TP309.2

10.3969/j.issn.1000-3428.2014.11.040

國家自然科學基金資助項目(61202194);河南省教育廳科學技術研究基金資助重點項目(13A520765);河南省信息技術教育研究基金資助項目(ITE12192)。

孫 偉(1981-),男,講師、碩士,主研方向:訪問控制,系統(tǒng)安全;蘇 輝,副教授、碩士;李艷靈,副教授、博士。

2013-12-20

2014-02-17E-mail:sw_810715@163.com

中文引用格式:孫 偉,蘇 輝,李艷靈.基于互斥權限約束的角色挖掘優(yōu)化方法［J］.計算工程,2014,40(11):205-210.

英文引用格式:Sun Wei,Su Hui,Li Yanling.Optimization Method of Role Mining Based on Mutually Exclusive Permissions Constraints［J］.Computer Engineering,2014,40(11):205-210.