Relationship-Based Access Control

In the previous two lessons, S7 was decided wrong. U-1001 had shared reading list number nine with U-1002; U-1002 should have been able to see that list. Neither the role-based model nor the attribute-based model could express this, because sharing is a property of neither the subject nor the object — it is the link between the two.

Relationship-based access control turns these links into first-class data. The subjects and objects in the system become the nodes of a graph, and the links between them become named edges. The access question turns into a reachability query over this graph: can the subject reach the object by following a specific sequence of edges?

The Graph, Edges, and Path Patterns

The library loan service’s relationships can be written with a small number of edge types. owner links a member to their own record. belongsTo links a record to its branch. worksAt and manages link staff to their branch. sharedWith links a list to the person or group it is shared with. memberOf links a person to a group.

An access rule is a path pattern made of these edges. The rule “can view its own loan record” is a one-step pattern: owner. The rule “branch staff can view their branch’s records” is a two-step pattern, and the second step follows the edge in reverse: from staff to branch via worksAt, from branch to record via the reverse of belongsTo.

The evaluator below runs these patterns. At each step it moves from one set of nodes to the neighboring set; this is the edge-type-filtered form of the breadth-first search from the Data Structures course.

cat > rebac.mjs <<'EOF'
const EDGES = [                         // [source, relation, target]
  ["U-1001", "owner", "loan:501"], ["U-1002", "owner", "loan:502"],
  ["U-1005", "owner", "loan:503"], ["U-1001", "owner", "list:9"],
  ["loan:501", "belongsTo", "S-02"], ["loan:502", "belongsTo", "S-02"],
  ["loan:503", "belongsTo", "S-01"], ["fine:77", "belongsTo", "S-02"],
  ["P-2001", "worksAt", "S-02"], ["Y-3001", "manages", "S-02"],
  ["list:9", "sharedWith", "U-1002"], ["list:9", "sharedWith", "group:reading-club"],
  ["U-1006", "memberOf", "group:reading-club"],
];

// A "~relation" in a pattern means the edge is followed in reverse.
const PATTERNS = {
  "view:loan":   [["owner"], ["worksAt", "~belongsTo"], ["manages", "~belongsTo"]],
  "update:loan": [["worksAt", "~belongsTo"], ["manages", "~belongsTo"]],
  "create:loan": [["worksAt", "~belongsTo"], ["manages", "~belongsTo"]],
  "delete:loan": [["manages", "~belongsTo"]],
  "delete:fine": [["manages", "~belongsTo"]],
  "view:list":   [["owner"], ["~sharedWith"], ["memberOf", "~sharedWith"]],
};

function step(nodes, relation) {
  const reversed = relation.startsWith("~");
  const name = reversed ? relation.slice(1) : relation;
  const result = new Set();
  for (const [s, r, t] of EDGES) {
    if (r !== name) continue;
    if (!reversed && nodes.has(s)) result.add(t);
    if (reversed && nodes.has(t)) result.add(s);
  }
  return result;
}

function rebac(subject, action, object) {
  for (const pattern of PATTERNS[`${action}:${object.split(":")[0]}`] ?? []) {
    let frontier = new Set([subject]);
    for (const relation of pattern) frontier = step(frontier, relation);
    if (frontier.has(object)) return [true, pattern.join(" -> ")];
  }
  return [false, "no reachable path"];
}

const SCENARIOS = [
  ["S1", "U-1001", "view",   "loan:501", true],
  ["S2", "U-1001", "view",   "loan:502", false],
  ["S3", "P-2001", "view",   "loan:502", true],
  ["S4", "P-2001", "view",   "loan:503", false],
  ["S5", "P-2001", "update", "loan:502", false],
  ["S6", "Y-3001", "delete", "fine:77",  true],
  ["S7", "U-1002", "view",   "list:9",   true],
  ["S8", "U-1005", "view",   "list:9",   false],
];

console.log("scenario | ReBAC | expect | match | path found");
console.log("---------|-------|--------|-------|--------------------------");
let matched = 0;
for (const [name, subject, action, object, expected] of SCENARIOS) {
  const [decision, path] = rebac(subject, action, object);
  if (decision === expected) matched++;
  console.log(`${name}       | ${(decision ? "allow" : "deny").padEnd(5)} | ` +
    `${(expected ? "allow" : "deny").padEnd(6)} | ${(decision === expected ? "+" : "-").padEnd(5)} | ${path}`);
}
console.log(`\nReBAC correct decisions: ${matched}/${SCENARIOS.length}`);

console.log("\ntransitive access (outside the common set):");
for (const code of ["U-1006", "U-1005"]) {
  const [decision, path] = rebac(code, "view", "list:9");
  console.log(`  ${code} -> list:9 : ${decision ? "allow" : "deny"}  (${path})`);
}
EOF
node rebac.mjs

scenario | ReBAC | expect | match | path found
---------|-------|--------|-------|--------------------------
S1       | allow | allow  | +     | owner
S2       | deny  | deny   | +     | no reachable path
S3       | allow | allow  | +     | worksAt -> ~belongsTo
S4       | deny  | deny   | +     | no reachable path
S5       | allow | deny   | -     | worksAt -> ~belongsTo
S6       | allow | allow  | +     | manages -> ~belongsTo
S7       | allow | allow  | +     | ~sharedWith
S8       | deny  | deny   | +     | no reachable path

ReBAC correct decisions: 7/8

transitive access (outside the common set):
  U-1006 -> list:9 : allow  (memberOf -> ~sharedWith)
  U-1005 -> list:9 : deny  (no reachable path)

S7 is solved for the correct reason for the first time in three lessons: a sharedWith edge runs to the list from U-1002. S8 is denied by the same pattern, because no edge runs to U-1005.

The last two lines show the model’s real strength. U-1006 is not directly linked to the list; it is a member of the reading club group, and the list is shared with that group. The two-step path establishes this link. In the attribute-based model, reaching the same result would have required copying every member of the group into the object’s attribute field and updating that copy every time the group changes. In the graph, group membership is a single edge, and adding the edge affects every list at once.

Where the Model Falls Short

S5 is wrong in this model. Loan records not being updated outside business hours is a context constraint, and the graph has no counterpart for it — time is not an edge between two nodes.

This is the mirror image of the previous lesson. The attribute-based model could see context but not relationships; the relationship-based model can see relationships but not context. The two models’ gaps do not overlap — they complement each other. This observation is the starting point for the next lesson.

Two Separate Questions, and Their Costs

Two different questions are asked in the relationship-based model, and their costs are not the same.

The first is a check: “can this subject reach this object?” The moment an answer is found, the search stops. The second is a listing: “which objects can this subject reach?” This question is needed to render a list page, and it requires running every pattern to completion.

cat > rebac-cost.mjs <<'EOF'
const EDGES = [
  ["U-1001", "owner", "loan:501"], ["U-1002", "owner", "loan:502"],
  ["U-1005", "owner", "loan:503"], ["U-1001", "owner", "list:9"],
  ["loan:501", "belongsTo", "S-02"], ["loan:502", "belongsTo", "S-02"],
  ["loan:503", "belongsTo", "S-01"], ["fine:77", "belongsTo", "S-02"],
  ["P-2001", "worksAt", "S-02"], ["Y-3001", "manages", "S-02"],
  ["list:9", "sharedWith", "U-1002"], ["list:9", "sharedWith", "group:reading-club"],
  ["U-1006", "memberOf", "group:reading-club"],
];
const PATTERNS = {
  "view:loan": [["owner"], ["worksAt", "~belongsTo"], ["manages", "~belongsTo"]],
  "view:list": [["owner"], ["~sharedWith"], ["memberOf", "~sharedWith"]],
};

let edgeReads = 0;
function step(nodes, relation) {
  const reversed = relation.startsWith("~"), name = reversed ? relation.slice(1) : relation;
  const result = new Set();
  for (const [s, r, t] of EDGES) {
    edgeReads++;
    if (r !== name) continue;
    if (!reversed && nodes.has(s)) result.add(t);
    if (reversed && nodes.has(t)) result.add(s);
  }
  return result;
}

const walk = (subject, pattern) => {
  let frontier = new Set([subject]);
  for (const relation of pattern) frontier = step(frontier, relation);
  return frontier;
};

function check(subject, permission, object) {     // stops at the first matching pattern
  for (const pattern of PATTERNS[permission] ?? []) if (walk(subject, pattern).has(object)) return true;
  return false;
}

function accessible(subject, permission) {         // all patterns are walked
  const all = new Set();
  for (const pattern of PATTERNS[permission] ?? []) for (const d of walk(subject, pattern)) all.add(d);
  const type = permission.split(":")[1] + ":";
  return [...all].filter((d) => d.startsWith(type)).sort();
}

console.log("single-object check (stops at the first matching pattern):");
for (const [subject, object] of [["P-2001", "loan:502"], ["U-1001", "loan:501"],
                             ["U-1005", "loan:502"]]) {
  edgeReads = 0;
  const k = check(subject, "view:loan", object);
  console.log(`  ${subject} -> ${object} : ${(k ? "allow" : "deny").padEnd(5)} ` +
    `(${String(edgeReads).padStart(2)} edge reads)`);
}

console.log("\nlist of accessible objects (all patterns are walked):");
for (const [subject, permission] of [["P-2001", "view:loan"], ["U-1001", "view:loan"],
                            ["U-1006", "view:list"], ["U-1005", "view:list"]]) {
  edgeReads = 0;
  const list = accessible(subject, permission);
  console.log(`  ${subject} ${permission.padEnd(16)} -> [${(list.join(", ") || "empty").padEnd(22)}]` +
    ` (${edgeReads} edge reads)`);
}
EOF
node rebac-cost.mjs

single-object check (stops at the first matching pattern):
  P-2001 -> loan:502 : allow (39 edge reads)
  U-1001 -> loan:501 : allow (13 edge reads)
  U-1005 -> loan:502 : deny  (65 edge reads)

list of accessible objects (all patterns are walked):
  P-2001 view:loan        -> [loan:501, loan:502    ] (65 edge reads)
  U-1001 view:loan        -> [loan:501              ] (65 edge reads)
  U-1006 view:list        -> [list:9                ] (52 edge reads)
  U-1005 view:list        -> [empty                 ] (52 edge reads)

The edge-read counts are specific to this small graph; what matters is the ratio between them. Two observations stand out.

First, a deny decision is the most expensive decision. An allow decision stops at the first matching pattern; a deny decision requires every pattern to be exhausted. Denying U-1005 cost sixty-five edge reads; allowing U-1001 cost thirteen. Unauthorized request traffic loads more cost onto the check layer than authorized traffic does — this is why rate limiting sits in front of the check layer.

Second, a listing query is not a repetition of the check query. Rendering a list page by “fetch every record, call the check for each one” produces as many check calls as the page has entries. The correct structure is to produce the set of accessible objects once and limit the data query to that set. How this set is passed into the query is a scale-dependent design decision: small sets travel as a plain list of identifiers, large sets travel as a join condition added to the resource query.

Maintaining the Graph

The relationship-based model’s operating cost is maintaining the edges.

An edge is written together with the source data. When a loan record is created, its owner edge is created too; if the two are written in separate transactions, requests arriving in between are decided wrongly. Writing the edge must sit inside the same transaction that writes the record.

An edge is deleted together with the source data. Edges left undeleted quietly leave access open, and because they produce no error, they go unnoticed. Regularly scanning for edges whose source no longer exists is the counterpart, here, of the orphan-record audit from the Relational Database Administration course.

Path length is bounded. The longer a pattern is, the wider a set of nodes the search spreads across. An inheritance chain with unbounded depth — a group’s group, and that group’s group — makes the cost unpredictable and makes who has access to what impossible to follow by eye.

Summary

• Relationship-based access control turns links into first-class data; the access question turns into a reachability query over a graph.
• An access rule is a path pattern; edges can be followed forward or in reverse.
• Transitive access — a record shared with a group opening up to the group’s members — is expressed with a single edge and requires no copying into an attribute field.
• The model cannot express context constraints; information like the time has no counterpart in the graph.
• A deny decision requires every pattern to be exhausted and so costs more than an allow decision; a listing query is done by producing the accessible set, not by calling the check one object at a time.

Next Step

All three models fell short in different places on the same scenario set, and their gaps complement each other. This points not to a fourth model but to a question about where these rules are written: will all of them just sit scattered through the application code in if blocks? The next lesson takes up policy-based authorization, which separates the decision from the code, and compares all four models’ decisions in the same table.