RBAC中角色挖掘算法研究

摘要

近些年来,基于角色的访问控制技术(Role-Based Access Control, RBAC)作为一种高效的安全控制策略得到广泛的关注,特别是在拥有用户众多的大型企业中得到青睐。RBAC策略在简化访问控制管理、提高组织效率和增强企业安全方面为企业提供了很大的便利。然而很多企业并不愿采用它,因为对大型企业来说在企业系统中配置 RBAC安全策略是一个复杂的系统工程,目前还没有具体的解决办法。其中一个重要的同时也是最困难的步骤就是角色工程,角色工程是一系列方法和工具的统称,目标是根据企业的需求来定义和发现角色以及相关的用户角色和角色权限分配关系。目前存在的用于角色工程的方法大体分为两类:自顶向下方法和自底向上方法。前者是通过分析企业的业务流程、组织结构和其他的企业信息去定义角色和相应的角色授权关系来配置 RBAC系统,因此其时间代价是非常大的,而且该方法还忽略了原本存在的用户权限分配关系。为了克服自顶向下方法的缺陷自底向上方法被提出,自底向上的方法是从现存的角色权限分配关系中抽取出角色,简称为角色挖掘。目前对于角色挖掘问题还没有系统的理论分析,现有的方法只能解决角色挖掘问题中一个或几个方面的问题,其效率还需进一步提高。因此,对于角色挖掘问题还需要进一步的研究。
　　本文详细分析角色工程中存在的问题并且研究相应的解决办法,重点针对角色挖掘中的两个问题展开,讨论问题本身的复杂性和可行的算法。本文首先详细分析了角色挖掘问题的候选角色集合,并且对于候选角色集合进行了划分。其次本文重点分析了角色挖掘中的两个基本问题:最小化角色个数的角色挖掘问题(简记为基本角色挖掘问题),即找一个角色个数最少的角色集合使其恰好覆盖用户角色分配关系;使分配关系总和最少的角色挖掘问题(简记为边最少角色挖掘问题),该问题是找出一个角色集合恰好覆盖原来的用户权限分配关系并且其用户角色分配关系和角色权限分配关系的和最小。本文将证明这两个问题都可以转化为集合覆盖问题。基本角色挖掘问题可以转化为最小集合覆盖问题,而边最少角色挖掘问题可以转化为最小权重的集合覆盖问题,从而对于角色挖掘问题解决给出了数学理论依据。
　　其次,本文根据前面的理论分析,通过把角色挖掘问题转化为相应的集合覆盖问题,给出了基本角色挖掘问题和边最少角色挖掘问题的贪婪算法。从实验结果可以看到基本角色挖掘问题的贪婪算法产生的角色集合与原角色集合的相似度的平均值在90％以上。最后本文还给出一个快速的启发式的算法用以解决基本角色挖掘问题,该算法具有多项式的时间复杂度O(n2),而且产生的角色集合与原角色集合的相似度的平均值也在90%以上，与基本角色挖掘问题的贪婪算法产生的结果几乎相同。

目录

RBAC中角色挖掘算法研究

ROLE MINING FOR ROLE BASED ACCESS CONTROL

摘 要

Abstract

第1章 绪 论

1.1课题背景和研究意义

1.2角色工程研究现状

1.3本文主要研究内容

1.4本文结构

第2章 RBAC模型综述与角色工程

2.1 访问控制

2.1.1访问控制矩阵

2.1.2访问控制列表

2.1.3权能表

2.2 RBAC模型综述

2.2.1 RBAC简介

2.2.2 RBAC模型基本概念

2.3角色工程

2.3.1角色工程概述

2.3.2自顶向下方法

2.3.3自底向上方法

2.3.4混合方法

2.4本章小结

第3章 角色挖掘问题形式化定义

3.1角色挖掘问题数据

3.1.1角色挖掘问题数据来源

3.1.2角色挖掘问题数据形式化表示

3.2角色挖掘问题分析

3.2.1挖掘候选角色集合

3.2.2角色挖掘问题的优化目标

3.3本章小结

第4章 角色挖掘问题算法研究

4.1角色挖掘问题转化

4.2角色挖掘问题的贪婪算法

4.2.1 集合覆盖问题的贪婪算法

4.2.2 Basic-RMP 的贪婪算法

4.2.3 Edge-RMP问题的贪婪算法

4.3 Basic-RMP的快速算法

4.3.1 UPA的简化策略

4.3.2 Basic-RMP的快速算法

4.4本章小结

第5章 角色挖掘问题算法实验结果

5.1真实数据集实验及分析

5.1.1真实数据集来源

5.1.2真实数据集实验结果

5.2拟合数据实验及分析

5.2.1拟合数据产生

5.2.2评价标准

5.2.3拟合数据集实验结果

5.3本章小结

结 论

参考文献

攻读硕士学位期间发表的学术论文及其它成果

哈尔滨工业大学学位论文原创性声明及使用授权说明

致 谢