Abstract
We introduce the notion of resiliency policies in the context of access
control systems. Such policies require an access control system
to be resilient to the absence of users. An example resiliency
policy requires that, upon removal of any s users, there should
still exist d disjoint sets of users such that the users in each set
together possess certain permissions of interest. Such a policy ensures
that even when emergency situations cause some users to be
absent, there still exist independent teams of users that have the permissions
necessary for carrying out critical tasks. The Resiliency
Checking Problem determines whether an access control state satisfies
a given resiliency policy. We show that the general case of the
problem and several subcases are intractable (NP-hard), and identify
two subcases that are solvable in linear time. For the intractable
cases, we also identify the complexity class in the polynomial hierarchy
to which these problems belong. We discuss the design
and evaluation of an algorithm that can efficiently solve instances
of nontrivial sizes that belong to the intractable cases of the problem.
Finally, we study the consistency problem between resiliency
policies and static separation of duty policies.
