Do algorithms for performing hierarchical permission checking exist?

Question

I have a data structure which represents a hierarchy.

• folder
  • folder
    • folder
    • file
  • file
  • etc.

Permissions are stored in a flat table:

| pKey | type | bitperms |

When performing global operations like search, we need to check permissions recursively within the tree.

Checking permissions inline with the individual leaves of the tree structure is easy. However accounting for permission on the nodes requires one of two known approaches:

• after fetching the filtered leaves, post process each one to check it's parents perms
  • cost is delayed until after
  • there might be lots of initial leaves found, but after processing the parents, nothing remains resulting in useless work being done

• pre calculating all the roots (nodes which grant the permission) ahead of time and using that as a query filter while getting leaves

  • potentially a huge query if many roots exist resulting in excessive time spent processing each leaf

  Do any algorithms exist for doing this in a more efficient way? Perhaps reorganizing the permission data or adding more information to the hierarchy?

  Perhaps adding some heuristics to deal with extremes?

Answer 1

Dunno about a complete paper about that, but here are my thoughts.

1. You obviously need to check at some point the whole path from the leaf to the root.
2. I assume no permission rule introduction from the side (i.e. you're working on a tree, not a general graph).
3. I assume lots of leafs on few "folder" nodes.
4. I also assume that you have a method for including permissions (ORing on a bitmask) or excluding them (NOTANDing on a bitmask).
5. Permissions are mostly granted to roles/groups, not individual users (in the latter case, you'd need to create s.th. like an "ad-hoc role/group" for that user).
6. Permissions will not go up the tree, only down to the leafs.

Then I'd pre-calculate all permissions on folders from the root up and save them along with the folder nodes whenever some permissions on folders change (or a role is added, etc). When a specific file/leaf is called, you only have to check the files/leafs permissions and its folders permissions.

You could also mark some folders as "do not inherit permissions from parent", which may shorten your calculations when the root's permissions change...

This would make it cheap for the following operations:

• checking a leaf's permissions (join leaf and its parent permissions).
• changing the permissions of a folder which does not contain more folders.

Costly are these operations, but since they do not need to work on any leaf/file, they only need to touch a minor part of the whole tree:

• changing/extending the permission model (e.g. by adding a role/group, which might broaden your bitmask, depending on your implementation).
• changing the roots permissions.