The generalized temporal role mining problem

Abstract

Role mining, the process of deriving a set of roles from the available user-permission assignments, is considered to be an essential step in successful implementation of Role-Based Access Control (RBAC) systems. Traditional role mining techniques, however, are not equipped to handle temporal extensions of RBAC like the Temporal-RBAC (TRBAC) model. In this paper, we formally define the problem of finding a minimal set of roles from temporal user-permission assignments, such that in the resulting TRBAC system, users acquire either the same or a subset of the permissions originally assigned to them for the complete or partial durations of time as specified in the input. We show that the problem is NP-complete and propose a greedy algorithm for solving it. Our algorithm first derives a set of candidate roles from the temporal user-permission assignments and then selects the least possible number of roles from the candidate role set. The final output consists of a set of roles, a user-to-role assignment relation, a role-to-permission assignment relation and a role enabling base describing the time durations for which each role is enabled. Performance of the proposed approach has been evaluated on a number of synthetic as well as real-world datasets.

Keywords

TRBAC temporal user-permission assignment generalized temporal role mining NP-complete temporal mismatch greedy algorithm

1. Introduction

Over the years, Role-Based Access Control (RBAC) has become a well-accepted and successful model for enforcing secured access to sensitive information and restricted resources [10,34]. In RBAC, roles are defined by an organization to which users are assigned. One or more permissions are associated with each role. Users acquire necessary authorizations to access resources through these permissions by being members of appropriate roles. In an RBAC system, the set of permissions included in a role is at the disposal of any user assigned to that role for an unrestricted period of time until the role is revoked from the user, typically by an administrator. Thus, RBAC does not impose any constraint on the time duration for which roles can be available to the users. In many real-life scenarios, however, there is a need to restrict the availability of permissions to users only for specific periods of time. To achieve this, it is necessary to impose a constraint on the duration for which a user can assume a particular role assigned to him. Since the basic RBAC model cannot handle such a temporal dimension associated with roles, several extensions of RBAC have been proposed like the Temporal Role-Based Access Control (TRBAC) model [2] and the Generalized Temporal Role-Based Access Control (GTRBAC) model [23]. These models allow roles to be enabled for specific sets of time intervals and remain disabled for the rest of the time.

For organizations choosing to use RBAC, defining a complete and correct set of roles is a primary requirement. This is necessary to ensure that we can derive the most benefit from RBAC. The process of determining the set of roles is known as Role Engineering [8], which can be of two types: top-down [33] and bottom-up [9,38]. The top-down approach analyzes and decomposes the organizational business processes into smaller units in order to identify the permissions required to carry out specific tasks. It is not viable when the number of business processes, users and permissions becomes very large, consequently increasing the number of roles. In contrast, the bottom-up approach, often called role mining, forms the roles in an algorithmic way that can be easily automated. The input to role mining is a set of direct user-permission assignments. Role mining generates a set of roles, a user-role assignment relation denoting which roles are assigned to each user and a role-permission assignment relation capturing the permissions associated with each role. Various kinds of metrics have been considered for optimality during role mining, most notably the number of roles generated [35] and the weighted structural complexity [30]. Since role mining might result in roles that are semantically less meaningful, a combination of top-down and bottom-up approaches, known as hybrid role engineering, has recently been proposed [13,30].

The traditional role mining techniques [3,5,9,25,38] do not consider any temporal information that could be associated with the user-permission assignments while deriving a set of roles. Hence, these are not suitable for mining roles in the context of temporal role-based access control models like TRBAC [2]. We call such user-permission assignments as temporal user-permission assignments and the process of mining roles from them as temporal role mining. Each user, on being assigned a subset of the derived set of roles, acquires the corresponding permissions only for those durations of time for which the roles are enabled. Thus, the process of temporal role mining not only generates the set of roles, user-role assignments and role-permission assignments, but also the sets of time intervals during which each role is enabled (captured in a Role Enabling Base – REB).

It may be noted that the sets of time intervals for which users acquire various permissions through their assigned roles after role mining can be required to match either exactly or with limited deviations from the sets of time intervals for which they were originally assigned those permissions. This would depend on specific organizational needs and it affects the nature of the target role set generated by the process of temporal role mining. The problem of finding a minimal set of roles from initial temporal user-permission assignments can have different formulations depending on whether an exact or an near-to-exact (partial) match is the final objective. In this paper, a generalized formulation of the temporal role mining problem for TRBAC is presented that incorporates the notions of both exact and partial match. We name this problem as the Generalized Temporal Role Mining Problem (GTRMP).

The main contributions of the current work can be summarized as follows:

We formally define the Generalized Temporal Role Mining Problem and show it to be NP-complete. This problem definition extends the work presented in [28] by incorporating both exact and inexact variants of the problem. The acceptable level of mismatch for the inexact variant can be set appropriately by specifying the value of an input parameter to the problem.

We propose a greedy algorithm to solve GTRMP. It incorporates several improvements over the one proposed in [28].

Results of extensive experiments in terms of the number of roles produced and the overall execution time with both synthetic as well as real-world datasets are presented. These show significant improvement in comparison to the previous algorithm. Moreover, results on real-world datasets indicate that the proposed approach can be effectively used for temporal role mining in practical applications.

The proposed approach operates in two phases, namely, (a) generation of candidate roles and (b) selection of a minimum cardinality subset of candidate roles and assigning them to appropriate users so that the intended type of match (exact or partial) between the role mining output and the input temporal user-permission assignments is obtained. For the second phase, four different greedy choices are proposed using which candidate role selection can be done.

The rest of the paper is organized as follows. Section 2 discusses some of the preliminaries on RBAC, TRBAC and role mining. Section 3 formally defines the Generalized Temporal Role Mining Problem. In Section 4, we present our approach to solve the problem and illustrate its working with an example. Experimental results, both on synthetic as well as real-world datasets, are presented in Section 5. Section 6 reviews existing literature and Section 7 concludes the paper with some insight into future work.

2. Preliminaries

This section presents some of the preliminary concepts related to the RBAC and TRBAC models as well as role mining that would help in understanding our proposed work.

2.1. Role-Based Access Control (RBAC)

In the core RBAC model [10] (the ${RBAC}_{0}$ model of [34]), users are granted necessary permissions to carry out specific operations through one or more roles assigned to them. The model consists of the following components:

$USERS$ , $ROLES$ , $OPS$ and $OBJS$ are the sets of users, roles, operations and objects, respectively;

$UA \subseteq USERS \times ROLES$ , a many-to-many user-to-role assignment relation;

Set of permissions, $PRMS$ : $PRMS \subseteq {(op, obj) | op \in OPS \land obj \in OBJS}$ ;

$PA \subseteq ROLES \times PRMS$ , a many-to-many role-to-permission assignment relation;

$assigned_users : ROLES \to 2^{USERS}$ , the mapping of the set $ROLES$ onto the powerset of $USERS$ $assigned_users (r) = {u \in USERS | r \in ROLES, (u, r) \in UA}$ ;

$assigned_permissions : ROLES \to 2^{PRMS}$ , the mapping of the set $ROLES$ onto the powerset of $PRMS assigned_permissions (r) = {p \in PRMS | r \in ROLES, (r, p) \in PA}$ .

Core RBAC also has sessions, which have not been included here as they are not directly relevant in the context of role mining.

2.2. Temporal Role-Based Access Control (TRBAC)

The TRBAC model [2] is an extension of RBAC in which each role is enabled for a set of time intervals as specified in a Role Enabling Base (REB). Otherwise, they remain disabled. In order to specify the sets of time intervals for which a role can be enabled, TRBAC uses the periodic expression formalism [2]. A periodic expression denotes an infinite set of time intervals represented in terms of Calendars, each of which is a set of consecutive time intervals. Let $C_{r}, C_{1}, \dots, C_{n}$ be a set of calendars. A periodic expression P is of the form: $\begin{matrix} (1) & P = \sum_{k = 1}^{n} O_{k} \cdot C_{k} ⊳ r \cdot C_{r}, \end{matrix}$ where $O_{1} = all$ , $O_{k} \in 2^{N} \cup {all}$ , $C_{k} ⊑ C_{k - 1}$ for $k = 2, \dots, n$ , $C_{r} ⊑ C_{n}$ and $r \in N$ . ⊑ represents sub-calendar relationship. The part of the periodic expression P to the left of the symbol ⊳ represents the starting points of the time intervals given by P and the part on the right of ⊳ denotes the duration of each time interval in terms of a natural number r and calendar $C_{r}$ . To bound the infinite set of time intervals given by a periodic expression, the construct $⟨ [begin, end], P ⟩$ is used, where P is a periodic expression while $begin$ and $end$ are respectively the lower and upper limits bounding the periodic time intervals given by P.

As an example, the periodic expression $Working_Hour \equiv [all . Years + {1, 2, 8} . Months + {2, 4} . Weeks + {1, 3, 5} . Days + {9} . Hours ⊳ 8 . Hours]$ represents the set of time intervals starting at 9 AM and ending at 5 PM of every Monday, Wednesday and Friday of every second and fourth week of January, February and August of every year. An REB entry of the form: $⟨ [1 / 1 / 2010, 12 / 31 / 2011], Working_Hour, Enable Faculty ⟩$ denotes that the role $Faculty$ is enabled only during the time intervals represented by $Working_Hour$ over the two years 2010 and 2011. Thus, even if a user Alice is assigned to the role $Faculty$ , she can invoke the role (and hence, use the permissions assigned to that role) only during these time intervals.

2.3. Role mining

Role mining is the process of deriving a set of roles from direct user-permission assignments represented in the form of a boolean matrix called the UPA matrix. The rows of UPA correspond to users and the columns correspond to permissions. An entry ( $i, j$ ) of the UPA is either a 0 or a 1 depending on whether permission j has been assigned to user i or not. The output from the role mining process consists of a set of roles ROLES, a user-role assignment relation UA and a role-permission assignment relation PA. UA and PA are conveniently represented using two boolean matrices. The rows of the UA matrix correspond to users and the columns correspond to roles. A 1 in the cell ( $i, k$ ) of UA signifies that user i has been assigned role k and a 0 signifies that user i is not assigned role k. In the PA matrix, the rows and the columns correspond to roles and permissions, respectively. If permission j is included in role k, then the cell ( $k, j$ ) contains a 1, otherwise it contains a 0. The problem of finding an optimal set of roles and the corresponding UA and PA matrices from a given UPA is called the Role Mining Problem (RMP). RMP is usually posed as a minimization problem, where the objective is to minimize either the number of roles (Basic-RMP) [35], the summation of the sizes of UA and PA [25], or other metrics like the Weighted Structural Complexity (WSC) [30]. Several variants of RMP exist in the literature, such as δ-approx RMP [35], Minimal-Noise RMP [35], Edge-RMP [25], etc.

3. Mining roles in the context of TRBAC

In this section, we first describe how the temporal user-permission assignments can be represented in the form of a matrix. We then present a generalized version of the temporal role mining problem, which we name as GTRMP.

3.1. Temporal UPA matrix

Unlike the UPA matrix introduced in Section 2.3 that captures static binding of permissions to users, a temporal user-permission assignment relation describes the set of time intervals for which one or more permissions are available to each user. It is assumed that such information is available with the system administrator and is provided as input for temporal role mining. We represent these temporal assignments in the form of a matrix and name it as the Temporal UPA (TUPA) matrix. The rows of TUPA correspond to users and the columns represent permissions. Each cell ( $i, j$ ) of the matrix contains the set of time intervals $T_{i j}$ for which user i is assigned permission j. If user i is never assigned permission j, then $T_{i j} = ϕ$ . Each non-empty set of time intervals $T_{i j}$ is represented using one or more constructs of the form $⟨ [begin, end], P ⟩$ introduced in Section 2.2.

Table 1
Example Temporal User-Permission Assignment (TUPA) matrix

$p_{1}$ $p_{2}$ $p_{3}$ $p_{4}$

$u_{1}$ $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 1 . Hours ⟩$ $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 1 . Hours ⟩$ ϕ $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$

$u_{2}$ $⟨ [1 / 1 / 2009, \infty], all . Days + {7} . Hours ⊳ 1 . Hours ⟩$ , $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$ $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 1 . Hours ⟩$ $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 1 . Hours ⟩$ $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$

$u_{3}$ ϕ $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$ $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$ $⟨ [1 / 1 / 2009, \infty], all . Days + {7} . Hours ⊳ 1 . Hours ⟩$ $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$

	$p_{1}$	$p_{2}$	$p_{3}$	$p_{4}$
$u_{1}$	$⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 1 . Hours ⟩$	$⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 1 . Hours ⟩$	ϕ	$⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$
$u_{2}$	$⟨ [1 / 1 / 2009, \infty], all . Days + {7} . Hours ⊳ 1 . Hours ⟩$ , $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$	$⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 1 . Hours ⟩$	$⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 1 . Hours ⟩$	$⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$
$u_{3}$	ϕ	$⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$	$⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$	$⟨ [1 / 1 / 2009, \infty], all . Days + {7} . Hours ⊳ 1 . Hours ⟩$ $⟨ [1 / 1 / 2009, \infty], all . Days + {9} . Hours ⊳ 2 . Hours ⟩$

Table 1 shows an example TUPA matrix in which user $u_{1}$ is assigned permissions $p_{1}$ and $p_{2}$ for the set of time intervals: everyday from 9 AM to 10 AM. $u_{1}$ is also assigned $p_{4}$ for the set of time intervals: everyday from 9 AM to 11 AM. Since $u_{1}$ is not assigned permission $p_{3}$ , the cell ( $u_{1}, p_{3}$ ) contains ϕ. $u_{2}$ is assigned $p_{1}$ for two different sets of time intervals: everyday from 7 AM to 8 AM and from 9 AM to 11 AM. Since the durations are different (respectively 1 hour and 2 hours), two different periodic expressions (Eq. (1)) are needed to represent these two sets of time intervals. $u_{2}$ is also assigned $p_{2}$ and $p_{3}$ everyday from 9 AM to 10 AM and $p_{4}$ everyday from 9 AM to 11 AM. Finally, $u_{3}$ is assigned $p_{2}$ and $p_{3}$ each for the same set of time intervals: everyday from 9 AM to 11 AM and is assigned $p_{4}$ for the sets of time intervals: everyday from 7 AM to 8 AM and from 9 AM to 11 AM. Thus, a user can be assigned a single permission for more than one set of time intervals and also different permissions for the same or different sets of time intervals. Moreover, the same permission can be assigned to different users for the same or different sets of time intervals. The sets of time intervals that are not identical can be either intersecting or disjoint.

3.2. Generalized Temporal Role Mining Problem (GTRMP)

Given a TUPA matrix as input, temporal role mining derives a set of roles ROLES, a user-role assignment relation UA, a role-permission assignment relation PA and a role enabling base REB. UA and PA are boolean matrices similar to the ones obtained through traditional role mining as described in Section 2.3. The need to generate the REB makes the temporal role mining process different and more challenging than the traditional role mining algorithms.

Once temporal role mining is complete and a TRBAC system has been obtained, the sets of time intervals for which the users acquire various permissions through roles and their enabling conditions, can be determined from UA, PA and REB. These temporal user-permission assignments in the generated TRBAC system either match exactly or there are some mismatches with the TUPA, which could be of the following types:

Mismatch in the set of permissions of any user.

Mismatch only in the set of time intervals during which any permission is available to a user.

Mismatch both in the set of permissions and the time intervals of availability of those permissions.

Thus, depending on the type of mismatch, the following situations may arise (under closed world assumption, where only more restricted availability of permissions to users is considered):

one or more users acquire less number of permissions after temporal role mining than they were originally assigned;

while the users acquire only those permissions that were originally assigned to them, the sets of time intervals for which they get these permissions are subsets of the sets of time intervals corresponding to the original permission assignments;

a combination of the two.

We say that the output of temporal role mining is temporally δ-consistent with the input TUPA, if there are δ or lesser number of mismatches of the types mentioned above. We call δ as the temporal mismatch limit. Depending on the value of δ, the problem of temporal role mining can have two versions: the exact version in which

δ = 0

and the inexact version where

δ \neq 0

. Combining the two, we introduce a generalized formulation of the problem of temporal role mining, which we name as the Generalized Temporal Role Mining Problem (GTRMP). GTRMP can be formally defined as follows.

Definition 1 (Generalized Temporal Role Mining Problem (GTRMP)).

Given a set of users USERS, a set of permissions PRMS, a temporal user-permission assignment TUPA and a temporal mismatch limit $δ ⩾$ 0, find a set of roles ROLES, a user-role assignment UA, a role-permission assignment PA and a role enabling base REB, temporally δ-consistent with the TUPA such that the total number of roles is minimized.

Note that an exact version of the problem where $δ = 0$ , was introduced as the Temporal Role Mining Problem (TRMP) in [28]. Hence, TRMP is a special case of GTRMP. From Definition 1, it is evident that the value of δ would affect the number of roles generated. For the same input TUPA, the number of roles generated for $δ = 0$ is likely to be higher than that for $δ > 0$ . Although a non-zero value of δ implies that the generated TRBAC system is not an accurate representation of the original direct temporal user-permission assignments, yet, as has been mentioned in [35], minor mismatches are usually tolerable especially if there is a significant reduction in the number of generated roles. It may be noted that, while GTRMP as defined above aims to minimize the size of the mined role set, other metrics for minimization, such as, the sizes of UA and PA as well as the sizes of the REB and role hierarchy may also be considered. Various non-temporal role mining algorithms have previously been proposed that minimize the sizes of the UA, PA and role hierarchy [16,25,29]. However, consideration of such metrics is not within the scope of the current work.

It needs to be emphasized here that, GTRMP is not a trivial extension of δ-approx RMP introduced in [35], where the threshold is simply the number of 0s and 1s obtained by combining the UA and PA matrices generated by the role mining procedure that do not match with the input UPA matrix. GTRMP can be reduced to δ-approx RMP if a mismatch only in the permission component of the temporal mismatch limit δ is considered and the sets of time intervals corresponding to all the input temporal user-permission assignments are taken to be the same. Thus, δ-approx RMP is also a special case of GTRMP. Besides, the sets of time intervals corresponding to the temporal user-permission assignments can span over several calendars and can be different from each other.

The Generalized Temporal Role Mining Problem is NP-complete. The proof is given in the Appendix.

4. Greedy algorithm for solving GTRMP

In this section, we propose a heuristic algorithm for solving GTRMP that takes as input a TUPA matrix and a value of the temporal mismatch limit δ. We first generate a set of candidate roles from TUPA. A greedy heuristic then selects the least possible number of roles out of these candidate roles so that the output is temporally δ-consistent with the TUPA. This section also illustrates the working of our approach using an example.

4.1. Algorithm description

The following two sub-sections describe our approach for solving GTRMP using two phases.

4.1.1. Creation of candidate roles

We first describe how the set of candidate roles is created from an input TUPA matrix. The set of candidate roles consists of three types of roles – unit roles, initial roles and generated roles.

Unit roles. As mentioned in Section 3.1, each user-permission combination in TUPA consists of one or more entries of the form $⟨ [begin, end], P ⟩$ . The user, his assigned permission, and the corresponding periodic expression form a triple $⟨ u_{i}, p_{j}, T_{i j} ⟩$ , denoting that user $u_{i}$ is assigned permission $p_{j}$ for the set of time intervals $T_{i j}$ . Let Γ be the set of all such triples. Since a role in TRBAC is a collection of permissions assigned to a set of users and enabled for a specific set of time intervals, each triple $⟨ u_{i}, p_{j}, T_{i j} ⟩$ in Γ can be thought of as a role consisting of a single permission, enabled for a single set of time intervals and assigned to a single user. We call these roles as unit roles. The set of all unit roles is named as $UnitRoles$ .

Initial roles. In this step, for each user, one or more initial roles are created by taking into consideration the set of time intervals corresponding to each permission assignment. If one or more permissions are assigned to a user u for the same set of time intervals, then the user u, the assigned permissions and the corresponding set of time intervals are combined together to create an initial role.

We illustrate the process of creating the set of initial roles, denoted by $InitialRoles$ , using the following example: Let a user $u_{1}$ be assigned three permissions – $p_{1}$ for the set of time intervals $T_{11}$ , $p_{2}$ for the set of time intervals $T_{12}$ and $p_{3}$ for the set of time intervals $T_{13}$ . Now, depending on how $T_{11}$ , $T_{12}$ and $T_{13}$ are related to one another, different types of roles would be created.

If $T_{11} = T_{12} = T_{13}$ , then a single role r is created consisting of $p_{1}$ , $p_{2}$ and $p_{3}$ assigned to $u_{1}$ and enabled during $T_{11}$ .

If $T_{11} = T_{12} \neq T_{13}$ , then two roles are created: (i) r consisting of $p_{1}$ and $p_{2}$ assigned to $u_{1}$ and enabled during $T_{11}$ , (ii) $r^{'}$ consisting of $p_{3}$ assigned to $u_{1}$ and enabled during $T_{13}$ .

If $T_{11} \neq T_{12} = T_{13}$ , then two roles are created: (i) r consisting of $p_{2}$ and $p_{3}$ assigned to $u_{1}$ and enabled during $T_{12}$ , (ii) $r^{'}$ consisting of $p_{1}$ assigned to $u_{1}$ and enabled during $T_{11}$ .

If $T_{11} = T_{13} \neq T_{12}$ , then two roles are created: (i) r consisting of $p_{1}$ and $p_{3}$ assigned to $u_{1}$ and enabled during $T_{11}$ , (ii) $r^{'}$ consisting of $p_{2}$ assigned to $u_{1}$ and enabled during $T_{12}$ .

If $T_{11} \neq T_{12} \neq T_{13}$ , then three roles are created: (i) r consisting of $p_{1}$ assigned to $u_{1}$ and enabled during $T_{11}$ , (ii) $r^{'}$ consisting for $p_{2}$ assigned to $u_{1}$ and enabled during $T_{12}$ , (iii) $r^{″}$ consisting of $p_{3}$ assigned to $u_{1}$ and enabled during $T_{13}$ .

In general, if a user is assigned n permissions and t distinct sets of time intervals exist across those n permission assignments, then a total of t initial roles will be created for that user.

Generated roles. Pairwise intersection among the initial roles is next carried out to create roles consisting of a set of permissions and a set of time intervals that are common between any two users. We call this set of newly created roles as $GeneratedRoles$ . While performing pairwise intersection among the initial roles, both the permission and time interval components are taken into consideration. Let $r_{1}$ and $r_{2}$ be two initial roles such that, $r_{1}$ consisting of the set of permissions ${p_{1}, \dots, p_{i - 1}, p_{i}, \dots, p_{j}}$ is assigned to $u_{1}$ and is enabled during $T_{1}$ , while $r_{2}$ consisting of the permission set ${p_{i}, \dots, p_{j}, p_{j + 1}, \dots, p_{k}}$ is assigned to $u_{2}$ and is enabled during $T_{2}$ ( $i < j < k$ ). In order to represent the set of users $U_{i}$ who have been assigned a particular role $r_{i}$ , the set of permissions $P_{i}$ included in $r_{i}$ and the set of time intervals $T_{i}$ during which $r_{i}$ can be enabled, we use the following notation: $r_{i} = (U_{i}, P_{i}, T_{i})$ . Thus, $r_{1}$ and $r_{2}$ can be represented as: $r_{1} = ({u_{1}}, {p_{1}, \dots, p_{i - 1}, p_{i}, \dots, p_{j}}, T_{1})$ and $r_{2} = ({u_{2}}, {p_{i}, \dots, p_{j}, p_{j + 1}, \dots, p_{k}}, T_{2})$ . If $T_{1} \cap T_{2} \neq ϕ$ , then the following generated roles are created:

$r_{3} = ({u_{1}, u_{2}}, {p_{i}, \dots, p_{j}}, T_{1} \cap T_{2})$ ;

$r_{4} = ({u_{1}}, {p_{i}, \dots, p_{j}}, T_{1} ∖ (T_{1} \cap T_{2}))$ ;

$r_{5} = ({u_{2}}, {p_{i}, \dots, p_{j}}, T_{2} ∖ (T_{1} \cap T_{2}))$ ;

$r_{6} = ({u_{1}}, {p_{1}, \dots, p_{i - 1}}, T_{1})$ ;

$r_{7} = ({u_{2}}, {p_{j + 1}, \dots, p_{k}}, T_{2})$ .

Role $r_{3}$ is created by combining the associated users, the common permissions and the common set of time intervals of $r_{1}$ and $r_{2}$ . As a result, the sets of time intervals corresponding to the common permissions of roles $r_{1}$ and $r_{2}$ , i.e., $p_{i}, \dots, p_{j}$ get split (if $T_{1} \neq T_{2}$ ). So, two roles $r_{4}$ and $r_{5}$ are created consisting of the corresponding users, the common permissions of $r_{1}$ and $r_{2}$ as well as the remaining sets of time intervals (if any) associated with $r_{1}$ and $r_{2}$ . Role $r_{6}$ is created by combining user $u_{1}$ , the permissions of $r_{1}$ that are not present in $r_{2}$ and the set of time intervals during which $r_{1}$ is enabled. Similarly, $r_{7}$ is created by combining user $u_{2}$ , the permissions of $r_{2}$ that are not present in $r_{1}$ and the set of time intervals during which $r_{2}$ is enabled. Depending on whether one of $T_{1}$ and $T_{2}$ is a subset of the other or they are equal, any one or both of $r_{4}$ and $r_{5}$ may be superfluous and are removed.

The set of candidate roles, denoted by $CandidateRoles$ is created by taking the union of $UnitRoles$ , $InitialRoles$ and $GeneratedRoles$ . In the final step of candidate role creation, two candidate roles $r_{a} = (U_{a}, P_{a}, T_{a})$ and $r_{b} = (U_{b}, P_{b}, T_{b})$ are merged to create a single role $r_{c}$ if any one of the following conditions is satisfied:

$U_{a} = U_{b}$ and $T_{a} = T_{b}$ , then $r_{c} = (U_{a}, P_{a} \cup P_{b}, T_{a})$ ;

$P_{a} = P_{b}$ and $T_{a} = T_{b}$ , then $r_{c} = (U_{a} \cup U_{b}, P_{a}, T_{a})$ ;

$U_{a} = U_{b}$ , $P_{a} = P_{b}$ and $T_{a}$ and $T_{b}$ are consecutive or are overlapping or one is contained in the other, then $r_{c} = (U_{a}, P_{a}, T_{a} \cup T_{b})$ .

$CandidateRoles$ , thus, contains the roles that have a possibility of being part of the final set of roles produced as output of the complete temporal role mining process.

4.1.2. Role selection

The set $CandidateRoles$ is given as input to the role selection phase. In this phase, a minimal cardinality subset of the set of candidate roles is selected using a greedy heuristic so that the number of mismatched temporal user-permission assignments is less than or equal to δ. Let C be the set of candidate roles. Let a role $r_{k} \in C$ has a set of users $U_{k}$ associated with it and a set of permissions $P_{k}$ included in it. Let $r_{k}$ be enabled for the set of time intervals $T_{k}$ . For any triple $⟨ u_{i}, p_{j}, T_{i j} ⟩$ of the TUPA matrix to be covered by $r_{k}$ , we must have $u_{i} \in U_{k}$ and $p_{j} \in P_{k}$ . Further, if $T_{i j} \subseteq T_{k}$ , the triple is fully covered by $r_{k}$ and if $T_{k} \subset T_{i j}$ , then the triple is partially covered by $r_{k}$ . Otherwise, $r_{k}$ does not cover $⟨ u_{i}, p_{j}, T_{i j} ⟩$ . The above definition of coverage of a triple by a role can be extended to the coverage of a triple by a set of roles.

At the end of the role selection phase, at least $| Γ | - δ$ number of triples are to be fully covered by the selected set of roles, so that the sum of the number of partially covered and uncovered triples is less than or equal to δ. In each iteration, the role that appears to be the best possible option is selected using a greedy heuristic. In this paper, we propose four greedy choices as described below.

Strict Coverage of Triples (SCT): Select the role that fully covers the maximum number of uncovered or already partially covered triples. If there is a tie, break the tie by selecting the role that partially covers the maximum number of uncovered or already partially covered triples.

Weak Coverage of Triples (WCT): Select the role that covers (either fully or partially) the maximum number of uncovered or already partially covered triples. If there is a tie, break the tie by selecting the role that fully covers the maximum number of uncovered or already partially covered triples.

Strict Coverage of Uncovered Triples (SCUT): Select the role that fully covers the maximum number of uncovered triples. If there is a tie, break the tie by selecting the role that partially covers the maximum number of uncovered triples. If no such role exists, select the role that fully covers the maximum number of already partially covered triples and break the tie by selecting the role that partially covers the maximum number of already partially covered triples.

Weak Coverage of Uncovered Triples (WCUT): Select the role that covers (either fully or partially) the maximum number of uncovered triples. If there is a tie, break the tie by selecting the role that fully covers the maximum number of uncovered triples. If no such role exists, select the role that covers (either fully or partially) the maximum number of already partially covered triples and break the tie by selecting the role that fully covers the maximum number of already partially covered triples.

Since at least $| Γ | - δ$ number of triples of the TUPA matrix need to be fully covered, it is beneficial to fully cover higher number of triples in each iteration. Thus, full coverage of triples is always given higher priority over partial coverage. Moreover, assigning a permission to a user for a limited time duration is less restrictive than not assigning that permission at all for the same total number of allowable mismatches. So, it is preferred to have lesser number of uncovered triples than partially covered triples remaining on completion of all the steps, and hence, higher weightage is given to partially covering all triples rather than leaving some of them uncovered.

SCT gives priority to roles that fully cover more number of triples in a single iteration. Its tie breaking logic ensures that triples that remain partially covered as a result of selecting a role in a particular iteration may be covered fully by some other role in a subsequent iteration, and in the final output, lesser number of uncovered triples are present than partially covered ones. In contrast, WCT selects roles in such a manner that both full and partial coverage of triples are ensured as a specific number of triples need to be fully covered and also it is desirable to have lesser number of triples left uncovered. WCT breaks ties in such a manner that more number of triples get fully covered in each iteration.

SCUT initially tries to select a role that fully covers the maximum number of triples not covered so far. This implies that SCUT gives higher priority to the uncovered triples over the partially covered ones, as we intend to have less number of uncovered triples at the end of role selection. Tie is broken by selecting the role that fully covers the maximum number of uncovered triples, thereby giving precedence to roles that will result in more number of uncovered triples getting fully covered after being selected. Proceeding in this manner, after first few iterations, every triple of the TUPA will be partially covered. In successive iterations, roles that fully cover the maximum number of such already partially covered triples are selected and if there is a tie, it is broken by selecting the role that partially covers the maximum number of already partially covered triples, thereby preferring triples getting partially covered rather than remaining uncovered. In contrast, WCUT first selects those roles that cover (either fully or partially) more number of uncovered triples, thus giving priority to full and partial coverage of triples as opposed to their remaining uncovered. Tie is broken by giving preference to the role that fully covers more number of uncovered triples. Subsequently, when some of the triples get fully covered and the rest get partially covered, WCUT selects a role that covers (either fully or partially) the maximum number of triples that are already partially covered, and in the event of a tie, breaks it by selecting the role that partially covers the highest number of already partially covered triples.

Thus, SCT and WCT do not take into explicit consideration whether a particular triple has already been partially covered during role selection, whereas SCUT and WCUT first consider only those triples that have not been covered so far while selecting a role. Hence, SCT and WCT as well as SCUT and WCUT are pairs of complementary choices, i.e., the initial criterion for role selection in one becomes the criterion for tie breaking in the other. The four choices for role selection essentially differ from each other with regard to the nature of coverage of the different types of triples.

After the best candidate role is selected in each iteration, the fully and partially covered triples are marked appropriately and Γ is updated. The algorithm terminates when $| Γ | - δ$ number of triples are fully covered. At the end of the role selection phase, it is checked whether two or more of the selected roles can be merged further. While merging, besides considering the criteria similar to those considered during merging of candidate roles discussed in Section 4.1.1, one more criterion is considered: two roles are merged if their associated user sets and permission sets are identical, but the sets of time intervals are different. The resulting single role is enabled for two separate sets of time intervals. This final merging step further reduces the number of roles.

We summarize the steps of our proposed approach before presenting the detailed algorithms.

Candidate role generation:

Creation of three types of roles from the input TUPA:

Unit roles: Single permission roles that can be assigned to a single user and can be enabled for a single set of time intervals, created corresponding to each triple of the TUPA.

Initial roles: Created by combining the different permissions assigned to a single user for the same sets of time intervals.

Generated roles: Produced by performing pairwise intersection among the initial roles.

Creation of candidate role set by taking union of the sets of unit, initial and generated roles.

Merging of appropriate candidate roles.

Role selection:

Iterative selection of a minimal cardinality subset of the candidate role set using any one of the four greedy heuristics, namely, SCT, WCT, SCUT and WCUT.

Selecting the best candidate role in each iteration and updating the TUPA.

Execution stops when required number of triples have been fully covered.

Further merging among the selected candidate roles, if possible.

Generating the set of roles R, the user-role assignment relation UA, the role-permission assignment relation PA and the role enabling base REB as output.

The algorithm for determining the set of candidate roles (Det-Cand-Roles) is shown in Algorithm 1. Line 1 initializes $UnitRoles$ , $InitialRoles$ , $GeneratedRoles$ and $CandidateRoles$ as empty sets. Lines 2–5 create the set of unit roles. The set $InitialRoles$ is created in Lines 6–9. By performing pairwise intersection between the initial roles, the set $GeneratedRoles$ is created in Lines 10–22. In Line 23, the set $CandidateRoles$ is created by taking union of the sets $UnitRoles$ , $InitialRoles$ and $GeneratedRoles$ . Finally, in Lines 24–43, it is checked whether any of the candidate roles can be merged with any other candidate role. If so, then the merging operation is carried out.

Algorithm 1.

Det-Cand-Roles

Algorithm 2.

Sel-Fin-Roles

The algorithm for selecting the final set of roles (Sel-Fin-Roles) is shown in Algorithm 2. The input to Sel-Fin-Roles is the set $CandidateRoles$ generated by the Det-Cand-Roles algorithm. The variables $entry_count$ and $fully_covered$ respectively denote the number of triples of Γ that are yet to be fully covered and the number of triples of Γ fully covered in a particular iteration. Line 1 initializes $entry_count$ to $| Γ | - δ$ . The while loop of Lines 2–9 iterates till the required number of triples are fully covered. In Line 3, a candidate role is selected using any one of the four greedy choices described earlier in this sub-section. If a tie occurs, it is broken using the tie breaking logic (Line 5) corresponding to the greedy choice used in Line 3. The set Γ and the variable $entry_count$ are updated in Lines 7 and 8 respectively. Merging of the selected roles is carried out in Line 10. Finally, UA, PA and REB are created from the set of selected roles in Line 11.

The overall time complexity is $O (m^{2} n^{2} t^{2})$ where m is the number of users, n is the number of permissions and t is the number of distinct sets of time intervals in the TUPA matrix.

Table 2

Simplified representation of the TUPA shown in Table 1

	$p_{1}$	$p_{2}$	$p_{3}$	$p_{4}$
$u_{1}$	9 AM–10 AM	9 AM–10 AM	ϕ	9 AM–11 AM
$u_{2}$	7 AM–8 AM9 AM–11 AM	9 AM–10 AM	9 AM–10 AM	9 AM–11 AM
$u_{3}$	ϕ	9 AM–11 AM	9 AM–11 AM	7 AM–8 AM9 AM–11 AM

4.2. Illustrative example

We illustrate the working of our proposed approach with the help of the TUPA given in Table 2, which is a simplified representation of the TUPA of Table 1.

Candidate role generation

The TUPA matrix is given as input to the algorithm Det-Cand-Roles. First, the set $UnitRoles$ is constructed consisting of the following roles. $\begin{array}{rcl} UnitRoles & = & {r_{1} = ({u_{1}}, {p_{1}}, {9 AM–10 AM}), \\ r_{2} = ({u_{1}}, {p_{2}}, {9 AM–10 AM}), \\ r_{3} = ({u_{1}}, {p_{4}}, {9 AM–11 AM}), \\ r_{4} = ({u_{2}}, {p_{1}}, {7 AM–8 AM}), \\ r_{5} = ({u_{2}}, {p_{1}}, {9 AM–11 AM}), \\ r_{6} = ({u_{2}}, {p_{2}}, {9 AM–10 AM}), \\ r_{7} = ({u_{2}}, {p_{3}}, {9 AM–10 AM}), \\ r_{8} = ({u_{2}}, {p_{4}}, {9 AM–11 AM}), \\ r_{9} = ({u_{3}}, {p_{2}}, {9 AM–11 AM}), \\ r_{10} = ({u_{3}}, {p_{3}}, {9 AM–11 AM}), \\ r_{11} = ({u_{3}}, {p_{4}}, {7 AM–8 AM}), \\ r_{12} = ({u_{3}}, {p_{4}}, {9 AM–11 AM})} . \end{array}$ Next, the set of initial roles is constructed by considering the individual users in the TUPA matrix. $\begin{array}{rcl} InitialRoles & = & {r_{13} = ({u_{1}}, {p_{1}, p_{2}}, {9 AM–10 AM}), \\ r_{14} = ({u_{1}}, {p_{4}}, {9 AM–11 AM}), \\ r_{15} = ({u_{2}}, {p_{1}}, {7 AM–8 AM}), \\ r_{16} = ({u_{2}}, {p_{1}, p_{4}}, {9 AM–11 AM}), \\ r_{17} = ({u_{2}}, {p_{2}, p_{3}}, {9 AM–10 AM}), \\ r_{18} = ({u_{3}}, {p_{2}, p_{3}, p_{4}}, {9 AM–11 AM}), \\ r_{19} = ({u_{3}}, {p_{4}}, {7 AM–8 AM})} . \end{array}$ The set $GeneratedRoles$ is created by taking pairwise intersection of the initial roles. $\begin{array}{rcl} GeneratedRoles & = & {r_{20} = ({u_{1}, u_{2}}, {p_{1}}, {9 AM–10 AM}), \\ r_{21} = ({u_{2}}, {p_{1}}, {10 AM–11 AM}), \\ r_{22} = ({u_{1}}, {p_{2}}, {9 AM–10 AM}), \\ r_{23} = ({u_{2}}, {p_{4}}, {9 AM–11 AM}), \\ r_{24} = ({u_{1}, u_{2}}, {p_{2}}, {9 AM–10 AM}), \\ r_{25} = ({u_{1}}, {p_{1}}, {9 AM–10 AM}), \\ r_{26} = ({u_{2}}, {p_{3}}, {9 AM–10 AM}), \\ r_{27} = ({u_{1}, u_{3}}, {p_{2}}, {9 AM–10 AM}), \\ r_{28} = ({u_{3}}, {p_{2}}, {10 AM–11 AM}), \\ r_{29} = ({u_{3}}, {p_{3}, p_{4}}, {9 AM–11 AM}), \\ r_{30} = ({u_{1}, u_{2}}, {p_{4}}, {9 AM–11 AM}), \\ r_{31} = ({u_{2}}, {p_{1}}, {9 AM–11 AM}), \\ r_{32} = ({u_{1}, u_{3}}, {p_{4}}, {9 AM–11 AM}), \\ r_{33} = ({u_{3}}, {p_{2}, p_{3}}, {9 AM–11 AM}), \\ r_{34} = ({u_{2}, u_{3}}, {p_{4}}, {9 AM–11 AM}), \\ r_{35} = ({u_{2}, u_{3}}, {p_{2}, p_{3}}, {9 AM–10 AM}), \\ r_{36} = ({u_{3}}, {p_{2}, p_{3}}, {10 AM–11 AM}), \\ r_{37} = ({u_{3}}, {p_{4}}, {9 AM–11 AM})} . \end{array}$ Finally, the set of candidate roles is created by taking the union of $UnitRoles$ , $InitialRoles$ and $GeneratedRoles$ . After merging the appropriate roles and renaming, the set $CandidateRoles$ is produced as follows. $\begin{array}{rcl} CandidateRoles & = & {r_{1} = ({u_{1}}, {p_{1}, p_{2}}, {9 AM–10 AM}), \\ r_{2} = ({u_{2}, u_{3}}, {p_{2}, p_{3}}, {9 AM–10 AM}), \\ r_{3} = ({u_{1}, u_{2}, u_{3}}, {p_{4}}, {9 AM–11 AM}), \\ r_{4} = ({u_{2}}, {p_{1}, p_{4}}, {9 AM–11 AM}), \\ r_{5} = ({u_{3}}, {p_{2}, p_{3}, p_{4}}, {9 AM–11 AM}), \\ r_{6} = ({u_{2}}, {p_{1}}, {7 AM–8 AM}), \\ r_{7} = ({u_{3}}, {p_{4}}, {7 AM–8 AM}), \\ r_{8} = ({u_{1}, u_{2}, u_{3}}, {p_{2}}, {9 AM–10 AM}), \\ r_{9} = ({u_{1}, u_{2}}, {p_{1}}, {9 AM–10 AM}), \\ r_{10} = ({u_{2}}, {p_{3}}, {9 AM–10 AM}), \\ r_{11} = ({u_{2}}, {p_{1}}, {10 AM–11 AM}), \\ r_{12} = ({u_{3}}, {p_{2}, p_{3}}, {10 AM–11 AM})} . \end{array}$

Role selection

The algorithm Sel-Fin-Roles takes the set $CandidateRoles$ as input and selects the best candidate role in each iteration. We illustrate the working of this phase of our approach by considering the four greedy choices introduced in Section 4.1.2. Table 3 shows which roles are involved in a tie and which role finally gets selected in each iteration for the four greedy choices. All the four greedy choices result in seven roles for $δ = 0$ . However, the order in which these roles are selected and also the roles that are involved in a tie in a particular iteration are different, thereby showing that the four greedy choices prefer different types of roles during selection. In our current example, the selected roles cannot be merged further. After sorting the roles according to their indices, the final UA, PA and REB are shown in Tables 4(a)–(c). For the sake of brevity, we show only the periodic expressions for the roles in the REB.

If the value of δ is set to 2, then the final number of roles would be 5 if SCT or WCT is used, whereas it would be 6 if SCUT or WCUT is used. The cells highlighted in gray in Table 3 indicate the roles that are not selected when $δ = 2$ . For SCT and WCT, the roles $r_{1}$ , $r_{2}$ , $r_{3}$ , $r_{4}$ and $r_{5}$ are selected and the triples $⟨ u_{2}, p_{1}, 7 AM–8 AM ⟩$ and $⟨ u_{3}, p_{4}, 7 AM–8 AM ⟩$ remain uncovered. For SCUT and WCUT, the roles $r_{1}$ , $r_{2}$ , $r_{3}$ , $r_{4}$ , $r_{6}$ and $r_{7}$ are selected and the triples $⟨ u_{3}, p_{2}, 9 AM–11 AM ⟩$ and $⟨ u_{3}, p_{3}, 9 AM–11 AM ⟩$ remain partially covered.

Table 3
Candidate role selection

Table 4

Output for the TUPA of Table 2

5. Experimental results

In this section, we evaluate the performance of our proposed approach in terms of the number of roles produced and the overall execution time. The algorithms were implemented in C on a 3 GHz Core 2 Duo processor machine having 2 GB memory and running Fedora 13 as the operating system. We carried out experiments using both synthetically generated datasets as well as real-world datasets. Appropriate code optimization was done to reduce the overall execution time. During the creation of initial and generated roles, whenever a new role is created, it is first checked if any existing role contains the same set of permissions and is enabled for the same set of time intervals. If so, the two sets of users are merged. As a result, the sizes of the initial and generated role sets are reduced, which in turn reduces the time required to create the candidate role set. Creating the initial and generated roles in this manner also decreases the overall execution time if the number of distinct sets of time intervals is increased, which is reflected in the experimental results. We conclude this section with a discussion, summarizing the observations from the results of both types of datasets.

5.1. Results on synthetic datasets

This sub-section first describes how the synthetic datasets are generated followed by results of our experiments on these datasets.

5.1.1. Dataset generation

For synthetically generating the datasets, a simulator has been built that creates TUPA matrices of different dimensions. For our experiments, number of users has been taken to be 100, 200 and 400 and the number of permissions is considered to be half, equal and double the number of users. The number of distinct sets of time intervals is varied from 1 to 3. When it is 1, all the permissions are assigned for the same set of time intervals. This case is denoted as 1D. When 2 distinct sets of time intervals are present, they can be related to one another in three different ways: (i) one set of time intervals contains the other (2C), (ii) the two sets of time intervals intersect, but neither contains the other (2O) and (iii) the two sets of time intervals are mutually disjoint (2D). For 3 distinct sets of time intervals, the interrelationships are of the following types: (i) two sets of time intervals intersect one another, but neither of them contains the other and the third one is disjoint from the two (2O1D), (ii) all the three sets of time intervals are mutually disjoint (3D), (iii) one set of time intervals contains another and the third is disjoint from the two (2C1D), (iv) one set of time intervals contains the other, which in turn contains the third (3C) and (v) all the three sets of time intervals intersect one another, but none of them contains any of the remaining two (3O). Each user-permission assignment of the TUPA matrices is randomly associated with one or more of the above mentioned types of sets of time intervals when the distinct sets of time intervals is 2 and 3. The value of the temporal mismatch limit δ is taken as 0, 0.5, 1 and 2 percent of the total number of triples in the TUPA. Since these datasets are randomly generated, each experiment was repeated 30 times. For all the experiments, we report the median number of roles obtained and the mean execution time over all 30 runs. In our results, we show how the number of roles produced and the execution time of our approach are affected due to variation in the number of users, number of permissions, value of δ and the different time interval relationships. Performance of all the four proposed heuristics were found to be similar both in terms of the number of roles and the execution time, with the SCT heuristic described in Section 4.1.2 producing the best results in most of the cases. Hence in the rest of this section, we report the results obtained by using SCT for role selection.

5.1.2. Results

Tables 5–7 show the median number of roles obtained when the number of users are 100, 200 and 400, respectively. Results have been reported in each of the three tables for all the nine cases of time interval relationships mentioned in the previous sub-section and for all values of δ.

Table 5
Number of roles for 100 users

δ (%) No. of perms. Time interval type

1D 2C 2O 2D 2O1D 3D 2C1D 3C 3O

0.0 50 5 7 7 7 7 7 6 6 7

100 5 7 7 7 7 6 7 6 7

200 5 7 7 8 7 7 7 7 7

0.5 50 5 6 7 7 6 7 6 6 7

100 5 7 6 6 7 6 7 6 7

200 5 6 7 7 7 6 7 7 7

1.0 50 5 6 6 6 6 6 6 6 6

100 5 6 6 6 6 6 6 6 7

200 5 6 6 6 6 6 6 6 6

2.0 50 5 5 6 6 5 6 5 5 6

100 5 5 5 6 6 5 5 5 6

200 5 5 6 6 6 6 6 5 6

δ (%)	No. of perms.	Time interval type
0.0	50	5	7	7	7	7	7	6	6	7
100	5	7	7	7	7	6	7	6	7
200	5	7	7	8	7	7	7	7	7
0.5	50	5	6	7	7	6	7	6	6	7
100	5	7	6	6	7	6	7	6	7
200	5	6	7	7	7	6	7	7	7
1.0	50	5	6	6	6	6	6	6	6	6
100	5	6	6	6	6	6	6	6	7
200	5	6	6	6	6	6	6	6	6
2.0	50	5	5	6	6	5	6	5	5	6
100	5	5	5	6	6	5	5	5	6
200	5	5	6	6	6	6	6	5	6

Table 6

Number of roles for 200 users

δ (%)	No. of perms.	Time interval type

		1D	2C	2O	2D	2O1D	3D	2C1D	3C	3O
0.0	100	10	39	52	55	46	47	43	38	48
	200	10	49	61	60	48	54	48	42	51
	400	10	51	59	65	56	63	59	43	61
0.5	100	10	26	35	36	30	32	28	25	31
	200	10	32	39	37	31	34	30	27	34
	400	10	30	36	40	36	38	36	26	37
1.0	100	10	22	29	30	25	28	24	21	26
	200	10	26	32	31	27	29	25	22	28
	400	10	24	30	33	30	32	29	22	31
2.0	100	10	18	23	24	21	22	20	16	22
	200	10	20	26	24	22	23	20	18	22
	400	10	19	24	26	24	25	23	18	24

Table 7

Number of roles for 400 users

δ (%)	No. of perms.	Time interval type

		1D	2C	2O	2D	2O1D	3D	2C1D	3C	3O
0.0	200	20	24	25	25	25	24	24	23	24
	400	20	28	28	27	28	28	28	27	29
	800	20	33	33	36	33	33	32	32	34
0.5	200	20	20	21	21	21	21	21	20	21
	400	20	22	23	22	23	22	22	22	23
	800	20	24	24	25	24	24	24	23	24
1.0	200	20	20	20	20	20	20	20	20	20
	400	20	21	21	20	21	20	20	20	21
	800	20	21	22	23	21	22	22	21	21
2.0	200	20	20	20	20	20	20	20	20	20
	400	20	20	20	20	20	20	20	20	20
	800	20	20	20	20	20	20	20	20	20

The temporal role mining problem reduces to the non-temporal role mining problem for case 1D with $δ = 0 %$ . The number of roles generated is the same as the number of roles that would have been produced by a non-temporal role mining algorithm, which are respectively 5, 10 and 20 for the datasets with 100, 200 and 400 users. This gives an indication of the validity of our approach. As the value of δ increases, the final number of roles gets reduced as expected. This reduction is most prominent for the datasets with 200 users for 2 and 3 distinct sets of time intervals, where, for $δ = 2 %$ , the number of roles is less than half of that obtained for $δ = 0 %$ . For the datasets with 100 and 400 users, the total number of roles for higher values of δ is equal to that produced by a non-temporal role mining algorithm.

It may be observed from the tables that, cases 2C and 3C respectively produce the least number of roles among all the combinations of 2 and 3 distinct sets of time intervals most of the time. In these cases, due to containment of the sets of time intervals, a user is effectively assigned a permission for a single set of time intervals, thereby resulting in limited number of time interval splitting during role selection. The number of roles obtained for cases 2O, 2O1D and 3O are most of the times higher than those obtained for cases 2C, 2C1D and 3C, respectively, since overlapping time intervals result in more splitting of time intervals than contained time intervals. However, cases 2C1D and 2O1D produce equal number of roles in many cases. Presence of the single disjoint set of time intervals effectively increases the total number of distinct sets of time intervals from 1 to 2 for case 2C1D in comparison to cases 2C and 3C, but for 2O1D, the total number of distinct sets of time intervals remains 3. As a result, 2C1D sometimes produces the same number of roles as that produced by 2O1D, which is not observed for cases 2C–2O and 3C–3O. Disjoint sets of time intervals, though do not result in time interval splitting, increase the effective number of distinct sets of time intervals in comparison to contained sets of time intervals. So, case 2D, in general, generates more roles than 2C and cases 3D and 2C1D produce higher number of roles than 3C. For similar reasons, 2C1D produces lesser number of roles than 3D. However, 2C1D sometimes generates the same number of roles as that produced by 3D, thereby showing that the cumulative effect of contained and disjoint sets of time intervals can produce results similar to the case containing only disjoint sets of time intervals.

Between the cases 2O and 2D, the former, in general, generates higher or equal number of roles. Splitting of the sets of time intervals both during candidate role generation as well as selection due to the presence of overlapping sets of time intervals, sometimes outweighs the effect of the presence of the disjoint sets of time intervals, resulting in more number of roles in case of overlapping time intervals. However, such splitting can, at times, produce effects similar to that observed in the case of disjoint sets of time intervals, ultimately producing equal number of roles. Similar reasoning applies for cases 3D and 3O. In general, the number of roles for 2O1D is lesser or equal to 3O. The lesser number of roles for 2O1D are produced due to the presence of more number of overlapping time intervals in 3O, leading to greater amount of time interval splitting. However, the combination of overlapping and disjoint sets of time intervals, in some cases, produces an effect similar to that of overlapping sets of time intervals, thereby generating equal number of roles for 2O1D and 3O.

It can be observed that as the number of distinct sets of time intervals increases from 1 to 2, the number of roles generated also increases due to the splitting of time intervals and the presence of more number of disjoint sets of time intervals. When the number of distinct sets of time intervals is 3, the number of triples in the TUPA matrix is more than that for 2 distinct sets of time intervals. Since splitting of time intervals is not carried out during initial role creation, roles that can fully cover a large number of triples are created, which ultimately does not increase the final number of roles obtained for cases of 3 distinct sets of time intervals than those of 2 distinct sets of time intervals. The tables further show that the number of roles increases with increase in the number of users and permissions. The increase in the number of roles with an increase in the number of permissions is more prominent in case of higher number of users.

Table 8

Execution time (in ms) for 100 users

δ (%)	No. of perms.	Time interval type

		1D	2C	2O	2D	2O1D	3D	2C1D	3C	3O
0.0	50	23.58	13.56	14.94	7.56	7.10	6.13	8.05	11.92	8.67
	100	47.12	27.86	27.18	17.37	16.85	12.09	13.54	18.09	16.39
	200	129.47	53.39	68.83	41.09	34.36	31.04	35.26	48.04	42.35
0.5	50	22.78	13.51	14.28	7.89	7.47	6.57	9.34	13.06	10.31
	100	49.17	28.51	27.62	16.58	16.26	11.91	13.62	18.01	15.67
	200	131.60	53.47	67.46	40.81	35.29	30.15	35.89	46.74	41.72
1.0	50	22.61	14.46	13.53	8.10	8.92	6.64	8.76	11.89	9.45
	100	48.73	26.62	28.84	16.36	15.91	12.73	13.35	17.96	16.75
	200	130.80	52.84	67.13	39.46	34.43	30.07	35.01	47.13	40.94
2.0	50	22.94	13.15	13.68	7.16	7.14	6.32	8.66	12.16	8.78
	100	46.83	27.19	26.24	15.97	16.29	11.27	12.95	17.62	15.92
	200	130.72	51.58	67.80	38.99	32.77	30.94	33.80	46.36	41.40

Table 9

Execution time (in s) for 200 users

δ (%)	No. of perms.	Time interval type

		1D	2C	2O	2D	2O1D	3D	2C1D	3C	3O
0.0	100	28.25	26.17	26.08	3.70	1.59	1.01	2.23	6.68	5.47
	200	30.65	45.51	35.12	6.06	6.99	2.42	6.54	17.62	7.75
	400	48.95	53.60	39.02	12.82	8.89	5.42	7.57	15.64	13.55
0.5	100	19.95	20.97	19.23	3.10	1.44	0.91	1.75	5.63	4.66
	200	29.26	34.12	32.58	5.47	6.29	2.14	5.52	14.65	7.38
	400	50.72	54.03	39.24	11.35	7.79	4.63	6.57	14.30	11.85
1.0	100	20.42	21.50	19.48	2.99	1.39	0.88	1.71	5.51	4.56
	200	30.02	34.86	32.33	5.23	6.11	2.03	4.93	13.50	6.90
	400	48.04	50.52	36.30	10.94	7.48	4.43	6.28	13.92	11.45
2.0	100	20.37	21.28	19.24	2.90	1.34	0.84	1.67	5.43	4.46
	200	29.79	34.18	31.70	5.05	5.94	1.95	4.77	13.26	6.71
	400	47.59	49.21	35.32	10.53	7.17	4.20	5.99	13.59	10.97

Table 10

Execution time (in s) for 400 users

δ (%)	No. of perms.	Time interval type

		1D	2C	2O	2D	2O1D	3D	2C1D	3C	3O
0.0	200	134.58	8.70	10.04	1.74	0.60	0.35	0.55	1.80	1.04
	400	241.47	27.04	26.02	3.98	1.21	0.64	2.14	3.84	2.99
	800	276.52	40.08	38.44	8.36	4.20	1.69	2.64	8.37	6.49
0.5	200	138.90	8.86	10.24	1.74	0.60	0.35	0.55	1.81	1.03
	400	243.98	27.53	27.75	4.04	1.24	0.64	2.18	4.05	3.13
	800	285.82	43.20	38.22	8.07	4.04	1.61	2.55	8.06	6.26
1.0	200	137.34	8.90	10.33	1.74	0.60	0.34	0.55	1.81	1.04
	400	241.07	25.96	24.69	3.91	1.18	0.62	2.09	3.68	2.88
	800	275.89	39.06	37.49	8.04	4.00	1.59	2.54	8.01	6.20
2.0	200	136.56	8.91	10.30	1.76	0.63	0.37	0.58	1.85	1.06
	400	245.90	27.62	25.17	3.92	1.18	0.62	2.10	3.68	2.90
	800	281.54	39.81	38.00	8.14	4.09	1.67	2.62	8.18	6.30

Next, the execution time of our algorithm is reported in Tables 8–10 for the same datasets considered in Tables 5–7. It is seen from the tables that the execution time increases with increase in the number of users and permissions. The rate of increase matches with the time complexity of the algorithm mentioned in Section 4.1. Also, increasing the value of δ reduces the execution time as expected. It is observed from the tables that case 3D takes less time than 2D, which in turn takes lesser time than 1D. This is because, with an increase in the number of disjoint sets of time intervals, more users are assigned different permissions for the disjoint sets of time intervals. As a result, pairwise intersection among the initial roles leads to the creation of a smaller number of generated roles. Thus, the overall size of the candidate role set is reduced, which in turn, reduces the total execution time.

When two or more sets of time intervals overlap or are contained within one another, the execution time is much higher than the cases having all disjoint sets of time intervals since intersecting or contained time intervals, in general, result in the creation of higher number of generated roles. So, 3D has a lower execution time than both 2O1D and 2C1D, which again have lower execution time than 3O and 3C, respectively. Moreover, contained time intervals result in higher execution time than overlapping time intervals. Though in case of contained time intervals, the effective number of distinct sets of time intervals is less than that of overlapping time intervals, the former results in a higher number of time interval splitting during the creation of generated roles as compared to overlapping time intervals, thereby creating more number of candidate roles. Therefore, 2C, 3C and 2C1D, in general, take more time than 2O, 3O and 2O1D, respectively. It may be noted that, 2D, 2C and 2O respectively have longer execution time than 3D, 3C and 3O. This shows that with increase in the number of distinct sets of time intervals, the execution time decreases as a result of the code optimization mentioned at the beginning of this section. Thus, it can be concluded that the execution time not only depends on the number of distinct sets of time intervals, but also on the interrelationships among those intervals.

5.2. Results on real-world datasets

In this sub-section, we present results on the number of roles generated and the corresponding execution time for several real-world datasets introduced in [9]. We compare the performance of our current approach in terms of these two evaluation criteria with the approach presented in [28]. The datasets used for performance evaluation were also used by a number of other non-temporal role mining algorithms for reporting their results [24,31].

5.2.1. Dataset description

Table 11 shows the details of the UPA matrices of the real-world datasets along with the number of roles generated by the non-temporal role mining algorithm of [9]. UA and PA matrices for these datasets are first obtained by decomposing the respective UPA matrices using the biclique cover based approach proposed in [9]. Since these datasets are non-temporal in nature, the REBs are synthetically generated. For creating the REBs, 10 distinct sets of time intervals are considered and these time intervals are related to one another via the relationships of containment, overlap, consecutiveness and disjointedness. This is done keeping in mind real-life scenarios, where different roles can be enabled for different sets of time intervals and the interrelationships among these intervals can be of varied nature. Each role of a particular dataset is enabled for any one of the 10 sets of time intervals. The real UA and PA matrices and the synthetically generated REBs are combined to derive the TUPA matrices, which serve as input to our temporal role mining algorithm. Thus, each user-permission assignment in a TUPA is associated with one or more of these 10 sets of time intervals. Since the REBs are randomly generated, 30 different REBs are considered for each dataset, resulting in that many number of random temporal UPA variants. The value of δ is taken to be 0, 0.5, 1 and 2 percent of the total number of temporal user-permission assignments in each of the TUPA matrices. For each dataset, the median number of roles over the 30 executions is computed, which is reported as a percentage of the number of non-temporal roles given in the rightmost column of Table 11. In case of the overall execution time, the mean of the 30 executions has been reported. The next sub-section also presents a comparison of the proposed approach with the approach presented in [28]. Henceforth, for the sake of convenience we refer to the approach proposed in the current paper as PROP and that given in [28] as DBS. Since DBS provides an exact solution, only the results for $δ = 0 %$ have been included for this approach.

Table 11
Real-world datasets

Dataset Users Permissions User-permission assignments Roles

apj 2,044 1,164 6,841 456

emea 35 3,046 7,220 34

healthcare 46 46 1,486 15

domino 79 231 730 20

firewall2 325 590 36,428 10

firewall1 365 709 31,951 69

americas small 3,477 1,587 105,205 211

americas large 3,485 10,127 185,294 421

customer 10,021 277 45,427 276

Dataset	Users	Permissions	User-permission assignments	Roles
apj	2,044	1,164	6,841	456
emea	35	3,046	7,220	34
healthcare	46	46	1,486	15
domino	79	231	730	20
firewall2	325	590	36,428	10
firewall1	365	709	31,951	69
americas small	3,477	1,587	105,205	211
americas large	3,485	10,127	185,294	421
customer	10,021	277	45,427	276

5.2.2. Results

Figure 1 shows the number of roles produced by PROP and DBS as percentage of the corresponding non-temporal roles for all the nine datasets. When $δ = 0 %$ , though the number of roles produced by PROP for all the datasets is higher than the corresponding number of non-temporal roles, the difference is not significantly higher for most of the datasets. This implies that the proposed algorithm is capable of handling substantial variation in interrelationship among the distinct sets of time intervals in real-life applications. As the value of δ is increased, lesser number of roles are generated. For even small non-zero values of δ, the number of roles is even less than the corresponding non-temporal roles. This decrease in the number of roles is most notable in firewall1, firewall2 and customer datasets, where the number of roles is reduced to almost 50% when $δ = 2 %$ . For americas small, the reduction is a slightly higher than 50%. Thus, it can be concluded that allowing even a limited amount of mismatch reduces the number of roles significantly during temporal role mining and the impact is more significant for larger datasets. This justifies the inexact formulation of the problem. The results corresponding to DBS were obtained for apj, emea, healthcare, domino and customer. For the rest of the 4 datasets, each execution required more than 1 hour and hence was terminated before completion. This is indicated by the absence of the corresponding bars in Fig. 1. It can be observed that the number of roles produced by PROP is lower than that produced by DBS for apj, healthcare, domino and customer. In case of emea, the number of roles produced by the two approaches are the same.

Fig. 1.

Roles generated for real-world datasets.

Execution time for the real-world datasets is reported in Table 12. Since the overall execution time of PROP did not show much variation with increase in the value of δ, we report the execution time for only $δ = 0.0 %$ . The execution time of DBS is also shown in the table. It can be observed that the execution time of PROP is much lower than that of DBS. The entries containing “>3,600” correspond to the 4 datasets for which the execution time of DBS were more than 1 hour. Thus, it can be seen that the proposed approach for temporal role mining performs better than that of [28] both in terms of the number of roles and overall execution time.

Table 12

Execution time (in s) for real-world datasets

Dataset	PROP-0.0%	DBS-0.0%
apj	8.22	67.88
emea	0.34	0.33
healthcare	<0.01	130.48
domino	0.01	0.23
firewall2	0.12	>3,600
firewall1	0.56	>3,600
americas small	16.11	>3,600
americas large	225.84	>3,600
customer	40.82	88.77

5.3. Discussions

In this sub-section, we summarize our observations from the results obtained from both synthetic and real-world datasets. Results from both these datasets show that with an increase in the value of δ, the number of roles produced and the execution time decreases. Thus, for systems where a limited degree of mismatch is tolerable, a considerably smaller role set can be obtained in a reduced amount of time than that obtained when no mismatch is allowed. The number of roles and execution time are also affected by the interrelationships among the time intervals. In general, contained sets of time intervals produce lesser number of roles than both overlapping and disjoint sets of time intervals. Also, it is observed that overlap among the sets of time intervals results in time interval splitting, leading to higher number of roles than disjoint sets of time intervals. However, since presence of disjoint sets of time intervals increases the effective number of distinct sets of time intervals, in certain cases they produce the same number of roles as that produced by overlapping sets of time intervals. Increase in the number of disjoint sets of time intervals reduces the overall execution time. Disjoint sets of time intervals result in lower execution time than overlapping sets of time intervals, which in turn, have lower execution time than contained sets of time intervals. Moreover, comparative results on the real-world datasets show that our current approach outperforms the approach proposed in [28].

6. Related work

Role mining, a bottom-up role engineering technique, is the process of deriving a set of roles from the available user-permission assignments. Vaidya et al. define Basic-RMP as the problem of finding a minimal set of roles from the input user-permission assignment relation [35,36]. They prove it to be NP-complete and also map the problem to the Minimum Tiling Problem of databases. A heuristic algorithm for finding the minimum tiling is adopted to solve Basic-RMP. Two algorithms were proposed by them in [38], namely, CompleteMiner and FastMiner to derive a set of candidate roles from a given user-permission assignment relation via subset enumeration. Several variants of the role mining problem have been proposed in the existing literature of which Edge-RMP [25] aims to find a set of roles, a UA and a PA so that $(| UA | + | PA |)$ is minimized. In [20,21], the authors convert Basic-RMP and Edge-RMP respectively to the set cover problem and the weighted set cover problem, and propose greedy algorithms for solving them. The role minimization problem has also been shown to be equivalent to the Minimum Biclique Cover (MBC) problem, where each biclique corresponds to a role [9]. Since MBC is an NP-hard problem, a heuristic strategy has been presented in [9] for finding the minimum biclique cover of a bipartite graph which can be used to find the minimum set of roles covering all the user-permission assignments. In [11], the authors formulate the role mining problem as a predictive problem and call it as Inference RMP. They propose two probabilistic models, namely, disjoint-decomposition model (DDM) and multi-assignment clustering (MAC) to generate roles from the available user-permission assignments.

Lu et al. [25] model RMP as an optimal boolean matrix decomposition (OBMD) problem. They consider different variants of OBMD and solve them using binary integer programming. Frank et al. in [12] propose a probabilistic model that clusters boolean data. In this model, a single object can simultaneously belong to multiple clusters. The authors have shown that the proposed method can be used to solve the role mining problem. The user-permission assignment data given as input to role mining can contain several erroneous assignments which can propagate to the mined set of roles. Such erroneous assignments are called noise. Vaidya et al. in [37] propose a noise model that considers both over-assignment and under-assignment noise. They show that the algorithm proposed in [36] for solving δ-approx RMP can be used to handle over-assignment errors. However, this algorithm is not able to handle under-assignment errors.

Blundo and Cimato propose a Simple Role Mining Algorithm (SMA) [3]. In each iteration, SMA selects a particular row of the UPA, either randomly or depending on whether the user corresponding to that row has the maximum or the minimum number of permissions. The permissions associated with the selected row are taken collectively to form a candidate role. When a new candidate role is generated, the rows corresponding to the users whose permissions are already covered by the current set of candidate roles are removed from the UPA. The algorithm terminates when all the rows of the UPA have been considered. In [32], the authors propose role mining algorithms based on two machine learning techniques, Latent Dirichlet Allocation (LDA) and Author-Topic Model (ATM). These algorithms reflect the pattern of usage of permissions by the users and also user attributes. A number of genetic algorithm based approaches have been proposed to solve the role mining problem [21,42].

Ma et al. [27] present an approach for role mining where each permission is assigned a particular weight depending on its importance. Visual Role Mining (VRM) [6] is a role mining approach that derives a set of roles from the available user-permission assignments by visually analyzing their graphical representation. In [40], Xu and Stoller propose role mining algorithms which optimize several policy quality metrics that are based on the policy size and role interpretability. Verde et al. [39] propose a six step methodology to make role mining scalable and hence suitable for deployment in the real world. Gal-Oz et al. [14] propose an algorithm for deriving roles from the usage pattern information present in web applications.

In [5] the authors propose a three-step methodology to reduce the complexity of the role mining process and also the administration cost by deriving the role set only from the stable user-permission assignments, i.e., user-permission assignments that belong to roles having weight above a predefined threshold value. The unstable assignments are used to create single-permission roles. In order to elicit comprehensible roles having strong relationships with the business structures of the respective organizations, a role generating procedure has been proposed in [7], which incorporates business information in the process of finding roles.

Baumgrass and Strembeck [1] propose a set of guidelines that allow migration of current-state RBAC models derived from role mining approaches to target-state RBAC models derived from role engineering approaches. Hachana et al. [17] formally define the problem of comparing two sets of roles and prove it to be NP-complete. They also propose a greedy heuristic for solving the problem. Hybrid role engineering techniques developed by combining top-down and bottom-up strategies have been proposed in [11,41].

Enumerating roles in presence of various constraints are also available in the literature. In [4,18,22,24], role mining algorithms considering various cardinality constraints like maximum number of users that can be assigned to a role, maximum number of roles per user, and maximum number of permissions per role have been proposed. Lu et al. in [26] propose a variant of RMP, called the constraint-aware role mining problem (CRM) that allows negative permissions in roles. Such negative permission roles can account for the separation of duty constraints. In order to solve CRM, they propose the Extended Boolean Matrix Decomposition (EBMD) approach. Hu et al. [19] use answer set programming to find RBAC configurations that conform with several constraints which reflect various security and business requirements.

A survey of the existing literature indicates that though a considerable amount of work exists on role mining in RBAC systems, none of the existing work, except for the one proposed by us in [28], focuses on mining roles in temporal RBAC systems. However, our current work is different from the work presented in [28] in terms of the formulation of a generalized version of the temporal role mining problem and also the greedy approach proposed to solve the problem.

7. Conclusion and future directions

Temporal role mining provides a method for deriving roles in TRBAC systems that assign permissions to users for specific sets of time intervals. In this paper, we have presented a formal definition of the Generalized Temporal Role Mining Problem (GTRMP), which takes into consideration both notions of exact and partial matches between the input temporal user-permission assignments and those obtained from the output of the temporal role mining process. The problem has been shown to be NP-complete and we have proposed a greedy heuristic for solving it. Results of extensive experiments show that permitting a limited degree of mismatch, though results in restricted availability of certain permissions to some users, reduces the number of roles significantly, especially when the number of users and permissions is large.

In this work, the number of roles has been considered to be the only optimization metric. This metric is useful for organizations which consider the cost of administering the resulting TRBAC system only in terms of the number of roles. However, the administrative cost may also include other aspects like the cost of administering the user-role assignment relation, role-permission assignment relation, role enabling base and the role hierarchy. So, metrics that consider the sizes of the user-role and role-permission assignment relations as well as the size of the role enabling base and role hierarchy apart from the size of the mined role set can be designed for overall cost optimization. Various other temporal constraints present in the TRBAC model other than enabling and disabling of roles can be taken into consideration while devising the temporal role mining techniques. Apart from these, features such as temporal role hierarchies and temporal Separation of Duty (SoD) constraints of the GTRBAC model [23] may also be considered during temporal role mining. In temporal role hierarchies, the inheritance relationships among the roles (and consequently the associated permissions) are dependent on the enabling duration of the roles and temporal SoDs reflect conflicts among time intervals and role assignment to users and consequently the availability of permissions included in those roles. We would also like to look into hybrid temporal role engineering techniques in the context of temporal RBAC models which will help to create roles incorporating the business information available within any organization. Another future direction of work is to design tools for building the TUPA matrix from available information including access logs. Such a tool would aid the system administrator in his task of creating the TUPA matrix.

Footnotes

Complexity analysis of GTRMP

Here, we present a formal analysis of the complexity class of GTRMP. We first formulate a decision version of the problem called Decision-GTRMP (DGTRMP) as follows.

References

Baumgrass and

Strembeck, An approach to bridge the gap between role mining and role engineering via migration guides, in: Proceedings of 7th International Conference on Availability, Reliability and Security (ARES), 2012, pp. 113–122.

Bertino,

P.A.

Bonatti and

Ferrari, TRBAC: a temporal role-based access control model, ACM Transactions on Information and System Security (TISSEC)4(3) (2001), 191–233.

Blundo and

Cimato, A simple role mining algorithm, in: Proceedings of 25th ACM Symposium on Applied Computing (SAC), 2010, pp. 1958–1962.

Blundo and

Cimato, Constrained role mining, in: Proceedings of 8th International Workshop on Security and Trust Management, 2012, pp. 289–304.

Colantonio,

R.D.

Pietro,

Ocello and

N.V.

Verde, Taming role mining complexity in RBAC, Computers and Security29(5) (2010), 548–564. (Special Issue on Challenges for Security and Privacy and Trust.)

Colantonio,

R.D.

Pietro,

Ocello and

N.V.

Verde, Visual role mining: a picture is worth a thousand roles, IEEE Transactions on Knowledge and Data Engineering24(6) (2012), 1120–1133.

Colantonio,

R.D.

Pietro and

N.V.

Verde, A business-driven decomposition methodology for role mining, Computers and Security31(7) (2012), 844–855.

E.J.

Coyne, Role engineering, in: Proceedings of 1st ACM Workshop on Role Based Access Control, 1995, pp. 15–16.

Ene,

Horne,

Milosavljevic,

Rao,

Schreiber and

R.E.

Tarjan, Fast exact and heuristic methods for role minimization problems, in: Proceedings of 13th ACM Symposium on Access Control Models and Technologies (SACMAT), 2008, pp. 1–10.

10.

D.F.

Ferraiolo,

Sandhu,

Gavrila,

D.R.

Kuhn and

Chandramouli, Proposed NIST standard for role-based access control, ACM Transactions on Information and System Security (TISSEC)4(3) (2001), 224–274.

11.

Frank,

J.M.

Buhman and

Basin, Role mining with probabilistic models, ACM Transactions on Information and System Security (TISSEC)15(4) (2013), 1–28.

12.

Frank,

A.P.

Streich,

Basin and

J.M.

Buhmann, Multi-assignment clustering for Boolean data, Journal of Machine Learning Research13(1) (2012), 459–489.

13.

Fuchs and

Pernul, HyDRo – hybrid development of roles, in: Proceedings of 4th International Conference on Information Systems Security (ICISS), 2008, pp. 287–302.

14.

Gal-Oz,

Gonen,

Yahalom,

Gudes,

Rozenberg and

Shmueli, Mining roles from web application usage patterns, in: Proceedings of 8th International Conference on Trust, Privacy and Security in Digital Business (TrustBus), 2011, pp. 125–137.

15.

M.R.

Garey and

D.S.

Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.

16.

Guo,

Vaidya and

Atluri, The role hierarchy mining problem: discovery of optimal role hierarchies, in: Proceedings of 24th Annual Computer Security Applications Conference (ACSAC), 2008, pp. 237–246.

17.

Hachana,

Cuppens,

Cuppens-Boulahia and

Garcia-Alfaro, Towards automated assistance for mined roles analysis in role mining applications, in: Proceedings of 7th International Conference on Availability, Reliability and Security (ARES), 2012, pp. 123–132.

18.

Hingankar and

Sural, Towards role mining with restricted user-role assignment, in: Proceedings of 2nd International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace Electronic Systems Technology (Wireless VITAE), 2011, pp. 1–5.

19.

Hu,

K.M.

Khan,

Bai and

Zhang, Constraint-enhanced role engineering via answer set programming, in: Proceedings of 7th ACM Symposium on Information, Computer and Communications Security (ASIACCS), 2012, pp. 73–74.

20.

Huang,

Shang,

Liu and

Du, Handling least privilege problem and role mining in RBAC, Journal of Combinatorial Optimization (2014), to appear, DOI: 10.1007/s10878-013-9633-9.

21.

Huang,

Shang and

Zhang, Approximation algorithms for minimizing the number of roles and administrative assignments in RBAC, in: Proceedings of 36th Annual IEEE Computer Software and Applications Conference Workshops (COMPSAC), 2012, pp. 427–432.

22.

J.C.

John,

Sural,

Atluri and

Vaidya, Role mining under role-usage cardinality constraint, in: Proceedings of 27th IFIP TC 11 International Information Security and Privacy Conference (SEC), 2012, pp. 150–161.

23.

Joshi,

Bertino,

Latif and

Ghafoor, A generalized temporal role-based access control model, IEEE Transactions on Knowledge and Data Engineering17(1) (2005), 4–23.

24.

Kumar,

Sural and

Gupta, Mining RBAC roles under cardinality constraint, in: Proceedings of 6th International Conference on Information Systems Security (ICISS), 2010, pp. 171–185.

25.

Lu,

Vaidya and

Atluri, Optimal Boolean matrix decomposition: application to role engineering, in: Proceedings of 24th IEEE International Conference on Data Engineering (ICDE), 2008, pp. 297–306.

26.

Lu,

Vaidya,

Atluri and

Hong, Constraint-aware role mining via extended Boolean matrix decomposition, IEEE Transactions on Dependable and Secure Computing (TDSC)9(5) (2012), 655–669.

27.

Ma,

Li and

Lu, Role mining based on weights, in: Proceedings of 15th ACM Symposium on Access Control Models and Technologies (SACMAT), 2010, pp. 65–74.

28.

Mitra,

Sural,

Atluri and

Vaidya, Toward mining of temporal roles, in: Proceedings of 27th Annual IFIP WG 11.3 Working Conference on Data and Applications Security and Privacy (DBSec), 2013, pp. 65–80.

29.

Molloy,

Chen,

Li,

Wang,

Li,

Bertino,

Calo and

Lobo, Mining roles with semantic meanings, in: Proceedings of 13th ACM Symposium on Access Control Models and Technologies, 2008, pp. 21–30.

30.

Molloy,

Chen,

Li,

Wang,

Li,

Bertino,

Calo and

Lobo, Mining roles with multiple objectives, ACM Transactions on Information and System Security (TISSEC)13(4) (2010), 36:1–36:35.

31.

Molloy,

Li,

Mao,

Wang and

Lobo, Evaluating role mining algorithms, in: Proceedings of 14th ACM Symposium on Access Control Models and Technologies (SACMAT), 2009, pp. 95–104.

32.

Molloy,

Park and

Chari, Generative models for access control policies: applications to role mining over logs with attribution, in: Proceedings of 17th ACM Symposium on Access Control Models and Technologies (SACMAT), 2012, pp. 45–56.

33.

Roeckle,

Schimpf and

Weidinger, Process-oriented approach for role-finding to implement role-based security administration in a large industrial organization, in: Proceedings of 5th ACM Workshop on Role-Based Access Control, 2000, pp. 103–110.

34.

R.S.

Sandhu,

E.J.

Coyne,

H.L.

Feinstein and

C.E.

Youman, Role-based access control models, IEEE Computer29(2) (1996), 38–47.

35.

Vaidya,

Atluri and

Guo, The role mining problem: finding a minimal descriptive set of roles, in: Proceedings of 12th ACM Symposium on Access Control Models and Technologies (SACMAT), 2007, pp. 175–184.

36.

Vaidya,

Atluri and

Guo, The role mining problem: a formal perspective, ACM Transactions on Information and System Security (TISSEC)13(3) (2010), 27:1–27:31.

37.

Vaidya,

Atluri,

Guo and

Lu, Role mining in the presence of noise, in: Proceedings of 24th Annual IFIP WG 11.3 Working Conference on Data and Applications Security and Privacy (DBSec), 2010, pp. 97–112.

38.

Vaidya,

Atluri and

Warner, Role miner: mining roles using subset enumeration, in: Proceedings of 13th ACM Conference on Computer and Communications Security (CCS), 2006, pp. 144–153.

39.

N.V.

Verde,

Vaidya,

Atluri and

Colantonio, Role engineering: from theory to practice, in: Proceedings of 2nd ACM Conference on Data and Application Security and Privacy (CODASPY), 2012, pp. 181–191.

40.

Xu and

S.D.

Stoller, Algorithms for mining meaningful roles, in: Proceedings of 17th ACM Symposium on Access Control Models and Technologies (SACMAT), 2012, pp. 57–66.

41.

Zhang,

Chen,

Gunter,

Liebovitz and

Malin, Evolving role definitions through permission invocation patterns, in: Proceedings of 18th ACM Symposium on Access Control Models and Technologies (SACMAT), 2013, pp. 37–48.

42.

Zhao,

Lin,

Shi and

Fang, Mining the role-oriented process models based on genetic algorithm, in: Proceedings of 3rd International Conference on Advances in Swarm Intelligence (ICSI), 2012, pp. 398–405.

The generalized temporal role mining problem

Abstract

Keywords

1. Introduction

2. Preliminaries

2.1. Role-Based Access Control (RBAC)

2.2. Temporal Role-Based Access Control (TRBAC)

2.3. Role mining

3. Mining roles in the context of TRBAC

3.1. Temporal UPA matrix

Definition 1 (Generalized Temporal Role Mining Problem (GTRMP)).

4. Greedy algorithm for solving GTRMP

4.1. Algorithm description

4.1.1. Creation of candidate roles

4.1.2. Role selection

Table 3 Candidate role selection

5.1. Results on synthetic datasets

5.1.1. Dataset generation

5.1.2. Results

5.2.1. Dataset description

6. Related work

7. Conclusion and future directions

Footnotes

Complexity analysis of GTRMP

References

Table 3
Candidate role selection