Erman Pattuk
email: erman.pattuk@utdallas.edu

Murat Kantarcioglu
email: muratk@utdallas.edu

Huseyin Ulusoy
email: huseyin.ulusoy@utdallas.edu

Bradley Malin
email: b.malin@vanderbilt.edu

CheapSMC: A Framework to Minimize Secure Multiparty Computation Cost in the Cloud

Secure multi-party computation (SMC) techniques are increasingly more efficient and practical, due in part, to various improvements. For instance, recent research has shown that different protocols that are implemented using different sharing mechanisms (e.g., boolean and arithmetic sharings) can have varying computational and communication costs. Although there are some approaches to automatically mix protocols of different sharing schemes to enhance execution efficiency, none provide a generic optimization framework to discover the least expensive mixed-protocol SMC execution for cloud deployment. In this work, we introduce a generic SMC optimization framework CheapSMC that can invoke any mixed-protocol SMC circuit evaluation tool as a black box to uncover the cheapest SMC cloud deployment option. To do so, CheapSMC computes one-time benchmarks for the target cloud service and gathers performance statistics for basic circuit components. Relying on these statistics, an optimization layer of CheapSMC invokes several heuristics to find the cheapest mix-protocol circuit evaluation. Subsequently, the optimized circuit is passed to a mixed-protocol SMC tool for actual executable generation. Our empirical results, gathered by running cases studies on large range of complexity in data volume and functions for computation, show that significant cost savings can be achieved via our optimization framework in comparison to the state-of-the-art.

Introduction

Over the last couple of years, various two-party secure multi-party computation (SMC) protocols have been proposed to address different secure computation needs, ranging from privacy-preserving face recognition (e.g., [START_REF] Sadeghi | Efficient privacy-preserving face recognition[END_REF]) to secure biometric identification (e.g., [START_REF] Evans | Efficient privacy-preserving biometric identification[END_REF]). In addition, numerous generic two-party circuit evaluation platforms (e.g. [START_REF] Bogdanov | Sharemind: A framework for fast privacy-preserving computations[END_REF][START_REF] Henecka | Tasty: tool for automating secure two-party computations[END_REF]) have been developed to improve the efficiency of existing secure protocols. Most of these platforms (e.g., [START_REF] Malkhi | Fairplay-secure two-party computation system[END_REF]) also provide high-level programming language support that can automatically generate circuits from programs written in C-like languages. These recent advances have enabled two-party SMC protocols to be more practical and push towards actual deployment of such technologies.

At the same time, there remain several critical challenges to making these platforms practical. One challenge in particular that has received little attention is performance optimization. Recent research [START_REF] Demmler | ABY -A framework for efficient mixed-protocol secure two-party computation[END_REF] has shown that different two-party SMC protocols can have different computational and communication cost profiles. For example, arithmetic sharing-based circuit evaluation protocols may be better for certain tasks in comparison to Yao's garbled circuit evaluation protocols. On the other hand, Boolean secret sharing-based circuit evaluation techniques can achieve the best performance in certain situations. Based on such observations, it has been shown [START_REF] Demmler | ABY -A framework for efficient mixed-protocol secure two-party computation[END_REF] that the combination of these techniques can perform much better than each in isolation. This begs the question: How can we find the best combination of two-party SMC techniques for a given task?

Most of the existing work to date fails to consider the problem of finding the optimal combination of different sharing-based protocols for a given task. Rather, they require the end user to manually specify the specific sub-protocols that must be invoked. There has been some investigation into optimization and automation of the selection process (e.g., [START_REF] Kerschbaum | Automatic protocol selection in secure two-party computations[END_REF]), but it is limited in scope with respect to the cost dimensions that the user can choose to optimize. For example, if one party leverages a cloud infrastructure for running the protocol, the network communication may significantly impact the overall cost (in terms of money) paid by the parties. As such, it is clear that we need an optimization framework that can automatically consider communication, computation and monetary costs when searching for the optimal two-party SMC protocol composition.

The goal of this paper is to introduce an optimization framework where the given two-party SMC task can be automatically optimized under a set of predefined cost constraints. In doing so, the optimal (or near optimal) combination of different sharingbased subprotocols (e.g., arithmetic, boolean, and Yao's secret sharing protocols) can be selected automatically. This goal is similar to other automatic task optimization frameworks associated with other systems. In our optimization framework, we especially focus on the cloud setting because it is being widely adopted by organizations in a wide range of application domains [START_REF] Forbes | Cloud computing: United states businesses will spend $13 billion on it[END_REF] due to its flexibility and low initial management cost. In the cloud setting, in addition to minimizing the overall run time of the system, we may need to balance the network traffic, and computation time to achieve overall lowest monetary cost. This makes the problem more challenging because it suggests we need to consider both communication and computation costs in the optimal mixed-protocol circuit generation.

Overview of the CheapSMC. The objective of the system3 is to make it easier for users to implement and execute SMC protocols, while minimizing the monetary cost of the SMC execution in the cloud. To ease the implementation phase and make Cheap-SMC extensible to available SMC tools, we partition it into three primary components. First, the Programming API acts as the frontend for the users, which enables implementation of SMC protocol using a C++ library. This layer is ultimately responsible for representing the user protocol as a circuit of atomic operations. It should be noted that CheapSMC can be further extended by designing a custom language (e.g., SFDL of Fairplay [START_REF] Malkhi | Fairplay-secure two-party computation system[END_REF]), which uses our Programming API in the background. In this work, we do not focus on such integration and instead focus on the optimization aspects.

Second, the Optimization Module is responsible for assigning secret sharing schemes (e.g., Arithmetic, Boolean, Yao sharing as in the ABY framework [START_REF] Demmler | ABY -A framework for efficient mixed-protocol secure two-party computation[END_REF]; Additively homomorphic, Yao sharing as in the Tasty framework [START_REF] Henecka | Tasty: tool for automating secure two-party computations[END_REF]) to the nodes in the circuit, such that the total cost of executing the protocol in the cloud is minimized. Finding an optimal solution to this problem is NP-Hard, so this module provides heuristics to find near-optimal solutions.

Finally, the SMC Layer implements the optimized circuit given an existing SMC tool (e.g., ABY or Sharemind [START_REF] Bogdanov | Sharemind: A framework for fast privacy-preserving computations[END_REF]). We recognize the development of efficient SMC tools is a vibrant research area, such that the design of CheapSMC does not focus on a single SMC tool that could limit its usefulness. Rather, we leverage a given SMC tool as a black box, provided that it is a mixed-protocol SMC tool (i.e., it allows for implementation using different sharing schemes).

CheapSMC relies on several atomic operations (e.g., addition, multiplication, binary xor, as well as binary and) that cover various application scenarios. In Section 4, we show the results of applying our system to several case studies, while further applications can be realized using our C++ library. Moreover, the process of optimizing the circuit is decoupled from the circuit generation and other layers, so that proposing a new heuristic and implementing it can be achieved with minimal effort.

The Optimal Partitioning Problem 2.1 Problem Definition

Let S = {s 1 , . . . , s n } be the set of provided secret sharing mechanisms. Then, given a variable x in some domain I, let [x] si represent the secret sharing of x using s i .

Next, we define the set of operations O = {o 1 , . . . , o k }, such that each operation o i ∈ O takes a set of parameters that are secretly shared in s j and outputs a single variable secretly shared in s j . Note that the number of inputs that an operation takes is fixed, regardless of the secret sharing scheme. An operation o i is supported in s j , if there exists an execution protocol that takes the input parameters to o i and outputs a result secretly shared in s j . Let δ(o i ) ⊆ S represent the secret sharing mechanisms that support operation o i ∈ O.

Since an operation can be executed in the cloud environment, one should approximate the monetary cost of performing the protocol execution in a certain setup. In order to achieve this goal, we focus on the processing and network transfer costs of executing a single operation in the pay-as-you-go cloud model. In this computing model, a customer of a cloud provider service is charged a constant amount per unit time for using a particular type of virtual machine (VM), while the prices vary depending on the processing capabilities of the VM. On the other hand, the monetary cost of transferring a single byte in and out of the VM is fixed based on the VM specifications. The unit cost of network transfer vary as the network capacity of the VM changes.

Under such circumstances, we define the processing and network transfer costs of executing an operation o i ∈ O in the secret sharing scheme s j ∈ δ(o i ) as P(o i , s j ) and N(o i , s j ), respectively. Furthermore, we define the processing and network transfer cost of converting a variable that is secretly shared in s i ∈ S to s j ∈ S as CP(s i , s j ) and CN(s i , s j ), respectively. Note that defined costs may vary based upon VM specifications.

Given the set of operations O, the parties in the computation (i.e., the server and the client) implement a circuit C that is represented as a directed acyclic graph (DAG) and consists of m nodes c 1 , . . . , c m . Each node represents a single operation and takes input from other nodes, whereas the number of inputs is decided by the operation. To be more concrete, let α(c i ) ∈ O represent the operation that is assigned to the node c i ∈ C, while β(c i ) ⊆ C is the set of nodes that supply input to c i4 . Furthermore, let γ(c i ) ∈ S be the secret sharing scheme assigned to c i . Then the monetary cost of executing a node

c i ∈ C is simply: cost(c i ) = P(α(c i ), γ(c i )) + N(α(c i ), γ(c i )) + cj ∈β(ci) CP(γ(c j ), γ(c i )) + CN(γ(c j ), γ(c i )) (1)
Using the above definitions, the optimal partitioning problem investigated in this paper is formally defined as follows:

Definition 1. Given the processing and network transfer cost for a set of operations O using a set of secret sharing schemes S, the cost of conversion between different secret sharing schemes, and a circuit C = {c 1 , . . . , c m } of m nodes, where each node c i is assigned an operation α(c i ) ∈ O, assign a secret sharing scheme to each node c i , such that the total monetary cost of executing the circuit with the assigned secret sharing schemes is minimal.

Given :O, S, C, P(o, s) and N(o, s) ∀o ∈ O, ∀s ∈ δ(o), CP(s i , s j ) and CN(s i , s j ) ∀s i , s j ∈ S, α(c i ) ∀c i ∈ C Minimize : ci∈C cost(c i ) Subject to : γ(c i ) ∈ δ(α(c i )) ∀c i ∈ C (2)
The partitioning problem is NP-Hard, and the reduction can be realized via the Integer Programming problem.

3 The Details of CheapSMC

Architecture

CheapSMC is composed three primary parts: (i) The programming interface (API), (ii) the optimization module, and (iii) the SMC layer. Each part is responsible for a different task: The programming interface morphs a user's program into its circuit representation. The optimization module heuristically assigns the secret sharing schemes to each node in the circuit using. The SMC layer generates the executables using state-of-the-art cryptographic primitives and techniques. The user of CheapSMC is expected to provide two inputs: (A) the specifications of the protocol that are going to be executed securely and (B) the unit costs for the operations and secret sharing schemes supported by the SMC framework. As discussed later, we provide a benchmark suite to automatically learn these unit costs for any target cloud service to assist the user.

User Inputs. It is assumed that the user knows the secure protocol for the application for CheapSMC will be invoked. One input to our system is the protocol specification, which can either be implemented using the associated C++ library or via a custom programming language, whose compiler turns the user input to an output compatible with our programming API. Next, the user must input the unit monetary cost of the operations for the hardware specifications that secure executables will work over. We have implemented a set of benchmark applications that can be executed by a user to discover the unit costs of each operation. It should be recognize that this is a one-time operation per tested cloud environment.

Programming API. We implemented an extensible library in C++ that allows a user to implement a secure protocol (e.g., set intersection or biometric matching). We provided several operations in the API that cover a variety of applications. Currently, the set of operations O include addition (Add), subtraction (Sub), multiplication (Mul), greater (Ge), equality (Eq), multiplexer (Mux), binary xor (Xor), and binary and (And). There are also two additional operations in the form of input (In) and output (Out), which allow the programmer to specify secret inputs to the circuit and to learn the outputs of the protocol execution.

As a proof of concept, we provided the interface as a C++ library that can be used to generate cost-optimal SMC executables. The interface can be bound with the compiler of a custom programming language, though which the system user can type the protocol specifications. Next, the compiler can generate the C++ program that uses the Cheap-SMC programming interface. In any scenario, the programming interface transforms the protocol into the circuit representation (See Section 2).

Optimizer. Given the circuit representation of the user protocol and the secret sharing schemes that are provided by the SMC layer, the optimizer module applies one of the heuristics (cf. Section 3.2) to assign secret sharing schemes to each node in the circuit. As discussed earlier, this module is responsible for finding the assignment that minimizes the monetary cost of executing the protocol securely.

Due to the fact that the optimal partitioning problem problem is NP-Hard, finding the optimal assignment may be impractical (even for a circuit of moderate size). As such, we introduced several heuristics (See Section 3.2) that are oriented to find a reasonable solution. In the background, CheapSMC applies each heuristic and chooses the one that gives the best result.

SMC Layer. Once the secret sharing schemes are assigned to each node in the circuit, CheapSMC passes the circuit to the SMC layer to generate the SMC executables. It should be recognized that there are several related investigations that provide mixed-protocol SMC tools, including the ABY framework by Demmler et al [START_REF] Demmler | ABY -A framework for efficient mixed-protocol secure two-party computation[END_REF], the TASTY framework by Henecka et al. [START_REF] Henecka | Tasty: tool for automating secure two-party computations[END_REF], and the Sharemind framework by Bogdanov et al. [START_REF] Bogdanov | Sharemind: A framework for fast privacy-preserving computations[END_REF]. The SMC layer in CheapSMC is responsible for automatically implementing the optimized circuit from such existing tools. Note that since the selected SMC tool provides the low-level implementation of the cryptographic primitives (e.g., oblivious transfer [START_REF] Naor | Efficient oblivious transfer protocols[END_REF][START_REF] Rabin | How to exchange secrets with oblivious transfer[END_REF], multiplication triplets [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF], and sharing and reconstructing secret inputs), we focus on optimizing the user protocol using sharing assignments.

Optimization Heuristics

In addition to two existing heuristics, we developed two new heuristics to solve the optimal partitioning problem. Here, we provide a high-level description of thee heuristics.

Bottom-up Heuristic. The key idea in this heuristic is to assign an optimal secret sharing scheme to the nodes in their topological order in the circuit. When a node c i ∈ C is ready to be processed, the heuristic first assigns sharing schemes to the nodes that provide input to c i . Based on the values assigned to the children, this heuristic selects the scheme that minimizes the expected monetary cost for c i .

Top-Down Heuristic. This technique processes the nodes of the circuit in a manner quite the opposite of the Bottom-Up heuristic. Specifically, it assigns secret sharing schemes to the higher-level nodes first and iterates down to the lower levels. The idea in this heuristic is to assign the scheme that minimizes the cost of the current node, given that the schemes for the nodes for which its input to are already known. Now, assume that the secret sharing scheme for the node c k is set to s k previously. When assigning the secret sharing scheme for the node c i , this heuristic takes into account that the result of the node c i should be converted to s k . The optimal decision is made with this consideration in mind.

Fixed Secret Sharing. In this optimization heuristic, each node in the circuit is assigned the same secret sharing scheme. However, in some SMC tools, certain secret sharing schemes may not necessarily support each single operation (e.g., Arithmetic sharing in ABY framework does not support And, Xor, and Mux). In such a case, this heuristic selects one scheme that supports each CheapSMC operation. One common secret sharing scheme that is included in almost all SMC tools and supports each operation is garbled circuit sharing (based on Yao's garbled circuit protocol [START_REF] Yao | Protocols for secure computations[END_REF]). Using this heuristic, we can measure the monetary cost of executing the user protocol by a single secret sharing scheme (e.g., pure SMC by garbled circuit sharing).

Hill-Climbing. This heuristic is based on the technique of Kerschbaum et al. [START_REF] Kerschbaum | Automatic protocol selection in secure two-party computations[END_REF]. The basic idea is to start by assigning a common secret sharing scheme (e.g., garbled circuit sharing) to each node in the circuit. Next, we check if the total cost can be reduced by changing the current secret sharing scheme of a node. This loop continues until the total cost cannot be improved by any further assignment.

Case Studies

Experiment Setup

We conducted empirical performance evaluations in two scenarios: (1) Intra-Region, where the parties are in the same Amazon EC2 region and (2) Inter-Region, where the parties are not in same region, for four different Amazon EC2 VM models. We tested each scenario and VM model with four techniques: the three optimization heuristics -(i.e., Top-down, Bottom-up, and Hill Climbing) -and Pure-Yao, which assigns Yao-style (i.e., garbled circuit) sharing to each node in the circuit.

In addition to the monetary cost of running CheapSMC, we measure the average running time of the four techniques. As mentioned in Section 3.2, our optimization problem can be enhanced by introducing performance constraints (e.g., the expected running time should be less than some threshold t). Given such a performance constraint, the heuristic solver may prune any solution that fails to satisfy the estimated performance constraint.

Biometric Matching

Biometric matching applications cover a two-party scenario, where (i) the server has a set of private entries and (ii) a client, holding its private entry, wants to learn the closest entry in the server's dataset based on some similarity measure. There are various problems related to this case study (e.g., biometric identification [START_REF] Evans | Efficient privacy-preserving biometric identification[END_REF], fingercode authentication [START_REF] Barni | Privacy-preserving fingercode authentication[END_REF], and face recognition [START_REF] Sadeghi | Efficient privacy-preserving face recognition[END_REF][START_REF] Erkin | Privacy-preserving face recognition[END_REF]). One of the commonly used distance metric is squared Euclidean distance. In this protocol, the server and the client proceed over the server's dataset one by one, which results in the client learning the entry with the minimal distance to its private input. We implemented this case study using our Programming API for a dataset of 30 rows with 5 attributes of 32-bit numbers.

We performed tests on four different Amazon EC2 VM configurations. Detailed information on the specifications of each VM configuration can be found in the full version of this paper. Table 1 shows the average running time for the Biometric Matching case study, two different scenarios, four VM models, and four secret-sharing assignment heuristics. As expected, the performance is much better in the Intra-Region scenario. In all cases, applying any of the heuristics yields lower running times compared to the Pure-GC assignment (i.e., where each node is assigned the Yao sharing). Moreover, our Top-Down heuristic yields the best running time for all VM models. Specifically, it is 15% better than the Hill Climbing heuristic of Kerschbaum et al [START_REF] Kerschbaum | Automatic protocol selection in secure two-party computations[END_REF] in terms performance. For the Inter-Region scenario, we find that Pure-GC performs much better than the other techniques in terms of performance, except for the last model c4.xlarge. Since the physical distance between the two parties is large (i.e., between Tokyo and North Virginia), network latency plays a vital role in the overall performance. And it is shown that Yao sharing is much better than any other solution in high-latency networks. Since our primary optimization objective is to minimize cost (and not to minimize performance) the Inter-Region results are not surprising. Table 2 shows the monetary cost for the Biometric Matching case study with the aforementioned setup. In the Intra-Region scenario, we see that the Top-Down heuristic performs better than any other technique in all VM models. This is due to a better assignment of secret sharing schemes to the nodes in the circuit for this particular case study. Note that the network communication cost within the same region is 0 in Amazon EC2, which is why the network cost in Table 2 is simply 0. In the Inter-Region scenario, the Top-Down heuristic once again delivers the cheapest assignments for all VM models. It performs 30% better than the Hill Climbing heuristic. In terms of computation cost, we see that Pure-GC performs better due to the reasons discussed earlier (i.e., high network latency). However, in terms of total cost, Top-Down heuristic induces up to 80% reduction.

Conclusion

This paper introduced CheapSMC, an SMC framework that aims to minimize the cost of executing SMC protocols in the cloud. We performed extensive cost profiling for the Amazon EC2 cloud service leveraged the gathered statistics and applied our system two case studies (i.e., biometric matching and matrix multiplication). We evaluated Cheap-SMC using four VM models and two scenarios (i.e., Inter-Region and Intra-Region). and we showed that the cost of executing SMC using our heuristics is up to 96% and 30% less than pure garbled circuit and Hill-Climbing methods, respectively. The evidence suggests that purchasing faster and more expensive VM models from Amazon EC2 do not necessarily reduce the total monetary cost of executing SMC protocols. In general, compute-optimized VMs can result in more expenses, while those which are memory-optimized can produce cheaper SMC executions.

Acknowledgement

The research was supported by grants from the NIH (R01LM009989, R01HG006844, & 1U01HG008701) and NSF (CNS-1111529, CNS-1228198, & CICI-1547324).

Table 1 .

 1 The average execution time for the Biometric Matching case study in the Amazon EC2 Cloud. The results are for two different scenarios, four different VM models, and four different techniques.

			Execution time (ms)
		Pure-GC	Hill	TD	BU
	INTRA	m3.med 1229.481 398.02 348.43 416.944 m3.large 715.5147 355.2913 321.388 372.529 c4.large 577.333 293.544 256.363 284.378 c4.xlarge 561.602 352.197 292.522 326.393
	INTER	m3.med 5518.04 6738.14 6237.37 6749.467 m3.large 4801.94 6096.73 6103.647 6083.193 c4.large 8731.577 35580.13 33267.77 35569.97 c4.xlarge 9118.693 6916.357 6381.093 6826.727

Table 2 .

 2 The average computational, network, and total cost of running the Biometric Matching case study in the Amazon EC2 Cloud. The results are for two different scenarios, four different VM models, and four different techniques.

		Computation Cost (¢10 -3 )	Network Cost (¢10 -3 )	Total Cost (¢10 -3 )
		Pure-GC Hill	TD	BU Pure-GC Hill	TD	BU Pure-GC Hill	TD	BU
	INTRA	m3.med m3.large 5.57 4.78 c4.large 3.72 c4.xlarge 7.24	1.55 1.36 1.62 2.76 2.50 2.90 1.89 1.65 1.83 4.54 3.77 4.21	0.00 0.00 0.00 0.00	0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00	4.78 5.57 3.72 7.24	1.55 1.36 1.62 2.76 2.50 2.90 1.89 1.65 1.83 4.54 3.77 4.21
	INTER	m3.med 27.74 33.88 31.36 33.93 990.71 189.71 129.71 189.71 1018.46 223.58 161.07 223.64 m3.large 45.75 58.09 58.15 57.96 990.71 189.71 129.71 189.71 1036.46 247.80 187.86 247.67 c4.large 63.79 259.93 243.04 259.86 990.71 218.29 173.27 218.29 1054.50 478.23 416.31 478.15 c4.xlarge 133.23 101.06 93.23 99.75 990.71 189.71 129.71 189.71 1123.95 290.76 222.94 289.45

Please see https://arxiv.org/abs/1605.00300 for the full version of our paper.

Note that this circuit representation of a computation can be provided by the programming language.


Scott D Stoller

Thang Bui

Mining Hierarchical Temporal Roles with Multiple Metrics

Temporal role-based access control (TRBAC) extends rolebased access control to limit the times at which roles are enabled. This paper presents a new algorithm for mining high-quality TRBAC policies from timed ACLs (i.e., ACLs with time limits in the entries) and optionally user attribute information. Such algorithms have potential to significantly reduce the cost of migration from timed ACLs to TRBAC. The algorithm is parameterized by the policy quality metric. We consider multiple quality metrics, including number of roles, weighted structural complexity (a generalization of policy size), and (when user attribute information is available) interpretability, i.e., how well role membership can be characterized in terms of user attributes. Ours is the first TRBAC policy mining algorithm that produces hierarchical policies, and the first that optimizes weighted structural complexity or interpretability. In experiments with datasets based on real-world ACL policies, our algorithm is more effective than previous algorithms at their goal of minimizing the number of roles.

Introduction

Role-based access control (RBAC) offers significant advantages over lower-level access control policy representations, such as access control lists (ACLs). RBAC policy mining algorithms have potential to significantly reduce the cost of migration to RBAC, by partially automating the development of an RBAC policy from an access control list (ACL) policy and possibly other information, such as user attributes [START_REF] Hachana | Role mining to assist authorization governance: How far have we gone[END_REF]. The most widely studied versions of the RBAC policy mining problem involve finding a minimum-size RBAC policy consistent with (i.e., equivalent to) given ACLs. When user attribute information is available, it is also important to maximize interpretability (or "meaning") of roles-in other words, to find roles whose membership can be characterized well in terms of user attributes. Interpretability is critical in practice. Researchers at HP Labs report "the biggest barrier we have encountered to getting the results of role mining to be used in practice" is that "customers are unwilling to deploy roles that they can't understand" [START_REF] Ene | Fast exact and heuristic methods for role minimization problems[END_REF]. Algorithms for mining meaningful roles are described in, e.g., [START_REF] Molloy | Mining roles with multiple objectives[END_REF][START_REF] Xu | Algorithms for mining meaningful roles[END_REF].

Temporal RBAC (TRBAC) extends RBAC to limit the times at which roles are enabled [START_REF] Bertino | TRBAC: A temporal role-based access control model[END_REF]. TRBAC supports an expressive notation, called periodic expressions, for expressing sets of time intervals during which a role is enabled. A role's permissions are available to members only while the role is enabled. This allows tighter enforcement of the principle of least privilege.

This paper presents an algorithm for mining hierarchical TRBAC policies. It is parameterized by a policy quality metric. We consider multiple policy quality metrics: number of roles, weighted structural complexity (WSC) [START_REF] Molloy | Mining roles with multiple objectives[END_REF], a generalization of syntactic policy size, interpretability (INT) [START_REF] Molloy | Mining roles with multiple objectives[END_REF][START_REF] Xu | Algorithms for mining meaningful roles[END_REF], described briefly above, and a compound quality metric, denoted WSC-INT, that combines WSC and INT. Our algorithm is the first TRBAC policy mining algorithm that produces hierarchical policies, and the first that optimizes WSC or interpretability.

Our algorithm is based on Xu and Stoller's elimination algorithm for RBAC mining [START_REF] Xu | Algorithms for mining meaningful roles[END_REF] and some aspects of Mitra et al.'s pioneering algorithm for mining flat TRBAC policies (i.e., policies without role hierarchy) with minimal number of roles [START_REF] Mitra | Toward mining of temporal roles[END_REF][START_REF] Mitra | The generalized temporal role mining problem[END_REF], which inspired our work. Our algorithm has four phases: (1) produce a set of candidate roles, (2) merge candidate roles where possible, (3) organize the candidate roles into a role hierarchy, and (4) remove low-quality candidate roles. The generated policy is not guaranteed to have optimal quality. Fundamentally, this is because the problem of finding an optimal policy is NP-complete (this follows from NP-completeness of the untimed version of the problem ( [START_REF] Molloy | Mining roles with multiple objectives[END_REF]).

To evaluate the algorithm, we created datasets based on real-world ACL policies from HP, described in [START_REF] Ene | Fast exact and heuristic methods for role minimization problems[END_REF] and used in several evaluations of role mining algorithms, e.g., [START_REF] Molloy | Mining roles with multiple objectives[END_REF][START_REF] Xu | Algorithms for mining meaningful roles[END_REF][START_REF] Mitra | The generalized temporal role mining problem[END_REF]. We could simply extend the ACLs with temporal information to create a temporal user-permission assignment (TUPA), and then mine a TRBAC policy from the TUPA and attribute data. However, it would be hard to evaluate the algorithm's effectiveness, because there is nothing with which to compare the quality of the mined policies. Therefore, we adopt a similar methodology as Mitra et al. [START_REF] Mitra | The generalized temporal role mining problem[END_REF]. For each ACL policy, we mine an RBAC policy from the ACLs and synthetic attribute data using Xu and Stoller's elimination algorithm [START_REF] Xu | Algorithms for mining meaningful roles[END_REF], pseudorandomly extend the RBAC policy with temporal information numerous times to obtain TRBAC policies, expand the TRBAC policies into equivalent TUPAs, mine a TRBAC policy from each TUPA and fixed attribute data, and compare the average quality of the resulting TRBAC policies with the quality of the original TRBAC policy, with the goal that the former is at least as good as the latter.

We created two datasets, using different temporal information when extending RBAC policies to obtain TRBAC policies. For the first dataset, we use simple periodic expressions, each of which is a range of hours that implicitly repeats every day. For the second dataset, we use more complex periodic expressions based on a hospital staffing schedule.

In experiments using number of roles as the policy quality metric, Mitra et al.'s algorithm, designed to minimize number of roles, produces 34% more roles than our algorithm, on average. In experiments using WSC-INT as the policy quality metric, our algorithm succeeds in finding the implicit structure in the TUPA, producing policies with comparable (for the first dataset) or moderately higher (for the second dataset) WSC and better interpretability, on average, compared with the original TRBAC policy.

We explored the effect of different inheritance types on the quality of the mined policy and found that weakly restricted inheritance leads to policies with significantly better WSC and slightly better interpretability, on average. We experimentally evaluated the benefits of some design decisions and quantified the cost-quality trade-off provided by a parameter to our algorithm that limits the number of candidate roles.

Background on TRBAC

An RBAC policy is a tuple User , Perm, Role, UA, PA, RH , where User is a set of users, Perm is a set of permissions, Role is a set of roles, UA ⊆ U × Role is the user-role assignment, PA ⊆ Role × Perm is the permission-role assignment, and RH ⊆ Role ×Role is the role inheritance relation (also called the role hierarchy). Specifically, r, r ∈ RH means that r is senior to r , hence all permissions of r are also permissions of r, and all members of r are also members of r . A role r is junior to role r if rRH + r , where RH + is the transitive closure of RH .

A periodic expression (PE) is a symbolic representation for an infinite set of time intervals. The formal definition of periodic expressions in [START_REF] Bertino | TRBAC: A temporal role-based access control model[END_REF][START_REF] Mitra | The generalized temporal role mining problem[END_REF] is standard and somewhat complicated; instead of repeating it, we give a brief intuitive version. A calendar is an infinite set of consecutive time intervals of the same duration; informally, it corresponds to a time unit, e.g., a day or an hour. A sequence of calendars C 1 , . . . , C n , C d defines the sequence of time units used in a periodic expression, from larger to smaller. A periodic expression has the form

n k=1 O k • C k d • C d where O 1 = all , O k
is a set of natural numbers or the special value all for 2 ≤ k ≤ n, and d is a natural number. The first part of a PE (before ) identifies the set of starting points of the intervals represented by the PE. The second part of the PE (after ) specifies the duration of each interval.

For example, consider the sequence of calendars Quadweeks, Weeks, Days, hours, where a Quadweek is four consecutive weeks-similar to a month, but with a uniform duration. The periodic expression [all • Quadweeks + {1,3} • Weeks + {1,2,3,4,5} • Days + {10} • Hours 8

• Hours] represents the set of time intervals starting at 9am (the time intervals in each calendar are indexed starting with 1, so for Hours, 1 denotes the hour starting at midnight, 2 denotes the hour starting at 1am, etc.) and ending at 5pm (since duration is 8 hours) of every weekday (assuming days of the week are indexed with 1=Monday) during the first and third weeks of every quadweek.

A bounded periodic expression (BPE) is a tuple [begin, end ], pe , where begin and end are date-times, and pe is a periodic expression. A BPE represents the set of time intervals represented by pe except limited to the interval [begin, end ].

A role enabling base (REB) is a set of BPEs, representing the union of the sets of time intervals represented by the BPEs.

A temporal RBAC (TRBAC) policy is a tuple User , Perm, Role, UA, PA, RH , IT , REBA , where the first six components are the same as for an RBAC policy, IT is the inheritance type (described below), and REBA is the role enabling base assignment (REBA), which is a mapping from roles in Role to REBs [START_REF] Bertino | TRBAC: A temporal role-based access control model[END_REF]. A role r is enabled during the set of time intervals represented by REBA(r).

We consider two types of inheritance [START_REF] Joshi | Temporal hierarchies and inheritance semantics for GTRBAC[END_REF]. In both cases, a senior role r inherits permissions from each of its junior roles r . With weakly restricted inheritance, denoted by IT = WR, a permission inherited from r is available to members of r during the time intervals specified by REBA(r). With strongly restricted inheritance, denoted by IT = SR, a permission inherited from r is available to members of r during the time intervals specified by REBA(r ).

A temporal user-permission assignment (TUPA) is a set of triples of the form u, p, reb , where u is a user, p is a permission, and reb is a REB (even though reb is not associated with a role, we call it a REB, because it has the same type as a REB). We refer to such a triple as an entitlement triple. Such a triple means that u has permission p during the set of time intervals represented by reb. A TUPA should contain at most one entitlement triple for each user-permission pair. A TUPA can therefore be regarded as a mapping from user-permission pairs to REBs.

The meaning of a role r in a TRBAC policy π, denoted [[r]] π , is a TUPA that expresses the entitlements granted by r, taking inheritance into account. The meaning [[π]] of a TRBAC policy π is a TUPA that expresses the entitlements granted by π.

The Relaxed TRBAC Policy Mining Problem

A policy quality metric is a function from TRBAC policies to a totally-ordered set, such as the natural numbers. The ordering is chosen so that small values indicate high quality.

Number of roles is a simplistic but traditional policy quality metric.

Weighted Structural Complexity (WSC) is a generalization of policy size [START_REF] Molloy | Mining roles with multiple objectives[END_REF]. We adapt WSC to TRBAC. For a TRBAC policy π of the above form, the WSC of π is defined by WSC(π) = w 1 |Role| + w 2 |UA| + w 3 |PA| + w 4 |RH | + w 5 WSC(REBA), where the w i are user-specified weights, |s| is the size (cardinality) of set s, and WSC(REBA) is the sum of the sizes of the REBs in REBA. The size of an REB is the sum of the sizes of the BPEs in it. The size of a BPE is the size of the PE in it (the beginning and ending date-times are always the same size, so we ignore them). The size of a PE is the sum of the sizes of the sets in it plus 1 for the duration, with the special value all counted as a set of size 1.

Interpretability is a policy quality metric that measures how well role membership can be characterized in terms of user attributes. User-attribute data is a tuple A, f , where A is a set of attributes, and f is a function such that f (u, a)

is the value of attribute a for user u. An attribute expression e is a function from the set A of attributes to sets of values. A user u satisfies an attribute expression e iff (∀a ∈ A. f (u, a) ∈ e(a)). For example, if A = {dept, level }, the function e with e(dept) = {CS} and e(level ) = {2, 3} is an attribute expression, which can be written with syntactic sugar as dept ∈ {CS} ∧ level ∈ {2, 3}. We refer to the set e(a) as the conjunct for attribute a. Let [[e]] denote the set of users that satisfy e. For an attribute expression e and a set U of users, the mismatch of e and U is defined by mismatch(e, U ) = | [[e]] U |, where the symmetric difference of sets s 1 and s 2 is

s 1 s 2 = (s 1 \ s 2 ) ∪ (s 2 \ s 1 )
. The attribute mismatch of a role r, denoted AM(r), is min e∈E mismatch(e, asgndU(r)), where E is the set of all attribute expressions, and asgndU(r) = {u | u, r ∈ UA}. We define policy interpretability INT as the sum over roles of attribute mismatch, i.e., INT(π) = r∈Role AM(r).

Compound policy quality metrics take multiple aspects of policy quality into account. We combine metrics by Cartesian product, with lexicographic ordering on the tuples. Let WSC-INT(π) = WSC(π), INT(π) .

A TRBAC policy π is consistent with a TUPA T if they grant the same permissions to the same users for the same sets of time intervals. When the given TUPA contains noise, it is desirable to weaken this requirement. A TRBAC policy π is -consistent with a TUPA T , where is a natural number, if they grant the same permissions to the same users for the same sets of time intervals, except that, for at most entitlement triples u, p, reb in T , the policy π either does not grant p to u or grants p to u at fewer times than reb [START_REF] Mitra | The generalized temporal role mining problem[END_REF]. Note that consistency is a special case of -consistency, corresponding to = 0.

The relaxed TRBAC policy mining problem is: given a TUPA T and a policy quality metric Q pol , find a TRBAC policy π that is -consistent with T and has the best quality, according to Q pol , among policies consistent with T . Note that auxiliary information used by the policy quality metric, e.g., user-attribute data, is implicitly considered to be part of Q pol in this definition. Note that the temporal part of T strongly influences π, even using WSC with w 5 = 0, because it determines how entitlements can be grouped in roles.

Suggested role assignments for new users. The system can compute and store a best-fit attribute expression e r for each role r, i.e., an attribute expression that minimizes the attribute mismatch for r. When a new user u is added, the system can suggest that u be made a member of the roles for which u satisfies the bestfit attribute expression, and it presents these suggested roles in descending order of the attribute mismatch.

TRBAC Policy Mining Algorithm

Inputs to the algorithm are the TUPA T , the type of inheritance IT to use in the generated policy, the consistency threshold , and the policy quality metric Q pol . User attribute data, if available, is used only indirectly, via the policy quality metric, if it considers interpretability. Phase 1: Generate roles. Phase 1 generates initial roles and then creates additional candidate roles by intersecting sets of initial roles.

Phase 1.1: Generate initial roles. Pseudocode for generating initial roles appears in Figure 1. The set of permissions P that each user u has for exactly the same REB reb are grouped to form the permissions of an initial role; this is the effect of using permREB in Figure 1. If there are any permissions that u has for a REB that semantically contains reb, then we also create another role that has those permissions in addition to permissions in P ; this is the effect of using permREB + . In addition, for each BPE bpe in reb, we create an initial role with permissions P and with REB {bpe}. The algorithm uses a semantic containment relation on PEs, BPEs, and REBs: x 1 x 2 iff the set of time instants represented by x 1 is a subset of the set of time instants represented by x 2 .

Phase 1.2: Intersect roles. Phase 1.2 starts to construct a set R cand of candidate roles, by adding to R cand all of the initial roles in R init and all non-empty intersections of all subsets of the initial roles. In other words, for each subset of initial roles, if the intersection of their permission sets is a non-empty set P , and the intersection of their REBs is a non-empty REB reb, then create a candidate role with permissions P , REB reb, and the union of their user sets. REBs are intersected semantically, not syntactically; for example, if reb 1 represents 9am-5pm on Mondays and Wednesdays, and reb 2 represents 1pm-2pm on Mondays and Fridays, then their intersection is a REB that represents 1pm-2pm on Mondays. This phase is similar to role intersection in CompleteMiner [START_REF] Vaidya | RoleMiner: Mining roles using subset enumeration[END_REF] and the elimination algorithm [START_REF] Xu | Algorithms for mining meaningful roles[END_REF]. This phase is expensive for large datasets. We use two techniques to reduce the cost when necessary; they provide a trade-off between cost and policy quality.

(1) Compute intersections for all pairs (instead of all subsets) of initial roles, as in FastMiner [START_REF] Vaidya | RoleMiner: Mining roles using subset enumeration[END_REF]. This reduces the worst-case complexity of this step and the overall algorithm from exponential to quadratic. (2) Compute intersections involving only the largest roles, specifically, roles whose relative size is in the top RIC (mnemonic for "role intersection cutoff"), where 0 ≤ RIC ≤ 1. For example, RIC = 0.3 means that intersections are computed among roles whose size is in the top 30%. Role size is quantified as covEntit(r), defined below.

Phase 2: Merge roles. Phase 2 merges candidate roles to produce a revised set of candidate roles. We use three types of merges. (1) If candidate roles r and r have the same same set of users U and the same REB reb, then they are replaced with a new role with users U , permissions asgndP 0 (r) ∪ asgndP 0 (r ), and REB reb. (2) If candidate roles r and r have the same users U and same permissions P , then they are replaced with a new role with users U , permissions P , and REB reb(r) reb(r ). The function denotes semantic union of REBs; in other words, reb 1 reb 2 is a REB that represents the set of time instants represented by reb 1 or reb 2 . We distinguish two sub-cases. (2a) If reb 1 and reb 2 represent disjoint sets of time intervals, then reb 1 reb 2 is simply reb 1 ∪reb 2 . (2b) If reb 1 and reb 2 represent sets of overlapping or consecutive time intervals, then BPEs in them are merged, if possible, to simplify the result. For example, if reb 1 represents 9am-noon on weekdays, and reb 2 denotes noon-5pm on weekdays, then reb 1 reb 2 contains a single BPE denoting 9am-5pm on weekdays. Phase 3.1: Compute inheritance. Phase 3.1 determines inheritance relationships between candidate roles, based on the requirement of full inheritance. Function isAncestorFullInher(r , r) tests whether r is an ancestor of r with full inheritance; if IT = WR, the function avoids inheritance relationships that would lead to cycles in the role hierarchy. isAncestorFullInher(r , r) = asgndP 0 (r ) ⊆ asgndP 0 (r) ∧ asgndU 0 (r) ⊆ asgndU 0 (r )

∧ (IT = SR ⇒ REBA(r ) REBA(r)) ∧ (IT = WR ⇒ ¬(asgndP 0 (r) ⊂ asgndP 0 (r ) ∧ asgndU 0 (r ) ⊂ asgndU 0 (r)))
This function is called for every pair of candidate roles. If isAncestorFullInher(r , r) is true, and there is no intervening role r such that isAncestorFullInher(r , r) isAncestorFullInher(r, r), then r is a parent of r. This phase produces maps parents and children, such that parents(r) and children(r) are the sets of parents and children of r, respectively.

Phase 3.2: Compute assigned users and permissions. Phase 3.2 computes the directly assigned users asgndU(r) and directly assigned permissions asgndP(r) of each role r, by removing inherited users and permissions from the role's originally assigned users asgndU 0 (r) and originally assigned permissions asgndP 0 (r).

Phase 4: Remove roles. Phase 4 removes roles from the candidate role hierarchy if the removal preserves consistency with the given ACL policy and improves policy quality. When a role r is removed, the role hierarchy is adjusted to preserve inheritance relations between parents and children of r, and the sets of directly assigned users and permissions of other roles are expanded to contain users and permissions that they previously inherited from r.

The order in which roles are considered for removal affects the final result. We control this ordering with a role quality metric Q role , which maps roles to an ordered set, with the interpretation that large values denote high quality (note: this is opposite to the interpretation of the ordering for policy quality metrics). Low-quality roles are considered for removal first. We use a role quality metric that is a temporal variant of the role quality metric in [START_REF] Xu | Algorithms for mining meaningful roles[END_REF] that gave the best results in their experiments. Specifically, Q role (r) = redun(r), clsSz(r) , where redun(r) and clsSz(r) are defined next, and the ordering on these tuples is lexicographic order.

The redundancy of a role r measures how many other roles also cover the entitlement triples covered by r. We say that a role r covers an entitlement triple t if t ∈ [[r]] π . Removing a role with higher redundancy is less likely to prevent subsequent removal of other roles, so we eliminate roles with higher redundancy first. The redundancy of role r, denoted redun(r), is the negative of the minimum, over entitlement triples u, p, reb covered by r, of the number of removable roles that cover u, p, reb (we take the negative so that roles with more redundancy have lower quality). A role is removable in policy π, denoted removable(r) (the policy is an implicit argument), if the policy obtained by removing r is -consistent with T .

The clustered size of a role r measures how many entitlements are covered by r and how well they are clustered. A first attempt at formulating this metric (ignoring clustering) might be as the fraction of entitlement triples in T that are covered by r. As discussed in [START_REF] Xu | Algorithms for mining meaningful roles[END_REF], it is better for the covered entitlement triples to be "clustered" on (i.e., associated with) fewer users rather than being spread across many users. The clustered size of r is defined to equal the fraction of the entitlements of r's members that are covered by r. In the temporal case, each entitlement triple u, p, reb is weighted by the fraction of the time represented reb that is covered by REBA(r). where T (u, p) is the REB reb such that u, p, reb ∈ T , dur(reb) is the fraction of one time unit in calendar C 1 that is covered by reb, and entitlements(U, T ) is the set of entitlement triples in T for a user in U . For example, if the sequence of calendars is C 1 = Year, . . . , C n = Hour, C d = Hour, and reb is 9am-5pm every day, then dur(reb) = 1/3, since reb covers 1/3 of the time in a year.

Our algorithm may remove a role even if the removal worsens policy quality slightly. Specifically, we introduce a quality change tolerance δ, with δ ≥ 1, and we remove a role if the quality Q of the RBAC policy resulting from the removal is related to the quality Q of the current RBAC policy by Q < δQ (recall that, for policy quality metrics, smaller values are better). Choosing δ > 1 partially compensates for the fact that a purely greedy approach to policy quality improvement is not an optimal strategy.

Pseudocode for removing roles appears in Figure 2. It repeatedly tries to remove all removable roles, until none of the attempted removals succeeds in improving the policy quality. The policy π is an implicit argument to auxiliary functions such as removeRole and addRole. Function addRole(r) adds role r to the candidate role hierarchy: inheritance relations involving r are added, and the assigned users and assigned permissions of r's newly acquired ancestors and descendants are adjusted by removing inherited users and permissions. Removing a role r and then restoring r using addRole leaves the policy unchanged.

The following auxiliary functions are used in removeRole. isDescendant(r,r ) holds if r is a descendant of r , as determined by following the parent-child relations in the children map. The set of authorized users of r, denoted authU(r), is the set of users in asgndU(r) or asgndU(r ) for some r senior to r; this is the same as in RBAC. The notion of authorized permissions must be defined differently in TRBAC than RBAC, because, with strongly-restricted inheritance, the inherited permissions of a role r may be associated with REBs different than REBA(r). With strongly-restricted inheritance, the set of authorized permissions of r, denoted authP(r), is the set of permission-REB pairs p, reb such that (1) each directly assigned permission of r is paired with REBA(r) and (2) each permission p inherited by r is paired with the semantic union of the REBs of the junior roles from which it is inherited. With weakly-restricted inheritance, authP(r) is the set of permission-REB pairs p, REBA(r) such that p is in asgndP(r) or asgndP(r ) for some r junior to r; we use a set of pairs for uniformity with the case of strongly-restricted inheritance.

Datasets

Our datasets are based on real-world ACL policies from HP, described in [START_REF] Ene | Fast exact and heuristic methods for role minimization problems[END_REF], and the high-fit synthetic attribute data for these ACL policies described in [START_REF] Xu | Algorithms for mining meaningful roles[END_REF]; see those references for general information about the policies. As outlined in Section 1, for each ACL policy, we mine an RBAC policy from the ACLs and the attribute data using Xu and Stoller's elimination algorithm [START_REF] Xu | Algorithms for mining meaningful roles[END_REF], and pseudorandomly extend the RBAC policy with temporal information several times to obtain TRBAC policies. For each ACL policy except americas small, we create 30 TRBAC policies. For americas small, which is larger, we create only 10 TRBAC policies, to reduce the running time of the experiments. We extend the RBAC policies in two ways, using different temporal information.

of the four weeks of a Quadweek. Each REB is based on exactly one of the resulting 10 work schedules. Multiple PEs are needed to represent work schedules that wrap around calendar units; for example, a 7pm-7am shift is represented using two PEs, with time intervals 7pm-midnight and midnight-7am. The PEs are based on the following sequence of calendars: C 1 =Quadweeks, C 2 =Days, C 3 =Hours, C d =Hours. The days in a Quadweek are numbered 1..28. Including Week in the sequence of calendars is not helpful, because most workers' schedules do not repeat on a weekly basis.

Evaluation

The experimental methodology is outlined in Section 1. All experiments use quality change tolerance δ = 1.001 (this value gave the best results for the experiments in [START_REF] Xu | Algorithms for mining meaningful roles[END_REF]), = 0, All and w i = 1 for all weights in WSC. The policy quality metric is WSC-INT, and the inheritance type is weakly restricted, except where specified otherwise.

Our Java code, datasets, and an extended version of the paper are available at www.cs.stonybrook.edu/ stoller/policy-mining/. Periodic expressions are an abstract data type with two implementations: (1) simple PEs, as defined in Section 5, and implemented as pairs of integers, and (2) (general) PEs, as defined in Section 2, and implemented as arrays of arrays of integers. These implementations are used in the experiments in Sections 6.1 and 6.2, respectively. Running times include the cost of an end-to-end correctness check that checks equivalence of the input TUPA and the meaning of the mined TRBAC policy; the average cost is about 7% of the running time. The experiments were run on a Lenovo IdeaCentre K430 with a 3.4 GHz Intel Core i7-3770 CPU.

Experiments using dataset with simple PEs

In experiments on this dataset, role intersection is configured to use FastMiner for emea and americas small, CompleteMiner for the other policies, and RIC = 1 for all policies.

Comparison of original and mined policies. Figure 3 shows detailed results from experiments on this dataset. In the column headings, µ is mean, σ is standard deviation, CI is half-width of 95% confidence interval using Student's t-distribution, and time is the average running time in minutes:seconds. There is no standard deviation column for INT, because interpretability is unaffected by the REBA and is the same for all TRBAC policies generated by extending the same RBAC policy. Ignore the last 2 columns for now. The averages and standard deviations are computed over the TRBAC policies created by extending each RBAC policy. The WSC of the mined TRBAC policy ranges from about 1% lower (for apj) to about 11% higher (for domino) than the WSC of the original TRBAC policy. The interpretability of the mined policy ranges from about 35% lower (for firewall-2) to about 1% higher (for apj) than the interpretability of the original TRBAC policy. On average over the seven policies, the WSC is 3% higher, and the interpretability is 12% lower. Thus, our algorithm succeeds in finding the implicit structure in the TUPA and producing a policy with comparable WSC and better interpretability, on average, than the original TRBAC policy.

Comparison of inheritance types. We ran our algorithm again on the same dataset, specifying strongly restricted inheritance for the mined policies. This caused a significant increase in the WSC of the mined policies. The percentage increase averages 67% and ranges from 15% for apj to 140% for firewall-1. Intuitively, the reason for the increase is that, with strongly restricted inheritance, the temporal information associated with directly assigned and inherited permissions may be different, and this may prevent removing inherited permissions from a role's directly assigned permissions. Inheritance type has less effect on the average INT, increasing (worsening) it by about 9% on average, excluding the outlier firewall-2, for which the average INT decreases from 4 to 1.

Evaluation of choice of initial roles. We evaluated two ways of reducing the cost of the algorithm by creating fewer initial roles. [START_REF] Bertino | TRBAC: A temporal role-based access control model[END_REF] We modified Phase 1.1 to create fewer initial roles by removing the use of permREB + in Figure 1. Note that Mitra et al.'s algorithm does not use an analogue of permREB + . This change increased the average WSC by 36% on average over the policies used in this experiment (all except emea and americas small, which were omitted because of their longer running time), ranging from 13% for apj to 69% for healthcare. It increased (worsened) the average INT by 37% on average over those policies, ranging from 9% for apj to 67% for domino. (2) We modified Phase 1.1 to create fewer initial roles by removing the first call to addRole. Note that Mitra et al.'s algorithm does not include an analogue of this call. This change increased the average WSC by 8% on average over the policies used in this experiment (all except emea and americas small), ranging from 7% for domino and firewall-2 to 9% for apj. It increased (worsened) the average INT by 7% on average over those policies, ranging from 0% for firewall-2 to 11% for domino.

Comparison with Mitra et al.'s algorithm. We ran Mitra et al.'s algorithm [START_REF] Mitra | The generalized temporal role mining problem[END_REF], and our algorithm with number of roles as policy quality metric (because Mitra et al. use this metric), on our dataset with simple PEs. Their code supports only simple PEs, so we used only the simple PE dataset in the comparison. Their code, implemented in C, gave an error ("malloc: ...: pointer being freed was not allocated") on some TRBAC policies generated for emea and firewall-1; we ignored those results. Their code did not run correctly on americas small, so we omitted it from this comparison.

The last two columns of Figure 3 show the numbers of roles generated by the two algorithms. Standard deviations are omitted to save space but are small: on average, 3% of the mean, for both algorithms. Mitra et al.'s algorithm produces 34% more roles than ours, on average. Our algorithm produces hierarchical policies, and their algorithm produces flat policies, but this does not affect the number of roles. There are many other differences between the algorithms, discussed in Section 7, which contribute to the difference in results. The above paragraph on evaluation of choice of initial roles describes two experiments that explore differences between our algorithm and Mitra et al.'s and quantify the benefit of those differences. The effects of some other differences between our algorithms, such as the use of elimination vs. selection in Phase 4, were investigated in the untimed case in [START_REF] Xu | Algorithms for mining meaningful roles[END_REF] and likely have a similar impact here.

Experiments using dataset with complex PEs

In experiments on this dataset, role intersection is configured to use CompleteMiner for firewall2 and FastMiner for the other policies.

Comparison of original and mined policies. Figure 4 shows detailed results from experiments on this dataset. The original TRBAC policies here have higher WSC than the ones in Section 6.1, because complex PEs have higher WSC than simple PEs. For apj, emea, and firewall1, we created 5 TRBAC policies (instead of 30) from each, to reduce the running time of the experiments. The WSC of the mined TRBAC policy ranges from about 2% higher (for firewall2) to about 57% higher (for firewall1) than the WSC of the original TRBAC policy. The interpretability of the mined TRBAC policy ranges from about 34% lower (for healthcare) to about 2% higher (for apj) than the interpretability of the original TRBAC policy. On average over the six policies, the WSC is 20% higher, and the interpretability is 16% lower. Thus, our algorithm finds most of the implicit structure in the TUPA and produces a policy with moderately higher WSC and better interpretability, on average, than the original TRBAC policy. The results can be improved by using larger RIC, at the expense of higher running time.

The higher running times, compared to the dataset with simple PEs, are due primarily to the larger number of candidate roles created by role intersection (there are more overlaps between REBs in this dataset), and secondarily to the larger overhead of manipulating more complex PEs.

Benefit of general PEs. PEs can be translated into sets of simple PEs. For example, the REB {[all • Weeks + {1,2,7} more compact and efficient. In experiments with the healthcare policy, using this translation and simple PEs was about 19x slower than using general PEs.

Effect of role-intersection cutoff. We investigated the cost-benefit trade-off when varying the role-intersection cutoff RIC. Figure 5 shows running time and WSC as functions of RIC, averaged over three of the smaller policies (domino, firewall2, healthcare). The trade-off is favorable: as RIC decreases, running time decreases more rapidly than WSC increases. For example, at RIC = 0.8, running time is 40% lower than with RIC = 1, and WSC is only 13% higher.

Related Work

We discuss related work on TRBAC policy mining and then related work on RBAC mining. Role mining (for RBAC or TRBAC) is also reminiscent of some other data mining problems, but algorithms for those other problems are not well suited to role mining. For example, association rule mining algorithms are designed to find rules that are probabilistic in nature. They are not designed to produce a set of rules strictly consistent with the input that completely covers the input and is minimum-sized among such sets of rules.

Related Work on TRBAC Policy Mining

Mitra et al. define a version of the TRBAC policy mining problem and present an algorithm for mining a TRBAC policy from a TUPA [START_REF] Mitra | The generalized temporal role mining problem[END_REF]. It is an improved version of their earlier work [START_REF] Mitra | Toward mining of temporal roles[END_REF].

Our algorithm is more flexible, because it can optimize a variety of metrics, including WSC and interpretability. Their algorithm is designed to optimize only the number of roles. The importance of interpretability is discussed in Section 1. WSC is a more general measure of policy size than number of roles and can more accurately reflect expected administrative cost. For example, the average number of role assignments per user is a measure of expected administrative effort for adding a new user [START_REF] Uzun | Migrating from DAC to RBAC[END_REF], and this can be reflected in WSC by giving appropriate weight to the size of the user-role assignment.

Our algorithm produces hierarchical TRBAC policies. Their algorithm produces flat TRBAC policies. Role hierarchy is a well-known feature of RBAC that can significantly reduce policy size and administrative effort by avoiding redundancy in the policy. Some other differences are: (1) Our algorithm determines which candidate roles to include in the final policy by elimination of low-quality roles, instead of selection of high-quality roles. We showed that elimination gives better results in the untimed case [START_REF] Xu | Algorithms for mining meaningful roles[END_REF]. (2) Our algorithm creates more initial roles than theirs. The benefit of creating these additional initial roles is shown in Section 6.1 in the paragraph on evaluation of choice of initial roles. Their algorithm creates unit roles, which are similar to initial roles but have only one permission; our algorithm does not create unit roles. (3) Our algorithm performs fewer types of role intersections than theirs. Specifically, it omits types of role intersections that create PEs with time intervals that do not appear in the input, since these PEs are probably not natural (intuitive) ones in the application domain.

Our implementation supports periodic expressions for specifying temporal information, while theirs supports only ranges of hours that implicitly repeat every day. Design and implementation of operations on sets of PEs is non-trivial.

Related Work on RBAC Mining

A survey of work on RBAC mining appears in [START_REF] Hachana | Role mining to assist authorization governance: How far have we gone[END_REF]. The most closely related work is Xu and Stoller's elimination algorithm [START_REF] Xu | Algorithms for mining meaningful roles[END_REF]. We chose it as the starting point for design of our algorithm, because in the experiments in [START_REF] Xu | Algorithms for mining meaningful roles[END_REF], it optimizes WSC more effectively than Hierarchical Miner [START_REF] Molloy | Mining roles with multiple objectives[END_REF], while simultaneously achieving good interpretability, and it optimizes WSCA, an interpretability metric defined in [START_REF] Molloy | Mining roles with multiple objectives[END_REF], more effectively than Attribute Miner [START_REF] Molloy | Mining roles with multiple objectives[END_REF].

Our algorithm retains the overall structure of the elimination algorithm but differs in several ways, due to the complexities created by considering time. Our algorithm introduces more kinds of candidate roles than the elimination algorithm, because it needs to consider grouping permissions that are enabled for the same time or a subset of the time of other permissions. Our algorithm attempts to merge candidate roles; the elimination algorithm does not. Construction of the role hierarchy is significantly more complicated than in the elimination algorithm; for example, with strongly restricted inheritance, a permission p can be inherited by a role r from multiple junior roles with different REBs, which may together cover all or only part of the time that p is available in r. This also complicates adjustment of the role hierarchy when removing candidate roles. The role quality metric used to select roles for removal is more complicated, to give preference to roles that cover permissions for more times.

Phase 3 :

 3 Construct role hierarchy. Phase 3 organizes the candidate roles into a role hierarchy with full inheritance. A TRBAC policy has full inheritance if every two roles that can be related by the inheritance relation are related by it, i.e., ∀r, r ∈ R. [[r]] π ⊇ [[r ]] π ⇒ r, r ∈ RH * . Guo et al. call this property completeness in the context of RBAC [3].

  |entitlements(asgndU(r), T )|

Fig. 5 .

 5 Fig. 5. Relative running time and relative WSC as functions of RIC.

  Results of experiments with simple PEs.

		Original Policy	Mined Policy	Avg |R|
	Dataset	WSC INT	WSC	INT	Time OurAlg Mitra+
		µ	σ		µ σ CI µ	σ CI µ
	americas small 6975 7.5 189 7100 78 29 140	7 2.5 58:56	297
	apj	4879 10.0 385 4826 22 8.1 388 3.5 1.2 1:04	468	527
	domino	449 2.5	23 499 70 26 20 1.5 0.57 0:02	30	40
	emea	3929 4.4	32 4038 68 25 32 0.2 0.07 0:49	100	115
	firewall1	1533 4.1	48 1653 58 22 44 3.7 1.4 1:45	97	130
	firewall2	960 1.4	7 966 9.2 3.4 5 1.0 0.38 0:02	12	17
	healthcare	168 1.4	14 168 3.9 1.5 14 0.42 0.16 0:01	15	25
		Fig. 3.

  • Days + {1} • Hours 8 • Hours]} can be translated to the REB {[1,9], [25,33], [145,153]}. However, PEs are generally

		Original Policy	Mined Policy
	Dataset	WSC INT	WSC	INT	RIC Time
		µ σ		µ σ CI µ	σ CI	µ
	apj	16836 159 385 17434 337 419 391 1.9 2.3 0.7 50:43
	domino	1156 49 23 1278 80 30 16 1.8 0.7	1 0:35
	emea	5975 99 32 8683 284 353 32	0 0 0.7 201:10
	firewall1	3712 97 48 5832 199 247 46 2.2 2.8 0.7 165:30
	firewall2	1269 37	7 1291 52 19 5.3 0.68 0.3	1 1:00
	healthcare 560 35 14 582 40 15 9.3 1.7 0.6	1 8:57
	Fig. 4. Results of experiments with complex PEs.

Acknowledgements. We thank the authors of [7]-Barsha Mitra, Shamik Sural, Vijayalakshmi Atluri, and Jaideep Vaidya-for sharing their code and datasets with us and helping us understand their work.

This material is based on work supported in part by NSF under Grants CNS-1421893, CCF-1248184, and CCF-1414078, ONR under Grant N00014-15-1-2208, and AFOSR under Grant FA9550-14-1-0261. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of these agencies.

π = policy from Phase 3 q = Q pol (π) workL = list of removable roles in π changed = true while ¬empty(workL) ∧ changed sort workL in ascending order by Q role changed = false for r in workL removeRole(r) // if -consistency is violated, // restore r. Dataset with simple PEs. A simple PE is a range of hours (e.g., 9am-5pm) that implicitly repeats every day. This dataset uses the same simple PEs as in [START_REF] Mitra | The generalized temporal role mining problem[END_REF], namely, [START_REF] Mitra | Toward mining of temporal roles[END_REF][START_REF] Xu | Algorithms for mining meaningful roles[END_REF], [START_REF] Mitra | The generalized temporal role mining problem[END_REF][START_REF] Vaidya | RoleMiner: Mining roles using subset enumeration[END_REF], [START_REF] Molloy | Mining roles with multiple objectives[END_REF][START_REF] Uzun | Migrating from DAC to RBAC[END_REF], [START_REF] Molloy | Mining roles with multiple objectives[END_REF][START_REF] Xu | Algorithms for mining meaningful roles[END_REF], [START_REF] Uzun | Migrating from DAC to RBAC[END_REF][START_REF] Xu | Algorithms for mining meaningful roles[END_REF], [START_REF] Vaidya | RoleMiner: Mining roles using subset enumeration[END_REF][START_REF] Xu | Algorithms for mining meaningful roles[END_REF], [START_REF] Vaidya | RoleMiner: Mining roles using subset enumeration[END_REF]12], [START_REF] Xu | Algorithms for mining meaningful roles[END_REF]13], [14, 15], [16,17]. These PEs are designed to cover various relationships between intervals, such as overlapping, consecutive, disjoint, and nested. We choose the number of PEs in each REB pseudorandomly using a similar probability distribution as in [START_REF] Mitra | The generalized temporal role mining problem[END_REF], namely, pr (1) = 0.78, pr (2) = 0.2, pr (3) = 0.02. We choose the specific PEs in each REB pseudorandomly using a uniform distribution.

Dataset with complex PEs. For this dataset, we use periodic expressions based on a hospital staffing schedule, based on discussions with the Director of Timekeeping at Stony Brook University Hospital. The periodic expressions are not taken directly from the hospital's staffing schedule, but they reflect its general nature. The schedule does not repeat every week, but rather every few weeks, because weekend duty rotates. Clinicians may work 3 days/week for 12 hours/day starting at 7am or 7pm, or 5 days/week for 8.5 hours/day starting at 7am, 3pm, or 11pm. We create two instances of each of these five types of work schedules, by pseudorandomly choosing the appropriate number of days of the week in each