Paper Submission

I'm currently still writing my next paper. I have an extension until 15th January, a week after the original submission date, 8th January. My fellow research friends suggested there might be an extension because the submission site was still down a week before the 8th. This gives me more time to work on my results, and improve them for the paper.

I've gotten most of the sections of writing worked out and am now working on the implementation. Some of the transitive closures with the graphings are a little tricky. There are many exceptions for like if a role is connected to other roles and it wasn't to merge with another role, what happens to all the roles beneath it? How can they automatically be merged? I haven't quite decided what I want to do yet. But as I write, I think through the problems more and work out what's going on as I go.
Another way to describe trees is as an acyclic directed graph. Rao was drawing and the nodes we have originally are users and permissions. The edges we have are assignment of permissions to users. It is the pictorial representation of what we have when we enter an existing environment before the implementation of role based access control. As you can imagine, there are edges everywhere. Each user can have an edge between any number of permissions. If we were to place nodes/edges in between permissions and users, we can reduce the number of edges. The graph with the least number of edges produces the graph with the best role hierarchy structure. How can we prove this? Graph theory to the rescue. These additionally inserted nodes between permissions and users are the roles.

Access control and also be represented using matrices. The most common type of access control matrix representation is the access control matrix that lists users and permissions. Matrices also represent graphs. This access control matrix can directly be translated to the initial graph format that contains users and permissions and nodes and edges between permissions and nodes. Each column or row of the matrix is a permission or user and each value within the matrix represents an edge between a user and a permission if the value is set to 1 and no edge otherwise. The role hierarchy after edge reduction can represent two matrices, one that contains roles and users and one that contains roles and permissions. Mathematically speaking, this can create an operation on the two matrices that produce our initial one. The problem comes from identifying the best user-role matrix and user-permission matrix given the operation. The “best” two matrices can be defined as the combination of two matrices that have the least number of edges or the least number of 1’s within the matrix. That’s something interesting to think about.

Laurence sat in on the meeting because he was doing something very similar with his graphs. He wasn’t doing it for role discovering in a security based environment but the addition of nodes within a graph to reduce the number of edges was something that he was attempting to do in his own field of research. It was also noted that the concept of different levels in the hierarchy can be achieved by allowing self referencing values in one of our operation matrices. In the roles-permissions matrix, roles can be related to other roles. This is implicit of a hierarchy.

Update, ideas formalised in:
Dana Zhang, Kotagiri Ramamohanarao and Tim Ebringer. Role Engineering using Graph Optimisation. In Proceedings of the twelfth ACM Symposium on Access Control Models and Technology (SACMAT'07), Sophia Antiopolis, France, June, 2007