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.

Back to PhD

I have returned from my internship in Sydney and am now back to research. I had a fantastic time. I personally think I had the best project to work on out of all the other interns. It tied in perfectly with my data mining interest. There was a slight administrative hurdle that we never got over (just around) but I completed the project and was even able to produce a demo for my final presentation. This would not have happened without the help and support of my mentor and development team. It was a fantastic learning experience and I'm glad I had the opportunity to be involved on such a fun project with such a cool team. I was even offered supportive feedback after the project, which was helpful and sincere.

In terms of infrastructure, the code base was well documented and maintained, with high visibility within the company. It was easy to access tools and find assistance. The focus felt like it was on creating functional and innovative products, making the big G an enjoyable environment to work in.

However, even after this experience, I am still uncertain about the direction I wish to follow after my PhD. Both academia and industry are equally appealing. Luckily I still have a couple of years to decide. In the mean time, it is back to my PhD and my research topic. I'll take a while to get back into things but I'm sure I'll get there in the end. I'm currently looking at the code that I was working on 6 months ago. I'm glad I wrote comments but I am still more confused than anything else.

The toughest thing about being away from the research is coming back to realise the new and recent developments have made some of my work invalid. That's a shame. I guess the next step is to try and catch up with where the research area has progressed to and carry on from there. Time to do a lot of reading!

Conference Notes

There were some interesting comments raised by other researchers at ICDE in relation to my work. Data Mining community is generally interested in what model of data mining I can produce. Interesting perspective from a data mining view as opposed to a security applications one. After learning about my problem, they wanted to know the novelty of my approach. That is, how does it benefit the data mining community. I think their general view is data mining benefits everyone, people should be working towards creating interesting novel approaches for new types of data mining. Application of mining techniques to some problem will be easy after the idea is developed. I guess my next approach is to show how my approach is new and novel and modify it based on my access control data to suit data of this type. Special data mining for RBAC...

Preparation for Turkey

This week, I prepared slides and gave a department/postgrad seminar for the work that I plan to present in SEIW (Declarative monitoring of declarative Web services). This presentation, while being good preparation, was also for fulfilment of departmental funding requirements.

After the presentation, I received interesting questions relating mostly to the performance of having a monitoring tool. The extra data collection will increase response rates of service requests, as with returned data quantity. But with WSOL, WSOI, the returned information is piggy packed into SOAP headers so additional data returned is minimal and additional time requirements can be minimized if measurement modules are placed within the client or server (as opposed to a third party). The department presentation attracted related researchers from both Swinburne and RMIT. While I'm not working in this area as much anymore, it was nice to bring people with similar interests together.

Researchers from Monash and RMIT who were interested in this area of research attended the presentation.

Paper reference:
Kerry Taylor, Paul Brebner, Michael Kearney, Dana Zhang, Kelly Lam and Vladimir Tosic. Towards Declarative Monitoring of Declarative Service Compositions. In Proceedings of The 2nd International Workshop on Services Engineering (SEIW07) in conjunction with 23rd International Conference on Data Engineering (ICDE 2007), Istanbul, Turkey, April 2007.

First PhD Paper

Last week, I received notification that my paper to SACMAT07 has been accepted as a short paper. My industry sponsor should be able to fund me for this travel as it is directly related to my PhD research. Some money has been set aside for me every year for travel purposes by my industry sponsor. SACMAT have emailed with paper requirements so I will try to fix the paper asap when they do. The latex template is as expected and they have given advice and information on terms, categories and crdata. I think it is due on the 15th but I will try to get it out of the way this weekend to distribute to relevant parties and allow time for fixes before I leave. I have shortened and addressed most of the issues but there is still a page of writing to delete before it meets the page limit requirements. Deleting words that you have put thought in to writing is the most difficult.

Official PhD Student

This week I received notification of PhD confirmation.

The application for conversion from Masters to PhD stated 6-8 processing time. I needed to be confirmed before date of travel which was 11th April. Since I was not ready to convert before my leave in February, I had to do it immediately after my return for the 6-8 week allowance. However, I found out on Wednesday through the School of Graduate Studies that I have been confirmed. The confirmation process requires a departmental seminar, a conversion report, a progress report and a meeting with the student's committee (along with all the relevant forms). I fulfilled all the criteria and handed in the forms on 27th of February and on Wednesday, I went to SGS to discover that I have been confirmed on their records. I was pleasantly surprised that in less than 3 weeks I have been confirmed and registered officially as a PhD student.

Synthetic Datasets vs Real Data

In research, one part of a new approach is to justify it mathematically. Another part is to experiment to show that it matches your predictions.

For my previous algorithms, I've mostly been testing with /etc/passwd and /etc/group files located within the department unix systems. After testing on this data, the only real way to show the usefulness of our results is via manual analysis. On other industry data (which I will get to eventually), this is also the only form of analysis if the enterprise had no original form of RBAC implemented.

For simulated data, I have completed the synthetic data generator that creates flat role hierarchies given the number of users, permissions and roles and the max number of roles/user and permissions/role. Testing on our frequent pattern approach exploited one of the issues with FPRM that I kind of knew about. However, I haven't not added noise or hierarchical layers into the data for additional testing analysis. The test data confirmed my suspicion that an enormous number of candidate roles are generated if each user is assigned many permissions, each set of permissions similar to another user but not exactly the same. I need to analyse closed/maximal algorithms. I have not yet used the synthetic data on my graph optimisation approach.

Ideally, the best data to work with would be access control permissions from an enterprise that has RBAC implemented. That way, we can compare our results with the one of actual implementation and compare/contrast the differences.

LDIF Files

While coding the synthetic data generator and I have also started analysing ldif active directory export files of various companies. Access to these files are granted by my industry sponsors as helpful resources for my PhD.

In analysing the ldif files, I am having some difficulty loading it into JXplorer. The error I get is javax.naming.CommunicationsException:connection closed[Root exception is java.io.IOException: connection closed] remaining name 'DC=ca, DC=com'. I think one of my co-workers suggested that it was because some of the objects were missing object classes. O_O. I guess there are also schema issues because each enterprise has their own AD schema and exporting the file simply extracts the data, not the formatting. But you'd think it would be able to work out a general idea of the tree.

I will keep working out how to load it into the directory on my VM if I can. Otherwise, I can manually (perl/python script) extract the user/group information that I need. There are perl scripts and modules that allow you to directly connect to an active directory or an x500 but they will not install properly into the university machines (I have limited privileges) and refuse to do so on my own Unix environment. I have successfully got it work in on my windows machine but I have not had a play with it. It might just end up easier to extract information from the files manually with a parser.

Synthetic Test Data Generation

This week I have mostly been working in the synthetic data generation test suite. The purpose of the data is to create RBAC infrastructures, extract only the user-permission assignments from them and mine back the original roles.

While I'm not entirely convinced of the usefulness of this (skewed roles, random roles represent real enterprises?), the research community seem to think it's useful. So the plan of my algorithm is as follows:

Inputs:

1. number of users
   
2. number of roles
   
3. number of permissions
   
4. average number of roles per user
   
5. standard deviation of roles per user
   
6. average number of permissions per role
   
7. standard deviation of permissions per role
   

Constructing roles to users and permissions to roles then extracting fundamental relationships should not be too difficult. The only issue is how real is our model. What kind of distribution could our model take? So to start with, the number of roles to users and permissions to roles are normally (Gaussian) distributed. (Most thing are normal right?) After the number of roles and permissions are picked for each user and role respectively, that number of roles and permissions are picked according to a normal distribution given the mean and std. That is, which permission and which role is picked at based on a Gaussian number generator.

I initially had some problems with the Gaussian distribution, requiring an inverse error function to transform randomly generated numbers into a normal distribution. But then I was directed to some C code that does magical stuff. I was also made aware that Java's normalised Gaussian number generator could easily be translated to a number of whatever mean and std I gave it, so that's making the coding process easier.

Alternative, permissions or roles could be assigned randomly to roles and users respectively, given a max number of permissions per role and roles per user. Either option is feasible since the actual distribution is unknown.

12 month project summary

The main focus if this project is investigation into various techniques of bottom up role engineering for the development of a comprehensive infrastructure for Role Based Access Control. Since commencement of the research project, detailed analysis of the research area has been performed and two algorithms that address open issues in existing algorithms have been proposed.

Future work exists for both of the proposed algorithms. The first approach is a frequent pattern approach for role engineering and this can be extended to identify closed or maximal frequent itemsets. This reduce the number of generated candidate permission sets. Using this approach would also eliminate the need for removing roles that were not explicitly assigned to any users. Results returned from frequent closed permission set mining could then be used to produce the role hierarchy.

The second algorithm is the graph optimisation approach and can be tested using different optimisation rules with different metrics. Doing so may identify interesting properties of each algorithm.

Both of these approaches can also be tested on more data. The current project is being sponsored by CA (formerly Computer Associates). CA has provided some policy data that provides information on users and access rights from large corporations. Investigations on actual permission data can be done to justify the practicality of our proposed approaches. This testing on CA gathered data for extraction of roles from real companies may involve the creation of a more general purpose prototype that moves the theoretical ideas of the project onto some more solid practical foundations.

While practical applications of the algorithms are important, more testing on theoretical foundations also need to be done. This requires a large set of synthetic test data. This test data can be generated artificially by creating permissions, users and roles in a RBAC model and extracting the direct user permission relationships. This data can then be manipulated by different algorithms in the attempt to recreate the original artificial RBAC model with users, permissions and roles.

The lack of sufficient test data needs to be addressed within the whole area of role engineering, not just for our algorithms. One of the future goals of this project is to create this large synthetic data test suite. This data can be used for our testing to verify our algorithms. The data can also be made available to other researchers in role engineering to test their algorithms.

The result of such a publicly available test suite is a set of results that are comparable. Different approaches on a comprehensive comparison technique can be proposed. One such technique is to place each result into a graph and compare subtree sections. Another proposal can be to create an algorithm that can map from one RBAC infrastructure to another for comparison.
The majority of existing algorithms assume clean noiseless data. Our proposed frequent pattern approach deals with incorrect assignments to an extent but analysis of access logs can further our clean our data. Preprocessing algorithms may involve analysis of access logs to removing inactive permissions before bottom up role engineering algorithms are performed.

The improvement of previous approaches and the creation of pre and post processing for the role engineering techniques will be our main focus for future research in this project.

The intention is to convert the current Masters by Research into a PhD. A department seminar has been given and approval has been granted by the research committee. Due to the conversion, final thesis preparation will occur during 2009 for the new PhD thesis deadline.

Masters to PhD Conversion

I returned to work on the 18th of February (I went on leave for the first half of Feb) and my return, I have been working furiously towards my official conversion from Masters by Research to PhD. At The University of Melbourne, the process usually takes place between 12-16 months after the commencement of a Masters by Research. I officially started with the university on 1st March 2006 so I thought I'd like to have it done by 1st March 2007. Also because for extra funding to my next conference/workshop, I have to be a confirmed PhD student before I can apply. So anyway, today is 1st March 2007 and I have been given the okay to continue as a PhD student. The forms are in works and it is now just a waiting game.

So how does the process work? Well, there needs to be a department seminar that is advertised as a conversion talk. Then there is a meeting with your committee members. For my conversion, I had the meeting right after the seminar. I know friends who have or are converting right now say they've had their meeting already but they haven't given a seminar or they've given their conversion seminar but they haven't had their meeting yet. But I just did everything all in one go so it was all fresh in everyone's mind. I think that's the best way to go about it. Either way, you have to have written and given your conversion report to your committee before the meeting. This was what has kept me busy for the past week or so. I originally wrote 5-6 pages for my conversion report but James, my new supervising member suggested it would be better if I put more effort into it. So I changed it to 65 pages. Yeah, a bit of a jump, but as long as you talk about the work that you've accomplished in the past 12 months and what your plans for the next 2-2.5 years are, it's all good. You also need a project time line. I drew up a gantt chart for what I hope to accomplish in the next 2 years and then discussed it. I also talked about when I want to accomplish what and future work in my current algorithms and what I can do about generating test data and such. So that was the report. I sent it to Rao, James and Tim (my committee).

After my report, I prepared my slides. I didn't have enough slides and I regret not making some more. I finished in about 35 minutes for a 50 minute presentation. However, questions went for about 15 minutes afterwards to that was good. I had lots of interest from the audience so I'm very happy. At first I was a little bit worried about the turnout. I was hoping for about 5-6 people but there was at least 30 there. However, this meant there was a wider range of questions from different research backgrounds as well. Some of the questions were very interesting and raised issues I had not previously thought about. Usually, the person giving the conversion seminar has to take notes on all the questions that is asked.

Straight after my seminar, I went upstairs to a little meeting room with my committee. They asked me more questions when I answered more satisfactorily than my seminar questions. They asked me to leave the room and then about 5 minutes later, they asked me to return and said congratulations. They asked if I have forms for them and I said no. If I was to do the conversion again, that's what I would have done differently: to speed up the form process, I would have filled out my sections before my meeting and during the meeting, if they agreed to let me convert, they could sign off on it right then and there. But anyway, I filled out the forms later that day and appended the committee meeting minutes as well as a list of questions that were asked at my seminar. I left these forms at reception yesterday and now I'm just sitting tight and hoping things go through before 15th April (the Istanbul workshop).

NP complexities

As an extension to the work that I have completed in January for my last paper submission, I wish to show the problem itself is NP-hard. But first is first, I have to learn what this NP business is and analyse some proofs. So I am currently reading about NP problems. I borrowed a very old looking book by Johnson from the library that looks like it will be very useful. In the decomposition of my A matrix into B and C, we would like to show that the problem itself is NP-Hard. To do so would be very good because we can quit using algorithms to solve it and work on heuristics.

In order to show the problem is NP-Hard, there are two steps that need to be performed:

1. Show Problem X is NP
   
2. Reduce an existing NP-Complete problem to it.
   

Task 1 is often simple. To accomplish task two, an arbitrary instance of a NP-Complete problem needs to be transformed into an instance of X such that the answer in the NP-Complete problem is positive if and only if the answer to the corresponding X is positive.

This is where the Johnson book comes in, to find a problem to reduce.

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

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

PhD with a University and Industry

I commenced my PhD through The University of Melbourne in March this year. In July this year, my industry agreements came through and I am officially the first PhD student to be sponsored by CA Labs. The reason it took so long was because I was the first and there were lots of legal issues, like IP to sort through. The general agreement is that the work I do is still owned by the university, but CA have non-restricted rights to everything I do as well.

My current research aims to incorporate data mining for role based access control (RBAC). My supervisor is strong in his data mining knowledge and an expert in this field. Industry have some practical problems they hope to solve with data mining in the area of role extraction for RBAC. I have spent my first 4 months reading about general RBAC issues and have discovered the name of what I am trying to do is called Role Engineering.

My previous research was related to coordinated scan detection algorithms. I completed my honours last year in this area. I evaluated some existing scan detection algorithms and extended one anomaly detection algorithm to consider coordinated scans. The move to data mining for RBAC isn't a great jump. Previous I was working with data mining for network security, now I'm looking at data mining for enterprise security.