Currently in Oak Ridge

Just before Easter, I was notified my submission to CSIIRW '10, 6th Annual Cyber Security and Information Intelligence Research Workshop was accepted. After funding was approved with less than 2 weeks before the start of the workshop, organising travel from Australia to the United States was a bit hectic. But I'm pleased to say, everything worked out and after over 20 hours of flying, I am here in Tennessee.

Location: The workshop itself is held at Oak Ridge National Laboratory, a national research centre with an interesting history. Initially established in 1943, ORNL was part of the secret Manhattan project to pioneer a method for producing and separating plutonium. Apparently I'm sitting near a nuclear reactor right now? The laboratory is in Oak Ridge, where the whole town seems to have been built in support of the research laboratories in the area.

Currently, the lab facilitates six major areas of research: neutron science, energy, high-performance computing, systems biology, materials science at the nanoscale and national security. The workshop that I will be presenting at falls under national security. But while attendees were at ORNL, they had the opportunity to take a tour around the facilities and have a look at both the Jaguar and the Kraken, the first and third fastest supercomputers in the world. We were also shown the type of simulations the computers ran to support the research performed by other parts of the laboratory. Very amazing indeed. Feel free to read up more about the research lab on their official website: http://www.ornl.gov/

Content: As the title of the workshop suggests, the focus was on Cyber Security and Information Security. The plenary speakers spoke on a range of issues including national security, system security and web security. Keynote bios can be found here: http://www.ioc.ornl.gov/csiirw/keynotebios.html. As some of these areas hasn't been the primary focus of my research in the past several years, it raised very many interesting issues that I had not considered. What is the strategy that should be taken to make security less beneficial to the "bad guys" and in more favour of the "good guys"? An aikido approach to redirect threats can be taken; use the force of the attacker to beat them at their own game. We should be making detection systems online and capable of analysing larger volumes of data. Design for failure and have a recovery plan! The keynote speakers really made this conference for me.

The paper sessions looked at design, malware, network, privacy and metrics, enterprise, survivability, formal methods and trust. Most times I had difficulty deciding which room to go to. I usually ended up in the network/malware stream, listening to malware classification, and any sort of categorisations that used data mining tools.

There were also some interesting posters out in the lobby area, available to be read at your leisure during the entire event.

My Work: The paper I had accepted and presented this morning was titled: Graph Based Strategies to Role Engineering. It's the foundations of my current research in graph based role engineering for definition of a set of roles that accurately reflect the internal functionalities of an enterprise for RBAC. To identify the roles, we first map users, permissions and roles to nodes and user-to-permission, user-to-role, role-to-role and role-to-permission assignments to edges in a directed acyclic graph (DAG). There are three graphs:

UPGraph

URPGraph

UHRPGraph

There are three different cost models:
Role minimisation: cost(G)= c₁|V_R|
Edge minimisation: cost(G)= c₂|E|
Role and Edge minimisation: cost(G)= c₁|V_R| + c₂|E|
where c_x are the static costs of role and assignment administration, |V_R| is the number of role nodes in the graph and |E| is the number of edges in the graph.

Using both the graph model and the cost metrics, we propose a heuristic strategy for optimisation. Please check the paper for more details on the heuristic and some preliminary results.

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.

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.