Re: ACL schema with Neo4j, data in MySQL/MongoDB

[Benjamin Makus]

I now decided to use Neo4j as my main DB, this will simplify ACL stuff very much.

So here's my basic schema:

node User {
  String username
}

node Role {
  String name
}

relationship MEMBER_OF { }

relationship PARENT_OF { }

relationship HAS_PERMISSION {
  boolean read
  boolean update
  boolean delete
  boolean ...
}

• Each User can be MEMBER_OF many roles.
  
• Each User can have a HAS_PERMISSION relation to every other node (i.e. Article, Event, ...).
  
• Each Role can have a HAS_PERMISSION relation to every other node (i.e. Article, Event, ...).
  
• Each HAS_PERMISSION relation defines what is allowed and what's not allowed. This can be different actions dependent on the node, i.e. Article has an "addComment" and a "publish" Permission, whereas Event doesn't have those Permissions.
  
• Each secured node can have a PARENT_OF relation to another node, but for example Article will never have a parent, because it's always at root level of my application.

This approach looks very flexible, but I'm stuck with the queries... I had a look at your ACL example, here: http://docs.neo4j.org/chunked/stable/examples-acl-structures-in-graphs.html

1. Reference Node?
• Is there any reason to use a Reference Node instead of Labels?
2. Query #1:
• Input: User node u, some secured Node s
• Query: Find the first HAS_PERMISSION relation, that connects u and s
• Returns: the HAS_PERMISSION relation
• I thought about using shortestPath(), but that doesn't fit in all situations.
3. Query #2:
• Input: User node u, some Label l, a Permission p
• Query: Find all nodes, labeled with Label l, where User u is somehow related to via HAS_PERMISSION and HAS_PERMISSION has Permission p set to true
• Returns: List of nodes, labeled with Label l

Basically both queries can use a similar algorithm, but I need some kind of precedence in it, so it will find the right HAS_PERMISSION relation. It's like:

1. User takes precedence over Role
2. Secured Node takes precedence over its parent

This means: If I have a graph, where

• User u has Write Access to the Parent p of Secured Node s
• Some Role r of the User u has only Read Access to Secured Node s

Then the User u will have write access to Secured Node s, because it has to match the Users permissions first.

And there's another scenario:

• User's Role r1 has Write Access = false for Secured Node s
• User's Role r2 has Write Access = true for Secured Node s

Then of the write access must be granted.

Sorry for this huge post, but I can't figure out how to do that...

[Michael Hunger]

Hi Benjamin,

how about setting up your example as  a graph gist (gist.neo4j.org) with a tiny sample dataset?

Am 14.07.2014 um 15:28 schrieb Benjamin Makus <benn...@gmail.com>:

I now decided to use Neo4j as my main DB, this will simplify ACL stuff very much.

So here's my basic schema:

node User {
  String username
}

node Role {
  String name
}

relationship MEMBER_OF { }

relationship PARENT_OF { }

relationship HAS_PERMISSION {
  boolean read
  boolean update
  boolean delete
  boolean ...
}


• Each User can be MEMBER_OF many roles.
  
• Each User can have a HAS_PERMISSION relation to every other node (i.e. Article, Event, ...).
  
• Each Role can have a HAS_PERMISSION relation to every other node (i.e. Article, Event, ...).
  
• Each HAS_PERMISSION relation defines what is allowed and what's not allowed. This can be different actions dependent on the node, i.e. Article has an "addComment" and a "publish" Permission, whereas Event doesn't have those Permissions.
  
• Each secured node can have a PARENT_OF relation to another node, but for example Article will never have a parent, because it's always at root level of my application.

This approach looks very flexible, but I'm stuck with the queries... I had a look at your ACL example, here: http://docs.neo4j.org/chunked/stable/examples-acl-structures-in-graphs.html

1. Reference Node?
• Is there any reason to use a Reference Node instead of Labels?

Use Labels

2. Query #1:
• Input: User node u, some secured Node s
• Query: Find the first HAS_PERMISSION relation, that connects u and s
• Returns: the HAS_PERMISSION relation
• I thought about using shortestPath(), but that doesn't fit in all situations.

MATCH path = shortestPath((u:User {username:{name}})-[:HAS_PERMISSION*]->(s:Article {id:{articleId}))

RETURN path

3. Query #2:
• Input: User node u, some Label l, a Permission p
• Query: Find all nodes, labeled with Label l, where User u is somehow related to via HAS_PERMISSION and HAS_PERMISSION has Permission p set to true
• Returns: List of nodes, labeled with Label l

MATCH (u:User {username:{name}})-[:HAS_PERMISSION {read:true}*]->(node:Label)

RETURN n

I'd probably change the HAS_PERMISSION.permission to

CAN_READ

CAN_WRITE

CAN_PUBLISH

CAN_DELETE

for performance and clarity reasons.

Basically both queries can use a similar algorithm, but I need some kind of precedence in it, so it will find the right HAS_PERMISSION relation. It's like:

What does "first" mean ?

1. User takes precedence over Role
2. Secured Node takes precedence over its parent

This means: If I have a graph, where

• User u has Write Access to the Parent p of Secured Node s
• Some Role r of the User u has only Read Access to Secured Node s

Then the User u will have write access to Secured Node s, because it has to match the Users permissions first.

Don't you ask for a certain permission in the first place?

You could filter paths after the fact or order them by the number of roles and parents (and minimize that number) ?

return path, 

length(FILTER (n in nodes(path) WHERE n:Role)) as roles,

length(FILTER (n in nodes(path) WHERE (n)<-[:PARENT_OF]-() )) as parents

order by roles + parents asc

And there's another scenario:

• User's Role r1 has Write Access = false for Secured Node s
• User's Role r2 has Write Access = true for Secured Node s

Then of the write access must be granted.

this would be easier with the CAN_WRITE relationship which then wouldn't exist in your case 1

Otherwise you have to filter them out, that's why you'd only look for paths with -[:HAS_PERMISSION {write:true}]->

Sorry for this huge post, but I can't figure out how to do that...

No worries, happy to help. Please write it up as a graphgist, this will definitely be helpful to others too. (If you need help with that ping me).

Michael

--
You received this message because you are subscribed to the Google Groups "Neo4j" group.
To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Benjamin Makus]

Thanks for your answer. I'll try to clarify things a bit.

First I created an ACL CHEAT SHEET: http://www.docdroid.net/er3w/acl-cheat-sheet.pdf.html

There you can see lot's of different scenarios. The "= +r" and "= -r" behind the Obj-Nodes show what's the resulting permission for this Object. ("= -r" means: no read permission, "= +r" means: read permissions granted)

Obj-Nodes are basically arbitrary Nodes which should be secured via ACL.

For retrieving the correct Permission there are basically just a few rules (order is important!):

1. User has a direct Permission relation to the Object
2. User has a direct Permission relation to the Object's parent (or parent of parent of parent of p.......)
3. User has a role(s) with direct relation to the Object
1. Take the first Role in every role subtree of the User
   
2. Remove those Roles, which are parents of other matching roles
3. If there's any Role left which grants Permission, take it!
4. User has a role(s) with direct relation to the Object's parent (or parent of parent of parent of p.......)
1. Again the same as above: Have a look at each role subtree, etc.

In other words:

• A Permission relation that comes directly from the User has precedence. It overrides everything the Roles allow/forbid.
• This is also true, if the User has a Permission relation, which points at a parent of the Object.
• If (and only if) there's no Permission relation from the User to the object or one of his parents, then we must have a closer look at the roles.
• If two equal roles (means: in 2 different subtrees) have a Permission relation to the object or one of its parents, then grant the permission if any of these roles grants it.

Shortest Path?

• No :(
• It doesn't always fit. Especially if there's something like:
• User is MEMBER_OF Role3
• User is MEMBER_OF Role2, and Role2 is MEMBER_OF Role1
• Role3 does not grant READ Permissions to Object
• Role1 does grant READ Permissions to Object
• Shortest Path would be to use Role3, but that's not the correct way. As said above: Have a look at both sub-trees (1. Role3, 2. Role2+Role1). And take the first role of each subtree that has a Permission relation (1. Role3, 2. Role1). And then return true if any of these Roles grant the Permission. Role1 does grant it, though return true :)

Background:

1. User1 puts User2 on his "ignore list":
• User2 has some basic role which allows him to read every other Users profile
• But now there's a direct Permission relation from User1 to User2, which says: Not allowed to read this!
2. User1 should be allowed to edit User2's Article:
• The basic role says: Users can only read Articles and create new ones. The creator is the only one that can edit it.
• Now User2 wants User1 as his co-author, so he can give him permission to edit this article.

I altered the ACL design a little bit:

• It's now possible to override just a single permission, i.e.:
• User1 is MEMBER_OF Role2 and Role2 is MEMBER_OF Role1
• Role1 {read: false, write:false}
• Role2 {read: true} -> it inherits the write property from Role1 and overrides the read property
• User {write: true} -> it inherits the read property from Role2 and overrides the write property
• There's room for design changes, if that affects performance in a positive way :)

Performance questions:

• Your suggestion was to use a relation for every possible permission, but how can I "ungrant" Permissions that way? I must be able to say: "Role2 is MEMBER_OF Role1, so it inherits all of Role1's permissions, but Role2 should not be allowed to have write access". With my suggested design, I'd just say: "Role2 {write: false} MEMBER_OF Role1".
• I understand that it's faster to just have a look, if "CAN_READ" exists, instead of having a look at the relation properties. But I'm really unsure, if I can build the desired system that way. Maybe there's another neat way to handle this? Or maybe even some Neo4j feature I'm not aware of?

Again, thank you for your help! If I get this system running, I'll build a small Spring / Spring Security app with it and put it on Github for everyone :-)

Btw: I had a look at Graph Gist, it's really amazing. I played a bit with it. And in a few hours, I'll put an example online which will cover all the examples from my ACL CHEAT SHEET.

[Benjamin Makus]

So... here is the Graph Gist: http://gist.neo4j.org/?github-benneq%2Fgists%2F%2Fmeta%2FSimple.adoc

And the PDF (from the previous post): http://www.docdroid.net/er3w/acl-cheat-sheet.pdf.html

The permission resolution algorithm:

1. Look if the User has a direct Permission relation to the Object
2. Look if the User has a relation to some parent of the Object (find first parent in the hierarchy)
3. Look at the Roles (here it get's a bit complicated):
• Find all Permission relations from a Role to the Object and its parents.
• If one of these Permission relations says "true", return "true, else return "false"

Example #1:

• User has a Permission relation to the Object
• Group (where user is member of) has Permission relation to the Object
• -> Take the Permission relation of the User

Example #2:

• User has a Permission relation to one (or more) of the Object's parents
• Some of the User's Groups has a direct Permission relation to the Object
• -> Ignore the Group permissions! Take the Permission relation between the User and the closest found parent of the Object

Example #3:

• User has no Permission relation to the Object or one of its parents
• Any of the User's Groups have a direct Permission relation to the Object
• -> Return "true", if some of the Group's Permission relations says "true", else return "false"

Example #4:

• User has no Permission relation to the Object or one of its parents
• Some of the User's Groups have a direct Permission relation to the Object and some have a direct relation to any of the Object's parents
• -> Return "true", if some of the Group's Permission relations says "true", else return "false"

Example #5:

• User has no Permission relation to the Object or one of its parents
• There's no direct Permission relation from any of the User's Groups to the Object and but some have a direct relation to any of the Object's parents
• -> Return "true", if some of the Group's Permission relations says "true", else return "false"

I hope, now the requirements are clear :)

[Benjamin Makus]

I've now written parts of the query, but I can't get a few things working. It's basically this:

IF(
       MATCH
               (u:User {name:'U1'})-[r:HAS_PERMISSION]->(o:Object {name:'O1'})
       RETURN r.READ
) ELSE IF (
       MATCH
               (u:User {name:'U1'}),
               (o:Object {name:'O1'}),
               u-[r:HAS_PERMISSION]->()-[:PARENT_OF*]->o
       RETURN r.READ
) ELSE (
       MATCH
               (u:User {name:'U1'}),
               (o:Object {name:'O1'}),
               u-[*]->(v:Role)-[r:HAS_PERMISSION]->o
       RETURN r.READ
)

I don't know how to express IF-ELSE with Cypher. I know, I can do CASE inside the return, but I can't figure out how to combine that with my query...

The IF-ELSE Blocks:

1. The first IF-Block is working as expected :)
   
2. The second Block is missing a "shortestPath" statement, but I don't know how to do the following:
• Return the "r:HAS_PERMISSION" relation of the shortest path (respectively its "READ" property)
3. The third Block is still missing a lot of code, but that can be resolved later.

The second block should more looks like:

MATCH
       (u:User {name:'U1'}),
       (o:Object {name:'O1'}),
       s = shortestPath(u-[r:HAS_PERMISSION]->()-[:PARENT_OF*]->o)
RETURN r.READ

But it seems, like it's not possible to use "r:HAS_PERMISSION" within the shortestPath

I also thought about combining Block 1 and 2, but I was not able to figure out, how to an optional node with optional relation within the query, i.e.:

MATCH
    (u:User {name:'U1'}),
    (o:Object {name:'O1'}),
    s = shortestPath(
      u-[r:HAS_PERMISSION]
      OPTIONAL ->()-[:PARENT_OF]
      ->o
    )
RETURN r.READ

And again, as stated above: The shortestPath stuff is not working, because i cannot name new nodes/relations with in this function.

Would be really cool, if someone can give me a hint how to get this working :)

Thank you!