A Unified Compositional View of Attack Tree Metrics
Benedikt Peterseim, Milan Lopuhaä-Zwakenberg · 2025
Read A Unified Compositional View of Attack Tree Metrics by Benedikt Peterseim, Milan Lopuhaä-Zwakenberg (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14717.txt.
Introduction
Benedikt Peterseim and Milan Lopuhaä-Zwakenberg give attack trees a unified mathematical treatment. Attack trees are diagrams that break a system break-in into smaller steps, and metrics on them turn the diagrams into risk numbers. Many metrics exist, yet past frameworks either missed important ones or stayed too abstract to define concrete new ones.
The authors build a compositional theory in which trees are read as string diagrams inside a special category. Parts of a tree form what they call a channel category, and metrics then arise in a systematic way. The payoff is a principled recipe for defining and comparing security metrics instead of inventing each one from scratch.
Catalog record
| CREATOR | Benedikt Peterseim, Milan Lopuhaä-Zwakenberg |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-14717
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Unified Compositional View of Attack Tree Metrics Benedikt Peterseim, Milan Lopuhaä-Zwakenberg Abstract Attack trees (ATs) are popular graphical models for reasoning about the security of complex systems, allowing for the quantification of risk through so-called AT metrics. A large variety of different such AT metrics have been proposed, and despite their wide-spread practical use, no systematic treatment of attack tree metrics so far is fully satisfactory. Existing approaches either fail to include important metrics, or they are too general to provide a useful systematic way for defining concrete AT metrics, giving only an abstract characterisation of their behaviour. We solve this problem by developing a compositional theory of ATs and their functorial semantics based on gs-monoidal categories. Viewing attack trees as string diagrams, we show that components of ATs form a channel category, a particular type of gs-monoidal category. AT metrics then correspond to functors of channel categories. This characterisation is both general enough to include all common AT metrics, and concrete enough to define AT metrics by their logical structure. I Introduction Background: Attack trees. Since their inception [ 26 ] , attack trees (ATs) have been widely applied across numerous domains, including nuclear control systems [ 16 ] , smart grids [ 2 ] , and railway control systems [ 8 ] . How they work is best illustrated by an example: Figure 1 shows a simple example of an AT. Note that an AT is not necessarily a tree in the graph-theoretic sense: some nodes (such as \mathtt{forge\ badge} in Figure 1 ) may have multiple parents. For a comprehensive overview of ATs in comparison to other graphical models for security modelling, see [ 18 , Section 3.1.1] . A number of extensions to the formalism of ATs have been proposed, such as dynamic ATs [ 14 ] and attack-defence trees [ 17 ] . While we focus on standard ATs for simplicity, our methods will be set up in a way that can easily be adapted to these extensions. $30 $100 $80 \mathtt{gain\ access} \mathtt{enter\ door} \mathtt{sneak\ in} \mathtt{pass\ turnstile} \mathtt{distract\ guard} \mathtt{forge\ badge} Fig. 1: Example attack tree: An attacker aims to gain unauthorised access to an office space. This requires passing a turnstile and entering through a secured door (top AND gate). To pass the turnstile, they can either forge an access badge or distract the guard and jump over (left OR gate). To enter the door, they can either also use a forged badge or follow an employee in (right OR gate). Basic attack steps are labelled with their cost: distracting the guard costs \$30 , forging a badge \$100 , and sneaking in \$80 . Attack tree metrics. In addition to a qualitative model of how basic attack steps combine via AND and OR gates, ATs allow for the quantification of risk through AT metrics. For example, in Figure 1 , we use the min. cost metric , associating to each basic attack step the minimum cost required to successfully perform it. The question of computing the metric value is now: how do these attribute values propagate from the basic attack steps to the top node? In our example: what is the minimum cost required to successfully gain access to the office space? Already in the example of the min. cost metric, this question may be answered in different ways: depending on how one interprets the AT, the minimum cost of a successful attack may either be \$110 or \$100 for the AT in Figure 1 ; see Section II-A . In addition, many other types of metrics are used, including the minimum time or skill level required for a successful attack, or its maximal probability (under certain assumptions on attacker behaviour). With each of the various ways to quantify risk in an AT admitting several interpretations as an AT metric, the need for a systematic unified account of AT metrics emerges: Problem I.1 . Provide a framework for attack tree metrics that is both: 1. sufficiently general to capture all common attack tree metrics used in practice, and 2. sufficiently concrete for attack tree metrics to be fully determined by how they behave on the basic building blocks of attack trees: logic gates and basic attack steps. The second property ensures that a framework for AT metrics yields a systematic method for defining AT metrics, instead of just an abstract characterisation of their general behaviour. Shortcomings of existing frameworks. Despite the widespread use of ATs, so far, no systematic treatment of AT metrics exists that meets both of the requirements of I.1 . Several mutually incompatible frameworks based on semirings (see Definition V.1 ) exist, one based on what we will refer to as the bottom-up interpretation [ 22 ] , one based on the propositional interpretation [ 20 ] , and another one based on yet a different interpretation [ 4 ] . All are concrete enough to provide a recipe for defining AT metrics as required by our second desideratum. However, they do not satisfy our first requirement, failing to capture those AT metrics that do not adhere to their chosen interpretation. In the other direction, earlier work based on operads [ 21 ] provided a framework that does include essentially every important AT metric, instead failing to satisfy our second requirement of sufficient concreteness. In particular, specifying an AT metric as defined in this framework requires specifying its value on infinitely many ATs, which is clearly not satisfactory. Approach. We introduce a new framework for AT metrics that solves Problem I.1 . The key idea is to consider building blocks of ATs with multiple inputs and outputs. We define a metric by the operations it associates to AND/OR gates, and how it handles the dependence between multiple outputs. This is general enough to capture all relevant metrics, and concrete enough to specify metrics from finite data. We differ from semiring formalisms (which only describe the AND/OR operators and hardcode the dependency handling) and from the operad approach (which needs to specify infinitely many operators, so it cannot be used computationally in full generality). Mathematically, our framework is based on gs-monoidal categories , a category-theoretic concept originally proposed in the context of term rewriting [ 12 ] . Nevertheless, we will assume no prior knowledge of category theory, as we give a self-contained definition of a special type of gs-monoidal category we call channel categories for their resemblance to information-theoretic channels. A channel category is defined in terms of abstract operations of parallel and sequential composition: how a metric handles these operations exactly describes how a metric handles dependencies within ATs. We show that attack trees give rise to a channel category, and that the same holds for most metrics from the literature (with only a few exceptions, discussed in Section V-F ). Thus, we define an AT metric as a functor of channel categories . Despite its generality, this definition is still sufficiently concrete to yield a method for computing the metric. Interestingly, the different AT semantics that have been proposed in the literature [ 22 , 18 , 20 ] can also be understood as functors of channel categories; hence our approach unifies AT metrics and