6.1. ACL structures in graphs

This example gives a generic overview of an approach to handling Access Control Lists (ACLs) in graphs, and a simplified example with concrete queries.

Generic approach

In many scenarios, an application needs to handle security on some form of managed objects. This example describes one pattern to handle this through the use of a graph structure and traversers that build a full permissions-structure for any managed object with exclude and include overriding possibilities. This results in a dynamic construction of ACLs based on the position and context of the managed object.

The result is a complex security scheme that can easily be implemented in a graph structure, supporting permissions overriding, principal and content composition, without duplicating data anywhere.

ACL.png

Technique

As seen in the example graph layout, there are some key concepts in this domain model:

  • The managed content (folders and files) that are connected by HAS_CHILD_CONTENT relationships
  • The Principal subtree pointing out principals that can act as ACL members, pointed out by the PRINCIPAL relationships.
  • The aggregation of principals into groups, connected by the IS_MEMBER_OF relationship. One principal (user or group) can be part of many groups at the same time.
  • The SECURITY — relationships, connecting the content composite structure to the principal composite structure, containing a addition/removal modifier property ("+RW").

Constructing the ACL

The calculation of the effective permissions (e.g. Read, Write, Execute) for a principal for any given ACL-managed node (content) follows a number of rules that will be encoded into the permissions-traversal:

Top-down-Traversal

This approach will let you define a generic permission pattern on the root content, and then refine that for specific sub-content nodes and specific principals.

  1. Start at the content node in question traverse upwards to the content root node to determine the path to it.
  2. Start with a effective optimistic permissions list of "all permitted" (111 in a bit encoded ReadWriteExecute case) or 000 if you like pessimistic security handling (everything is forbidden unless explicitly allowed).
  3. Beginning from the topmost content node, look for any SECURITY relationships on it.
  4. If found, look if the principal in question is part of the end-principal of the SECURITY relationship.
  5. If yes, add the "+" permission modifiers to the existing permission pattern, revoke the "-" permission modifiers from the pattern.
  6. If two principal nodes link to the same content node, first apply the more generic prinipals modifiers.
  7. Repeat the security modifier search all the way down to the target content node, thus overriding more generic permissions with the set on nodes closer to the target node.

The same algorithm is applicable for the bottom-up approach, basically just traversing from the target content node upwards and applying the security modifiers dynamically as the traverser goes up.

Example

Now, to get the resulting access rights for e.g. "user 1" on the "My File.pdf" in a Top-Down approach on the model in the graph above would go like:

  1. Traveling upward, we start with "Root folder", and set the permissions to 11 initially (only considering Read, Write).
  2. There are two SECURITY relationships to that folder. User 1 is contained in both of them, but "root" is more generic, so apply it first then "All principals" +W +R → 11.
  3. "Home" has no SECURITY instructions, continue.
  4. "user1 Home" has SECURITY. First apply "Regular Users" (-R -W) → 00, Then "user 1" (+R +W) → 11.
  5. The target node "My File.pdf" has no SECURITY modifiers on it, so the effective permissions for "User 1" on "My File.pdf" are ReadWrite → 11.

Read-permission example

In this example, we are going to examine a tree structure of directories and files. Also, there are users that own files and roles that can be assigned to users. Roles can have permissions on directory or files structures (here we model only canRead, as opposed to full rwx Unix permissions) and be nested. A more thorough example of modeling ACL structures can be found at How to Build Role-Based Access Control in SQL.

The-Domain-Structure-ACL-structures-in-graphs.svg

Find all files in the directory structure

In order to find all files contained in this structure, we need a variable length query that follows all contains relationships and retrieves the nodes at the other end of the leaf relationships.

MATCH ({ name: 'FileRoot' })-[:contains*0..]->(parentDir)-[:leaf]->(file)
RETURN file

resulting in:

file
2 rows

Node[16]{name:"File1"}

Node[14]{name:"File2"}

What files are owned by whom?

If we introduce the concept of ownership on files, we then can ask for the owners of the files we find — connected via owns relationships to file nodes.

MATCH ({ name: 'FileRoot' })-[:contains*0..]->()-[:leaf]->(file)<-[:owns]-(user)
RETURN file, user

Returning the owners of all files below the FileRoot node.

fileuser
2 rows

Node[16]{name:"File1"}

Node[3]{name:"User1"}

Node[14]{name:"File2"}

Node[2]{name:"User2"}

Who has access to a File?

If we now want to check what users have read access to all Files, and define our ACL as

  • The root directory has no access granted.
  • Any user having a role that has been granted canRead access to one of the parent folders of a File has read access.

In order to find users that can read any part of the parent folder hierarchy above the files, Cypher provides optional variable length path.

MATCH (file)<-[:leaf]-()<-[:contains*0..]-(dir)
OPTIONAL MATCH (dir)<-[:canRead]-(role)-[:member]->(readUser)
WHERE file.name =~ 'File.*'
RETURN file.name, dir.name, role.name, readUser.name

This will return the file, and the directory where the user has the canRead permission along with the user and their role.

file.namedir.namerole.namereadUser.name
9 rows

"File2"

"Desktop"

<null>

<null>

"File2"

"HomeU2"

<null>

<null>

"File2"

"Home"

<null>

<null>

"File2"

"FileRoot"

"SUDOers"

"Admin2"

"File2"

"FileRoot"

"SUDOers"

"Admin1"

"File1"

"HomeU1"

<null>

<null>

"File1"

"Home"

<null>

<null>

"File1"

"FileRoot"

"SUDOers"

"Admin2"

"File1"

"FileRoot"

"SUDOers"

"Admin1"

The results listed above contain null for optional path segments, which can be mitigated by either asking several queries or returning just the really needed values.