Matrix representation

All access control can be represented as a binary matrix, users and permissions, 1 if user has that permission, 0 otherwise. The presence of roles is the decomposition of the access control matrix to a user to role matrix and a role to permission matrix.

My supervisor goes to China for a while and comes back just before the next paper deadline so there's lots to discuss. The main results I wanted to analyse with him before he left was our matrix optimisation operations to find optimal tree hierarchies for our role structure. In order to do this, I formalised all of our beliefs and operation on our matrices. The difficulty of course is not the operation on the matrices but how to identify our matrices. It’s a bit of a reverse engineering problem. We have matrices A, B and C to represent users to permissions, users to roles and roles to permissions respectively. We can represent A as A = B*C where * is the matrix operation to convert to A. The solution we are attempting to find is how to extract the best B and C. The problem itself has not changed but this is a formal specification of the situation that turns it into optimisation problem. We define but best B and C as when |B| and |C| as minimal. That is, the least number of roles present when roles are compulsory. This should also imply least number of edges in the graph or user to role assignments as well as role to permission assignments. It will be a little math problem to formally prove this. After defining the problem, I’ve created simple examples on how I wish to derive B and C given A. Using this, I want to place the example into a simple graph using yFiles and apply my reverse engineering problems. This I found was more difficult than I thought because the so called reverse engineering operation of our operation is the whole role extraction process. But I will have to think about it more.

We also spoke of our next paper submission deadline, January 8th. This date is acceptable and we will try to have something from the graph mining for the submission. The most important will be the results from this section of work.

Databases: Loading my database was not as difficult as I thought it would be. I write this now because I have done it already. I created an account that allowed normal SQL Server Authentication and turned on TCP/IP connections to my server. Connecting to the server was not a problem. As part of the policy section of my research, I wanted to draw up an ER diagram of what the objects within the SiteMinder system was as well as their relationships. Using this, I found that I required only 4 tables. Many of the entities and relationships I originally thought I needed could be eliminated through the 1-1 and 1-n relationship rules. In the end, I only required four tables: Policy Link, Policy, Rule and UserPolicy. I am quite happy with the pictures as they are very clear and help me understand what it is that I’m trying to do whenever I look back at it. Next step is to place some foreign key constraints. Tim recommended placing all the data in the database before we attempted to place restrictions and constraints on attribute values. This is counter-intuitive to all the theory that I have been taught over the years as there is I always thought you should check referential integrity as you entered values to ensure that they are permissible entries. But in our situation, with our type formats, it is just easier, faster and more efficient if we do it this way. With the size of the files I’m working with, it would just take too long for checks to be placed on every entry. Anyway, next is to set up some views.

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