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

doi:10.11896/j.issn.1002-137X.2017.08.021

摘要/Abstract

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

关键词: RBAC,角色工程,最小角色集

Abstract: Role engineering,which focuses on role acquisition and optimization,is an important research area in role-based access control (RBAC).Recently,there have been many researches on role acquisition and optimization.Howe-ver,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.

Key words: Role based access control,Role engineering,Minimal role set

韩道军. 角色工程中一种最小角色集的求解算法[J]. 计算机科学, 2017, 44(8): 115-123. https://doi.org/10.11896/j.issn.1002-137X.2017.08.021

HAN Dao-jun. Acquiring Minimal Role Set Algorithm in Role Engineering[J]. Computer Science, 2017, 44(8): 115-123. https://doi.org/10.11896/j.issn.1002-137X.2017.08.021

参考文献

[1] COYNE E J.Role-engineering[C]∥1st ACM Workshop on Role-Based Access Control.1996.
[2] SANDHU R,COYNE E J.Role based access control models[J].IEEE Computer,1996,29(2):38-47.
[3] ZHANG D,RAMAMOHANRAO K,E BRINGER T.Role Engineering using Graph Optimisation[C]∥Symposium on Access Control Models and Technologies (SACMAT).2007:139-144.
[4] SCHLEGELMILCH J,STEENS U.Role mining with orca[C]∥Symposium on Access Control Models and Technologies (SACMAT).ACM,June 2005.
[5] VAIDYA J,ATLURI V,WARNER J.Role Engineering viaPrioritized Subset Enumeration[J].IEEE Transactions on De-pendable and Secure Computing,2010,7(3):300-314.
[6] MOLLOY I,LI N,LI T,et al.Evaluating role mining algorithms[C]∥Proceedings of the 14th ACM Symposium on Access Control Models and Technologies (SACMAT).2009:95-104.
[7] VAIDYA J,ATLURI V,GUO Q.The Role Mining Problem:Finding a Minimal Descriptive Set of Roles[C]∥Symposium on Access Control Models and Technologies (SACMAT).2007:175-184.
[8] ENE A,HORNE W,MILOSAVLJEVIC N,et al.Fast exact and heuristic methods for role minimization problems[C]∥The ACM Symposium on Access Control Models and Technologies.2008.
[9] COLANTONIO A,DI PIETRO R,OCELLO A,et al.Tamingrole mining complexity in RBAC[J].Computers & Security,2010,9(5):548-564.
[10] MITRA B,SURAL S,VAIDYA J,et al.A Survey of RoleMining[J].ACM Computing Surveys,2016,48(4):1-37.
[11] JAFARIAN J H,TAKABI H,TOUATI H,et al.Towards a General Framework for Optimal Role Mining:A Constraint Sa-tisfaction Approach[C]∥The ACM Symposium.2015:211-220.
[12] WU J W,ZHANG Y,LI R X,et al.Role Updating for Assignments[C]∥Symposium on Access Control Models and Techno-logies.2010:89-98.
[13] AHMED S,OSBORN S L.A system for risk awareness during role mining[C]∥ACM Symposium on Access Control MODELS and Technologies.ACM,2014:181-184.
[14] LU H,VAIDYA J,ATLURI V.Optimal Boolean matrix decomposition:Application to role engineering[C]∥ IEEE Iternational Conference on Data Engineering.IEEE Computer Society,2008:297-306.
[15] LI R,LI H,WANG W,et al.RMiner:a tool set for role mining[C]∥ACM Symposium on Access Control MODELS and Technologies.2013:193-196.
[16] COLANTONIO A,DI PIETRO R,O CELLO A,et al.A formal framework to elicit roles with business meaning in RBAC systems[C]∥Proceedings of the 14th ACM Symposium on Access Control Models and Technologies.2009:85-94.
[17] MA X P,LI R X,LU Z D.Role Mining Based on Weights[C]∥Symposium on Access Control Models and Technologies.Pittsburgh,Pennsylvania,USA,2010:65-74.
[18] WU M Y.Activities and Event-Driven-Based Role Engineering[C]∥2012 Sixth International Conference on Genetic and Evolutionary Computing (ICGEC).IEEE,2012:550-553.
[19] ZHANG L,ZHANG H L,HAN D J,et al.Theory and Algorithm for Roles Minimization Problem in RBAC Based on Concept Lattice[J].Acta Electronica Sinica,2014,2(12):2371-2378.(in Chinese) 张磊,张宏莉,韩道军,等.基于概念格的RBAC模型中角色最小化问题的理论与算法[J].电子学报,2014,2(12):2371-2378.
[20] YU Q Q.Role Hierarchy Mining For Role Based Access Control[D].Harbin:Harbin Institute of Technology,2013.(in Chinese) 蔚清琴.RBAC中分层角色挖掘算法研究[D].哈尔滨:哈尔滨工业大学,2013.
[21] MI X M.Role Mining Algorithm Based on Evoloutionary Algorithms[D].Beijing:Beijing Jiaotong University,2014.(in Chinese) 米秀明.基于进化算法的角色挖掘算法[D].北京:北京交通大学,2014.
[22] YE W.Role Mining and Logical Programming Model in Access Control[D].Wuhan:Huazhong University of Science and Technology,2014.(in Chinese) 叶威.访问控制中的角色挖掘与逻辑编程模型研究[D].武汉:华中科技大学,2014.
[23] FENG D G,ZHANG M,LI H.Big Data Security and Privacy Protection[J].Chinese Journal of Computer,2014,7(1):246-257.(in Chinese) 冯登国,张敏,李昊.大数据安全与隐私保护[J].计算机学报,2014,7(1):246-257.
[24] FANG B X,JIA Y,LI A P,et al.Privacy Preservation in Big Data:A Survey[J].Big Data,2016,2(1):1-18.(in Chinese) 方滨兴,贾焰,李爱平,等.大数据隐私保护技术综述[J].大数据,2016,2(1):1-18.
[25] 北京大学数学系几何与代数教研室代数小组.高等代数(第二版)[M].北京:高等教育出版社.1988:6.
[26] SYROPOULOS A.Mathematics of Multisets[M]∥Multiset Pro-cessing.Spinger Berlin Heidelberg,2000:347-358.
[27] LOEB D.Sets with a negative number of elements[J].Advances in Mathematics,1992,91(91):64-74.
[28] GANTER B,WILLE R.Formal concept analysis:Mathematical foundations[M].Berlin:Springer-Verlag,1999.
[29] ZHANG D,RAMAMOHANARAO K,ZHANG R.Syntheticdata generation for study of role engineering[EB/OL].http://www.cs.mu.oz.au/~zhangd/roledata.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed