孫偉++魯駿

摘 要：現(xiàn)有自底向上的角色工程方法構(gòu)建過程較繁雜，工程造價高昂。探討幾種角色挖掘算法的基本思想及其優(yōu)缺點(diǎn)。以這些角色挖掘算法為評價對象，以加權(quán)結(jié)構(gòu)復(fù)雜度為評價標(biāo)準(zhǔn)，在真實(shí)數(shù)據(jù)集上對構(gòu)建的RBAC系統(tǒng)狀態(tài)進(jìn)行測試與評價。實(shí)驗(yàn)結(jié)果驗(yàn)證了幾種算法的優(yōu)越性。

關(guān)鍵詞關(guān)鍵詞：角色工程；角色挖掘；評價標(biāo)準(zhǔn)；加權(quán)結(jié)構(gòu)復(fù)雜度

DOIDOI：10.11907/rjdk.161824

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：16727800（2016）011002503

0 引言

基于角色的訪問控制（RBAC）通過角色實(shí)現(xiàn)了用戶與權(quán)限的邏輯分離，是當(dāng)前主流的訪問控制機(jī)制之一[1]。作為構(gòu)建與維護(hù)RBAC系統(tǒng)的角色工程技術(shù)要求設(shè)計(jì)合適的角色集，并為其指派權(quán)限集與用戶集，以精確反映系統(tǒng)功能和安全需求。Kuhlmann等[2]利用數(shù)據(jù)挖掘技術(shù)從

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

1 相關(guān)研究

現(xiàn)有角色挖掘方法按輸出結(jié)果可分為兩類：第一類僅輸出挖掘角色集，不考慮角色層次關(guān)系，這類算法包括Complete Miner（CM）[4]、Fast Miner（FM）[4]；第二類輸出構(gòu)建的系統(tǒng)狀態(tài)，允許存在角色層次，這類算法包括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）

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

1.2 Fast Miner（FM）

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

1.3 ORCA

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

1.4 Graph Optimization（GO）

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

1.5 HP Role Minimization（HPRM）

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

1.6 HP Edge Minimization（HPEM）

首先利用HPRM算法挖掘候選角色集，然后執(zhí)行類似GO算法目標(biāo)函數(shù)對候選角色集進(jìn)行優(yōu)化，直至候選角色集不能被進(jìn)一步優(yōu)化。

1.7 Hierarchical Miner（HM）

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

以上幾種算法的優(yōu)缺點(diǎn)比較如表1所示。

2 基于加權(quán)結(jié)構(gòu)復(fù)雜度的角色挖掘評價

在角色工程領(lǐng)域?qū)BAC系統(tǒng)的構(gòu)建成本記為加權(quán)結(jié)構(gòu)復(fù)雜度。定義給出加權(quán)結(jié)構(gòu)復(fù)雜度，并以此為標(biāo)準(zhǔn)，對角色挖掘構(gòu)建的RBAC系統(tǒng)狀態(tài)進(jìn)行評價。

2.1 加權(quán)結(jié)構(gòu)復(fù)雜度

定義1：原始系統(tǒng)配置ρ。轉(zhuǎn)換RBAC前的原始配置ρ

是一個三元組。其中為U用戶集，P為權(quán)限集，UPA為用戶-權(quán)限分配關(guān)系。

定義2：構(gòu)造系統(tǒng)狀態(tài)γ。轉(zhuǎn)換RBAC后的系統(tǒng)狀態(tài)γ是一個四元組。其中R為角色集，UA為用戶-角色指派關(guān)系，PA為角色-權(quán)限指派關(guān)系，RH為角色層次關(guān)系。

定義3：加權(quán)結(jié)構(gòu)復(fù)雜度（Weighted Structural Complexity，WSC）[8]。給定系統(tǒng)狀態(tài)γ及四元組W=，其中權(quán)重變量wr，wu，wp，wh∈Q+∪{∞}，γ的加權(quán)結(jié)構(gòu)復(fù)雜度用wsc（γ，W）表示為：

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

WSC考慮了系統(tǒng)配置的所有關(guān)系，并為不同關(guān)系設(shè)置了不同的權(quán)重。

2.2 評價方法

角色挖掘評價描述如下：

步驟1：執(zhí)行上述幾種算法，輸出相應(yīng)的系統(tǒng)狀態(tài)γ。

步驟2：以加權(quán)結(jié)構(gòu)復(fù)雜度為評價標(biāo)準(zhǔn)，設(shè)置不同的W，并計(jì)算wsc（γ，W）。

步驟3：對構(gòu)建系統(tǒng)效果進(jìn)行評價。

3 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)選用文獻(xiàn)[9]的數(shù)據(jù)集進(jìn)行測試與評價，實(shí)驗(yàn)前相關(guān)數(shù)據(jù)如表2所示。

3.1 實(shí)驗(yàn)設(shè)置及測試環(huán)境

分別設(shè)置W=<1，0，0，0>、W=<0，1，1，1>。上述幾種不同算法進(jìn)行測試，評價系統(tǒng)狀態(tài)的加權(quán)結(jié)構(gòu)復(fù)雜度。

相關(guān)測試環(huán)境：奔騰雙核E5400CPU 2.70GHz，2GB內(nèi)存，160GB硬盤，Window XP操作系統(tǒng)；在Java中實(shí)現(xiàn)算法，并使用角色挖掘器Rminer。

3.2 結(jié)果分析

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

4 結(jié)語

本文以現(xiàn)有7種不同的角色挖掘研究方法為評價對象，結(jié)合預(yù)置的加權(quán)結(jié)構(gòu)復(fù)雜度，在真實(shí)數(shù)據(jù)集上對構(gòu)建系統(tǒng)進(jìn)行綜合評價。實(shí)驗(yàn)結(jié)果表明，HPRM、HPEM、HM三種算法構(gòu)建系統(tǒng)效果明顯優(yōu)于其它算法，對于角色工程實(shí)踐具有一定理論參考價值。

參考文獻(xiàn)：

[1] 孫偉，李艷靈，周文勇.細(xì)粒度基于傳遞功能的約束委托模型[J].信陽師范學(xué)院學(xué)報(bào)：自然科學(xué)版，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] 孫偉，魯駿，李艷靈.一種面向用戶的約束角色挖掘優(yōu)化[J].信陽師范學(xué)院學(xué)報(bào)：自然科學(xué)版，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.

（責(zé)任編輯：陳福時）