Let's say you have a permission system with which you can specify things like: user U is a member of group A, which is a subgroup of group B, which is a subgroup of group C, and all members of group C have access to object O. Then, you can query the system like: "does user U have access to object O"?

As far as I can tell, this is a reachability problem, where the vertices are users, groups, and objects, and an edge implies direct access. However, I don't think that most large-scale permission systems frame this as a reachability problem because the only fast reachability algorithms are restricted to planar graphs.

How are these systems usually designed?

  • 1
    I know that SAP evaluates and folds all intermediate levels at the moment of logon for a user. During his session, this static map is used for authorization checks. Now this was designed like 25 years ago; I couldn’t say if it is still considered a state-of-the-art approach.
    – Aganju
    Commented Feb 18, 2018 at 21:56
  • Are these systems typically designed using micro-optimization approach (making the core computational task fast), or algorithm approach (exploiting advanced CS theories that typical software programmers don't know), or cache-invalidation approach (caching the results, meanwhile having a robust mechanism for knowing when to invalidate)? Also, what would be the typical "orders of magnitude" for the numbers (instances) of users, groups, and objects? Is the access control implemented centrally (on one machine) or distributed? etc.
    – rwong
    Commented Feb 19, 2018 at 1:11
  • I can't comment on what real large scale systems tend to use in this context, but my suspicion is that they generally use a fairly naive approach, because even large systems generally have a relatively flat hierarchy with users having only a few groups and groups having only a few super-groups, which means that either depth-first search or Dijkstra's algorithm can run over the entire graph reasonably quickly (and if allowed to completely traverse it the results can be cached, which results in basically the same algorithm @Aganju mentions SAP using).
    – Jules
    Commented Feb 19, 2018 at 10:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.