Attack-Defense Trees and Countermeasure Selection as a Two-Player Problem

An attack tree answers whether a goal is achievable. A defender’s actual question is different: given a fixed budget, which subset of countermeasures makes the goal least achievable, or most expensive, for an adversary who will adapt to whatever is deployed. That question cannot be answered by evaluating one attack tree, because the tree has no representation of the defender’s moves. The extension that supplies them adds a second kind of node, and the evaluation rule changes from a bottom-up fold to an alternating search.

The two node families and their connectives

Attack-defense trees keep the attack structure and add defense nodes with the same two connectives, applied from the defender’s side. A defensive OR node means the defender chooses one of the children: any single countermeasure suffices to defeat the parent attack step. A defensive AND node means all children are required: the defense is a combination, such as a control that both authenticates and rate-limits, where implementing one without the other leaves the step open.

The alternation is what gives the structure its meaning. Attacker OR nodes are choices the attacker makes; attacker AND nodes are obligations the attacker must satisfy; defender OR nodes are choices the defender makes; defender AND nodes are obligations the defender must satisfy. Evaluation alternates between the two players’ choice points, and the value at each node depends on whose turn it is to choose.

That alternation is a game tree in the sense of combinatorial game theory, and the standard machinery applies. The attacker wants to maximize its own utility, meaning success probability or negative cost, and the defender wants to minimize it. A bottom-up evaluation with min at defender choice nodes and max at attacker choice nodes computes the value of the game under optimal play by both sides, which is the min-max value.

from math import prod

# node = ('a-or', kids) | ('a-and', kids) | ('d-or', kids) | ('d-and', kids) | ('leaf', p)
def value(node):
    kind, payload = node
    if kind == 'leaf':
        return payload                      # probability the attack step succeeds
    vals = [value(k) for k in payload]
    if kind == 'a-or':
        return max(vals)                    # attacker picks the strongest route
    if kind == 'a-and':
        return prod(vals)                   # every step must work
    if kind == 'd-or':
        return min(vals)                    # defender picks the strongest control
    return prod(vals)                       # layered controls multiply residual risk

The leaf value is the probability that the attack step succeeds given the defenses in place. Defense nodes therefore do not add cost; they change leaf probabilities. That is the modeling choice that makes the structure a game rather than an optimization over independent items: a countermeasure’s effect is mediated through the attack steps it covers, and its value depends on which other countermeasures are present.

Why the value is not the sum of the parts

The reason countermeasure selection is hard shows up in one line of the recursion: prod at a defender AND node. Layered controls multiply residual probabilities rather than adding their protections, so the marginal value of the second control depends on the first. Two controls that each halve the success probability of a step leave a quarter, not zero, and a third that covers the same step adds less than either.

The same effect appears at attacker OR nodes, from the other direction. A defense that blocks one alternative route leaves the others intact, and the attacker’s value at that node is the maximum over routes. Blocking the cheapest route of five does nothing to the value if a second route is nearly as cheap. This is why single-control deployments so often fail to change the outcome: the control was chosen because it addresses a real threat, and it addresses one branch of an OR.

Both effects mean the value function is submodular in the set of defenses: adding a control to a larger set yields less improvement than adding it to a smaller one. Submodularity is a useful property rather than a nuisance: it makes greedy selection a reasonable heuristic with a bounded approximation guarantee, and it makes the exact optimum a combinatorial problem that grows quickly. For a set of $n$ candidate controls the number of subsets is $2^n$, so enumeration is viable only for small candidate sets, and any real selection procedure is a heuristic over a structure that has been pruned to a manageable size.

First mover and the asymmetry of commitment

The min-max value assumes both players choose optimally and simultaneously, which is rarely true. The defender usually commits first: controls are deployed, then an adversary observes and adapts. That sequence is not the same game.

Under defender-first commitment, the defender picks a set $D$ without knowing which attack route the adversary will take, and the adversary then maximizes over routes given $D$. The defender’s objective is therefore to minimize the maximum, which is the min-max value. Committing first cannot help: the order of the quantifiers is $\min_D \max_A$, and for a pure-strategy game this is never better for the defender than the simultaneous value $\max_A \min_D$, because the adversary’s response is chosen with full knowledge of $D$. The minimax theorem recovers equality only when both sides may randomize, which in this setting means the defender distributing effort across several controls rather than committing to one.

The asymmetry that does change the answer is information. If the defender’s choice is visible and the adversary can wait, the adversary selects the route with the highest residual probability and the defender’s control set must cover the maximum rather than the average. If the defender can keep some controls undisclosed, the adversary’s route selection is made under uncertainty, and a control that is not in the adversary’s model has value beyond its direct effect. This is the formal version of the argument for not publishing every detection rule, and it also explains why the value evaporates once the control becomes known: the game reverts to full information.

A third sequence is attacker-first, where the adversary has already committed to a route and the defender responds. That is the incident-response posture rather than the design posture, and evaluating a design under it systematically overvalues controls that address the specific route the analyst imagines.

Cost, budget, and the multi-objective problem

The recursion above maximizes probability, which assumes the defender’s budget is unconstrained. Real selection has a cost per control and a total budget, which turns the problem into a knapsack-like optimization over a submodular objective: choose the set of controls whose total cost is within budget and whose combined effect minimizes the attacker’s value.

Three complications make the problem harder than a knapsack. Costs are not scalar, since a control consumes engineering time, operational attention, and sometimes latency budget, and the three are not interchangeable. Effects are uncertain, because the probability a control reduces at a leaf is an estimate, and the estimate’s error propagates through products at AND nodes in a way that compounds. And the candidate set is not fixed, because a control may cover several leaves at once, which creates a coverage structure rather than a one-to-one mapping.

The practical response is to reduce the problem before optimizing it. Controls that cover a single leaf on no cheapest path can be dropped, since they cannot change the value at the root. Controls whose effect at a leaf is below the uncertainty of that leaf’s estimate can be deferred, since the model cannot distinguish their contribution from noise. What remains is a small set of controls that sit on high-value paths, and among those the choice is usually clear enough that an exact optimizer adds little.

One further structure deserves recording because it breaks the independence assumption the recursion silently makes: controls are not independent of each other. Two countermeasures that both depend on the same identity provider fail together when that provider is compromised, and their combined effect at a leaf is the effect of the weaker one, not the product. The same holds for controls that share a bypass, such as a network policy and an application check that both trust the same header. Where a shared dependency exists, the model should record it as an additional attack node feeding the leaves that the controls cover, so that the dependency’s compromise shows up as a route rather than as a surprise. Without that node, the arithmetic reports a residual risk lower than any achievable configuration, which is the direction of error that produces a false sense of coverage.

What the structure still cannot express

Attack-defense trees model choice and conjunction over discrete steps. They do not model continuous allocation, where a defender divides a budget across detection thresholds rather than choosing a subset. They do not model deception or signaling, where the defender’s apparent posture differs from its actual posture, except by treating the two as separate models. And they do not model the adversary’s learning, where repeated attempts reveal which controls are present and the value of each changes over the engagement.

The last gap is the significant one for systems with a long exposure. A min-max value computed against a fully informed adversary is a lower bound on the defender’s effectiveness, and it is the right bound to design against when the adversary has time to probe. Where the adversary does not, the same model overstates the threat and leads to controls that cost more than the risk they retire. Choosing between the two framings is a judgment about the system’s exposure, and it is the kind of judgment the model can inform but not make. The candidate controls that survive this analysis still need an order in which to be built, which is where a comparison of consequences rather than a score becomes the deciding input, as discussed in ordinal risk scales.