概念格在访问控制中的研究综述

张磊 张宏莉

摘 要： 随着信息技术的发展，信息系统日趋复杂和多样化，这给访问控制的设计和维护提出了更高的要求。概念格作为一种重要的数据挖掘和知识发现方法，具有自动聚类和自动构建层次的特点，可以用于设计和维护一个访问控制所需要的层次结构。本文对概念格在强制访问控制和基于角色的访问控制中的相关研究进展进行了分析和总结，并对未来的研究趋势进行了讨论。

关键词： 形式概念分析； 概念格； 访问控制

中图分类号： TP309 文献标识号：A 文章编号：2095-2163（2014）06-

Abstract： With the development of information technology， information system has become increasingly complex and diverse. This brings higher requirements to the design and maintain of access control. As an important method of data mining and knowledge discovery， concept lattices have the property of automatic clustering and constructing hierarchy， and can be used to design and maintain a hierarchy required by an access control system. In this paper， research progress of concept lattices in mandatory access control and access control based on roles is analyzed and summarized， and the future research trend is prospected.

Keywords： Formal Concept Analyses； Concept Lattice； Access Control

0引 言

形式概念分析理论由德国的Wille R.教授于1982年首次提出[1]。该理论源于哲学范畴中的“概念”，每个“概念”分为内涵和外延两部分：内涵是事物的某些属性的集合，而外延就是具有这些属性的事物对象的集合。概念间的包含关系等价于外延和内涵的包含关系。从数学的角度来看，概念间的包含关系是一种偏序关系，其产生的完全格，就是概念格。由概念格上的偏序关系生成的Hasse图，能够反映概念的层次结构，生动简洁地体现了概念之间的泛化—例化关系。现实世界的各种事物或信息大都可以比较容易地表示成一个对象或实例具有某些属性或特征的关系。在形式概念分析中，这种对象-属性间的二元关系即可称为形式背景。将形式背景生成为概念格的过程则将称为概念格构造。

概念格被认为是进行数据分析的有力工具，在诸多领域得到了研究和应用，如信息检索[2-4]、数据挖掘和知识发现[5-6]、社交网络[7-8]、生物信息学[9-11]、本体构建等[12]。

在信息安全领域，有学者利用概念格的层次分类和聚类能力对各种安全信息进行归类分析。例如，Sarmah等人[13]使用语言学和形式概念分析构建形式化模型进行安全模式的分类；Alvi等人[14]在综合比较了已有的23种安全模式分类方法之后，认为该方法具有通用性、导航性、完备性、可接受性、互排他性、可重复性、无歧义性等特点。Breier等人[15]用形式概念分析描述各个安全属性，来对系统的安全控制进行离散尺度的评估。Jang等人[16]利用形式概念分析来统一描述个人信息的隐私保护系统，能够计算信息的敏感级并进行分类以避免没有用户授权情况下隐私数据的泄露风险。Priss[17]提出了一种基于形式概念分析的Unix系统监控方法。该方法不需要提前知道事件性质再去搜索分析，而是能够将所有的事件数据分析归类。

概念格具有数学上的完备性，同时能够自动化地将数据聚类为概念、并建立概念层次模型。访问控制本身也具有层次化和主客体分组归类的要求，因此概念格成为访问控制研究的一个重要研发工具。大多数学者都利用概念格的自动聚类特点来实现访问控制的某些自动计算要求，如自动建立角色或安全类的层次结构、自动寻找安全约束、自动发现安全类或角色等等。

1 强制访问控制

强制访问控制模型只允许信息在低级和高级之间单向流动或同级间流动，也即按格的偏序关系流动。因此强制访问控制模型满足数学上格的定义，往往是一种格模型，例如Biba模型[18]、BLP模型[19]等。而概念格在数学上满足完备格的定义，形式背景中的对象和属性正好对应于访问控制矩阵，形式概念对应于安全类，概念间的偏序关系恰好是安全类的偏序关系。因此利用概念格对强制访问控制具有很强的表示能力。

概念格在强制访问控制方面的研究主要有两类：一类主要利用概念格的自动聚类能力构建信息流动的偏序关系，来实现自动化的强制访问控制能力。如Sakuraba等人[20]将形式概念分析应用到文件服务器组中来实现强制访问控制。该方法首先将安全策略映射为形式背景，又将安全类映射为形式概念，由此然后直接从安全策略中产生例如用户访问点等相关配置参数，构成访问策略的安全概念格。该方法还能通过将文件服务器映射到安全类或角色，来实现面向信息流控制的强制访问控制和基于角色的访问控制。

另一类主要利用概念格的相关理论工具来实现强制访问控制的强制约束和验证，以对系统开发人员提供辅助。例如Obiedkov等人在文献[21]中指出形式概念分析理论的属性探索能够强制系统开发人员考虑研究中可能会忽视的问题，并在文献[22]中对基于属性探测的强制访问控制模型进行了进一步的讨论，认为该方法可以使系统设计者更好地理解不同安全类之间的依赖。

2 基于角色的访问控制

当前信息系统的复杂性对RBAC模型提出了更高的要求。在RBAC模型中，角色的设定对权限管理的安全性和易操作性有重要的影响。因此寻找适合系统功能要求的角色及其对应的权限，是关系到RBAC系统合理性和安全性的一个关键工作。随着信息技术的发展，信息系统日趋复杂和多样化，访问控制中的用户、资源和权限日益增多，而信息系统业务流程以及涉及到的领域知识日趋复杂，这就使得设计和管理一个符合用户对功能和安全需求的RBAC系统变得越来越困难。为了应对当前信息系统对访问控制的复杂性要求，自动化原则[23]已经公认为即是下一代RBAC模型的五大原则之一。目前角色工程的研究主要集中于自动化的角色工程方法。

如表1、表2和图1所示（具体地，图1中左侧图形即为概念格），概念格模型与RBAC模型存在严格的对应关系[24]： 用户对应于形式背景的对象，权限对应于属性，形式概念对应于角色，Hasse图对应于角色间的层次关系。利用概念格来进行RBAC模型的研究有着极大的便利性。目前的研究主要用于支持RBAC模型的角色工程方法，大体上可以分为角色挖掘、约束生成、角色分配和角色维护四个方面。

2.1 角色挖掘

基于概念格的角色挖掘研究主要是利用概念格的自动聚类和层次模型来发现新的角色以及构建角色的层次结构。Sobieski等人[24]首先系统性地提出利用概念格与RBAC模型对应关系来进行构建RBAC层次模型，研究首先建立了RBAC模型和概念格模型的映射关系，然后提出了一个利用概念格从访问控制矩阵中发现角色并建立角色的层次结构的方法，最后阐明该方法能够判定系统的安全度并发现越权的恶意登陆。Kumar[25]进一步利用形式概念分析的格的性质，对RBAC模型中的各种角色的访问权限进行建模。首先将三维的RBAC矩阵转化为一个动态的安全背景。在此背景上，访问权限是属性而交叉积为角色，数据项为对象。最终将访问权限以格结构的形式展示并获得权限上的依赖关系。

基于概念格的角色挖掘技术不仅可以用于新建或移植RBAC系统，也能用于对已有信息系统的角色进行逆向工程。这是由于概念格具有聚类和层次化的特点，能够对软件模块中的结构进行良好的导航和显示。例如，Gauthier等人在文献[26]中提出了一个软件逆向工程中利用形式概念分析来对访问控制模型的理解和可视化提供支持的方法，该方法能够抽取角色-权限关系、发现潜在角色并绘制角色层次视图，同时还能够发现错误的权限、提供角色定制的用户交互接口。

角色挖掘的核心问题有两个，一个是准确地反映系统安全需求，另一个是最高限的方便管理。在具体的角色挖掘研究中，主要目标是挖掘出的角色需尽可能地符合商业意义，以及挖掘出的角色及其层次结构还要尽可能地简单。而且基于概念格的角色挖掘方法与RBAC模型有着天然的对应关系，因而相关方面的研究已然取得了突出的成果。Molloy等人[27-28]指出层次RBAC系统的挖掘问题与形式概念分析紧密相关，并提出了一个基于形式概念分析的角色挖掘方法。该方法把挖掘到的角色层次的权重结构复杂度（weighted structural complexity）作为最小代价函数，并以此来评判挖掘出的角色是否符合预定义参数的优化目标要求，同时也给出了一个基于概念格的贪婪算法HierarchicalMiner（HM）来降低角色发现的时间复杂度。算法中，将每个角色视作一个形式概念，其外延为角色对应的用户，而内涵则为角色对应的权限，约简后的概念格即为角色的层次结构。该方法能够挖掘出有意义的角色信息。继而。文献[29]又对已经存在的各种角色挖掘方法进行对比后指出，该方法能够找出权重结构复杂度最低的RBAC角色层次结构，并且研究产生的角色也都有着实际的商业意义。

2.2 约束生成

约束是RBAC模型中的一组强制性规则，是RBAC系统安全的一个重要组成部分，确保相关安全管理人员的操作能够被执行或者被禁止。例如角色互斥约束、基数约束、职责分离原则、时间约束等等。作为一个经典的知识发现和机器学习方法，概念格的相关理论能够为RBAC模型中的约束发现提供更可靠的手段。国内外的学者主要利用形式概念分析的属性探测对未知约束进行探测，同时利用概念格的完备性特点进行验证。例如Frithjof Dau 和Martin Knechtel[30]应用描述逻辑（Description Logics，DLs）来形式化RBAC模型，然后使用基于形式概念分析的属性探测方法系统地找到非计划中的含义并且获得约束，后又将其显示化。进一步地，Knechtel 在文献[31]中系统地介绍了如何利用形式概念分析的属性探测方法来从RBAC矩阵中找出RBAC模型的约束条件。Kumar在文献[32]中利用了形式概念分析理论的格和偏序的特性，把传统的表示角色访问权限的安全背景延伸为一个动态的形式背景，而在此形式背景上执行形式概念分析的属性探索，并且又将该方法用于一个医疗ad hoc网络，应用后的综合分析表明该方法能够满足RBAC的静态职责分离约束和角色层次的要求。

2.3 角色分配

在传统的信息系统中，用户的角色和权限赋值通常由人工完成。而在复杂信息系统或一些信息网络应用中，完全的人工操作无法应对数量庞大的角色分配任务和随时变化的访问请求，这给系统管理带来了一定的安全隐患。针对这一问题，韩道军等人[33]提出了一种利用概念格将角色权限和属性进行关联分析的模型，根据用户属性将满足需求的角色自动分配给新用户。贾笑明等人[34]则提出了一种基于概念格的角色评估模型，来应对RBAC模型中人工对角色进行分配权限导致的人力成本过高及分配结果不合理的情况。

移动服务的推荐也可以看做是一个用户的角色分配问题。在移动环境中，服务推荐必须依赖上下文环境。因为上下文数据是多级的，并不断在变化和重新配置，因此通常从上下文数据中挖掘特征然后进行归类，进而能够快速且自动地给移动用户推荐所需要的服务[35]。利用角色来代表具有相同兴趣或抽象特征的用户组，可以把移动服务的推荐问题转化为用户的角色分配问题。

除了经典的访问控制需要进行角色分配，在一些新型的计算模型和应用中也存在类似的角色分配问题。例如，在移动互联网中，为移动用户推荐适合的服务也通常被研究人员看做是一个角色分配问题。通常的角色挖掘方法只考虑两个维度的参数（用户，权限），而并不关心上下文感知问题。Wang等人在文献[36]中提出了一个上下文感知的角色挖掘方法，他们利用概念格创建角色树然后进行角色挖掘，自动地将用户按照他们的兴趣、习惯归类分组，并在此基础上进行移动服务的推荐。

2.4 角色更新

在复杂信息系统中由人工对角色进行更新，增加、删除或修改角色的权限，均会带来极大的管理复杂性。由于概念格与RBAC模型存在一一对应关系，当主体和客体的权限发生变化时，可以利用概念格的渐进式构造对角色进行动态调整，从而完成角色的自动维护工作。例如，何云强等人[37]针对复杂信息系统中权限管理由人工操作的安全隐患问题，将概念格模型引入到角色访问控制中，提出了一种自动化的权限管理方法，为系统管理人员的操作提供辅助支持。

3 讨论与展望

概念格的自动聚类等特点，使得其在访问控制中一些自动化构建和维护的问题上得到了很好的应用。随着信息系统的飞速发展，云计算和物联网等新兴计算模型的出现，给访问控制的深入研究和发展带来了新的问题，而同时却也给概念格在访问控制中的进一步深入研究和广泛讨论带来了新的机遇。

（1） 云计算环境中的访问控制。在云计算环境中，访问控制策略所在的服务器是不可信的。由此产生的基于属性的加密等新型的细粒度访问控制策略中，依然需要层次化的加密和访问控制模型[38]。如何利用概念格的自动聚类技术，与这些新型的访问控制方法相结合，是一个值得关注的研究方向。

（2）分布式环境中的访问控制。协同工作和跨域访问是分布式系统的两大特点。由此出现了基于团队的访问控制模型、基于域的访问控制模型等分布式的访问控制模型。概念格的分布式存储模型[39]，能够实现概念格的分布式存储和计算，并将概念格的分布式模型结合分布式的访问控制特点，从而实现分布式环境下的访问控制自动聚类和层次构造，因此也是一个值得探索的研究方向。

（3）基于时态的访问控制。在大多数信息系统中，访问控制与时间因素紧密相关，用户只能在某个特定时间段具有某些权限。而概念格由于其离散性特点，自身对时间等非离散变量建模能力比较弱。对此类访问控制的自动化层次构建则有赖于对概念格模型的进一步拓展研究。

参考文献

[1] Ganter B， Wille R. Formal Concept Analysis： Mathematical Foundations[M]. Berlin： Springer， 1999.

[2] PENG Qiangqiang， DU Yajun， HAI Yufeng， et al. Topic-specific crawling on the Web with concept context graph based on FCA[C]//Proceedings of International Conference on Management and Service Science， Wuhan， China： IEEE， 2009： 1-4.

[3] De MAIO C， FENZA G， LOIA V， et al. Hierarchical web resources retrieval by exploiting Fuzzy Formal Concept Analysis[J]. Information Processing & Management， 2012， 48（3）： 399-418.

[4] POELMANS J， IGNATOV D， VIAENE S， et al. Text mining scientific papers： a survey on FCA-based information retrieval research[J]. Advances in Data Mining. Applications and Theoretical Aspects， 2012： 273-287.

[5] POELMANS J， ELZINGA P， VIAENE S， et al. Formal concept analysis in knowledge discovery： a survey[J]. Conceptual Structures： From Information to Intelligence， 2010： 139-153.

[6] GUPTA A， BHATNAGAR V， KUMAR N. Mining closed itemsets in data stream using formal concept analysis[J]. Data Warehousing and Knowledge Discovery， 2010： 285-296.

[7] STATTNER E， COLLARD M. Social-based conceptual links： Conceptual analysis applied to social networks[C]// 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining （ASONAM）. IEEE， 2012： 25-29.

[8] KIM H L， BRESLIN J G， DECKER S， et al. Mining and representing user interests： The case of tagging practices[J]. Systems， Man and Cybernetics， Part A： Systems and Humans， IEEE Transactions on， 2011， 41（4）： 683-692.

[9] KAYTOUE M， DUPLESSIS S， KUZNETSOV S， et al. Two fca-based methods for mining gene expression data[J]. Formal Concept Analysis， 2009： 251-266.

[10] KAYTOUE M， KUZNETSOV S O， NAPOLI A， et al. Mining gene expression data with pattern structures in formal concept analysis[J]. Information Sciences， 2011， 181（10）： 1989-2001.

[11] AMIN I I， KASSIM S K， HASSANIEN A E， et al. Formal concept analysis for mining hypermethylated genes in breast cancer tumor subtypes[C]//2012 12th International Conference on Intelligent Systems Design and Applications （ISDA）. IEEE， 2012： 764-769.

[12] STUMME G， MAEDCHE A. FCA - MERGE： Bottom-up Merging of Ontologies[C] //Proceedings of the 17th International Joint Conference on Artificial Intelligence. San Francisco： Morgan Kaufmann Publishers Inc.， 2001： 225- 230.

[13] SARMAH A， HAZARIKA S M， SINHA S K. Security Pattern Lattice： A Formal Model to Organize Security Patterns[C] //19th International Workshop on Database and Expert Systems Application（DEXA'08）. IEEE， 2008： 292-296.

[14] ALYI A K， ZULKERNINE M. A comparative study of software security pattern classifications[C]// 2012 Seventh International Conference on Availability， Reliability and Security （ARES）. IEEE， 2012： 582-589.

[15] BREIER J， HUDEC L. Towards a security evaluation model based on security metrics[C]//Proceedings of the 13th International Conference on Computer Systems and Technologies. ACM， 2012： 87-94.

[16] JANG I， YOO H S. Personal information classification for privacy negotiation[C] // Fourth International Conference on Computer Sciences and Convergence Information Technology（ICCIT'09）. IEEE， 2009： 1117-1122.

[17] PRISS U. Unix systems monitoring with FCA[C]//Conceptual Structures for Discovering Knowledge. Springer Berlin Heidelberg， 2011： 243-256.

[18] ] BIBA K J. Integrity Considerations for Secure Computer Systems[R]. The MITRE Corporation. Tech. Rep.： MTR-3153， 1977

[19] BELL D E， LAPADULA L J.Secure Computer System：Unified Exposition and Multics Interpretation[R]. The MITRE Corporation. Tech. Rep.： MTR-2997 Revision 1， 1976

[20] SAKURABA T， SAKURAI K. Proposal of the hierarchical file server groups for implementing mandatory access control[C]//2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing （IMIS）. IEEE， 2012： 639-644.

[21] Obiedkov S， Kourie D G， Eloff J H P. On lattices in access control models[M]//Conceptual Structures： Inspiration and Application. Springer Berlin Heidelberg， 2006： 374-387.

[22] OBIEDKOV S， KOURIE D G， ELOFF J H P. Building access control models with attribute exploration[J]. Computers & Security， 2009， 28（1）： 2-7.

[23] SANDHU R，BHAMIDIPATI. The ASCAA principles for next generation role-based access control[C]//Proceedings of 3rd International Conference on Availability，Reliability and Security（ARES）.Barcelona，Spain，March 2008： xxvii - xxxii.

[24] SOBIESKI ？， ZIELINSKI B. Modelling role hierarchy structure using the Formal Concept Analysis[J]. Annales UMCS， Informatica， 2010， 10（2）： 143-159.

[25] KUMAR C A. Modeling access permissions in role based access control using formal concept analysis[C]//Wireless Networks and Computational Intelligence. Springer Berlin Heidelberg， 2012： 578-583.

[26] GAUTHIER F， MERLO E. Investigation of access control models with formal concept analysis： A case study[C]// 2012 16th European Conference on Software Maintenance and Reengineering （CSMR）. IEEE， 2012： 397-402.

[27]MOLLOY I， CHEN H， LI T， et al. Mining roles with multiple objectives[J]. ACM Transactions on Information and System Security （TISSEC）， 2010， 13（4）： 36.

[28]LI Ninghui， LI Tiancheng， MOLLOY I， et al. Role mining for engineering and optimizing role based access control systems[R]. Technical report， November， 2007.

[29] MOLLOY I， LI Ninghui， LI Tiancheng， et al. Evaluating role mining algorithms[C]//Proceedings of the 14th ACM symposium on Access control models and technologies. ACM， 2009： 95-104.

[30] DAU F， KNECHTEL M. Access policy design supported by FCA methods[C]//Conceptual Structures： Leveraging Semantic Technologies. Springer Berlin Heidelberg， 2009： 141-154.

[31] KNECHTEL M. Access restrictions to and with description logic web ontologies[D]. Dresden University of Technology， 2010.

[32] KUMAR C. Designing role‐based access control using formal concept analysis[J]. Security and communication networks， 2013， 6（3）： 373-383.

[33] HAN DaoJun， ZHUO Hankui， XIA Lanting， et al. Permission and role automatic assigning of user in role-based access control[J]. Journal of Central South University of Technology， 2012， 19（4）： 1049-1056.

[34] 贾笑明， 韩道军， 王宝祥. RBAC 中基于概念格的角色评估[J]. 河南大学学报： 自然科学版， 2013， 43（1）： 85-90.

[35] KWON O， KIM J. Concept lattices for visualizing and generating user profiles for context-aware service recommendations[J]. Expert Systems with Applications， 2009， 36（2）： 1893-1902.

[36] WANG Jian， ZENG Cheng， HE Chuan， et al. Context-aware role mining for mobile service recommendation[C]//Proceedings of the 27th Annual ACM Symposium on Applied Computing. ACM， 2012： 173-178.

[37] 何云强， 李建凤. RBAC 中基于概念格的权限管理研究[J]. 河南大学学报： 自然科学版， 2011， 41（3）： 308-311.

[38] WAN Z， LIU J， DENG R H. HASBE： A hierarchical attribute-based solution for flexible and scalable access control in cloud computing[J]. Information Forensics and Security， IEEE Transactions on， 2012， 7（2）：743 - 754.

[39] 智慧来， 智东杰， 刘宗田. 概念格合并原理与算法[J]. 电子学报， 2010， 38（2）： 455-459.

基金项目： 国家重点基础研究发展计划（973） （2011CB302605）；国家高技术研究发展计划（863） （2010AA012504， 2011AA010705）；国家自然科学基金（61272545，U1204605，61402149）。

作者简介： 张 磊（1981-），男，河南博爱人，博士研究生，讲师，主要研究方向：形式概念分析、数据挖掘、 信息安全；

张宏莉（1973-），女，吉林榆树人，博士，教授，博士生导师，主要研究方向：信息内容安全、网络测量和建模、并行计算。