王靜宇 吳曉暉

(內(nèi)蒙古科技大學(xué)信息工程學(xué)院 內(nèi)蒙古 包頭 014010)

0 引 言

自底向上的角色工程(Role Engineering)[1]，也被稱為角色挖掘(Role Mining)，它是通過數(shù)據(jù)挖掘的方法對(duì)訪問控制系統(tǒng)現(xiàn)存數(shù)據(jù)中的用戶-權(quán)限之間關(guān)系的進(jìn)行分析，然后自底向上挖掘出可以安全管理系統(tǒng)的角色。這種方法可以半自動(dòng)化或自動(dòng)化地實(shí)現(xiàn)角色的提取和優(yōu)化。目前大數(shù)據(jù)及復(fù)雜的信息系統(tǒng)中提取和優(yōu)化角色是一個(gè)熱點(diǎn)研究問題[2]。

在屬性角色挖掘算法上，傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)存在一些不足之處，它在挖掘過程中常常會(huì)挖掘出大量冗余的屬性角色信息，造成了屬性角色和權(quán)限管理復(fù)雜性的增加。而屬性角色挖掘算法的目標(biāo)就是找出一組最小角色集合能夠安全有效地實(shí)現(xiàn)系統(tǒng)中用戶權(quán)限的分配、刪除和更新等管理，因此如何高效地找到滿足最小權(quán)限原則的最小屬性角色集合成為角色挖掘的一個(gè)重要研究內(nèi)容。目前角色挖掘方面的算法和研究成果已有很多[3-8]，都是NP完全的。20世紀(jì)80年代，德國的Wille教授提出形式概念分析[9](Formal Concept Analysis,FCA),它的核心數(shù)據(jù)結(jié)構(gòu)就是概念格。概念格作為一種工具，由于其具有的一些特點(diǎn)在角色挖掘方面有很大的優(yōu)勢[10]，這方面已有一些重要研究[11-15]。文獻(xiàn)[16]在基于概念格的RBAC模型基礎(chǔ)上，給出了概念格模型上最小角色集、角色約簡、角色替代的定義及相關(guān)定理的證明。為了降低時(shí)間復(fù)雜度，還提出了一種貪婪算法尋找最小角色集。

本文利用概念格的RBAC模型，引入概念格分層的性質(zhì)，將概念格分層的性質(zhì)與角色約簡等定理相結(jié)合，提出一種逐層查找最小角色集的優(yōu)化算法，避免貪婪算法帶來的重復(fù)性計(jì)算，進(jìn)一步提高查找最小角色集算法的時(shí)間性能，降低算法的時(shí)間復(fù)雜度。通過仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。

1 基本概念及性質(zhì)

1.1 概念格

三元組K=(U,M,I)稱為一個(gè)形式背景(簡稱背景)，其中U表示對(duì)象的集合，M表示屬性的集合，I是U與M兩個(gè)集合的笛卡爾積U×M上的二元關(guān)系。(u,m)∈I(或?qū)懽鱱Im)表示對(duì)象u具有屬性m。通常形式背景用一個(gè)矩形的表來表示，它的行表示對(duì)象，列表示屬性。若u行m列的交叉處用數(shù)字1，則表示對(duì)象u擁有屬性m；若u行m列的交叉處用數(shù)字0，則表示對(duì)象u不擁有屬性m。

設(shè)K=(U,M,I)為一個(gè)背景，若A?U,B?M,令：

f(A)={m∈M|?u∈A,(u,m)∈I}

g(B)={u∈U|?m∈B,(u,m)∈I}

如果A、B滿足f(A)=B,g(B)=A，則稱二元組(A,B)是形式概念(簡稱概念)。A是概念(A,B)的外延，B是概念(A,B)的內(nèi)涵。用L(U,M,I)或L(K)表示背景K=(U,M,I)上的所有概念的集合。

設(shè)K=(U,M,I)是一個(gè)形式背景，?A,A1,A2∈U,?B,B1,B2∈M,則有以下性質(zhì)：

性質(zhì)1A1?A2?f(A1)?f(A2)，B1?B2?g(B1)?g(B2)；

性質(zhì)2A?g(f(A))，B?f(g(B))；

性質(zhì)3f(A)=f(g(f(A)))，g(B)=g(f(g(B)))；

性質(zhì)4f(A1)∩f(A2)=f(A1∪A2)，g(B1)∩g(B2)=g(B1∪B2);

性質(zhì)5(g(f(A)),f(A))和(g(B),f(g(B)))都為概念。

設(shè)(A1,B1)和(A2,B2)是形式背景K=(U,M,I)的兩個(gè)概念，若A1?A2(等價(jià)于B2?B1),則稱(A1,B1)是(A2,B2)的特化概念，或(A2,B2)是(A1,B1)的泛化概念。用“≤”符號(hào)表示概念之間的這種特化-泛化關(guān)系為，即(A1,B1)≤(A2,B2)。在形式背景K=(U,M,I)上的所有概念連同特化-泛化關(guān)系構(gòu)成一個(gè)完備格，稱為概念格，記為L(U,M,I)或L(K)。在L(K)中，如果A1?A2，且不存在概念(A3,B3)，使得A1?A3?A2((A1,B1)≤(A3,B3)≤(A2,B2)),則稱(A1,B1)是(A2,B2)的直接子概念，(A2,B2)是(A1,B1)的直接父概念，并記作(A1,B1)<(A2,B2),將直接父概念和直接子概念用線段連接起來就構(gòu)成了概念格的Hasse圖。

對(duì)于一個(gè)對(duì)象u∈U,通常用f(u)代替f({u})來表示對(duì)象u的對(duì)象內(nèi)涵{m∈M|ulm}，g(m)代替g({m})來表示屬性m的屬性外延{u∈U|ulm}。故(g(f(u)),f(u))一定是概念，稱為u的對(duì)象概念。同樣，(g(m),f(g(m)))也一定是概念，稱為m的屬性概念。

1.2 基于概念格的RBAC

訪問控制矩陣的三個(gè)基本要素為主體(用戶)、客體(資源)和操作。列表示主體，行表示客體，矩陣中的列行交叉處表示主體對(duì)客體之間的操作?；诮巧脑L問控制中，用戶表示主體，權(quán)限表示操作與客體(對(duì)象)的二元組，并且引入角色的概念，有以下相關(guān)定義：

1) 用戶集合U(USERS)、角色集合R(ROLES)、權(quán)限集合P(PRMS)；

2) 用戶權(quán)限分配關(guān)系：UPA，將此關(guān)系分為用戶與角色的關(guān)系UA和角色與權(quán)限的關(guān)系PA來表示；

3) 用戶角色分配關(guān)系：UA?U×R,表示多對(duì)多的用戶和角色的對(duì)應(yīng)關(guān)系；

4) 角色權(quán)限分配關(guān)系：PA?R×P,表示多對(duì)多的角色和權(quán)限的對(duì)應(yīng)關(guān)系；

5)pers(r)={p∈P|(r,P)∈PA}表示角色r所擁有的權(quán)限集；

6)PERS(R)={p∈P|r∈R,(r,P)∈PA}表示角色集R所擁有的權(quán)限集。

根據(jù)這種對(duì)應(yīng)關(guān)系，一個(gè)形式背景K=(U,M,IA)就對(duì)應(yīng)于一個(gè)訪問控制矩陣，其中U表示用戶集合，P表示權(quán)限集合，IA?U×P。對(duì)于u∈U,p∈P,(u,p)∈IA表示用戶u擁有權(quán)限p。因此可以用表1的矩形表來表示RBAC模型下的形式背景。形式背景生成的概念格L(K)如圖1所示。

表1 形式背景示例

圖1 表1所示形式背景的概念格Hasse圖

2 最小角色集

2.1 概 念

定義1角色挖掘問題 給定一個(gè)m×n的訪問控制矩陣A(表示用戶-權(quán)限的關(guān)系)，將A分解為大小分別為m×k和k×n的兩個(gè)矩陣UA(表示用戶-角色的關(guān)系)和PA(表示角色-權(quán)限的關(guān)系)，使得k在所有可能的矩陣分解中最小。

在概念格上，由于可以挖出所有可能的角色，并且概念和角色是一一對(duì)應(yīng)的，角色挖掘問題中在訪問控制矩陣A上求解最小角色集的問題就可以等價(jià)于在概念格生成的角色概念集合中求解最小角色概念集的問題。

定義2最小屬性角色概念集 設(shè)形式背景K=(U,M,I)，Sm是形式背景生成的概念格L(K)當(dāng)中的一個(gè)概念集合。如果Sm滿足以下兩個(gè)條件，則稱Sm為訪問控制背景K上的最小屬性角色概念集。

條件1對(duì)于訪問控制背景K中每個(gè)用戶所擁有的權(quán)限，都可以用概念集合Sm中的若干個(gè)概念的內(nèi)涵的并集來表示。

條件2概念集合Sm中的概念個(gè)數(shù)是最小的。

文獻(xiàn)[16]給出了相關(guān)定理及證明：

定理1概念格上所有對(duì)象概念的集合必然滿足定義2最小角色概念集定義中的條件1。

定理2角色集替代具有傳遞性。

定理3設(shè)CS?L(K),C∈L(K),CS是C的所有父概念構(gòu)成的集合，若C不是屬性概念，則C可以用CS來替代。

定理4概念格上由屬性概念誘導(dǎo)的角色集不存在其他替代。

定理5既是屬性概念，也是對(duì)象概念的概念必然包含在最小角色概念集中。

2.2 概念格分層

對(duì)于K=(U,M,I)的形式背景，其生成的概念格為L(K)，a是L(K)中的一個(gè)概念節(jié)點(diǎn)，節(jié)點(diǎn)a的父節(jié)點(diǎn)集合為Sf，則節(jié)點(diǎn)a的層號(hào)值為：

從L(K)的頂點(diǎn)開始遍歷整個(gè)概念格節(jié)點(diǎn)，則L(K)中的每個(gè)節(jié)點(diǎn)的層號(hào)是唯一的。

入度Indegree：該節(jié)點(diǎn)的父節(jié)點(diǎn)數(shù)目。

出度Outdegree：該節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目。

對(duì)于概念格L(K)中的節(jié)點(diǎn)，可以用層號(hào)、入度以及出度來標(biāo)記它，記作(Layer，Indegree，Outdegree)。

如圖1所示的概念格Hasse圖，將它分層并用(Layer，Indegree，Outdegree)標(biāo)記每個(gè)節(jié)點(diǎn)如下：

第0層：1#(0，0，2)。

第1層：2#(1，1，2)，3#(1，1，3)。

第2層：4#(2，1，1)，5#(2，2，2)，6#(2，1，2)，7#(2，1，2)。

第3層：8#(3，2，2)，9#(3，2，1)，10#(3，2，1)。

第4層：11#(4，2，1)，12#(4，1，1)。

第5層：13#(5，4，0)。

性質(zhì)6位于同一層的節(jié)點(diǎn)之間不能相互轉(zhuǎn)化。

性質(zhì)7任一個(gè)第N+1層的節(jié)點(diǎn)，至少被一個(gè)第N層的節(jié)點(diǎn)所覆蓋。

推論1由性質(zhì)6可知，同層節(jié)點(diǎn)之間不存在替代和約簡，故同層節(jié)點(diǎn)可以同時(shí)按層從底向上進(jìn)行替代和約簡。

推論2由定理3及性質(zhì)7可知，只有當(dāng)對(duì)象集合節(jié)點(diǎn)的父節(jié)點(diǎn)大于等于2時(shí)，該節(jié)點(diǎn)才能被其父節(jié)點(diǎn)所替代。

推論3由定理4可知，當(dāng)遇到屬性概念時(shí)就不能在被其他替代，可以找到屬性概念所在的層作為角色替代的終止條件。

3 算法描述

本節(jié)主要描述在概念格中尋找最小概念角色集的算法。首先可以使用任意一種構(gòu)造概念格的方法從形式背景下構(gòu)造出概念格，然后再進(jìn)行最小概念角色集查找算法。

根據(jù)第2節(jié)介紹，算法的主要思想是：首先先遍歷整個(gè)概念格得到層號(hào)值，就可以得到每個(gè)格節(jié)點(diǎn)對(duì)應(yīng)的(Layer，Indegree，Outdegree)標(biāo)記向量； 然后從對(duì)象概念的集合開始，根據(jù)層號(hào)得到算法的起始位置和終止位置，從下到上逐層將集合中滿足條件的角色概念用父概念集合替代；最終得到最小角色概念集。

3.1 概念格分層算法

概念格分層算法如算法1所示，目的是求得概念格各個(gè)節(jié)點(diǎn)的層號(hào)。該算法是根據(jù)經(jīng)典的Bellman-Ford算法(求最短路徑算法)改寫的。首先將輸入的概念格 Hasse圖邊權(quán)值賦予負(fù)值，找到頂點(diǎn)C0賦予零，從頂點(diǎn)開始利用Bellman-Ford算法的原理求出每個(gè)節(jié)點(diǎn)到頂點(diǎn)C0的最長路徑的dist()，這個(gè)值是個(gè)負(fù)值，故取dist()的相反數(shù)得出每個(gè)節(jié)點(diǎn)的層號(hào)；然后得到每個(gè)節(jié)點(diǎn)的標(biāo)記向量(Layer，Indegree，Outdegree)。

算法1概念格分層算法

Function StratificationLattice(L(K))

輸入：概念格L(K)

輸出：每個(gè)節(jié)點(diǎn)的層號(hào)Layer以及標(biāo)記

向量(Layer，Indegree，Outdegree)

BEGIN

1. 查找沒有前驅(qū)節(jié)點(diǎn)的節(jié)點(diǎn)C0為Hasse圖的頂點(diǎn)；

2. Fori=0；i<總節(jié)點(diǎn)數(shù)n；i++；

3.dist(i)=∞

4. END Fori

5. dist(C0)=0；

6. Fori=1，i<總節(jié)點(diǎn)數(shù)n；i++；

7. For 每一條邊e(u,v)；

8. Ifdist(u)+w(u,v)

9.dist(v)=dist(u)+w(u,v)；

10.Layer(v)=-dist(v)；

11. END IF

12. END Fore(u,v)

13. END Fori

14. 為每個(gè)節(jié)點(diǎn)得到標(biāo)記向量(Layer，Indegree，Outdegree)

END

算法1第1～5行找到Hasse圖頂點(diǎn)并初始化每個(gè)節(jié)點(diǎn)到頂點(diǎn)的最長路徑dist()。第6～10行遍歷所有邊得到各節(jié)點(diǎn)的層號(hào)。第8行，若節(jié)點(diǎn)u和節(jié)點(diǎn)v存在vu關(guān)系，則w(u,v)=-1。算法1的時(shí)間復(fù)雜度為O(Ne)，其中N為Hasse圖的總節(jié)點(diǎn)數(shù)，e為Hasse圖的總邊數(shù)。

3.2 查找算法

算法2查找算法描述

Function SearchRole(L(K))

輸入：概念格L(K)；

輸出：最小角色集MinRoleSet

BEGIN

1.ObjSet:={概念格L(K)中的所有對(duì)象概念}；

2.AttSet:={概念格L(K)中的所有屬性概念}；

3.MinRoleSet:=ObiSet∩AttSet

4. 標(biāo)記MinRoleSet中的概念為必選角色概念；

5.CandidateRoleSet:=ObjSet-MinRoleSet；

6. 得到AttSet集合中所有屬性概念的最小層數(shù)Layer1；

7. 得到CandidateRoleSet集合所有對(duì)象概念的最大層數(shù)Layer2；

8. DO

9.RoleSet:=CandidateRoleSet；

10. FOR eachP∈CandidateRoleSet

11. FORLayerC=Layer2,LayerC<=Layer1,LayerC--；

12. IF(P不是屬性概念)AND(IndegreeC>=2)THEN

13. 將P的所有父概念加入CandidateRoleSet,并刪除P；

14.TempSet:=CandidateRoleSet；

15. IFTempSet<=RoleSetTHEN

16.RoleSet:=TempSet；

17. END IF；

18.CandidateRoleSet:=RoleSet；

19. END IF；

20. END FOR；

21. END FOR；

22. 將CandidateRoleSet中的所有概念移至MinRoleSet；

23. ReturnMinRoleSet；

END

查找算法如算法2所示，其中：第1～2行初始化ObjSet和AttSet分別保存對(duì)象概念和屬性概念；第3～4行根據(jù)定理5計(jì)算出必選角色概念，并標(biāo)記必選角色概念然后保存到MinRoleSet集合中；第5行是去除必選角色概念得到待選角色概念集合并保存到CandidateRoleSet集合中；第6～7行得到終止與起始的層數(shù)；第8～21行是對(duì)待選角色集合進(jìn)行角色替代和約簡，直至到達(dá)算法的終止層數(shù)并且找不到更小的角色概念集就結(jié)束算法；第22行將算法找到的最后的結(jié)果保存到MinRoleSet集合中即為最小角色概念集。本算法的時(shí)間復(fù)雜度為O(UP)，其中U表示用戶數(shù)，P表示屬性(權(quán)限)數(shù)。

4 實(shí)驗(yàn)及分析

本文實(shí)驗(yàn)環(huán)境平臺(tái)：硬件是3.0 GHz的CPU和8 GB內(nèi)存，操作系統(tǒng)是Windows 7。實(shí)驗(yàn)主要從時(shí)間復(fù)雜度和準(zhǔn)確度兩方面驗(yàn)證算法的有效性。仿真測試數(shù)據(jù)集是隨機(jī)生成了兩組形式背景數(shù)據(jù)集。為了驗(yàn)證本文優(yōu)化算法的結(jié)果，與文獻(xiàn)[16]的SearchMinRole方法進(jìn)行對(duì)比。

第一組形式背景數(shù)據(jù)集，權(quán)限的數(shù)目不變，都為30，用戶數(shù)目從100到500，每一次間隔20的增加進(jìn)行測試算法的時(shí)間復(fù)雜度和準(zhǔn)確度。此次實(shí)驗(yàn)的目的是觀察用戶數(shù)目增加時(shí)算法的時(shí)間復(fù)雜度和準(zhǔn)確度(真實(shí)的最小角色概念集與算法所找到的最小角色概念集的比例)，并與SearchMinRole方法進(jìn)行對(duì)比。圖2顯示了算法的時(shí)間復(fù)雜度，圖3顯示了算法的準(zhǔn)確度?？梢钥闯觯S著用戶數(shù)目的增加，兩個(gè)算法的時(shí)間復(fù)雜度都呈指數(shù)級(jí)增長，準(zhǔn)確度下降。主要原因是用戶數(shù)目的增加，導(dǎo)致了概念格構(gòu)造時(shí)會(huì)產(chǎn)生大量的概念集合，在進(jìn)行搜索角色替代需要更多的時(shí)間。圖2中，隨著用戶數(shù)目的增多，本文算法比SearchMinRole算法的時(shí)間復(fù)雜度有很大的優(yōu)化，這是由于本文采用層次化的方法，按層進(jìn)行角色替代，避免了SearchMinRole算法迭代帶來的一些重復(fù)性計(jì)算。圖3中，本文的算法與SearchMinRole算法的準(zhǔn)確度大致相同。

圖2 用戶數(shù)目增大時(shí)算法的時(shí)間復(fù)雜度

圖3 用戶數(shù)目增大時(shí)算法的準(zhǔn)確度

第二組形式背景數(shù)據(jù)集，用戶的數(shù)目不變，都為200，權(quán)限數(shù)目以每一次間隔10增加，從10到150進(jìn)行測試算法的時(shí)間復(fù)雜度和準(zhǔn)確度。此次實(shí)驗(yàn)的目的是觀察權(quán)限數(shù)目的變化對(duì)算法的時(shí)間復(fù)雜度和準(zhǔn)確度的影響，并與SearchMinRole方法進(jìn)行對(duì)比。圖4顯示了算法的時(shí)間復(fù)雜度，圖5顯示了算法的準(zhǔn)確度。可以看出，隨著權(quán)限數(shù)目的增加，兩個(gè)算法在時(shí)間開銷方面都呈指數(shù)級(jí)增長，準(zhǔn)確度上升。由于權(quán)限數(shù)目的增加，導(dǎo)致了概念格構(gòu)造時(shí)會(huì)產(chǎn)生大量的概念集合，在進(jìn)行搜索角色替代需要更多的時(shí)間。但是權(quán)限的數(shù)目增多使得概念格的連通性增大，更容易找到最小角色概念集，準(zhǔn)確度就會(huì)提高。圖4中，隨著權(quán)限數(shù)目的增多，本文算法比SearchMinRole算法的時(shí)間復(fù)雜度有很大的優(yōu)化。圖5中，本文的算法與SearchMinRole算法的準(zhǔn)確度大致相同。

圖4 權(quán)限數(shù)目增大時(shí)算法的時(shí)間復(fù)雜度

圖5 權(quán)限數(shù)目增大時(shí)算法的準(zhǔn)確度

由以上兩組實(shí)驗(yàn)結(jié)果分析可知，本文算法是實(shí)用有效的，能夠根據(jù)角色擁有的權(quán)限找到最小的角色概念集，降低復(fù)雜系統(tǒng)中訪問控制策略的管理難度。相比SearchMinRole方法在時(shí)間復(fù)雜度方面有更高的效率。

5 結(jié) 語

本文研究了基于概念格分層的最小角色集算法問題。根據(jù)最小角色集、角色替代和角色約簡的定義及定理，結(jié)合概念格分層的性質(zhì)，提出了一種逐層進(jìn)行角色替代去尋找最小角色集的算法，降低了復(fù)雜系統(tǒng)訪問控制的管理難度，提高了系統(tǒng)安全性。最后通過實(shí)驗(yàn)證明了算法的有效性。

研究利用分層方法構(gòu)造概念格的算法，與本文的查找算法相結(jié)合，進(jìn)一步降低時(shí)間復(fù)雜度是一個(gè)值得研究的工作。另外，用戶數(shù)目過大時(shí)，算法的準(zhǔn)確性會(huì)下降，提高準(zhǔn)確性是下一步的研究方向。