Leveraging Lattices to Improve Role Mining

@inproceedings{colantonio08leveraging,
author = {Alessandro Colantonio and Roberto Di Pietro and Alberto Ocello},
title = {Leveraging Lattices to Improve Role Mining},
booktitle = {Proceedings of The Ifip Tc 11 23rd International Information Security Conference (SEC'08)},
year = {2008},
isbn = { 978-0-387-09698-8},
pages = {333--347},
location = {Milano, Italy},
publisher = {Springer},
address = {Boston},
}

There has been recent works that use lattices for role mining [1][2]; this paper analyses role mining lattice properties. Findings are used to remove data redundancies and compress lattice representation. This  can speed up the search for a role set. Optimisations are tested using Apriori and rationalised using RBAM(Role Based Association Rule Mining). Less roles are found faster.

One of the most basic ways to generate frequent patterns is by using lattices. Applying this to role engineering, the lattice represents all possible roles from given user permission assignments. However, lattices can become very large. This paper maps frequent pattern concepts to RBAC and creates RBAC representation for the data mining concepts. Lattice properties are described using the new RBAC representation and when roles can be deleted is discussed. For example, lattices can produce multiple related roles of the same frequency. Only the role of maximal size needs to be kept.

Compression techniques are then applied to Apriori for RBAC and tested on real data from an undisclosed domain. In the dataset, there are 954 users and 1108 permissions. Using Apriori with minimum support of 10%, 299 roles that were assigned 16 permissions were identified. 890 users were assigned these 16 permissions. Using RB-Apriori, 109 roles were found faster. However, the quality of RB-Apriori roles is not discussed, but 299 roles with 16 permissions? Doesn't sound ideal.

A Cost-Driven Approach to Role Engineering

@inproceedings{1364198,
author = {Alessandro Colantonio and Roberto Di Pietro and Alberto Ocello},
title = {A cost-driven approach to role engineering},
booktitle = {SAC '08: Proceedings of the 2008 ACM symposium on Applied computing},
year = {2008},
month = {March},
isbn = {978-1-59593-753-7},
pages = {2129--2136},
location = {Fortaleza, Ceara, Brazil},
publisher = {ACM},
address = {New York, NY, USA}
}

This paper proposes association mining with cost analysis for role engineering (RBAM - Role Based Associate Rule Mining). A cost function that reduces the number of roles and role relationships as well as an attribute cost of the role is used. The attribute cost represents available business semantics that are available. In absence of high level information, role and role relationship cost is used. Association mining is performed on roles to identify inheritance relationships.

The following metrics are presented
support of a role - percent of users assigned permissions in the role
actual support of a role - percentage of users assigned the role
grade of a role - number of permissions assigned to a role
confidence of two hierarchically related roles - ratio of number of users assigned to superrole to the number of users assigned to subrole

Cost components are analysed and the cost of deleting a role is evaluated in accordance with their cost model.

Their approach is as follows:
Using a priori, generate a lattice of all possible combinations of assigned permissions as roles above a frequency threshold, removing roles with low support. Remove roles that no users are directly assigned to. Remove roles if doing so does not modify the access control matrix and the cost improves.

Migrating to Optimal RBAC with Minimal Perturbation

Jaideep Vaidya, Vijayalakshmi Atluri and Qi Guo. Migrating to Optimal RBAC with Minimal Perturbation. In SACMAT’08: Proceedings of the thirteenth ACM symposium on Access control models and technologies, Estes Park, Colorado, June 2008.

A new variation to the role mining problem (RMP) is introduced: minimal perturbation RMP. When roles within an enterprise already exist, minimal perturbation RMP aims to identify an optimal set of roles that is also similar to the current configuration. A role migration cost based on role similarity is incorporated with their existing subset enumeration algorithm.

A method for measuring role similarity using the Jaccard coefficient is proposed. In general terms, Jaccard coefficient is calculated as the ratio of the intersect of two sets to the union of those to sets to produce a value between 0 and 1 that measures similarity. 0 for no similarity (different) and 1 for high similarity (same). In terms of roles, role is a set of permissions. The similarity of a role now becomes the ratio of the intersect of two permission sets to the union of two permission sets to produce a value between 0 and 1.

Given a proposed role and the collection of existing roles, the similarity metric of the role is the best Jaccard coefficient between the proposed role and a role that exists within the collection. That is, the Jaccard coefficient between the proposed role and every role in the collection is calculated and the best coefficient is used as the similarity.

To measure the similarity of between the collection of proposed roles and the collection of existing roles, the similarity metric of each role in the proposed role collection is calculated and averaged.

The metric is coined with FastMiner, an iterative role mining process that looks at user permission assignment intersections. A greedy heuristic that chooses roles with the most coverage (user + permission assignment) and highest similarity until all permission assignments is covered is used.

Trade-offs between minimizing only roles and searching for only the most similar roles is also analysed.

There are lots of examples in the paper.

Mining Roles with Semantic Meaning

@inproceedings{molloy08semantic,
author = {Ian Molloy and Hong Chen and Tiancheng Li and Qihua Wang and Ninghui Li and Elisa Bertino and Seraphin Calo and Jorge Lobo},
title = {Mining Roles with Semantic Meanings},
booktitle = {SACMAT'08: Proceedings of the thirteenth ACM symposium on Access control models and technologies},
year = {2008},
month = {June},
address = {Estes Park, Colorado},
}

In this paper:

1. What semantic analysis can be performed based on data availability/dimension.
2. Using "Formal Concept Analysis", a hierarchical miner is developed.
3. Performs role mining with user attributes as well as user permission information.
   

Data Dimension: user permission, user attribute (user's job title), permission parameter (database permission, read access), permission update (logs of how permissions have changed over time), permission usage (what users are using what permissions and when). What additional information can be offered with each extra dimension is discussed.

Formal Concept Analysis: applied to role mining, a formal context is triple (G, M, I) where G = set of users, M = set of permissions, I = relationship between users and permissions. A concept of the context (G, M, I) is a pair (X, Y) where Y is the set of all properties shared by all objects in X and X is a set of all objectes that share all properties in Y. X = extent and Y = intent. (X, Y) can be subconcept of (X', Y') iff X⊆X' or Y⊆Y'.

For example, {{u1, u2, u3}, {p1, p2, p3, p4, p5}} can be a concept, allowing concepts to represent roles. Each user is assigned exactly one role and each permission is assigned exactly one role. To reduce large concept latices, weighted structural complexity is introduced. Weighted structural complexities gives different costs/weights to different components of RBAC (wr * number roles, wu * number of user assignments, vp * number of permission assignments, and so on) . Optimal RBAC state has minimal weighted structural complexity.

Hierarchical Miner: greedy algorithm that iterates all possible roles and prunes roles if doing so reduces the cost of the RBAC state. Algorithm terminates when no more oprations can be performed.

Attribute mining creates "attribute roles" using a candidate role set and user attributes to help describe roles. Each role/permission set can turned into multiple attribute roles (a role can be give multiple attribute descriptions, each attribute description is an attribute role). Because of this, a role to user assignments are based on a edge to complexity ratio metric. 

Fast Exact and Heuristic Methods for Role Minimization Problems

@inproceedings{ene08fast,
author = {Alina Ene and William Horne and Mikola Milosavljevic and Prasad Rao and Robert Schreiber and Robert E. Tarjan},
title = {Fast Exact and Heuristic Methods for Role Minimization Problems},
booktitle = {SACMAT'08: Proceedings of the thirteenth ACM symposium on Access control models and technologies},
year = {2008},
month = {June},
address = {Estes Park, Colorado},
}

This paper addresses the RMP (Role Mining Problem) as a graphing problem. To minimise the number of roles while ensuring no user to permissions assignments are modified, user permission assignments are graphed and reduced. Role set solutions are then derived from the reduced graph. To address the issue of both minimising number of roles and number of edges, my graph optimisation approach was implemented, tested on their data sets and analysed. (Horrah).

The basic access control matrix is presented as an undirected bipartite graph G. Vertices are either in U (users) or P (permissions). It was noted that for a role, users and permissions assigned to the role induce a biclique in G. Since roles cover all permissions and users, the set of all roles R is a biclique cover of G. The role minimisation problem maps to finding the minimal biclique cover (MBC) of G, which is also NP-hard and known to be hard to approximate.

MBC is then reduced to minimum clique partition and chromatic number. Graph G' is created where edges in G are vertices in G'. An edge in G' is present iff endpoints of correspondence edges of G include a biclique in G. A clique in G' corresponds to a biclique in G. The clique cover number of G' corresponds to the biclique cover number of G. The biclique cover number of G is the chromatic number of G'.

Based on these proofs/reduction/mapping of problems, lower bound biclique cover algorithms are presented that can find best clique covers when each biclique is a star (equivalent to finding minimal number of roles). Rank adjacency is also used to estimate biclique cover number. When proposed iterative method for exact solutions for finding bicliques are too time consuming, greedy algorithms for finding bicliques are also proposed. Reducing the number of roles based on edge count is also used. Interesting results using the applied techniques on their data tests is then discussed. Assignment of users to groups before assignment to roles can also be done to reduce the size of the graph.

Algorithms were tested on 7 data sets, none of which seem to have RBAC implemented. Exact details of the datasets were not disclosed: number of users, number of permissions (probably for privacy reasons). Results of algorithm on the data are tabulated. One role that is found in their largest dataset is assigned to 2804 users and has 20 permissions. Four-fifths of the roles consist of a single user and all of their permissions. Heuristic approaches are quite fast and a combination of their approaches comes close to exact calculations. Bounds for heuristics are measured based on their test results.

They note that their results still have some what under defined meaning for roles semantically. What do the roles mean, why is the infrastructure good? Also in some of their data sets, the number of roles is the same as the number of users or permissions.

Optimal Boolean Matrix Decomposition: Application to Role Engineering

@inproceedings{lu08optimal,
author = {Haibing Lu and Jaideep Vaidya and Vijayalakshmi Atluri},
title = {Optimal Boolean Matrix Decomposition: Application to Role Engineering},
booktitle = {IEEE 24th International Conference on Data Engineering},
year = {2008},
month = {April},
address = {Cancun, Mexico},
}

This paper models boolean matrix decomposition through binary integer programming. The problem is mostly described in the context of role engineering and RMP, the Role Mining Problem. The same problems are described with the addition of edge-RMP. Edge-RMP sounds like the goal of my graph optimisation, a graphing approach that minimises number of roles as well as role assignments/edges. This paper re-describes RMP, min-noise RMP, δ-approximate RMP now with edge-RMP. The contribution of the paper is the transformation of the problems into a set of equalities and inequalities models for binary integer programming. Different constraints on the models are applied to the problem to represent different variations of RMP.

Once again, the access control matrix A is described as the composition of B ⊗ C. That is, B and C is the decomposition of A. The are translated into binary integer programming models and heuristics for solving the problems are described.

Basic RMP approach: use FastMiner to identify candidate roles and create role to permission matrix based on results. Prune permission sets of users to that each permission set is unique and create access control matrix. Use constraints (to ensure no addition/remove of user/permissions) to identify user to permission assignment matrix.

Similar/slightly modified approaches are discussed for the edge-RMP and δ-approximate RMP and min-noise RMP. The approaches rely on FastMiner for producing good candidate roles.

The main contribution of the paper is theoretical representation of problem and how greedy heuristics can be used in modelled binary integer problems when candidate roles are provided. Experimental results show good run times and accuracy for their generated test sets.

Role Mining - Revealing Business Roles for Security Administration using Data Mining Technology

@inproceedings{kuhlmann03rolemining,
author = {Martin Kuhlmann, Dalia Shohat, Gerhard Schimpf},
title = {Role Mining - Revealing Business Roles for Security Administration using Data Mining Technology},
booktitle = {SACMAT '03: Proceedings of the eighth ACM symposium on Access control models and technologies},
year = {2003},
address = {Como, Italy},
publisher = {ACM Press},
}

This is the earliest work that discuss the application of Data Mining techniques to assist Role Engineering. The paper goes through more as a case study of possible RBAC deployment within different organisations using SAM(Security Administration Manager software framework). Details of how data mining is not explored in great detail. The contribution of this paper focuses more on the feasibility of data mining application for role engineering. There is no discussion on what techniques for data mining would be better, analysis of their mining results or what the data mining actually does/means. Their "data miner" is a black box machine that produces statistical and semantic information that is used to assist role definition.

One example for case study was a bank organisation that has 45 000+ employees, distributed across 14 00 branches with 40 types of systems supporting 65 000 user ids and 47 000 user groups. I found it interesting that there are about 20 000 more user ids than there are employees. New users are assigned roles based on user attributes.

Other case studies show their technique was capable of finding existing SAM models from basic data. The models took 2 months to manually define, 2 hours to use data mining to identify. (What about accuracy? Were other incorrect models identified?) An evaluation cost was performed, stating potential cost savings of 60% during role creation and 50% during role maintenance given cost of manual analysis and some growth assumptions.

In their system, roles are separated into two categories: organisational roles and functional roles. Organisational roles define basic access privileges and functional roles describe access rights in relation to additional functions or tasks. Roles also contain attributes or rules that are true for all users to are assigned to the role.

Process:
The data mining techniques that are mentioned are association rules and clustering from the IBM Intelligent Miner for Data. Iterative role finding using only a fixed set of users and assumes each user only has one account on each system. Uses user to system information, user attributes for system, existence of groups or roles in system, resource authorisations and global user information. Assumes all used is correct (pre-processing to remove incorrect data).

Clustering is performed on user attributes to receive organisational roles. Association is performed to create group connections for organisational roles and functional roles.

Reports from clustering and association rules are used to create roles.

Issues: how does the selection of the subset of users to perform data mining occur? How does the data mining happen? What kind of clustering is used? What are you finding associations in? It is not clear the data mining is performed as the IBM data miner was used as a black box and results were used as is.

It's nice to see results of deployment in real businesses.

The Role Mining Problem: Finding a Minimal Descriptive Set of Roles

@inproceedings{vaidya07rmp,
author = {Jaideep Vaidya and Vijayalakshmi Alturi and Qi Guo},
title = {The Role Mining Problem: Finding a Minimal Descriptive Set of Roles},
booktitle = {SACMAT '07: Proceedings of the twelth ACM symposium on Access control models and technologies},
year = {2007},
address = {Sophia Antipolis, France},
publisher = {ACM Press},
}

This paper formally describes the aim of role engineering with data mining through RMP, the role mining problem as well as two variations of the problem: δ-approx RMP and the minimal noise RMP. All three problems are shown to be NP-complete.

The RMP is defined as the the problem of finding the optimal set of roles from existing user permissions. The paper defines the optimal/good set of roles as the set of minimal roles that represent the initial access control matrix. Like me, they define the discovery of roles as a decomposition of the access control matrix. (A = B ⊗ C)

To measure matrices, difference metrics for matrix normals are employed. That is, a count of differences between binary matrix values. In RMP, the composition of the user role matrix and the role permission matrix should be exactly the same as the the access control matrix. That is, the decomposition of the access control matrix should not give extra or remove existing permissions. In δ-approx RMP, access control matrix resulting from the mining is allowed to differ from the original access control matrix by δ. The mining is bound by δ. In minimal noise RMP, the δ is minimized while ensuring the number or roles does not exceed a certain threshold. The mining is bound by the number of roles.

The RMP and it's variations are then mapped to the set basis problem and shown to be NP-complete. The RMP problem and its variants are then mapped onto existing problems (minimum tiling in databases and discrete basis) and analysed. A solution for the minimum tiling problem is a greedy approximation algorithm that finds largest tiles first. This is synonymous to finding roles with the largest size first. Semantically, this is probably not quite right for RBAC. This approximation is bound to O(logmn) of optimal where m is number of users and n is number of permissions. The minimal noise RMP is mapped to the discrete basis problem and basis usage problem. The discrete basis problem has been shown to have no approximation in constant factor polynomial time. The discrete basis problem is synonymous to the optimal assignment of minimal noise role to users in the minimal noise RMP context.

Role Engineering using Graph Optimisation

@inproceedings{zhang07graph,
author = {Dana Zhang and Ramamohanarao Kotagiri and Tim Ebringer},
title = {Role Engineering using Graph Optimisation},
booktitle = {SACMAT '07: Proceedings of the twelth ACM symposium on Access control models and technologies},
year = {2007},
address = {Sophia Antipolis, France},
publisher = {ACM Press},
}

Role engineering is the definition of roles for Role Based access control. Initial approaches used elicitation of job functionalities and business requirements for role creation. Due to the costly and time consuming process of the manual analysis, more recent approaches have moved to automated extraction. While most automated approaches have data mining techniques, this paper explores the optimal decomposition of the access control matrix through graphing techniques.

All user permission assignments can be represented as an access control matrix. Role based access control can be described as the decomposition of the access control matrix to a user-role matrix and a role-permission matrix. That is A = B ⊗ C. Where A is the access control matrix, B is the user to role assignment matrix and C is the role to permission assignment matrix. Many decompositions exist. The challenge comes from producing the optimal user-role and role-permission matrix. Optimality is dependant on given metrics.

In this paper, the problem is described as a matrix decomposition problem and the solution produced by specifying metric that reduce the user-role and role-permission relationships (synonymous to a reduction of administration requirements on user permission management) and reduce the number of roles (synonymous to a reduction in administration requirements of roles).

The problem can easily represented as a graph and the optimisation process is a series of graphing operations with the aim of reducing the number of nodes and edges in the graph (or number of roles and role relationships respectively).

The algorithm was tested on user permission assignments within a public domain to produce Role Based Access Control infrastructures that offer improved access control administration for the system. The test set used was of medium to small size and problems of local minimum have not yet been addressed.

Closet: an efficient algorithm for mining frequent closed itemsets

@inproceedings{pei00closet,
author = {Jian Pei and Jiawei Han and Runying Mao},
title = {Closet: an efficient algorithm for mining frequent closed itemsets},
booktitle = {ACM SIGMOD Workshop on Research Issues in
Data Mining and Knowledge Discovery (DMKD 2000) },
year = {2000},
}

Mining frequent closed itemsets has the same power as mining the complete set of frequent itemsets. This reduces redundant rules to be generated and increases both efficiency and effectiveness of mining. If frequent pattern mining was used to generate roles, this effectively means generation of redundant roles are reduced.

The idea behind this approach is to use conditional databases in a divide and concur format. Given a list of all frequent items above min_sup, find conditional database of item in reverse order of support. Closed itemsets can be extracted iteratively from these conditional databases. Each conditional database may be further divided into more conditional databases.

The proposed approach extends the FP-growth tree approach for pattern discovery. Implementation requires FP tree and pruning for increased efficiency. Comparison with A-Close that uses Apriori to identify closed itemsets is basically the comparison between FP tree and Apriori.

The paper is not the easiest to read. It is filled with more theory and proofs than needed for a comprehensive understanding of the algorithm.

Role Mining with Orca

@inproceedings{schlegelmilch05orca,
author = {Jurgen Schlegelmich, Ulrike Steffens},
title = {Role Mining with ORCA},
booktitle = {SACMAT '05: Proceedings of the tenth ACM symposium on Access control models and technologies},
year = {2005},
address = {Stockholm, Sweden},
publisher = {ACM Press},
}

This paper proposes ORCA, a java visualisation tool that performs hierarchical clustering on permission assignments for definition of role concepts/role engineering. User interaction can add information during hierarchy construction to assist clustering.

Mentioned caveats in role mining:

1. Noise in data: cleansing/anamolies must be removed
2. Multi-role systems: systems support multiple roles
3. Multi-role users: users can be assigned multiple roles
4. Multiple identities per user
5. No semantics in data mined roles

These issues are mentioned but not solved (with the exception of 3) by ORCA.

Method ideology: place permissions in a cluster if a significant number of users have them. Each cluster has a set of permissions and a set of users assigned to the cluster.

Technique:

1. Each permission starts as a permission set cluster in C.
   
2. Identify pairs of clusters from C with maximum user assignment intersect and maximum union.
3. Create a role from the new permission set union. If more than one exist, randomly pick one.
   
4. Remove original pair of clusters from C so previous clusters can no longer be used/selected to create new roles.
5. New role created as a super clusters of previous clusters and add to C.
   

Problems in approach:

• each permission can only belong to one path of the role hierarchy, modifications to reduce this constraint can produce inconsistencies and large number of additional yet not required roles.
  
• time consuming, must generate all cluster pair intersects at each iteration
• choosing one pair can remove the possibility of other pairings, making ordering important
  
• when more than one pair has merging potential (more than one maximal pair for new cluster creation) one is chosen at random

Novelness:

• At that time, it was the first role mining approach that didn't used a generic set of tools developed general pupose data mining. It was role engineering specific. The data mining used applied heirarchical clustering for permissions to create roles. While no new data mining contribution was made, it was a new application of data mining to enterprise security.
• The visualisation tool sounds pretty, describing what is being done at each step, what is in each cluster and different colour intensities are used for clusters with more user assignments. It sounds pretty but also confusing to use in situations with many entities. Some learning is required to understand what the data mining does and what it means in context of the different possible clusters. Some options for finding different correlations is present: highlighting clusters who have users who fit a certain criteria. Less information is given on exactly how this information can be used to create roles.
  
• Visualizations also allows for the concept of neighbouring clusters, where clusters of permissions are similar are placed next to each other for viewing in ORCA. Similarity between clusters is measured by the propotion of permissions that are the same within two clusters.
  

RoleMiner: Mining Roles using Subset Enumeration

@inproceedings{vaidya06roleminer,
author = {Jaideep Vaidya, Vijayalakshmi Atluri, and Janice Warner},
title = {RoleMiner: Mining Roles using Subset Enumeration},
booktitle = {CCS '06: Proceedings of the 13th ACM Conference on Computer and Communications Security},
year = {2006},
location = {Virginia, USA},
publisher = {ACM Press},
address = {New York, NY, USA},
}

Jaideep Vaidya et al.'s work uses unsupervised clustering and has a number of references what have also used clustering approaches to extract roles.

The concept behind the proposed “RoleMiner” is unsupervised clustering that uses each set of user permissions as a starting cluster. Roles are then created by finding common sets of permissions between users and other common sets of permissions. The theory behind this approach is that a set of permissions assigned to a user could potentially be a role. Intersects between user permission sets could also be potential roles.

Two approaches are proposed: the CompleteMiner and the FastMiner. The CompleteMiner uses each permission set for each user as the initial possible set of roles. From this, it uses subset enumeration to find all possible subsets as possible roles. To find all possible subsets, the algorithm completes in exponential time. A more computationally feasible approach (quadratic runtime) is to only consider subsets from pairs of initial roles (FastMiner). Both these approaches find possible roles (permission clusters). An ordering algorithm determines which are the best roles identified and the ones most likely to be implemented for the best RBAC infrastructure. The ordering algorithm places a bias on subsets found early from the first few iterations of the CompleteMiner, thus producing results that both approaches produce similar candidate roles. Also in the used test sets, each user is given at most 3 roles so it is very likely that a role is found during the first iteration of the CompleteMiner, the FastMiner.

For simplicity, separation of duty (SoD) constraints and sessions are not considered. Would considering these attributes of RBAC generate an alteration to the way that roles are identified? Is it possible to consider these attributes? Using the definition of a session as being an activation of a set of permissions or a set of roles assigned to a particular user, sessions would have limited effect on role extraction if the algorithm was purely based on analysis of permission to user assignments. SoD constraints would require more consideration. Static SoD’s would simply deny certain users to be allowed certain permissions in conjunction. This becomes a problem if permissions within each role are switched on or off for each user (based on the constraint). Otherwise, roles that cannot be granted in conjunction will cause permissions to not be granted in conjunction and thus will not effect the role mining. I cannot see the immediate effects on extracting roles from user permission assignments when there are dynamic SoD constraints. Dynamic SoD constraints would only effect session activations. In general, different types of SoD constraints may require different approaches. The solution seems unsolvable without more domain knowledge.

An open issue with the approach addressed by the paper is the lack of a role prioritization after candidate roles have been identified. It is suggested that semantics of what is required be added. Their approach places a bias roles found in the initial merge between any two user permission sets as a role. Doing so justifies their FastMiner, the computationally feasible approach that only consider merges from the first iterations of the CompleteMiner. If each user is given multiple roles, more iterations of the subset enumeration must be performed in order to find the original roles. Also, just because these are the roles that existed originally, what shows that they are "good" roles?

What is not discussed is the creation of a role hierarchy. The ORCA approach that RoleMiner is based on identifies role hierarchies while finding roles with no permission overlaps. Permission overlaps in different roles is now permissible, however, no method for extracting hierarchy is discussed. Possible future work may be to incorporate hierarchy definition into this approach. Permission subsets from later iterations of the CompleteMiner could potentially be lower lever roles that are inherited for people who require a superset of the permissions of that role.

It would also be interesting to see if different classification techniques other than clustering can be applied to extract roles. Why have previous approaches only looked at clustering?