Scalable Learning of Intrusion Response

through Recursive Decomposition

Kim Hammar 23 and Rolf Stadler23

Division of Network and Systems Engineering, KTH Royal Institute of Technology, Sweden

3 KTH Center for Cyber Defense and Information Security, Sweden

Email: {kimham<EMAIL_ADDRESS>
August 27, 2024

We study automated intrusion response for an IT infrastructure and formulate the interaction between an attacker and a defender as a partially observed stochastic game. To solve the game we follow an approach where attack and defense strategies co-evolve through reinforcement learning and self-play toward an equilibrium. Solutions proposed in previous work prove the feasibility of this approach for small infrastructures but do not scale to realistic scenarios due to the exponential growth in computational complexity with the infrastructure size. We address this problem by introducing a method that recursively decomposes the game into subgames with low computational complexity which can be solved in parallel. Applying optimal stopping theory we show that the best response strategies in these subgames exhibit threshold structures, which allows us to compute them efficiently. To solve the decomposed game we introduce an algorithm called Decompositional Fictitious Self-Play (), which learns Nash equilibria through stochastic approximation. We evaluate the learned strategies in an emulation environment where real intrusions and response actions can be executed. The results show that the learned strategies approximate an equilibrium and that significantly outperforms a state-of-the-art algorithm for a realistic infrastructure configuration.

Cybersecurity, network security, intrusion response, reinforcement learning, game theory, game decomposition, Markov decision process, optimal control, digital twin, .

§ INTRODUCTION

A promising direction of recent research is to automatically find security strategies for an IT infrastructure through reinforcement learning methods, whereby the problem is formulated as a Markov decision problem and strategies are learned through simulation (see survey <cit.>). While encouraging results have been obtained following this approach (see e.g., <cit.> and <cit.>), key challenges remain. Most of the prior work, for example, follows a decision-theoretic formulation and aims at learning effective defender strategies against a static attacker with a fixed strategy <cit.>. Only recently has the problem of learning effective security strategies against dynamic attackers been studied. This approach includes a game-theoretic framing, and the problem becomes one of learning Nash equilibria <cit.>.

The target infrastructure and the actors involved in the intrusion response use case.

Chief among the remaining challenges is the complexity of the formal model, resulting from the need to describe the target infrastructure with sufficient detail and at a realistic scale. Learning effective strategies with currently known methods is infeasible for most realistic use cases.

In this paper, we address the complexity challenge and present a scalable approach to automatically learn near-optimal defender strategies against dynamic attackers. We apply our approach to an intrusion response use case that involves the IT infrastructure of an organization (see Fig. <ref>). We formalize the use case as a partially observed stochastic game between two players – the operator of the infrastructure, which we call the defender, and an attacker, which seeks to intrude on the infrastructure. To manage the complexity when formalizing the use case, we recursively decompose the game into simpler subgames, which allows detailed modeling of the infrastructure while keeping computational complexity low.

The decomposition involves three steps. First, we partition the infrastructure according to workflows that are isolated from each other. This allows us to decompose the game into independent subgames (one per workflow) that can be solved in parallel. Second, the graph structure of a workflow allows us to decompose the workflow games into node subgames. We prove that these subgames have optimal substructure <cit.>, which means that a best response of the original game can be obtained from best responses of the node subgames. Third, we show that the problem of selecting which response action to apply on a node can be separated from that of deciding when to apply the action, which enables efficient learning of best responses through the application of optimal stopping theory <cit.>. We use this insight to design an efficient reinforcement learning algorithm, called Decompositional Fictitious Self-Play (), which allows scalable approximation of Nash equilibrium strategies.

Our method for learning the equilibrium strategies and evaluating them is based on a digital twin of the target infrastructure, which we use to run attack scenarios and defender responses (see Fig. <ref>) <cit.>. Such runs produce system measurements and logs, from which we estimate infrastructure statistics. We then use these statistics to instantiate simulations of the infrastructure's dynamics and learn strategies through . (Documentation of the software framework that implements the digital twin and the simulations is available at <cit.>; the source code is available at <cit.>; and a video demonstration is available at <cit.>.)

We summarize the contributions in this paper as follows.

* We formulate the intrusion response problem as a partially observed stochastic game and prove that, under assumptions often met in practice, the game decomposes into subgames whose best responses can be computed efficiently and in parallel.

* We design , an efficient reinforcement learning algorithm for approximating Nash equilibria of the decomposed game.

* For a realistic use case, we evaluate the learned response strategies against network intrusions on a digital twin.

Our framework for finding and evaluating intrusion response strategies <cit.>.

§ RELATED WORK

Networked systems found in engineering and science often exhibit a modular topological structure that can be exploited for designing control algorithms <cit.>. System decomposition for the purpose of automatic control was first suggested by Šiljak in 1978 <cit.> and approaches based on decomposition, such as divide and conquer, layering, and hierarchical structuring are well established in the design of large-scale systems, a notable example being the Internet <cit.>. Similar decomposition methods are frequently used in robotics and multi-agent systems, as exemplified by the subsumption architecture <cit.>. Within the fields of decision- and game-theory, decomposition is studied in the context of factored decision processes <cit.>, distributed decision processes <cit.>, factored games <cit.>, and graph-structured games <cit.>.

Decomposition as a means to automate intrusion response has been studied first in <cit.>. The work in <cit.> formulates the interaction between a defender and an attacker on a cyber-physical infrastructure as a factored Markov game and introduces a decomposition based on linear programming. Following a similar approach, the work in <cit.> studies a Markov game formulation and shows that a multi-stage game can be decomposed into a sequence of one-stage games. In a separate line of work, <cit.> models intrusion response as a minimax control problem and develops a heuristic decomposition based on clustering and influence graphs. This approach resembles the work in <cit.>, which studies a factored decision process and proposes a hierarchical decomposition.

In all of the above works, decomposition is key to obtain effective strategies for large-scale systems. Compared to our work, some of them propose decomposition methods without optimal substructure <cit.>, others do not consider partial observability <cit.>, or dynamic attackers <cit.>. Most importantly, all of the above works evaluate the obtained strategies in a simulation environment. They do not perform evaluation in an emulation environment as we report in this paper, which gives higher confidence that the strategies are effective on the target infrastructure.

For a comprehensive review of prior research on automated intrusion response (beyond work that use decomposition), see <cit.>.

§ THE INTRUSION RESPONSE USE CASE

We consider an intrusion response use case that involves the IT infrastructure of an organization. The operator of this infrastructure, which we call the defender, takes measures to protect it against an attacker while providing services to a client population (see Fig. <ref>). The infrastructure is segmented into zones with virtual nodes that run network services. Services are realized by workflows that are accessed by clients through a gateway, which also is open to the attacker.

The attacker's goal is to intrude on the infrastructure, compromise nodes, and disrupt workflows. It can take three types of actions to achieve this goal: (i) reconnaissance; (ii) brute-force attacks; and (iii) exploits (see Fig. <ref>).

The defender continuously monitors the infrastructure through accessing and analyzing intrusion detection alerts and other statistics. It can take four types of defensive actions to respond to possible intrusions: (i) migrate nodes between zones; (ii) redirect or block network flows; (iii) shut down nodes; and (iv) revoke access to nodes (see Fig. <ref>). When deciding between these actions, the defender must balance two conflicting objectives: maximize workflow utility towards its clients and minimize the cost of intrusion.

Attacker actions: (i) reconnaissance actions; (ii) brute-force attacks; and (iii) code execution attacks.

§ FORMALIZING THE INTRUSION RESPONSE PROBLEM

We formalize the above use case as an optimization problem where the goal is to select an optimal sequence of defender actions in response to a sequence of attacker actions. We assume a dynamic attacker, which leads to a game-theoretic formulation of the intrusion response problem. The game is played on the IT infrastructure, which we model as a discrete-time dynamical system whose evolution depends on the actions by the attacker and the defender. Both actors have partial observability of the system state, and their observations depend on the traffic generated by clients requesting service, which we assume can be described by a stationary process.

Notations. Boldface lower case letters (e.g., $\mathbf{x}$) denote row vectors and upper case calligraphic letters (e.g., $\mathcal{V}$) represent sets. The set of probability distributions over $\mathcal{V}$ is written as $\Delta(\mathcal{V})$. A random variable is denoted by upper case (e.g., $X$) and a random vector is denoted by boldface (e.g., $\mathbf{X}=(X_1,\hdots,X_n)$). $\mathbb{P}$ is the probability measure and the expectation of $f$ with respect to $X$ is expressed as $\mathbb{E}_X[f]$. When $f$ includes many random variables that depend on $\pi$ we simplify the notation to $\mathbb{E}_{\pi}[f]$. We use $x \sim f$ to mean that $x$ is sampled from $f$ and sometimes write $\mathbb{P}[x|z,y]$ instead of $\mathbb{P}[X=x|Z=z,Y=y]$ when $X,Z,Y$ are clear from the context. Symbols used throughout the paper are listed in Table <ref>.

§.§ Modeling the Infrastructure and Services

Following the description in <ref>, we consider an IT infrastructure with application servers connected by a communication network that is segmented into zones (see Fig. <ref>). Overlaid on this physical infrastructure is a virtual infrastructure with tree-structure that includes nodes, which collectively offer services to clients.

A service is modeled as a workflow, which comprises a set of interdependent nodes. A dependency between two nodes reflects information exchange through service invocations. We assume that each node belongs to exactly one workflow. As an example of a virtual infrastructure, we can think of a microservice architecture where a workflow is defined as a tree of microservices (see Fig. <ref>).

Infrastructure. We model the virtual infrastructure as a (finite) directed graph $\mathcal{G} \triangleq \langle \{\mathrm{gw}\}\cup \mathcal{V}, \mathcal{E} \rangle$. The graph has a tree structure and is rooted at the gateway $\mathrm{gw}$. Each node $i \in \mathcal{V}$ has three state variables. $v_{i,t}^{(\mathrm{R})}$ represents the reconnaissance state and realizes the binary random variable $V_{i,t}^{(\mathrm{R})}$. $v_{i,t}^{(\mathrm{R})}=1$ if the attacker has discovered the node, $0$ otherwise. $v_{i,t}^{(\mathrm{I})}$ represents the intrusion state and realizes the binary random variable $V_{i,t}^{(\mathrm{I})}$. $v_{i,t}^{(\mathrm{I})}=1$ if the attacker has compromised the node, $0$ otherwise. Lastly, $v^{(\mathrm{Z})}_{i,t}$ indicates the zone in which the node resides and realizes the random variable $V^{(\mathrm{Z})}_{i,t}$. We call a node active if it is functional as part of a workflow (denoted $\alpha_{i,t}=1$). Due to a defender action (e.g., a shut down) a node $i \in \mathcal{V}$ may become inactive (i.e., $\alpha_{i,t}=0$).

Workflows. We model a workflow $\mathbf{w} \in \mathcal{W}$ as a subtree $\mathcal{G}_{\mathbf{w}} \triangleq \langle \{\mathrm{gw}\}\cup \mathcal{V}_{\mathbf{w}}, \mathcal{E}_{\mathbf{w}} \rangle$ of the infrastructure graph. Workflows do not overlap except for the gateway which belongs to all workflows.

Defender actions: (i) migrate a node between two zones; (ii) redirect or block traffic flows to a node; (iii) shut down a node; and (iv) revoke access to a node.

§.§ Modeling Actors

The intrusion response use case involves three types of actors: an attacker, a defender, and clients (see Fig. <ref>).

Attacker. At each time $t$, the attacker takes an action $\mathbf{a}^{(\mathrm{A})}_t$, which is defined as the composition of the local actions on all nodes $\mathbf{a}^{(\mathrm{A})}_t \triangleq (\mathbf{a}^{(\mathrm{A})}_{1,t}, \hdots, \mathbf{a}^{(\mathrm{A})}_{|\mathcal{V}|,t}) \in \mathcal{A}_{\mathrm{A}}$, where $\mathcal{A}_{\mathrm{A}}$ is finite. A local action is either the null action (denoted with $\bot$) or an offensive action (see examples in Fig. <ref>). An offensive action on a node $i$ may change the reconnaissance state $v^{(\mathrm{R})}_{i,t}$ or the intrusion state $v^{(\mathrm{I})}_{i,t}$. A node $i$ can only be compromised if it is discovered, i.e., if $v^{(\mathrm{R})}_{i,t}=1$. We express this constraint as $\mathbf{a}^{(\mathrm{A})}_t \in \mathcal{A}_{\mathrm{A}}(\mathbf{s}^{(\mathrm{A})}_t)$.

The attacker state $\mathbf{S}^{(\mathrm{A})}_t \triangleq \big(V^{(\mathrm{I})}_{i,t},V^{(\mathrm{R})}_{i,t}\big)_{i \in \mathcal{V}} \in \mathcal{S}_{\mathrm{A}}$ evolves as

\begin{align}
\mathbf{s}^{(\mathrm{A})}_{t+1} \sim f_{\mathrm{A}}\big(\cdot \mid \mathbf{s}^{(\mathrm{A})}_t, \mathbf{a}^{(\mathrm{A})}_t,\mathbf{a}^{(\mathrm{D})}_t\big)\label{eq:transition_atc}
\end{align}

where $\mathbf{S}^{(\mathrm{A})}_t$, $\mathbf{A}^{(\mathrm{A})}_t$, and $\mathbf{A}^{(\mathrm{D})}_t$ are random vectors with realizations $\mathbf{s}^{(\mathrm{A})}_t$, $\mathbf{a}^{(\mathrm{A})}_t$, and $\mathbf{a}^{(\mathrm{D})}_t$. ($\mathbf{A}^{(\mathrm{D})}_t$ represents the defender action at time $t$.)

Defender. At each time $t$, the defender takes an action $\mathbf{a}^{(\mathrm{D})}_t$, which is defined as the composition of the local actions on all nodes $\mathbf{a}^{(\mathrm{D})}_t \triangleq (\mathbf{a}^{(\mathrm{D})}_{1,t}, \hdots, \mathbf{a}^{(\mathrm{D})}_{|\mathcal{V}|,t}) \in \mathcal{A}_{\mathrm{D}}$, where $\mathcal{A}_{\mathrm{D}}$ is finite. A local action is either a defensive action or the null action $\bot$ (see examples in Fig. <ref>). Each defensive action $\mathbf{a}^{(\mathrm{D})}_{i,t}\neq \bot$ leads to $\mathbf{S}^{(\mathrm{A})}_{i,t+1}=(0,0)$ and may affect $V^{(\mathrm{Z})}_{i,t+1}$.

The defender state $\mathbf{S}^{(\mathrm{D})}_t \triangleq \big(V^{(\mathrm{Z})}_{i,t}\big)_{i \in \mathcal{V}} \in \mathcal{S}_{\mathrm{D}}$ evolves according to

\begin{align}
\mathbf{s}^{(\mathrm{D})}_{t+1} \sim f_{\mathrm{D}}\big(\cdot \mid \mathbf{s}^{(\mathrm{D})}_t, \mathbf{a}^{(\mathrm{D})}_t\big)\label{eq:transition_def}
\end{align}

where $\mathbf{s}^{(\mathrm{D})}_{t}$ and $\mathbf{a}^{(\mathrm{D})}_{t}$ realize the random vectors $\mathbf{S}^{(\mathrm{D})}_{t}$ and $\mathbf{A}^{(\mathrm{D})}_t$.

Clients. Clients consume services of the infrastructure by accessing workflows. We model client behavior through stationary stochastic processes, which affect the observations available to the attacker and the defender.

§.§ Observability and Strategies

At each time $t$, the defender and the attacker both observe $\mathbf{o}_t \triangleq \left(\mathbf{o}_{1,t},\hdots,\mathbf{o}_{|\mathcal{V}|,t}\right) \in \mathcal{O}$, where $\mathcal{O}$ is finite. (In our use case  $\mathbf{o}_t$ relates to the number of alerts per node.) $\mathbf{o}_t$ is drawn from the random vector $\mathbf{O}_t \triangleq (\mathbf{O}_{1,t},\hdots,\mathbf{O}_{|\mathcal{V}|,t})$ whose marginal distributions $Z_{\mathbf{O}_1}, \hdots, Z_{\mathbf{O}_{|\mathcal{V}|}}$ are stationary and conditionally independent given $\mathbf{S}_{i,t}\triangleq(\mathbf{S}^{(\mathrm{D})}_{i,t},\mathbf{S}^{(\mathrm{A})}_{i,t})$. (Note that $Z_{\mathbf{O}_i}$ depends on the traffic generated by clients.) As a consequence, the joint conditional distribution $Z$ is given by

\begin{align}
Z\big(\mathbf{O}_{t}=\mathbf{o} \mid \mathbf{s}_{t}\big)=\prod^{|\mathcal{V}|}_{i=1} Z_{\mathbf{O}_i}\big(\mathbf{O}_{i,t}=\mathbf{o}_{i} \mid \mathbf{s}_{i,t}\big) && \forall \mathbf{o} \in \mathcal{O}\label{eq:obs_1}
\end{align}

The sequence of observations and states at times $1,\hdots,t$ forms the histories $\mathbf{h}^{(\mathrm{D})}_t\in \mathcal{H}_{\mathrm{D}}$ and $\mathbf{h}^{(\mathrm{A})}_t\in \mathcal{H}_{\mathrm{A}}$. These histories are realizations of the random vectors $\mathbf{H}^{(\mathrm{D})}_t\allowbreak\triangleq\allowbreak(\mathbf{S}^{(\mathrm{D})}_1,\allowbreak\mathbf{A}_1^{(\mathrm{D})},\allowbreak\mathbf{O}_1,\allowbreak\hdots,\allowbreak\mathbf{A}_{t-1}^{(\mathrm{D})},\allowbreak\mathbf{S}^{(\mathrm{D})}_t,\allowbreak\mathbf{O}_t)$ and $\mathbf{H}^{(\mathrm{A})}_t\allowbreak\triangleq \allowbreak(\mathbf{S}_1^{(\mathrm{A})},\allowbreak\mathbf{A}_1^{(\mathrm{A})},\allowbreak\mathbf{O}_1,\allowbreak\hdots,\allowbreak\mathbf{A}_{t-1}^{(\mathrm{A})},\allowbreak\mathbf{S}_t^{(\mathrm{A})},\allowbreak\mathbf{O}_t)$. Based on their respective histories, the defender and the attacker select actions, which define the defender strategy $\pi_{\mathrm{D}}\in \Pi_{\mathrm{D}}: \mathcal{H}_{\mathrm{D}} \rightarrow \Delta(\mathcal{A}_{\mathrm{D}})$ and the attacker strategy $\pi_{\mathrm{A}} \in \Pi_{\mathrm{A}}: \mathcal{H}_{\mathrm{A}} \rightarrow \Delta(\mathcal{A}_{\mathrm{A}})$.

Dependency graph of a workflow consisting of a tree of virtual network functions and microservices; fw, lb, and idps are acronyms for firewall, load balancer, and intrusion detection and prevention system, respectively.

§.§ The Intrusion Response Problem

When selecting the strategy $\pi_{\mathrm{D}}$ the defender must balance two conflicting objectives: maximize the workflow utility towards its clients and minimize the cost of intrusion. The weight $\eta \geq 0$ controls the trade-off between these two objectives, which results in the bi-objective

\begin{align}
&J \triangleq \sum_{t=1}^{\infty}\gamma^{t-1} \Biggl(\sum_{\mathbf{w} \in \mathcal{W}}\sum_{i \in \mathcal{V}_{\mathbf{w}}}\underbrace{\eta u^{(\mathrm{W})}_{i,t}}_{\text{workflows utility}} - \underbrace{c_{i,t}^{(\mathrm{I})}}_{\text{intrusion cost}}\Biggr) \label{eq:objective_fun}
\end{align}

where $\gamma \in [0,1)$ is a discount factor, $c_{i,t}^{(\mathrm{I})}$ is the intrusion cost associated with node $i$ at time $t$, and $u^{(\mathrm{W})}_{i,t}$ expresses the workflow utility associated with node $i$ at time $t$. For this paper, we assume that $u^{(\mathrm{W})}_{i,t}$ is proportional to the number of active nodes in the subtree rooted at $i$ and that $c_{i,t}^{(\mathrm{I})}= v^{(\mathrm{I})}_{i,t} + c^{(\mathrm{A})}(\mathbf{a}^{(\mathrm{D})}_{i,t})$, where $c^{(\mathrm{A})}$ is a non-negative function.

Given (<ref>) and an attacker strategy $\pi_{\mathrm{A}}$, the intrusion response problem can be stated as

\begin{align}
\maximize_{\pi_{\mathrm{D}} \in \Pi_{\mathrm{D}}} \quad &\mathbb{E}_{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}\left[J\right]\\
\text{subject to} \quad &\mathbf{s}^{(\mathrm{D})}_{t+1} \sim f_{\mathrm{D}}\big(\cdot \mid \mathbf{s}^{(\mathrm{D})}_t, \mathbf{a}^{(\mathrm{D})}_t\big) && \forall t \label{eq:dynamics_constraint}\\
&\mathbf{s}^{(\mathrm{A})}_{t+1} \sim f_{\mathrm{A}}\big(\cdot \mid \mathbf{s}^{(\mathrm{A})}_t, \mathbf{a}^{(\mathrm{A})}_t, \mathbf{a}^{(\mathrm{D})}_t\big) && \forall t \label{eq:dynamics_constraint_attacker}\\
&\mathbf{o}_{t+1} \sim Z\big(\cdot \mid \mathbf{s}^{(\mathrm{D})}_{t+1}, \mathbf{s}^{(\mathrm{A})}_{t+1}) && \forall t \label{eq:obs_constraint}\\
&\mathbf{a}^{(\mathrm{A})}_{t} \sim \pi_{\mathrm{A}}\big(\cdot \mid \mathbf{h}^{(\mathrm{A})}_t\big) && \forall t\label{eq:attacker_strategy_constraint}\\
&\mathbf{a}^{(\mathrm{D})}_{t} \sim \pi_{\mathrm{D}}\big(\cdot \mid \mathbf{h}^{(\mathrm{D})}_t\big) && \forall t\label{eq:defender_strategy_constraint}\\
&\mathbf{s}^{(\mathrm{D})}_{t} \in \mathcal{S}_{\mathrm{D}}, \quad \mathbf{s}^{(\mathrm{A})}_{t} \in \mathcal{S}_{\mathrm{A}},\quad \mathbf{o} \in \mathcal{O} && \forall t\label{eq:domain_constraint_1} \\
&\mathbf{a}^{(\mathrm{D})}_{t} \in \mathcal{A}_{\mathrm{D}}, \quad \mathbf{a}^{(\mathrm{A})}_{t} \in \mathcal{A}_{\mathrm{A}}(\mathbf{s}^{(\mathrm{A})}_t) && \forall t \label{eq:domain_constraint_2}\\
&\mathbf{s}^{(\mathrm{A})}_1 \sim \mathbf{b}^{(\mathrm{A})}_1 \label{eq:init_dist_a}\\
&\mathbf{s}^{(\mathrm{D})}_1 \sim \mathbf{b}^{(\mathrm{D})}_1\label{eq:init_dist_d}
\end{align}

where $\mathbb{E}_{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}$ denotes the expectation over the random vectors $(\mathbf{H}^{(\mathrm{D})}_t,\mathbf{H}^{(\mathrm{A})}_t)_{t\in \{1,2,\hdots\}}$ when following the strategy profile $(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$; (<ref>)–(<ref>) are the dynamics constraints; (<ref>) describes the observations; (<ref>)–(<ref>) capture the actions; (<ref>)–(<ref>) are the domain constraints; and (<ref>)–(<ref>) define the initial state distributions. (As a maximizer of (<ref>) exists (see Thm. <ref>), we write $\max$ instead of $\sup$ throughout this paper).

Solving (<ref>) yields an optimal defender strategy against a static attacker with a fixed strategy. Note that this defender strategy is generally not optimal against a different attacker strategy. For this reason, we aim to find a defender strategy that maximizes the minimum value of $J$ (<ref>) across all possible attacker strategies. This objective can be formally expressed as a maxmin problem:

\begin{align}
\maximize_{\pi_{\mathrm{D}} \in \Pi_{\mathrm{D}}}\minimize_{\pi_{\mathrm{A}} \in \Pi_{\mathrm{A}}}&\text{ } \text{ }\mathbb{E}_{(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})}\left[J\right] \text{ subject to (\ref{eq:dynamics_constraint})--(\ref{eq:init_dist_d})} \label{eq:game_def_maxmin}
\end{align}

Solving (<ref>) corresponds to finding a Nash equilibrium <cit.> of a two-player game. Hence the problem of solving (<ref>) can be analyzed through game theory.

§ THE INTRUSION RESPONSE GAME

The maxmin problem in (<ref>) defines a stationary, finite, and zero-sum Partially Observed Stochastic Game with Public Observations (a ) <cit.><cit.>:

\begin{align}
\Gamma = \langle \mathcal{N}, (\mathcal{S}_{\mathrm{k}},\mathcal{A}_{\mathrm{k}},f_{\mathrm{k}},\mathbf{b}^{(\mathrm{k})}_1)_{\substack{\mathrm{k} \in \mathcal{N}}}, u, \gamma, \mathcal{O}, Z \rangle \label{def:game}
\end{align}

The game $\Gamma$ has two players $\mathcal{N}=\{\mathrm{D},\mathrm{A}\}$ with $\mathrm{D}$ being the defender and $\mathrm{A}$ being the attacker. $(\mathcal{S}_{\mathrm{k}})_{\mathrm{k} \in \mathcal{N}}$ are the state spaces, $(\mathcal{A}_{\mathrm{k}})_{\mathrm{k} \in \mathcal{N}}$ are the action spaces, and $\mathcal{O}$ is observation space (as defined in <ref>). The transition functions $(f_{\mathrm{k}})_{\mathrm{k} \in \mathcal{N}}$ are defined by (<ref>)–(<ref>), the observation function $Z$ is defined in (<ref>), and the utility function $u(\mathbf{s}_t,\mathbf{a}^{(\mathrm{D})}_{t})$ is the expression within brackets in (<ref>). $(\mathbf{b}^{(\mathrm{k})}_1)_{\mathrm{k} \in \mathcal{N}}$ are the state distributions at $t=1$ and $\gamma$ is the discount factor in (<ref>).

Game play. When the game starts at $t=1$, $\mathbf{s}^{(\mathrm{D})}_1$ and $\mathbf{s}_1^{(\mathrm{A})}$ are sampled from $\mathbf{b}^{(\mathrm{D})}_1$ and $\mathbf{b}^{(\mathrm{A})}_1$. A play of the game proceeds in time-steps $t=1,2,\hdots$. At each time $t$, the defender observes $\mathbf{h}^{(\mathrm{D})}_t$ and the attacker observes $\mathbf{h}^{(\mathrm{A})}_t$. Based on these histories, both players select actions according to their respective strategies, i.e., $\mathbf{a}^{(\mathrm{D})}_{t} \sim \pi_{\mathrm{D}}(\cdot \mid \mathbf{h}^{(\mathrm{D})}_t)$ and $\mathbf{a}^{(\mathrm{A})}_{t} \sim \pi_{\mathrm{A}}(\cdot \mid \mathbf{h}^{(\mathrm{A})}_t)$. As a result of these actions, five events occur at time $t+1$: (i) $\mathbf{o}_{t+1}$ is sampled from $Z$; (ii) $\mathbf{s}_{t+1}^{(\mathrm{D})}$ is sampled from $f_{\mathrm{D}}$; (iii) $\mathbf{s}_{t+1}^{(\mathrm{A})}$ is sampled from $f_{\mathrm{A}}$; (iv) the defender receives the utility $u(\mathbf{s}_t,\mathbf{a}^{(\mathrm{D})}_{t})$; and (v) the attacker receives the utility $-u(\mathbf{s}_t,\mathbf{a}^{(\mathrm{D})}_{t})$.

Belief states. Based on their histories $\mathbf{h}^{(\mathrm{D})}_t$ and $\mathbf{h}^{(\mathrm{A})}_t$, both players form beliefs about the unobservable components of the state $\mathbf{s}_t$, which are expressed through the belief states $\mathbf{b}^{(\mathrm{D})}_t(\mathbf{s}^{(\mathrm{A})}_t)\triangleq\mathbb{P}[\mathbf{s}^{(\mathrm{A})}_t \mid \mathbf{H}^{(\mathrm{D})}_t=\mathbf{h}^{(\mathrm{D})}_t]$ and $\mathbf{b}^{(\mathrm{A})}_t(\mathbf{s}^{(\mathrm{D})}_t)\triangleq\mathbb{P}[\mathbf{s}^{(\mathrm{D})}_t \mid \mathbf{H}^{(\mathrm{A})}_t=\mathbf{h}^{(\mathrm{A})}_t]$.

The belief states are are realizations of $\mathbf{B}^{(\mathrm{D})}_t$ and $\mathbf{B}^{(\mathrm{A})}_t$ and are updated at each time $t>1$ via <cit.>

\begin{align}
&\mathbf{b}^{(\mathrm{k})}_{t}(\mathbf{s}^{(\mathrm{-k})}_{t}) = C_{\mathrm{k}} \sum_{\mathbf{s}^{(\mathrm{-k})}_{t-1} \in \mathcal{S}_{\mathrm{-k}}}\sum_{\mathbf{a}^{(\mathrm{-k})}_{t-1} \in \mathcal{A}_{\mathrm{-k}}(\mathbf{s}_t)}\mathbf{b}^{(\mathrm{k})}_{t-1}(\mathbf{s}^{(\mathrm{-k})}_{t-1})\cdot \label{eq:irs_belief_upd}\\
&\pi^{(s)}_{\mathrm{-k}}(\mathbf{a}^{(\mathrm{-k})}_{t-1}\mid \mathbf{s}^{(\mathrm{-k})}_{t-1})Z(\mathbf{o}_{t} \mid \mathbf{s}^{(\mathrm{D})}_{t}, \mathbf{a}^{(\mathrm{A})}_{t-1}) f_{\mathrm{-k}}(\mathbf{s}^{(\mathrm{-k})}_{t} \mid \mathbf{s}^{(\mathrm{-k})}_{t-1}, \mathbf{a}_{t-1})\nonumber
\end{align}

where $\mathrm{k} \in \{\mathrm{D}, \mathrm{A}\}$, $C_{\mathrm{k}}=1/\mathbb{P}[\mathbf{o}_{t}\mid \mathbf{s}^{(\mathrm{k})}_{t}, \mathbf{a}^{(\mathrm{k})}_{t-1},\pi_{\mathrm{-k}}, \mathbf{b}^{(\mathrm{k})}_{t-1}]$ is a normalizing factor that makes the components of $\mathbf{b}^{(\mathrm{k})}_{t}$ sum to $1$ and $\pi^{(s)}_{\mathrm{-k}}: \mathcal{S}_{\mathrm{-k}} \rightarrow \Delta(\mathcal{A}_{\mathrm{-k}})$ is the stage strategy for the opponent, i.e., the strategy of the opponent in the current stage only, which is assumed known to both players at each stage <cit.>.

The initial beliefs at $t=1$ are the degenerate distributions $\mathbf{b}^{(\mathrm{D})}_1(\mathbf{0}_{2|\mathcal{V}|})=1$ and $\mathbf{b}^{(\mathrm{A})}_1(\mathbf{s}_1^{(\mathrm{D})})=1$, where $\mathbf{0}_n$ is the n-dimensional zero-vector and $\mathbf{s}_1^{(\mathrm{D})}$ is given by the infrastructure configuration (see <ref>).

Best response strategies. A defender strategy $\tilde{\pi}_{\mathrm{D}} \in \Pi_{\mathrm{D}}$ is called a best response against $\pi_{\mathrm{A}}\in \Pi_{\mathrm{A}}$ if it maximizes $J$ (<ref>). Similarly, an attacker strategy $\tilde{\pi}_{\mathrm{A}}$ is called a best response against $\pi_{\mathrm{D}}$ if it minimizes $J$ (<ref>). Hence, the best response correspondences are

\begin{align}
B_{\mathrm{D}}(\pi_{\mathrm{A}}) &\triangleq \argmax_{\pi_{\mathrm{D}} \in \Pi_{\mathrm{D}}}\mathbb{E}_{(\pi_{\mathrm{D}},\pi_{\mathrm{A}})}[J]\label{eq:br_defender}\\
B_{\mathrm{A}}(\pi_{\mathrm{D}}) &\triangleq \argmin_{\pi_{\mathrm{A}} \in \Pi_{\mathrm{A}}} \mathbb{E}_{(\pi_{\mathrm{D}},\pi_{\mathrm{A}})}[J]\label{eq:br_attacker}
\end{align}

Optimal strategies. An optimal defender strategy $\pi_{\mathrm{D}}^{*}$ is a best response strategy against any attacker strategy that minimizes $J$. Similarly, an optimal attacker strategy $\pi_{\mathrm{A}}^{*}$ is a best response against any defender strategy that maximizes $J$. Hence, when both players follow optimal strategies, they play best response strategies against each other:

\begin{align}
(\pi_{\mathrm{D}}^{*}, \pi_{\mathrm{A}}^{*}) \in B_{\mathrm{D}}(\pi_{\mathrm{A}}^{*}) \times B_{\mathrm{A}}(\pi_{\mathrm{D}}^{*})\label{eq:minmax_objective}
\end{align}

Since no player has an incentive to change its strategy, $(\pi_{\mathrm{D}}^{*},\pi_{\mathrm{A}}^{*})$ is a Nash equilibrium <cit.>.

We know from game theory that $\Gamma$ has a mixed Nash equilibrium <cit.> and we know from Markov decision theory that $B_{\mathrm{D}}(\pi_{\mathrm{A}})$ and $B_{\mathrm{A}}(\pi_{\mathrm{D}})$ are non-empty <cit.>. Based on these standard results, we state the following theorem.

* A game $\Gamma$ (<ref>) with instantiation described in <ref> has a mixed Nash equilibrium.

* The best response correspondences (<ref>)–(<ref>) in $\Gamma$ with the instantiation described in <ref> satisfy $|B_{\mathrm{D}}(\pi_{\mathrm{A}})|>0$ and $|B_{\mathrm{A}}(\pi_{\mathrm{D}})| > 0$ $\forall (\pi_{\mathrm{A}},\pi_{\mathrm{D}}) \in \Pi_{\mathrm{A}} \times \Pi_{\mathrm{D}}$.

The statement in (A) follows from the following sufficient conditions: (i) $\Gamma$ is stationary, finite, and zero-sum; (ii) $\Gamma$ has public observations; and (iii) $\gamma \in [0,1)$. Due to these conditions, the existence proofs in <cit.>, <cit.>, and <cit.> apply, which show that $\Gamma$ can be modeled as a finite strategic game, for which Nash's theorem applies <cit.>. In the interest of space we do not restate the proof.

To prove (B), we note that obtaining a pair of best response strategies $(\tilde{\pi}_{\mathrm{D}} ,\tilde{\pi}_{\mathrm{A}}) \in B_{\mathrm{D}}(\pi_{\mathrm{A}})\times B_{\mathrm{A}}(\pi_{\mathrm{D}})$ for a given strategy pair $(\pi_{\mathrm{A}},\pi_{\mathrm{D}}) \in \Pi_{\mathrm{A}} \times \Pi_{\mathrm{D}}$ amounts to solving two finite and stationary (Partially Observed Markov Decision Processes) with discounted utilities. It then follows from Markov decision theory that a pair of pure best response strategies $(\tilde{\pi}_{\mathrm{D}}, \tilde{\pi}_{\mathrm{A}})$ exists <cit.> <cit.>. For the sake of brevity we do not restate the proof, which is based on Banach's fixed-point theorem <cit.>.

Notation(s)     Description
$\mathcal{G}, \mathcal{G}_{\mathbf{w}}$     Infrastructure tree, subtree of $\mathbf{w}$

$\mathcal{V}, \mathcal{E}$     Sets of nodes and edges in $\mathcal{G}$

$\mathcal{V}_{\mathbf{w}}, \mathcal{E}_{\mathbf{w}}$     Sets of nodes and edges in $\mathcal{G}_{\mathbf{w}}$

$\mathcal{Z}, \mathcal{W}$     Sets of network zones and workflows

$\mathcal{A}_{\mathrm{D}}, \mathcal{A}_{\mathrm{A}}(\mathbf{s}_t)$     Defender and attacker action spaces at time $t$

$\mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}, \mathcal{A}^{(\mathrm{V})}_{\mathrm{A}}(\mathbf{s}_t)$     Action spaces per node at time $t$, $\mathcal{A}_{\mathrm{k}}=(\mathcal{A}^{(\mathrm{V})}_{\mathrm{k}})^{|\mathcal{V}|}$

$\mathcal{O}^{(\mathrm{V})}$     Observation space per node at time $t$, $\mathcal{O}=(\mathcal{O}^{(\mathrm{V})})^{|\mathcal{V}|}$

$v_{i,t}^{(\mathrm{I})},v_{i,t}^{(\mathrm{Z})},v_{i,t}^{(\mathrm{R})}$     Intrusion state and zone of $i \in \mathcal{V}$ at time $t$

$v_{i,t}^{(\mathrm{R})}$     Reconnaissance state of $i \in \mathcal{V}$ at time $t$

$V_{i,t}^{(\mathrm{I})},V_{i,t}^{(\mathrm{Z})},V_{i,t}^{(\mathrm{R})}$     Random variables with realizations $v_{i,t}^{(\mathrm{I})},v_{i,t}^{(\mathrm{Z})},v_{i,t}^{(\mathrm{R})}$

$\Gamma, \mathcal{N}$     (<ref>), set of players

$\mathcal{S}_{\mathrm{D}}, \mathcal{S}_{\mathrm{A}}$     Defender and attacker state spaces

$\mathcal{S}\triangleq \mathcal{S}_{\mathrm{D}} \times \mathcal{S}_{\mathrm{A}}$     State space

$u, \mathcal{O}$     Utility function and observation space

$\mathbf{s}_t=(\mathbf{s}_t^{(\mathrm{D})},\mathbf{s}_t^{(\mathrm{A})})$     State at time $t$

$\mathbf{a}_t=(\mathbf{a}_t^{(\mathrm{D})},\mathbf{a}_t^{(\mathrm{A})})$     Action at time $t$

$\mathbf{o}_t, \mathbf{u}_t$     Observation, utility  at time $t$

$\mathbf{a}_t^{(\mathrm{k})},\mathbf{h}_t^{(\mathrm{k})}$     Action and history of player $\mathrm{k}$ at time $t$

$\mathcal{B}_{\mathrm{k}}, \mathbf{b}_t^{(\mathrm{k})}$     Belief space and belief state of player $k$

$\tilde{\pi}_{\mathrm{k}}, \tilde{\mathbf{a}}^{(\mathrm{k})}$     Best response strategy and action of player $k$

$\mathbf{S}_t, \mathbf{O}_t, \mathbf{A}_t$     Random vectors with realizations $\mathbf{s}_t, \mathbf{o}_t, \mathbf{a}_t$

$\mathbf{U}_t,\mathbf{B}^{(\mathrm{k})}_t,\mathbf{H}^{(\mathrm{k})}_t$     Random vectors with realizations $\mathbf{u}_t,\mathbf{b}^{(\mathrm{k})}_t,\mathbf{h}^{(\mathrm{k})}_t$

$\pi_{\mathrm{k}}, Z$     Strategy of player $k$, observation distribution

$u^{(\mathrm{w})}_{i,t}$     Workflow utility of node $i$ at time $t$

$\bot, \mathrm{an}(i)$     Null action, set of $i$ and its ancestors in $\mathcal{G}$

$\alpha_{i,t}$     Active status of node $i$ at time $t$

$f_{\mathrm{A}},f_{\mathrm{D}}$     Attacker and defender transition functions

$B_{\mathrm{k}}$     Best response correspondence of player $\mathrm{k}$

$c^{(\mathrm{I})}_{i,t}$     Intrusion cost associated with node $i$ at time $t$

$c^{(\mathrm{A})}$     Action cost function

§ DECOMPOSING THE INTRUSION RESPONSE GAME

In this section we present the main contribution of the paper. We show how the game $\Gamma$ (<ref>) with the instantiation described in <ref> can be recursively decomposed into subgames with optimal substructure <cit.>, which means that a best response (<ref>)–(<ref>) of the original game can be obtained from best responses of the subgames. We further show that best responses of the subgames can be computed in parallel and that the space complexity of a subgame is independent of the number of nodes $|\mathcal{V}|$. Note that the space complexity of the original game increases exponentially with $|\mathcal{V}|$ (see Fig. <ref>).

Growth of $|\mathcal{S}|$, $|\mathcal{O}|$, and $|\mathcal{A}_{\mathrm{k}}|$ in function of the number of nodes $|\mathcal{V}|$, where $\mathrm{k} \in \{\mathrm{D}, \mathrm{A}\}$; the curves are computed using $|\mathcal{Z}|=10$, $|\mathcal{O}^{(\mathrm{V})}|=100$, and $|\mathcal{A}_{\mathrm{D}}^{(\mathrm{V})}|=|\mathcal{A}_{\mathrm{A}}^{(\mathrm{V})}|=10$.

* A game $\Gamma$ (<ref>) with the instantiation described in <ref> can be decomposed into independent workflow subgames $\Gamma^{(\mathbf{w}_1)},\hdots,\Gamma^{(\mathbf{w}_{|\mathcal{W}|})}$. Due to their independence, the subgames have optimal substructure.

* Each subgame $\Gamma^{(\mathbf{w})}$ can be further decomposed into node subgames $(\Gamma^{(i)})_{i \in \mathcal{V}_{\mathbf{w}}}$ with optimal substructure and space complexities independent of $|\mathcal{V}|$.

* For each subgame $\Gamma^{(i)}$, a best response strategy for the defender can be characterized by switching curves, under the assumption that the observation distributions $Z_{\mathbf{O}_1\mid \mathbf{s}^{(\mathrm{A})}},\hdots, Z_{\mathbf{O}_{|\mathcal{V}|}\mid \mathbf{s}^{(\mathrm{A})}}$ (<ref>) are totally positive of order 2 (i.e., <cit.>).

Statements A and B express that $\Gamma$ decomposes into simpler subgames, which consequently can be solved in parallel (see Fig. <ref>). This decomposition implies that the largest game that is tractable on a given compute platform scales linearly with the number of processors. Further, statement C says that a best response strategy for the defender in each subgame can be characterized by switching curves, which can be estimated efficiently.

In the following sections we provide proofs of Thm. <ref>.A–C. The requisite notations are given in Table <ref>.

Theorem <ref>.A

Theorem <ref>.B

Theorem <ref>.C

Illustrations of Thm. <ref>; arrows indicate inputs and outputs; $\oplus$ denotes vector concatenation; $k \in \{\mathrm{D}, \mathrm{A}\}$; $\mathbf{h}^{(\mathrm{k})}_{\mathbf{w},t}\triangleq (\mathbf{h}^{(\mathrm{k})}_{j,t})_{j \in \mathcal{V}_{\mathbf{w}}}$; and $\mathbf{a}^{(\mathrm{k})}_{\mathbf{w},t}\triangleq (\mathbf{a}^{(\mathrm{k})}_{j,t})_{j \in \mathcal{V}_{\mathbf{w}}}$; (a) illustrates that a game strategy $\pi_{\mathrm{k}}$ decomposes into $|\mathcal{W}|$ independent substrategies; (b) illustrates that a workflow strategy $\pi^{(\mathbf{w})}_{\mathrm{k}}$ for $\mathbf{w} \in \mathcal{W}$ decomposes into substrategies $(\pi_{\mathrm{k}}^{(i)})_{i\in\mathcal{V}_{\mathbf{w}}}$ with optimal substructure; (c) provides a geometric illustration of the proof of Thm. <ref>.C, showing a switching curve that partitions the defender's belief space of a node $i \in \mathcal{V}$.

§.§ Proof of Theorem <ref>.A

Following the instantiation of $\Gamma$ described in <ref>, the state, observation, and action spaces factorize as

\begin{align}
\mathcal{S} = (\mathcal{Z}\times \{0,1\}^{2})^{|\mathcal{V}|}, \mathcal{O} = (\mathcal{O}^{(\mathrm{V})})^{|\mathcal{V}|}, \mathcal{A}_{\mathrm{k}} = (\mathcal{A}_{\mathrm{k}}^{(\mathrm{V})})^{|\mathcal{V}|}\label{eq:factorization:a}
\end{align}

for player $\mathrm{k} \in \{\mathrm{D}, \mathrm{A}\}$, where $\mathcal{O}^{(\mathrm{V})}$, $\mathcal{A}_{\mathrm{D}}^{(\mathrm{V})}$, and $\mathcal{A}_{\mathrm{A}}^{(\mathrm{V})}$ denote the local observation and action spaces for each node.

Since each node belongs to exactly one workflow, (<ref>) implies that $\Gamma$ can be decomposed into subgames $\Gamma^{(\mathbf{w}_1)},\hdots,\Gamma^{(\mathbf{w}_{|\mathcal{W}|})}$. To show that the subgames are independent, it suffices to show that they are observation-independent, transition-independent, and utility-independent <cit.>.

From (<ref>) we have

\begin{align}
Z\big(\mathbf{o}_{i,t+1} \mid \mathbf{s}^{(\mathrm{D})}_{t+1},\mathbf{s}^{(\mathrm{A})}_{t+1}\big) &= Z\big(\mathbf{o}_{i,t+1} \mid \mathbf{s}^{(\mathrm{D})}_{i,t+1},\mathbf{s}^{(\mathrm{A})}_{i,t+1}\big)
\end{align}

for all $\mathbf{o}_{i,t+1} \in \mathcal{O}$, $\mathbf{s}_{t+1}\in \mathcal{S}$, and $t \geq 1$, which implies observation independence across nodes $i \in \mathcal{V}$ and therefore across workflows <cit.>.

From the definitions in <ref> and (<ref>)–(<ref>) we have

\begin{align}
f_{\mathrm{D}}(\mathbf{s}^{(\mathrm{D})}_{i,t+1} | \mathbf{s}^{(\mathrm{D})}_{t},\mathbf{a}^{(\mathrm{D})}_{t}) &= f_{\mathrm{D}}(\mathbf{s}^{(\mathrm{D})}_{i,t+1} | \mathbf{s}^{(\mathrm{D})}_{i,t},\mathbf{a}^{(\mathrm{D})}_{i,t})\nonumber\\
f_{\mathrm{A}}(\mathbf{s}^{(\mathrm{A})}_{i,t+1} | \mathbf{s}^{(\mathrm{A})}_{t},\mathbf{a}^{(\mathrm{A})}_{t},\mathbf{a}^{(\mathrm{D})}_{t}) &= f_{\mathrm{A}}(\mathbf{s}^{(\mathrm{A})}_{i,t+1} | \mathbf{s}^{(\mathrm{A})}_{i,t},\mathbf{a}^{(\mathrm{A})}_{i,t},\mathbf{a}^{(\mathrm{D})}_{i,t})\nonumber
\end{align}

for all $\mathbf{s}_{i,t} \in \mathcal{S},\mathbf{a}_{i,t} \in \mathcal{A}, i \in \mathcal{V}$, and $t \geq 1$, which implies transition independence across nodes $i \in \mathcal{V}$ and therefore across workflows <cit.>.

Following (<ref>) and the definition of $u_{i,t}^{(\mathrm{W})}$ (see <ref>) we can rewrite $u(\mathbf{s}_t,\mathbf{a}_t^{(\mathrm{D})})$ as

\begin{align}
u(\mathbf{s}_t,\mathbf{a}_t^{(\mathrm{D})})&=\sum_{\mathbf{w}\in \mathcal{W}}\overbrace{\sum_{i\in \mathcal{V}_{\mathbf{w}}}\eta u_{i,t}^{(\mathrm{W})}-c_{i,t}^{(\mathrm{I})}(\mathbf{a}^{(\mathrm{D})}_{i,t},v^{(\mathrm{I})}_{i,t})}^{\triangleq u_{\mathbf{w}}}\nonumber\\
&=\sum_{\mathbf{w}\in \mathcal{W}} u_{\mathbf{w}}\Big(\big(\mathbf{s}_{i,t},\mathbf{a}^{(\mathrm{D})}_{i,t}\big)_{i \in \mathcal{V}_{\mathbf{w}}}\Big)\label{eq:workflow_util}
\end{align}

The final expression in (<ref>) is a sum of workflow utility functions, each of which depends only on the states and actions of one workflow. Hence, $\Gamma^{(\mathbf{w}_1)},\hdots,\Gamma^{(\mathbf{w}_{|\mathcal{W}|})}$ are utility independent <cit.>.

§.§ Proof of Theorem <ref>.B

Our goal is to show that a workflow subgame $\Gamma^{(\mathbf{w})}$ decomposes into node-level subgames with optimal substructure. That is, we aim to show that a best response in $\Gamma^{(\mathbf{w})}$ can be constructed from best responses of the subgames.

Following the description in <ref>, we know that the nodes in a workflow are connected in a tree and that the utility generated by a node $i$ depends on the number of active nodes in the subtree rooted at $i$. Taking into account this tree structure and the definition of the utility function, we decompose $\Gamma^{(\mathbf{w})}$ into node subgames $(\Gamma^{(i)})_{i \in \mathcal{V}_{\mathbf{w}}}$ where each subgame depends only on the local state and action of a single node. It follows from (<ref>) that this decomposition is feasible and that the space complexity of a subgame is independent of $|\mathcal{V}|$. Further, we know from Thm. <ref>.A that the subgames are transition-independent and observation-independent but utility-dependent. To prove optimal substructure it therefore suffices to show that it is possible to redefine the utility functions for the subgames such that at each time $t$, the best response action in $\Gamma^{(\mathbf{w})}$ for any node $i$ is also a best response in $\Gamma^{(i)}$ and vice versa. For the sake of brevity we give the proof for the defender only. The proof for the attacker is analogous. In this proof, for better readability, we omit the constants $\gamma,\eta$ and use the shorthand notations $\mathbf{s}_{\mathbf{w},t}^{(\mathrm{D})} \triangleq (\mathbf{s}^{(\mathrm{D})}_{j,t})_{j \in \mathcal{V}_{\mathbf{w}}}$, $\mathbf{b}_{\mathbf{w},t}^{(\mathrm{D})} \triangleq (\mathbf{b}^{(\mathrm{D})}_{j,t})_{j \in \mathcal{V}_{\mathbf{w}}}$, $\mathscr{V}\triangleq \mathscr{V}_{\mathrm{D},\pi_{\mathrm{A}}}^{*}$, and $\tau \in \argmin_{k>t}\mathbf{a}^{(\mathrm{D})}_k\neq \bot$, where $\mathscr{V}$ is the value function <cit.>. Further, we use $\mathrm{an}(i)$ to denote the set of node $i$ and its ancestors in the infrastructure graph $\mathcal{G}$.

From Bellman's optimality equation <cit.>, a best response action for node $i$ at time $t$ in $\Gamma^{(\mathbf{w})}$ against an attacker strategy $\pi_{\mathrm{A}}$ is given by

\begin{align}
&\argmax_{\mathbf{a}_{i,t}^{(\mathrm{D})}\in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}}\Biggl[\underset{\pi_{\mathrm{A}}}{\mathbb{E}}\biggl[\mathbf{U}_{t} + \mathscr{V}(\mathbf{S}^{(\mathrm{D})}_{t+1}, \mathbf{B}^{(\mathrm{D})}_{t+1}) \Bigl\vert\mathbf{s}^{(\mathrm{D})}_t, \mathbf{b}^{(\mathrm{D})}_t, \mathbf{a}_{i,t}^{(\mathrm{D})}\biggr]\Biggr]\nonumber\\
&\numeq{a}\argmax_{\mathbf{a}_{i,t}^{(\mathrm{D})} \in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}}\Biggl[\underset{\pi_{\mathrm{A}}}{\mathbb{E}}\biggl[-c^{(\mathrm{I})}_{i,t} + \mathscr{V}(\mathbf{S}^{(\mathrm{D})}_{t+1}, \mathbf{B}^{(\mathrm{D})}_{t+1}) \Bigl\vert\mathbf{s}^{(\mathrm{D})}_t, \mathbf{b}^{(\mathrm{D})}_t, \mathbf{a}_{i,t}^{(\mathrm{D})}\biggr]\Biggr]\nonumber\\
&\numeq{b}\argmax_{\mathbf{a}_{i,t}^{(\mathrm{D})}\in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}}\Biggl[\underset{\pi_{\mathrm{A}}}{\mathbb{E}}\biggl[-c^{(\mathrm{I})}_{i,t} + \sum_{k=t+1}^{\infty}\sum_{j \in \mathcal{V}_{\mathbf{w}}}\mathbf{U}_{j,k} \Bigl\vert\overbrace{\mathbf{s}^{(\mathrm{D})}_{\mathbf{w},t}, \mathbf{b}^{(\mathrm{D})}_{\mathbf{w},t}, \mathbf{a}_{i,t}^{(\mathrm{D})}}^{\triangleq \kappa}\biggr]\Biggr]\nonumber\\
&\numeq{c}\argmax_{\mathbf{a}_{i,t}^{(\mathrm{D})}\in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}}\Biggl[\underset{\pi_{\mathrm{A}}}{\mathbb{E}}\biggl[-c^{(\mathrm{I})}_{i,t} + \sum_{k=t+1}^{\tau}\sum_{j \in \mathcal{V}_{\mathbf{w}}}\mathbf{U}_{j,k}\Bigl\vert\kappa\biggr]\Biggr]\nonumber\\
&\numeq{d}\argmax_{\mathbf{a}_{i,t}^{(\mathrm{D})}\in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}}\Biggl[\underset{\pi_{\mathrm{A}}}{\mathbb{E}}\biggl[-c^{(\mathrm{I})}_{i,t} + \sum_{k=t+1}^{\tau}\sum_{j \in \mathrm{an}(i)}\mathbf{U}_{j,k}\Bigl\vert\kappa\biggr]\Biggr]\nonumber\\
&\numeq{e} \argmax_{\mathbf{a}_{i,t}^{(\mathrm{D})}\in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}}\Biggl[\underset{\pi_{\mathrm{A}}}{\mathbb{E}}\biggl[-c^{(\mathrm{I})}_{i,t} + \sum_{k=t+1}^{\tau}\sum_{j \in \mathrm{an}(i)} u^{(\mathrm{W})}_{j,k} - c_{j,k}^{(\mathrm{I})}\Bigl\vert\kappa\biggr]\Biggr]\nonumber\\
&\numeq{f} \argmax_{\mathbf{a}_{i,t}^{(\mathrm{D})}\in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}}\Biggl[\underset{\pi_{\mathrm{A}}}{\mathbb{E}}\biggl[\overbrace{-c_{i,t}^{(\mathrm{I})} + \sum_{k=t+1}^{\tau}|\mathrm{an}(i)|\alpha_{i,t+1}-c_{i,k}^{(\mathrm{I})}}^{\triangleq \omega}\Bigl\vert\kappa\biggr]\Biggr] \nonumber\\
&\numeq{g} \argmax_{\mathbf{a}_{i,t}^{(\mathrm{D})}\in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}}\Biggl[\underset{\pi_{\mathrm{A}}}{\mathbb{E}}\biggl[\omega \text{ }\Bigl\vert \text{ }\mathbf{s}_{i,t}^{(\mathrm{D})}, \mathbf{b}_{i,t}^{(\mathrm{D})}, \mathbf{a}_{i,t}^{(\mathrm{D})}\biggr]\Biggr]
\label{eq:lemma_3_proof}
\end{align}

where $\mathbf{U}_t$ denotes the vector of utilities for all nodes at time $t$. (a) holds because $(\mathbf{U}_{j,t})_{j \in \mathcal{V}\setminus \{i\}}$ and $u^{(\mathrm{W})}_{i,t}$ are independent of $\mathbf{a}_{i,t}^{(\mathrm{D})}$ and therefore does not affect the maximization; (b) follows from the utility independence across workflows (Thm. <ref>.A) and the definition of the value function $\mathscr{V}$ <cit.>; (c) holds because any $\mathbf{a}^{(\mathrm{D})}_{i,t}$ except $\bot$ leads to $\mathbf{s}^{(\mathrm{A})}_{i,t+1}=(0,0)$, which means that all state variables at time $k>\tau$ are independent of $\mathbf{a}_{i,t}^{(\mathrm{D})}$ and can therefore be moved outside the $\argmax$ operator; (d) follows because $(\mathbf{U}_{j,t})_{j \in \mathcal{V} \setminus \mathrm{an}(i)}$ is independent of $\mathbf{a}_{i,t}^{(\mathrm{D})}$; (e) is an expansion of $(\mathbf{U}_{j,k})_{j\in \mathrm{an}(i),k\in \{t+1,\hdots,\tau\}}$ based on (<ref>); and (f)-(g) follow because the terms in $(u^{(\mathrm{W})}_{j,k})_{j \in \mathrm{an}(i),k \in \{t+1,\hdots,\tau\}}$ that depend on $\mathbf{a}^{(\mathrm{D})}_{i,t}$ equal $k|\mathrm{an}(i)|\alpha_{t+1,i}$, where $k$ is the constant of proportionality (see <ref>). (Recall that $\alpha_{i,t}=1$ if node $i$ is active at time $t$ and $\alpha_{i,t}=0$ otherwise.)

The final expression in (<ref>) depends only on local information related to node $i$. This means that we can use it to define utility functions of the subgames $(\Gamma^{(i)})_{i \in \mathcal{V}_{\mathbf{w}}}$ such that they become utility-independent. Further, since the maximizer of the final expression in (<ref>) is also a maximizer of the first expression, it follows that a a best response in $\Gamma^{(i)}$ is also a best response for node $i$ in $\Gamma^{(\mathbf{w})}$ and thus in $\Gamma$ (Thm. <ref>.A). Hence the subgames $(\Gamma^{(i)})_{i \in \mathcal{V}_{\mathbf{w}}}$ have optimal substructure.

§.§ Proof of Theorem <ref>.C

The idea behind this proof is that the problem of selecting which defensive action to apply in a subgame $\Gamma^{(i)}$ (Thm. <ref>.B) against a given attacker strategy can be separated from the problem of deciding when to apply it. Through this separation, we can analyze the latter problem using optimal stopping theory. Applying a recent result by Krishnamurthy <cit.>, the optimal stopping strategy in $\Gamma^{(i)}$ can be characterized by switching curves.

We perform the above separation by decomposing $\mathbf{a}^{(\mathrm{D})}_{i,t}$ into two subactions: $\mathbf{a}^{(\mathrm{D},1)}_{i,t}$ and $\mathbf{a}^{(\mathrm{D},2)}_{i,t}$ which realize $\mathbf{A}^{(\mathrm{D},1)}_{i,t}$ and $\mathbf{A}^{(\mathrm{D},2)}_{i,t}$. The first subaction $\mathbf{a}^{(\mathrm{D},1)}_{i,t}\neq \bot$ determines the defensive action and the second subaction $\mathbf{a}^{(\mathrm{D},2)}_{i,t} \in \{\mathrm{S},\mathrm{C}\}$ determines when to take it. Specifically, if $\mathbf{a}^{(\mathrm{D},2)}_{i,t}=\mathrm{C}$, then $\mathbf{a}^{(\mathrm{D})}_{i,t}=\bot$, otherwise $\mathbf{a}^{(\mathrm{D})}_{i,t}=\mathbf{a}^{(\mathrm{D},1)}_{i,t}$. Using this action decomposition, at each time $t$, a strategy $\pi_{\mathrm{D}}^{(i)}$ in $\Gamma^{(i)}$ is a joint distribution over $\mathbf{A}^{(\mathrm{D},1)}_{i,t}$ and $\mathbf{A}^{(\mathrm{D},2)}_{i,t}$, which means that it can be represented in an auto-regressive manner as

\begin{align}
&\pi_{\mathrm{D}}^{(i)}(\mathbf{a}^{(\mathrm{D},1)}_{i,t}, \mathbf{a}^{(\mathrm{D},2)}_{i,t} \mid \mathbf{h}^{(\mathrm{k})}_{i,t}) \label{eq:stopping_1}\\
&\numeq{a} \pi_{\mathrm{D}}^{(i)}(\mathbf{a}^{(\mathrm{D},1)}_{i,t} \mid \mathbf{h}^{(\mathrm{D})}_{i,t})\pi_{\mathrm{D}}^{(i)}(\mathbf{a}^{(\mathrm{D},2)}_{i,t} \mid  \mathbf{h}^{(\mathrm{D})}_{i,t}, \mathbf{a}^{(\mathrm{D},1)}_{i,t})\nonumber\\
&\numeq{b} \pi_{\mathrm{D}}^{(i)}(\mathbf{a}^{(\mathrm{D},1)}_{i,t} \mid \mathbf{b}^{(\mathrm{D})}_{i,t},\mathbf{s}^{(\mathrm{D})}_{i,t})\pi_{\mathrm{D}}^{(i)}(\mathbf{a}^{(\mathrm{D},2)}_{i,t} \mid \mathbf{b}^{(\mathrm{D})}_{i,t}, \mathbf{s}^{(\mathrm{D})}_{i,t}, \mathbf{a}^{(\mathrm{D},1)}_{i,t})  \nonumber \\
&\numeq{c} \pi_{\mathrm{D}}^{(i)}(\mathbf{a}^{(\mathrm{D},1)}_{i,t} \mid \mathbf{s}^{(\mathrm{D})}_{i,t})\pi_{\mathrm{D}}^{(i)}(\mathbf{a}^{(\mathrm{D},2)}_{i,t} \mid \mathbf{b}^{(\mathrm{D})}_{i,t}, \mathbf{s}^{(\mathrm{D})}_{i,t}, \mathbf{a}^{(\mathrm{D},1)}_{i,t})\nonumber
\end{align}

where (a) follows from the chain rule of probability; (b) holds because $(\mathbf{s}^{(\mathrm{D})}_{i,t},\mathbf{b}^{(\mathrm{D})}_{i,t})$ is a sufficient statistic for $\mathbf{H}^{(\mathrm{D})}_{i,t}$ <cit.>; and (c) follows because

\begin{align}
&\argmax_{\mathbf{a}^{(\mathrm{D},1)}_{i,t} \in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}\setminus \bot}\Biggl[\eta |\mathrm{an}(i)|\alpha_{i,t+1} - c^{(\mathrm{I})}_{i,t}(v^{(\mathrm{I})}_{i,t}, \mathbf{a}^{(\mathrm{D},1)}_{i,t}) + \label{eq:belief_indep}\\
&\quad\quad\quad\quad\quad\gamma \mathbb{E}\biggl[\mathscr{V}(\mathbf{S}^{(\mathrm{D})}_{i,t+1}, \mathbf{B}^{(\mathrm{D})}_{i,t+1})\text{ }\Bigl\vert\text{ } \mathbf{s}^{(\mathrm{D})}_{i,t},\mathbf{b}^{(\mathrm{D})}_{i,t}, \mathbf{a}^{(\mathrm{D},1)}_{i,t}\biggr]\Biggr]\nonumber\\
&\numeq{a}\argmax_{\mathbf{a}^{(\mathrm{D},1)}_{i,t} \in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}\setminus \bot}\Biggl[\eta |\mathrm{an}(i)|\alpha_{i,t+1} - c^{(\mathrm{A})}(\mathbf{a}^{(\mathrm{D},1)}_{i,t}) + \nonumber\\
&\quad\quad\quad\quad\quad\gamma \mathbb{E}\biggl[\mathscr{V}(\mathbf{S}^{(\mathrm{D})}_{i,t+1}, \mathbf{B}^{(\mathrm{D})}_{i,t+1})\text{ }\Bigl\vert\text{ } \mathbf{s}^{(\mathrm{D})}_{i,t},\mathbf{b}^{(\mathrm{D})}_{i,t}, \mathbf{a}^{(\mathrm{D},1)}_{i,t}\biggr]\Biggr]\nonumber\\
&\numeq{b}\argmax_{\mathbf{a}^{(\mathrm{D},1)}_{i,t} \in \mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}\setminus \bot}\Biggl[\eta |\mathrm{an}(i)|\alpha_{i,t+1} - c^{(\mathrm{A})}(\mathbf{a}^{(\mathrm{D},1)}_{i,t}) \nonumber\\
&\quad\quad\quad\quad\quad\quad\quad\gamma \mathbb{E}\biggl[\mathscr{V}(\mathbf{S}^{(\mathrm{D})}_{i,t+1}, \mathbf{e}_1)\text{ }\Bigl\vert\text{ } \mathbf{s}^{(\mathrm{D})}_{i,t}, \mathbf{a}^{(\mathrm{D},1)}_{i,t}\biggr]\Biggr]\nonumber
\end{align}

which means that $\mathbf{a}^{(\mathrm{D},1)}_{i,t}\neq \bot$ is independent of $\mathbf{B}_{i,t}^{(\mathrm{D})}$. The first statement in (<ref>) is the Bellman equation <cit.>; (a) holds because $V^{(\mathrm{I})}_{i,t}$ is independent of $\mathbf{a}^{(\mathrm{D},1)}_{i,t}$; and (b) is true because any $\mathbf{a}^{(\mathrm{D},1)}_{i,t}\neq \bot$ leads to $\mathbf{S}^{(\mathrm{A})}_{i,t+1}=(0,0)$ and thus to $\mathbf{B}^{(\mathrm{D})}_{i,t+1}=\mathbf{e}_1=(1,0,0)$. (Recall that the belief space $\mathcal{B}^{(i)}_{\mathrm{D}}$ is the two-dimensional unit simplex.)

The strategy decomposition in (<ref>) means that we can obtain a best response strategy in $\Gamma^{(i)}$ by jointly optimizing two substrategies: $\pi_{\mathrm{D}}^{(i,1)}$ and $\pi_{\mathrm{D}}^{(i,2)}$. The former corresponds to solving an  $\mathscr{M}^{(\mathrm{D},1)}$ with state space $\mathbf{s}_{i}^{(\mathrm{D})} \in \mathcal{Z}$ and the latter corresponds to solving a set of optimal stopping s $(\mathscr{M}^{(\mathrm{D},2)}_{i,s^{(\mathrm{D})},a^{(\mathrm{D})}})_{s^{(\mathrm{D})} \in \mathcal{Z}, a^{(\mathrm{D})} \in \mathcal{A}_{\mathrm{D}}^{(\mathrm{V})}}$ with state space $\mathbf{s}_{i}^{(\mathrm{A})} \in \{(0,0),(1,0),(1,1)\}=\{0,1,2\}$.

Each stopping problem can be defined with a single stop action rather than multiple stop actions <cit.> because

\begin{align}
&\argmax_{\pi_{\mathrm{D}} \in \Pi^{(i,2)}_{\mathrm{D}}}\Biggl[\mathbb{E}_{\pi_{\mathrm{D}}}\biggl[\sum_{t=1}^{\infty}\gamma^{t-1}\mathbf{U}_{i,2,t} \text{ }\Bigl\vert\text{ } \mathbf{B}^{(\mathrm{D})}_{i,1}=\mathbf{e}_1\biggr]\Biggr] \nonumber\\
&=\argmax_{\pi_{\mathrm{D}} \in \Pi^{(i,2)}_{\mathrm{D}}}\Biggl[\mathbb{E}_{\pi_{\mathrm{D}}}\biggl[\sum_{t=1}^{\tau_1}\gamma^{t-1}\mathbf{U}_{i,2,t} \text{ }\Bigl\vert\text{ } \mathbf{B}^{(\mathrm{D})}_{i,1}=\mathbf{e}_1\biggr] +\nonumber\\
&\quad\quad\quad\mathbb{E}_{\pi_{\mathrm{D}}}\biggl[\sum_{t=\tau_1+1}^{\tau_2}\gamma^{t-1}\mathbf{U}_{i,2,t} \text{ }\Bigl\vert\text{ } \mathbf{B}^{(\mathrm{D})}_{i,\tau_1+1}=\mathbf{e}_1\biggr] + \hdots \Biggr]\nonumber\\
&=\argmax_{\pi_{\mathrm{D}} \in \Pi^{(i,2)}_{\mathrm{D}}}\Biggl[\mathbb{E}_{\pi_{\mathrm{D}}}\biggl[\sum_{t=1}^{\tau_1}\gamma^{t-1}\mathbf{U}_{i,2,t} \text{ }\Bigl\vert\text{ } \mathbf{B}^{(\mathrm{D})}_{i,1}=\mathbf{e}_1\biggr]\Biggr] \label{eq:stopping_indep}
\end{align}

where $\Pi^{(i,2)}_{\mathrm{D}}$, $\mathbf{U}_{i,2,t}$, and $\tau_1, \tau_2, \hdots $ denote the strategy space, utility, and stopping times in $\mathscr{M}^{(\mathrm{D},2)}_{i,s^{(\mathrm{D})},a^{(\mathrm{D})}}$. Note that the belief space $\mathcal{B}^{(i)}_{\mathrm{D}}$ for each stopping problem is the $2$-dimensional unit simplex and that $\mathbf{B}^{(\mathrm{D})}_{i,\tau_j+1}=\mathbf{e}_1=(1,0,0)$ for each stopping time $\tau_j$ since $\mathbf{a}^{(\mathrm{D},2)}_{i,\tau_j}=\mathrm{S}\implies \mathbf{s}^{(\mathrm{A})}_{i,\tau_j+1}=(0,0)$.

The transition matrices for each stopping problem are of the form:

\begin{align}
\begin{bmatrix}
1-p & p & 0\\
0 & 1-q & q\\
0 & 0 & 1
\end{bmatrix}
\quad \text{and}\quad
\begin{bmatrix}
1 & 0 & 0\\
1 & 0 & 0\\
1 & 0 & 0
\end{bmatrix}\label{eq:p_tp2}
\end{align}

where $p$ is the probability that the attacker performs reconnaissance and $q$ is the probability that the attacker compromises the node. The left matrix in (<ref>) relates to $\mathbf{a}_{i,t}^{(\mathrm{D},2)}=\mathrm{C}$ and the right matrix relates to $\mathbf{a}_{i,t}^{(\mathrm{D},2)}=\mathrm{S}$. The non-zero second order minors of the matrices are $(1-p)(1-q)$, $pq$, $1-q$, $1-p$, $p$, and $(1-p)q$, which implies that the matrices are <cit.>. Further, it follows from (<ref>) that the utility function of the stopping problems satisfies

\begin{align*}
\mathbf{u}_{j,2}(0,a) \geq \mathbf{u}_{j,2}(1,a) \geq \mathbf{u}_{j,2}(2,a)
\end{align*}

for $a \in \{\mathrm{S}, \mathrm{C}\}$ and that

\begin{align*}
\mathbf{u}_{j,2}(s,\mathrm{S})-\mathbf{u}_j(s,\mathrm{C}) &\geq \mathbf{u}_{j,2}(2,\mathrm{S})-\mathbf{u}_{j,2}(2,\mathrm{C})\\
\mathbf{u}_{j,2}(0,\mathrm{S})-\mathbf{u}_j(0,C) &\geq \mathbf{u}_{j,2}(s,\mathrm{S})-\mathbf{u}_{j,2}(s,\mathrm{C})
\end{align*}

for all $s \in \mathcal{S}^{(j),2}$. Since the distributions $Z_{\mathbf{O}_1\mid \mathbf{s}^{(\mathrm{A})}},\hdots, Z_{\mathbf{O}_{|\mathcal{V}|}\mid \mathbf{s}^{(\mathrm{A})}}$ are by assumption it then follows from <cit.> that there exists a switching curve $\Upsilon$ that partitions $\mathcal{B}_{\mathrm{D}}^{(i)}$ into two individually connected regions: a stopping set $\mathscr{S}^{(i)}_{\mathrm{D}}$ where $\mathbf{a}_{i,t}^{(\mathrm{D},2)}=\mathrm{S}$ is a best response and a continuation set $\mathscr{C}^{(i)}_{\mathrm{D}}$ where $\mathbf{a}_{i,t}^{(\mathrm{D},2)}=\mathrm{C}$ is a best response (see Fig. <ref>).

The argument behind the existence of a switching curve is as follows <cit.>. On any line segment $\mathcal{L}(\mathbf{e}_1,\widehat{\mathbf{b}}^{(\mathrm{D})})$ in $\mathcal{B}_{\mathrm{D}}^{(i)}$ that starts at $\mathbf{e}_1$ and ends at the subsimplex joining $\mathbf{e}_2$ and $\mathbf{e}_3$ (denoted with $\widehat{\mathbf{b}}^{(\mathrm{D})} \in \mathcal{B}_{\mathrm{D},\mathbf{e}_1}^{(i)}$), all belief states are totally ordered with respect to the Monotone Likelihood Ratio () order <cit.>. As a consequence, Topkis's theorem <cit.> implies that the optimal strategy on $\mathcal{L}(\mathbf{e}_1,\widehat{\mathbf{b}}^{(\mathrm{D})})$ is monotone with respect to the order. Consequently, there exists a threshold belief state $\alpha_{\widehat{\mathbf{b}}^{(\mathrm{D})}}$ on $\mathcal{L}(\mathbf{e}_1,\widehat{\mathbf{b}}^{(\mathrm{D})})$ where the optimal strategy switches from $\mathrm{C}$ to $\mathrm{S}$. Since $\mathcal{B}_{\mathrm{D}}^{(i)}$ can be covered by the union of lines $\mathcal{L}(\mathbf{e}_1,\widehat{\mathbf{b}}^{(\mathrm{D})})$, the thresholds $\alpha_{\widehat{\mathbf{b}}^{(\mathrm{D})}_1},\alpha_{\widehat{\mathbf{b}}^{(\mathrm{D})}_2},\hdots$ yield a switching curve $\Upsilon$.

§ FINDING NASH EQUILIBRIA OF THE
DECOMPOSED INTRUSION RESPONSE GAME

To find a Nash equilibrium of $\Gamma$ (<ref>) we develop a fictitious self-play algorithm called Decompositional Fictitious Self-Play (), which estimates Nash equilibria based on the decomposition presented above. The pseudocode is listed in Alg. <ref>. (In Alg. <ref>, $\oplus$ denotes vector concatenation, $-\mathrm{k}$ denotes the opponent of player $\mathrm{k}$, and $\mathscr{M}^{(\mathrm{k})}_{i}$ denotes the best response of $\mathrm{k}$ in $\Gamma^{(i)}$ (Thm <ref>).)

Forpin parallel fordo
DoParalleldo in parallelend

p-solver: a solver,

$\delta$: convergence criterion, $\Gamma$: the

An approximate Nash equilibrium $(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})$

(p-solver, $\delta$, $\Gamma$)
Initialize $\pi_{\mathrm{D}},\pi_{\mathrm{A}},\widehat{\delta}$
$\widehat{\delta} \geq \delta$
$\mathrm{k} \in \{\mathrm{D}, \mathrm{A}\}$
$\bm{\pi}_{\mathrm{k}} \leftarrow $local-brs$(\textsc{p-solver}, \Gamma, \mathrm{k}, \pi_{-\mathrm{k}})$
$\tilde{\pi}_{\mathrm{k}} \leftarrow $composite-strategy$(\Gamma, \bm{\pi}_{\mathrm{k}})$
$\pi_{\mathrm{k}} \leftarrow $average-strategy$(\pi_{\mathrm{k}}, \tilde{\pi}_{\mathrm{k}})$

$\widehat{\delta} \leftarrow $exploitability($\tilde{\pi}_{\mathrm{D}}$,$\tilde{\pi}_{\mathrm{A}}$) (see (<ref>))

$(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})$

local-brs$(\textsc{p-solver}, \Gamma, \mathrm{k}, \pi_{-\mathrm{k}})$
$\bm{\pi}_{\mathrm{k}} \leftarrow ()$
$\mathbf{w} \in \mathcal{W}$, $(i) \in \mathcal{V}_{\mathbf{w}}$
$\bm{\pi}_{\mathrm{k}} \leftarrow \bm{\pi}_{\mathrm{k}} \oplus $ p-solver($\mathscr{M}^{(\mathrm{k})}_{i}, \pi_{-\mathrm{k}}$)

composite-strategy$(\Gamma, \bm{\pi}_{\mathrm{k}})$
$\pi_{\mathrm{k}} \leftarrow $Procedure ($\mathbf{s}_t^{(\mathrm{k})}$, $\mathbf{b}_t^{(\mathrm{k})}$)
$\mathbf{a}^{(\mathrm{k})}_t \leftarrow ()$
$\mathbf{w} \in \mathcal{W}$, $i \in \mathcal{V}_{\mathbf{w}}$
$\mathbf{a}^{(\mathrm{k})}_t \leftarrow \mathbf{a}^{(\mathrm{k})}_t \oplus (\bm{\pi}_{\mathrm{k}}^{(i)}(\mathbf{s}_{i,t}^{(\mathrm{k})}, \mathbf{b}_{i,t}^{(\mathrm{k})}))$

implements the fictitious play process described in <cit.> and generates a sequence of strategy profiles $(\pi_{\mathrm{D}}, \pi_{\mathrm{A}})$, $(\pi^{\prime}_{\mathrm{D}}$, $\pi^{\prime}_{\mathrm{A}})$, $\hdots$ that converges to a Nash equilibrium $(\pi^{*}_{\mathrm{D}}, \pi^{*}_{\mathrm{A}})$ <cit.>. During each step of this process, learns best responses against the players' current strategies and then updates both players' strategies (lines $7$–$11$ in Alg. <ref>). To obtain the best responses, it first finds best responses for the node subgames as constructed in the proof of Thm. <ref>.B (lines $14$–$18$), and then it combines them using the method described in <ref> (lines $19$–$25$).

Finding best responses for node subgames amounts to solving . The principal method for solving is dynamic programming <cit.>. Dynamic programming is however intractable in our case, as demonstrated in Fig. <ref>. To find the best responses we instead resort to approximation algorithms. More specifically, we use the Proximal Policy Optimization () algorithm <cit.> to find best responses for the attacker, and we use a combination of dynamic programming and stochastic approximation to find best responses for the defender. In particular, to find best responses for the defender, we first solve the  defined in <ref> via the value iteration algorithm <cit.>, which can be done efficiently due to full observability. After solving the , we approximate the optimal switching curves defined in the proof of Thm. <ref>.C (<ref>) with the following linear approximation <cit.>.

\begin{align}
\pi_{\mathrm{D}}(\mathbf{b}^{(\mathrm{D})}) &=
\begin{dcases}
\mathrm{S} & \text{if }
\begin{bmatrix}
0 & 1 & \bm{\theta}
\end{bmatrix}
\begin{bmatrix}
\end{bmatrix}
> 0
\\
\mathrm{C} & \text{otherwise}
\end{dcases}\label{eq:linear_approx} \\
&\text{subject to } \bm{\theta} \in \mathbb{R}^2,\text{ }\bm{\theta}_2 > 0,\text{ and }\bm{\theta}_1 \geq 1 \nonumber
\end{align}

The coefficients $\bm{\theta}$ in (<ref>) are estimated through the stochastic approximation algorithm in <cit.> and <cit.>.

The digital twin is a virtual replica of the target infrastructure and is used in our framework for evaluation and data collection <cit.>.

Empirical observation distributions $\widehat{Z}_{\mathbf{O}_1}, \hdots, \widehat{Z}_{\mathbf{O}_{|\mathcal{V}|}}$ as estimates of $Z_{\mathbf{O}_1}, \hdots, Z_{\mathbf{O}_{|\mathcal{V}|}}$ in the target infrastructure (depicted in Fig. <ref>); $\mathbf{O}_{i}$ is a random variable representing the number of alerts related to node $i\in \mathcal{V}$, weighted by priority; the x-axes show the local observation spaces $\mathcal{O}^{(\mathrm{V})}$ for each node; the y-axes show $Z(\mathbf{O}_{i} \mid \mathbf{S}_{i})$ (<ref>).

§ DIGITAL TWIN AND SYSTEM IDENTIFICATION

The algorithm described above approximates a Nash equilibrium of $\Gamma$ (<ref>) by simulating games and updating both players' strategies through reinforcement learning and dynamic programming. To identify the parameters required to instantiate these simulations and to evaluate the learned strategies, we use a digital twin of the target infrastructure (see Fig. <ref>). This section describes the digital twin (<ref>) and the identification process (<ref>).

§.§ Creating a Digital Twin of the Target Infrastructure

We create a digital twin of the target infrastructure shown in Fig. <ref> through an emulation system. Documentation of this emulation system is available in <cit.>; the source code is available at <cit.>; and a video demonstration is available at <cit.>.

The process of creating the digital twin involves two main tasks. The first task is to replicate relevant parts of the physical infrastructure that is emulated, such as physical resources, network interfaces, and network conditions. This task is described in <ref>. The second task is to emulate actors in the digital twin (e.g., the attacker, the defender, and the client population). We describe this task in <ref>.

§.§.§ Emulating physical resources

The physical resources of the target infrastructure are emulated through the following steps.

Emulating physical hosts. Physical hosts are emulated with Docker containers <cit.>, i.e., lightweight executable packages that include runtime systems, code, system tools, system libraries, and configurations. Resource allocation to containers, e.g., and memory, is enforced using . The software functions running inside the containers replicate important components of the target infrastructure, such as, web servers, databases, the <cit.>, and the controller <cit.>.

Emulating physical switches. Physical switches are emulated with Docker containers that run Open vSwitch () <cit.> and may connect to a controller through the protocol <cit.>. (Since the switches are programmed through flow tables, they can act either as classical layer 2 switches or as routers, depending on the flow table configurations.)

Emulating physical network links. Network connectivity is emulated with virtual links implemented by Linux bridges. Network isolation between virtual containers on the same physical host is achieved through network namespaces, which create logical copies of the physical host's network stack. To connect containers on different physical hosts, the emulated traffic is tunneled over the physical network using tunnels <cit.>.

Emulating network conditions. Network conditions of virtual links are configured using the module in the Linux kernel <cit.>. This module allows fine-gained configuration of bit rates, packet delays, packet loss probabilities, jitter, and packet reordering probabilities.

We emulate connections between nodes as full-duplex loss-less connections of $1$ Gbit/s capacity in both directions. We emulate connections between the gateway and the external client population as full-duplex connections of $100$ Mbit/s capacity and $0.1\%$ packet loss with random bursts of $1\%$ packet loss. (These numbers are based on measurements on enterprise and wide-area networks <cit.>.)

§.§.§ Emulating Actors in the Digital Twin

In this section, we describe how actors of the intrusion response use case described in <ref> are emulated in the digital twin.

Emulating the client population. The client population is emulated by processes in Docker containers. Clients interact with application nodes through the gateway by consuming workflows. The workflow of a client is selected uniformly at random and its sequence of service invocations is decided uniformly at random. Client arrivals per time-step are emulated using a stationary Poisson process with rate $\lambda=50$ and exponentially distributed service times with mean $\mu=4$. The duration of a time-step in the emulation is $30$ seconds.

Emulating the attacker. The attacker's actions are emulated by executing scripts that automate exploits (see Table <ref>).

Type     Actions
Reconnaissance      scan, port scan, scan

vulnerability scanner, ping-scan

Brute-force     , , , ,

, , , ,

Exploit     -2017-7494, -2015-3306,

-2010-0426, -2015-5602,-2015-1427

-2014-6271, -2016-10033

-89 weakness on the web app DVWA <cit.>

Attacker actions executed on the digital twin; actions that exploit vulnerabilities in specific software products are identified by the vulnerability identifiers in the Common Vulnerabilities and Exposures () database <cit.>; actions that exploit vulnerabilities that are not described in the database are categorized according to the types of the vulnerabilities they exploit based on the Common Weakness Enumeration () list <cit.>; shell commands and scripts for executing the actions are listed in <cit.>; further details about the actions can be found in Appendix <ref>.

Emulating the defender. The four types of defender actions (see Fig. <ref>) are emulated as follows. To emulate the node migration action, we remove all virtual network interfaces of the emulated node and add a new interface that connects it to the new zone. To emulate the flow migration/blocking action we add rules to the flow tables of the emulated switches that match all flows towards the node and redirect them to a given destination. To emulate the node shut down action, we shut down the virtual container corresponding to the emulated node. Finally, to emulate the access control action, we reset all user accounts and certificates on the emulated node.

§.§ Estimating the Observation Distributions

Following the intrusion response use case described in <ref>, we define the observation $\mathbf{O}_{i,t}$ to be the number of alerts associated with node $i$ at time $t$, weighted by priority. As our target infrastructure consists of $64$ nodes (see App. <ref> and Fig. <ref>), there are $64$ alert distributions $Z_{\mathbf{O}_1}, \hdots, Z_{\mathbf{O}_{64}}$ (<ref>). We estimate these distributions based on empirical data from the digital twin.

Best response learning curves for the target infrastructure and synthetic infrastructures with varying $|\mathcal{V}|$ and $|\mathcal{W}|$.

Runtimes of dynamic programming.

Best response scalability.

Best response structure.

Best response learning via decomposition; (a) shows learning curves in simulation for synthetic infrastructures and the target infrastructure; the curves show the mean and 95% confidence interval for five random seeds; (b) shows execution times of computing best responses via dynamic programming and Sondik's value iteration algorithm <cit.>; (c) shows the speedup of our approach when computing best responses with different number of parallel processes; the speedup is calculated as $S_n = \frac{T_1}{T_{n}}$ where $T_n$ is the completion time with $n$ processes; and (d) shows an estimated switching curve (Thm. <ref>.C).

At the end of every time-step in the digital twin we collect the number of alerts that occurred during the time-step. These values are then used to compute the vector $\mathbf{o}_t$, which contains the total number of alerts per node, weighted by priority. For the evaluation in this paper we collect measurements from $10^4$ time-steps using the Snort <cit.>. (Each time-step in the digital twin is $30$ seconds.) Based on these measurements, we compute the empirical distributions $\widehat{Z}_{\mathbf{O}_1}, \hdots, \widehat{Z}_{\mathbf{O}_{64}}$ as estimates of $Z_{\mathbf{O}_1}, \hdots, Z_{\mathbf{O}_{64}}$ (see Fig. <ref>).

We observe in Fig. <ref> that the distributions differ between nodes, which can be explained by the different services provided by the nodes (see App. <ref>). We further observe that both the distributions when no intrusion occurs and the distributions during intrusion have most of their probability masses within $[0, 300]$. The distributions during intrusion also have substantial probability mass at larger values.

Remark: the stochastic matrices with the rows $\widehat{Z}_{\mathbf{O}_i|\mathbf{s}^{(\mathrm{A})}_i=(0,0)}$ and $\widehat{Z}_{\mathbf{O}_i|\mathbf{s}^{(\mathrm{A})}_i \neq (0,0)}$ have $250 \times 10^9$ second-order minors, which are almost all non-negative. This suggests that the assumption in Thm. <ref>.C can be made.

§ EXPERIMENTAL EVALUATION

Our approach to find near-optimal defender strategies includes learning Nash equilibrium strategies via the algorithm and evaluating these strategies on the digital twin (see Fig. <ref>). This section describes the evaluation results.

Experiment setup. The instantiation of $\Gamma$ (<ref>) and the hyperparameters are listed in App. <ref>. We evaluate both on a digital twin of the target infrastructure and in simulations of synthetic infrastructures. The topology of the target infrastructure is depicted in Fig. <ref> and its configuration is available in App. <ref>. The digital twin is deployed on a server with a $24$-core intel xeon gold $2.10$ GHz cpu and $768$ gb ram. Simulations of $\Gamma$ and executions of run on a cluster with $2$xtesla p100 gpus, $4$xrtx$8000$ gpus, and $3$x$16$-core intel xeon $3.50$ GHz cpus. Code for replicating the experiments is available in <cit.>.

Convergence metric. To estimate the convergence of the sequence of strategy pairs generated by , we use the approximate exploitability metric $\widehat{\delta}$ <cit.>:

\begin{align}
\widehat{\delta} = \mathbb{E}_{\widehat{\pi}_{\mathrm{D}},\pi_{\mathrm{A}}}\left[J\right] - \mathbb{E}_{\pi_{\mathrm{D}},\widehat{\pi}_{\mathrm{A}}}\left[J\right] \label{eq:approx_exp}
\end{align}

where $J$ is defined in (<ref>) and $\widehat{\pi}_{\mathrm{k}}$ denotes an approximate best response strategy for player $\mathrm{k}$. The closer $\widehat{\delta}$ becomes to $0$, the closer $(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$ is to a Nash equilibrium.

Baseline algorithms. We compare the performance of our approach ($\pi^{\text{decomposition}}$) with two baselines: $\pi^{\text{full}}$ and $\pi^{\text{workflow}}$. Baseline $\pi^{\text{full}}$ solves the full game without decomposition and $\pi^{\text{workflow}}$ decomposes the game on the workflow-level only.

We compare the performance of with that of Neural Fictitious Self-Play () <cit.> and <cit.>, which are the most popular algorithms among related work (see <cit.> for a review of algorithms used in related work).

Baseline strategies. We compare the defender strategies learned through with three baselines. The first baseline selects actions uniformly at random. The second baseline assumes prior knowledge of the opponent's actions and acts optimally based on this information. The last baseline acts according to the following heuristic: shut down a node $i \in \mathcal{V}$ when an alert occurs, i.e., when $\mathbf{o}_{i,t} > 0$.

§.§ Learning Best Responses Against Static Opponents

We first examine whether our method can discover effective strategies against a static opponent strategy, which in game-theoretic terms is the problem of finding best responses (<ref>)–(<ref>). The static strategies are defined in App. <ref>.

Nash equilibrium learning curves.

Comparison and .

Equilibrium learning via ; the red curves show simulation results and the blue curves show emulation results; the green, orange, purple, and black curves relate to baselines; the figures show approximate exploitability (<ref>) and normalized utility; the curves indicate the mean and the shaded areas indicate the standard deviation over three random seeds.

To measure the scalability of $\pi^{\text{decomposition}}$ we compare its performance with $\pi^{\text{workflow}}$ and $\pi^{\text{full}}$ on synthetic infrastructures with varying number of nodes $|\mathcal{V}|$ and workflows $|\mathcal{W}|$. To evaluate the optimal stopping approach described in <ref> we compare its rate of convergence with that of . Figure <ref> shows the learning curves. The red, purple, and pink curves represent the results obtained with $\pi^{\text{decomposition}}$; the blue and beige curves represent the results obtained with $\pi^{\text{workflow}}$; the orange and green curves represent the results obtained with $\pi^{\text{full}}$; and the dashed black lines relate to the baseline strategy that assumes prior knowledge of the opponent's strategy.

We note in Fig. Fig. <ref> that all the learning curves of $\pi^{\text{decomposition}}$ converge near the dashed black lines, which suggests that the learned strategies are close to best responses. In contrast, the learning curves of $\pi^{\text{workflow}}$ and $\pi^{\text{full}}$ do not converge near the dashed black lines within the measured time. This is expected as $\pi^{\text{workflow}}$ and $\pi^{\text{full}}$ can not be parallelized like $\pi^{\text{decomposition}}$. (The speedup of parallelization is shown in Fig. <ref>.) Lastly, we note in the rightmost plot of Fig. <ref> that the optimal stopping approach, which exploits the statement in Thm. <ref>.C, converges significantly faster than . An example of a learned optimal stopping strategy based on the linear approximation in (<ref>) is shown in Fig. <ref>.

§.§ Learning Equilibrium Strategies through Self-Play

Figures <ref>–<ref> show the learning curves of the strategies obtained during the self-play process and the baselines introduced above. The red curves represent the results from the simulator; the blue curves show the results from the digital twin; the green curve give the performance of the random baseline; the orange curve relate to the $\mathbf{o}_{i,t}>0$ baseline; and the dashed black line gives the performance of the baseline strategy that assumes prior knowledge of the attacker actions.

We note that all learning curves in Fig. <ref> converge, which suggests that the learned strategies converge as well. Specifically, we observe that the approximate exploitability (<ref>) of the learned strategies converges to small values (left plot), which indicates that the learned strategies approximate a Nash equilibrium both in the simulator and in the digital twin. Further, we see from the middle plot that both baseline strategies show decreasing performance as the attacker updates its strategy. In contrast, the defender strategy learned through improves its performance over time. This shows the benefit of a game-theoretic approach where the defender strategy is optimized against a dynamic attacker.

Figure <ref> compares with on the simulator. implements fictitious self-play and can thus be compared with with respect to approximate exploitability (<ref>). We observe that converges significantly faster than . The fast convergence of in comparison with is expected as is parallelizable while is not.

§.§ Discussion of the Evaluation Results

In this work, we propose a formal framework based on recursive decomposition for solving the intrusion response use case, which we evaluate experimentally on a digital twin. The key findings can be summarized as follows.

* Our framework approximates optimal defender strategies for a practical IT infrastructure (see Fig. <ref>). While we have not evaluated the learned strategies on the target infrastructure due to safety reasons, the fact that they achieve almost the same performance on the digital twin as on the simulator gives us confidence in the strategies' expected performance on the target infrastructure.

* Decomposition provides a scalable approach to automate intrusion response for IT infrastructures (see Fig. <ref> and Fig. <ref>). The intuition behind this finding is that decomposition allows to design efficient divide-and-conquer algorithms that can be parallelized (see Thm. <ref>.A–B and Alg. <ref>).

* The theory of optimal stopping provides insight about optimal defender strategies, which enables efficient computation of best responses (see the rightmost plot in Fig. <ref>). This property can be explained by the threshold structures of the best response strategies, which drastically reduce the search space of possible strategies (Thm. <ref>.C).

* Static defender strategies' performance deteriorate against a dynamic attacker whereas defender strategies learned through improve over time (see the right plot in Fig. <ref>). This finding is consistent with previous studies that use game-theoretic approaches (e.g., <cit.> and <cit.>) and suggests fundamental limitations of static intrusion response systems, such as the Snort .

§ CONCLUSIONS AND FUTURE WORK

We include elements of game theory and reinforcement learning in a framework to address the problem of automated intrusion response for a realistic use case. We formalize the use case as a partially observed stochastic game. We prove a decomposition theorem stating that the game decomposes recursively into subgames that can be solved efficiently and in parallel, and that the best response defender strategies exhibit threshold structures. This decomposition provides us with a scalable approach to learn near-optimal defender strategies. We develop Decompositional Fictitious Self-Play () – a fictitious self-play algorithm for finding Nash equilibria. To assess the learned strategies for a target infrastructure, we evaluate them on a digital twin. The results demonstrate that converges in reasonable time to near-optimal strategies, both in simulation and on the digital twin, while a state-of-the-art algorithm makes little progress toward an optimal strategy within the same time frame.

§ ACKNOWLEDGMENTS

The authors would like to thank Pontus Johnson and Quanyan Zhu for useful inputs to this research. The authors are also grateful to Forough Shahab Samani and Xiaoxuan Wang for their constructive comments on a draft of this paper.

§ HYPERPARAMETERS AND GAME INSTANTIATION

We instantiate $\Gamma$ (<ref>) for the experimental evaluation as follows. Client arrivals are sampled from a stationary Poisson process $Po(\lambda=50)$ and service times are exponentially distributed with mean $\mu=4$. In addition to migrate a node, the defender can shut it down or redirect its traffic to a honeynet, which we model with the zones $\mathfrak{S},\mathfrak{R} \in \mathcal{Z}$. A node $i \in \mathcal{V}$ is shutdown if $v^{(\mathrm{Z})}_{i,t}=\mathfrak{S}$ and have its traffic redirected if $v^{(\mathrm{Z})}_{i,t}=\mathfrak{R}$. The set of local attacker actions is $\mathcal{A}_{\mathrm{A}}^{(\mathrm{V})}=\{\bot, \text{reconnaissance}, \text{brute-force}, \text{exploit}\}$, which we encode as $\{0,1,2,3\}$. These actions have the following effects on the state $\mathbf{s}_{t}$: $\mathbf{a}_{i,t}^{(\mathrm{A})}=1 \implies v^{(\mathrm{R})}_{i,t}=1$, $\mathbf{a}_{i,t}^{(\mathrm{A})}=2 \implies v^{(\mathrm{I})}_{i,t}=1$ with probability $0.3$, and $\mathbf{a}_{i,t}^{(\mathrm{A})}=3 \implies v^{(\mathrm{I})}_{i,t}$ with probability $0.4$. We enforce a tree structure on the target infrastructure in Fig. <ref> by disregarding the redundant edges in the zone. The remaining parameters are listed in Table <ref>.

Game parameters     Values

$u_{\mathbf{w},t}$, $\mathcal{A}^{(\mathrm{V})}_{\mathrm{D}}$      $\sum_{i \in \mathcal{V}_{\mathbf{w}}}[\mathrm{gw} \rightarrow_{t}i]$, $\mathcal{Z} \cup \{\text{access control},\bot\}$

$|\mathcal{O}^{(\mathrm{V})}|$, $\gamma$, $\eta$, $|\mathcal{Z}|$, $|\mathcal{W}|$, $|\mathcal{V}|$     $10^3$, $0.9$, $0.4$, $6$, $10$, $64$

$u^{(\mathrm{w})}_{i}(\bot, l)$, $u^{(\mathrm{w})}_{i}(\mathfrak{S}, l)$,$u^{(\mathrm{w})}_{i}(\mathfrak{R}, l)$, $u^{(\mathrm{w})}_{i}(2, l)$    $0$, $10 + l$, $15+l$, $0.1+l$

$u^{(\mathrm{w})}_{i}(3, l)$, $u^{(\mathrm{w})}_{i}(4, l)$, $u^{(\mathrm{w})}_{i}(5, l)$, $u^{(\mathrm{w})}_{i}(0.8, l)$     $0.5+l$, $1+l$, $1.5+l$, $2+l$

topology $\mathcal{G}$ and $\mathbf{s}_1^{(\mathrm{D})}$     see Fig. <ref>

$|\mathcal{V}_{\mathbf{w}_1}|$,$|\mathcal{V}_{\mathbf{w}_2}|$,$|\mathcal{V}_{\mathbf{w}_3}|$,$|\mathcal{V}_{\mathbf{w}_4}|$,$|\mathcal{V}_{\mathbf{w}_5}|$,$|\mathcal{V}_{\mathbf{w}_6}|$     $16$, $16$, $16$, $16$, $6$, $4$

$|\mathcal{V}_{\mathbf{w}_7}|$,$|\mathcal{V}_{\mathbf{w}_8}|$,$|\mathcal{V}_{\mathbf{w}_9}|$,$|\mathcal{V}_{\mathbf{w}_{10}}|$     $6$, $4$, $6$, $6$

PPO parameters

lr $\alpha$, batch, # layers, # neurons, clip $\epsilon$     $10^{-5}$, $4\cdot 10^{3}t$, $4$, $64$, $0.2$

GAE $\lambda$, ent-coef, activation     $0.95$, $10^{-4}$, ReLU

NFSP parameters

lr RL, lr SL, batch, # layers,# neurons, $\mathcal{M}_{RL}$     $10^{-2}$, $5\cdot 10^{-3}$, $64$, $2$,$128$, $2\times 10^{5}$

$\mathcal{M}_{SL}$,$\epsilon$, $\epsilon$-decay, $\eta$     $2\times 10^{6}$, $0.06$, $0.001$, $0.1$

Stochastic approximation parameters

$c, \epsilon, \lambda, A, a, N, \delta$     $10$, $0.101$, $0.602$, $100$, $1$, $50$, $0.2$

Hyperparameters ($[\cdot]$ is the Iverson bracket).

§ STATIC DEFENDER AND ATTACKER STRATEGIES

The static defender and attacker strategies for the evaluation described in <ref> are defined in (<ref>)–(<ref>). (w.p is short for "with probability”.)

\begin{align}
&\pi_{\mathrm{D}}(\mathbf{h}_{t}^{(\mathrm{D})})_{i} =
\begin{dcases}
\bot & \text{w.p }0.95\\
j \in \mathcal{Z} & \text{w.p }\frac{0.05}{|\mathcal{Z}|+1}
\end{dcases}\label{eq:static_defender}\\
&\pi_{\mathrm{A}}(\mathbf{h}_{t}^{(\mathrm{A})})_{i} =
\begin{dcases}
\bot & \text{ if }v^{(\mathrm{I})}_{i,t}=1\\
\bot & \text{w.p }0.8 \text{ if }v^{(\mathrm{R})}_{i,t}=0\\
\bot & \text{w.p }0.7 \text{ if }v^{(\mathrm{R})}_{i,t}=1,v^{(\mathrm{I})}_{i,t}=0\\
\text{recon} & \text{w.p }0.2 \text{ if }v^{(\mathrm{R})}_{i,t}=0\\
\text{brute} & \text{w.p }0.15 \text{ if }v^{(\mathrm{R})}_{i,t}=1,v^{(\mathrm{I})}_{i,t}=0\\
\text{exploit} & \text{w.p }0.15 \text{ if }v^{(\mathrm{R})}_{i,t}=1,v^{(\mathrm{I})}_{i,t}=0
\end{dcases}\label{eq:static_attacker}
\end{align}

§ CONFIGURATION OF THE INFRASTRUCTURE IN FIG. <REF>

The configuration of the target infrastructure (Fig. <ref>) is available in Tables <ref> and <ref>.

ID(s)     Type     Operating system     Zone     Services     Vulnerabilities
$1$     Gateway     20     -     (ruleset v2.9.17.1), , v1.3, controller     -

$2$     Gateway     20         (ruleset v2.9.17.1), , v2.16, v1.3     -

$28$     Gateway     20         (ruleset v2.9.17.1), , v2.16, v1.3     -

$3$,$12$     Switch     22         , v1.3 , v2.16    -

$21,22$     Switch     22     -     , v1.3, v2.16     -

$23$     Switch     22         , v1.3, v2.16     -

$29$-$48$     Switch     22         , v1.3, v2.16     -

$13$-$16$     Honeypot     20         , , ,     -

$17$-$20$     Honeypot     20         , , , ,     -

$4$     App node     20         , ,     -1391

$5$, $6$     App node     20         , , ,     -

$7$     App node     20         , ,     -1391

$8$     App node             , , 2,    -2015-3306

$9$,$10$     App node     20         , , , ,     -

$11$     App node             2, ,     -2016-10033

$24$     Admin system     20         , ,     -1391

$25$     Admin system     20         , , , , 3,     -

$26$     Admin system     20         , , ,     -

$27$     Admin system     20         , , , , 3,     -1391

$49$-$59$     Compute node     20         ,     -

$60$     Compute node             , , 2,,     -2014-6271

$61$     Compute node     9.2         , 2,     -89

$62$     Compute node             , , 3, ,     -2010-0426

$63$     Compute node             , ,     -2015-5602

$64$     Compute node             , , , ,     -2017-7494

Configuration of the target infrastructure shown in Fig. <ref>; each row contains the configuration of one or more nodes; vulnerabilities in specific software products are identified by the vulnerability identifiers in the Common Vulnerabilities and Exposures () database <cit.>; vulnerabilities that are not described in the database are categorized according to the types of the vulnerabilities they exploit based on the Common Weakness Enumeration () list <cit.>.

ID     Name     Zone     Nodes
1     $1$         $1$, $21$, $22$, $28$, $(29-32)$, $(33-34)$, $(41-42)$, $(49-52)$

2     $2$         $1$, $21$, $22$, $28$, $(29-32)$, $(35-36)$, $(43-44)$, $(53-56)$

3     $3$         $1$, $21$, $22$, $28$, $(29-32)$, $(37-38)$, $(45-46)$, $(57-60)$

4     $4$         $1$, $21$, $22$, $28$, $(29-32)$, $(39-40)$, $(47-48)$, $(61-65)$

5     Web $1$         $1$, $2$, $3$, $4$, $5$, $6$

6     Web $2$         $1$, $2$, $3$, $7$

7     Storage $1$         $1$, $2$, $3$, $8$, $9$, $10$

8     Mail $1$         $1$, $2$, $3$, $11$

9     Admin $1$         $1$, $21$, $22$, $23$, $24$, $25$

10     Admin $2$         $1$, $21$, $22$, $23$, $25$, $26$

Workflows of the target infrastructure (Fig. <ref>).

§ ATTACKER ACTIONS

The attacker actions and their descriptions are listed in Table <ref>.

Action     Description
scan     port scan by sending or empty packets using ,

it allows detecting open ports by checking the responses

port scan     port scan by sending packets using ,

it allows detecting open ports by checking the responses

ping scan     IP scan with ping messages, it allows detecting alive hosts

vulnerability scan using , it allows detecting known vulnerabilities

brute-force attack     performs a dictionary attack against a login service using

-2017-7494 exploit     uploads a malicious binary to the service for remote code execution

-2015-3306 exploit     uses the  in  for remote code execution

-2014-6271 exploit     uses a vulnerability in  for remote code execution

-2016-10033 exploit     uses  for remote code execution

-2015-1427 exploit     uses the scripting engine in  for remote code execution

exploit of -89 weakness on DVWA <cit.>     sends a HTTP request injecting SQL code for SQLite3

Descriptions of the attacker actions; shell commands and scripts for executing the actions are listed in <cit.>.