Supporting user authorization queries in RBAC systems by role-permission reassignment

The User Authorization Query (UAQ) Problem is a key issue related to efficient handling of users' access requests in Role Based Access Control (RBAC) systems. However, there may not exist any solution to a given UAQ problem due to the limitation caused by the current system state, because missing any requested permission may thwart a task, while an extra permission may bring an intolerable risk to the system. Hence, update of the role-permission assignment is needed to support the feasibility of an UAQ problem. In this paper, we study fundamental problems related to role-permission reassignment, including the RVP problem the goal of which is to determine whether a given role-permission assignment satisfies all reassignment objectives and does not violate any prerequisite constraint or permission-capacity constraint, the RFP problem which verifies whether there exists a valid role-permission assignment, and the RGP problem which studies how to generate a valid role-permission assignment. We present the computational complexity analysis of RVP, RFP and RGP, showing that RVP is solvable in linear time, while both RFP and RGP are NP-hard. We also propose an approach for RGP, which incorporates a preprocessing to decrease the size of the problem, and reduce it to an SAT problem. Finally, experimental results show the validity and effectiveness of our proposed approach.