Role Mining with ORCAJ¨urgen SchlegelmilchOFFIS e.V.Escherweg 226121 Oldenburg, [email protected] SteffensOFFIS e.V.Escherweg 226121 Oldenburg, [email protected] continuously growing numbers of applications, enter-prises face the problem of efficiently managing the assign-ment of access permissions to their users. On the one hand,security demands a tight regime on permissions; on the otherhand, users need permissions to perform their tasks. Role-based access control (RBAC) has proven to be a solutionto this problem but relies on a well-defined set of role def-initions, a role concept for the enterprise in question. Thedefinition of a role concept (role engineering) is a difficulttask traditionally performed via interviews and workshops.However, often users already have the permissions that theyneed to do their jobs, and roles can be derived from thesepermission assignments using data mining technology, thusgiving the process of role concept definition a head-start.In this paper, we present the ORCA role mining tool andits algorithm. The algorithm performs a cluster analysis onpermission assignments to build a hierarchy of permissionclusters and presents the results to the user in graphicalform. It allows the user to interactively add expert knowl-edge to guide the clustering algorithm. The tool providesvaluable insights into the permission structures of an enter-prise and delivers an initial role hierarchy for the definitionof an enterprise role concept using a bottom-up approach.Categories and Subject DescriptorsD.4.6 [Software]: Operating Systems—Access controls;H.1.2 [Information Systems]: Models and Principles—User/Machine Systems, Human factors; K.6.5 [ComputingMilieux]: Security and ProtectionGeneral TermsSecurity, Management, Algorithms, Human FactorsKeywordsRole-based access control, role definition, role hierarchy, roleengineering, role mining, data mining, cluster analysisPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SACMAT’05, June 1–3, 2005, Stockholm, Sweden.Copyright 2005 ACM 1-59593-045-0/05/0006 ...$5.00.1. INTRODUCTIONSince the early 1990s [7], Role-Based Access Control hasbecome more popular. There are standard models (RBAC96[23], NIST2001 [4]) and active research on both extensions[23, 22, 15, 10, 11] and methodologies [5, 17, 6]. Mainlyenterprises with many users and high security demands likebanking companies are now considering RBAC and role con-cepts, and therefore facing the problem of how to defineroles. This has prompted new approaches in role engineer-ing. The traditional top-down approach [17, 6] has beencomplemented with bottom-up approaches using data min-ing techniques [24]. This application of data mining to iden-tify roles from existing data is called role mining.The few proposals for role mining differ in the choice ofalgorithm as well as source data. In this paper, we discussrole mining based on existing permission assignments andpresent ORCA, the OFFIS Role mining tool with ClusterAnalysis, and its algorithm. This algorithm builds a hierar-chy of permission clusters using a bottom-up cluster analy-sis. The tool provides the user with valuable insights intothe existing permission structures and allows to iterativelytransform the cluster hierarchy into an initial role hierarchy.The remainder of this document is organised as follows:Section 2 describes role mining along with its benefits andpitfalls. Section 3 presents a data mining algorithm tailoredfor role mining. The algorithm has been implemented withinthe ORCA tool which is introduced in Section 4. We dis-cuss some related work in Section 5 before closing with aconclusion and a prospect on future work in Section 6.2. THE CONCEPT OF ROLE MININGRole engineering is a tedious, error-prone and politicallydifficult task. Once role definitions are established, there isno more slack to shift responsibilities or to demand addi-tional permissions. So, people are hesitant to specify rolesand reluctant to co-operate. Any tool supporting the pro-cess of role engineering with objective data helps puttingdiscussions on a firm base and avoids intentional as well asaccidental errors, thereby accelerating the process.There are generally two approaches to role engineering [6]:Either working top-down from an initial description to rolesand permissions or else aggregating permissions bottom-upinto roles. The first approach starts with business processdefinitions or scenarios, extracts role candidates from thesedescriptions, and then transforms them into an enterpriserole concept [5, 17, 18]. The roles are then fitted with thenecessary permissions. This approach is time-consumingand may deliver process descriptions as an unwanted side-168product (unwanted because of their potential for process op-timization and hence reorganisation). It also requires earlyco-operation of employees and/or experts and is harder tosupport with a tool: the necessary knowledge is in people’sminds and has to be externalised first.The second approach starts bottom-up by analysing arti-facts of roles [12] and then transforms and aggregates theminto the roles themselves. The idea here is that roles are al-ready implicitly in use [23] and have to be identified ratherthan defined. Roles describe tasks within a process and inmodern enterprises, these tasks often involve applications.So, to act in a role a person has to access applications andtherefore has to have permissions. In short, roles leave pat-terns in the permission assignments and it is possible to findthose patterns using data mining technology. This providesthe role engineering process with an impartial and reliablebase for discussions and refinements.Caveats of Role Mining. The usual precautions of datamining apply to role mining, too: The more permissionsare needed for a role, and the more specialised they are, thebetter will be the mining result. For example, the permissionto use Microsoft Word is not very specific and will thereforenot distinguish any role. On the other hand, access rights fora geo-information system, a database of telecommunicationlines, and