Attack Trees

The previous lesson’s most notable finding was chain threats: twelve items, defined on no single element, visible only on a path. But that lesson only counted paths; all five of the five scenarios stood at equal weight on the list.

In reality, paths are not equal. A target can be reached by more than one path, and some of these are cheaper than others; what defense cares about is not the most expensive path but the cheapest one. Counting this requires writing the scenario not as a flat sequence but as a structure branching backward from the target. The attack tree is this structure: a root goal, sub-goals, and leaf steps whose cost is written together with their precondition.

Root, Sub-Goal, Leaf

The tree below is a model. Leaf nodes are described only by their precondition and fictional cost; nowhere is it written how a step is carried out — the tree’s value on the defense side lies not in the step itself but in the combining structure of the steps. Running such an analysis on a real system, without written authorization and a defined scope, is both illegal and unprofessional. The cost and countermeasure numbers are fictional units, not currency.

TM17: every node is either OR (one of its children is enough), AND (all are required), or a leaf; a leaf carries a precondition, a cost, and a countermeasure price. TM18: an OR node’s cost is the smallest of its children’s, an AND node’s cost is their sum. TM19: a closed leaf’s cost is infinite. TM20: the cheapest path is the leaf set obtained by picking the cheapest child at every OR node.

// threat/tree.mjs — attack tree (model): root goal, sub-goals, and leaf steps.
// Leaf steps are written ONLY with their precondition and fictional cost; nowhere is it
// described how a step is carried out. The cost and countermeasure units are fictional, not currency.

// TM17: a node is either OR (one of its children is enough), AND (all are required), or a leaf.
// A leaf carries "name precondition cost countermeasure": the countermeasure is the fictional
// price of closing that leaf.
export const TREE = {
  name: "altering-the-billing-record", type: "OR", children: [
    { name: "writing-to-the-store-directly", type: "AND", children: [
      { name: "access-to-the-data-zone", type: "OR", children: [
        { name: "access-from-the-management-network", precondition: "internal-network-access", cost: 8, countermeasure: 4 },
        { name: "access-via-the-backup-channel", precondition: "backup-endpoint-open", cost: 12, countermeasure: 3 }] },
      { name: "store-write-authority", type: "OR", children: [
        { name: "obtaining-a-service-identity", precondition: "identity-store-readable", cost: 15, countermeasure: 6 },
        { name: "changing-a-role-assignment", precondition: "management-authority", cost: 20, countermeasure: 5 }] }] },
    { name: "via-billing", type: "AND", children: [
      { name: "a-valid-subscriber-session", type: "OR", children: [
        { name: "obtaining-subscriber-credentials", precondition: "portal-externally-exposed", cost: 6, countermeasure: 7 },
        { name: "session-hijacking", precondition: "token-visible", cost: 9, countermeasure: 5 }] },
      { name: "bypassing-the-authorization-check", type: "OR", children: [
        { name: "changing-the-object-id", precondition: "authorization-decision-on-client", cost: 3, countermeasure: 2 },
        { name: "changing-the-role-claim", precondition: "role-from-client", cost: 5, countermeasure: 2 }] }] },
    { name: "altering-the-validator-output", type: "AND", children: [
      { name: "entering-the-measurement-flow", type: "OR", children: [
        { name: "meter-identity-spoofing", precondition: "meter-identity-unverified",
          cost: 10, countermeasure: 9 },
        { name: "access-to-the-collection-endpoint", precondition: "collection-endpoint-externally-exposed",
          cost: 14, countermeasure: 4 }] },
      { name: "bypassing-the-validation-rule", type: "OR", children: [
        { name: "changing-a-setting", precondition: "management-flow-unverified", cost: 11, countermeasure: 3 },
        { name: "exceeding-the-threshold-value", precondition: "threshold-fixed", cost: 7, countermeasure: 2 }] }] }] };

export const LEAVES = (d = TREE) => d.children ? d.children.flatMap((c) => LEAVES(c)) : [d];

// TM18: an OR node's cost is the smallest of its children's, an AND node's cost is their sum.
// TM19: a closed leaf's cost is infinite; every path running through a closed leaf is closed.
export function cost(d = TREE, closed = []) {
  if (!d.children) return closed.includes(d.name) ? Infinity : d.cost;
  const c = d.children.map((x) => cost(x, closed));
  return d.type === "OR" ? Math.min(...c) : c.reduce((a, b) => a + b, 0);
}

// TM20: the cheapest path is the leaf set obtained by picking the cheapest child at every OR node.
export function cheapestPath(d = TREE, closed = []) {
  if (!d.children) return cost(d, closed) === Infinity ? [] : [d.name];
  if (d.type === "OR") {
    const best = d.children.reduce((a, b) => cost(a, closed) <= cost(b, closed) ? a : b);
    return cost(best, closed) === Infinity ? [] : cheapestPath(best, closed);
  }
  return d.children.flatMap((c) => cheapestPath(c, closed));
}

// threat/closing.mjs — the cheapest path's cost and by what factor closing a node
// makes the root more expensive.
import { TREE, LEAVES, cost, cheapestPath } from "./tree.mjs";

const write = (g, ...s) => console.log(s.map((v, i) =>
  (g[i] < 0 ? String(v).padEnd(-g[i]) : String(v).padStart(g[i]))).join(""));
const format = (x) => (x === Infinity ? "closed" : String(x));
const ratio = (x) => (x === Infinity ? "closed" : (x / BASE).toFixed(2));
const leaves = LEAVES();
const BASE = cost();

console.log(`${leaves.length} leaves, ${TREE.children.length} sub-goals; root cost ` +
  `${BASE} units, cheapest path ${cheapestPath().join(" + ")}`);

const A = [-32, 6, 6, 8, 15];
console.log("\n1. sub-goals and their costs");
write(A, "sub-goal", "type", "cost", "leaves", "cheapest path");
for (const c of TREE.children)
  write(A, c.name, c.type, cost(c), LEAVES(c).length, cheapestPath(c).length + " steps");

const B = [-37, -41, 6, 16, 10, 7, 22];
console.log("\n2. closing each leaf one at a time");
write(B, "leaf", "precondition", "cost", "countermeasure", "new root", "ratio", "ratio/countermeasure");
const measure = leaves.map((y) => ({ y, root: cost(TREE, [y.name]) }))
  .sort((a, b) => b.root - a.root || a.y.countermeasure - b.y.countermeasure);
for (const { y, root } of measure)
  write(B, y.name, y.precondition, y.cost, y.countermeasure, root, ratio(root),
    ((root - BASE) / y.countermeasure).toFixed(2));

const C = [-35, 16, 7, 10, 12, 13];
console.log("\n3. greedy closing: the leaf that raises the root most each round");
write(C, "closed leaf", "countermeasure", "spent", "new root", "step ratio", "total ratio");
const closed = [];
let spent = 0;
while (cost(TREE, closed) !== Infinity) {
  const candidate = leaves.filter((y) => !closed.includes(y.name))
    .map((y) => ({ y, root: cost(TREE, [...closed, y.name]) }))
    .sort((a, b) => b.root - a.root || a.y.countermeasure - b.y.countermeasure)[0];
  const previous = cost(TREE, closed);
  closed.push(candidate.y.name);
  spent += candidate.y.countermeasure;
  write(C, candidate.y.name, candidate.y.countermeasure, spent, format(candidate.root),
    candidate.root === Infinity ? "closed" : (candidate.root / previous).toFixed(2), ratio(candidate.root));
}
console.log(`closing the root completely calls for ${closed.length} leaves and ${spent} ` +
  `countermeasure units; the remaining ${leaves.length - closed.length} leaves sit on no open path`);

// Closing every leaf of an OR node closes that node and eliminates the AND branch containing it.
const orNodes = (d = TREE) => (d.children
  ? [...(d.type === "OR" && d !== TREE ? [d] : []), ...d.children.flatMap((c) => orNodes(c))]
  : []);
const D = [-36, 8, 16, 10, 7, 10];
console.log("\n4. closing an OR node in full");
write(D, "OR node", "leaves", "countermeasure", "new root", "ratio", "per unit");
for (const d of orNodes()) {
  const ls = LEAVES(d), o = ls.reduce((a, y) => a + y.countermeasure, 0);
  const root = cost(TREE, ls.map((y) => y.name));
  write(D, d.name, ls.length, o, format(root), ratio(root),
    root === Infinity ? "-" : ((root - BASE) / o).toFixed(2));
}
const path = leaves.filter((y) => cheapestPath().includes(y.name));
console.log(`comparison: closing the ${path.length} leaves of the cheapest path spends ` +
  `${path.reduce((a, y) => a + y.countermeasure, 0)} countermeasure units and raises the root ` +
  `to ${cost(TREE, path.map((y) => y.name))} units`);

// The cheapest way to close the root: pick one OR node from each AND branch, try every
// combination, and take the one with the smallest total countermeasure.
const branchOptions = TREE.children.map((branch) => orNodes(branch)
  .map((d) => ({ name: d.name, leaves: LEAVES(d) })));
let cheapestClosure = null;
const walk = (i, choice) => {
  if (i === branchOptions.length) {
    const ls = choice.flatMap((s) => s.leaves), o = ls.reduce((a, y) => a + y.countermeasure, 0);
    if (cost(TREE, ls.map((y) => y.name)) === Infinity &&
      (!cheapestClosure || o < cheapestClosure.o)) cheapestClosure = { choice, o, n: ls.length };
    return;
  }
  for (const s of branchOptions[i]) walk(i + 1, [...choice, s]);
};
walk(0, []);
console.log(`\nthe cheapest full closure is ${cheapestClosure.n} leaves and ${cheapestClosure.o} ` +
  `countermeasure units (${cheapestClosure.choice.map((s) => s.name).join(", ")}); the greedy ` +
  `order gives the same result for ${spent} units — ${(spent / cheapestClosure.o).toFixed(2)} ` +
  `times as expensive`);

12 leaves, 3 sub-goals; root cost 9 units, cheapest path obtaining-subscriber-credentials + changing-the-object-id

1. sub-goals and their costs
sub-goal                          type  cost  leaves  cheapest path
writing-to-the-store-directly      AND    23       4        2 steps
via-billing                        AND     9       4        2 steps
altering-the-validator-output      AND    17       4        2 steps

2. closing each leaf one at a time
leaf                                 precondition                               cost  countermeasure  new root  ratio  ratio/countermeasure
obtaining-subscriber-credentials     portal-externally-exposed                     6               7        12   1.33                  0.43
changing-the-object-id               authorization-decision-on-client              3               2        11   1.22                  1.00
changing-the-role-claim              role-from-client                              5               2         9   1.00                  0.00
exceeding-the-threshold-value        threshold-fixed                               7               2         9   1.00                  0.00
access-via-the-backup-channel        backup-endpoint-open                         12               3         9   1.00                  0.00
changing-a-setting                   management-flow-unverified                   11               3         9   1.00                  0.00
access-from-the-management-network   internal-network-access                       8               4         9   1.00                  0.00
access-to-the-collection-endpoint    collection-endpoint-externally-exposed       14               4         9   1.00                  0.00
changing-a-role-assignment           management-authority                         20               5         9   1.00                  0.00
session-hijacking                    token-visible                                 9               5         9   1.00                  0.00
obtaining-a-service-identity         identity-store-readable                      15               6         9   1.00                  0.00
meter-identity-spoofing              meter-identity-unverified                    10               9         9   1.00                  0.00

3. greedy closing: the leaf that raises the root most each round
closed leaf                          countermeasure  spent  new root  step ratio  total ratio
obtaining-subscriber-credentials                  7      7        12        1.33         1.33
session-hijacking                                 5     12        17        1.42         1.89
exceeding-the-threshold-value                     2     14        21        1.24         2.33
changing-a-setting                                3     17        23        1.10         2.56
obtaining-a-service-identity                      6     23        28        1.22         3.11
changing-a-role-assignment                        5     28    closed      closed       closed
closing the root completely calls for 6 leaves and 28 countermeasure units; the remaining 6 leaves sit on no open path

4. closing an OR node in full
OR node                               leaves  countermeasure  new root  ratio  per unit
access-to-the-data-zone                    2               7         9   1.00      0.00
store-write-authority                      2              11         9   1.00      0.00
a-valid-subscriber-session                 2              12        17   1.89      0.67
bypassing-the-authorization-check          2               4        17   1.89      2.00
entering-the-measurement-flow              2              13         9   1.00      0.00
bypassing-the-validation-rule              2               5         9   1.00      0.00
comparison: closing the 2 leaves of the cheapest path spends 9 countermeasure units and raises the root to 14 units

the cheapest full closure is 6 leaves and 16 countermeasure units (access-to-the-data-zone, bypassing-the-authorization-check, bypassing-the-validation-rule); the greedy order gives the same result for 28 units — 1.75 times as expensive

The numbers are in the measurement class; their inputs are TM17–TM20.

Nine Units

The root cost is 9 units and the cheapest path consists of two steps. This single number has nothing to do with the twelve leaves’ combined cost of 120 units: the tree is not a sum, it is a minimum choice.

The first table splits this into three branches. Writing directly to the store is 23 units, altering the validator output is 17 units, going via billing is 9 units. All three branches have four leaves and a two-step cheapest path; what produces the difference is not the number of leaves but the leaves’ costs. Because the root is an OR node, it takes the smallest of the three — that is, the weakest branch decides the tree’s cost.

This directly shows a costing mistake commonly made on the defense side. Effort spent making direct writes to the store harder never changes the root cost, because that branch is already the most expensive one and the attacking side will not choose it. The tree is a structure that writes down which work goes to waste.

Ten of the Twelve Leaves Change Nothing

The second table closes each leaf one at a time. The result is harsh: for ten of the twelve leaves the root cost stays at 9, a ratio of 1.00. Only two leaves change anything — closing obtaining-subscriber-credentials raises the root to 12 (1.33x), closing changing-the-object-id raises it to 11 (1.22x). Both sit on the cheapest path; the remaining ten do not.

The last column gives the return per countermeasure unit and reverses the ranking. obtaining-subscriber-credentials costs 7 countermeasure units for a 3-unit increase: 0.43 per unit. changing-the-object-id costs 2 countermeasure units for a 2-unit increase: 1.00 per unit. The closure with the smaller ratio is two and a half times more efficient per unit spent.

The most expensive countermeasures are the least efficient. meter-identity-spoofing demands 9 countermeasure units and changes the root cost not at all; obtaining-a-service-identity demands 6 units and again changes nothing. In a threat-modeling output, these two rows would probably look “high priority” — both correspond to a real vulnerability. Measured against the tree, both contribute zero to the root cost, because both already sit on the most expensive branch.

Closing an OR Node

The fourth table does the closing at the node level instead of the leaf level. Closing all of an OR node’s leaves closes that node and completely eliminates the AND branch containing it.

Of six OR nodes, only two change the root cost, and both are in the billing branch: a-valid-subscriber-session (12 countermeasure units) and bypassing-the-authorization-check (4 countermeasure units). Both raise the root to 17 — 1.89x. For the same result, one costs three times what the other does; the return per unit is 0.67 against 2.00.

The comparison row delivers the real decision. Closing the two leaves of the cheapest path spends 9 countermeasure units and raises the root to 14. Closing the two leaves of the bypassing-the-authorization-check node spends 4 units and raises the root to 17. The choice that spends less pays off more, because the cheapest path’s leaves are spread across two separate OR nodes and each one has a sibling leaf ready to replace it. Closing a leaf shifts the path; closing an OR node eliminates the branch.

Closing the Root Completely

The third table runs the greedy order: each round closes the leaf that raises the root the most. Six leaves and 28 countermeasure units later the root closes; the remaining six leaves sit on no open path. Intermediate values run 12, 17, 21, 23, 28, but the step ratios do not decrease evenly: 1.33 · 1.42 · 1.24 · 1.10 · 1.22. One closure’s return depends not on the previous one but on the structure of the open paths left remaining.

The last line measures this order’s inefficiency. A full closure done by picking one OR node from each AND branch also closes six leaves, but spends only 16 countermeasure units. The greedy order delivers the same result for 1.75 times the price.

The reason is in table 3’s first row. The greedy choice starts with obtaining-subscriber-credentials because it raises the root the most — but that leaf’s countermeasure price is 7, and closing the same branch via bypassing-the-authorization-check would have cost 4 units. Choosing the highest-payoff move each round does not give the choice with the smallest total price; in a tree, choices’ costs affect each other, and item-by-item ranking cannot see that.

Summary

• The number measured in an attack tree is not the leaf count but the root cost: in a tree of 12 leaves and three sub-goals, the root is 9 fictional units and the cheapest path is two steps. The root is an OR node, meaning its cost is decided by the weakest branch.
• Closing ten of the twelve leaves one at a time never changes the root cost; only the two leaves on the cheapest path yield 1.33 and 1.22x.
• Return per countermeasure unit reverses the ranking: the closure that yields 1.33x returns 0.43 per unit, the one that yields 1.22x returns 1.00 per unit.
• Closing an OR node in full eliminates the branch; a node worth 4 countermeasure units raises the root to 1.89x, while the two leaves of the cheapest path spend 9 units for only 1.56x.
• Closing the root completely costs 28 units in greedy order, 16 units by picking one OR node per branch; the highest-payoff move each round is 1.75 times more expensive in total.

Next Step

Across five lessons this topic produced a threat list and a priority order: 23 boundary crossings, 58 items, 108 systematic threats, 12 chain threats, and a handful of closures that actually change the root cost. All these numbers sit inside the model.

As long as they sit inside the model, nothing changes. A countermeasure only turns into code once someone takes ownership of it, ties it to an acceptance criterion, and writes it into a release; if any one of these is missing, the work item never opens and the item quietly disappears. The next lesson turns the model’s output into work items and takes the final measurement: how many threats land on how many separate countermeasures, how many of those are actually planned, how many disappear due to which gap, and how many items of the remaining residual risk are accepted in writing.