基于概念格分層的角色最小化優化算法

王靜宇 吳曉暉

(內蒙古科技大學信息工程學院 內蒙古 包頭 014010)

0 引 言

自底向上的角色工程(Role Engineering)[1]，也被稱為角色挖掘(Role Mining)，它是通過數據挖掘的方法對訪問控制系統現存數據中的用戶-權限之間關系的進行分析，然后自底向上挖掘出可以安全管理系統的角色。這種方法可以半自動化或自動化地實現角色的提取和優化。目前大數據及復雜的信息系統中提取和優化角色是一個熱點研究問題[2]。

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

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

1 基本概念及性質

1.1 概念格

三元組K=(U,M,I)稱為一個形式背景(簡稱背景)，其中U表示對象的集合，M表示屬性的集合，I是U與M兩個集合的笛卡爾積U×M上的二元關系。(u,m)∈I(或寫作uIm)表示對象u具有屬性m。通常形式背景用一個矩形的表來表示，它的行表示對象，列表示屬性。若u行m列的交叉處用數字1，則表示對象u擁有屬性m；若u行m列的交叉處用數字0，則表示對象u不擁有屬性m。

設K=(U,M,I)為一個背景，若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)的內涵。用L(U,M,I)或L(K)表示背景K=(U,M,I)上的所有概念的集合。

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

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

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

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

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

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

設(A1,B1)和(A2,B2)是形式背景K=(U,M,I)的兩個概念，若A1?A2(等價于B2?B1),則稱(A1,B1)是(A2,B2)的特化概念，或(A2,B2)是(A1,B1)的泛化概念。用“≤”符號表示概念之間的這種特化-泛化關系為，即(A1,B1)≤(A2,B2)。在形式背景K=(U,M,I)上的所有概念連同特化-泛化關系構成一個完備格，稱為概念格，記為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),將直接父概念和直接子概念用線段連接起來就構成了概念格的Hasse圖。

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

1.2 基于概念格的RBAC

訪問控制矩陣的三個基本要素為主體(用戶)、客體(資源)和操作。列表示主體，行表示客體，矩陣中的列行交叉處表示主體對客體之間的操作。基于角色的訪問控制中，用戶表示主體，權限表示操作與客體(對象)的二元組，并且引入角色的概念，有以下相關定義：

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

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

3) 用戶角色分配關系：UA?U×R,表示多對多的用戶和角色的對應關系；

4) 角色權限分配關系：PA?R×P,表示多對多的角色和權限的對應關系；

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

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

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

表1 形式背景示例

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

2 最小角色集

2.1 概 念

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

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

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

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

條件2概念集合Sm中的概念個數是最小的。

文獻[16]給出了相關定理及證明：

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

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

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

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

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

2.2 概念格分層

對于K=(U,M,I)的形式背景，其生成的概念格為L(K)，a是L(K)中的一個概念節點，節點a的父節點集合為Sf，則節點a的層號值為：

從L(K)的頂點開始遍歷整個概念格節點，則L(K)中的每個節點的層號是唯一的。

入度Indegree：該節點的父節點數目。

出度Outdegree：該節點的子節點數目。

對于概念格L(K)中的節點，可以用層號、入度以及出度來標記它，記作(Layer，Indegree，Outdegree)。

如圖1所示的概念格Hasse圖，將它分層并用(Layer，Indegree，Outdegree)標記每個節點如下：

第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)。

性質6位于同一層的節點之間不能相互轉化。

性質7任一個第N+1層的節點，至少被一個第N層的節點所覆蓋。

推論1由性質6可知，同層節點之間不存在替代和約簡，故同層節點可以同時按層從底向上進行替代和約簡。

推論2由定理3及性質7可知，只有當對象集合節點的父節點大于等于2時，該節點才能被其父節點所替代。

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

3 算法描述

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

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

3.1 概念格分層算法

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

算法1概念格分層算法

Function StratificationLattice(L(K))

輸入：概念格L(K)

輸出：每個節點的層號Layer以及標記

向量(Layer，Indegree，Outdegree)

BEGIN

1. 查找沒有前驅節點的節點C0為Hasse圖的頂點；

2. Fori=0；i<總節點數n；i++；

3.dist(i)=∞

4. END Fori

5. dist(C0)=0；

6. Fori=1，i<總節點數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. 為每個節點得到標記向量(Layer，Indegree，Outdegree)

END

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

3.2 查找算法

算法2查找算法描述

Function SearchRole(L(K))

輸入：概念格L(K)；

輸出：最小角色集MinRoleSet

BEGIN

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

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

3.MinRoleSet:=ObiSet∩AttSet

4. 標記MinRoleSet中的概念為必選角色概念；

5.CandidateRoleSet:=ObjSet-MinRoleSet；

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

7. 得到CandidateRoleSet集合所有對象概念的最大層數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分別保存對象概念和屬性概念；第3～4行根據定理5計算出必選角色概念，并標記必選角色概念然后保存到MinRoleSet集合中；第5行是去除必選角色概念得到待選角色概念集合并保存到CandidateRoleSet集合中；第6～7行得到終止與起始的層數；第8～21行是對待選角色集合進行角色替代和約簡，直至到達算法的終止層數并且找不到更小的角色概念集就結束算法；第22行將算法找到的最后的結果保存到MinRoleSet集合中即為最小角色概念集。本算法的時間復雜度為O(UP)，其中U表示用戶數，P表示屬性(權限)數。

4 實驗及分析

本文實驗環境平臺：硬件是3.0 GHz的CPU和8 GB內存，操作系統是Windows 7。實驗主要從時間復雜度和準確度兩方面驗證算法的有效性。仿真測試數據集是隨機生成了兩組形式背景數據集。為了驗證本文優化算法的結果，與文獻[16]的SearchMinRole方法進行對比。

第一組形式背景數據集，權限的數目不變，都為30，用戶數目從100到500，每一次間隔20的增加進行測試算法的時間復雜度和準確度。此次實驗的目的是觀察用戶數目增加時算法的時間復雜度和準確度(真實的最小角色概念集與算法所找到的最小角色概念集的比例)，并與SearchMinRole方法進行對比。圖2顯示了算法的時間復雜度，圖3顯示了算法的準確度。可以看出，隨著用戶數目的增加，兩個算法的時間復雜度都呈指數級增長，準確度下降。主要原因是用戶數目的增加，導致了概念格構造時會產生大量的概念集合，在進行搜索角色替代需要更多的時間。圖2中，隨著用戶數目的增多，本文算法比SearchMinRole算法的時間復雜度有很大的優化，這是由于本文采用層次化的方法，按層進行角色替代，避免了SearchMinRole算法迭代帶來的一些重復性計算。圖3中，本文的算法與SearchMinRole算法的準確度大致相同。

圖2 用戶數目增大時算法的時間復雜度

圖3 用戶數目增大時算法的準確度

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

圖4 權限數目增大時算法的時間復雜度

圖5 權限數目增大時算法的準確度

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

5 結 語

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

研究利用分層方法構造概念格的算法，與本文的查找算法相結合，進一步降低時間復雜度是一個值得研究的工作。另外，用戶數目過大時，算法的準確性會下降，提高準確性是下一步的研究方向。