Attack Tree Semantics: AND/OR Nodes and the Cost of the Cheapest Path

An attack tree takes one statement, that the attacker achieves a specific goal, and decomposes it into the steps that would produce it. The decomposition is a small logic: a goal is either achievable by any one of several means or by several means that must all succeed together. That is the whole formalism, and it turns out to be sufficient to express most of what a threat model wants to say about how an attacker would proceed, while also making the arithmetic of cost and probability explicit enough to argue about.

The root is a goal, the leaves are actions

The root is not “the system is insecure” but a bounded claim, such as “an unauthenticated party obtains a valid session for another user’s account”. Boundedness is what makes the tree useful; a root that admits any harm admits no structure. In practice a model has a small set of roots, one per asset and property pairing, since reaching the root must be a meaningful loss.

Leaves are atomic actions in the sense that the model does not further decompose them: obtain a credential from a paste dump, read a value from process memory, submit a request with a crafted token. Atomicity is a modeling choice rather than a fact about the world, and the right level is the level at which the action has an owner and a cost. A leaf that says “exploit the application” has neither.

Interior nodes carry the two connectives. An OR node asserts that any child achieves the parent, so the children are alternatives. An AND node asserts that all children must be achieved, so they are conjunctive requirements. The semantics are those of an alternating tree over booleans: a leaf is true when the attacker can perform it, an OR node is true when any child is, an AND node is true when every child is.

The interesting output of the analysis is not the boolean answer, which is usually trivially true, but the set of minimal paths that make the root true. A minimal path here is a set of leaves that is sufficient and contains no redundant element. In the boolean-function view, these are the minimal satisfying assignments, and in the language of the original security literature they are the attacker’s viable scenarios. The count can grow exponentially in the number of leaves even when the tree is shallow, which is the first practical limit of the formalism: a tree with twenty leaves can have hundreds of minimal sets, and enumerating them by hand is not viable.

Cost flows up the tree through a min and a sum

Once the model is annotated with a per-leaf cost in money, time, expertise, or a weighted combination, the two connectives acquire arithmetic. For an OR node, the attacker takes the cheapest alternative, so the node’s cost is the minimum over its children. For an AND node, every child must be paid for, so the cost is the sum.

That pair of rules is enough to compute the cost of the cheapest attacker path in a single bottom-up pass, in time linear in the number of nodes. A short evaluator makes the recursion explicit:

# A node is either ('leaf', cost), ('or', [children]) or ('and', [children])
def cheapest(node):
    kind, payload = node
    if kind == 'leaf':
        return payload
    child_costs = [cheapest(c) for c in payload]
    # An alternative is satisfied by its best child; a conjunction pays for all.
    return min(child_costs) if kind == 'or' else sum(child_costs)

goal = ('or', [
    ('and', [('leaf', 200), ('leaf', 1500)]),   # phish a session, then replay it
    ('or',  [('leaf', 40000), ('leaf', 300000)]),  # buy access, or break crypto
])
print(cheapest(goal))    # 1700: the conjunctive path is the cheapest route

The result is the attacker’s price, which is the quantity a defender can move. Turning that price into a choice among countermeasures requires a second player in the structure, which is what attack-defense trees add. Adding a step to a leaf on the cheapest path raises the attacker’s cost; adding a step to a leaf elsewhere changes nothing. This is what makes attack trees actionable in a way that a flat list of threats is not: the tree names the specific leaves whose cost determines the cheapest route, and those leaves are the ones where mitigation has leverage.

Cheapest and most likely are different paths

Annotating leaves with probability instead of cost inverts the arithmetic. For an AND node under an independence assumption, the probability that all children succeed is the product of their probabilities, so a conjunction of two likely steps is less likely than either. For an OR node, the probability that at least one child succeeds is one minus the product of the complements, so alternatives accumulate probability rather than diluting it.

The consequence is a systematic disagreement between the two metrics. Consider an OR node with a cheap but unreliable route and an expensive but reliable one. The cost view selects the cheap route; the probability view may select the expensive one, because the cheap route has a high chance of failing. Where the two metrics are combined into an expected cost of price divided by probability of success, neither route necessarily wins, and the ranking depends on parameters the model does not know with any precision.

The independence assumption is where probability annotations most often break, and the break is not minor. Two leaves are independent only if the failure of one does not inform the other. A single reused credential, a single vulnerable library, or a single upstream provider makes leaves correlated, and correlated success probabilities multiply into larger numbers than independence predicts. Treating correlated steps as independent systematically underestimates the attacker’s chance, which is the direction of error that costs a defender the most.

Where the tree stops being a tree

Four structural problems recur, and each has a standard response.

The first is shared subgoals. If two branches both require the attacker to obtain a valid user identifier, that leaf appears twice in the tree while being paid for once in reality. Left as a tree, the model double-counts the cost on any AND node that mentions both branches, and it double-counts the probability as well. The fix is to convert the tree into a directed acyclic graph in which shared leaves have a single node and multiple parents, and to compute costs over the graph rather than the tree. This is the same move that attack graph analysis makes, and it is why attack graphs generalize trees rather than replacing them.

The second is ordering. An AND node asserts that all children happen, not that they happen in a particular sequence, and many real attacks require a strict order: the credential must be obtained before it can be replayed. A tree cannot express that constraint, so it will happily generate a scenario that a state machine would reject. Modeling ordering requires either a state-based representation or an explicit annotation on each AND node recording which child must precede which.

The third is cyclic goals. Some attacks genuinely require the attacker to already possess part of what it is trying to obtain, which makes the dependency graph cyclic rather than acyclic. Trees cannot represent cycles at all, and forcing the analysis into a tree requires either expanding the goal into a larger one with more steps or dropping the cycle and producing a model whose cheapest path is not achievable.

The fourth is negation and defense. A tree says what makes the goal true; it does not directly say what makes it false. Adding defensive nodes converts the structure into an attack-defense tree with alternating attacker and defender levels, which changes the semantics from satisfiability to a game, and the cheapest-path computation to a search over both players’ choices. That extension is worth making only when the model must compare candidate countermeasures rather than describe exposure, and it requires deciding in advance whether the defender moves first, which in most systems is at least partly false.

Reading a tree as a prioritization argument

A tree is useful when it is read as a comparison between candidate routes, which is a use that ordinal risk ratings cannot support because they collapse the routes into one score. The candidates it names are the cheapest attacker routes, the most probable routes, and the leaves common to many routes. That third category is the most valuable and the least obvious, because a leaf that appears in most minimal sets is a chokepoint: raising its cost or reducing its probability degrades many scenarios at once, whereas a costly leaf that appears once is worth less than its annotation suggests.

Producing that reading requires knowing which leaves lie on the minimal sets, which is a different computation from the bottom-up cost pass. It is also where the tree’s assumptions become visible: the model asserts that these are the actions an attacker would take, that they can be evaluated independently, and that cost is additive across them. Those assumptions hold well enough to compare designs and badly enough that the resulting numbers should never be presented as forecasts.