# Hybrid Role-Engineering Optimization with Multiple Cardinality Constraints Using Natural Language Processing and Integer Linear Programming Techniques

Authors: Wei Sun
Journal: Mobile Information Systems
 (2022)

---

## Abstract

Role-based access control (RBAC) is a widely popular access control mechanism because of its convenience for authorization administration, as well as various security policies, such as separation-of-duty constraints and cardinality constraints. In recent few years, role-engineering technology has emerged as an efficient approach to construct optimal RBAC systems. However, the top-down approaches are labor-intensive and error-prone; the bottom-up approaches lack flexibility and scalability as the organizational requirements change dynamically, and cannot generate valuable or meaningful roles that are relevant to actual application scenarios. Furthermore, most conventional methods do not consider multiple cardinality constraints. To address these issues, this paper proposes a novel hybrid role-engineering method. First, to develop an initial access control system while alleviating manual workloads, we use the natural language processing techniques to extract machine-readable and machine-enforceable access control policies from the top-down natural language requirement documents. Second, to flexibly meet diverse organizational requirements while enhancing the security of role-engineering processes, according to different evaluation measures or optimization objectives, we define several variants of the optimization problem with multiple cardinality constraints via Boolean matrix decomposition and present a unified modelling framework for these variants using integer linear programming technique. Third, to verify whether the constraints can be satisfied in the constructed access control system, we present the heuristic optimization algorithms in the bottom-up ways. The experimental evaluations demonstrate the effectiveness and efficiency of the proposed method.


---

## Body

## 1. Introduction

With the rapid development and comprehensive application of network information technology, there are large amounts of information storages as well as frequent information exchanges in large-scale and complex management information systems [1]. Role-based access control (RBAC) mechanism, which is featured by its convenience for authorization administration and various security policies, is widely accepted and adopted in organizations of all scales [2–7]. With the successful deployments of RBAC systems for meeting actual application requirements, accomplishing the task of devising a complete, correct, and effective role set and constructing a good RBAC system becomes more and more crucial. As a solution to facilitate the process of migrating from a non-RBAC system to an RBAC system, role-engineering technology has been proposed in the literature, which consists of two main approaches: the top-down [8] and bottom-up [9].The top-down role-engineering approach defines particular roles for job responsibilities and decomposes them into smaller units by analyzing the business processes of organizations in detail. Once the required privileges for performing specific tasks are identified, they are grouped into appropriate functional roles [10]. This process is repeated until all the job functions are covered. Such technique discovers roles that can well reflect the functional requirements of organizations. However, it is very complex and tedious to identify the access privileges from a large number of business processes, when there are thousands of users and millions of permissions. Moreover, many enterprises or organizations have high-level requirement specifications for accessing resources, which describe who can access what information under what circumstances and conditions in human understandable ways. They are referred to as natural language access control policies (NLACPs) [8], and usually cannot be directly enforced in RBAC systems. It is time-consuming, labor-intensive, and error-prone to identify and extract the buried access control policies (ACPs) by manually sifting through the natural language specification documents.The bottom-up approach, also known as role mining, starts from the existing user-permission assignments and then aggregates them into roles by applying data mining techniques. It has received considerable attention in recent years, and numerous role mining approaches have been developed subsequently [11–14]. The role-mining problem can be viewed as an instantiation of Boolean matrix decomposition [15]. Although a Boolean matrix can be decomposed in various ways, different optimal decomposition solutions may match various semantics with respect to different criteria. Vaidya et al. [16] converted the role mining problem into a Boolean matrix decomposition problem and presented a definition for the basic role mining problem (basic RMP), which aims to discover a minimal set of roles that fully cover all the permission assignments. The basic RMP has been proven to be NP-complete, and it is difficult to derive an optimal role set. According to different optimization objectives, several RMP variants of the basic RMP have been proposed, such as δ-approx RMP [16], min-noise RMP [16], and edge-RMP [17]. Instead of the complete coverage of permissions, the δ-approx RMP allows an error in the matrix reconstruction while minimizing the number of mining roles. As a result, it is easy to derive a suboptimal role set that can cover the majority of the permission assignments. The edge-RMP attempts to minimize the summing of the size of user-role assignments and that of role-permission assignments, in order to reduce the administration burden. The min-noise RMP aims to minimize the error of the matrix reconstruction. Different RMP variant can help pick and choose the mining results that perfectly suit a particular organizational need. However, most existing role mining methods lack flexibility and scalability, and cannot handle all these RMP variants in a unified way. System engineers need to deal with each problem variant individually, and these methods cannot mine valuable or meaningful results when the organizational needs change dynamically.Furthermore, a key characteristic of RBAC mechanism is that it allows the specification and enforcement of various security policies [18, 19], such as separation-of-duty constraints and cardinality constraints, which can reflect the constraint requirements of organizations while ensuring system security. A typical k-n SOD constraint states that at least k users are required to together perform a particular task that includes n operating permissions [20], which has been widely used in the banking industry and military systems. Another commonly used constraint in actual scenarios is referred to as cardinality constraint. It involves user-to-role cardinality constraint (URCC), permission-to-role cardinality constraint (PRCC), role-to-user cardinality constraint (RUCC), and role-to-permission cardinality constraint (RPCC), which restrict the maximum number of roles assigned to a user, the maximum number of roles to which a permission can be assigned, the maximum number of permissions assigned to a role, and the maximum number of users to which a role can be assigned, respectively [21]. For example, the general-manager role in a company is only assigned to one person; ordinary users cannot possess too many roles; otherwise, there is the possibility of the abuse of privileges. In the approaches for role engineering with cardinality constraints, however, most existing methods do not consider multiple cardinality constraints, such as the URCC and PRCC. Moreover, the bottom user-permission assignments already have been given in some form. However, in many cases, the access control systems are completely unknown in advance and need to be constructed.To address the abovementioned issues, this paper proposes a novel method, called hybrid role-engineering optimization with multiple cardinality constraints using natural language processing and integer linear programming techniques (HREOMCC_NLP&ILP). In summary, the main contributions of this work are as follows:(1)
To alleviate manual workloads and reduce human errors, we use natural language processing techniques (NLP), including the lexical parsing, ACP sentences identification, semantic role labeling, and post processing, in order to extract machine-readable and machine-enforceable ACPs from the natural language requirement documents, and then develop an initial access control system. We evaluate its performance on benchmark datasets and compare its performance to the existing method(2)
To suit the organizational needs flexibly, while enhancing the security of role engineering, we convert the role-engineering problem into the Boolean matrix decomposition (BMD) problem. We define several variants of the optimization problem with multiple cardinality constraints, according to different optimization objectives, and then present a unified modelling representation for all these variants using integer linear programming technique (ILP)(3)
To further verify whether the cardinality constraints can be satisfied in the constructed RBAC system, we present the heuristic algorithms for solving the optimization problems. We evaluate the performance of our method on both synthetic and real-world datasets and compare its performance to the existing methodsThe rest of the paper is organized as follows. In Section2, we discuss the related work and present some necessary preliminaries in Section 3. In Section 4, we propose a novel research methodology, which includes two aspects: (1) the top-down initial development of an access control system using natural language processing techniques and (2) bottom-up constrained role-engineering optimization using integer linear programming technique. Section 5 presents the heuristic algorithms. We implement the experiments and present performance evaluations and comparisons to the existing studies in Section 6. Section 7 concludes the paper and discusses future work.


## 2. Related Work

Conventional role-engineering methods are usually divided into two categories: the top-down and bottom-up.


### 2.1. Methods of Top-down Role Engineering

To extract access control policies from the given document resources, Fernandez and Hawkins [22] proposed a top-down basic framework for developing an RBAC system. Fontaine et al. [23] proposed an approach based on the object-requirement engineering, in order to extract authorization and obligation rules from natural language documents. Xiao et al. [24] utilized the deductive reasoning to find ACPs that did not require a labeled dataset and proposed an approach for automatic extraction of ACPs, named as Text2Policy. It uses the semantic role labeling technique with finite state transducers to implement sentence matches, with respect to the given access control patterns. If any match is successful, then the Text2Policy extracts the subjects, actions, and objects using the annotations within the sentence. Additionally, the Text2Policy needed to split complicated long sentences into short sentences with easy structures. Slankas et al. [25] adopted the supervised learning and inductive reasoning methods to find suitable ACPs based on a labeled dataset, proposed a method of extracting access control rules, named as ACRE, and then developed an access control system. None of these approaches consider the contextual environments. To this end, Baumgrass et al. [26] proposed a method to automatically find the role-engineering artifacts from business processes and scenario models. Molloy et al. [27] manually defined roles that correspond to the job responsibilities in the top-down way and then derived an optimal set of roles based on these candidate role results, in order to construct an RBAC system. Hernandez et al. [28] proposed a top-down method to generate roles from information that include the attributes of users and other objects, as well as the user-permission assignments. Frank et al. [29] proposed a probabilistic method, which identifies the business information that are relevant to the user-permission assignments, and then implement the role engineering using the identified information.


### 2.2. Methods of Bottom-up Role Engineering

Various bottom-up role-engineering methods have been proposed. According to whether or not constraints are taken into account, the state of the art studies are further divided into two categories: The unconstrained role engineering, and role engineering with constraints.


#### 2.2.1. Unconstrained Role Engineering

To reflect the semantic characteristics of functional requirements while enhancing the interpretability of role mining, Molloy et al. [30] proposed an optimization algorithm to discover optimal roles based on the formal concept lattices. To further optimize an RBAC system, Zhang et al. [31] proposed a novel role mining algorithm using the theory of graph optimization. However, there existed role redundancies that were not eliminated in the mining results. Ene et al. [32] adopted the methods of heuristics and graph theory to derive as few optimal roles as possible, in order to reduce the redundancies of mining roles. Lu et al. [15] used the methods of Boolean matrix decomposition and integer linear programming to propose a unified framework for several variants of role mining, including the basic RMP, δ-approx RMP, edge-RMP, and min-noise RMP, and presented the heuristic algorithms for solving these problems. However, the mining processes are complex, and the mining scales are very large. To reduce the complexity of solving problems, Colantonio et al. [33] separated the dataset of user-permission assignments into several subsets. To reduce the mining scale, Verde et al. [34] converted the role mining problem into a clustering problem, which compresses each single partition into a cluster, extracts similar features from different clusters, and ensures the integrity of the mining results. The constraints play a crucial role for ensuring system security. However, none of these methods take into consideration constraints in the role-engineering processes.


#### 2.2.2. Role Engineering with Constraints

In order to restrict the number of permissions assigned to a role, Blundo and Cimato [35] proposed a heuristic algorithm to discover a complete set of roles. To limit the maximum number of users related to a role, Hingankar and Sural [36] proposed a biclique-cover method to derive constrained roles. To restrict the number of roles assigned to a user, John et al. proposed two alternative approaches: the role priority-based approach (RPA) and coverage of permissions-based approach (CPA). The RPA prioritizes roles based on the number of permissions and then assigns optimal roles to users according to the priority order. The CPA iteratively picks roles with the largest number of permissions that are yet uncovered and ensures that the number of roles assigned to a user does not exceed a given number [37]. In order to limit the maximum number of users or that of permissions related to a role, Ma et al. [21] proposed a role mining algorithm to generate roles using the permission cardinality constraints and user cardinality constraints. Blundo et al. [38] comprehensively examined different types of cardinality constraints, defined the constrained mining problem for each constraint type, and presented efficient heuristics for solving these problems. Subsequently, to restrict the number of roles assigned to a user and the number of permissions assigned to a role simultaneously, they presented two heuristics to produce roles compliant with both the constraints [39]. However, all of these studies are post-processing methods, which first identify initial unconstrained role sets, and then consider constraints and derive optimal roles from the initial roles. In order to limit the maximum number of roles assigned to a user and a related permission simultaneously, Harika et al. proposed two optimization methods for role mining: the post processing and concurrent processing. The former mines roles without considering the cardinality constraints and constructs the initial user-role and role-permission assignments. Then, these assignment relationships are checked for constraint violation in the optimization phase and appropriately re-assigned, if necessary [40]. The latter implements the optimization with the double cardinality constraints, during the process of role mining. In addition, other constraints are also considered during or after the mining process in the literature. Sarana et al. [41] proposed three methods for role optimization with the separation-of-duty constraints. To satisfy separation-of-duty constraints while ensuring authorization security, Sun et al. [42] constructed various mutually exclusive constraints to implement the given separation-of-duty constraints, converted the authorization query problem into a partial maximal satisfiability problem, and proposed a novel role-mining optimization method.


### 2.3. Drawbacks of Existing Studies and Benefits of our Work

Obviously, there are three main drawbacks in the existing studies. The first drawback is that it is time-consuming, labor-intensive, and error-prone to manually extract the ACPs from the natural language specification documents, using the top-down role-engineering approaches. The second drawback is that the bottom-up approaches lack flexibility and scalability, and cannot generate valuable or meaningful roles when the organizational requirements change dynamically. The third drawback is that most existing studies do not consider the URCC and PRCC constraints simultaneously and assume that the bottom user-permission assignments already have been given in some form. However, in many cases, the access control systems are completely unknown in advance. In this work, we comprehensively consider the top business requirement specifications and bottom access control information and use natural language processing and integer linear programming techniques to propose a novel hybrid constrained role-engineering methodology, called HREOMCC_NLP&ILP, which is also post-processing and more adaptable to organizations that adopt the RBAC mechanism. We also compare the performance of the HREOMCC_NLP&ILP with that of the existing methods through experiments.


## 2.1. Methods of Top-down Role Engineering

To extract access control policies from the given document resources, Fernandez and Hawkins [22] proposed a top-down basic framework for developing an RBAC system. Fontaine et al. [23] proposed an approach based on the object-requirement engineering, in order to extract authorization and obligation rules from natural language documents. Xiao et al. [24] utilized the deductive reasoning to find ACPs that did not require a labeled dataset and proposed an approach for automatic extraction of ACPs, named as Text2Policy. It uses the semantic role labeling technique with finite state transducers to implement sentence matches, with respect to the given access control patterns. If any match is successful, then the Text2Policy extracts the subjects, actions, and objects using the annotations within the sentence. Additionally, the Text2Policy needed to split complicated long sentences into short sentences with easy structures. Slankas et al. [25] adopted the supervised learning and inductive reasoning methods to find suitable ACPs based on a labeled dataset, proposed a method of extracting access control rules, named as ACRE, and then developed an access control system. None of these approaches consider the contextual environments. To this end, Baumgrass et al. [26] proposed a method to automatically find the role-engineering artifacts from business processes and scenario models. Molloy et al. [27] manually defined roles that correspond to the job responsibilities in the top-down way and then derived an optimal set of roles based on these candidate role results, in order to construct an RBAC system. Hernandez et al. [28] proposed a top-down method to generate roles from information that include the attributes of users and other objects, as well as the user-permission assignments. Frank et al. [29] proposed a probabilistic method, which identifies the business information that are relevant to the user-permission assignments, and then implement the role engineering using the identified information.


## 2.2. Methods of Bottom-up Role Engineering

Various bottom-up role-engineering methods have been proposed. According to whether or not constraints are taken into account, the state of the art studies are further divided into two categories: The unconstrained role engineering, and role engineering with constraints.


### 2.2.1. Unconstrained Role Engineering

To reflect the semantic characteristics of functional requirements while enhancing the interpretability of role mining, Molloy et al. [30] proposed an optimization algorithm to discover optimal roles based on the formal concept lattices. To further optimize an RBAC system, Zhang et al. [31] proposed a novel role mining algorithm using the theory of graph optimization. However, there existed role redundancies that were not eliminated in the mining results. Ene et al. [32] adopted the methods of heuristics and graph theory to derive as few optimal roles as possible, in order to reduce the redundancies of mining roles. Lu et al. [15] used the methods of Boolean matrix decomposition and integer linear programming to propose a unified framework for several variants of role mining, including the basic RMP, δ-approx RMP, edge-RMP, and min-noise RMP, and presented the heuristic algorithms for solving these problems. However, the mining processes are complex, and the mining scales are very large. To reduce the complexity of solving problems, Colantonio et al. [33] separated the dataset of user-permission assignments into several subsets. To reduce the mining scale, Verde et al. [34] converted the role mining problem into a clustering problem, which compresses each single partition into a cluster, extracts similar features from different clusters, and ensures the integrity of the mining results. The constraints play a crucial role for ensuring system security. However, none of these methods take into consideration constraints in the role-engineering processes.


### 2.2.2. Role Engineering with Constraints

In order to restrict the number of permissions assigned to a role, Blundo and Cimato [35] proposed a heuristic algorithm to discover a complete set of roles. To limit the maximum number of users related to a role, Hingankar and Sural [36] proposed a biclique-cover method to derive constrained roles. To restrict the number of roles assigned to a user, John et al. proposed two alternative approaches: the role priority-based approach (RPA) and coverage of permissions-based approach (CPA). The RPA prioritizes roles based on the number of permissions and then assigns optimal roles to users according to the priority order. The CPA iteratively picks roles with the largest number of permissions that are yet uncovered and ensures that the number of roles assigned to a user does not exceed a given number [37]. In order to limit the maximum number of users or that of permissions related to a role, Ma et al. [21] proposed a role mining algorithm to generate roles using the permission cardinality constraints and user cardinality constraints. Blundo et al. [38] comprehensively examined different types of cardinality constraints, defined the constrained mining problem for each constraint type, and presented efficient heuristics for solving these problems. Subsequently, to restrict the number of roles assigned to a user and the number of permissions assigned to a role simultaneously, they presented two heuristics to produce roles compliant with both the constraints [39]. However, all of these studies are post-processing methods, which first identify initial unconstrained role sets, and then consider constraints and derive optimal roles from the initial roles. In order to limit the maximum number of roles assigned to a user and a related permission simultaneously, Harika et al. proposed two optimization methods for role mining: the post processing and concurrent processing. The former mines roles without considering the cardinality constraints and constructs the initial user-role and role-permission assignments. Then, these assignment relationships are checked for constraint violation in the optimization phase and appropriately re-assigned, if necessary [40]. The latter implements the optimization with the double cardinality constraints, during the process of role mining. In addition, other constraints are also considered during or after the mining process in the literature. Sarana et al. [41] proposed three methods for role optimization with the separation-of-duty constraints. To satisfy separation-of-duty constraints while ensuring authorization security, Sun et al. [42] constructed various mutually exclusive constraints to implement the given separation-of-duty constraints, converted the authorization query problem into a partial maximal satisfiability problem, and proposed a novel role-mining optimization method.


## 2.2.1. Unconstrained Role Engineering

To reflect the semantic characteristics of functional requirements while enhancing the interpretability of role mining, Molloy et al. [30] proposed an optimization algorithm to discover optimal roles based on the formal concept lattices. To further optimize an RBAC system, Zhang et al. [31] proposed a novel role mining algorithm using the theory of graph optimization. However, there existed role redundancies that were not eliminated in the mining results. Ene et al. [32] adopted the methods of heuristics and graph theory to derive as few optimal roles as possible, in order to reduce the redundancies of mining roles. Lu et al. [15] used the methods of Boolean matrix decomposition and integer linear programming to propose a unified framework for several variants of role mining, including the basic RMP, δ-approx RMP, edge-RMP, and min-noise RMP, and presented the heuristic algorithms for solving these problems. However, the mining processes are complex, and the mining scales are very large. To reduce the complexity of solving problems, Colantonio et al. [33] separated the dataset of user-permission assignments into several subsets. To reduce the mining scale, Verde et al. [34] converted the role mining problem into a clustering problem, which compresses each single partition into a cluster, extracts similar features from different clusters, and ensures the integrity of the mining results. The constraints play a crucial role for ensuring system security. However, none of these methods take into consideration constraints in the role-engineering processes.


## 2.2.2. Role Engineering with Constraints

In order to restrict the number of permissions assigned to a role, Blundo and Cimato [35] proposed a heuristic algorithm to discover a complete set of roles. To limit the maximum number of users related to a role, Hingankar and Sural [36] proposed a biclique-cover method to derive constrained roles. To restrict the number of roles assigned to a user, John et al. proposed two alternative approaches: the role priority-based approach (RPA) and coverage of permissions-based approach (CPA). The RPA prioritizes roles based on the number of permissions and then assigns optimal roles to users according to the priority order. The CPA iteratively picks roles with the largest number of permissions that are yet uncovered and ensures that the number of roles assigned to a user does not exceed a given number [37]. In order to limit the maximum number of users or that of permissions related to a role, Ma et al. [21] proposed a role mining algorithm to generate roles using the permission cardinality constraints and user cardinality constraints. Blundo et al. [38] comprehensively examined different types of cardinality constraints, defined the constrained mining problem for each constraint type, and presented efficient heuristics for solving these problems. Subsequently, to restrict the number of roles assigned to a user and the number of permissions assigned to a role simultaneously, they presented two heuristics to produce roles compliant with both the constraints [39]. However, all of these studies are post-processing methods, which first identify initial unconstrained role sets, and then consider constraints and derive optimal roles from the initial roles. In order to limit the maximum number of roles assigned to a user and a related permission simultaneously, Harika et al. proposed two optimization methods for role mining: the post processing and concurrent processing. The former mines roles without considering the cardinality constraints and constructs the initial user-role and role-permission assignments. Then, these assignment relationships are checked for constraint violation in the optimization phase and appropriately re-assigned, if necessary [40]. The latter implements the optimization with the double cardinality constraints, during the process of role mining. In addition, other constraints are also considered during or after the mining process in the literature. Sarana et al. [41] proposed three methods for role optimization with the separation-of-duty constraints. To satisfy separation-of-duty constraints while ensuring authorization security, Sun et al. [42] constructed various mutually exclusive constraints to implement the given separation-of-duty constraints, converted the authorization query problem into a partial maximal satisfiability problem, and proposed a novel role-mining optimization method.


## 2.3. Drawbacks of Existing Studies and Benefits of our Work

Obviously, there are three main drawbacks in the existing studies. The first drawback is that it is time-consuming, labor-intensive, and error-prone to manually extract the ACPs from the natural language specification documents, using the top-down role-engineering approaches. The second drawback is that the bottom-up approaches lack flexibility and scalability, and cannot generate valuable or meaningful roles when the organizational requirements change dynamically. The third drawback is that most existing studies do not consider the URCC and PRCC constraints simultaneously and assume that the bottom user-permission assignments already have been given in some form. However, in many cases, the access control systems are completely unknown in advance. In this work, we comprehensively consider the top business requirement specifications and bottom access control information and use natural language processing and integer linear programming techniques to propose a novel hybrid constrained role-engineering methodology, called HREOMCC_NLP&ILP, which is also post-processing and more adaptable to organizations that adopt the RBAC mechanism. We also compare the performance of the HREOMCC_NLP&ILP with that of the existing methods through experiments.


## 3. Preliminaries

Before actually proposing our novel method, we present some preliminaries that are discussed in this paper, including the basic components of role engineering, several representative RMP variants, cardinality constraints, integer linear programming, and natural language processing techniques.


### 3.1. Basic Components of Role Engineering

According to the NIST standard of RBAC, conventional role engineering consists of the following basic components:(1)
U, P, and R are the basic set elements of RBAC, which represent the sets of users, permissions, and roles, respectively(2)
UPA⊆U×P, which represents a many-to-many mapping relationship of user-permission assignments(3)
URA⊆U×R, which represents a many-to-many mapping relationship of user-role assignments(4)
RPA⊆R×P, which represents a many-to-many mapping relationship of role-permission assignments(5)
user_rolesu=r∃r∈R:u,r∈URA, which represents the set of roles assigned to user u(6)
role_usersr=u∃u∈U:u,r∈URA, which represents the set of users associated with role r(7)
perm_rolesp=r∃r∈R:r,p∈RPA, which represents the set of roles associated with permission p(8)
role_permsr=p∃p∈P:r,p∈RPA, which represents the set of permissions assigned to role r(9)
user_permsu=p∃p∈P,∃r∈R:u,r∈URA∧r,p∈RPA, which represents the set of permissions assigned to user u in RBAC(10)
perm_usersp=u∃u∈U,∃r∈R:u,r∈URA∧r,p∈RPA, which represents the set of users associated with permission p in RBACFor convenience, theUPA, URA, and RPA are also used to represent Boolean matrices corresponding to their respective assignment relationships.


### 3.2. Several Representative RMP Variants

According to the different constraint conditions and objectives in the mining process, we consider four different RMP variants with no constraints, including the basic RMP,δ-approx RMP, edge-RMP, and min-noise RMP, which can be converted into the BMD problems as follows [16, 17].The basic RMP states that, given a setU of users, a set P of permissions, and a matrix UPA of user-permission assignments, find a set R of roles, a matrix URA of user-role assignments, and a matrix RPA of role-permission assignments, such that the UPA can be precisely Boolean decomposed as the URA and RPA and the number of the mining roles is minimum. This process is formalized as follows:
(1)minRURA⊗RPA=UPA,Different from the basic RMP, theδ-approx RMP allows the matrix reconstruction with an error value δ when the UPA is approximately Boolean decomposed as the URA and RPA, which is formalized as follows:
(2)minRURA⊗RPA‐UPA1≤δ.Different from the basic RMP, the edge-RMP aims to minimize the summing of the number of the user-role assignments and that of the role-permission assignments, which is formalized as follows:(3)minURA+RPAURA⊗RPA=UPA.At last, the min-noise RMP aims to minimize the reconstruction error, while considering that the number of the mining roles is less than a fixed valuek, which is formalized as follows:
(4)minURA⊗RPA‐UPA1R≤k.The basic RMP is the primary RMP variant, though there are similarities and differences towards the constraint conditions and mining objectives for all the RMP variants. The Fast Miner method, which is used to solve the basic RMP, mainly consists of the following steps:(1)
According to the hash mapping rule, a given access control matrix is converted into the user-permission assignment relationship(2)
To reduce the role-engineering scale, different users who have the same permissions in the permission assignments are grouped together, and an initial set of roles is constructed(3)
All the potentially interesting roles are identified by implementing intersections between any pair of the initial roles, and they are regarded as new candidate roles


### 3.3. Cardinality Constraints

Two different types of cardinality constraints, URCC and PRCC, which have been proven to be mutually exclusive [40], are taken into consideration.The URCC states that given a setU of users, a set R of roles, and threshold MRCuser, the maximum number of roles assigned to any user should not exceed MRCuser. This can be formalized as follows:
(5)∀u∈U:user_rolesu∩R≤MRCuser.The PRCC states that given a setP of permissions, a set R of roles, and threshold MRCperm, the maximum number of roles to which any permission can be assigned should not exceed MRCperm. This can be formalized as follows:
(6)∀p∈P:perm_rolesp∩R≤MRCperm.In addition, since the mapping relationships ofURA and RPA are bidirectional, there are the other two constraints RUCC and RPCC, which are not discussed in this work.


### 3.4. Integer Linear Programming Technique (ILP)

The ILP problem is an important branch of operational research and is widely used in economic analysis, operation management, and engineering technology [15]. The 0-1 programming method in the ILP is often used to solve the practical problems such as the assignment, location, and delivery. The general form of solving the problem using the 0-1 programming is represented as follows:
(7)mincT⋅xst.A⋅x≤bxi∈0,1,1≤i≤n.where mincT⋅x and A⋅x≤bxi∈0,1,1≤i≤n indicate the objective function and constraint conditions, respectively.


### 3.5. Natural Language Processing Techniques (NLP)

In general, most modern NLP parsers [43] for analyzing NLACP documents consist of the following main tasks:
(1)
Tokenization, which detects individual words, punctuations, and other items within a text(2)
Sentence segmentation, which identifies the boundaries of sentences(3)
Part-of-speech tagging (POS), which determines whether a token is a member of nouns, verbs, or adjectives(4)
Lemmatization, which produces the common root prototype for morphologically similar words such as “does,” “done,” and “doing” that are the different forms with respect to the common prototype “do”(5)
Named-entity recognition (NER), which categorizes all the nouns within a sentence into different entity types such as person names, organization names, time, and locations(6)
Co-reference resolution, which determines whether or not two expressions in the texts refer to the same entity or event(7)
Semantic role labeling (SRL), which identifies different predicates within a sentence using the semantic arguments, is also called shallow semantic parsing


## 3.1. Basic Components of Role Engineering

According to the NIST standard of RBAC, conventional role engineering consists of the following basic components:(1)
U, P, and R are the basic set elements of RBAC, which represent the sets of users, permissions, and roles, respectively(2)
UPA⊆U×P, which represents a many-to-many mapping relationship of user-permission assignments(3)
URA⊆U×R, which represents a many-to-many mapping relationship of user-role assignments(4)
RPA⊆R×P, which represents a many-to-many mapping relationship of role-permission assignments(5)
user_rolesu=r∃r∈R:u,r∈URA, which represents the set of roles assigned to user u(6)
role_usersr=u∃u∈U:u,r∈URA, which represents the set of users associated with role r(7)
perm_rolesp=r∃r∈R:r,p∈RPA, which represents the set of roles associated with permission p(8)
role_permsr=p∃p∈P:r,p∈RPA, which represents the set of permissions assigned to role r(9)
user_permsu=p∃p∈P,∃r∈R:u,r∈URA∧r,p∈RPA, which represents the set of permissions assigned to user u in RBAC(10)
perm_usersp=u∃u∈U,∃r∈R:u,r∈URA∧r,p∈RPA, which represents the set of users associated with permission p in RBACFor convenience, theUPA, URA, and RPA are also used to represent Boolean matrices corresponding to their respective assignment relationships.


## 3.2. Several Representative RMP Variants

According to the different constraint conditions and objectives in the mining process, we consider four different RMP variants with no constraints, including the basic RMP,δ-approx RMP, edge-RMP, and min-noise RMP, which can be converted into the BMD problems as follows [16, 17].The basic RMP states that, given a setU of users, a set P of permissions, and a matrix UPA of user-permission assignments, find a set R of roles, a matrix URA of user-role assignments, and a matrix RPA of role-permission assignments, such that the UPA can be precisely Boolean decomposed as the URA and RPA and the number of the mining roles is minimum. This process is formalized as follows:
(1)minRURA⊗RPA=UPA,Different from the basic RMP, theδ-approx RMP allows the matrix reconstruction with an error value δ when the UPA is approximately Boolean decomposed as the URA and RPA, which is formalized as follows:
(2)minRURA⊗RPA‐UPA1≤δ.Different from the basic RMP, the edge-RMP aims to minimize the summing of the number of the user-role assignments and that of the role-permission assignments, which is formalized as follows:(3)minURA+RPAURA⊗RPA=UPA.At last, the min-noise RMP aims to minimize the reconstruction error, while considering that the number of the mining roles is less than a fixed valuek, which is formalized as follows:
(4)minURA⊗RPA‐UPA1R≤k.The basic RMP is the primary RMP variant, though there are similarities and differences towards the constraint conditions and mining objectives for all the RMP variants. The Fast Miner method, which is used to solve the basic RMP, mainly consists of the following steps:(1)
According to the hash mapping rule, a given access control matrix is converted into the user-permission assignment relationship(2)
To reduce the role-engineering scale, different users who have the same permissions in the permission assignments are grouped together, and an initial set of roles is constructed(3)
All the potentially interesting roles are identified by implementing intersections between any pair of the initial roles, and they are regarded as new candidate roles


## 3.3. Cardinality Constraints

Two different types of cardinality constraints, URCC and PRCC, which have been proven to be mutually exclusive [40], are taken into consideration.The URCC states that given a setU of users, a set R of roles, and threshold MRCuser, the maximum number of roles assigned to any user should not exceed MRCuser. This can be formalized as follows:
(5)∀u∈U:user_rolesu∩R≤MRCuser.The PRCC states that given a setP of permissions, a set R of roles, and threshold MRCperm, the maximum number of roles to which any permission can be assigned should not exceed MRCperm. This can be formalized as follows:
(6)∀p∈P:perm_rolesp∩R≤MRCperm.In addition, since the mapping relationships ofURA and RPA are bidirectional, there are the other two constraints RUCC and RPCC, which are not discussed in this work.


## 3.4. Integer Linear Programming Technique (ILP)

The ILP problem is an important branch of operational research and is widely used in economic analysis, operation management, and engineering technology [15]. The 0-1 programming method in the ILP is often used to solve the practical problems such as the assignment, location, and delivery. The general form of solving the problem using the 0-1 programming is represented as follows:
(7)mincT⋅xst.A⋅x≤bxi∈0,1,1≤i≤n.where mincT⋅x and A⋅x≤bxi∈0,1,1≤i≤n indicate the objective function and constraint conditions, respectively.


## 3.5. Natural Language Processing Techniques (NLP)

In general, most modern NLP parsers [43] for analyzing NLACP documents consist of the following main tasks:
(1)
Tokenization, which detects individual words, punctuations, and other items within a text(2)
Sentence segmentation, which identifies the boundaries of sentences(3)
Part-of-speech tagging (POS), which determines whether a token is a member of nouns, verbs, or adjectives(4)
Lemmatization, which produces the common root prototype for morphologically similar words such as “does,” “done,” and “doing” that are the different forms with respect to the common prototype “do”(5)
Named-entity recognition (NER), which categorizes all the nouns within a sentence into different entity types such as person names, organization names, time, and locations(6)
Co-reference resolution, which determines whether or not two expressions in the texts refer to the same entity or event(7)
Semantic role labeling (SRL), which identifies different predicates within a sentence using the semantic arguments, is also called shallow semantic parsing


## 4. Proposed Methodology

In this section, we propose a novel research methodology, named as HREOMCC_NLP&ILP, which is twofold: (1) the top-down initial development of an access control system using natural language processing techniques and (2) bottom-up constrained role-engineering optimization using integer linear programming technique. Specifically, for the given NLACP specification documents, we first utilize the lexical parsing such as sentence segmentation and tokenization, ACP sentences identification, semantic role labeling, and post processing such as named-entity recognition and argument extension, in order to extract the actual ACP policies, and then construct an initial access control system. Subsequently, we convert the role-engineering problems with the URCC and PRCC into BMD problems and use the 0-1 programming method to uniformly model several variants of the optimization problem. Last, we implement the role-engineering optimization and present the heuristic algorithms to verify whether the cardinality constraints can be satisfied in the constructed role-engineering system. An overall view of the proposed framework is shown in Figure1.Figure 1
Overview of the proposed framework for hybrid role-engineering optimization.


### 4.1. Top-down Initial Development of the Access Control System

In this subsection, we use the NLP techniques to automatically extract ACPs from the given NLACP documents and then develop an initial access control system.


#### 4.1.1. Preprocessing

Essentially, the NLACPs describe who can access what resources in what way. We read through the whole natural language documents and carry out the sentence segmentation and tokenization. To make the input texts to be easy for evaluation, one critical step is to identify all the sentences and separate them by periods and carriage returns, which is easy to understand. Thus, we use the toolkit CoreNLP [44] to handle this issue and make sure that each complete sentence is laid on a unique line. Further, there are many pronouns in the documents, and sometimes we do not have the clear ideas of these pronouns. For example, consider the following sentence: The doctor can read and write the healthcare records of the patients with whom he or she has immediately associated. Here, “doctor,” “he,” and “she” all correspond to the same role entity. To correctly extract the ACP elements from the candidate ACP sentences, we carry out the co-reference resolution to identify the clear meanings of these pronouns. Thus, we utilize a fast and robust algorithm, called pronoun anaphora resolution [45], in order to replace each pronoun with its corresponding referent appeared somewhere in the documents.


#### 4.1.2. ACP Sentences Identification

Usually, the NLACP documents contain the contents that mainly describe functional requirements and are not necessary related to the ACP contents. Although these documents also contain ACP sentences, the process of attempting to sift through the whole documents to distinguish ACP sentences from non-ACP contents is error-prone and tedious. To correctly extract ACP sentences from the natural language documents, it is important to find the contents that seem to be potential ACP sentences and then make further analysis only on these sentences. In this work, we employ the ACRE method [25] that has been proven to correctly identify the ACP elements.


#### 4.1.3. Semantic Role Labeling (SRL)

SRL, sometimes also called shallow semantic parsing in the natural language processing, aims to detect the semantic arguments that are associated with the predicate (that is, a verb in fact) of a sentence and categorize them into their corresponding roles. The SRL uses the notations in the project Propbank [46] to label the semantic structure of the predicate argument and assigns different semantic roles to the entities that are related to a specific verb in a sentence, in order to identify who did what to whom. It is very critical to recognize these semantic arguments for answering the questions such as “who,” “what,” “when,” and “where,” which are especially used in the extraction of ACP sentences from all the sentences, for example: Doctor Jam can only read the healthcare records of patient A.Then, the semantic roles for predicates defined in the Probank project can be inserted into the sentence, which can be represented as follows:[Arg0 Doctor Jam] [ArgM-MOD can only] [V read] [Arg1 the healthcare records of patient A], where V, ArgM-MOD, Arg0, and Arg1 denotes the verb, modal, assigning subject and assigned object, respectively.The SRL is very important for making sense of the meaning of a sentence, of which the abstraction level is higher than other representation methods such as the syntax tree. Consider the following two sentences:“One person cannot possess the accountant and cashier roles at the same time.”“The accountant and cashier roles cannot be possessed by one person at the same time.”Although the latter sentence is different from the former in the syntactic form, they have the same semantic roles.Generally, for the given sentence, the task of SRL includes analyzing the meanings of the sentence expressed by the target verb, while extracting the constituents of the sentence that are filled by the semantic roles of the verb argument. Here, we use the following notations to represent the policy ACP:arg0;predicate;arg1, where arg0 usually represents the subject for predicate and arg1 represents the object that predicate affects.In this work, we use the semantic role labeler, named as Semantic/syntax Extraction using a Neural Network Architecture (SENNA) [47], to analyze the levels of sentences. The SENNA is a multilayer architecture of neural network that can handle amounts of natural language documents such as POS, sentence segmentation, NER, and SRL with satisfactory effects. It depends on large-scale datasets that are unlabeled and allows a training algorithm to find useful representation information with respect to the access requests. Particularly, the SENNA has three main features: fast speed, independency, and accuracy.


#### 4.1.4. Post-Processing

Additional processing is needed after the generation of annotation results using the abovementioned SRL tools. This is because the system analysts usually use the natural language and their specific grammars to state requirements specification, and they do not possess the technical knowledges of the system. As a result, extraction of ACP sentences from their documents becomes very complicated. To improve the accuracy of the extracted ACPs, the named-entity recognition (NER) and argument extension are applied into the SRL results.The task of NER is to identify the name entities and word sequences such as person names, organization names, time, and location, in order to generate the annotated sentences that highlight the entity names as shown in the following example:[Organization name Hospital Management System], [Person name Nurse-in-Charge] and [Person name Patient] can only read patients’ general healthcare informationHere,Hospital Management System is an organization name consisting of three tokens, Nurse-in-Charge is a person consisting of three tokens, and Patient is also person consisting of one token.In fact, most of the extracted ACP sentences are also complicated, because they are sated by the system analysts using natural language and their own grammar structures. One of these complicated cases is that sometimes more than one access control policy is buried in a sentence. For example, consider the following the extracted roles for the predicate retrieve using SRL as follows:[Arg0 Educational Management System, Teaching Secretary and Class Teacher] [ArgM-MOD can] [V retrieve] and update [Arg1 students’ information] in the registration systemMoreover, as seen from the comparison between the semantic arguments using SRL and the actual ACPs, the SRL output is formally represented with the annotations of SRL, and it can be interpreted as an abstract form for the ACP sentence. Therefore, the SRL result should be extended to produce all the related ACPs. This extension could list all the named entities in Arg0 and Arg1 as subjects, and objects, respectively. After extraction of all the entities, the combinations of these entities with each predicate can be referred to as ACPs. Consider the above example again; there are six different ACPs involved in the sentence using the arguments extension:{Educational Management System; retrieve; students’ information}{Educational Management System; update; students’ information}{Teaching Secretary; retrieve; students’ information}{Teaching Secretary; update; students’ information}{Class Teacher; retrieve; students’ information}{Class Teacher; update; students’ information}


#### 4.1.5. Development of an Initial Access Control System

When all the ACP sentences in the documents are extracted, the extracted information can be utilized to define roles by a role extractor, and these roles can be used to build an initial RBAC system. As seen from the form of the ACPs, many subjects correspond to the job functions in organizations, such as doctors, nurses, and patients in a hospital, which can represent different roles. Thus, we only need to take into consideration the ACPs, find the ones with the same subject, group them together into one role, and implement role-permission assignments. Since the operation and object elements involved in the ACPs can be used to construct permissions in RBAC, these permissions can be assigned to different roles according to the specific subjects from the extracted ACPs.


### 4.2. Bottom-up Constrained Role-Engineering Optimization

To flexibly suit diverse requirements of organizations, based on the basic RMP,δ-approx RMP, edge-RMP, and min-noise RMP, as well as the cardinality constraints URCC and PRCC, we utilize the ILP technique to uniformly model the constrained role-engineering problems in the initial constructed system. First, we present the definitions for these optimization problems using the BMD method.


#### 4.2.1. Problem Definitions

Definition 1.
Basic role-engineering optimization problem, basicREOPURCC&PRCC
Given a matrixUPAn×m of user-permission assignments, the initial Boolean decomposed matrices for the UPAn×m, and two particular constraint thresholds MRCuser and MRCperm, find two matrices URAn×k and RPAk×m such that, (1) the number k of the optimal roles, which is regarded as the optimization objective, should be minimum; (2) the UPAn×m is precisely Boolean decomposed as the URAn×k and RPAk×m to ensure the integrity of the matrix reconstruction; the number of roles assigned to any user is less than or equal to MRCuser; and/or the number of roles to which any permission can be assigned is less than or equal to MRCperm, which are together regarded as the constraint conditions. This process can be formalized as follows:
(8)minkURAn×k⊗RPAk×m=UPAn×m∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,mDefinition 2.
δ-approx role-engineering optimization problem, δ-approx REOPURCC&PRCC
Compared to Definition1, the integrity constraint becomes that the UPAn×m can be approximately reconstructed by the URAn×k and RPAk×m with a reconstruction error δ. This process can be formalized as follows:
(9)minkURAn×k⊗RPAk×m‐UPAn×m1≤δ∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,mDefinition 3.
Edge-role-engineering optimization problem,edge−REOPURCC&PRCC
Compared to Definition1, the optimization objective becomes that the summing of the number of the user-role assignments and that of the role-permission assignments should be minimum. This process can be formalized as follows:
(10)minURAn×k+RPAk×mURAn×k⊗RPAk×m=UPAn×m∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,m.Definition 4.
Min-noise role-engineering optimization problem, min-noiseREOPURCC&PRCC
Compared to the above definitions, the optimization objective becomes that the reconstruction error should be minimum when the numberkof the mining roles is no more than k’. This process can be formalized as follows:
(11)minURAn×k⊗RPAk×m‐UPAn×m1k≤k′∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,m.


#### 4.2.2. Complexity Analysis

Now, we analyze the computational complexity of the above four optimization problems. Notice that, first, the basic RMP can be viewed as a special case of the basicREOPURCC&PRCC when both the constraint thresholds take values of the number of mining roles. Since the decision version of the basic RMP has been proven to be NP-complete [16], so is the basic REOPURCC&PRCC. Similarly, the basic REOPURCC&PRCC can be viewed as a special case of the δ-approx REOPURCC&PRCC when the reconstruction error takes a value of 0, and the δ-approx REOPURCC&PRCC is also NP-complete. The differences of the other two REOP variants are either the optimization objective or constraint condition, and then the following statement can be concluded.Statement 1. ThebasicREOPURCC&PRCC, δ-approx REOPURCC&PRCC, edge-REOPURCC&PRCC, and min-noise REOPURCC&PRCC are all NP-hard


#### 4.2.3. Unified Modelling Framework for REOP Variants Using 0-1 Programming

The differences among all the REOP variants lie in the constraint conditions and optimization objectives. The basicREOPURCC&PRCC is the most basic and important variant, and the others can be easily extended once the basic REOPURCC&PRCC is modelled. Here, for the convenience of discussion, Boolean matrices Xn×m, Cn×k, and Rk×m are used to represent matrices UPAn×m, URAn×k, and RPAk×m, respectively, and the variants xit, cij, and rjt are used to denote the cells of matrices Xn×m, Cn×k, and Rk×m, respectively. According to Definitions 1–4, the unified modelling framework for all the REOP variants via 0-1 programming are presented as follows.Step 1.
Suppose there areq candidate roles, r1,r2,⋯,rq, and the set of all these roles can be represented as the matrix R. Next, define a new set d1,d2,⋯,dq of identifier variables, in which role rj is present when dj=1; otherwise, rj is absent. Thus, the number of roles can be denoted as k=∑j=1qdj. Furthermore, several observations can be concluded as follows:
(1)
To ensure the integrity of the optimization process, if one user has a permission, which is represented asxit=1, then at least one role containing permission t should be assigned to user i, which can be denoted as ∑j=1qcij⋅rjt≥1,∀xit=1; otherwise, any role containing permission t should not be assigned to user i, which can be denoted as ∑j=1qcij⋅rjt=0,∀xit=0(2)
At least one user has a rolerj when dj=1, that is, at least one variable in c1j,c2j,⋯,cnj has a value of 1, which can be denoted as ∀i:dj≥cij. Similarly, at least one variable in rj1,rj2,⋯,rjm has a value of 1, which can be denoted as ∀t:dj≥rjt(3)
The cardinality constraints URCC and PRCC should be taken into consideration, which can be denoted as∑j=1qcij≤MRCuser and ∑j=1qrjt≤MRCperm, respectively
Based on these analyses, we model the basicREOPURCC&PRCC in Equation (12) as follows, where min∑j=1qdj represents the optimization objective, and the other parts of the equation represent the constraint conditions:
(12)min∑j=1qdjst.∑j=1qcij⋅rjt≥1,∀xit=1∑j=1qcij⋅rjt=0,∀xit=0∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjt,dj∈0,1,cij∈0,1,rjt∈0,11≤j≤q,1≤i≤n,1≤t≤m.Step 2.
Compared with the basicREOPURCC&PRCC, the optimization objective of the δ-approx REOPURCC&PRCC remains unchanged, while the constraint conditions vary and tolerate a reconstruction error. Thus, we only need to update the constraints and follow the same target function as shown in Step 1. For this purpose, a slack variable x′it is employed to make sure that the reconstruction matrix is acceptable, and the reconstruction error does not exceed a particular value. We model the δ-approx REOPURCC&PRCC in Equation (13) as follows, where min∑j=1qdj represents the optimization objective and the other parts of the equation represent the updated constraint conditions:
(13)min∑j=1qdjst.∑j=1qcij⋅rjt+x′it≥1,∀xit=1∑j=1qcij⋅rjt−x′it=0,∀xit=0∑i=1n∑t=1mx′it≤δ∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjt,dj∈0,1,cij∈0,1,rjt∈0,1,x′it∈0,11≤j≤q,1≤i≤n,1≤t≤mStep 3.
Compared with the basicREOPURCC&PRCC, the constraint conditions of the edge-REOPURCC&PRCC remain unchanged, while the optimization objective varies. Thus, we only need to update the target function and follow the same constraints as shown in Step 1. To reduce the space cost of the modelling, the users with the same permission set are clustered for a given set R of candidate roles. Assume that there are n’ different permission sets, the number of users corresponding to these sets are u1,u2,⋯,andun’, and then we model the edge-REOPURCC&PRCC in Equation (14) as follows, where min∑i=1n′ui⋅∑j=1qcij+∑j=1qdj⋅∑t=1mrjt represents the updated optimization objective and the other parts of the equation represent the constraint conditions:
(14)min∑i=1n′ui⋅∑j=1qcij+∑j=1qdj⋅∑t=1mrjtst.∑j=1qcij⋅rjt≥1,∀xit=1∑j=1qcij⋅rjt=0,∀xit=0∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjt,dj∈0,1,cij∈0,1,rjt∈0,11≤j≤q,1≤i≤n′,1≤t≤m.Step 4.
Compared with theδ-approx REOPURCC&PRCC, both the optimization objective and constraint conditions vary for the min-noise REOPURCC&PRCC. To address these issues, we need to make some improvements: Remove the expressions with the slack variables from the constraint conditions, construct a new objective function using these slack variables, and add a new expression of the upper limit number of roles into the constraint conditions. We model the min-noise REOPURCC&PRCC in Equation (15) as follows, where min∑i=1n∑t=1mx′it represents the optimization objective and the other parts of the equation are the constraint conditions:
(15)min∑i=1n∑t=1mx′itst.∑j=1qdj≤k′∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjtdj∈0,1,cij∈0,1,rjt∈0,1,x′it∈0,11≤j≤q,1≤i≤n,1≤t≤m.


## 4.1. Top-down Initial Development of the Access Control System

In this subsection, we use the NLP techniques to automatically extract ACPs from the given NLACP documents and then develop an initial access control system.


### 4.1.1. Preprocessing

Essentially, the NLACPs describe who can access what resources in what way. We read through the whole natural language documents and carry out the sentence segmentation and tokenization. To make the input texts to be easy for evaluation, one critical step is to identify all the sentences and separate them by periods and carriage returns, which is easy to understand. Thus, we use the toolkit CoreNLP [44] to handle this issue and make sure that each complete sentence is laid on a unique line. Further, there are many pronouns in the documents, and sometimes we do not have the clear ideas of these pronouns. For example, consider the following sentence: The doctor can read and write the healthcare records of the patients with whom he or she has immediately associated. Here, “doctor,” “he,” and “she” all correspond to the same role entity. To correctly extract the ACP elements from the candidate ACP sentences, we carry out the co-reference resolution to identify the clear meanings of these pronouns. Thus, we utilize a fast and robust algorithm, called pronoun anaphora resolution [45], in order to replace each pronoun with its corresponding referent appeared somewhere in the documents.


### 4.1.2. ACP Sentences Identification

Usually, the NLACP documents contain the contents that mainly describe functional requirements and are not necessary related to the ACP contents. Although these documents also contain ACP sentences, the process of attempting to sift through the whole documents to distinguish ACP sentences from non-ACP contents is error-prone and tedious. To correctly extract ACP sentences from the natural language documents, it is important to find the contents that seem to be potential ACP sentences and then make further analysis only on these sentences. In this work, we employ the ACRE method [25] that has been proven to correctly identify the ACP elements.


### 4.1.3. Semantic Role Labeling (SRL)

SRL, sometimes also called shallow semantic parsing in the natural language processing, aims to detect the semantic arguments that are associated with the predicate (that is, a verb in fact) of a sentence and categorize them into their corresponding roles. The SRL uses the notations in the project Propbank [46] to label the semantic structure of the predicate argument and assigns different semantic roles to the entities that are related to a specific verb in a sentence, in order to identify who did what to whom. It is very critical to recognize these semantic arguments for answering the questions such as “who,” “what,” “when,” and “where,” which are especially used in the extraction of ACP sentences from all the sentences, for example: Doctor Jam can only read the healthcare records of patient A.Then, the semantic roles for predicates defined in the Probank project can be inserted into the sentence, which can be represented as follows:[Arg0 Doctor Jam] [ArgM-MOD can only] [V read] [Arg1 the healthcare records of patient A], where V, ArgM-MOD, Arg0, and Arg1 denotes the verb, modal, assigning subject and assigned object, respectively.The SRL is very important for making sense of the meaning of a sentence, of which the abstraction level is higher than other representation methods such as the syntax tree. Consider the following two sentences:“One person cannot possess the accountant and cashier roles at the same time.”“The accountant and cashier roles cannot be possessed by one person at the same time.”Although the latter sentence is different from the former in the syntactic form, they have the same semantic roles.Generally, for the given sentence, the task of SRL includes analyzing the meanings of the sentence expressed by the target verb, while extracting the constituents of the sentence that are filled by the semantic roles of the verb argument. Here, we use the following notations to represent the policy ACP:arg0;predicate;arg1, where arg0 usually represents the subject for predicate and arg1 represents the object that predicate affects.In this work, we use the semantic role labeler, named as Semantic/syntax Extraction using a Neural Network Architecture (SENNA) [47], to analyze the levels of sentences. The SENNA is a multilayer architecture of neural network that can handle amounts of natural language documents such as POS, sentence segmentation, NER, and SRL with satisfactory effects. It depends on large-scale datasets that are unlabeled and allows a training algorithm to find useful representation information with respect to the access requests. Particularly, the SENNA has three main features: fast speed, independency, and accuracy.


### 4.1.4. Post-Processing

Additional processing is needed after the generation of annotation results using the abovementioned SRL tools. This is because the system analysts usually use the natural language and their specific grammars to state requirements specification, and they do not possess the technical knowledges of the system. As a result, extraction of ACP sentences from their documents becomes very complicated. To improve the accuracy of the extracted ACPs, the named-entity recognition (NER) and argument extension are applied into the SRL results.The task of NER is to identify the name entities and word sequences such as person names, organization names, time, and location, in order to generate the annotated sentences that highlight the entity names as shown in the following example:[Organization name Hospital Management System], [Person name Nurse-in-Charge] and [Person name Patient] can only read patients’ general healthcare informationHere,Hospital Management System is an organization name consisting of three tokens, Nurse-in-Charge is a person consisting of three tokens, and Patient is also person consisting of one token.In fact, most of the extracted ACP sentences are also complicated, because they are sated by the system analysts using natural language and their own grammar structures. One of these complicated cases is that sometimes more than one access control policy is buried in a sentence. For example, consider the following the extracted roles for the predicate retrieve using SRL as follows:[Arg0 Educational Management System, Teaching Secretary and Class Teacher] [ArgM-MOD can] [V retrieve] and update [Arg1 students’ information] in the registration systemMoreover, as seen from the comparison between the semantic arguments using SRL and the actual ACPs, the SRL output is formally represented with the annotations of SRL, and it can be interpreted as an abstract form for the ACP sentence. Therefore, the SRL result should be extended to produce all the related ACPs. This extension could list all the named entities in Arg0 and Arg1 as subjects, and objects, respectively. After extraction of all the entities, the combinations of these entities with each predicate can be referred to as ACPs. Consider the above example again; there are six different ACPs involved in the sentence using the arguments extension:{Educational Management System; retrieve; students’ information}{Educational Management System; update; students’ information}{Teaching Secretary; retrieve; students’ information}{Teaching Secretary; update; students’ information}{Class Teacher; retrieve; students’ information}{Class Teacher; update; students’ information}


### 4.1.5. Development of an Initial Access Control System

When all the ACP sentences in the documents are extracted, the extracted information can be utilized to define roles by a role extractor, and these roles can be used to build an initial RBAC system. As seen from the form of the ACPs, many subjects correspond to the job functions in organizations, such as doctors, nurses, and patients in a hospital, which can represent different roles. Thus, we only need to take into consideration the ACPs, find the ones with the same subject, group them together into one role, and implement role-permission assignments. Since the operation and object elements involved in the ACPs can be used to construct permissions in RBAC, these permissions can be assigned to different roles according to the specific subjects from the extracted ACPs.


## 4.1.1. Preprocessing

Essentially, the NLACPs describe who can access what resources in what way. We read through the whole natural language documents and carry out the sentence segmentation and tokenization. To make the input texts to be easy for evaluation, one critical step is to identify all the sentences and separate them by periods and carriage returns, which is easy to understand. Thus, we use the toolkit CoreNLP [44] to handle this issue and make sure that each complete sentence is laid on a unique line. Further, there are many pronouns in the documents, and sometimes we do not have the clear ideas of these pronouns. For example, consider the following sentence: The doctor can read and write the healthcare records of the patients with whom he or she has immediately associated. Here, “doctor,” “he,” and “she” all correspond to the same role entity. To correctly extract the ACP elements from the candidate ACP sentences, we carry out the co-reference resolution to identify the clear meanings of these pronouns. Thus, we utilize a fast and robust algorithm, called pronoun anaphora resolution [45], in order to replace each pronoun with its corresponding referent appeared somewhere in the documents.


## 4.1.2. ACP Sentences Identification

Usually, the NLACP documents contain the contents that mainly describe functional requirements and are not necessary related to the ACP contents. Although these documents also contain ACP sentences, the process of attempting to sift through the whole documents to distinguish ACP sentences from non-ACP contents is error-prone and tedious. To correctly extract ACP sentences from the natural language documents, it is important to find the contents that seem to be potential ACP sentences and then make further analysis only on these sentences. In this work, we employ the ACRE method [25] that has been proven to correctly identify the ACP elements.


## 4.1.3. Semantic Role Labeling (SRL)

SRL, sometimes also called shallow semantic parsing in the natural language processing, aims to detect the semantic arguments that are associated with the predicate (that is, a verb in fact) of a sentence and categorize them into their corresponding roles. The SRL uses the notations in the project Propbank [46] to label the semantic structure of the predicate argument and assigns different semantic roles to the entities that are related to a specific verb in a sentence, in order to identify who did what to whom. It is very critical to recognize these semantic arguments for answering the questions such as “who,” “what,” “when,” and “where,” which are especially used in the extraction of ACP sentences from all the sentences, for example: Doctor Jam can only read the healthcare records of patient A.Then, the semantic roles for predicates defined in the Probank project can be inserted into the sentence, which can be represented as follows:[Arg0 Doctor Jam] [ArgM-MOD can only] [V read] [Arg1 the healthcare records of patient A], where V, ArgM-MOD, Arg0, and Arg1 denotes the verb, modal, assigning subject and assigned object, respectively.The SRL is very important for making sense of the meaning of a sentence, of which the abstraction level is higher than other representation methods such as the syntax tree. Consider the following two sentences:“One person cannot possess the accountant and cashier roles at the same time.”“The accountant and cashier roles cannot be possessed by one person at the same time.”Although the latter sentence is different from the former in the syntactic form, they have the same semantic roles.Generally, for the given sentence, the task of SRL includes analyzing the meanings of the sentence expressed by the target verb, while extracting the constituents of the sentence that are filled by the semantic roles of the verb argument. Here, we use the following notations to represent the policy ACP:arg0;predicate;arg1, where arg0 usually represents the subject for predicate and arg1 represents the object that predicate affects.In this work, we use the semantic role labeler, named as Semantic/syntax Extraction using a Neural Network Architecture (SENNA) [47], to analyze the levels of sentences. The SENNA is a multilayer architecture of neural network that can handle amounts of natural language documents such as POS, sentence segmentation, NER, and SRL with satisfactory effects. It depends on large-scale datasets that are unlabeled and allows a training algorithm to find useful representation information with respect to the access requests. Particularly, the SENNA has three main features: fast speed, independency, and accuracy.


## 4.1.4. Post-Processing

Additional processing is needed after the generation of annotation results using the abovementioned SRL tools. This is because the system analysts usually use the natural language and their specific grammars to state requirements specification, and they do not possess the technical knowledges of the system. As a result, extraction of ACP sentences from their documents becomes very complicated. To improve the accuracy of the extracted ACPs, the named-entity recognition (NER) and argument extension are applied into the SRL results.The task of NER is to identify the name entities and word sequences such as person names, organization names, time, and location, in order to generate the annotated sentences that highlight the entity names as shown in the following example:[Organization name Hospital Management System], [Person name Nurse-in-Charge] and [Person name Patient] can only read patients’ general healthcare informationHere,Hospital Management System is an organization name consisting of three tokens, Nurse-in-Charge is a person consisting of three tokens, and Patient is also person consisting of one token.In fact, most of the extracted ACP sentences are also complicated, because they are sated by the system analysts using natural language and their own grammar structures. One of these complicated cases is that sometimes more than one access control policy is buried in a sentence. For example, consider the following the extracted roles for the predicate retrieve using SRL as follows:[Arg0 Educational Management System, Teaching Secretary and Class Teacher] [ArgM-MOD can] [V retrieve] and update [Arg1 students’ information] in the registration systemMoreover, as seen from the comparison between the semantic arguments using SRL and the actual ACPs, the SRL output is formally represented with the annotations of SRL, and it can be interpreted as an abstract form for the ACP sentence. Therefore, the SRL result should be extended to produce all the related ACPs. This extension could list all the named entities in Arg0 and Arg1 as subjects, and objects, respectively. After extraction of all the entities, the combinations of these entities with each predicate can be referred to as ACPs. Consider the above example again; there are six different ACPs involved in the sentence using the arguments extension:{Educational Management System; retrieve; students’ information}{Educational Management System; update; students’ information}{Teaching Secretary; retrieve; students’ information}{Teaching Secretary; update; students’ information}{Class Teacher; retrieve; students’ information}{Class Teacher; update; students’ information}


## 4.1.5. Development of an Initial Access Control System

When all the ACP sentences in the documents are extracted, the extracted information can be utilized to define roles by a role extractor, and these roles can be used to build an initial RBAC system. As seen from the form of the ACPs, many subjects correspond to the job functions in organizations, such as doctors, nurses, and patients in a hospital, which can represent different roles. Thus, we only need to take into consideration the ACPs, find the ones with the same subject, group them together into one role, and implement role-permission assignments. Since the operation and object elements involved in the ACPs can be used to construct permissions in RBAC, these permissions can be assigned to different roles according to the specific subjects from the extracted ACPs.


## 4.2. Bottom-up Constrained Role-Engineering Optimization

To flexibly suit diverse requirements of organizations, based on the basic RMP,δ-approx RMP, edge-RMP, and min-noise RMP, as well as the cardinality constraints URCC and PRCC, we utilize the ILP technique to uniformly model the constrained role-engineering problems in the initial constructed system. First, we present the definitions for these optimization problems using the BMD method.


### 4.2.1. Problem Definitions

Definition 1.
Basic role-engineering optimization problem, basicREOPURCC&PRCC
Given a matrixUPAn×m of user-permission assignments, the initial Boolean decomposed matrices for the UPAn×m, and two particular constraint thresholds MRCuser and MRCperm, find two matrices URAn×k and RPAk×m such that, (1) the number k of the optimal roles, which is regarded as the optimization objective, should be minimum; (2) the UPAn×m is precisely Boolean decomposed as the URAn×k and RPAk×m to ensure the integrity of the matrix reconstruction; the number of roles assigned to any user is less than or equal to MRCuser; and/or the number of roles to which any permission can be assigned is less than or equal to MRCperm, which are together regarded as the constraint conditions. This process can be formalized as follows:
(8)minkURAn×k⊗RPAk×m=UPAn×m∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,mDefinition 2.
δ-approx role-engineering optimization problem, δ-approx REOPURCC&PRCC
Compared to Definition1, the integrity constraint becomes that the UPAn×m can be approximately reconstructed by the URAn×k and RPAk×m with a reconstruction error δ. This process can be formalized as follows:
(9)minkURAn×k⊗RPAk×m‐UPAn×m1≤δ∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,mDefinition 3.
Edge-role-engineering optimization problem,edge−REOPURCC&PRCC
Compared to Definition1, the optimization objective becomes that the summing of the number of the user-role assignments and that of the role-permission assignments should be minimum. This process can be formalized as follows:
(10)minURAn×k+RPAk×mURAn×k⊗RPAk×m=UPAn×m∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,m.Definition 4.
Min-noise role-engineering optimization problem, min-noiseREOPURCC&PRCC
Compared to the above definitions, the optimization objective becomes that the reconstruction error should be minimum when the numberkof the mining roles is no more than k’. This process can be formalized as follows:
(11)minURAn×k⊗RPAk×m‐UPAn×m1k≤k′∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,m.


### 4.2.2. Complexity Analysis

Now, we analyze the computational complexity of the above four optimization problems. Notice that, first, the basic RMP can be viewed as a special case of the basicREOPURCC&PRCC when both the constraint thresholds take values of the number of mining roles. Since the decision version of the basic RMP has been proven to be NP-complete [16], so is the basic REOPURCC&PRCC. Similarly, the basic REOPURCC&PRCC can be viewed as a special case of the δ-approx REOPURCC&PRCC when the reconstruction error takes a value of 0, and the δ-approx REOPURCC&PRCC is also NP-complete. The differences of the other two REOP variants are either the optimization objective or constraint condition, and then the following statement can be concluded.Statement 1. ThebasicREOPURCC&PRCC, δ-approx REOPURCC&PRCC, edge-REOPURCC&PRCC, and min-noise REOPURCC&PRCC are all NP-hard


### 4.2.3. Unified Modelling Framework for REOP Variants Using 0-1 Programming

The differences among all the REOP variants lie in the constraint conditions and optimization objectives. The basicREOPURCC&PRCC is the most basic and important variant, and the others can be easily extended once the basic REOPURCC&PRCC is modelled. Here, for the convenience of discussion, Boolean matrices Xn×m, Cn×k, and Rk×m are used to represent matrices UPAn×m, URAn×k, and RPAk×m, respectively, and the variants xit, cij, and rjt are used to denote the cells of matrices Xn×m, Cn×k, and Rk×m, respectively. According to Definitions 1–4, the unified modelling framework for all the REOP variants via 0-1 programming are presented as follows.Step 1.
Suppose there areq candidate roles, r1,r2,⋯,rq, and the set of all these roles can be represented as the matrix R. Next, define a new set d1,d2,⋯,dq of identifier variables, in which role rj is present when dj=1; otherwise, rj is absent. Thus, the number of roles can be denoted as k=∑j=1qdj. Furthermore, several observations can be concluded as follows:
(1)
To ensure the integrity of the optimization process, if one user has a permission, which is represented asxit=1, then at least one role containing permission t should be assigned to user i, which can be denoted as ∑j=1qcij⋅rjt≥1,∀xit=1; otherwise, any role containing permission t should not be assigned to user i, which can be denoted as ∑j=1qcij⋅rjt=0,∀xit=0(2)
At least one user has a rolerj when dj=1, that is, at least one variable in c1j,c2j,⋯,cnj has a value of 1, which can be denoted as ∀i:dj≥cij. Similarly, at least one variable in rj1,rj2,⋯,rjm has a value of 1, which can be denoted as ∀t:dj≥rjt(3)
The cardinality constraints URCC and PRCC should be taken into consideration, which can be denoted as∑j=1qcij≤MRCuser and ∑j=1qrjt≤MRCperm, respectively
Based on these analyses, we model the basicREOPURCC&PRCC in Equation (12) as follows, where min∑j=1qdj represents the optimization objective, and the other parts of the equation represent the constraint conditions:
(12)min∑j=1qdjst.∑j=1qcij⋅rjt≥1,∀xit=1∑j=1qcij⋅rjt=0,∀xit=0∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjt,dj∈0,1,cij∈0,1,rjt∈0,11≤j≤q,1≤i≤n,1≤t≤m.Step 2.
Compared with the basicREOPURCC&PRCC, the optimization objective of the δ-approx REOPURCC&PRCC remains unchanged, while the constraint conditions vary and tolerate a reconstruction error. Thus, we only need to update the constraints and follow the same target function as shown in Step 1. For this purpose, a slack variable x′it is employed to make sure that the reconstruction matrix is acceptable, and the reconstruction error does not exceed a particular value. We model the δ-approx REOPURCC&PRCC in Equation (13) as follows, where min∑j=1qdj represents the optimization objective and the other parts of the equation represent the updated constraint conditions:
(13)min∑j=1qdjst.∑j=1qcij⋅rjt+x′it≥1,∀xit=1∑j=1qcij⋅rjt−x′it=0,∀xit=0∑i=1n∑t=1mx′it≤δ∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjt,dj∈0,1,cij∈0,1,rjt∈0,1,x′it∈0,11≤j≤q,1≤i≤n,1≤t≤mStep 3.
Compared with the basicREOPURCC&PRCC, the constraint conditions of the edge-REOPURCC&PRCC remain unchanged, while the optimization objective varies. Thus, we only need to update the target function and follow the same constraints as shown in Step 1. To reduce the space cost of the modelling, the users with the same permission set are clustered for a given set R of candidate roles. Assume that there are n’ different permission sets, the number of users corresponding to these sets are u1,u2,⋯,andun’, and then we model the edge-REOPURCC&PRCC in Equation (14) as follows, where min∑i=1n′ui⋅∑j=1qcij+∑j=1qdj⋅∑t=1mrjt represents the updated optimization objective and the other parts of the equation represent the constraint conditions:
(14)min∑i=1n′ui⋅∑j=1qcij+∑j=1qdj⋅∑t=1mrjtst.∑j=1qcij⋅rjt≥1,∀xit=1∑j=1qcij⋅rjt=0,∀xit=0∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjt,dj∈0,1,cij∈0,1,rjt∈0,11≤j≤q,1≤i≤n′,1≤t≤m.Step 4.
Compared with theδ-approx REOPURCC&PRCC, both the optimization objective and constraint conditions vary for the min-noise REOPURCC&PRCC. To address these issues, we need to make some improvements: Remove the expressions with the slack variables from the constraint conditions, construct a new objective function using these slack variables, and add a new expression of the upper limit number of roles into the constraint conditions. We model the min-noise REOPURCC&PRCC in Equation (15) as follows, where min∑i=1n∑t=1mx′it represents the optimization objective and the other parts of the equation are the constraint conditions:
(15)min∑i=1n∑t=1mx′itst.∑j=1qdj≤k′∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjtdj∈0,1,cij∈0,1,rjt∈0,1,x′it∈0,11≤j≤q,1≤i≤n,1≤t≤m.


## 4.2.1. Problem Definitions

Definition 1.
Basic role-engineering optimization problem, basicREOPURCC&PRCC
Given a matrixUPAn×m of user-permission assignments, the initial Boolean decomposed matrices for the UPAn×m, and two particular constraint thresholds MRCuser and MRCperm, find two matrices URAn×k and RPAk×m such that, (1) the number k of the optimal roles, which is regarded as the optimization objective, should be minimum; (2) the UPAn×m is precisely Boolean decomposed as the URAn×k and RPAk×m to ensure the integrity of the matrix reconstruction; the number of roles assigned to any user is less than or equal to MRCuser; and/or the number of roles to which any permission can be assigned is less than or equal to MRCperm, which are together regarded as the constraint conditions. This process can be formalized as follows:
(8)minkURAn×k⊗RPAk×m=UPAn×m∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,mDefinition 2.
δ-approx role-engineering optimization problem, δ-approx REOPURCC&PRCC
Compared to Definition1, the integrity constraint becomes that the UPAn×m can be approximately reconstructed by the URAn×k and RPAk×m with a reconstruction error δ. This process can be formalized as follows:
(9)minkURAn×k⊗RPAk×m‐UPAn×m1≤δ∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,mDefinition 3.
Edge-role-engineering optimization problem,edge−REOPURCC&PRCC
Compared to Definition1, the optimization objective becomes that the summing of the number of the user-role assignments and that of the role-permission assignments should be minimum. This process can be formalized as follows:
(10)minURAn×k+RPAk×mURAn×k⊗RPAk×m=UPAn×m∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,m.Definition 4.
Min-noise role-engineering optimization problem, min-noiseREOPURCC&PRCC
Compared to the above definitions, the optimization objective becomes that the reconstruction error should be minimum when the numberkof the mining roles is no more than k’. This process can be formalized as follows:
(11)minURAn×k⊗RPAk×m‐UPAn×m1k≤k′∑jURAij≤MRCuser≤k,∀i∈1,n∑jRPAjt≤MRCperm≤k,∀t∈1,m.


## 4.2.2. Complexity Analysis

Now, we analyze the computational complexity of the above four optimization problems. Notice that, first, the basic RMP can be viewed as a special case of the basicREOPURCC&PRCC when both the constraint thresholds take values of the number of mining roles. Since the decision version of the basic RMP has been proven to be NP-complete [16], so is the basic REOPURCC&PRCC. Similarly, the basic REOPURCC&PRCC can be viewed as a special case of the δ-approx REOPURCC&PRCC when the reconstruction error takes a value of 0, and the δ-approx REOPURCC&PRCC is also NP-complete. The differences of the other two REOP variants are either the optimization objective or constraint condition, and then the following statement can be concluded.Statement 1. ThebasicREOPURCC&PRCC, δ-approx REOPURCC&PRCC, edge-REOPURCC&PRCC, and min-noise REOPURCC&PRCC are all NP-hard


## 4.2.3. Unified Modelling Framework for REOP Variants Using 0-1 Programming

The differences among all the REOP variants lie in the constraint conditions and optimization objectives. The basicREOPURCC&PRCC is the most basic and important variant, and the others can be easily extended once the basic REOPURCC&PRCC is modelled. Here, for the convenience of discussion, Boolean matrices Xn×m, Cn×k, and Rk×m are used to represent matrices UPAn×m, URAn×k, and RPAk×m, respectively, and the variants xit, cij, and rjt are used to denote the cells of matrices Xn×m, Cn×k, and Rk×m, respectively. According to Definitions 1–4, the unified modelling framework for all the REOP variants via 0-1 programming are presented as follows.Step 1.
Suppose there areq candidate roles, r1,r2,⋯,rq, and the set of all these roles can be represented as the matrix R. Next, define a new set d1,d2,⋯,dq of identifier variables, in which role rj is present when dj=1; otherwise, rj is absent. Thus, the number of roles can be denoted as k=∑j=1qdj. Furthermore, several observations can be concluded as follows:
(1)
To ensure the integrity of the optimization process, if one user has a permission, which is represented asxit=1, then at least one role containing permission t should be assigned to user i, which can be denoted as ∑j=1qcij⋅rjt≥1,∀xit=1; otherwise, any role containing permission t should not be assigned to user i, which can be denoted as ∑j=1qcij⋅rjt=0,∀xit=0(2)
At least one user has a rolerj when dj=1, that is, at least one variable in c1j,c2j,⋯,cnj has a value of 1, which can be denoted as ∀i:dj≥cij. Similarly, at least one variable in rj1,rj2,⋯,rjm has a value of 1, which can be denoted as ∀t:dj≥rjt(3)
The cardinality constraints URCC and PRCC should be taken into consideration, which can be denoted as∑j=1qcij≤MRCuser and ∑j=1qrjt≤MRCperm, respectively
Based on these analyses, we model the basicREOPURCC&PRCC in Equation (12) as follows, where min∑j=1qdj represents the optimization objective, and the other parts of the equation represent the constraint conditions:
(12)min∑j=1qdjst.∑j=1qcij⋅rjt≥1,∀xit=1∑j=1qcij⋅rjt=0,∀xit=0∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjt,dj∈0,1,cij∈0,1,rjt∈0,11≤j≤q,1≤i≤n,1≤t≤m.Step 2.
Compared with the basicREOPURCC&PRCC, the optimization objective of the δ-approx REOPURCC&PRCC remains unchanged, while the constraint conditions vary and tolerate a reconstruction error. Thus, we only need to update the constraints and follow the same target function as shown in Step 1. For this purpose, a slack variable x′it is employed to make sure that the reconstruction matrix is acceptable, and the reconstruction error does not exceed a particular value. We model the δ-approx REOPURCC&PRCC in Equation (13) as follows, where min∑j=1qdj represents the optimization objective and the other parts of the equation represent the updated constraint conditions:
(13)min∑j=1qdjst.∑j=1qcij⋅rjt+x′it≥1,∀xit=1∑j=1qcij⋅rjt−x′it=0,∀xit=0∑i=1n∑t=1mx′it≤δ∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjt,dj∈0,1,cij∈0,1,rjt∈0,1,x′it∈0,11≤j≤q,1≤i≤n,1≤t≤mStep 3.
Compared with the basicREOPURCC&PRCC, the constraint conditions of the edge-REOPURCC&PRCC remain unchanged, while the optimization objective varies. Thus, we only need to update the target function and follow the same constraints as shown in Step 1. To reduce the space cost of the modelling, the users with the same permission set are clustered for a given set R of candidate roles. Assume that there are n’ different permission sets, the number of users corresponding to these sets are u1,u2,⋯,andun’, and then we model the edge-REOPURCC&PRCC in Equation (14) as follows, where min∑i=1n′ui⋅∑j=1qcij+∑j=1qdj⋅∑t=1mrjt represents the updated optimization objective and the other parts of the equation represent the constraint conditions:
(14)min∑i=1n′ui⋅∑j=1qcij+∑j=1qdj⋅∑t=1mrjtst.∑j=1qcij⋅rjt≥1,∀xit=1∑j=1qcij⋅rjt=0,∀xit=0∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjt,dj∈0,1,cij∈0,1,rjt∈0,11≤j≤q,1≤i≤n′,1≤t≤m.Step 4.
Compared with theδ-approx REOPURCC&PRCC, both the optimization objective and constraint conditions vary for the min-noise REOPURCC&PRCC. To address these issues, we need to make some improvements: Remove the expressions with the slack variables from the constraint conditions, construct a new objective function using these slack variables, and add a new expression of the upper limit number of roles into the constraint conditions. We model the min-noise REOPURCC&PRCC in Equation (15) as follows, where min∑i=1n∑t=1mx′it represents the optimization objective and the other parts of the equation are the constraint conditions:
(15)min∑i=1n∑t=1mx′itst.∑j=1qdj≤k′∑j=1qcij≤MRCuser∑j=1qrjt≤MRCpermdj≥cij,dj≥rjtdj∈0,1,cij∈0,1,rjt∈0,1,x′it∈0,11≤j≤q,1≤i≤n,1≤t≤m.


## 5. Heuristic Algorithms

After constructing the access control system using the extracted ACPs, some pre-proceedings are taken into consideration, in order to construct an initial RBAC system. The Fast Miner and BMD methods are used to mine various types of role sets according to the representative RMP variants with no constraints, as shown in Algorithm1.Algorithm 1: Initial role mining with no constraints.
Input: the original matrix Xn×mOutput: the initial role set Init_Roles, and decomposed matrices Cn×k and Rk×mThe Fast Miner and BMD methods are adopted to deriveInit_Roles and configure an initial RBAC system, in order to satisfy different RMP variants, such as the basic RMP, δ-approx RMP, edge-RMP, and min-noise RMP;To satisfy the security requirements while enhancing the interpretability of the mining results, the URCC and PRCC should be taken into consideration in the constructed RBAC system. Specifically, the unconstrained mining results are checked to identify whether they violate the given cardinality constraints. If there are no violations, they are regarded as the effective solutions.According to Definitions1–4 and their unified modelling framework, we take the initial mining results and constraint threshold as inputs and present the process of the role optimization with URCC in Algorithm 2.Algorithm 2: Role-engineering optimization with URCC.
Input: the original matrix Xn×m, constraint threshold MRCuser, and candidate role set Init_RolesOutput: the constrained role set Cons_Roles, and updated matrices Cn×k and Rk×m1. Create and initialize setCons_Roles=Φ;2. Create and initialize functioncount_unvisitedperms(xi)=|user_perms(xi)|, which represents the number of the unvisited permissions assigned to user xi currently;3. Sort the roles ofInit_Roles in descending order according to the number of their associated users, and then construct a role-priority list, denoted as RPL1;4.for each row user xi in matrix Xdo5.whileuserrolesxi<MRCuser−1∧(count_unvisitedperms(xi)<>0) do6.  Choose rolerj from RPL1 based on a heuristic strategy, such that role_perms(rj)⊂user_perms(xi);7.if∃r1,r2,⋯⊆Cons_Roles:role_permsrj⊆∪r∈r1,r2,⋯role_permsrthen8.cij=0;9.else10.Cons_Roles=Cons_Roles∪{rj};11.cij=1;12.end if13.end while14.ifcount_unvisitedperms(xi)==0 then15.  ∀rj∈{RPL1\Cons_Roles}: cij=0;16.else17. if∃rj′∈RPL1\Cons_Roles:role_permsrj′=user_permsxi\∪r∈Cons_Rolesrole_permsrthen18.cij’=1;19.else20.  Create a new rolernr, such that21.role_permsrnr=user_permsxi\∪r∈Cons_Rolesrole_permsr;22.Cons_Roles=Cons_Roles∪{rnr};23.ci,nr=1;24.for each column permission xt in matrix Xdo25.ifperm_roles(xt)⊇rnrthen26.rnr,t=1;27.else28.rnr,t=0;29.end if30.end for31.end if32.end if33.end forIn Algorithm2, we first define the variant Cons_Roles and function count_unvisitedpermsxi in lines 1–2. Line 3 sorts the initial roles in some certain form and then constructs a role-priority list RPL1. For each row user, line 5 determines whether the permissions assigned to user xi is completely covered or whether the constraint URCC is satisfied. If both the two conditions are satisfied, then an optimal role rj is chosen using a heuristic strategy in line 6. Lines 7–12 indicate that if the set of permissions assigned to role rj is a subset of some mined role’ permissions (that is, rj is a redundant role), then the cell cij is set as 0; otherwise, the optimal role set is updated, and cij is set as 1. If all the permissions have been covered, and the constraint is still satisfied, then cij is set as 0 (lines 14–15); otherwise, when user xi has been assigned (MRCuser -1) number of roles, there are remaining permissions that are not covered. If another role rj’ can be found in the existing role set, then cij’ is set as 1; otherwise, a new role rnr is created, ci,nr is set as 1, and the matrix Rk×m is updated based on the new role in lines 17–31. This optimization process is repeated until there are not any users who satisfy the constraint conditions.Next, we take the initial mining results and another constraint threshold as inputs and present the process of the role optimization with PRCC in Algorithm3.Algorithm 3: Role-engineering optimization with PRCC.
Input: the original matrix Xn×m, constraint threshold MRCperm, and candidate role set Init_RolesOutput: the constrained role set Cons_Roles, and updated matrices Cn×k and Rk×m1. Create and initialize setCons_Roles=Φ;2. Create and initialize functioncount_uncoveredusers(xt)=|perm_users(xt)|, which represents the number of the uncovered users associated with permission xt currently;3. Sort the roles ofInit_Roles in descending order according to the number of their associated permissions, and then construct a role-priority list, denoted as RPL2;4.for each column permission xt in matrix Xdo5.while (|perm_roles(xt)|<MRCperm -1)∧(count_uncoveredusers(xt)<>0) do6.  Choose rolerj from RPL2 based on a heuristic strategy, such that role_users(rj)⊂perm_users(xt);7.if∃r1,r2,⋯⊆Cons_Roles:role_usersrj⊆∪r∈r1,r2,⋯role_usersrthen8.rjt=0;9.else10.Cons_Roles=Cons_Roles∪{rj};11.rjt=1;12.end if13.end while14.ifcount_uncoveredusers(xt)==0 then15.  ∀rj∈{RPL2\Cons_Roles}: rjt=0;16.else17.if∃rj′∈RPL2\Cons_Roles:role_usersrj′=perm_usersxt\∪r∈Cons_Rolesrole_usersrthen18.rj’t=1;19.else20.  Create a new rolernr, such that21.role_usersrnr=perm_usersxt\∪r∈Cons_Rolesperm_usersr;22.Cons_Roles=Cons_Roles∪{rnr};23.rnr,t=1;24.for each row user xi in matrix Xdo25.ifuser_roles(xi)⊇rnrthen26.ci,nr=1;27.else28.ci,nr=0;29.end if30.end for31.end if32.end if33.end forIn Algorithm3, we first define variant Cons_Roles and function count_uncoveredusersxt in lines 1–2. Line 3 sorts the initial roles in some certain form, and also constructs a role-priority list RPL2. For each column permission, line 5 determines whether the users associated to permission xi is completely covered or whether the constraint PRCC is satisfied. If both the two conditions are satisfied, then an optimal role rj is chosen using a heuristic strategy in line 6. Lines 7–12 indicate that if the set of users associated to role rj is a subset of some mined role’ users (that is, rj is a redundant role), then the cell rjt is set as 0; otherwise, the optimal role set is updated, and rjt is set as 1. If all the users have been covered, and the constraint is still satisfied; then rjt is set as 0 (lines 14–15); otherwise, when permission xt has been assigned to (MRCperm−1) number of users, there are remaining users that are not covered. If another role rj’ can be found in the existing role set, then rj’t is set as 1; otherwise, a new role rnr is created, rnr,t is set as 1, and the matrix Cn×k is updated based on the new role in lines 17–31. The optimization process is repeated until there are not any users who satisfy the constraint conditions.Computational complexity: The core of the above two algorithms is to update the candidate role set constantly, and take Algorithm2 for example. At each iteration of the algorithm, a role is selected from the candidate role set. Thus, the total computational time depends on the number of iterations, the method of generation of candidate roles, and the role selection method. The numbers of users, permissions, and candidate roles are n, m, and k, respectively. At least one user permissions are fully covered at each iteration. Thus, it requires n loops. Further, each role of k candidate roles is required to take a comparison with any one of the remaining users, and any user is assigned at most m permissions. Thus, the computational time is nmk for each iteration, and the total time complexity is n2mk.A single constraint, URCC or PRCC, is taken into account in Algorithm2 or Algorithm 3. However, satisfying one constraint may breach the other constraint. It is necessary to study how to implement both the URCC and PRCC in the optimization process. For this purpose, a role set RU, which would not cause any new violations to RPA, needs to be identified. Another role set RI, which would not cause any new violations to URA, also needs to be identified. Specifically, for each role r in RU, any permission assigned to r does not violate the constraint PRCC; similarly, for each role r in RI, any user possessing r would not violate the URCC. The optimization process with the double cardinality constraints is presented in Algorithm 4.Algorithm 4: Role-engineering optimization with URCC and PRCC.
Input: the preprocessed matrices Cn×k and Rk×m, candidate role set Init_Roles, and thresholds MRCuser and MRCpermOutput: the optimized role set Cons_Roles, and updated matrices Cn×k and Rk ×m1. Create and identify functionscount_user_roles(u), count_role_users(r), count_perm_roles(p),andcount_role_perms(r), respectively;2. IdentifyRU, RI, such that∀r∈RU, ∀p∈ role_perms(r): count_perm_roles(p)≤MRCperm -1;∀r∈RI, ∀u∈role_users(r): count_user_roles(u)≤MRCuser -1;3.while ((∃u∈U: count_user_roles(u)>MRCuser) or (∃p∈P: count_perm_roles(p)>MRCperm)) do4. Choose violating users or violating permissions based on a heuristic strategy;5.if user u is chosen then6.l= count_user_roles(u) - (MRCuser -1);7. Choose the firstl roles of u from RU with the greatest values of count_role_users(r) to constitute set S;8. Merge the permissions of all thel roles and denote the union as set PS;9. Create a new rolernr such that role_perms(rnr)= PS;10. Update theRPA and URA with rnr via Algorithm 2;11.else12.l= count_perm_roles(p) - (MRCperm -1);13. Choose the firstl roles of p from RI with the greatest values of count_role_perms(r) to constitute set S;14. Intersect the permissions of all thel roles and denote the intersection as set PS;15. Create a new rolernr such that role_perms(rnr)= PS;16. Update theURA and RPA with rnr via Algorithm 3;17.end if18.end whileIn Algorithm4, we first identify RU and RI and determine the violating users or permissions using a heuristic strategy in lines 2–4. Then, if user u is chosen, the first l roles are chosen from RU; if permission p is chosen, the first l roles are chosen from RI. Similar to updating the URA and RPA using Algorithm 2 and Algorithm 3, the detailed specifications of the algorithm are omitted owing to the limited space.


## 6. Experimental Evaluations

To evaluate the effectiveness and efficiency of the HREOMCC_NLP&ILP, we conduct experiments and compare its performances with the state of the art techniques in this section.


### 6.1. Performance Comparison with the ACRE Method for the ACPs Extraction

First, we implement experiments to study how effectively the elements of ACPs are extracted, including subjects, objects, and operations. We choose different natural language documents from multiple research domains [48], such as electronic healthcare, education, and conference management, as the research objects. For the healthcare domain, we use the open source document, called iTrust, which records the patients’ medical histories, primary caregivers, and communication results with doctors. For the education domain, we employ the resources from the IBM Course Registration System. For the conference management domain, we use the documents from the CyberChair that has been applied in different scenarios, such as conferences and workshops. We only consider the sentences that have been identified as ACPs from the documents, and the non-ACPs are not the focus of this work. The abovementioned datasets are presented in Table 1.Table 1
Descriptions of datasets.
DatasetNumber of identified ACP sentencesiTrust418IBM course registration system169CyberChair139Collected115To evaluate the effectiveness of our method for the ACPs extraction, three evaluation measuresPrecision, Recall, and F1 score are taken into consideration: Precision is the proportion of the correctly extracted ACP elements against all the extracted elements; Recall is the proportion of the correctly extracted ACP elements against all the elements in the current test dataset; F1 score indicates a coordination factor and is a weighted average between Precision and Recall. To calculate these values, we first divide the extracted values into four categories: false positive (FP), false negative (FN), true positive (TP), and true negative (TN), where FP represents the case when a word is mistakenly identified as an ACP element while it is actually not, FN represents the case when an actual ACP element cannot be correctly extracted, TP represents the correct extraction, and TN represents the case when a non-ACP element can be correctly identified. Based on these values, the Precision, Recall and F1 score are, respectively, calculated as follows:
(1)
Precision=TP/TP+FP,(2)
Recall=TP/TP+FN,(3)
F1=2×Precision×Recall/Precision+Recall,Further, the ACRE method extracts 1070 ACPs, 375 ACPs, 386 ACPs, and 258 ACPs using the iTrust, IBM Course Registration System, CyberChair, and Collected dataset, respectively. According to the algorithm in the ACRE, sentence structures throughout the documents are required to be repetitive, and more details of ACPs extraction using SRL can be found in [25]. Based on the above evaluation criteria, the results of our method as well as the performances of the ACRE method are presented in Table 2. As shown in the table, the ACRE performs well on the iTrust and IBM Course Registration System datasets, while it performs poor on the Collect dataset. The documents in the former two sets include lots of repetitive sentence structures, but there are not enough repetitions in the latter set. However, our method performs well and outperforms the ACRE method in most cases from the viewpoint of recall. This is because the SRL does not require repetitions for sentence structures. Each sentence is considered separately and is independent of other sentences. The SRL is able to find most of the ACP elements if a role set defined for the predicate exists. It provides very stable and good extraction results that are irrelevant to the sentence structures.Table 2
Comparison of the ACPs extraction.
DatasetACREOur methodPrecision (%)Recall (%)F1 (%)Precision (%)Recall (%)F1 (%)iTrust80%75%77%74%86%80%IBM course registration system81%62%70%56%86%69%CyberChair75%30%43%47%83%60%Collected68%18%29%78%87%82%However, our method does not outperform the ACRE method from the viewpoint of precision. This is because our method extracts all the verbs and considers them as the arguments using the SRL, while only a small part of these verbs describes ACPs. Other verbs arguments such as “to be” and modals do not specify ACPs in nature, which increase the ratio of FP in the ACPs extraction and then reduce the precision. Our method is unable to correctly identify all the arguments with the predicates owing to the complex structure of some sentences, which also reduces the precision.From the viewpoint ofF1 score, our method performs well with the F1 score of 82%, and it outperforms the ACRE with the F1 score of 29% for the Collected dataset. Only for the IBM Course Registration System, the ACRE performs better, as it has a higher precision that leads to the higher F1 score. Another benefit of our method is that it does not require any dataset to be labeled, while ACRE method requires a labeled dataset that is similar to the documents to be analyzed in structure and content. One issue with our method, however, is that sometimes it is unable to identify the predicate arguments using the SRL tools, as they are usually trained on publicly available documents and are not well adapted to the documents like access control requirements.


### 6.2. Performance Evaluations on Synthetic Datasets under a Single Cardinality Constraint

To further study the robustness of the constructed access-control system from the given NLACP documents, we randomly construct synthetic matricesUPA, URA, and RPA via Algorithm 1 with 80 number of users, 250 number of permissions, and 20 number of initial roles, such that matrix UPA is Boolean decomposed to be matrices URA and RPA according to different optimized variants. The basic REOPURCC&PRCC, edge-REOPURCC&PRCC, and δ-approx REOPURCC&PRCC are taken as the research objects.We carry out Algorithm2 in order to study how the constraint URCC and other factors affect the optimized results of our method in the optimization phase, when the value of the cardinality constraint varies from 2 to 8 with a step of 1. We take into account the number of the constrained roles, and the size of the optimized assignment relationships URA and RPA, as evaluation measures. The experimental results are shown in Figures 2–4. In Figure 2, the lateral axis represents the constraint threshold MRCuser, and the vertical axis represents the number of roles. In Figure 3, the lateral axis represents MRCuser, and the vertical axis represents the size of the assignments relationships URA and RPA. In Figure 4, the lateral axis represents the approximation rate, simply denoted as δ, which is calculated by URA⊗RPA/UPA, and the vertical axis represents the number of roles.Figure 2
Optimized results for the basicREOPURCC&PRCC.Figure 3
Optimized results for the edge-REOPURCC&PRCC.Figure 4
Optimized results for theδ-approx REOPURCC&PRCC.Figure2 demonstrates that the number of roles tends to decrease slightly as the value of MRCuser increases. When the value of MRCuser increases to a certain value, the number of roles tends to be stable and becomes unchanged. Specifically, the number of roles does not obviously vary and remains close to 15 when the value of MRCuser exceeds 6. However, the number of roles increases as MRCuser decreases. When the value of MRCuser equals 2, the number of roles becomes 23. Figure 3 demonstrates the effects of the constraint MRCuser on the size of the relationships URA and RPA, which is also regarded as the administrative cost of the system. Obviously, it tends to decrease as the value of MRCuser increases, which is similar to the variation tendency of Figure 2. This is because the greater the value of MRCuser is, the weaker the constraint will be. More general roles are assigned to any user. In other words, when MRCuser takes a greater value, general roles that do not include many permissions are more practical and can be utilized frequently. Thus, fewer irregular roles need to be generated, and the number of roles and size of assignments do not vary considerably. On the contrary, the less the value of MRCuser, the stricter the constraint is. When the constraint becomes strict and takes a small value, each user is allowed to associate with few roles. Thus, these roles need to possess more access permissions, in order to ensure that each user can still get enough access permissions. As a result, the number of roles and size of the assignment relationships increase remarkably. For the same dataset, in order to evaluate the effects of the approximation ratio on the mining roles, the value of MRCuser is fixed at 4, and the value of δ varies from 0.6 to 1. From Figure 4, it is observed that the number of roles increases as δ increases. This is because the greater value of the approximation rate, the better the integrity of the matrix reconstruction is. Thus, more roles are needed for covering the original permission assignments.Similarly, we carry out Algorithm3 in order to evaluate the effects of the constraint PRCC and other factors on the optimized results, with respect to the same evaluation measures. The experimental results are shown in Figures 5–7. Figure 5 shows that when MRCperm≥52, the number of roles first decreases slightly and then grows to be stable as the value of MRCperm increases. Specifically, when MRCperm equals 1, 231 roles are developed, and each role includes only one permission, which is not practical; when 2≤MRCperm<52, the number of roles decreases remarkably from 231 to 35 with the increasing value of MRCperm; when 52≤MRCperm<112, the number of roles decreases slightly from 35 to 18; when MRCperm≥112, it grows to be stable. Figure 6 demonstrates the effects of the constraint MRCperm on the size of assignments URA and RPA, which tends to decrease as the value of MRCperm increases and is similar to the variation tendency of Figure 5. This is because the less the value of MRCperm is, the stricter the constraints and the more roles and role-permission assignments that satisfy the constraint requirements will be. As a result, the value of URA+RPA increases accordingly as MRCperm decreases. For the same dataset, to evaluate the effects of the approximation ratio on the mining roles, the value of MRCperm is fixed at 80, and the value of δ varies from 0.6 to 1. From Figure 7, it is observed that the number of roles increases as δ increases. This is attributed to the fact that more roles are needed, in order to ensure the better integrity of the matrix reconstruction.Figure 5
Optimized results for the basicREOPURCC&PRCC.Figure 6
Optimized results for the edge-REOPURCC&PRCC.Figure 7
Optimized results for theδ-approx REOPURCC&PRCC.


### 6.3. Performance Evaluations on Real-World Datasets under Multiple Cardinality Constraints

To further evaluate the effectiveness and efficiency of our method, we comprehensively consider nine different real-world datasets that have been widely used for evaluating the performances of different methods of role-engineering optimization, such as Blundo method [38] and Harika method [40]. The conventional mining tool RMiner [49] can be adopted to derive different sets of candidate roles under unconstrained conditions on these datasets. The original datasets, including the density of the dataset, number of initial roles, and intervals of thresholds MRCuser and MRCperm, are shown in Table 3. The threshold intervals specify the lower and upper bounds, from which the constraints can take the values. All the experiments are implemented on a standard desktop PC with an Intel i5–7400 CPU, 4 GB RAM, and a 160 GB hard disk running a 128–bit Windows 10 operating system. All simulations are compiled and run under the Java environment.Table 3
Descriptions of original real-world datasets.
DatasetUPUPADensityInit_RolesInterval ofMRCuserInterval ofMRCpermAmerica-large3,48510,127185,2940.5%423[2, 4][2, 129]America-small3,4771,587105,2051.9%213[2, 12][2, 43]Apj2,0441,1646,8410.3%456[2, 8][2, 15]Customer10,96128445,4271.5%276[2, 25][2, 140]Domino792317304%20[2, 9][2, 6]Emea353,0467,2206.8%34[2, 3][2, 31]Firewall 136570931,95112.3%69[2, 9][2, 18]Firewall 232559036,42819%10[2, 3][2, 4]Healthcare4646148670%15[2, 6][2, 4]We take the similar research objects already used on the above synthetic datasets and consider the number of rolesR, administrative cost URA+RPA, and execution time as the evaluation measures. To study the effects of different combinations of parameters on the optimized results, we consider the approximate rare δ and a single constraint MRCuser as inputs and conduct Algorithm 2 using the Firewall 1, Firewall 2, Healthcare, America-small, Domino, and Apj datasets, respectively. Meanwhile, the value of δ varies from 0.80 to1.00 with a step of 0.05 for any dataset, and the threshold MRCuser takes a group of different values for a specific dataset. Specifically, the values of MRCuser takes 2, 4, and 8 for the Firewall 1; 2 and 3 for the Firewall 2, Healthcare and Domino; 2, 6, and 10 for the America-small; and 2, 3, and 4 for the Apj. We repeatedly implement the experiments with 75 different pair values of δ and MRCuser and compare the results with the performances of the Blundo method and Harika method, as shown in Tables 4–9, where the best results are highlighted in boldface and underlined. First of all, these tables show that, for the three methods, the values R, URA+RPA, and the execution time almost all increase as MRCuser decreases, whenever δ is fixed at a certain value. In addition, these evaluation values all decrease as δ decreases, whenever MRCuser is fixed, which is consistent with the performances and analyses on the synthetic datasets, as shown in Figures 2–4.Table 4
Performance comparisons on Firewall 1.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm248491524849152484915RURA+RPAExecution time (s)Blundo method1.00365906571686832,6815,8074,4263,2283,1943,1947288833837610.95280774255413723,9774,7193,7282,5742,4332,4316986813534570.90234533447332917,0583,8562,9412,1882,0662,0596784783330510.85189492735271814,6732,8551,7931,7991,6981,6716480743129470.80178411528191710,4171,9821,6011,3611,2471,247627669292639Harika method1.0090857112565657,1907,2074,6463,3023,2733,2734777754248380.956753438546415,8716,2253,8632,5632,4772,4614571694043370.905846327236333,7834,5873,0052,0842,0142,0014264623941370.854439266637352,5743,5912,3791,7741,6731,6453962593741360.803425194928231,9372,4131,3161,3571,3421,301325856353436Our method1.008885817168687,2016,8896,6313,0162,9882,8465768634345350.953748383438355,7385,6835,6692,7912,3122,3085665604140370.902825152320164,6684,3422,9672,0461,9191,9015463583939370.8518108161282,6601,7651,9981,6981,5671,5895260543837360.801296131071,9231,6891,8401,3021,2761,246495551353435Table 5
Performance comparisons on Firewall 2.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm232423242324RURA+RPAExecution time (s)Blundo method1.003253255901237,07837,07837,6091,5787748954650.953243245831236,85136,85136,9811,5037247951610.903213214741236,51736,51735,1321,4986944939600.853193193651236,12136,12131,2071,3216542901590.803073073611135,98135,98129,5781,302613987756Harika method1.001111323111,5101,54836,6081,3784846724430.951110281111,5071,50134,9811,3034745701350.9066273111,0331,03332,1321,1984542697340.8555264111,0331,03331,2071,1214341574210.8055260101,0311,02529,578902413754420Our method1.001111590121,6111,60737,6081,5786563954650.951110501121,6111,60436,9811,5036460951610.9066453121,2541,23135,1321,4986157939600.8566401111,1371,11731,2071,3215955901590.8065387101,0841,05929,5781,302555187756Table 6
Performance comparisons on healthcare.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm232423242324RURA+RPAExecution time (s)Blundo method1.00461846231,5785631,57839922430.95411646231,4924711,50333122430.90371545211,4214221,47129621430.85311344211,3273791,41123212330.80291342201,2033051,3641972133Harika method1.00181546235632631,57838922430.95181546235632631,43330122430.90171345215572541,32122622320.85161344215512521,25119221320.80151242205402391,1741662131Our method1.00201946234374181,57939221430.955625171932051,40330011430.905623162272111,33721121330.855621152132091,18118611320.805421151991341,0241751132Table 7
Performance comparisons on America-small.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm261022040261022040261022040RURA+RPAExecution time (s)Blundo method1.0025925925920720720725,48825,48825,48810,45010,45010,4501511501501531591600.9525425225220720720724,78924,74324,73110,33010,33010,3211511481451531591600.9023723423420520120123,98323,96023,94410,25810,25810,2471491471461471441430.8523122422419919519521,11421,10321,09810,11910,11910,1111481491441461431410.8022421721719719619420,61820,44520,11210,01710,01710,003145145144143142139Harika method1.0025824422520720720722,72318,53213,99711,65611,65611,6564291,5921,6127477297830.9522424322020720720721,63920,70920,08811,61511,61511,6094011,5821,5937257017590.9021717816520620120119,44519,20919,00711,60911,60911,6013781,5771,5887206917110.8516715513219219219018,88118,25718,10111,58911,58911,5773621,5241,5647116886790.8015915113119118718217,66516,34315,90611,57311,57311,5153601,5021,523703683673Our method1.0025925724920720720725,94423,64022,19511,65611,65611,6561,6501,5781,6131,6501,3771,3770.9522718618520720720723,17421,34920,10911,61511,61511,6091,5441,5181,6131,5441,2121,2120.9020916815320620120121,93920,8652173711,60911,60911,6011,5011,4771,5791,5011,1791,1790.8518514013219519419320,93717,83414,70911,58911,58911,5771,4561,4051,4031,4561,1021,1020.8017312711819318317718,73316,47014,28611,57311,57311,5151,3391,3651,3061,3391,0601,060Table 8
Performance comparisons on Domino.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm232423242324RURA+RPAExecution time (s)Blundo method1.0023231252073973996796721510.9522221241973173196396311510.9020201201772972995995911510.8518181181772772795195111510.801515107157247249439431141Harika method1.0027231232076276195395321510.9520181241873072994594521510.9018171201772472193193121510.8515131181570570192092011410.801411107126826799029021131Our method1.0022211252172572396796721510.9518161241969769496396311510.9015141201769168995995911510.8513121181768567995195111510.801010107156766639439431141Table 9
Performance comparisons on Apj.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm234271223427122342712RURA+RPAExecution time (s)Blundo method1.002,04448645449245745510,9296,1296,1295,1785,0455,034751,4311,5354346490.951,9973883444874324449,8906,0786,0785,0475,0474,943711,4291,4274145470.901,9653463214754214219,7345,9835,9834,9864,9864,879701,4251,4233944450.851,8232963154614094079,6785,7115,7114,7614,7614,642671,3811,3753741410.801,6502802934513643809,6555,5945,5944,5234,5234,469631,3721,366354039Harika method1.005644704574924574556,1295,3725,1605,3415,1215,1158839398877477800.954613753554874254215,4814,1894,1105,0195,0194,9177339398717287410.904023313304754194154,5344,0033,9124,9684,9684,8656537388647107300.853432893214613773744,3253,9473,8544,7124,7124,6315736368496787050.803082742734513563404,0863,6093,3914,4334,4334,459353333830653667Our method1.005674994874924574556,0195,9155,5315,4775,4775,1069249384445470.954603953814874234205,3764,4354,3405,0325,0324,9089139384045450.904093293244744214184,4924,2354,0414,9754,9614,8698935374045440.853412873134603883824,0173,8523,8524,7384,7084,6308534373843420.803142912694513523613,8153,5863,5864,4294,4224,460813237343940We compare the performances of the three methods using different datasets. As shown in Table4, compared to the other methods, our method returns a smaller set of roles in 14 tests out of 15, in terms of the values of R, while it returns a smaller size of assignment relationships only in 4 tests, in terms of the values of URA+RPA. Furthermore, it runs faster than the other two in 10 tests out of 15. Thus, according to the number of roles and execution time, our method outperforms the other two on the Firewall 1 dataset. As shown in Table 5, our method performs as well as the Harika method in terms of the values of R. However, the Harika method performs better and returns a smaller size of assignment relationships and runs faster in all the 10 tests. In summary, the Harika method outperforms our method on the Firewall 2 dataset. As shown in Table 6, compared to the other methods, our method returns a smaller set of roles in 8 tests out of 10, and it returns a smaller size of assignment relationships in 9 tests out of 10. Furthermore, it runs faster than the other two in all the 10 tests. Thus, our method outperforms the other two on the Healthcare dataset. As shown in Table 7, our method returns a smaller set of roles in 11 tests out of 15. However, in terms of the values of URA+RPA, the Harika method performs better and returns a smaller size of assignment relationships in all the 15 tests; in terms of execution time, the Blundo method performs better, which is from 3 to 10 times faster than Harika method, and is about 10 times faster than our method in all the 15 tests. In summary, our method does not perform as well as the Blundo method on the America-small dataset. As shown in Table 8, our method returns a smaller set of roles than the other two methods in all the 10 tests, and it also returns a smaller size of assignment relationships in all these tests. Further, in terms of execution time, our method also performs well. Thus, our method outperforms the other two on the Domino dataset. As shown in Table 9, our method returns a smaller set of roles in 7 tests out of 15, while the Harika method returns the best results in the other 8 tests. In terms of the values of URA+RPA, our method returns a smaller size of assignment relationships in 8 tests out of 15, while the Harika method returns the best results in the other 7 tests. In terms of execution time, our method returns runs faster in 7 tests out of 15, while the Harika method spends less time in the other 8 tests. Thus, our method performs almost as well as the Harika method on the Apj dataset.Second, we consider the approximate rareδ and another cardinality constraint MRCperm as inputs and conduct Algorithm 3 on the same datasets. The threshold MRCperm takes a group of different values for a specific dataset. Specifically, we set 4, 9, and 15 for the Firewall 1; we set 2 and 4 for the Firewall 2, Healthcare and Domino; we set 2, 20, and 40 for the America-small; we set 2, 7, and 12 for the Apj. We also conduct the experiments 75 times with different parameter pairs and compare the performances of different methods as shown in the remaining columns of Tables 4–9, where the best results are also highlighted in boldface and underlined. As shown in Table 4, our method returns a smaller set of roles in all the 15 tests, and it returns a smaller size of assignment relationships in 14 tests of 15. Furthermore, in terms of execution time, our method performs as well as the other two, though it runs faster only in 5 tests out of 15. In summary, our method outperforms the other two on the Firewall 1 dataset. As shown in Table 5, compared with our method and the Blundo method, however, the Harika method performs better and returns a smaller set of roles and a smaller size of assignment relationships, and it runs faster in all the 10 tests. Thus, the Harika method outperforms our method on the Firewall 2 dataset. As shown in Table 6, compared to the other methods, our method returns a smaller set of roles in all the 10 tests, and it returns a smaller size of assignment relationships in 6 tests out of 10. Furthermore, it runs as fast as the other two. Thus, our method outperforms the other two on the Healthcare dataset. As shown in Table 7, our method performs as well as the other two in terms of the number of roles. However, in terms of the values of URA+RPA, the Blundo method performs better and returns a smaller size of assignment relationships in all the 15 tests; in terms of execution time, the Blundo method also performs better, which is from 5 to 10 times faster than Harika method, and is from 7 to 10 times faster than our method in all the 15 tests. Thus, our method does not perform as well as the Blundo method on the America-small dataset. As shown in Table 8, in terms of the values of URA+RPA, the Harika Method returns a smaller size of assignment relationships in all the 10 tests, However, the three methods return the similar results in terms of the values of R and time overhead, respectively. Thus, according to the number of roles and execution time, our method performs as well as the other two methods on the Domino dataset. As shown in Table 9, our method returns a smaller set of roles in 6 tests out of 15, and the Harika method also returns the best results in 6 tests out of 15. Further, our method returns a smaller size of assignment relationships in 6 tests out of 15, and the Harika method also returns the best results in 6 tests out of 15. In terms of execution time, our method runs faster in 8 tests out of 15, while the Harika method spends less time only in 2 tests out of 15. Thus, our method outperforms the Harika method on the Apj dataset.Next, we study the effects of both the URCC and PRCC on the optimized results. According to Algorithm4, a heuristic strategy in line 4 is used to pick either a violating user or a violating permission, based on one of the following means: (1) choosing a user or a permission with the maximum number of roles according to count_user_rolesu−MRCuser or count_perm_rolesp−MRCperm, (2) choosing a user or a permission with the minimum number of roles according to count_user_rolesu−MRCuser or count_perm_rolesp−MRCperm, (3) choosing a violating permission first and then a user, and (4) choosing a violating user first and then a permission. To evaluate the effectiveness of our method under the double constraints, we consider MRCuser and MRCperm that, respectively, take groups of different values as inputs; implement the experiments with different heuristics on the America-large, Apj, Firewall 1 and Firewall 2 datasets, respectively; and output the number of roles when δ=1. The results are shown in Tables 10–13, where the values of MRCuser vary on the columns, the values of MRCperm vary on the rows, and the values of intersections of the rows and columns represent the number of the optimized roles. Notice that no valid set of roles is derived when both the constraints cannot be meet simultaneously, which is denoted with the symbol “x.”Table 10
The optimized results on America-large.
MRCpermMRCuser6543(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)145423423423423424424424424425425425425xxxx140424424425425425425426426427428428428xxxx130424424425425425425426426427428428428xxxx120425427427427426428428428427431429429xxxx110427431428428428433429429427433431431xxxx100428435431431429437432432433437435435xxxxTable 11
The optimized results on Apj.
MRCpermMRCuser131197(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)694564564564564574574574574574594584584614634654656545745745745745845845845845846045945946246446646655458460459459459461460460461463461461xx46746945459462460460460463461461463467462462xxxx35460462460460461463462462x468xxxxxx25460463462462461463462462x469xxxxxxTable 12
The optimized results on Firewall 1.
MRCpermMRCuser2117139(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)2769696969707070707171717173757373257070707071717171727272727476747422707171717273727273737474x77757518717273737374747474757676xxxx15727374747475757575767777xxxx117374757575767676x777878xxxxTable 13
The optimized results on Firewall 2.
MRCpermMRCuser9876(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)3101010101111111111111111xxxx2xxxxxxxxxxxxxxxxAs shown in Table10, the number of roles increases slightly or grows to be stable, as MRCuser or MRCperm decreases. However, no valid roles are derived from the America-large dataset when the value of MRCuser is less than 3. A further observation from the other tables is that the effective sets of roles are derived when the values of both MRCuser and MRCperm are greater, but no valid roles when MRCuser or MRCperm becomes smaller with any heuristic strategy. Thus, for the given MRCuser and MRCperm, if no valid roles can be derived, the role-optimization method is still ineffective as the constraint becomes stricter; otherwise, it remains to be effective as the constraint becomes weaker.


## 6.1. Performance Comparison with the ACRE Method for the ACPs Extraction

First, we implement experiments to study how effectively the elements of ACPs are extracted, including subjects, objects, and operations. We choose different natural language documents from multiple research domains [48], such as electronic healthcare, education, and conference management, as the research objects. For the healthcare domain, we use the open source document, called iTrust, which records the patients’ medical histories, primary caregivers, and communication results with doctors. For the education domain, we employ the resources from the IBM Course Registration System. For the conference management domain, we use the documents from the CyberChair that has been applied in different scenarios, such as conferences and workshops. We only consider the sentences that have been identified as ACPs from the documents, and the non-ACPs are not the focus of this work. The abovementioned datasets are presented in Table 1.Table 1
Descriptions of datasets.
DatasetNumber of identified ACP sentencesiTrust418IBM course registration system169CyberChair139Collected115To evaluate the effectiveness of our method for the ACPs extraction, three evaluation measuresPrecision, Recall, and F1 score are taken into consideration: Precision is the proportion of the correctly extracted ACP elements against all the extracted elements; Recall is the proportion of the correctly extracted ACP elements against all the elements in the current test dataset; F1 score indicates a coordination factor and is a weighted average between Precision and Recall. To calculate these values, we first divide the extracted values into four categories: false positive (FP), false negative (FN), true positive (TP), and true negative (TN), where FP represents the case when a word is mistakenly identified as an ACP element while it is actually not, FN represents the case when an actual ACP element cannot be correctly extracted, TP represents the correct extraction, and TN represents the case when a non-ACP element can be correctly identified. Based on these values, the Precision, Recall and F1 score are, respectively, calculated as follows:
(1)
Precision=TP/TP+FP,(2)
Recall=TP/TP+FN,(3)
F1=2×Precision×Recall/Precision+Recall,Further, the ACRE method extracts 1070 ACPs, 375 ACPs, 386 ACPs, and 258 ACPs using the iTrust, IBM Course Registration System, CyberChair, and Collected dataset, respectively. According to the algorithm in the ACRE, sentence structures throughout the documents are required to be repetitive, and more details of ACPs extraction using SRL can be found in [25]. Based on the above evaluation criteria, the results of our method as well as the performances of the ACRE method are presented in Table 2. As shown in the table, the ACRE performs well on the iTrust and IBM Course Registration System datasets, while it performs poor on the Collect dataset. The documents in the former two sets include lots of repetitive sentence structures, but there are not enough repetitions in the latter set. However, our method performs well and outperforms the ACRE method in most cases from the viewpoint of recall. This is because the SRL does not require repetitions for sentence structures. Each sentence is considered separately and is independent of other sentences. The SRL is able to find most of the ACP elements if a role set defined for the predicate exists. It provides very stable and good extraction results that are irrelevant to the sentence structures.Table 2
Comparison of the ACPs extraction.
DatasetACREOur methodPrecision (%)Recall (%)F1 (%)Precision (%)Recall (%)F1 (%)iTrust80%75%77%74%86%80%IBM course registration system81%62%70%56%86%69%CyberChair75%30%43%47%83%60%Collected68%18%29%78%87%82%However, our method does not outperform the ACRE method from the viewpoint of precision. This is because our method extracts all the verbs and considers them as the arguments using the SRL, while only a small part of these verbs describes ACPs. Other verbs arguments such as “to be” and modals do not specify ACPs in nature, which increase the ratio of FP in the ACPs extraction and then reduce the precision. Our method is unable to correctly identify all the arguments with the predicates owing to the complex structure of some sentences, which also reduces the precision.From the viewpoint ofF1 score, our method performs well with the F1 score of 82%, and it outperforms the ACRE with the F1 score of 29% for the Collected dataset. Only for the IBM Course Registration System, the ACRE performs better, as it has a higher precision that leads to the higher F1 score. Another benefit of our method is that it does not require any dataset to be labeled, while ACRE method requires a labeled dataset that is similar to the documents to be analyzed in structure and content. One issue with our method, however, is that sometimes it is unable to identify the predicate arguments using the SRL tools, as they are usually trained on publicly available documents and are not well adapted to the documents like access control requirements.


## 6.2. Performance Evaluations on Synthetic Datasets under a Single Cardinality Constraint

To further study the robustness of the constructed access-control system from the given NLACP documents, we randomly construct synthetic matricesUPA, URA, and RPA via Algorithm 1 with 80 number of users, 250 number of permissions, and 20 number of initial roles, such that matrix UPA is Boolean decomposed to be matrices URA and RPA according to different optimized variants. The basic REOPURCC&PRCC, edge-REOPURCC&PRCC, and δ-approx REOPURCC&PRCC are taken as the research objects.We carry out Algorithm2 in order to study how the constraint URCC and other factors affect the optimized results of our method in the optimization phase, when the value of the cardinality constraint varies from 2 to 8 with a step of 1. We take into account the number of the constrained roles, and the size of the optimized assignment relationships URA and RPA, as evaluation measures. The experimental results are shown in Figures 2–4. In Figure 2, the lateral axis represents the constraint threshold MRCuser, and the vertical axis represents the number of roles. In Figure 3, the lateral axis represents MRCuser, and the vertical axis represents the size of the assignments relationships URA and RPA. In Figure 4, the lateral axis represents the approximation rate, simply denoted as δ, which is calculated by URA⊗RPA/UPA, and the vertical axis represents the number of roles.Figure 2
Optimized results for the basicREOPURCC&PRCC.Figure 3
Optimized results for the edge-REOPURCC&PRCC.Figure 4
Optimized results for theδ-approx REOPURCC&PRCC.Figure2 demonstrates that the number of roles tends to decrease slightly as the value of MRCuser increases. When the value of MRCuser increases to a certain value, the number of roles tends to be stable and becomes unchanged. Specifically, the number of roles does not obviously vary and remains close to 15 when the value of MRCuser exceeds 6. However, the number of roles increases as MRCuser decreases. When the value of MRCuser equals 2, the number of roles becomes 23. Figure 3 demonstrates the effects of the constraint MRCuser on the size of the relationships URA and RPA, which is also regarded as the administrative cost of the system. Obviously, it tends to decrease as the value of MRCuser increases, which is similar to the variation tendency of Figure 2. This is because the greater the value of MRCuser is, the weaker the constraint will be. More general roles are assigned to any user. In other words, when MRCuser takes a greater value, general roles that do not include many permissions are more practical and can be utilized frequently. Thus, fewer irregular roles need to be generated, and the number of roles and size of assignments do not vary considerably. On the contrary, the less the value of MRCuser, the stricter the constraint is. When the constraint becomes strict and takes a small value, each user is allowed to associate with few roles. Thus, these roles need to possess more access permissions, in order to ensure that each user can still get enough access permissions. As a result, the number of roles and size of the assignment relationships increase remarkably. For the same dataset, in order to evaluate the effects of the approximation ratio on the mining roles, the value of MRCuser is fixed at 4, and the value of δ varies from 0.6 to 1. From Figure 4, it is observed that the number of roles increases as δ increases. This is because the greater value of the approximation rate, the better the integrity of the matrix reconstruction is. Thus, more roles are needed for covering the original permission assignments.Similarly, we carry out Algorithm3 in order to evaluate the effects of the constraint PRCC and other factors on the optimized results, with respect to the same evaluation measures. The experimental results are shown in Figures 5–7. Figure 5 shows that when MRCperm≥52, the number of roles first decreases slightly and then grows to be stable as the value of MRCperm increases. Specifically, when MRCperm equals 1, 231 roles are developed, and each role includes only one permission, which is not practical; when 2≤MRCperm<52, the number of roles decreases remarkably from 231 to 35 with the increasing value of MRCperm; when 52≤MRCperm<112, the number of roles decreases slightly from 35 to 18; when MRCperm≥112, it grows to be stable. Figure 6 demonstrates the effects of the constraint MRCperm on the size of assignments URA and RPA, which tends to decrease as the value of MRCperm increases and is similar to the variation tendency of Figure 5. This is because the less the value of MRCperm is, the stricter the constraints and the more roles and role-permission assignments that satisfy the constraint requirements will be. As a result, the value of URA+RPA increases accordingly as MRCperm decreases. For the same dataset, to evaluate the effects of the approximation ratio on the mining roles, the value of MRCperm is fixed at 80, and the value of δ varies from 0.6 to 1. From Figure 7, it is observed that the number of roles increases as δ increases. This is attributed to the fact that more roles are needed, in order to ensure the better integrity of the matrix reconstruction.Figure 5
Optimized results for the basicREOPURCC&PRCC.Figure 6
Optimized results for the edge-REOPURCC&PRCC.Figure 7
Optimized results for theδ-approx REOPURCC&PRCC.


## 6.3. Performance Evaluations on Real-World Datasets under Multiple Cardinality Constraints

To further evaluate the effectiveness and efficiency of our method, we comprehensively consider nine different real-world datasets that have been widely used for evaluating the performances of different methods of role-engineering optimization, such as Blundo method [38] and Harika method [40]. The conventional mining tool RMiner [49] can be adopted to derive different sets of candidate roles under unconstrained conditions on these datasets. The original datasets, including the density of the dataset, number of initial roles, and intervals of thresholds MRCuser and MRCperm, are shown in Table 3. The threshold intervals specify the lower and upper bounds, from which the constraints can take the values. All the experiments are implemented on a standard desktop PC with an Intel i5–7400 CPU, 4 GB RAM, and a 160 GB hard disk running a 128–bit Windows 10 operating system. All simulations are compiled and run under the Java environment.Table 3
Descriptions of original real-world datasets.
DatasetUPUPADensityInit_RolesInterval ofMRCuserInterval ofMRCpermAmerica-large3,48510,127185,2940.5%423[2, 4][2, 129]America-small3,4771,587105,2051.9%213[2, 12][2, 43]Apj2,0441,1646,8410.3%456[2, 8][2, 15]Customer10,96128445,4271.5%276[2, 25][2, 140]Domino792317304%20[2, 9][2, 6]Emea353,0467,2206.8%34[2, 3][2, 31]Firewall 136570931,95112.3%69[2, 9][2, 18]Firewall 232559036,42819%10[2, 3][2, 4]Healthcare4646148670%15[2, 6][2, 4]We take the similar research objects already used on the above synthetic datasets and consider the number of rolesR, administrative cost URA+RPA, and execution time as the evaluation measures. To study the effects of different combinations of parameters on the optimized results, we consider the approximate rare δ and a single constraint MRCuser as inputs and conduct Algorithm 2 using the Firewall 1, Firewall 2, Healthcare, America-small, Domino, and Apj datasets, respectively. Meanwhile, the value of δ varies from 0.80 to1.00 with a step of 0.05 for any dataset, and the threshold MRCuser takes a group of different values for a specific dataset. Specifically, the values of MRCuser takes 2, 4, and 8 for the Firewall 1; 2 and 3 for the Firewall 2, Healthcare and Domino; 2, 6, and 10 for the America-small; and 2, 3, and 4 for the Apj. We repeatedly implement the experiments with 75 different pair values of δ and MRCuser and compare the results with the performances of the Blundo method and Harika method, as shown in Tables 4–9, where the best results are highlighted in boldface and underlined. First of all, these tables show that, for the three methods, the values R, URA+RPA, and the execution time almost all increase as MRCuser decreases, whenever δ is fixed at a certain value. In addition, these evaluation values all decrease as δ decreases, whenever MRCuser is fixed, which is consistent with the performances and analyses on the synthetic datasets, as shown in Figures 2–4.Table 4
Performance comparisons on Firewall 1.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm248491524849152484915RURA+RPAExecution time (s)Blundo method1.00365906571686832,6815,8074,4263,2283,1943,1947288833837610.95280774255413723,9774,7193,7282,5742,4332,4316986813534570.90234533447332917,0583,8562,9412,1882,0662,0596784783330510.85189492735271814,6732,8551,7931,7991,6981,6716480743129470.80178411528191710,4171,9821,6011,3611,2471,247627669292639Harika method1.0090857112565657,1907,2074,6463,3023,2733,2734777754248380.956753438546415,8716,2253,8632,5632,4772,4614571694043370.905846327236333,7834,5873,0052,0842,0142,0014264623941370.854439266637352,5743,5912,3791,7741,6731,6453962593741360.803425194928231,9372,4131,3161,3571,3421,301325856353436Our method1.008885817168687,2016,8896,6313,0162,9882,8465768634345350.953748383438355,7385,6835,6692,7912,3122,3085665604140370.902825152320164,6684,3422,9672,0461,9191,9015463583939370.8518108161282,6601,7651,9981,6981,5671,5895260543837360.801296131071,9231,6891,8401,3021,2761,246495551353435Table 5
Performance comparisons on Firewall 2.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm232423242324RURA+RPAExecution time (s)Blundo method1.003253255901237,07837,07837,6091,5787748954650.953243245831236,85136,85136,9811,5037247951610.903213214741236,51736,51735,1321,4986944939600.853193193651236,12136,12131,2071,3216542901590.803073073611135,98135,98129,5781,302613987756Harika method1.001111323111,5101,54836,6081,3784846724430.951110281111,5071,50134,9811,3034745701350.9066273111,0331,03332,1321,1984542697340.8555264111,0331,03331,2071,1214341574210.8055260101,0311,02529,578902413754420Our method1.001111590121,6111,60737,6081,5786563954650.951110501121,6111,60436,9811,5036460951610.9066453121,2541,23135,1321,4986157939600.8566401111,1371,11731,2071,3215955901590.8065387101,0841,05929,5781,302555187756Table 6
Performance comparisons on healthcare.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm232423242324RURA+RPAExecution time (s)Blundo method1.00461846231,5785631,57839922430.95411646231,4924711,50333122430.90371545211,4214221,47129621430.85311344211,3273791,41123212330.80291342201,2033051,3641972133Harika method1.00181546235632631,57838922430.95181546235632631,43330122430.90171345215572541,32122622320.85161344215512521,25119221320.80151242205402391,1741662131Our method1.00201946234374181,57939221430.955625171932051,40330011430.905623162272111,33721121330.855621152132091,18118611320.805421151991341,0241751132Table 7
Performance comparisons on America-small.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm261022040261022040261022040RURA+RPAExecution time (s)Blundo method1.0025925925920720720725,48825,48825,48810,45010,45010,4501511501501531591600.9525425225220720720724,78924,74324,73110,33010,33010,3211511481451531591600.9023723423420520120123,98323,96023,94410,25810,25810,2471491471461471441430.8523122422419919519521,11421,10321,09810,11910,11910,1111481491441461431410.8022421721719719619420,61820,44520,11210,01710,01710,003145145144143142139Harika method1.0025824422520720720722,72318,53213,99711,65611,65611,6564291,5921,6127477297830.9522424322020720720721,63920,70920,08811,61511,61511,6094011,5821,5937257017590.9021717816520620120119,44519,20919,00711,60911,60911,6013781,5771,5887206917110.8516715513219219219018,88118,25718,10111,58911,58911,5773621,5241,5647116886790.8015915113119118718217,66516,34315,90611,57311,57311,5153601,5021,523703683673Our method1.0025925724920720720725,94423,64022,19511,65611,65611,6561,6501,5781,6131,6501,3771,3770.9522718618520720720723,17421,34920,10911,61511,61511,6091,5441,5181,6131,5441,2121,2120.9020916815320620120121,93920,8652173711,60911,60911,6011,5011,4771,5791,5011,1791,1790.8518514013219519419320,93717,83414,70911,58911,58911,5771,4561,4051,4031,4561,1021,1020.8017312711819318317718,73316,47014,28611,57311,57311,5151,3391,3651,3061,3391,0601,060Table 8
Performance comparisons on Domino.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm232423242324RURA+RPAExecution time (s)Blundo method1.0023231252073973996796721510.9522221241973173196396311510.9020201201772972995995911510.8518181181772772795195111510.801515107157247249439431141Harika method1.0027231232076276195395321510.9520181241873072994594521510.9018171201772472193193121510.8515131181570570192092011410.801411107126826799029021131Our method1.0022211252172572396796721510.9518161241969769496396311510.9015141201769168995995911510.8513121181768567995195111510.801010107156766639439431141Table 9
Performance comparisons on Apj.
MethodδMRCuserMRCpermMRCuserMRCpermMRCuserMRCperm234271223427122342712RURA+RPAExecution time (s)Blundo method1.002,04448645449245745510,9296,1296,1295,1785,0455,034751,4311,5354346490.951,9973883444874324449,8906,0786,0785,0475,0474,943711,4291,4274145470.901,9653463214754214219,7345,9835,9834,9864,9864,879701,4251,4233944450.851,8232963154614094079,6785,7115,7114,7614,7614,642671,3811,3753741410.801,6502802934513643809,6555,5945,5944,5234,5234,469631,3721,366354039Harika method1.005644704574924574556,1295,3725,1605,3415,1215,1158839398877477800.954613753554874254215,4814,1894,1105,0195,0194,9177339398717287410.904023313304754194154,5344,0033,9124,9684,9684,8656537388647107300.853432893214613773744,3253,9473,8544,7124,7124,6315736368496787050.803082742734513563404,0863,6093,3914,4334,4334,459353333830653667Our method1.005674994874924574556,0195,9155,5315,4775,4775,1069249384445470.954603953814874234205,3764,4354,3405,0325,0324,9089139384045450.904093293244744214184,4924,2354,0414,9754,9614,8698935374045440.853412873134603883824,0173,8523,8524,7384,7084,6308534373843420.803142912694513523613,8153,5863,5864,4294,4224,460813237343940We compare the performances of the three methods using different datasets. As shown in Table4, compared to the other methods, our method returns a smaller set of roles in 14 tests out of 15, in terms of the values of R, while it returns a smaller size of assignment relationships only in 4 tests, in terms of the values of URA+RPA. Furthermore, it runs faster than the other two in 10 tests out of 15. Thus, according to the number of roles and execution time, our method outperforms the other two on the Firewall 1 dataset. As shown in Table 5, our method performs as well as the Harika method in terms of the values of R. However, the Harika method performs better and returns a smaller size of assignment relationships and runs faster in all the 10 tests. In summary, the Harika method outperforms our method on the Firewall 2 dataset. As shown in Table 6, compared to the other methods, our method returns a smaller set of roles in 8 tests out of 10, and it returns a smaller size of assignment relationships in 9 tests out of 10. Furthermore, it runs faster than the other two in all the 10 tests. Thus, our method outperforms the other two on the Healthcare dataset. As shown in Table 7, our method returns a smaller set of roles in 11 tests out of 15. However, in terms of the values of URA+RPA, the Harika method performs better and returns a smaller size of assignment relationships in all the 15 tests; in terms of execution time, the Blundo method performs better, which is from 3 to 10 times faster than Harika method, and is about 10 times faster than our method in all the 15 tests. In summary, our method does not perform as well as the Blundo method on the America-small dataset. As shown in Table 8, our method returns a smaller set of roles than the other two methods in all the 10 tests, and it also returns a smaller size of assignment relationships in all these tests. Further, in terms of execution time, our method also performs well. Thus, our method outperforms the other two on the Domino dataset. As shown in Table 9, our method returns a smaller set of roles in 7 tests out of 15, while the Harika method returns the best results in the other 8 tests. In terms of the values of URA+RPA, our method returns a smaller size of assignment relationships in 8 tests out of 15, while the Harika method returns the best results in the other 7 tests. In terms of execution time, our method returns runs faster in 7 tests out of 15, while the Harika method spends less time in the other 8 tests. Thus, our method performs almost as well as the Harika method on the Apj dataset.Second, we consider the approximate rareδ and another cardinality constraint MRCperm as inputs and conduct Algorithm 3 on the same datasets. The threshold MRCperm takes a group of different values for a specific dataset. Specifically, we set 4, 9, and 15 for the Firewall 1; we set 2 and 4 for the Firewall 2, Healthcare and Domino; we set 2, 20, and 40 for the America-small; we set 2, 7, and 12 for the Apj. We also conduct the experiments 75 times with different parameter pairs and compare the performances of different methods as shown in the remaining columns of Tables 4–9, where the best results are also highlighted in boldface and underlined. As shown in Table 4, our method returns a smaller set of roles in all the 15 tests, and it returns a smaller size of assignment relationships in 14 tests of 15. Furthermore, in terms of execution time, our method performs as well as the other two, though it runs faster only in 5 tests out of 15. In summary, our method outperforms the other two on the Firewall 1 dataset. As shown in Table 5, compared with our method and the Blundo method, however, the Harika method performs better and returns a smaller set of roles and a smaller size of assignment relationships, and it runs faster in all the 10 tests. Thus, the Harika method outperforms our method on the Firewall 2 dataset. As shown in Table 6, compared to the other methods, our method returns a smaller set of roles in all the 10 tests, and it returns a smaller size of assignment relationships in 6 tests out of 10. Furthermore, it runs as fast as the other two. Thus, our method outperforms the other two on the Healthcare dataset. As shown in Table 7, our method performs as well as the other two in terms of the number of roles. However, in terms of the values of URA+RPA, the Blundo method performs better and returns a smaller size of assignment relationships in all the 15 tests; in terms of execution time, the Blundo method also performs better, which is from 5 to 10 times faster than Harika method, and is from 7 to 10 times faster than our method in all the 15 tests. Thus, our method does not perform as well as the Blundo method on the America-small dataset. As shown in Table 8, in terms of the values of URA+RPA, the Harika Method returns a smaller size of assignment relationships in all the 10 tests, However, the three methods return the similar results in terms of the values of R and time overhead, respectively. Thus, according to the number of roles and execution time, our method performs as well as the other two methods on the Domino dataset. As shown in Table 9, our method returns a smaller set of roles in 6 tests out of 15, and the Harika method also returns the best results in 6 tests out of 15. Further, our method returns a smaller size of assignment relationships in 6 tests out of 15, and the Harika method also returns the best results in 6 tests out of 15. In terms of execution time, our method runs faster in 8 tests out of 15, while the Harika method spends less time only in 2 tests out of 15. Thus, our method outperforms the Harika method on the Apj dataset.Next, we study the effects of both the URCC and PRCC on the optimized results. According to Algorithm4, a heuristic strategy in line 4 is used to pick either a violating user or a violating permission, based on one of the following means: (1) choosing a user or a permission with the maximum number of roles according to count_user_rolesu−MRCuser or count_perm_rolesp−MRCperm, (2) choosing a user or a permission with the minimum number of roles according to count_user_rolesu−MRCuser or count_perm_rolesp−MRCperm, (3) choosing a violating permission first and then a user, and (4) choosing a violating user first and then a permission. To evaluate the effectiveness of our method under the double constraints, we consider MRCuser and MRCperm that, respectively, take groups of different values as inputs; implement the experiments with different heuristics on the America-large, Apj, Firewall 1 and Firewall 2 datasets, respectively; and output the number of roles when δ=1. The results are shown in Tables 10–13, where the values of MRCuser vary on the columns, the values of MRCperm vary on the rows, and the values of intersections of the rows and columns represent the number of the optimized roles. Notice that no valid set of roles is derived when both the constraints cannot be meet simultaneously, which is denoted with the symbol “x.”Table 10
The optimized results on America-large.
MRCpermMRCuser6543(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)145423423423423424424424424425425425425xxxx140424424425425425425426426427428428428xxxx130424424425425425425426426427428428428xxxx120425427427427426428428428427431429429xxxx110427431428428428433429429427433431431xxxx100428435431431429437432432433437435435xxxxTable 11
The optimized results on Apj.
MRCpermMRCuser131197(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)694564564564564574574574574574594584584614634654656545745745745745845845845845846045945946246446646655458460459459459461460460461463461461xx46746945459462460460460463461461463467462462xxxx35460462460460461463462462x468xxxxxx25460463462462461463462462x469xxxxxxTable 12
The optimized results on Firewall 1.
MRCpermMRCuser2117139(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)2769696969707070707171717173757373257070707071717171727272727476747422707171717273727273737474x77757518717273737374747474757676xxxx15727374747475757575767777xxxx117374757575767676x777878xxxxTable 13
The optimized results on Firewall 2.
MRCpermMRCuser9876(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)(1)(2)(3)(4)3101010101111111111111111xxxx2xxxxxxxxxxxxxxxxAs shown in Table10, the number of roles increases slightly or grows to be stable, as MRCuser or MRCperm decreases. However, no valid roles are derived from the America-large dataset when the value of MRCuser is less than 3. A further observation from the other tables is that the effective sets of roles are derived when the values of both MRCuser and MRCperm are greater, but no valid roles when MRCuser or MRCperm becomes smaller with any heuristic strategy. Thus, for the given MRCuser and MRCperm, if no valid roles can be derived, the role-optimization method is still ineffective as the constraint becomes stricter; otherwise, it remains to be effective as the constraint becomes weaker.


## 7. Conclusions

A novel hybrid role-engineering method, called HREOMCC_NLP&ILP, was proposed in this paper. We first used the NLP techniques to extract machine-readable and machine-enforceable ACPs from the natural language requirement documents and then developed an initial access control system. The evaluation of extracting ACPs on benchmark datasets showed that our method performs better than the existing method and returns the best results with a precision of 78%, recall of 87%, andF1 score of 82%. Next, we converted the role-engineering problem into the BMD problem, defined several variants of the optimization problem with multiple cardinality constraints, and proposed a unified modelling framework using the ILP technique. We also presented the heuristic algorithms for solving all the optimization problems in the initial constructed system. The experiments on synthetic and real-world datasets demonstrated that the proposed method is efficient and effective. However, a few interesting issues remain to be resolved. One issue is how to improve the precision ratio of ACPs extraction during the process of constructing access control systems, in order to further alleviate manual workloads and reduce human errors. Another issue is how to implement the other cardinality constraints or other types of constraints for hybrid role-engineering optimization in future work.



---

*Source: 3453041-2022-05-11.xml*