Abstract
Separation of Duty (SoD) is widely considered to be a fundamental
principle in computer security. A Static SoD (SSoD) policy states
that in order to have all permissions necessary to complete a sensi-
tive task, the cooperation of at least a certain number of users is re-
quired. In Role-Based Access Control (RBAC), Statically Mutually
Exclusive Role (SMER) constraints are used to enforce SSoD poli-
cies. In this paper, we pose and answer fundamental questions re-
lated to the use of SMER constraints to enforce SSoD policies. We
show that directly enforcing SSoD policies is intractable (coNP-
complete), while checking whether an RBAC state satisfies a set
of SMER constraints is efficient. Also, we show that verifying
whether a given set of SMER constraints enforces an SSoD policy
is intractable (coNP-complete) and discuss why this intractability
result should not lead us to conclude that SMER constraints are not
an appropriate mechanism for enforcing SSoD policies. We show
also how to generate SMER constraints that are as accurate as pos-
sible for enforcing an SSoD policy.
