基于加權結構復雜度的角色挖掘評價

孫偉++魯駿

摘 要：現有自底向上的角色工程方法構建過程較繁雜，工程造價高昂。探討幾種角色挖掘算法的基本思想及其優缺點。以這些角色挖掘算法為評價對象，以加權結構復雜度為評價標準，在真實數據集上對構建的RBAC系統狀態進行測試與評價。實驗結果驗證了幾種算法的優越性。

關鍵詞關鍵詞：角色工程；角色挖掘；評價標準；加權結構復雜度

DOIDOI：10.11907/rjdk.161824

中圖分類號：TP301

文獻標識碼：A 文章編號文章編號：16727800（2016）011002503

0 引言

基于角色的訪問控制（RBAC）通過角色實現了用戶與權限的邏輯分離，是當前主流的訪問控制機制之一[1]。作為構建與維護RBAC系統的角色工程技術要求設計合適的角色集，并為其指派權限集與用戶集，以精確反映系統功能和安全需求。Kuhlmann等[2]利用數據挖掘技術從

原始系統配置中提取角色，用于構建RBAC系統。此方法又稱角色挖掘，因其具有自動、快速的特點而備受關注[3]。為充分體現RBAC系統管理方便、操作簡單的特點，首先需要定義一個完整、正確的角色集。然而，現有利用矩陣分解法、子集枚舉法、圖優化法、概率模型法、最小干擾法等構建RBAC系統代價高昂。本文以現有7種不同的角色挖掘方法為研究對象，結合加權結構復雜度，對其構建的系統進行多方位評價。

1 相關研究

現有角色挖掘方法按輸出結果可分為兩類：第一類僅輸出挖掘角色集，不考慮角色層次關系，這類算法包括Complete Miner（CM）[4]、Fast Miner（FM）[4]；第二類輸出構建的系統狀態，允許存在角色層次，這類算法包括ORCA[5]、Graph Optimization（GO）[6]、HP Role Minimization（HPRM）[7]、HP Edge Minimization（HPEM）[7]、Hierarchical Miner（HM）[8]。7種角色挖掘算法基本思想如下：

1.1 Complete Miner（CM）

將分配給用戶的不同權限集視為初始角色，對任意兩個不同的初始角色作交集運算，產生新角色，將其添進初始角色集，并在此角色集中作交運算以尋找新角色。重復上述過程直至不再產生新角色。該算法運用集合論的枚舉法，窮舉權限集合的所有可能，時間復雜度為O（2|InitRoles|），其中|InitRoles|為初始角色的個數。

1.2 Fast Miner（FM）

按照分配給用戶的不同權限集形成初始角色集，并將得到的角色集作交集運算以產生新的角色集。FM和CM 的不同之處在于 FM 新產生的角色不再參與交集運算，時間復雜度降為O（|InitRoles|2）。其中|InitRoles|為初始角色的個數。

1.3 ORCA

基于數據挖掘的聚類算法思想，首先設定每個權限對應一個角色，也就是一個簇，其次選擇兩個簇進行合并。重復上述過程直至剩下一個簇或者簇的數目滿足用戶要求。ORCA 最終得到的凝聚層次樹可以在某一層進行分割，得到的狀態即為ORCA 的一個角色狀態。

1.4 Graph Optimization（GO）

將分配給每個用戶的權限集作為初始角色，給出優化目標函數，按目標函數對初始角色集進行優化。GO算法分為以下4種情況：①兩個角色的權限集相同，刪除一個角色并將該角色的用戶集添加到另外一個角色的用戶集中；②兩個角色的權限集相交，形成一新角色，其權限集是兩個相交角色的共有權限組合，其用戶集是兩個角色的用戶之和，并在原角色和新角色之間添加一條角色層次線；③兩個角色中其中一角色的權限集包含另一個角色的權限集，在包含到被包含角色之間添加一條角色層次線；④兩個角色的權限集之間沒有任何關系，不進行任何操作。

1.5 HP Role Minimization（HPRM）

首先選擇一用戶，查看其它用戶是否包含當前用戶的所有權限，并將得到的用戶集合和當前用戶的權限集合并成一角色；其次，從用戶-權限分配關系中刪除相應用戶的當前權限集；最后，進行下一次迭代，直至用戶-權限分配關系被挖掘角色集完全覆蓋。

1.6 HP Edge Minimization（HPEM）

首先利用HPRM算法挖掘候選角色集，然后執行類似GO算法目標函數對候選角色集進行優化，直至候選角色集不能被進一步優化。

1.7 Hierarchical Miner（HM）

首先，利用形式概念得出初始形式概念格；其次，處理繼承中的包含關系以簡化概念格形式；再次，在存在復合角色的情況下，若刪除復合角色后的目標函數值比刪除前的目標函數值小，則需要刪除復合角色；最后，重復刪除復合角色直至目標函數值不再減少。

以上幾種算法的優缺點比較如表1所示。

2 基于加權結構復雜度的角色挖掘評價

在角色工程領域將RBAC系統的構建成本記為加權結構復雜度。定義給出加權結構復雜度，并以此為標準，對角色挖掘構建的RBAC系統狀態進行評價。

2.1 加權結構復雜度

定義1：原始系統配置ρ。轉換RBAC前的原始配置ρ

是一個三元組。其中為U用戶集，P為權限集，UPA為用戶-權限分配關系。

定義2：構造系統狀態γ。轉換RBAC后的系統狀態γ是一個四元組。其中R為角色集，UA為用戶-角色指派關系，PA為角色-權限指派關系，RH為角色層次關系。

定義3：加權結構復雜度（Weighted Structural Complexity，WSC）[8]。給定系統狀態γ及四元組W=，其中權重變量wr，wu，wp，wh∈Q+∪{∞}，γ的加權結構復雜度用wsc（γ，W）表示為：

wsc（γ，W）= wr×|R|+wu×|UA|+wp×|PA|+wh×|RH|

WSC考慮了系統配置的所有關系，并為不同關系設置了不同的權重。

2.2 評價方法

角色挖掘評價描述如下：

步驟1：執行上述幾種算法，輸出相應的系統狀態γ。

步驟2：以加權結構復雜度為評價標準，設置不同的W，并計算wsc（γ，W）。

步驟3：對構建系統效果進行評價。

3 實驗與結果分析

實驗選用文獻[9]的數據集進行測試與評價，實驗前相關數據如表2所示。

3.1 實驗設置及測試環境

分別設置W=<1，0，0，0>、W=<0，1，1，1>。上述幾種不同算法進行測試，評價系統狀態的加權結構復雜度。

相關測試環境：奔騰雙核E5400CPU 2.70GHz，2GB內存，160GB硬盤，Window XP操作系統；在Java中實現算法，并使用角色挖掘器Rminer。

3.2 結果分析

表3、表4分別給出了不同W下系統狀態的評價值?？梢钥闯?，后三種算法（HPRM，HPEM，HM）構建系統效果明顯優于其它算法。

4 結語

本文以現有7種不同的角色挖掘研究方法為評價對象，結合預置的加權結構復雜度，在真實數據集上對構建系統進行綜合評價。實驗結果表明，HPRM、HPEM、HM三種算法構建系統效果明顯優于其它算法，對于角色工程實踐具有一定理論參考價值。

參考文獻：

[1] 孫偉，李艷靈，周文勇.細粒度基于傳遞功能的約束委托模型[J].信陽師范學院學報：自然科學版，2013，26（3）：442445.

[2] KUHLMANN M，SHOHAT D，SCHIMPF G.Role miningrevealing business roles for security administration using data mining technology[C].Proceedings of the 8th ACM Symposium on Access Control Models and Technologies.Como：ACM Press，2003：179186.

[3] 孫偉，魯駿，李艷靈.一種面向用戶的約束角色挖掘優化[J].信陽師范學院學報：自然科學版，2014，27（4）：589592，618.

[4] VAIDYA J，ATLURI V，WARNER J.RoleMiner：mining roles using subset enumeration[C].Proc. of the 13th ACM Conference on Computer and Communications Security.Alexandria：ACM press，2006：144153.

[5] SCHLEGELMILCH J，STEFFENS U.Role mining with ORCA[C].Proceedings of the 10th ACM Symposium on Access Control Models and Technologies.New York：ACM Press，2005：168176.

[6] ZHANG DANA，RAMAMOHANARAO K，EBRINGERT.Role engineering using graph optimisation[C].Proc. of the 12th ACM Symposium on Access Control Models and Technologies.Sophia Antipolis：ACM Press，2007：139144.

[7] ENE A，HORNE W，MILOSAVLJEVIC N，et al.Fast exact and heuristic methods for role minimization problems[C].Proc. of the 13th ACM Symposium on Access Control Models and Technologies.Estes Park：ACM Press，2008：110.

[8] MOLLOY I，CHEN H，LI T C，et al.Mining roles with semantic meanings[C].Proceedings of the 13th ACM Symposium on Access Control Models and Technologies.Estes Park：ACM Press，2008：2130.

[9] MOLLOY I，LI NINGHUI，LI TIANCHENG，et al.Evaluating role mining algorithms[C].Proceedings of the 14th ACM Symposium on Access Control Models and Technologies.Stresa：ACM Press，2009：95104.

（責任編輯：陳福時）