On the complexity of role updating feasibility problem in RBAC

• We define RUFP to determine whether there exists a valid RP assignment.
• Several subcases of RUFP are solvable in linear time.
• RUFP is intractable (NP-complete) in the general case.

In Role Based Access Control (RBAC) systems, it is necessary and important to update the role–permission assignments in order to reflect the evolutions of the system transactions. However, role updating is generally complex and challenging, especially for large-scale RBAC systems. This is because the resulting state is usually expected to meet various requirements and constraints. In this paper, we focus on a fundamental problem of role updating in RBAC, which determines whether there exists a valid role–permission assignment, i.e., whether it can satisfy all the requirements of the role updating and without violating any role–capacity or permission–capacity constraint. We formally define such a problem as the Role Updating Feasibility Problem (RUFP), and study the computational complexity of RUFP in different subcases. Our results show that although several subcases are solvable in linear time, this problem is NP-complete in the general case.