What is the best way to adapt this security system to deal with multiple inheritance?

Question

Strap yourselves in, this is a tricky question.

We have a system that deals with big datasets. (million to billion records per table big). All the data is handled in a tree structure of nodes.

We are using Symfony2, and the Symfony2 security system (Domain Objects, Acls, Aces etc). Our Acl tree mirrors our node tree.

To coin some language:

• DP Defined permission, ie an ace record on this acl node
• EP Effective permission, no ace record, permission inherited from a parent with a DP

Business logic wise, we assign 0 or 1 ace to an object per user, and rely on inheritance where there is none. Root > lvl1 (DP: VIEW) > lvl2 > lvl3 (EP: VIEW)

So far, so good. This all works.

Some nodes not only have a parent, but are associated to other nodes (many to many). When a node is associated to another node, this represents a separate path up the tree for acls to follow. IE we would have 1 or many paths up the tree to root to gather ace's.

Leaf < Parent < GrandParent < Root
Leaf < AssociatedNode < AssociatedNodeParent < AssociatedNodeGrandParent < Root
 ...

Or logic for managing the voting of the aces is fine, what we are unsure of is how to represent the multiple paths up the tree. Our current (read: bad) ideas are:

• Multiple parent behaviour in the acl tree
  • Pros
    • Seems cleaner?
  • Cons
    • Almost entire rewrite of the security system to put this in.
    • Potential ratsnesting.
• Duplicate object identities / acls against entities, specifying different parents.
  • Pros
    • Er...
  • Cons
    • Will create a very large amount of acl records potentially.
    • Hard to manage in code.

Answer 1

In your multiple parent case, you effectively have an inverse tree traversal from your initial node to any node that contains an ace. So, if we visualize the upwards and side traversal operations as their own tree (pruning loops), you could, potentially, search your entire node network before you find an ace in the worst case.

The easiest way to resolve this would be to guarantee some form of a heap property that ensures each node with an ace has a large or small value that can drive the traversal. This takes the traversal time down from worst case O(n) (if you searched every node in your database index) to O(log n) as you backpath through the network.

The reason why getting O(1) traversal here is difficult is your node network guarantees the possibility of loops. But, if you construct an ACL graph maintaining the properties of, for example, a min heap, you should be okay.

Best of luck with your permissions model.

Answer 2

Again, as noted, this is an interesting, but non-trivial problem -- thanks! Now I know how I have to spend this weekend :-) I might consider the heap idea as well, but I'd make it a threaded heap. Each node in the heap contains a pointer to a ACL "index" if you will.

Assume I have just three nodes in the example (R(oot), P(aren't) and N(ode)). Thus, the ACL set for N is ACL(R)+ACL(P)+ACL(N). Assume that when a node is created, that node contains a pointer X that points to a node index. So R(X) = ACLIndex(R). No node itself actual contains it's ACL.

Now, for a given node N, I still have to chase from the root in worst case, but I'm simply hopping around a flat index to do it rather than bouncing all over the tree. It would be better if you could make the assertion that for a given node N, there is only one path to N, or, if there are multiple paths, N keeps another table of traversals such that, for N, Path(N) from node A is listened in that table. In effect, you have to leave breadcrumbs in N when a node attaches to it.

I'm wondering if we can borrow a concept from geolocation. It's not possible for your little handheld GPS to keep all possible shortest-path routes from any point to any point, and keep traffic times in mind. It cheats and divides the maps into "tiles" Since you can't be all over the map at the same time, but rather, you are limited to a tile you're currently in, it only needs to compute the shortest paths from within that tile to its known exists. Once you take an exit, it loads that tile and repeats. In effect, we use the principle of locality to reduce the scope.

What if we used the same idea? For a given node, if you divided the access tree into "shards", you could pre-compute the costs or at least update them, and then the path cost from R to N is simply the sum of the shard costs plus the path cost in your local shard.