Role Hierarchies and the Reachability Problem in RBAC

The complaint that motivates role-based access control is specific: discretionary permissions are assigned per user per object, so the permission table grows with the product of users and objects, and no one can answer what a given user can reach without enumerating rows. RBAC replaces the direct user-to-permission edge with two edges through a role, and adds a hierarchy so that roles can inherit from other roles. The structure that results is a partial order, and almost all of the interesting behaviour, including the cost of evaluating it, follows from that.

Users, roles, permissions, and sessions

The core model has three relations. User assignment maps users to roles. Permission assignment maps permissions to roles, where a permission is conventionally an operation on an object, though the standard leaves the definition of the permission set to the implementer. Role inheritance maps roles to roles.

A session is the runtime instantiation: a user activates some subset of the roles assigned to them, and the session’s effective permissions are the union over the activated roles. Activation is not automatic for all assigned roles, and that distinction matters. A user may be assigned both a role that approves a payment and a role that initiates one, while policy forbids holding both active at once; the model permits the assignment and constrains the session.

Because permissions come from roles and roles are activated per session, the effective permission set is a function of three things: the assignment relation, the inheritance relation, and the activation choices. Static analysis can only reason about the first two. Any question about what a user can actually do at a given moment requires knowing which roles they will activate, and that is a runtime decision.

The hierarchy is a partial order, not a tree

Inheritance is reflexive, transitive, and antisymmetric: a role inherits its own permissions, inheritance composes, and two distinct roles cannot each inherit the other. The last property is what makes the structure acyclic. A cycle in the inheritance graph means the roles are equivalent, so implementations either reject the cycle at definition time or collapse the members into one role.

A role that inherits from several parents holds the union of their permissions. This is why the hierarchy is not a tree: the senior role that combines the duties of two junior roles needs edges to both, and the resulting graph is a directed acyclic graph with multiple parents.

The standard distinguishes general hierarchical RBAC, where inheritance depth is unbounded, from limited hierarchies restricted to a depth of one or two. The restriction is not arbitrary. Unbounded depth makes the reachability question more expensive and makes the effective permission set of a senior role depend on distant parts of the graph that the role’s administrator may never have inspected. Depth-limited hierarchies bound both.

Reading permissions downward is one direction; the same edges are read upward to answer which users hold a permission. That upward query is the one that matters for audit: given a permission on a sensitive object, the set of users who can obtain it is the set of users assigned to any role that inherits, directly or transitively, from a role holding the permission.

Reachability and why evaluation cost is not trivial

A naive evaluation walks the inheritance graph from every activated role and collects permissions. With n roles and e inheritance edges, a depth-first walk per role is linear in the reachable subgraph; repeating it for every request and every session makes the cost proportional to the graph’s size times the request rate. Systems that evaluate this way end up caching the transitive closure.

The transitive closure of the inheritance relation is n by n bits, so the storage is quadratic in the number of roles even when the graph is sparse. For a few thousand roles that is a few million bits, which is unremarkable. For a hierarchy with tens of thousands of roles it becomes the dominant structure, and recomputing it after each change is expensive.

The incremental problem is worse than the batch problem. Adding a single inheritance edge changes reachability for every ancestor of the child and every descendant of the parent. Deletion is the harder direction, because determining which pairs of roles were connected only through the removed edge requires either maintaining counts per pair or recomputing the affected region. Systems that treat the closure as derived data and recompute it lazily accept a window in which authorization decisions reflect a stale hierarchy, and that window is a security parameter.

def reachable(role, parents, seen=None):
    """Roles whose permissions role inherits, including itself."""
    seen = set() if seen is None else seen
    stack = [role]
    while stack:
        r = stack.pop()
        if r in seen:
            continue
        seen.add(r)
        stack.extend(parents.get(r, ()))
    return seen

The set returned by such a walk is the permission source set for one activated role. Unioning it across the session’s activated roles gives the effective permission set. Note that the union is over roles, not over permissions directly, because permission assignment may carry attributes that need to travel with the role.

Separation of duty as a constraint layer

Constraints are what turn RBAC from a grouping mechanism into a policy. Static separation of duty forbids a user from being assigned two roles in a conflicting set. Dynamic separation of duty forbids the same roles from being active in one session. Cardinality constraints bound how many users may hold a role, which is how “at least two approvers” is expressed.

The computational character of these constraints differs sharply from reachability. Checking static separation of duty against a candidate assignment is cheap; checking that a whole assignment state satisfies all constraints is equivalent to graph colouring for certain constraint families and is NP-complete in the general case. Implementations therefore restrict the constraint language, most commonly to pairs, which keeps the check polynomial and covers most real policy.

Dynamic constraints are checked per session and are comparatively simple, but they force the authorization decision to depend on session state that must be maintained, invalidated on logout, and re-established on token refresh. A stateless bearer token cannot express dynamic separation of duty unless the token’s claims encode the activated role set and the issuer enforces the constraint at issuance.

Where RBAC strains

Role explosion is the standard failure. When the permission set a population needs varies along several independent dimensions, roles multiply combinatorially, and the hierarchy fills with roles that exist for one team’s exact combination. The usual symptom is a role count in the thousands with most roles assigned to a handful of users.

The deeper problem is that roles are coarse relative to the objects they protect. A role grants an operation on a class of objects; it cannot express “the records belonging to the department this user manages” without a role per department. That requirement pushes toward attribute-based evaluation, covered in the ABAC and policy-engine article, and the two models are usually combined rather than chosen between.

RBAC also has no natural representation for delegation with attenuation. A user who wants to hand a subset of their authority to a deputy for a week must either be assigned a narrower role or be given a mechanism outside the model, which is the problem that capability-based designs address directly.

The remaining practical issue is naming discipline. Since inheritance means permission accumulates upward, a senior role’s effective rights are the union of everything below it, and the role’s name usually reflects only its primary function. Auditing a hierarchy means computing the closure and comparing it against intent, which is the same operation the enforcement path performs at runtime.

The hierarchy also interacts badly with the two directions of review. Revoking a permission from a role removes it from that role and from everything that inherits from it, because the closure is computed from the graph on each evaluation. Nothing removes it from a role that was given the permission by a separate assignment, so a permission granted in three places requires three edits, and the second and third are usually missed. Tools that compute the reverse closure turn that edit into a checklist; tools that do not leave the residue to be discovered by the next audit.