概念格在訪問控制中的研究綜述

張磊 張宏莉

摘 要： 隨著信息技術的發展，信息系統日趨復雜和多樣化，這給訪問控制的設計和維護提出了更高的要求。概念格作為一種重要的數據挖掘和知識發現方法，具有自動聚類和自動構建層次的特點，可以用于設計和維護一個訪問控制所需要的層次結構。本文對概念格在強制訪問控制和基于角色的訪問控制中的相關研究進展進行了分析和總結，并對未來的研究趨勢進行了討論。

關鍵詞： 形式概念分析； 概念格； 訪問控制

中圖分類號： 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-），女，吉林榆樹人，博士，教授，博士生導師，主要研究方向：信息內容安全、網絡測量和建模、并行計算。