1、近些年來,基于角色的訪問控制技術(Role-Based Access Control, RBAC)作為一種高效的安全控制策略得到廣泛的關注,特別是在擁有用戶眾多的大型企業(yè)中得到青睞。RBAC策略在簡化訪問控制管理、提高組織效率和增強企業(yè)安全方面為企業(yè)提供了很大的便利。然而很多企業(yè)并不愿采用它,因為對大型企業(yè)來說在企業(yè)系統(tǒng)中配置 RBAC安全策略是一個復雜的系統(tǒng)工程,目前還沒有具體的解決辦法。其中一個重要的同時也是最困難的步驟就是角色工程

2、,角色工程是一系列方法和工具的統(tǒng)稱,目標是根據(jù)企業(yè)的需求來定義和發(fā)現(xiàn)角色以及相關的用戶角色和角色權(quán)限分配關系。目前存在的用于角色工程的方法大體分為兩類:自頂向下方法和自底向上方法。前者是通過分析企業(yè)的業(yè)務流程、組織結(jié)構(gòu)和其他的企業(yè)信息去定義角色和相應的角色授權(quán)關系來配置 RBAC系統(tǒng),因此其時間代價是非常大的,而且該方法還忽略了原本存在的用戶權(quán)限分配關系。為了克服自頂向下方法的缺陷自底向上方法被提出,自底向上的方法是從現(xiàn)存的角色權(quán)限分配

3、關系中抽取出角色,簡稱為角色挖掘。目前對于角色挖掘問題還沒有系統(tǒng)的理論分析,現(xiàn)有的方法只能解決角色挖掘問題中一個或幾個方面的問題,其效率還需進一步提高。因此,對于角色挖掘問題還需要進一步的研究。
　　本文詳細分析角色工程中存在的問題并且研究相應的解決辦法,重點針對角色挖掘中的兩個問題展開,討論問題本身的復雜性和可行的算法。本文首先詳細分析了角色挖掘問題的候選角色集合,并且對于候選角色集合進行了劃分。其次本文重點分析了角色挖掘中的兩

4、個基本問題:最小化角色個數(shù)的角色挖掘問題(簡記為基本角色挖掘問題),即找一個角色個數(shù)最少的角色集合使其恰好覆蓋用戶角色分配關系;使分配關系總和最少的角色挖掘問題(簡記為邊最少角色挖掘問題),該問題是找出一個角色集合恰好覆蓋原來的用戶權(quán)限分配關系并且其用戶角色分配關系和角色權(quán)限分配關系的和最小。本文將證明這兩個問題都可以轉(zhuǎn)化為集合覆蓋問題?；窘巧诰騿栴}可以轉(zhuǎn)化為最小集合覆蓋問題,而邊最少角色挖掘問題可以轉(zhuǎn)化為最小權(quán)重的集合覆蓋問題,從

5、而對于角色挖掘問題解決給出了數(shù)學理論依據(jù)。
　　其次,本文根據(jù)前面的理論分析,通過把角色挖掘問題轉(zhuǎn)化為相應的集合覆蓋問題,給出了基本角色挖掘問題和邊最少角色挖掘問題的貪婪算法。從實驗結(jié)果可以看到基本角色挖掘問題的貪婪算法產(chǎn)生的角色集合與原角色集合的相似度的平均值在90％以上。最后本文還給出一個快速的啟發(fā)式的算法用以解決基本角色挖掘問題,該算法具有多項式的時間復雜度O(n2),而且產(chǎn)生的角色集合與原角色集合的相似度的平均值也在90%