基于RBAC的角色挖掘及授權查詢方法的研究

孫偉　王淑禮

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

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

中圖分類號：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 引言

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

1 相關研究

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

2 預備知識與問題描述

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

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

Basic RMP可以看作是BMD的一個實例，即：將原始UPA分解成UA與PA，以輔助構造RBAC相關配置，同時使q（UA的列數或PA的行數）取極小值。可表示如下：

?

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

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

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

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

⑶ 真值指派：用映射函數（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的角色挖掘及授權查詢

3.1 角色挖掘方法

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

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

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

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

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

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

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

3.2 授權查詢方法

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

步驟1 使用轉換規則將靜態授權邏輯和動態互斥角色約束轉化為嚴格子句。

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

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

4 實例分析

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

首先，通過調用挖掘算法能夠壓縮數據集空間，降低了挖掘規模，并得到候選角色集：{{p2}，{p1，p2}，{p2，p3}，

{p1，p2，p3}}。結果如圖2所示。

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

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

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

5 結束語

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

參考文獻（References）：

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

陽師范學院學報：自然科學版，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].小型微型

計算機系統，2013.34（6）：1301-1306

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

算機應用，2011，31（5）：1291-1294.

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

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

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

色查找算法[J].通信學報，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