角色工程中一种最小角色集的求解算法

Acquiring Minimal Role Set Algorithm in Role Engineering

角色工程是基于角色访问控制(Role-Based Access Control,RBAC)中的一个重要研究方向,它主要研究角色的获取与优化。目前已有很多关于角色获取与优化的研究,但这些研究所提出的算法要么复杂度较高(NP完全的),要么不能保证优化的效果是最优的。因此,研究建立了一种新的最小角色集求解算法。该算法的时间复杂度是多项式的,而且可以保证优化效果是最优的。首先通过引入代数方法对数据进行预处理,使用极大线性无关组对角色集合进行化简;然后在分析了集合各个运算符特点的基础上,利用概念格模型建立等价类,并最终获得最小角色集。实验结果表明所提算法是有效的。

Role engineering,which focuses on role acquisition and optimization,is an important research area in rolebased access control（RBAC）.Recently,there have been many researches on role acquisition and optimization.However,these researches either have high time-complexity（NP complete）,or cannot guarantee the acquired results optimal.In this paper,we proposed a new algorithm to acquire the optimal（or minimal）role set.Our algorithm has polynomial time complexity,and guarantees to acquire the optimal result.We first pretreated the role set using an algebra measure,and maximum linear independent group was introduced to simplify the role set.And after analyzing the characteristic of every set operator,we built equivalence classes using concept lattice model,and finally attained the optimal role set.The experiment results show that our algorithm is effective.