IIT Kharagpur, India

Discovery of Attribute Based Access Control policies through mining has been studied extensively in the literature. However, current solutions assume that the rules are to be mined from a static data set of access permissions and that this process only needs to be done once. However, in real life, access policies are dynamic in nature and may change based on the situation. Simply utilizing the current approaches would necessitate that the mining algorithm be re-executed for every update in the permissions or user/object attributes, which would be significantly inefficient. In this paper, we propose to incrementally maintain ABAC policies by only updating the rules that may be affected due to any change in the underlying access permissions or attributes. A comprehensive experimental evaluation demonstrates that the proposed incremental approach is significantly more efficient than the conventional ABAC mining.

The flexibility, scalability, dynamic nature, portability and identityless features of Attribute Based Access Control (ABAC) make it an attractive choice to be employed as a means to enforce access control in many traditional and emerging application domains [8]. Under ABAC, security policies (also called rules in this paper) are specified based on subject, object and environmental attribute conditions. However, a key problem in deploying ABAC is to precisely configure it for effective access control. The problem of automatically discovering the best set of minimum ABAC rules to configure the system using existing permissions of users on the resources is known as ABAC Policy Mining.

While the ABAC mining problem has been well studied in the literature, all the approaches assume the system to be static in nature. However, in reality, all systems change in due course of time, which necessitates updating (or maintaining) the ABAC rules since the original rules may no longer be valid. Such maintenance requires re-mining of the ABAC policies that reflect the changes, which is often quite expensive and inefficient, especially when the number of users and objects is large and changes to the data are quite frequent.

In this paper, we propose an efficient alternative where ABAC policy maintenance can be performed in an incremental fashion whenever a change occurs. In particular, we consider the following changes (Δ). Note that other changes such as adding subjects and objects do not affect the ABAC policies.

Given the current set of ABAC policies and the set of changes Δ, the two alternative approaches to discover the new set of ABAC policies have been depicted in Figure 1. More specifically:

Alternative Approaches to Maintenance of ABAC Policies

In this paper, we have employed the ABAC-SRM mining algorithm proposed by Talukdar et al. [20] as this is one of the fastest approaches thus far proposed. We have compared the efficiency of the above two approaches - the redo ABAC mining and the incremental maintenance. Since the data used to mine the policies in the latter case is significantly smaller than the former approach, is very efficient as shown in our experimental evaluation.

The rest of this paper is organized as follows. In Section 2, we review the preliminaries of ABAC definition and concepts, as well as the ABAC-SRM mining approach [20]. In Section 3, we discuss the types of changes and formalize the problem of incremental maintenance of ABAC policies. We also provide an overview of the approach to solve the problem. In Section 4 we present the proposed incremental maintenance approach with detailed algorithms. This includes a pre-processing phase to extract the necessary intermediate data structures and algorithms to handle the four types of changes mentioned above. In Section 5, we experimentally compare the cost of maintaining ABAC system using our proposed incremental maintenance approach versus employing the redoing ABAC mining approach. In Section 6 we discuss the related work and in Section 7, we present conclusions and future research.

In this section, we briefly review the attribute based access control model (ABAC) [9], and the ABAC mining approach from Talukdar et al. [20], called the ABAC-SRM. The notations of ABAC and ABAC Mining approach have been borrowed from [20].

In an ABAC system, the authorization to perform an operation (e.g., read, write) is granted based on the attributes of the requesting user, requested object, and the environment in which a request is made. The ABAC policy rules are comprised of the attributes, which include user attribute conditions and object attribute conditions that determine granting of a permission to the user.

The basic components of an ABAC system are as follows:

Users (U): Represents a set of authorized users/subjects. ui, for 1 ≤ i ≤ |U| denotes each member of this set.

Objects (O): Represents a set of resources to be protected. Each member of this set is denoted as oi, for 1 ≤ I ≤ |O|.

Environment (E): Represents a set of environment conditions, independent of users and objects. Each member of this set is denoted as ei, for 1 ≤ i ≤ |E|.

UA:Represents a set of user attribute names. Members of these sets are represented as uai, for 1≤ i ≤ |UA|, Each uai is associated with a set of possible values it can acquire. For instance, if a user attribute Title is associated with the values {Instructor, TA, Student}, then for every u ∈ U, value of the attribute Title can be either Instructor, TA or Student.

OA:Represents a set of object attribute names. Members of these sets are represented as oai, for 1 ≤ j ≤ |OA|. Each oai is associated with a set of possible values it can acquire. For instance, if an object folder with records of student has object attribute Major associated with a set of values {Computer Science, Electronics, Mechanical}, then for every o ∈ O, value of the attribute Major can be either Computer Science, Electronics or Mechanical.

EA: Represents a set of environment attribute names. Members of these sets are represented as eai, for 1 ≤ i ≤ |EA|. Each eai is associated with a set of possible values it can acquire. For instance, if an environment attribute Campus is associated with a set of values {USA, UK, Australia}, then for every e ∈ E, value of the attribute Campus can be either USA, UK or Australia.

P: A set consisting of all possible permissions/operations on objects allowed in a system. For example, if read and write are the only two possible operations on objects, then P = {read, write}. Each member of P is represented as pi, for 1 ≤ i ≤ |P|.

UC: Represents a set of all possible user attribute conditions denoted as ucj, for 1 ≤ j ≤ |UC|. Members of this set are represented as equalities of the form n = c, where n is a user attribute name and c is either a constant or any. For instance if user attribute Title has possible values {Instructor, TA, Student} and user attribute Department has possible values as {Computer Science, Electronics, Mechanical}, then UC will be a set comprising of {Title=Instructor, Title=TA, Title=Student, Title=Any, Department=Computer Science, Department=Electronics, Department=Mechanical, Department=Any}. Note here, that the condition n = Any does not have to be explicitly chosen. It is set only if at least one other condition for n is present.

OC: Represents a set of all possible object attribute conditions denoted as ock, for 1 ≤ k ≤ |OC|. Members of this set are represented as equalities of the form n = c, where n is an object attribute name and c is either a constant or any. For instance if object attribute Major has possible values {Computer Science, Electronics, Mechanical} and object attribute RecordsOf has possible values {Instructor, TA, Student, Staff }, then OC will be a set comprising of {Major=Computer Science, Major=Electronics, Major=Mechanical, Major=Any, RecordOf= Instructor, RecordOf=Student, RecordOf=TA, RecordOf=Staff, RecordOf =Any}. For an attribute name n, if the value of c is any, then the attribute n is not relevant for making the corresponding access decision. Therefore, as above, the condition n = Any does not have to be explicitly chosen. It is set only if at least one other condition for n is present.

Π: Represents a set of access rules called the rule base of the ABAC system. Each member of this set is denoted as ri, for 1 ≤ i ≤ |Π|. A rule r in ABAC is of the form 〈uc, oc, p〉.

If a user makes a request to access an object, the rule base is searched for any rule through which the user can gain access. If such a rule exists, then the access is granted, otherwise it is denied.

For the sake of simplicity, in this paper, we assume the environment condition to be any.

UA: User attribute relation UA ⊆ U × UC is a many-to-many mapping of users and user attribute conditions. We use a m × n binary matrix to represent UA , where UA [i,j]=1, if user ui satisfies an attribute condition ucj. An example is shown in Table 1 where user u1 is a TA whose department is Electronics.

UA

OA: Object attribute relation, OA ⊆ O × O C is a many-to-many mapping of objects and the set of all attributes conditions, where an m × n binary matrix represents OA. OA [i,j]=1 if an object oi satisfies an object attribute condition ocj. Table 2 shows an example where object o1 is the recordof Student in Electronics Major.

OA

A: An authorization a is of the form of 〈u ,o, p〉 and represents user u ∈ U, object o ∈ O , and permission p ∈ P, respectively, where a denotes that a user u is allowed to perform an operation p on an object o. We use p.a as the permission associated with a. We denote the set of all authorizations as A. For each permissions pi ∈ P , we define Api ⊂ A such that for every a∈Apl, p.a = pi. For example, if P = {read,write}, we have Aread and Awrite such that Aread ∪ Awrite = A.

Given A, we construct a table UOPp for each permission type p (read, write etc.). The columns of this matrix are all possible user attribute conditions and object attribute conditions of users and objects in A, respectively, a column for p and column for Row Id. There is a row in UOPp for each user object pair. For each row, if the user attribute condition (object attribute condition) is true for a user (object), the corresponding cell is filled with 1, otherwise with 0. If there exists a a = 〈u ,o, p〉, we insert a 1 in the p column of that u − o . For the remaining rows, the p column is 0. Given P = {p1, p2 … pn}, UOP=∪i=1nUOPpt.

UOPp: User Object Permission Matrix UOPp, is a M × N matrix, where M = |U| × |O| comprising of a row for each user-object pair, and N = |UC| + |OC| + 1, comprising of a column for each object attribute condition, a column for each user attribute condition, and a column for the permission p and a column for Row Id. For the UA in table 1, OA in table 2 and A in table 4a, table 4b shows the UOPread constructed.

The set of Authorizations and the correspondingUOPRead

Given the set of authorizations A, the set of user attribute conditions (UC), the set of object attribute conditions(OC), ABAC Mining discovers minimum set of access rules Π such that there exists a rule r ∈ Π where u is allowed to perform p on o iff a = 〈u ,o ,p〉 ∈ A. Table 3 shows the rules Π corresponding to the UOPread in table 4b.

Π

In this work, to find out Π, the ABAC-SRM Mining algorithm has been used. This algorithm finds minimum possible ABAC rules through subset enumeration. It is being used in the form of the following function: ABAC-SRM(Perm1Rules,Perm0Rules,SpecificRules), where Perm1Rules are the Permission One rows, Perm0Rules are Permission Zero rows and SpecificRules are current ABAC rules. This function evaluates the ABAC rules Π and returns them.

In this section, we define the problem of maintenance of ABAC policies in an incremental fashion, and discuss the basic idea behind our proposed approach.

Δ: Represents a set of possible changes allowed in an ABAC system. Each member is denoted as Δi for 1 ≤ i ≤ |Δ|. The change Δ could be to authorization set (A) or User Attribute Relation (UA) or Object Attribute Relation (OA) in ABAC, and makes the current rules Π invalid. Types of changes, Δ are:

This will lead to the permission column of a row in UOP corresponding to user m_user and object m_object to be changed from 0 to 1.

This will lead to the permission column of a row in UOP corresponding to user m_user and object m_object to be changed from 1 to 0.

This will lead to the attribute condition being 1 for all of the user’s/object’s rows in the UOP.

This will lead to the attribute condition being 0 for all of the user’s/object’s rows in the UOP.

We assume that during the addition and deletion of permission changes, the user/object attribute values remain the same. Similarly, we assume that during the addition and deletion of attribute values, the permissions of users on objects remain unchanged. We would also like to note that addition/deletion of environment attributes will be handled similar to user/object attributes.

Given a set of ABAC rules Π that encapsulate the original access policy, and the change △, the Incremental ABAC Maintenance Problem aims to discover a set of rules Π′ that encapsulates the new access policy derived by applying the changes Δ more efficiently than re-mining the new policy.

The concept behind performing incremental mining is that whenever a change occurs, it impacts only a particular row in the UOP or a small set of rows in the UOP. We only need to work on that part of the UOP to update the ABAC rules. Intuitively, we need to replace a few rows in the UOP with new ones which have the change incorporated in them. We can have two types of rows in UOP that can be added or deleted from the UOP:

For example, in Table 5, the Permission One Rows are [3,5,6,8] and Permission Zero Rows are [1,2,4,7,9]. For every type of change, we delete the Permission Zero and Permission One rows impacted and add the modified/changed Permission Zero and Permission One rows back to the data set (or data structures that we maintain for efficient updation). Our approach to incremental ABAC maintenance is based on the above concept.

Illustrative example:UOP

In this section, we describe in detail our proposed approach to perform the incremental maintenance of ABAC policies. We first discuss the steps performed during the pre-processing phase and then discuss the incremental maintenance algorithms for the four change types.

The incremental ABAC maintenance approach is based on the idea that we maintain certain intermediary data structures on which we can operate to find out the new set of ABAC rules Π′. Specifically, given the set of ABAC rules Π (i.e, the original policy) and the UOP derived from the policy, we maintain the following data structures:

We will denote the entire set of the above data structures by I. Algorithm 1 gives the specific steps to construct these, and utilizes two helper functions: i) findZeroRules (Algorithm 2) and ii) CoverageCalc (Algorithm 3). findZeroRules takes as input ZeroRowIds and returns the minimum set of Permission Zero Rows that encapsulate all the Zero rows such that each Zero row is a subset of atleast one ZeroRule. This is done by sorting the Zero Rows in descending order based on the number of attribute conditions in each row and then by adding each row that is not already covered by some rule to the ZeroRules.

The CoverageCalc function is used to find OneRowCoverage and ZeroRowCoverage. CoverageCalc takes as input the OneRowIds or ZeroRowIds, Π or ZeroRules and type as 1 for OneRowCoverage and 0 for ZeroRowCoverage. It returns the corresponding list of sets called coverage in Line 9 (OneRowCoverage or ZeroRowCoverage depending on the type). This is accomplished by simply iterating over each rule and each row provided as input and checking if the rule is a subset (superset) of the role if the ZeroRowCoverage (correspondingly, OneRowCoverage) is requested.

Consider the UOP given in Table 5. The existing ABAC rules in the system are : [(uc3, oc2), (uc1, uc2, oc1)]. By performing the Pre-processing Steps, we get:

Algorithm 4 gives the procedure to grant m_user the permission to access m_object . This is done by removing the corresponding row from the list of permission zero rows and adding to the list of permission one rows. Two helper functions are used to accomplish this: i) Delete_Perm0Rows (Algorithm 5) and ii) Add_Perm1Rows (Algorithm 6).

Delete_Perm0Rows (del0rowsIds) Algorithm 5 gives the specific steps for removing a permission. First, we remove the row from the permission zero rows (Line 3). Now, we update the intermediary data structures. First we update the ZeroRowCoverage mapping. If the permission row to be removed is a rule in ZeroRules then we need to recompute the rule by removing it from the set of zero permission rows covered by that rule (lines 7–8). Off course, if this is the only zero permission row represented by that rule, then it is eliminated altogether. Otherwise the permission row is removed from the cover of every rule in ZeroRules it belongs to (line 10). Lines 15–20 update the ZeroRules, ZeroRuleIds, and the ZeroRowCoverage by first removing the appropriate rules and affected covers, and then adding in the additional rules prior calculated (at line 7) and recalculating the cover corresponding to those rules (line 17).

Algorithm 6 gives the specific steps for adding a permission one row. This function adds the rows given in add1rows to the ABAC system and re-mines the policy. To do this, the ABAC-SRM function is used, but instead of passing in the entire UOP, only the ZeroRules, add1rows and Π are used since they encapsulate the entire UOP, and therefore the mining is much more efficient, as confirmed by the experimental evaluation. We then update the OneRowIds and the OneRowCoverage using CoverageCalc (Algorithm 3).

Granting u3 access to o3, means we have to make the permission in RowId 9 equal to 1. This effectively means we have to delete the Permission Zero, Row Id 9 from the UOP and add a Permission One row with the same attribute conditions. Therefore, Algorithm 4 calls Delete_Perm0Rows with [9] and Add_Perm1Rows with argument ([(uc1, uc2, oc2, oc3)],[9]), obtaining the output given below:

Delete_Perm0Rows([9])

Add_Perm1Rows([(uc1, uc2, oc2, oc3)],[9])

Algorithm 7 gives the specific steps to revoke m_user ‘s permission to access m_object . This is done by removing the corresponding row from the list of permission one rows and adding to the list of permission zero rows. Two helper functions are used to accomplish this: i) Delete_Perm1Rows (Algorithm 8) and ii) Add_Perm0Rows (Algorithm 9).

Algorithm 8 gives the specific steps to delete permission one rows from the ABAC system. Note that whenever a permission one row is deleted, some ABAC rules become invalid. These rules are found in Line 2, using OneRowCoverage. Every Id in del1rowsIds is checked in every cover of OneRowCoverage. If an Id is in a cover, the index of the cover is added to ridinvalid. The numbers in ridinvalid signify that those rules in Π have become invalid. Next, in Lines 3 – 5, for all r in ridinvalid, minerowids is evaluated, which is cover at r (in OneRowCoverage) after the del1rowsIds are deleted from it. The Π and covers in OneRowCoverage are deleted at row numbers in ridinvalid in Line 6.

The list of attribute conditions of the rows in minerowids is put in minerows in Line 7. In Line 8, rowsleftattributes are then used to mine new Π using the algorithm ABAC-SRM. In Lines 9 – 10, OneRowIds are updated by removing the del1rowsIds from them and OneRowCoverage is also updated by using CoverageCalc function in Algorithm 3.

Algorithm 9 gives the specific steps to add permission zero rows. It adds the add0rows to the ABAC system. When permission zero rows are added, some rule in Π may become invalid. If an ABAC rule is subset of a Permission Zero row, the rule becomes invalid. In Line 2, we find any such rules that become invalid. For each row in add0rows, and for all Π, if any rule in Π is a subset of any row in add0rows, index of that rule is added to ridinvalid. In Line 3, for all rules in ridinvalid, the row Ids in OneRowCoverage are added to minerowids and in Line 4, the attribute conditions of all rows in row Ids of minerowids are made into list and added to minerows. Next, in Line 5 and 6, at the row numbers in ridinvalid, we delete the Π and covers in OneRowCoverage. In Lines, 7–15, we update the ZeroRules by adding the add0rows. If a rule in ZeroRules is a subset of a row in add0rows, then the rule is replaced with the row in add0rows; the row in add0rows is added to ZeroRules if it is not subset of any rule in ZeroRules. In Line 16, the add0rowsIds are added to ZeroRowIds. Also in Line 17, ZeroRuleIds and ZeroRowCoverage are updated. Finally, in Line 18, Π are updated using the ABAC-SRM mining algorithm. As earlier, the mining is much more efficient in practice since it only utilizes the ZeroRules and the Π as opposed to the entire UOP.

This means we have to make the permission in RowId 8 equal to 0. This effectively means we have to delete the Permission One, Row Id 8 from the UOP and add a Permission Zero row with same attributes conditions. Therefore, Algorithm 7 calls Delete_Perm1Rows with [8] and Add_Perm0Rows with [(uc1, uc3, oc2, oc3)],[8]), obtaining the output given below:

Delete_Perm1Rows([8])

Add_Perm0Rows([(uc1, uc3, oc2, oc3)],[8])

Algorithm 10 gives the specific steps to add the attribute value m_attribute to user m_user . This is done in four steps: i) we extract all permission zero rows and permission one rows for m_user and the corresponding attribute sets (lines 1–4); ii) we remove the corresponding rows from the permission zero and permission one rows; iii) we update the attributes sets; iv) we insert the updated rows into the permission zero rows and permission one rows. To ensure that the intermediary data structures are consistently maintained, the four prior defined functions i) Delete_Perm0Rows (Algorithm 5); ii) Delete_Perm1Rows (Algorithm 8); iii) Add_Perm0Rows (Algorithm 9) and iv) Add_Perm1Rows (Algorithm 6) are used to accomplish this. Note that an attribute value can also be added to an object in exactly the same way.

Adding attribute condition uc3 to user u1, requires removing all the rows of user u1, i.e. Row Ids 1, 4 and 7. Then we have to add the attribute condition uc3 to the attribute condition set of these rows and add them back to the data set. Therefore, Algorithm 10 calls Delete_Perm0Rows with [1, 4, 7], Delete_Perm1Rows with ϕ, Add_Perm0Rows with [(uc2, uc3, oc1),(uc2, uc3, oc1, oc2), (uc2, uc3, oc2, oc3)],[1,4,7] and Add_Perm1Rows with (ϕ, ϕ) obtaining the output given below:

Delete_Perm0Rows ([1,4,7])

Delete_Perm1Rows (ϕ)

Add_Perm0Rows ([(uc2, uc3, oc1),(uc2, uc3, oc1, oc2), (uc2, uc3, oc2, oc3)],[1,4,7])

Add_Perm1Rows (ϕ, ϕ)

Algorithm 11 gives the specific steps to remove attribute value m_attribute from user m_user. This works exactly the same as Algorithm 10, except that in line 7, we delete m_attribute from the permission zero and permission one rows for m_user, before updating all the intermediary data structures.

Removing attribute condition uc1 from user u2 requires removing all the rows of user u2, i.e. Row Ids 2, 5 and 8. Then we have to remove the attribute condition uc1 from the attribute condition set of these rows and add them back to the dataset. Therefore, Algorithm 11 calls Delete_Perm0Rows with [2], Delete_Perm1Rows with [5, 8], Add_Perm0Rows with [(uc3, oc1)], [2] and Add_Perm1Rows with [(uc3,oc1,oc2),(uc3,oc2,oc3)],[5,8] obtaining the output given below:

Delete_Perm0Rows([2])

Delete_Perm1Rows([5,8])

Add_Perm0Rows([(uc3,oc1)], [2])

Add_Perm1Rows([(uc3,oc1,oc2),(uc3,oc2,oc3)],[5,8])

We carried out detailed experiments to study the effectiveness of the proposed approach in a wide variety of settings, and to understand the effect of different factors. There are no real datasets available that capture the incremental change in ABAC policies. So we ran experiments on synthetic datasets and controlled the degree of changes and examined the effect of each parameter independently.

We have used the synthetic dataset generator introduced by Talukdar et al. in [20] to create ABAC policies. The input data set for the four ABAC maintenance algorithms and ABAC Mining (using ABAC-SRM) are the same.

ABAC Maintenance algorithms for each type of change were implemented considering a single modification at a time and without putting constraints to perform a fair comparison with ABAC-SRM algorithm. The ABAC Maintenance algorithms can handle multiple permissions and constraints.

For each set of parameter values, synthetic data was created. The default values for the various parameters are given in Table 6. In each experiment, we vary one parameter of interest while the rest are set to the default values given in Table 6.

Default values of Parameters

ABAC rules were mined from the dataset using the ABAC-SRM algorithm. While using the proposed ABAC Maintenance algorithm, pre-processing steps were carried out and recorded as Pre-Processing Time. Further, for every change type (four ABAC Maintenance Algorithms: Add Permission, Delete Permission, Add Attribute value, Delete Attribute value), a random possible input (user and object or user and attribute value) is identified and both ABAC Maintenance and ABAC-SRM algorithms are used to accommodate the change. For all four change types, this process was repeated for 20 random possible inputs on a data set. For Add attribute value and Delete attribute value, we have performed experiments for addition and deletion of attribute in users. The results will be similar for object attributes and environment attributes.

Our objective is to compare the difference in time taken by the two approaches for different types of changes. Therefore, we observed: (I) the time taken for redoing the ABAC Mining from scratch; (II) the time taken for pre-processing to generate the intermediary data structures; and (III) the time taken for incrementally updating the policy as well as the intermediary data structures.

Note that without incremental maintenance, the time required for any change is given by (I). If incremental maintenance is used, then the time given by (II) is a one-time cost, while the time given by (III) is incurred for each change. From the figures, it is observed that for all the cases, ABAC Maintenance (III) is more efficient than ABAC-SRM (I). In fact, ABAC Maintenance (III) with the Preprocessing steps (II) also performs better than ABAC-SRM (I).

Figure 3 gives the average running time for adding a permission. Figure 3a shows the time taken when the User-Object Count is varied. It can be observed that the time taken for mining, preprocessing and incremental update all increase linearly. However, the overall time taken by the incremental approach is significantly less. Figure 3b shows the time taken when the rule count is varied. Here, it can be observed that the time taken by the incremental approach is independent of the number of rules, where as the time taken for mining increases, though it plateaus after about 60 rules. The overall time taken by the incremental approach is again significantly less. Finally, Figure 3c shows the results when the user-object attribute count is varied. Here, it is observed that the time taken by the incremental approach is again independent of the number of attribute values, whereas the time required for mining increases linearly with it. Figures 4, ​,5,5, and ​and66 give the average running time for deleting a permission, adding an attribute value, and deleting an attribute value respectively. The behavior in all three cases is very similar to that in Figure 3.

Running Time for Add Permission

Running Time for Delete Permission

Running Time for Add Attribute Value

Running Time for Delete Attribute Value

We also looked at the rules generated by our incremental approach and compared them to the rules obtained directly through mining. The experiments show that over the course of all 960 runs, in 598 of the cases, the rules generated are exactly the same, and only in 362 cases are the results different. Furthermore, even in those 362 cases, the number of rules generated by our incremental approach is no more than 3% more than the number of rules obtained directly through mining. This clearly shows that the quality of the results obtained through the incremental approach is very close to that obtained through mining.

To the best of our knowledge, maintenance of ABAC policies has been studied for the first time in this paper. Hence, there are no previous work directly related to this problem. However, there are works in field of ABAC Mining, incremental FD mining and incremental maintenance of databases, which are discussed below.

The standard for ABAC model can be found in [9]. ABAC Mining has been studied by many researchers. Xu.et al. [23] are the first to propose an approach for ABAC Mining. Their approach iterates over tuples in the user-permission relation and constructs candidate rules. Then it generalizes the candidate rule to cover additional tuples by using merging techniques. Medvet et al. [16] have proposed an evolutionary approach that is separate and conquer algorithm, where at every iteration, a new rule is generated and the set of access requests is reduced to a smaller size. The efficiency of this approach is not very different when compared to that in [23]. Mocanu et al. [17] have proposed a deep learning model (Restricted Boltzmann Machines) trained on logs to generate candidate rules. Their system is still under development. Iyer et al. [10] have presented an approach to mine ABAC policies having both positive and negative authorization rules. The approach is based on the rule mining algorithm called PRISM. Gautam et al. [7] have discussed a constrained policy mining algorithm that generates a set of ABAC rules, such that the total weight of all the rules in the mined policy is minimum and no individual rule can have weight greater than a pre-specified constraint. Cotrini et al. [5] have proposed an algorithm for mining ABAC rules from sparse access logs. The algorithm, called Rhapsody, is built upon subgroup discovery algorithm called APRIORI-SD.

Karimi and Joshi [13] have proposed an approach to apply clustering algorithms over the decision examples to predict rules. Karimi et al. [14] have also proposed an unsupervised learning-based technique for detecting patterns in a set of access records and extracting ABAC policy rules from these patterns. They have presented two algorithms, rule pruning and policy refinement that improve quality of mined policy. The latter is useful in ABAC policy maintenance. Bertino et al. [12] have proposed an approach, called Polisma, for learning ABAC policies. It combines data mining, statistical, and machine learning techniques, with potential context information obtained from external sources to learn a better model. Iyer et al. [11] have proposed an algorithm for mining ReBAC policies, and an approach to mine graph transition policies. Gupta et al. [8] have proposed dynamic groups with attribute-based access control model for smart cars ecosystem.

Talukdar et al. [20] have used a subset enumeration approach to discover the ABAC rules in a bottom-up fashion. In this paper, we have chosen to develop our incremental maintenance approach on the ABAC-SRM mining algorithm proposed by [20] as they have shown that they take an order of magnitude less time than [23]. Also, both the algorithms ([20] and [23]) discover almost the same number of rules; whereas [20] has better WSC [18] of the rules than [23]. It is to be noted that the mining approaches in [20] and [23] do not consider unrepresented attribute value combinations [2] as these do not exist in the current authorization set. Better mining algorithms will need to be devised to tackle this issue. However, with respect to maintenance, if an existing user is authorized access to an object with attribute values from unrepresented set, the incremental mining approach can handle this in terms of updating the policy by deleting the previous attribute and adding the new attribute to the user/object. We require the maintenance algorithm to be as fast as possible and to the best of our knowledge, the time results of this algorithm are one of the best. While all the above approaches focus on mining of ABAC policies, none of them attempt to perform incremental maintenance of the policies when changes occur. The idea in [20] is that ABAC rules are nothing but a set of Functional Dependencies. Based on this premise, we have performed a review of incremental FD mining algorithms which also inspired us to develop and implement our approach.

Caruccio et al. [1] represent FDs in a bit-vector. Their approach employs an upward and downward search strategy, and updates the set of Functional Dependencies on addition of new tuples to the database. Wang et al. [21] have proposed to add new set of tuples to the database based on concept of tuple partitions and the monotonicity of the Functional Dependencies and avoid re-scanning of the database. In [22], Wang et al. have also given a Functional Dependency maintenance algorithm which deals with tuple deletion. Also, Gasmi et al. [6] have proposed an algorithm to maintain the canonical Functional Dependencies incrementally when a new tuple is appended to the original database. Our approach is mostly inspired by the work of Schirmer et al.’s DynFD [19]. They maintain Functional Dependencies for a dynamic dataset using a bottom up and top down approach, and indices to evolve the Functional Dependencies. For a batch of operations, insert, update and delete of data, the algorithm adapts its validation data structures, and a positive and negative cover of Functional Dependencies.

Besides the above, incremental maintenance has been studied extensively in data bases. Cheung et al. [3] use incremental updating technique to update the association rules in large databases whenever new transactions are added to the database. Also in [4], Cheung et al. have proposed algorithms for frequent pattern mining in a database and to allow mining in a single pass over the database as well as insertion or deletion of transactions in an efficient manner.

Lin et al. [15] have proposed an efficient incremental algorithm for transaction insertion. The algorithm reduces computations without candidate generation and is based on the utility-list structures.

In this paper, we have examined the problem of maintenance of ABAC policies in an incremental fashion. We have formalized this problem and proposed an efficient algorithm to maintain ABAC policies considering four types of changes. We have experimentally evaluated the performance of the proposed algorithm and showed that it takes significantly less time to perform a change when compared to redoing ABAC mining from scratch.

In the future, we plan to develop an approach that would allow batching of changes and optimally switch between incremental maintenance and re-mining. We plan to study the the consistency and scalability aspects of this approach. We would also like to implement the algorithm for negative authorizations and by adding noise. Also, we plan to implement the ABAC maintenance approach when there are constraints such as mutual exclusion, preconditions, obligations, SoD, attribute-attribute conditions, etc.

ABAC Mining Process

Research reported in this publication was supported by the National Science Foundation awards CNS-1564034, CNS-1624503 and CNS-1747728 and the National Institutes of Health awards R01GM118574 and R35GM134927. The work of Shamik Sural was partially supported by the Fulbright Program. The content is solely the responsibility of the authors and does not necessarily represent the official views of the agencies funding the research.