Access control lists the graph database way

In many contexts you need to handle user permissions to access, create or change some kind of resources. A common example is a file system, and that’s what we are going to dive into in this blog post. We’re going to use Ruby bindings for the Neo4j graph database to create a small – but working – example application.

Preparation

To set up the environment for this example on Ubuntu, I used the following commands:

sudo apt-get install jruby
sudo jruby -S gem install neo4j

To import the libraries, the following code was used:

require 'rubygems'
require 'neo4j'
require 'neo4j/extensions/find_path'

Heading for the node space

So user permissions, what are they all about? Obviously it’s about users, and usually user groups as well. We’ll abstract this away a bit and use the term principals, which can be single users or groups.
The other side of user permissions are the resources which are to be protected. In our case we’ll have a file system, so there will be folders and files. Here we’ll use the term content.
Let’s start out building a graph to support the application from what we have gathered so far! When working with a graph it’s beneficial to think in a graphy manner, so that’s where we’ll begin. Graphs are presumably about connecting things, so our first step is to create some relationships. Neo4j comes with a built-in reference node, which is easily accessible at all times. We use this to create our own “subreference nodes”, one for principals and one for content. This is how our graph looks so far:

To create (and get) the subreference nodes, we use this function:

def get_or_create_sub_ref( name )
  result = Neo4j.ref_node.rels.outgoing( name ).nodes.first
  if ( result.nil? )
    result = Neo4j::Node.new :name => name.to_s.capitalize.gsub("_", " ")
    Neo4j.ref_node.rels.outgoing( name ) << result
  end
  return result
end

This function is then called whenever we need to use a subreference node. The important parts here are:

ref_node: the built-in reference node
rels: relationships connected to a node
outgoing: the direction of the relationship (the relationships are always directed, but you can choose to ignore the direction in traversals)
( name ): the type of relationships to follow (the type can be ignored in traversals as well, but in our case we want to use it)
nodes: the nodes in the other end of the relationships
first: the first node found – there sould only be one subreference node of each type

If the subreference node isn’t found, it will be created and connected to the reference node. As you can see, we’re adding a property with the key name to the nodes as well, which is there solely for the purpose of visualization (the images in this post are created using Neoclipse).

Basic structure

For the principals part, we are going to connect the top-level ones to the corresponding subreference node using a PRINCIPAL type of relationship. Other than that, there’s just users and groups, so let’s use a IS_MEMBER_OF_GROUP relationship type to encode that. This is how that looks in the graph:

And here’s the code to create it:

def new_principal( name, member_of_groups = [] )
  principal = Neo4j::Node.new
  principal[ :name ] = name
  if member_of_groups.empty?
    get_or_create_sub_ref( :PRINCIPALS ).rels.outgoing( :PRINCIPAL ) << principal
  else
    for group in member_of_groups
      principal.rels.outgoing( :IS_MEMBER_OF_GROUP ) << group
    end
  end
  return principal
end

If a new principal isn’t member of any groups, it’s added as a top-level principal, connected to the principals subrefererence node. In other case, it’s simply added to the groups.
With Neo4j all operations on the graph have to be encapsulated in a transaction, so this is how we’ll call the above function:

Neo4j::Transaction.run do
  all_principals = new_principal( "All principals" )
  root = new_principal( "root", [ all_principals ] )
  regular_users = new_principal( "Regular users", [ all_principals ] )
  user1 = new_principal( "user1", [ regular_users ] )
  user2 = new_principal( "user2", [ regular_users ] )
end

For the content part, things are very similar to the principals part. The main difference is that in this case, an item can have only a single parent item. Here’s the graphical view on that:

And this is the code to create the structure:

def new_content( name, parent = nil )
  content = Neo4j::Node.new
  content[ :name ] = name
  if ( parent.nil? )
    get_or_create_sub_ref( :CONTENT_ROOTS ).rels.outgoing( :CONTENT_ROOT ) << content
  else
    parent.rels.outgoing( :HAS_CHILD_CONTENT ) << content
  end
  return content
end

Similar to how the principals were created, this is the code to create the content data:

Neo4j::Transaction.run do
  root_folder = new_content( "Root folder" )
  temp_folder = new_content( "Temp", root_folder )
  home_folder = new_content( "Home", root_folder )
  user1_home_folder = new_content( "user1 home", home_folder )
  user2_home_folder = new_content( "user2 home", home_folder )
  a_file = new_content( "MyFile.pdf", user1_home_folder )
end

At the core

Now that we have the basic structure in place, what’s left regarding our data is a small but crucial part: the permissions information! We’re using a simple scheme: adding security relationships with optional boolean flags for read and write permission. Not much to say here, this is what we want the full graph to look like (click for a bigger version):

A small function will help us add the security information:

def apply_security( content, principal, map_with_flags )
  security_relationship = Neo4j::Relationship.new( :SECURITY, principal, content )
  map_with_flags.each_pair {|key, value| security_relationship[ key ] = value}
end

It’s time to add the security data:

Neo4j::Transaction.run do
  apply_security( root_folder, root, { "w" => true } )
  apply_security( root_folder, all_principals, { "r" => true } )
  apply_security( temp_folder, all_principals, { "w" => true } )
  apply_security( user1_home_folder, regular_users, { "r" => false, "w" => false } )
  apply_security( user1_home_folder, user1, { "r" => true, "w" => true } )
  apply_security( user2_home_folder, user2, { "r" => true, "w" => true } )
end

To check the permission for some action by an actual principal for some content, there’s some work to do. This is the algorithm we use to retrieve a permission flag:

Move from the content node and upwards through the file system structure and investigate each level for permission information.
On each level, see if there are any principals related to or identical with the principal concerned.
Make sure to use the permission information from the principal closest to the principal concerned.
If permission information was found, return it; otherwise, continue traversing to the next level in the file system.

In the code for this, we’ll use a function named depth_of_principal() to calculate the distance between the principal we have traversed to and the principal concerned. More on that later, here’s the code to check the permissions:

def has_access( content, principal, flag )
  for current_content in content.incoming( :HAS_CHILD_CONTENT ).depth( :all )
    lowest_score = nil
    lowest_modifier = nil
    for rel in current_content.rels.incoming( :SECURITY )
      rel_principal = rel.start_node
      if !rel[ flag ].nil?
        score = depth_of_principal( rel_principal, principal )
        if !score.nil?
          modifier = rel[ flag ]
          if lowest_score.nil? || score < lowest_score ||
            ( score == lowest_score && modifier )
            lowest_score = score
            lowest_modifier = modifier
          end
        end
      end
    end
    if !lowest_modifier.nil?
      return lowest_modifier
    end
  end
  return false
end

Here’s our function to check the distance between principals (and to see if they’re on the same path at all).

def depth_of_principal( principal, reference_principal )
  result = reference_principal.outgoing( :IS_MEMBER_OF_GROUP ).depth( :all ).path_to( principal )
  return result.nil? ? nil : result.size
end

Finally, we want to see that everything works, so here’s a utility function to print permission information:

def print_has_access( content, principal, flag )
  print principal[ :name ] + " +" + flag.upcase + " access to " + content[ :name ] + "? " +
    has_access( content, principal, flag ).to_s + "n"
end

And here’s how to use the function:

Neo4j::Transaction.run do
  print_has_access( home_folder, root, "w" )
  print_has_access( home_folder, user1, "w" )
  print_has_access( a_file, root, "r" )
  print_has_access( a_file, user2, "r" )
  print_has_access( a_file, user1, "w" )
end

Next steps

The full source code is found here
Here’s a few useful resources to help you on your way:

Thanks for reading – any feedback is welcome!

Want to learn more about graph databases? Click below to get your free copy of O’Reilly’s Graph Databases ebook and discover how to use graph technologies for your application today.

Download My Ebook