Skip to content

Pathfinding

Jump to bottom
Dirk-jan edited this page Dec 4, 2018 · 1 revision

Pathfinding

aclpwn has support for several different pathfinding methods:

  • shortestonly: Only query the shortest path.
  • dijkstra: Use the Dijkstra algorithm for weighed pathfinding (uses REST API, default method).
  • allsimple: Find all possible direct paths (extremely slow, don't use).
  • dijkstra-cypher: Dijkstra algorithm, pure cypher implementation.

The shortest path VS the most efficient path

Neo4j has a few built in pathfinding methods. The simplest one just uses whichever algorithm it considers best to find the shortest path. This is solely based on the number of nodes that it encounters along the way. The shortest path may in our case however not be the most efficient. Consider the following paths:

(USER@TESTSEGMENT.LOCAL)-[MemberOf]->(GROUP@TESTSEGMENT.LOCAL)-[MemberOf]->(ANOTHER GROUP@TESTSEGMENT.LOCAL)-[WriteDacl]->(TESTSEGMENT.LOCAL)

and

(USER@TESTSEGMENT.LOCAL)-[Owns]->(YET ANOTHER GROUP@TESTSEGMENT.LOCAL)-[WriteDacl]->(TESTSEGMENT.LOCAL)

While the second path is shorter, it does require more modifications to reach the end. In the first path, user is already a member of a group that has direct write rights on the domain object. Neo4j will however only consider the second path since this has fewer nodes.

To solve this, we can assign weights to each edge, which is based on the number of modifications we would need to perform. In this, the MemberOf edge has weight 0, since there aren't any modifications required (we are already a member of the specific group and thus have all its privileges). The Owns edge has weight 2, since two modifications are required to add user as a member to the target group: first the DACL needs to be modified to give the user privileges to add itself as member, then in the second step the user is added as a member.

Efficiency

The shortestonly algorithm is the fasted to calculate, but may result in an inefficient path. The Dijkstra algorithm is slightly slower, especially since we need to modify all the relationships in the database to assign the proper weights before we can run it. Since alcpwn cannot know if you made any modifications since you ran the algorithm the last time, it will by default assign the proper weights to edges every time you run the program. If you did not make any modifications since calculating a path the last time you can use the command line parameter --no-prepare to suppress this. On larger databases, preparing the database may crash if neo4j has insufficient memory. Increasing the memory available for neo4j as described on this page should solve this.

Dijkstra implementations

Neo4j has two ways to access the Dijkstra algorithm. The first one is based on the REST API. This API is included by default with Neo4j, but is deprecated and will be removed in a future version. The dijkstra algorithm uses the REST API.

The alternative is to use a cypher procedure which calls the Dijkstra algorithm. This is only possible if you have the neo4j-graph-algorithms plugin installed. To install this, download the jar to the neo4j plugins directory: https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases

Additionally you should add the following configuration line to your $NEO4J_HOME/conf/neo4j.conf file:

dbms.security.procedures.unrestricted=algo.*

This could have security implications so make sure you only do this on a Neo4j database that is not shared or publicly accessible. After you install the plugin and restart neo4j, you can use the dijkstra-cypher algorithm to calculate the most efficient path.

All simple paths

The allsimple algorithm tries to find all the non-circular paths and then performs the length calculation manually. Because of the inefficiency of this algorithm it's use it not recommended and can easily crash Neo4j even on a small domain.

Selecting the shortest path

If you use the shortestonly algorithm, aclpwn.py makes an approximation of which path is the most efficient. However it does not consider the differences between node types, and thus the weights are not as accurate as with the Dijkstra algorithm. You will have to choose the shortest path manually. The Dijkstra algorithm only returns the most efficient paths, and thus only if there are two paths of the same length it will offer a choice.

Clone this wiki locally