Analysis of Authorization Constraints via Integer Linear Programming

Abstract

This paper focuses on constraint verification and violation resolution for Petri nets (PNs) modeling of role-based access control (RBAC) policy. Checking the satisfiability of authorization constraints imposes a major challenge when the number of states of a target system is large. To overcome this difficulty, we provide three necessary and sufficient conditions to check three different constraints, namely Separation of Duties (SoDs), Binding of Duties (BoDs), and Constraints of Cardinality (CoCs). The proposed results are based on the solutions of integer linear programming problems (ILPs). By relying on an ILP formulation that does not require the explicit computation of the net reachability set, the proposed approach is particularly well suited for large-size PNs. When the given system does not satisfy a considered constraint, the objective is to propose a suitable violation resolution strategy to correctly enforce the given constraint. In this paper, enforcement of control places and administration of RBAC are presented to solve the SoD, BoD, and CoC violations. All violations can be corrected in a once for all manner while simultaneously ensuring the satisfaction of all other constraints. The comparison between our approach and the existing ones is given to illustrate the effectiveness and efficiency of ours.