孫偉　王淑禮

摘 要： 針對現(xiàn)有角色挖掘結(jié)果存在冗余，以及授權(quán)管理在安全性等方面存在的問題，將角色挖掘與授權(quán)查詢分別轉(zhuǎn)化為布爾矩陣分解問題及部分最大可滿足性問題，給出一種基于RBAC的角色挖掘及授權(quán)查詢方法。應(yīng)用實例結(jié)果表明：該方法挖掘的角色集更為簡潔，且具有可解釋性；查詢搜索的角色組合能夠嚴格保證系統(tǒng)的安全性，且滿足授權(quán)的有效性要求。

關(guān)鍵詞： 角色挖掘； 授權(quán)查詢； 布爾矩陣分解問題； 部分最大可滿足性問題

中圖分類號：TP309 文獻標志碼：A 文章編號：1006-8228（2016）11-11-03

Research on role mining and authorization query method based on RBAC

Sun Wei， Wang Shuli

（School of Computer & Informatiion Technology， Xinyang Normal University， Xinyang， Henan 464000， China）

Abstract： Aiming at the problems of redundancy in the existing role mining results， and security in authorization management， etc.， the role mining and authorization query are transformed into the problems of Boolean matrix decomposition and partial maximal satisfiability， and a role mining and authorization query method based on RBAC（Role-Based Access Control）is proposed. The application example shows that the set of optimal roles dug by proposed method is succinct and interpretable； the role's combination of the query and search can strictly guarantee the security of the system， and meet the requirements of the validity of the authorization.

Key words： role mining； authorization querying； Boolean matrix decomposition problem； partial maximal satisfiability problem

0 引言

伴隨著計算機、互聯(lián)網(wǎng)與通信技術(shù)的高速發(fā)展與大規(guī)模應(yīng)用，信息系統(tǒng)的安全性成為越來越突出的問題。作為保證網(wǎng)絡(luò)與信息系統(tǒng)安全的一個重要環(huán)節(jié)，訪問控制機制備受人們關(guān)注?；诮巧脑L問控制（RBAC）已成為當前企業(yè)建立安全應(yīng)用的首選機制。隨著大量非RBAC案例向RBAC系統(tǒng)的大量遷移和成功實施，設(shè)計一個完整、正確的角色集，并構(gòu)建好RBAC系統(tǒng)對于成功實現(xiàn)用戶與權(quán)限的邏輯分離至關(guān)重要。作為構(gòu)建RBAC系統(tǒng)的角色挖掘技術(shù)旨在尋找一組適合的角色來精確地反映系統(tǒng)的功能和安全需求[1]。同時，對于構(gòu)建好的RBAC系統(tǒng)，作為管理與維護RBAC系統(tǒng)的用戶授權(quán)查詢問題旨在尋求在單個會話中激活能覆蓋用戶請求權(quán)限的角色組合，以達到提高系統(tǒng)安全性并保證信息完整性的目的[2]。因此，在傳統(tǒng)訪問控制中如何挖掘簡潔、可用且具有可解釋性的角色集，輔助構(gòu)建RBAC系統(tǒng)并尋求覆蓋盡可能多權(quán)限的合適角色組合，對于角色挖掘方法及授權(quán)查詢問題的研究很具挑戰(zhàn)性，是一項熱點研究課題。

1 相關(guān)研究

自頂向下方法通過對業(yè)務(wù)流程和用戶場景進行專家分析而得到滿足系統(tǒng)功能需求的角色。盡管自頂向下方法定義的角色更加符合實際需求，該方法需要大量專家的參與，耗時費力。自底向上方法從底層的用戶-權(quán)限分配關(guān)系出發(fā)，采用數(shù)據(jù)挖掘技術(shù)自動、快速地構(gòu)建或輔助構(gòu)建RBAC系統(tǒng)。此方法又稱角色挖掘，現(xiàn)已成為角色工程技術(shù)的主要研究方向[3]。對于構(gòu)建好的RBAC系統(tǒng)，授權(quán)管理通過角色實現(xiàn)用戶與權(quán)限的邏輯分離，這已被證明是一種靈活、方便的訪問控制技術(shù)。文獻[4]針對授權(quán)管理中權(quán)限查詢難以計算，提出基于衍生規(guī)則和可達矩陣的兩種查詢方法，但不滿足最小權(quán)限分配要求，且未對角色授權(quán)作進一步研究。文獻[5]通過靜態(tài)互斥角色約束對權(quán)限查詢進行有效約束，支持靈活的角色授權(quán)。文獻[6]針對云計算環(huán)境中授權(quán)管理繁重，提出最小惟一角色集及其求解方法，縮短為用戶授權(quán)角色的時間。然而兩文獻均不滿足動態(tài)互斥角色約束要求。針對現(xiàn)有角色挖掘結(jié)果存在冗余、缺乏可解釋性，以及RBAC授權(quán)管理在安全性、有效性等方面存在的問題，本文將布爾矩陣分解問題與部分最大可滿足性問題的研究相結(jié)合，提出一種基于RBAC的角色挖掘及授權(quán)查詢研究方法。

2 預(yù)備知識與問題描述

沿用標準化RBAC模型的用戶集U、角色集R、權(quán)限集P、用戶-角色關(guān)聯(lián)UA、角色-權(quán)限關(guān)聯(lián)PA，不考慮角色層次和互斥約束。

定義1 布爾矩陣分解問題（BMD）[7]。如果存在A=CX，其中A，C，X均為布爾矩陣，那么稱CX是A的一個布爾分解，即A可布爾分解成C與X。

Basic RMP可以看作是BMD的一個實例，即：將原始UPA分解成UA與PA，以輔助構(gòu)造RBAC相關(guān)配置，同時使q（UA的列數(shù)或PA的行數(shù)）取極小值?？杀硎救缦拢?

?

定義2 部分最大可滿足性問題（Partial MAX-

SAT）的布爾邏輯描述[8]。

⑴ 文字：用布爾變量x1，x2，…，xi，…表示實例中的若干個體元素。對于任意xi，稱xi或xi（xi的邏輯非）為文字。

⑵ 子句：由n個文字通過析取運算符（）連接成形如“x1x2…xn”的實例，稱為子句c。

⑶ 真值指派：用映射函數(shù)（t：{x1，x2，…，xi，…}→

{0，1}）為子句中每一文字賦以真（用1表示）或假（用0表示）。

⑷ 合取范式：由m個子句通過合取運算符（）連接成“c1c2…cm”形式，稱為Partial MAX-SAT的合取范式，用cnf（c1，c2，…，cm）表示。cnf（c1，c2，…，cm）為1，當且僅當每個ci在同一真值指派下均為1。

⑸ 嚴格子句：稱子句c1，c2，…，cm為Partial MAX-

SAT的嚴格子句，是可滿足的，當且僅當存在真值指派，使得cnf（c1，c2，…，cm）為1。所有嚴格子句的集合用HC表示。

⑹ 松弛子句：Partial MAX-SAT中不滿足嚴格子句要求的，稱為松弛子句。所有松弛子句的集合用SC表示。

3 基于RBAC的角色挖掘及授權(quán)查詢

3.1 角色挖掘方法

給出基于布爾矩陣分解的角色挖掘步驟如下。

步驟1 將擁有相同權(quán)限集的用戶群聚成一類。分別選取同一聚類的一個用戶，并暫時去除該聚類的其他冗余用戶，以降低挖掘規(guī)模。

步驟2 基于Fast Miner，將分配給用戶的不同權(quán)限集作為整體視為角色，確立初始角色集。

步驟3 結(jié)合Fast Miner的挖掘結(jié)果，將挖掘問題轉(zhuǎn)化為布爾矩陣分解形式：UPA=UAPA。

步驟4 對于UPA中任意值為0的單元，確定UA中相應(yīng)位置值為0的單元。

步驟5 根據(jù)布爾矩陣乘運算法則，將步驟3得到的分解式進行轉(zhuǎn)置操作，并等價表示成A=CX，其中A表示直接權(quán)限指派的列向量矩陣，C表示算法1中候選角色集的列向量矩陣，X表示待確定用戶指派的列向量矩陣。

步驟6 根據(jù)，進一步確定X中相應(yīng)單元的值（當X的某一行全為0時，去除對應(yīng)的候選角色）。反復(fù)執(zhí)行該步驟，直至候選角色集達到極小化。

3.2 授權(quán)查詢方法

授權(quán)查詢是指尋求在單個會話中激活能覆蓋用戶請求權(quán)限的角色組合，同時遵循動態(tài)互斥角色約束并滿足最小權(quán)限分配要求。動態(tài)互斥角色約束表示為dmer<{r1，r2，…，rm}，t，s>，其中1。其中s∈S，表示單個會話；Plb、Pub分別表示請求權(quán)限下界、上界，且Plb?Pub?P；match∈{min（最小匹配），max（最大匹配），exact（精確匹配）}，表示匹配類型。以下給出基于部分最大可滿足性問題的授權(quán)查詢方法。

步驟1 使用轉(zhuǎn)換規(guī)則將靜態(tài)授權(quán)邏輯和動態(tài)互斥角色約束轉(zhuǎn)化為嚴格子句。

步驟2 采用子句更新算法將滿足不同匹配的請求權(quán)限轉(zhuǎn)化為松弛子句。

步驟3 利用子句編碼及遞歸算法尋求真值指派。

4 實例分析

為了驗證角色挖掘方法的有效性，選用構(gòu)造的數(shù)據(jù)集實例進行分析，并與Fast Miner挖掘結(jié)果進行比較。圖1給出了一個由6個用戶、3個權(quán)限構(gòu)成的原始數(shù)據(jù)集UPA。

首先，通過調(diào)用挖掘算法能夠壓縮數(shù)據(jù)集空間，降低了挖掘規(guī)模，并得到候選角色集：{{p2}，{p1，p2}，{p2，p3}，

{p1，p2，p3}}。結(jié)果如圖2所示。

其次，通過步驟3、步驟4，可以得到初始分解形式，并根據(jù)UPA中值為0的單元，改進初始分解方案如下：

步驟5通過對上述分解式進行整體轉(zhuǎn)置，得到形如A=CX的列向量矩陣等價分解形式：

根據(jù)步驟6的分析可知，X中x21=x32=x43=1，其余單元可取值0或1。然而，由于C4=C2∪C3，將x23，x33取值為1而將x43修改為0，既能保證挖掘的角色覆蓋所有權(quán)限，又使挖掘的角色結(jié)果{r2，r3}達到極小化。因此，與挖掘出{r1，r2，r3，r4}的Fast Miner方法相比，本文方案更易于優(yōu)化，挖掘結(jié)果更簡潔。

5 結(jié)束語

本文將角色挖掘問題轉(zhuǎn)化為布爾矩陣分解問題，通過創(chuàng)建并優(yōu)化候選角色集以滿足基本角色挖掘的要求，并在構(gòu)建的RBAC系統(tǒng)中將授權(quán)查詢問題轉(zhuǎn)化為部分最大可滿足性問題，以尋求合適的角色組合。應(yīng)用實例分析表明，與快速挖掘法相比，本文挖掘的角色結(jié)果更加簡潔，且查詢搜索的角色組合保證了系統(tǒng)的安全性，體現(xiàn)了授權(quán)的有效性。然而，本文方法未能體現(xiàn)RBAC機制的角色勢約束要求，存在局限性。因此，如何限制指派給用戶的角色數(shù)、進一步增強挖掘結(jié)果的可解釋性是下一步需要研究的問題。

參考文獻（References）：

[1] 孫偉，魯駿，李艷靈.一種面向用戶的約束角色挖掘優(yōu)化[J].信

陽師范學(xué)院學(xué)報：自然科學(xué)版，2014.27（4）：589-592，618

[2] ZHANG YUE，JOSHI J B D.Uaq：a framework for user

authorization query processing in RBAC extended with hybrid hierarchy and constraints[C]//Proceedings of the 13th ACM Symposium on Access Control Models and Technologies.New York：ACM Press，2008：83-92

[3] 馬曉普，李瑞軒，胡勁緯.訪問控制中的角色工程[J].小型微型

計算機系統(tǒng)，2013.34（6）：1301-1306

[4] 王婷，陳性元，任志宇.授權(quán)管理中的權(quán)限衍生計算方法[J].計

算機應(yīng)用，2011，31（5）：1291-1294.

[5] 王婷，陳性元，張斌，等.基于互斥角色約束的靜態(tài)職責(zé)分離策

略[J].計算機應(yīng)用，2011，31（7）：1884-1886，1890

[6] 楊柳，唐卓，李仁發(fā)，等.云計算環(huán)境中基于用戶訪問需求的角

色查找算法[J].通信學(xué)報，2011，32（7）：169-175

[7] 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

[8] FU ZHAOHUI，MALIK S.On solving the partial MAX-SAT

problem[C]//Proceedings of the 9th International Conference on the Theory and Application of Satisfiability Testing-SAT 2006. Seattle： IEEE Press，2006：252-265