Attack Graphs, Shared Subgoals, and Shortest Paths Through State Space

An attack tree assumes that a goal decomposes into independent steps, and it pays for that assumption with duplicated leaves: when two branches both need a valid user identifier, the tree contains two copies and the cost arithmetic charges for both. An attack graph drops the tree shape. Nodes are states or facts, edges are transitions that a successful action licenses, and a shared prerequisite appears once with as many incoming and outgoing edges as it actually has. What the tree loses in readability, the graph recovers in correctness, and the analysis changes from recursive evaluation of a fixed structure to a reachability question over a space of states.

Facts as nodes, exploits as edges

The standard construction makes the node set the union of conditions and privileges. A condition is a fact about the environment: a host runs a particular service, a service is reachable from a particular network, a credential exists. A privilege is an authority the attacker holds: user access on a host, the ability to read a database, membership in an administrative group. An exploit is an edge from a conjunction of conditions and privileges to a new privilege.

Because an edge can require several prerequisites simultaneously, the graph is technically a hypergraph: an edge is a set of source nodes and one target. Collapsing it to a directed graph is the common simplification, and the collapse is where models lose the ability to express conjunctions. Keeping the hyperedge is the honest representation, and it makes the evaluation rule simple: a target becomes reachable when every source in some incoming hyperedge is reachable.

The result of analysis is a closure, computed by iterating until no new node becomes reachable. The iteration terminates because the node set is finite and nodes are never removed, so the worst case is one pass per node, giving $O(|V| \cdot |E|)$ for a naive implementation. With monotone semantics, in which a fact once gained is never lost, the closure is the unique least fixed point, which is what makes the answer well defined at all.

def closure(initial, hyperedges):
    """hyperedges: (prerequisite_set, target_node) pairs; all prerequisites needed."""
    reached = set(initial)
    changed = True
    while changed:
        changed = False
        for sources, target in hyperedges:
            # An exploit fires only when every prerequisite is already held.
            if target not in reached and sources <= reached:
                reached.add(target)
                changed = True
    return reached

That loop is the entire core of a monotone reachability analysis. Its simplicity is the reason the approach scales to graphs with many thousands of nodes, and its simplicity is also the reason it can only answer one question: what is reachable. It cannot answer what is reachable given a budget, in what order, or with what probability, and each of those requires a different algorithm on the same graph.

Monotonicity is an assumption, not a fact

The fixed-point argument depends on facts being permanent. Real systems violate this in several ways, and each violation makes the analysis unsound in a specific direction.

Credentials expire, so a privilege gained early may not be available when a later exploit needs it. Sessions are invalidated, so a token obtained at one step may be dead at the next. Hosts are patched, so a condition that was true when the graph was built may be false by the time the attack is attempted. Configuration changes close paths that the graph still contains.

The standard response is to treat the graph as a snapshot: it describes what is reachable from the modeled initial state under the modeled configuration, and its validity is bounded by the interval during which that configuration holds. This is not a weakness so much as a scope statement, and models that omit it produce conclusions of the form “this attack is possible” that are true of a system that no longer exists.

A subtler violation is the action that destroys a prerequisite. Exploiting a service may crash it, which removes a condition that another branch needed. Attacker actions that consume a one-time token or trigger a lockout have the same shape. Monotone analysis cannot represent this, and the usual mitigation is to split the model into two graphs corresponding to the states before and after the destructive action, which restores monotonicity inside each.

Adding cost turns reachability into a shortest-path problem

Annotating each hyperedge with a cost and asking for the cheapest way to reach a target privilege gives a shortest-path problem over a hypergraph. The straightforward approach is to treat the hyperedge as an AND and apply the same min-over-alternatives, sum-over-prerequisites rule used in attack trees, computed with a priority queue in place of the naive fixed-point loop. Each node’s cost is the minimum over its incoming hyperedges of the sum of the source costs plus the edge cost; nodes are settled in increasing order of cost, and a hyperedge becomes eligible when all its sources are settled.

The ordering matters for correctness. A naive loop that relaxes edges in arbitrary order still converges when all costs are non-negative, but it can revisit each edge many times. Settling nodes in cost order means each is finalized once, which is the same argument that makes Dijkstra’s algorithm correct, and the same precondition applies: no negative edge costs. A negative cost would correspond to an exploit that makes the attacker’s position cheaper than before it started, which is not meaningful in this setting, so the precondition is satisfied by construction.

The result assigns a cost to every node, measured from the initial state, and the useful reading is the reverse of the tree’s. Instead of “here is the cheapest path to the root”, the graph gives “here is the cost of every privilege the attacker could hold”, which lets a defender ask a different question: which single node, if removed, raises the cost of the most targets. That question is a cut problem, and its answer is the structural definition of a chokepoint.

Minimal cut sets and why they overcount

The set of nodes whose removal disconnects the initial state from a target is a cut, and the smallest such set is a minimal cut. Cut sets are the graph-theoretic version of the tree’s chokepoints and are the natural output when the model’s purpose is to choose where to invest.

Two difficulties make the output less clean than it sounds. The first is that cuts interact: removing node A may make node B redundant, so the cost of a cut is not the sum of its members’ costs when the members are alternative mitigations. The second is that a cut over privileges and conditions mixes things that cannot be removed in the same way. A privilege can be revoked by changing a permission; a condition can be removed only by changing the deployment. The two have different costs, different owners, and different lead times, and a cut set that mixes them produces a mitigation plan that nobody can execute as a unit.

The practical discipline is to partition the graph by what kind of change removes each node, compute cuts within each partition, and compare the resulting options rather than the raw minimal sets. That is more work than listing the smallest cut, and it produces plans that correspond to actual engineering decisions.

Where the graph and the tree each belong

The graph is the right representation when the question concerns shared prerequisites, cumulative capability, or the effect of a single change on many routes. It is the wrong representation when the question is explanatory: a reader can follow a tree’s decomposition without knowing the formalism, and a graph with a few hundred nodes and hyperedges is not a document anyone reads.

The two are not in competition so much as at different scales. A tree is a readable argument about one goal; a graph is a computable model of a system’s reachable states. Producing the second from the first is mechanical: expand each leaf into its prerequisites, merge duplicates, and keep the conjunction structure. The merge step is where the tree’s cost arithmetic gets corrected. What the graph still cannot express is ordering and timing, since a monotone closure says nothing about whether two privileges can be held simultaneously, and that gap is the same one that appears in the per-element enumeration of failure modes, where each entry describes a state and not a sequence of states. A model that treats tokens as consumable rather than permanent, and therefore can express a race, is the Petri-net formulation.