孫偉　王淑禮

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

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

中圖分類號(hào)：TP309 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

1 相關(guān)研究

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

2 預(yù)備知識(shí)與問(wèn)題描述

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

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

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

?

定義2 部分最大可滿足性問(wèn)題（Partial MAX-

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

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

⑵ 子句：由n個(gè)文字通過(guò)析取運(yùn)算符（）連接成形如“x1x2…xn”的實(shí)例，稱為子句c。

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

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

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

⑸ 嚴(yán)格子句：稱子句c1，c2，…，cm為Partial MAX-

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

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

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

3.1 角色挖掘方法

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)例分析

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)（References）：

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

陽(yáng)師范學(xué)院學(xué)報(bào)：自然科學(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] 馬曉普，李瑞軒，胡勁緯.訪問(wèn)控制中的角色工程[J].小型微型

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

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

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

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

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

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

色查找算法[J].通信學(xué)報(bào)，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