2

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?
Anmol Singh Jaggi
  • 8,376
  • 4
  • 36
  • 77
Jacco
  • 23,534
  • 17
  • 88
  • 105
  • Have you looked into ABAC? – David Brossard Mar 10 '16 at 18:05
  • 1
    @DavidBrossard, yeah, I'm aware of ABAC; it is quite fashionable atm. It is however solving a different problem while lacking in auditability. There are, of course, many options for hybrid models. Anyhow, in this case I'm writing my own to deepen my understanding of access systems. – Jacco Mar 10 '16 at 20:22
  • @Jacco It seems that I have completely misunderstood the problem, and my answer makes no sense with respect to the context at all. Am I right? – Anmol Singh Jaggi Mar 12 '16 at 08:51
  • @AnmolSinghJaggi, I'm not sure yet. An adjacency list may be the correct data structure to use, although I'm not sure it will provide easy access to the delegation chain. I'm still working on it and will comment on your answer when I know more. – Jacco Mar 12 '16 at 11:31
  • @Jacco Oh Okay! All the best! – Anmol Singh Jaggi Mar 12 '16 at 12:56

2 Answers2

1

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.

Anmol Singh Jaggi
  • 8,376
  • 4
  • 36
  • 77
  • I used an adjacency list. I'm still not sure it is the best solution, but, in a relational database, it *does* supports cascading constraints; a feature missing when from the [nested sets](https://en.wikipedia.org/wiki/Nested_set_model) solution (which is more *efficient* at querying a subtree), while I don't like the denormalization required by a [closure table](http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree). – Jacco Mar 28 '16 at 19:20
  • That's great Jacco! I'm glad that the answer could be of some use to you. – Anmol Singh Jaggi Mar 28 '16 at 20:52
0

This model can't support delegation of permission per a user like you described for manager -> programmer -> intern situation. Permissions are set for a role and setting new permission for a role effects all users that has that role.

To support permission delegation per a user, new relation is needed that describes delegation. Data needed to describe it is: which user gave permission, which user received permission and permission that is delegated. Like, relation delegatedPermission with columns:

  • giveUserId
  • receiveUserId
  • permissionId
Ante
  • 5,350
  • 6
  • 23
  • 46
  • I'm aware that the current model cannot support delegation; it needs an extra data structure to keep track of the delegation chain. I asked this question to help me find a suitable data structure for the delegation chain which support the requirements as outlined in the OP. – Jacco Mar 14 '16 at 14:50