基于布爾矩陣分解的角色極小化挖掘方法
2016-08-18 20:15:29孫偉魯駿
電腦知識與技術(shù) 2016年19期
孫偉 魯駿
摘要：現(xiàn)有自底向上的角色工程方法挖掘結(jié)果存在冗余、缺乏可解釋性。為優(yōu)化角色結(jié)果，結(jié)合基本角色挖掘問題及布爾矩陣分解問題的研究，提出一種基于布爾矩陣分解的角色極小化挖掘方法。該方法使用快速挖掘法創(chuàng)建候選角色集，采用貪心算法進(jìn)一步優(yōu)化候選角色集。應(yīng)用實例結(jié)果表明，該方法挖掘的極小角色集更加簡潔，且具有可解釋性。
關(guān)鍵詞：角色工程；角色挖掘；基本角色挖掘問題；布爾矩陣分解
中圖分類號：TP309 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）19-0215-03
Mining Minimal Role Set Based on Boolean Matrix Decomposition
SUN Wei， LU Jun
（School of Computer & Informatiion Technology， Xinyang Normal University， Xinyang 464000， China）
Abstract： Results of role mining lack interpretability and are very redundant in existing approaches to bottom-up role engineering.In order to discover optimal roles，this paper researches basic role mining problem and boolean matrix decomposition problem，a method of mining minimal role set is proposed.Candidate role set is generated by using fast miner，and the greedy algorithm is applied to optimize the roles.Results of the application example show that，the set of optimal roles is succinct and interpretable.
Key words： role engineering；role mining；basic role mining problem；boolean matrix decomposition
基于角色的訪問控制（RBAC）系統(tǒng)具有操作簡單、可擴(kuò)展性強、管理代價低等優(yōu)點[1]，RBAC是大規(guī)模企業(yè)等組織建立系統(tǒng)應(yīng)用的首選機制。從企業(yè)組織的功能需求出發(fā)，構(gòu)建能準(zhǔn)確反映其功能特征的RBAC系統(tǒng)關(guān)鍵在于設(shè)計合適的角色集。為此，研究者們相繼提出了角色工程技術(shù)以及自頂向下與自底向上兩種基本方法[2，3]。自頂向下方法通過對業(yè)務(wù)流程和用戶場景進(jìn)行專家分析而得到滿足系統(tǒng)功能需求的角色。盡管自頂向下方法定義的角色更加符合實際需求，該方法需要大量專家的參與，耗時費力。與自頂向下的人工處理方式相比，自底向上方法從底層的用戶-權(quán)限分配關(guān)系出發(fā)，采用數(shù)據(jù)挖掘技術(shù)自動、快速地構(gòu)建或輔助構(gòu)建RBAC系統(tǒng)。此方法又稱角色挖掘，現(xiàn)已成為角色工程技術(shù)的主要研究方向[4]。
1 相關(guān)研究
角色挖掘研究方法主要有以下幾類：（1）將用戶-權(quán)限分配關(guān)系的布爾矩陣轉(zhuǎn)化為用戶-角色指派與角色-權(quán)限指派兩個布爾矩陣，以挖掘合適的角色集；（2）RBAC系統(tǒng)的角色實際上是不同權(quán)限組合成的角色集合。將分配給用戶的初始權(quán)限集作為角色，并通過集合交操作可得到新角色；（3）角色看作圖的頂點，頂點所包含的元素表示權(quán)限，角色間的層次關(guān)系看作圖的邊，基于圖論思想進(jìn)行角色挖掘；（4）將分配給不同用戶的權(quán)限集進(jìn)行聚類，基于數(shù)據(jù)挖掘的聚類思想挖掘角色。Vaidya等[5]對基本的角色挖掘問題進(jìn)行了系統(tǒng)的闡述和定義，分析了問題的理論邊界，給出了δ-近似和最小噪聲兩種方法，并指出該問題是NP-難問題。在此基礎(chǔ)上，Vaidya等又提出了邊角色挖掘問題及其求解方法，進(jìn)一步減輕管理員在角色分配和權(quán)限定義方面的負(fù)擔(dān)。Lu等[6]提出了一個角色數(shù)最小化問題的統(tǒng)一建?？蚣?。Ene等[7]提出了把最小角色數(shù)的求解轉(zhuǎn)化為最小biclique覆蓋問題，以尋找最小角色集。Zhang等[8]使用矩陣分解法獲取角色層次圖，再利用圖優(yōu)化技術(shù)以尋找合適的角色集。角色挖掘目標(biāo)是尋找滿足用戶-權(quán)限分配關(guān)系的最小角色集合。然而，在實際系統(tǒng)的構(gòu)建與維護(hù)過程中，以上方法挖掘出的冗余角色將增加系統(tǒng)管理負(fù)擔(dān)，并存在安全隱患。針對該問題，本文將角色挖掘問題轉(zhuǎn)化為布爾矩陣分解問題，提出一種角色極小化挖掘方法，能夠?qū)崿F(xiàn)基本角色挖掘目標(biāo)。
2 預(yù)備知識與問題描述
2.1 角色工程元素
定義1 角色工程元素。沿用標(biāo)準(zhǔn)化RBAC模型的用戶集U、角色集R、權(quán)限集P、用戶-角色關(guān)聯(lián)UA、角色-權(quán)限關(guān)聯(lián)PA，不考慮角色層次和互斥約束。ass_perms（r）、ass_roles（u）分別表示在RBAC系統(tǒng)中指派給角色r的權(quán)限集和指派給用戶u的角色集；ass_perms（u）表示在非RBAC系統(tǒng)中直接指派給用戶u的權(quán)限集。可形式化表示如下：
2.2 基本角色挖掘問題
定義2 基本角色挖掘問題（Basic RMP）[5]。對于給定非RBAC系統(tǒng)中的用戶集U，權(quán)限集P以及用戶-權(quán)限分配關(guān)系UPA，尋找角色集R，用戶-角色指派關(guān)系UA及角色-權(quán)限指派關(guān)系PA，以輔助構(gòu)建RBAC系統(tǒng)，滿足指派給任意用戶的角色集恰好覆蓋該用戶的所有權(quán)限，同時挖掘的角色數(shù)|R|應(yīng)盡可能少?？尚问交硎緸椋?/p>
2.3 布爾矩陣表示法
定義3 布爾矩陣相乘[8]。給定n行k列布爾矩陣C、k行m列布爾矩陣X、n行m列布爾矩陣A，其中用“”表示布爾乘操作符，C與X相乘的結(jié)果為A，表示為CX=A。
若cil、xlj、aij分別表示C、X、A中的單元元素，則布爾矩陣相乘運算應(yīng)滿足：
一個布爾矩陣可以表示成兩個布爾矩陣的乘積，乘積中前一個矩陣表示概念集，后一個矩陣表示如何將目標(biāo)數(shù)據(jù)用概念集合并的形式表示。
（2） A=CXAT=（CX）T AT=X TC T，即將分解前后的矩陣同時轉(zhuǎn)置，分解式仍成立。
2.4 Basic RMP的布爾矩陣表示
對于包含n個用戶、m個權(quán)限、q個角色的RBAC系統(tǒng)，用戶-角色指派關(guān)系可以表示成一個二維布爾矩陣，用UA簡化表示，其中矩陣單元值UA[i][k]表示用戶是否擁有角色；角色-權(quán)限指派關(guān)系也用矩陣PA簡化表示，PA[k][j]表示角色是否擁有權(quán)限；而非RBAC系統(tǒng)的用戶-權(quán)限直接指派關(guān)系也可以表示為矩陣UPA，UPA[i][j]表示用戶是否擁有權(quán)限，形式化表示如下：
3 基于布爾矩陣分解的角色極小化挖掘
角色極小化挖掘方法的基本思想：首先，基于聚類思想并使用快速挖掘法（Fast Miner）創(chuàng)建候選角色集；其次，基于布爾矩陣分解思想，采用貪心算法將候選角色指派給不同用戶，并不斷優(yōu)化候選角色集，以滿足Basic RMP的挖掘要求。以下給出角色極小化挖掘方法的算法描述。
算法1 候選角色集的創(chuàng)建
步驟1 將擁有相同權(quán)限集的用戶群聚成一類。分別選取同一聚類的一個用戶，并暫時去除該聚類的其他冗余用戶，以降低挖掘規(guī)模。
步驟2 基于Fast Miner，將分配給用戶的不同權(quán)限集作為整體視為角色，確立初始角色集。
步驟3 采用集合論的枚舉法，通過二重循環(huán)將任意兩初始角色做交集，創(chuàng)建新角色，并構(gòu)造候選角色集。
算法2 候選角色集的優(yōu)化
步驟1 結(jié)合Fast Miner的挖掘結(jié)果，將挖掘問題轉(zhuǎn)化為布爾矩陣分解形式：UPA=UAPA。
步驟2 對于UPA中任意值為0的單元，確定UA中相應(yīng)位置值為0的單元。
步驟3 根據(jù)布爾矩陣乘運算法則，將步驟1得到的分解式進(jìn)行轉(zhuǎn)置操作，并等價表示成A=CX，其中A表示直接權(quán)限指派的列向量矩陣，C表示算法1中候選角色集的列向量矩陣，X表示待確定用戶指派的列向量矩陣。
步驟4 根據(jù)進(jìn)一步確定X中相應(yīng)單元的值（當(dāng)X的某一行全為0時，去除對應(yīng)的候選角色）。反復(fù)執(zhí)行該步驟，直至候選角色集達(dá)到極小化。
4 實例分析與比較
為了驗證本文方法的有效性，選用構(gòu)造的數(shù)據(jù)集實例進(jìn)行分析，并與Fast Miner挖掘結(jié)果進(jìn)行比較。圖1給出了一個由6個用戶、3個權(quán)限構(gòu)成的原始數(shù)據(jù)集UPA。
首先，通過調(diào)用算法1能夠壓縮數(shù)據(jù)集空間，降低了挖掘規(guī)模，并得到候選角色集：{{p2}，{p1，p2}，{p2，p3}，{p1，p2，p3}}。結(jié)果如圖2所示。
其次，調(diào)用算法2。通過步驟1、步驟2，可以得到初始分解形式，并根據(jù)UPA中值為0的單元，改進(jìn)初始分解方案如下：
步驟3通過對上述分解式進(jìn)行整體轉(zhuǎn)置，得到形如A=CX的列向量矩陣等價分解形式：
根據(jù)步驟4的
5 結(jié)束語
本文提出的角色極小化挖掘方法將角色挖掘問題轉(zhuǎn)化為布爾矩陣分解問題，通過創(chuàng)建并優(yōu)化候選角色集，能夠滿足基本角色挖掘的要求。實例分析表明，與快速挖掘法相比，該方法挖掘的角色結(jié)果更加簡潔，對于角色工程實踐具有一定的理論參考價值。然而，本文方法未能體現(xiàn)RBAC機制的角色勢約束要求，存在局限性。因此，如何限制指派給用戶的角色數(shù)、進(jìn)一步增強挖掘結(jié)果的可解釋性是下一步需要研究的問題。
參考文獻(xiàn)：
[1] 孫偉，李艷靈，周文勇.細(xì)粒度基于傳遞功能的約束委托模型[J].信陽師范學(xué)院學(xué)報：自然科學(xué)版，2013，26（3）：442-445.
[2] 馬曉普，李瑞軒，胡勁緯.訪問控制中的角色工程[J].小型微型計算機系統(tǒng)，2013，34（6）：1301-1306.
[3] 孫偉，魯駿，李艷靈.一種面向用戶的約束角色挖掘優(yōu)化[J].信陽師范學(xué)院學(xué)報：自然科學(xué)版，2014，27（4）：589-592，618.
[4] Molloy I，Li Ning-hui，Li Tian-cheng，et al.Evaluating role mining algorithms[C]//Proceedings of the 14th ACM Symposium on Access Control Models and Technologies.New York：ACM Press，2009：95-104.
[5] 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：ACM Press，2007：175-184.
[6] Lu Hai-bing，Vaidya J，Atluri V.Optimal boolean matrix decomposition：application to role engineering[C]//Proceedings of the 24th International Conference on Data Engineering.Cancun：IEEE press， 2008：297-306.
[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：1-10.
[8] Zhang Dana，Ramamohanarao K，Ebringer T.Role engineering using graph optimisation[C]//Proc. of the 12th ACM Symposium on Access Control Models and Technologies.Sophia Antipolis：ACM Press，2007：139-144.
