Search code examples
data-structureshierarchygraph-theoryhierarchical-dataaccess-control

Revokable Discretionary Tree

For my own understanding, I'm writing a Hierarchical Discretionary Access System. It is not DAC, it is more akin to Discretionary RBAC, but those details do not matter for the question at hand.


Each user has a certain Role; each Role has a certain set of permissions.
Each Role is organised in a hierarchical tree-like structure: the role named root has all permissions; child roles of root have a subset of the permission of their parent role.

Schematic views of the above: schematic view


Let's say that a user with the role named manager decides to delegate the permission named set_salary to a user with the role named programmer, who subsequently delegates this permission to the user with the role named intern.

Somebody decides to fire said user with the role named manager. As a result, the role named manager is revoked from said user. What is more, all permissions delegated by said user also need to be revoked.


So my question is:
Is there a data structure which facilitates easy identification of:

  • the chain of permissions delegated by a certain subject within a hierarchical tree structure;
  • whether or not a certain permission has been delegated to a certain subject?
Solution

  • How about an adjacency list ?
    Or in other words, 'a list of linked lists', similar to how we use it in representing graphs.

    Each user can be associated with a delegation linked list.
    A node of the delegation linked list can be of the form <permissionId, userId>, denoting that the owner of the linked list has delegated the permission permissionId to the user userId. Then we can go through the linked list of the user userId and repeat the same process recursively until we find a user whose delegation linked list is empty.

    This algorithm is basically the same as Depth-first search.