Specification and enforcement of separation-of-duty policies in role-base access control

Separation-of-duty (SoD) is widely considered to be a fundamental principle to role based access control (RBAC) models and systems should adhere. In this paper, we formulate and study the fundamental problem of SoD policies in the context of RBAC systems. We give a set-based specification of SoD policies and the safety checking problem for SoD policies in the context of RBAC. We study the problem of determining whether a SoD policy is enforceable, and show that directly enforcing SoD policies in RBAC is intractable (coNP-complete). Moreover, indirectly enforcing SoD policies by using mutually exclusive role constraints is also intractable (NP-hard). Therefore, we reduce the safety checking problem for SoD to SAT4J problem which can be solved using available SAT solvers. The experiments show the validity and effectively of the SAT approach.