# Learning Near-Optimal Intrusion Responses
Against Dynamic Attackers

Kim Hammar 23 and Rolf Stadler23
2 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>

###### Abstract

We study automated intrusion response and formulate the interaction between an
attacker and a defender as an optimal stopping game where attack and defense
strategies evolve through reinforcement learning and self-play. The game-
theoretic modeling enables us to find defender strategies that are effective
against a dynamic attacker, i.e. an attacker that adapts its strategy in
response to the defender strategy. Further, the optimal stopping formulation
allows us to prove that optimal strategies have threshold properties. To
obtain near-optimal defender strategies, we develop Threshold Fictitious Self-
Play (t-fp), a fictitious self-play algorithm that learns Nash equilibria
through stochastic approximation. We show that t-fp outperforms a state-of-
the-art algorithm for our use case. The experimental part of this
investigation includes two systems: a simulation system where defender
strategies are incrementally learned and an emulation system where statistics
are collected that drive simulation runs and where learned strategies are
evaluated. We argue that this approach can produce effective defender
strategies for a practical IT infrastructure.

###### Index Terms:

Cybersecurity, network security, automated security, intrusion response,
optimal stopping, Dynkin games, reinforcement learning, game theory, Markov
decision process, mdp, pomdp.

##  I Introduction

An organization’s security strategy has traditionally been defined,
implemented, and updated by domain experts [1]. This approach can provide
basic security for an organization’s communication and computing
infrastructure. As infrastructure update cycles become shorter and attacks
increase in sophistication, meeting the security requirements becomes
increasingly difficult. To address this challenge, significant efforts have
started to automate the process of obtaining security strategies [2]. Examples
of this research include: computation of defender strategies using dynamic
programming and control theory [3, 4]; computation of exploits and
corresponding defenses through evolutionary methods [5, 6]; computation of
defender strategies through game-theoretic methods [7, 8]; derivation of
defender responses through causal inference [9]; use of machine learning
techniques to estimate model parameters and strategies [10, 11, 12]; automated
creation of threat models [13]; and identification of infrastructure
vulnerabilities through attack simulations and threat intelligence [14, 15].

A promising new direction of research is automatically learning security
strategies through reinforcement learning methods [16], whereby the problem of
finding security strategies is modeled as a Markov decision problem and
strategies are learned through simulation (see surveys [17, 18]). While
encouraging results have been obtained following this approach [10, 11, 12,
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37,
38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56,
57], key challenges remain [58]. Chief among them is narrowing the gap between
the environment where strategies are evaluated and a scenario playing out in a
real system. Most of the results obtained so far are limited to simulation
environments, and it is not clear how they generalize to practical IT
infrastructures. Another challenge is to obtain security strategies that are
effective against a dynamic attacker, i.e. an attacker that adapts its
strategy in response to the defender strategy. Most of the prior work have
used reinforcement learning to find effective defender strategies against
static attackers, and little is known about the found strategies’ performance
against a dynamic attacker.

Attacker

Clients $\ldots$

Defender$1$idps$1$alerts Gateway
$7$$8$$9$$10$$11$$6$$5$$4$$3$$2$$12$$13$$14$$15$$16$$17$$18$$19$$21$$23$$20$$22$$24$$25$$26$$27$$28$$29$$30$$31$

Figure 1: The IT infrastructure and the actors in the intrusion response use
case.

In this paper, we address the above challenges and present a novel framework
to automatically learn a defender strategy against a dynamic attacker. We
apply this framework to an intrusion response use case, which involves the IT
infrastructure of an organization (see Fig. 1). 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.

We formulate the intrusion response use case as an optimal stopping game,
namely a stochastic game where both players face an optimal stopping problem
[59, 60, 61]. This formulation enables us to gain insight into the structure
of optimal strategies, which we prove to have threshold properties. To obtain
effective defender strategies, we use reinforcement learning and self-play.
Based on the threshold properties, we design Threshold Fictitious Self-Play
(t-fp), an efficient algorithm that iteratively computes near-optimal defender
strategies against a dynamic attacker.

Our method for learning and evaluating strategies for a given infrastructure
includes building two systems (see Fig. 2). First, we develop an emulation
system where key functional components of the target infrastructure are
replicated. This system closely approximates the functionality of the target
infrastructure and is used to run attack scenarios and defender responses.
Such runs produce system measurements and logs, from which we estimate
infrastructure statistics, which then are used to instantiate the simulation
model.

Second, we build a simulation system where game episodes are simulated and
strategies are incrementally learned through self-play. Learned strategies are
extracted from the simulation system and evaluated in the emulation system.

Two benefits of this method are: (i) that the emulation system allows
evaluating strategies without affecting operational workflows on the target
infrastructure; and (ii) that the simulation system enables efficient and
rapid learning of strategies. (A video demonstration of the software framework
that implements the emulation and simulation systems is available at [62].)

$s_{1,1}$$s_{1,2}$$s_{1,3}$$\ldots$$s_{1,n}$$s_{2,1}$$s_{2,2}$$s_{2,3}$$\ldots$$s_{2,n}$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$
Emulation System TargetInfrastructure Model estimation Strategy mapping
$\pi$Selectivereplication Strategyimplementation $\pi$ Simulation System Game
model &self-playreinforcement learning Strategy evaluation &data collection
Automatedintrusion response

Figure 2: Our framework for finding and evaluating intrusion response
strategies [10].

We make three contributions with this paper. First, we formulate intrusion
response as an optimal stopping game between an attacker and a defender. This
novel formulation allows us a) to derive and prove structural properties of
optimal strategies; and b) to find defender strategies that are effective
against an attacker with a dynamic strategy. We thus address a key limitation
of many related works, which only consider static attackers [10, 22, 25, 27,
28, 33, 12, 19, 29, 23, 38, 39, 41, 42, 63, 64, 65, 66, 44, 54, 53, 50, 67,
55, 68, 69]. Second, we propose t-fp, an efficient reinforcement learning
algorithm that exploits threshold properties of optimal stopping strategies
and outperforms a state-of-the-art algorithm for our use case. Third, we
provide evaluation results from an emulated infrastructure. This addresses a
drawback in related research that relies solely on simulations to learn and
evaluate strategies [11, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 8, 70,
71, 72, 35, 37, 36, 73, 74, 40, 41, 66, 65, 63, 45, 46, 47, 75, 48, 52, 54,
76, 67, 68, 56, 57, 77, 78].

We believe that this paper provides a foundation for the next generation of
security systems, including Intrusion Prevention Systems (ipss) (e.g. Trellix
[79]), Intrusion Response Systems (irss) (e.g. Wazuh [80]), and Intrusion
Detection Systems (idss) (e.g. Snort [81]). The optimal stopping strategies
computed through our framework can be used in these systems to decide at which
point in time an automated response action should be triggered or at which
point in time a human operator should be alerted to take action.

The work in this paper builds on our earlier results in automated intrusion
response [12, 10, 82]. Specifically, this paper can be seen as a
generalization of the work in [10], where we investigate intrusion response
against a static attacker. As explained in this paper, intrusion response
against a dynamic attacker requires a different mathematical framework. An
extended abstract of this paper was presented at the “Machine learning for
cyber security” workshop at the International Conference on Machine Learning
(icml) 2022 [82].

##  II 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 (Fig. 1). The infrastructure includes a set of
servers that run the services and an Intrusion Detection and Prevention System
(idps) that logs events in real-time. Clients access the services through a
public gateway, which is also open to the attacker.

The attacker’s goal is to intrude on the infrastructure and compromise its
servers. To achieve this, the attacker explores the infrastructure through
reconnaissance and exploits vulnerabilities while avoiding detection by the
defender. The attacker decides when to start an intrusion and may stop the
intrusion at any moment. During the intrusion, the attacker follows a pre-
defined strategy. When deciding the time to start or stop an intrusion, the
attacker considers both the gain of compromising additional servers and the
risk of detection. The optimal strategy for the attacker is to compromise as
many servers as possible without being detected.

The defender continuously monitors the infrastructure through accessing and
analyzing idps alerts and other statistics. It can take a fixed number of
defensive actions, each of which has a cost and a chance of stopping an
ongoing attack. An example of a defensive action is to drop network traffic
that triggers idps alerts of a certain priority. The defender takes actions in
a pre-determined order, starting with the action that has the lowest cost. The
final action blocks all external access to the gateway, which disrupts any
intrusion as well as the services to the clients.

When deciding the time for taking a defensive action, the defender balances
two objectives: (i) maintain services to its clients; and (ii) stop a possible
intrusion at the lowest cost. The optimal strategy for the defender is to
monitor the infrastructure and maintain services until the moment when the
attacker enters through the gateway, at which time the attack must be stopped
at minimal cost through defensive actions. The challenge for the defender is
to identify this precise moment.

##  III Formalizing The Intrusion Response Use Case

We formulate the above intrusion response use case as a partially observed
stochastic game. The attacker wins the game when it can intrude on the
infrastructure and hide its actions from the defender. Similarly, the defender
wins the game when it manages to stop an intrusion. It is a zero-sum game,
which means that the gain of one player equals the loss of the other player.

The attacker and the defender have different observability in the game. The
defender observes alerts from an Intrusion Detection and Prevention System
(idps) but has no certainty about the presence of an attacker or the state of
a possible intrusion. The attacker, on the other hand, is assumed to have
complete observability. It has access to all the information that the defender
has access to, as well as the defender’s past actions. This means that the
defender has to find strategies that are effective against an opponent that
has more knowledge than itself.

The reward function of the game encodes the defender’s objective. An optimal
defender strategy maximizes the reward when facing an attacker with an optimal
strategy, i.e. a worst-case attacker. Similarly, an optimal attacker strategy
minimizes the reward when facing a worst-case defender. Such a pair of optimal
strategies is known as a Nash equilibrium in game theory [83].

We model the game as a finite, zero-sum Partially Observed Stochastic Game
(posg) with one-sided partial observability:

$\displaystyle\Gamma=\langle\mathcal{N},\mathcal{S},(\mathcal{A}_{i})_{i\in\mathcal{N}},\mathcal{T},\mathcal{R},\gamma,\rho_{1},T,\mathcal{O},\mathcal{Z}\rangle$
(1)

It is a discrete-time game that starts at time $t=1$ and ends at time $t=T$.
In the following, we describe the components of the game, its evolution, and
the objectives of the players.

Players $\mathcal{N}$. The game has two players: player $\mathrm{D}$ is the
defender and player $\mathrm{A}$ is the attacker. Hence,
$\mathcal{N}=\\{\mathrm{D},\mathrm{A}\\}$.

Time horizon $T$. The time horizon $T$ is a random variable that depends on
both players’ strategies and takes values in the set
$T\in\\{2,3,\ldots,\infty\\}$.

State space $\mathcal{S}$. The game has three states: $s_{t}=0$ if no
intrusion occurs, $s_{t}=1$ if an intrusion is ongoing, and $s_{T}=\emptyset$
if the game has ended. Hence, $\mathcal{S}=\\{0,1,\emptyset\\}$. The state at
time $t$, $s_{t}$, is a realization of the random variable $S_{t}$. The
initial state is $s_{1}=0$. Hence the initial state distribution
$\rho_{1}\colon\mathcal{S}\rightarrow[0,1]$ is the degenerate distribution
$\rho_{1}(0)=1$.

Action spaces $\mathcal{A}_{i}$. Each player $i\in\mathcal{N}$ can invoke two
actions: “stop” ($\mathfrak{S}$) and “continue” ($\mathfrak{C}$). The action
spaces are thus
$\mathcal{A}_{\mathrm{D}}=\mathcal{A}_{\mathrm{A}}=\\{\mathfrak{S},\mathfrak{C}\\}$.
Executing action $\mathfrak{S}$ triggers a change in the game while action
$\mathfrak{C}$ is a passive action. In the following, we encode $\mathfrak{S}$
with $1$ and $\mathfrak{C}$ with $0$.

The attacker can invoke the stop action twice: the first time to start the
intrusion and the second time to terminate it.

The defender can invoke the stop action $L\geq 1$ times. A stop action is a
defensive action against a possible intrusion. The number of stop actions
remaining to the defender is known to both players and is denoted by
$l\in\\{1,\ldots,L\\}$.

At each time-step, the attacker and the defender simultaneously choose an
action $\mathbf{a}_{t}=(a^{(\mathrm{D})}_{t},a^{(\mathrm{A})}_{t})$, where
$a^{(i)}_{t}\in\mathcal{A}_{i}$ is a realization of the random variable
$A^{(i)}_{t}$ and $\mathbf{a}_{t}$ is a realization of the random vector
$\mathbf{A}_{t}$.

Observation space $\mathcal{O}$. The attacker has complete observability and
knows the game state, the defender’s actions, and the defender’s observations.
In contrast, the defender has a limited set of observations
$o_{t}\in\mathcal{O}$, where $\mathcal{O}$ is a discrete set. (In our use
case, $o_{t}$ relates to the weighted sum of idps alerts triggered during
time-step $t$. We focus on the idps alert metric as it provides more
information than other possible metrics for detecting intrusions, see Appendix
D for details.)

Both players have perfect recall, meaning they remember their respective play
history. The history of the defender at time-step $t$ is the vector
$\mathbf{h}^{(\mathrm{D})}_{t}=\allowbreak(\rho_{1},a^{(\mathrm{D})}_{1}\allowbreak,o_{1}\allowbreak,\ldots,\allowbreak
a^{(\mathrm{D})}_{t-1},\allowbreak o_{t})$ and the history of the attacker is
the vector $\mathbf{h}^{(\mathrm{A})}_{t}=\allowbreak(\rho_{1},\allowbreak
a^{(1)}_{1},\allowbreak a^{(\mathrm{A})}_{1},\allowbreak o_{1},\allowbreak
s_{1},\allowbreak\ldots,\allowbreak a^{(\mathrm{D})}_{t-1},\allowbreak
a^{(\mathrm{A})}_{t-1},\allowbreak o_{t},\allowbreak s_{t})$, which are
realizations of the random vectors $\mathbf{H}^{(\mathrm{D})}_{t}$ and
$\mathbf{H}^{(\mathrm{A})}_{t}$, respectively.

Belief space $\mathcal{B}$. Based on its history
$\mathbf{h}^{(\mathrm{D})}_{t}$, the defender forms a belief about the game
state $s_{t}$, which is expressed in the belief state
$b_{t}(s_{t})=\mathbb{P}[S_{t}=s_{t}\mid\mathbf{H}^{(\mathrm{D})}_{t}]$. Since
$s_{t}\in\\{0,1\\}$ and $b_{t}(0)=1-b_{t}(1)$ for $t<T$, we can model
$\mathcal{B}=[0,1]\subset\mathbb{R}$, where $b_{t}(1)\in\mathcal{B}$ is a
realization of the random variable $B_{t}$.

Transition probabilities $\mathcal{T}$. At each time-step $t$, a state
transition from $s_{t}$ to $s_{t+1}$ occurs with probability
$\mathcal{T}\big{(}s_{t+1},s_{t},\allowbreak(a^{(\mathrm{D})}_{t},\allowbreak
a^{(\mathrm{A})}_{t})\big{)}=\allowbreak\mathbb{P}\big{[}S_{t+1}=s_{t+1}\mid\allowbreak
S_{t}=s_{t},\allowbreak\mathbf{A}_{t}=\allowbreak(a^{(\mathrm{D})}_{t},\allowbreak
a^{(\mathrm{A})}_{t})\allowbreak\big{]}$:

$\displaystyle\mathcal{T}_{l>1}\big{(}0,0,(\mathfrak{S},\mathfrak{C})\big{)}=\mathcal{T}\big{(}0,0,(\mathfrak{C},\mathfrak{C})\big{)}=1$
(2)
$\displaystyle\mathcal{T}_{l>1}\big{(}1,1,(\cdot,\mathfrak{C})\big{)}=\mathcal{T}\big{(}1,1,(\mathfrak{C},\mathfrak{C})\big{)}=1-\phi_{l}$
(3)
$\displaystyle\mathcal{T}_{l>1}\big{(}1,0,(\cdot,\mathfrak{S})\big{)}=\mathcal{T}\big{(}1,0,(\mathfrak{C},\mathfrak{S})\big{)}=1$
(4)
$\displaystyle\mathcal{T}_{l>1}\big{(}\emptyset,1,(\cdot,\mathfrak{C})\big{)}=\mathcal{T}\big{(}\emptyset,1,(\mathfrak{C},\mathfrak{C})\big{)}=\phi_{l}$
(5)
$\displaystyle\mathcal{T}_{l=1}\big{(}\emptyset,\cdot,(\mathfrak{S},\cdot)\big{)}=\mathcal{T}(\emptyset,\emptyset,\cdot)=\mathcal{T}(\emptyset,1,(\cdot,\mathfrak{S}))=1$
(6)

where $\mathcal{T}_{l>1}$ and $\mathcal{T}_{l=1}$ refer to the transition
probabilities when $l>1$ and $l=1$, respectively ($\mathcal{T}$ denotes the
transition probabilities for any value of $l$). All other state transitions
have probability $0$.

(2)–(3) define the probabilities of the recurrent state transitions
$0\rightarrow 0$ and $1\rightarrow 1$. The game stays in state $0$ with
probability $1$ if the attacker selects action $\mathfrak{C}$ and
$l_{t}-a_{t}^{(\mathrm{D})}>0$. (Note that
$l_{t+1}=l_{t}-a_{t}^{(\mathrm{D})}$.) Similarly, the game stays in state $1$
with probability $1-\phi_{l}$ if the attacker chooses action $\mathfrak{C}$
and $l_{t}-a_{t}^{(\mathrm{D})}>0$. Here $\phi_{l}$ denotes the probability
that the intrusion is stopped, which is a parameter of the use case. The
intrusion can be stopped at any time-step as a consequence of previous stop
actions by the defender. We assume that $\phi_{l}$ increases with each stop
action that the defender takes.

(4) captures the transition $0\rightarrow 1$, which occurs when the attacker
chooses action $\mathfrak{S}$ and $l_{t}-a_{t}^{(\mathrm{D})}>0$. (5)–(6)
define the probabilities of the transitions to the terminal state $\emptyset$.
The terminal state is reached in three cases: (i) when $l_{t}=1$ and the
defender takes the final stop action $\mathfrak{S}$ (i.e. when
$l_{t}-a^{(\mathrm{D})}_{t}=0$); (ii) when the intrusion is stopped by the
defender with probability $\phi_{l}$; and (iii) when $s_{t}=1$ and the
attacker terminates the intrusion ($a^{(\mathrm{A})}_{t}=1$).

The evolution of the game can be described with the state transition diagram
in Fig. 3. The figure captures a game episode, which starts at $t=1$ and ends
at $t=T$.

$0$$1$$\emptyset$$t\geq 1$$l>0$$t\geq
2$$l>0$$a^{(\mathrm{A})}_{t}=\mathfrak{S}$$l=1,a_{t}^{(\mathrm{D})}=\mathfrak{S}$$l=1,a_{t}^{(\mathrm{D})}=\mathfrak{S}$intrusion
stopped w.p $\phi_{l}$or terminated ($a^{(\mathrm{A})}_{t}=\mathfrak{S}$)

Figure 3: State transition diagram of a game episode: each disk represents a
state; an arrow represents a state transition; a label indicates the
conditions for the state transition (w.p means “with probability”); a game
episode starts in state $s_{1}=0$ with $l=L$ and ends in state
$s_{T}=\emptyset$.

Reward function $\mathcal{R}$. At time-step $t$, the defender receives the
reward $r_{t}=\mathcal{R}(s_{t},(a^{(\mathrm{D})}_{t},a^{(\mathrm{A})}_{t}))$
and the attacker receives the reward $-r_{t}$. Here $r_{t}\in\mathbb{R}$ is a
realization of the random variable $R_{t}$. The reward function $\mathcal{R}$
is parameterized by the defender’s reward for stopping an intrusion
($\mathrm{R}_{\mathrm{st}}\in\mathbb{R}_{>0}$), the defender’s cost of taking
a defensive action ($\mathrm{R}_{\mathrm{cost}}\in\mathbb{R}_{<0}$), and the
defender’s cost while an intrusion occurs
($\mathrm{R}_{\mathrm{int}}\in\mathbb{R}_{<0}$):

$\displaystyle\mathcal{R}(\emptyset,\cdot)=0$ (7)
$\displaystyle\mathcal{R}\big{(}1,(\cdot,\mathfrak{S})\big{)}=0$ (8)
$\displaystyle\mathcal{R}\big{(}0,(\mathfrak{C},\cdot)\big{)}=0$ (9)
$\displaystyle\mathcal{R}\big{(}0,(\mathfrak{S},\cdot)\big{)}=\frac{\mathrm{R}_{\mathrm{cost}}}{l_{t}}$
(10)
$\displaystyle\mathcal{R}\big{(}1,(\mathfrak{S},\mathfrak{C})\big{)}=\frac{\mathrm{R}_{\mathrm{st}}}{l_{t}}$
(11)
$\displaystyle\mathcal{R}\big{(}1,(\mathfrak{C},\mathfrak{C})\big{)}=\mathrm{R}_{\mathrm{int}}$
(12)

(7)–(8) state that the reward is zero in the terminal state and when the
attacker terminates an intrusion. (9) states that the defender incurs no cost
when no attack occurs and it does not take a defensive action. (10) indicates
that the defender incurs a cost when taking a defensive action if no intrusion
is ongoing. (11) states that the defender receives a reward when taking a stop
action while an intrusion occurs. Lastly, (12) indicates that the defender
incurs a cost for each time-step during which an intrusion occurs.

Observation function $\mathcal{Z}$. At time-step $t$, $o_{t}\in\mathcal{O}$ is
drawn from a random variable $O$ whose distribution $f_{O}$ depends on the
current state $s_{t}$. We define
$\mathcal{Z}(o_{t},s_{t},(a^{(\mathrm{D})}_{t-1},a^{(\mathrm{A})}_{t-1}))=\allowbreak\mathbb{P}[O=o_{t}\mid\allowbreak
S_{t}=s_{t},\allowbreak\mathbf{A}_{t}=(a^{(\mathrm{D})}_{t-1},\allowbreak
a^{(\mathrm{A})}_{t-1})\allowbreak]$ as follows:

$\displaystyle\mathcal{Z}\big{(}o_{t},0,\cdot\big{)}=f_{O}(o_{t}\mid 0)$ (13)
$\displaystyle\mathcal{Z}\big{(}o_{t},1,\cdot\big{)}=f_{O}(o_{t}\mid 1)$ (14)

Player strategies $\pi_{i}$. A defender strategy is a function
$\pi_{\mathrm{D}}\in\Pi_{\mathrm{D}}=\\{1,\ldots,L\\}\times\mathcal{B}\rightarrow\Delta(\mathcal{A}_{\mathrm{D}})$,
where $\Delta(\mathcal{A}_{\mathrm{D}})$ denotes the set of probability
distributions over $\mathcal{A}_{\mathrm{D}}$. Similarly, an attacker strategy
is a function
$\pi_{\mathrm{A}}\in\Pi_{\mathrm{A}}=\\{1,\ldots,L\\}\times\mathcal{B}\times\mathcal{S}\rightarrow\Delta(\mathcal{A}_{\mathrm{A}})$.
The strategies for both players are dependent on $l$ but independent of $t$
(i.e. strategies are stationary). If $\pi_{i}$ always maps on to an action
with probability $1$, it is called pure, otherwise it is called mixed. In
other words, a pure strategy is deterministic and a mixed strategy is
stochastic.

Belief update. At time-step $t>1$, the defender updates the belief state
$b_{t-1}$ using the equation

$\displaystyle
b_{t}(s_{t})=C\sum_{s_{t-1}\in\mathcal{S}}\sum_{a^{(\mathrm{A})}_{t-1}\in\mathcal{A}_{\mathrm{A}}}\Big{(}b_{t-1}(s_{t-1})\pi_{\mathrm{A}}(a^{(\mathrm{A})}_{t-1}\mid
s_{t-1},b_{t-1})\cdot$
$\displaystyle\mathcal{Z}(o_{t},s_{t},(a^{(\mathrm{D})}_{t-1},a^{(\mathrm{A})}_{t-1}))\mathcal{T}\big{(}s_{t},s_{t-1},(a^{(\mathrm{D})}_{t-1},a^{(\mathrm{A})}_{t-1})\big{)}\Big{)}$
(15)

where $C=1/\mathbb{P}[o_{t}\mid
a^{(\mathrm{D})}_{t-1},\pi_{\mathrm{A}},b_{t-1}]$ is a normalizing factor to
ensure that the sum over $b_{t}(s_{t})$ for all $s_{t}$ equals $1$. The
initial belief is $b_{1}(0)=1$.

Objective functions $J_{i}$. The goal of the defender is to maximize the
expected discounted cumulative reward over the time horizon $T$. Similarly,
the goal of the attacker is to minimize the same quantity. Therefore, the
objective functions $J_{\mathrm{D}}$ and $J_{\mathrm{A}}$ are

$\displaystyle J_{\mathrm{D}}(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$
$\displaystyle=\mathbb{E}_{(\pi_{\mathrm{D}},\pi_{\mathrm{A}})}\left[\sum_{t=1}^{T}\gamma^{t-1}\mathcal{R}(S_{t},\mathbf{A}_{t})\right]$
(16) $\displaystyle J_{\mathrm{A}}(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$
$\displaystyle=-J_{\mathrm{D}}(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$ (17)

where $\gamma\in[0,1)$ is the discount factor and
$\mathbb{E}_{(\pi_{\mathrm{D}},\pi_{\mathrm{A}})}$ denotes the expectation of
the random variables $(S_{t},O_{t},\mathbf{A}_{t})_{t\in\\{1,\ldots,T\\}}$
under strategy profile $(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$.

Best response strategies $\tilde{\pi}_{i}$. 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_{\mathrm{D}}$
(16). Similarly, an attacker strategy $\tilde{\pi}_{\mathrm{A}}$ is called a
best response against $\pi_{\mathrm{D}}$ if it minimizes $J_{\mathrm{D}}$
(17). Hence, the best response correspondences $\mathscr{B}_{\mathrm{D}}$ and
$\mathscr{B}_{\mathrm{A}}$ are obtained as follows:

$\displaystyle\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}})$
$\displaystyle=\operatorname*{arg\,max}_{\pi_{\mathrm{D}}\in\Pi_{\mathrm{D}}}J_{\mathrm{D}}(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$
(18) $\displaystyle\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})$
$\displaystyle=\operatorname*{arg\,min}_{\pi_{\mathrm{A}}\in\Pi_{\mathrm{A}}}J_{\mathrm{D}}(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$
(19)

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

$\displaystyle(\pi_{\mathrm{D}}^{*},\pi_{\mathrm{A}}^{*})\in\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}}^{*})\times\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}}^{*})$
(20)

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

Notation(s) | Description
---|---
$\Gamma$ | The intrusion response posg (1)
$\mathrm{D},\mathrm{A}$ | The defender player and the attacker player
$t,T,\gamma$ | Time-step, time horizon, and discount factor
$l_{t}$ | Defender stops remaining at time-step $t$
$L$ | Maximum number of defender stops
$\pi_{\mathrm{D}},\pi_{\mathrm{A}}$ | Defender and attacker strategies
$\tilde{\pi}_{\mathrm{D}},\tilde{\pi}_{\mathrm{A}}$ | Best response strategies
$\pi^{*}_{\mathrm{D}},\pi^{*}_{\mathrm{A}}$ | Optimal strategies
$\mathcal{N},\mathcal{S},\mathcal{O}$ | Sets of players, states, and observations
$\mathcal{A}_{\mathrm{D}},\mathcal{A}_{\mathrm{A}}$ | Sets of defender and attacker actions
$\mathcal{T},\mathcal{R},\mathcal{Z}$ | Transition, reward and observation functions
$s_{t},o_{t},\mathbf{a}_{t}=(a_{t}^{\mathrm{D}},a_{t}^{\mathrm{A}})$ | State, observation, and actions at time-step $t$
$b_{t}(1)\in\mathcal{B},r_{t}$ | Defender belief and reward at time-step $t$
$\mathfrak{S},\mathfrak{C}$ | Stop and continue actions
$\tau_{i,k}$ |  $k$th stopping time of player $i$
$\mathscr{B}_{\mathrm{D}},\mathscr{B}_{\mathrm{A}}$ | Best response correspondences (18)–(19)
$J_{\mathrm{D}},J_{\mathrm{A}}$ | Defender and attacker objectives (16)–(17)
$\mathcal{M}^{P},\mathcal{M}$ | Best response pomdp and mdp for $\mathrm{D}$ and $\mathrm{A}$
$\mathscr{S}^{i},\mathscr{C}^{i}$ | Stopping and continuation sets of player $i$
$S_{t},\mathbf{A}_{t},O_{t}$ | Random variables with realizations $s_{t},\mathbf{a}_{t},o_{t}$
$R_{t},B_{t}$ | Random variables with realizations $r_{t},b_{t}$
$V^{*}_{l,\pi_{\mathrm{A}}},V^{*}_{l,\pi_{\mathrm{D}}}$ | Value functions of $\mathcal{M}^{P}$ and $\mathcal{M}$
$f_{O\mid s}$ | Observation distribution (13)–(14)
TABLE 1: Notations for our mathematical model.

##  IV Game-Theoretic Analysis and Our Algorithm for Finding Near-Optimal
Defender Strategies

Finding optimal strategies that satisfy (20) is equivalent to finding a Nash
equilibrium for the posg $\Gamma$ (1). We know from game theory that $\Gamma$
has at least one mixed Nash equilibrium [84, 83, 85, 86]. (A Nash equilibrium
is called mixed if one or more players follow mixed strategies.) In this
section, we first analyze the structure of Nash equilibria in $\Gamma$ using
optimal stopping theory and then we describe an efficient reinforcement
learning algorithm for approximating these equilibria.

###  IV-A Analyzing Best Responses using Optimal Stopping Theory

The equilibria in $\Gamma$ can be obtained by finding the pairs of strategies
that are best responses against each other (20). A best response for the
defender is obtained by solving a pomdp $\mathcal{M}^{P}$, and a best response
for the attacker is obtained by solving an mdp $\mathcal{M}$. The
corresponding Bellman equations are [87]:

$\displaystyle
V_{l,\pi_{\mathrm{A}}}^{*}(b_{t})=\max_{a^{(\mathrm{D})}_{t}\in\mathcal{A}_{\mathrm{D}}}\mathop{\mathbb{E}}_{\pi_{\mathrm{A}},b_{t},a^{(\mathrm{D})}_{t}}\Big{[}R_{t+1}+\gamma
V_{l-a^{(\mathrm{D})}_{t},\pi_{\mathrm{A}}}^{*}(B_{t+1})\Big{]}$ (21)
$\displaystyle V_{l,\pi_{\mathrm{D}}}^{*}((b_{t},s_{t}))=$
$\displaystyle\min_{a^{(\mathrm{A})}_{t}\in\mathcal{A}_{\mathrm{A}}}\mathop{\mathbb{E}}_{\pi_{\mathrm{D}},a^{(\mathrm{A})}_{t}}\Big{[}R_{t+1}+\gamma
V_{l-A^{(\mathrm{D})}_{t},\pi_{\mathrm{D}}}^{*}((B_{t+1},S_{t+1}))\Big{]}$
(22)

where $V_{l,\pi_{\mathrm{A}}}^{*}$ is the value function in the pomdp
$\mathcal{M}^{P}$ given that the attacker follows strategy $\pi_{\mathrm{A}}$
and the defender has $l$ stops remaining, and $V^{*}_{l,\pi_{\mathrm{D}}}$ is
the value function in the mdp $\mathcal{M}$ given that the defender follows
strategy $\pi_{\mathrm{D}}$ and has $l$ stops remaining.

Since the game is zero-sum, stationary, and $\gamma<1$, it follows from the
Minimax theorem in game theory that there exists a value function:

$\displaystyle
V_{l}^{*}(b_{t})=\max_{\pi_{\mathrm{D}}\in\Delta(\mathcal{A}_{\mathrm{D}})}\min_{\pi_{\mathrm{A}}\in\Delta(\mathcal{A}_{\mathrm{A}})}\mathop{\mathbb{E}}_{\pi_{\mathrm{D}},\pi_{\mathrm{A}},b_{t}}\Big{[}R_{t+1}+$
(23)
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\gamma
V_{l-a^{(\mathrm{D})}_{t}}^{*}(B_{t+1})\Big{]}$

and that
$V_{l}^{*}(b)=V_{l,\pi^{*}_{\mathrm{A}}}^{*}(b)=V_{l,\pi^{*}_{\mathrm{D}}}^{*}(b,s)$
[84][88, Thm. 2.3]. Further, from Markov decision theory we know that for any
strategy pair ($\pi_{\mathrm{D}},\pi_{\mathrm{A}}$), a corresponding pair of
pure best response strategies
$(\tilde{\pi}_{\mathrm{D}},\tilde{\pi}_{\mathrm{A}})\in\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}})\times\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})$
exists [89, Thm. 6.2.7][90, Thm. 7.6.1-7.6.2].

Attacker Defender
$t=1$$t=T$$\tau_{\mathrm{D},1}$$\tau_{\mathrm{D},2}$$\tau_{\mathrm{D},3}$$\tau_{\mathrm{A},1}$$t$$\mathbin{\leavevmode\hbox
to5.6pt{\vbox to5.6pt{\pgfpicture\makeatletter\hbox{\hskip
0.21527pt\lower-0.21527pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.43056pt}\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}{{}}{} {}{}{}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{5.16666pt}{5.16666pt}\pgfsys@moveto{0.0pt}{5.16666pt}\pgfsys@lineto{5.16666pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$StoppedGame episode
Intrusion

Figure 4: Stopping times of the defender and the attacker in a game episode;
the bottom horizontal axis represents time; the black circles on the middle
axis and the upper axis represent time-steps of the defender’s stop actions
and the attacker’s stop actions, respectively; $\tau_{i,j}$ denotes the $j$th
stopping time of player $i$; the cross shows the time the intrusion is
stopped; an intrusion starts when the attacker takes the first stop action (at
time $\tau_{\mathrm{A},1}$); an episode ends either when the attacker is
stopped (as a consequence of defender actions) or when the attacker terminates
its intrusion.

We interpret the pomdp $\mathcal{M}^{P}$ and the mdp $\mathcal{M}$ that
determine the best response strategies as optimal stopping problems (see Fig.
4) [59, 91, 92, 10]. Consequently, an optimal solution to $\mathcal{M}^{P}$
(or $\mathcal{M}$) is also an optimal solution to the corresponding stopping
problem and vice versa.

The problem for the defender is to find a stopping strategy
$\pi_{\mathrm{D}}^{*}(b_{t})\rightarrow\\{\mathfrak{S},\mathfrak{C}\\}$ that
maximizes $J_{\mathrm{D}}$ (16) and prescribes the optimal stopping times
$\tau^{*}_{\mathrm{D},1},\tau^{*}_{\mathrm{D},2},\ldots,\tau^{*}_{\mathrm{D},L}$.
Similarly, the problem for the attacker is to find a stopping strategy
$\pi_{\mathrm{A}}^{*}(s_{t},b_{t})\rightarrow\\{\mathfrak{S},\mathfrak{C}\\}$
that minimizes $J_{\mathrm{D}}$ (17) and prescribes the optimal stopping times
$\tau^{*}_{\mathrm{A},1}$ and $\tau^{*}_{\mathrm{A},2}$.

Given a pair of stopping strategies $(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$ and
their (pure) best responses
$\tilde{\pi}_{\mathrm{D}}\in\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}})$ and
$\tilde{\pi}_{\mathrm{A}}\in\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})$, we
define two subsets of $\mathcal{B}=[0,1]$: the stopping sets and the
continuation sets.

The stopping sets $\mathscr{S}^{(\mathrm{D})}$ and
$\mathscr{S}^{(\mathrm{A})}$ include the belief states where $\mathfrak{S}$ is
a best response:

$\displaystyle\mathscr{S}^{(\mathrm{D})}_{l,\pi_{\mathrm{A}}}$
$\displaystyle=\left\\{b(1)\mid
b(1)\in[0,1],\tilde{\pi}_{\mathrm{D},l}\big{(}b(1)\big{)}=\mathfrak{S}\right\\}$
(24) $\displaystyle\mathscr{S}^{(\mathrm{A})}_{s,l,\pi_{\mathrm{D}}}$
$\displaystyle=\left\\{b(1)\mid
b(1)\in[0,1],\tilde{\pi}_{\mathrm{A},l}\big{(}s,b(1)\big{)}=\mathfrak{S}\right\\}$
(25)

Similarly, the continuation sets $\mathscr{C}^{(\mathrm{D})}$ and
$\mathscr{C}^{(\mathrm{A})}$ contain the belief states where $\mathfrak{C}$ is
a best response:

$\displaystyle\mathscr{C}^{(\mathrm{D})}_{l,\pi_{\mathrm{A}}}$
$\displaystyle=\left\\{b(1)\mid
b(1)\in[0,1],\tilde{\pi}_{\mathrm{D},l}\big{(}b(1)\big{)}=\mathfrak{C}\right\\}$
(26) $\displaystyle\mathscr{C}^{(\mathrm{A})}_{s,l,\pi_{\mathrm{D}}}$
$\displaystyle=\left\\{b(1)\mid
b(1)\in[0,1],\tilde{\pi}_{\mathrm{A},l}\big{(}b(1),s\big{)}=\mathfrak{C}\right\\}$
(27)

Based on [90, Thm. 12.3.4] [93, Prop. 4.5-4.8], [94, Thm. 1][10, Thm. 1], and
[95, Thm. 2.3], we formulate Theorem 1, which contains an existence result for
equilibria and a structural result for best response strategies of the game.

######  Theorem 1.

Given the posg $\Gamma$ (1) with one-sided partial observability and $L\geq
1$, the following holds:

  1. (A)

$\Gamma$ has a mixed Nash equilibrium. If $s=0\iff b(1)=0$, then it has a pure
Nash equilibrium.

  2. (B)

We assume that the probability mass function $f_{O\mid s}$ is totally positive
of order 2 (i.e., tp-2 [90, Def. 10.2.1, pp. 223]). Given an attacker strategy
$\pi_{\mathrm{A}}\in\Pi_{\mathrm{A}}$, then there exist values
$\tilde{\alpha}_{1}$ $\geq$ $\tilde{\alpha}_{2}$ $\geq$ $\ldots$ $\geq$
$\tilde{\alpha}_{L}\in[0,1]$ and a best response strategy
$\tilde{\pi}_{\mathrm{D}}\in\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}})$ for
the defender that satisfies

$\displaystyle\tilde{\pi}_{\mathrm{D},l}(b(1))=\mathfrak{S}\iff
b(1)\geq\tilde{\alpha}_{l}\quad l\in\\{1,\ldots,L\\}$ (28)

  3. (C)

Given a defender strategy $\pi_{\mathrm{D}}\in\Pi_{\mathrm{D}}$ where
$\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ is non-decreasing in $b(1)$ and
$\pi_{\mathrm{D}}(\mathfrak{S}\mid 1)=1$, then there exist values
$\tilde{\beta}_{0,1},$ $\tilde{\beta}_{1,1},$ $\ldots$, $\tilde{\beta}_{0,L}$,
$\tilde{\beta}_{1,L}\in[0,1]$ and a best response strategy
$\tilde{\pi}_{\mathrm{A}}\in\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})$ for
the attacker that satisfies

$\displaystyle\tilde{\pi}_{\mathrm{A},l}(b(1),0)=\mathfrak{C}$
$\displaystyle\iff\pi_{\mathrm{D},l}(\mathfrak{S}\mid
b(1))\geq\tilde{\beta}_{0,l}$ (29)
$\displaystyle\tilde{\pi}_{\mathrm{A},l}(b(1),1)=\mathfrak{S}$
$\displaystyle\iff\pi_{\mathrm{D},l}(\mathfrak{S}\mid
b(1))\geq\tilde{\beta}_{\mathrm{D},l}$ (30)

for $l\in\\{1,\ldots,L\\}$.

  * Proof.

See Appendix A. ∎

$b(1)$$0$$1$$\mathscr{S}^{(\mathrm{D})}_{1,\pi_{\mathrm{A}}}$$\mathscr{S}^{(\mathrm{D})}_{2,\pi_{\mathrm{A}}}$$\vdots$$\mathscr{S}^{(\mathrm{D})}_{L,\pi_{\mathrm{A}}}$$\tilde{\alpha}_{1}$$\tilde{\alpha}_{2}$$\tilde{\alpha}_{L}$$\ldots$$b(1)$$0$$1$$\mathscr{S}^{(\mathrm{A})}_{1,1,\pi_{\mathrm{D}}}$$\mathscr{S}^{(\mathrm{A})}_{1,L,\pi_{\mathrm{D}}}$$\tilde{\beta}_{1,1}$$\tilde{\beta}_{1,L}$$\tilde{\beta}_{0,1}$$\ldots$$\tilde{\beta}_{0,L}$$\ldots$$\mathscr{S}^{(\mathrm{A})}_{0,1,\pi_{\mathrm{D}}}$$\mathscr{S}^{(\mathrm{A})}_{0,L,\pi_{\mathrm{D}}}$

Figure 5: Illustration of Theorem 1; the upper part shows $L$ thresholds
$\tilde{\alpha}_{1}\geq\tilde{\alpha}_{2},\ldots,\geq\tilde{\alpha}_{L}\in[0,1]$
that define a best response strategy
$\tilde{\pi}_{\mathrm{D}}\in\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}})$ for
the defender (28); the lower part shows $2L$ thresholds
$\tilde{\beta}_{0,1},\tilde{\beta}_{1,1},\ldots,\tilde{\beta}_{0,L},\tilde{\beta}_{1,L}\in[0,1]$
that define a best response strategy
$\tilde{\pi}_{\mathrm{A}}\in\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})$ for
the attacker (29)–(30).

Theorem 1 tells us that $\Gamma$ has a mixed Nash equilibrium. Further, under
assumptions generally met in practice, the best response strategies have
threshold properties (see Fig. 5). In the following, we describe an algorithm
that leverages these properties to efficiently approximate Nash equilibria of
$\Gamma$.

###  IV-B Finding Nash Equilibria through Fictitious Self-Play

Computing Nash equilibria for a posg is generally intractable [96, Thm. 3.5]
[97, Thm. 6]. However, approximate solutions can be obtained through iterative
methods. One such method is fictitious self-play, where both players start
from random strategies and continuously update their strategies based on
outcomes of played game episodes [98].

Fictitious self-play evolves through a sequence of iteration steps, which is
illustrated in Fig. 6. An iteration step includes three stages. First, player
$1$ learns a best response strategy against player $2$’s current strategy. The
roles are then reversed and player $2$ learns a best response strategy against
player $1$’s current strategy. Lastly, each player adopts a new strategy,
which is determined by the empirical distribution over its past best response
strategies. The sequence of iteration steps continues until the strategies of
both players have sufficiently converged to a Nash equilibrium [99, Thms.
7.2.4-7.2.5].

###  IV-C Our Self-Play Algorithm: t-fp

We present a fictitious self-play algorithm called Threshold Fictitious Self-
Play (t-fp), which efficiently approximates a Nash equilibrium of $\Gamma$
based on Theorem 1. The pseudocode of t-fp is listed in Algorithm 1.

$\tilde{\pi}_{\mathrm{A}}\in\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})$$\pi_{\mathrm{A}}$

$\pi_{\mathrm{D}}$$\tilde{\pi}_{\mathrm{D}}\in\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}})$

$\tilde{\pi}^{\prime}_{\mathrm{A}}\in\mathscr{B}_{\mathrm{A}}(\pi^{\prime}_{\mathrm{D}})$$\pi^{\prime}_{\mathrm{A}}$

$\pi^{\prime}_{\mathrm{D}}$$\tilde{\pi}^{\prime}_{\mathrm{D}}\in\mathscr{B}_{\mathrm{D}}(\pi^{\prime}_{\mathrm{A}})$$\ldots$

$\pi^{*}_{\mathrm{A}}\in\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}}^{*})$

$\pi^{*}_{\mathrm{D}}\in\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}}^{*})$

Figure 6: The fictitious self-play process; in every iteration step each
player learns a best response strategy
$\tilde{\pi}_{i}\in\mathscr{B}_{i}(\pi_{{-i}})$ and updates its strategy based
on the empirical distribution of its past best response strategies; the
horizontal arrows indicate iteration steps of self-play and the vertical
arrows indicate the learning of best response strategies; the process
converges towards a Nash equilibrium
$(\pi_{\mathrm{D}}^{*},\pi_{\mathrm{A}}^{*})$.

t-fp implements the fictitious self-play process described above and generates
a sequence of strategy profiles $(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$,
$(\pi^{\prime}_{\mathrm{D}}$, $\pi^{\prime}_{\mathrm{A}})$, $\ldots$ that
converges to a Nash equilibrium $(\pi^{*}_{\mathrm{D}},\pi^{*}_{\mathrm{A}})$
[99, Thms. 7.2.4-7.2.5]. During each step of this process, t-fp learns best
responses against the players’ current strategies and then updates the
strategies of both players (see Fig. 6).

To learn the best response strategies
$\tilde{\pi}_{\mathrm{D}}\in\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}})$ and
$\tilde{\pi}_{\mathrm{A}}\in\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})$, t-fp
parameterizes $\tilde{\pi}_{\mathrm{D}}$ and $\tilde{\pi}_{\mathrm{A}}$
through threshold vectors according to Theorem 1. The defender’s best response
strategy $\tilde{\pi}_{\mathrm{D}}$ is parameterized with the vector
$\tilde{\bm{\theta}}^{(\mathrm{D})}\in\mathbb{R}^{L}$ (32). Similarly, the
attacker’s best response strategy $\tilde{\pi}_{\mathrm{A}}$ is parameterized
with the vector $\tilde{\bm{\theta}}^{(\mathrm{A})}\in\mathbb{R}^{2L}$ (33).

$\displaystyle\varphi(a,b)$
$\displaystyle\triangleq\left(1+\left(\frac{b(1-\sigma(a))}{\sigma(a)(1-b)}\right)^{-20}\right)^{-1}$
(31)
$\displaystyle\tilde{\pi}_{\mathrm{D},\tilde{\bm{\theta}}^{(\mathrm{D})}}\big{(}\mathfrak{S}\mid
b(1)\big{)}$
$\displaystyle\triangleq\varphi\left(\tilde{\bm{\theta}}^{(\mathrm{D})}_{l},b(1)\right)$
(32)
$\displaystyle\tilde{\pi}_{\mathrm{A},\tilde{\bm{\theta}}^{(\mathrm{A})}}\big{(}\mathfrak{S}\mid
b(1),s\big{)}$
$\displaystyle\triangleq\varphi\left(\tilde{\bm{\theta}}^{(\mathrm{A})}_{sL+l},\pi_{\mathrm{D}}(\mathfrak{S}\mid
b(1))\right)$ (33)

The parameterized strategies defined by (31)–(33) are mixed (and
differentiable) strategies that approximate threshold strategies (see Fig. 7).
In (31)–(33), $\sigma(\cdot)$ is the sigmoid function, $a\in\mathbb{R}$, and
$b\in\mathbb{R}$. Further, $\sigma(\tilde{\bm{\theta}}^{(\mathrm{D})}_{1})$,
$\sigma(\tilde{\bm{\theta}}^{(\mathrm{D})}_{2})$, $\ldots$,
$\sigma(\tilde{\bm{\theta}}^{(\mathrm{D})}_{L})\in[0,1]$ are the $L$
thresholds of the defender (see Theorem 1.B) and
$\sigma(\tilde{\bm{\theta}}^{(\mathrm{A})}_{1})$,
$\sigma(\tilde{\bm{\theta}}^{(\mathrm{A})}_{2})$, $\ldots$,
$\sigma(\tilde{\bm{\theta}}^{(\mathrm{A})}_{2L})\in[0,1]$ are the $2L$
thresholds of the attacker (see Theorem 1.C).

$0.5$$1$$0.5$$1$$\tilde{\pi}_{\mathrm{D},l,\tilde{\bm{\theta}}^{(\mathrm{D})}}(\mathfrak{S}\mid
b(1))$threshold $\sigma(\tilde{\bm{\theta}}^{(\mathrm{D})}_{l})$$b(1)$$0$

Figure 7: A mixed threshold strategy where
$\sigma(\tilde{\bm{\theta}}_{l}^{(\mathrm{D})})$ is the threshold ($0.5$ in
this example); the x-axis indicates the defender’s belief state $b(1)\in[0,1]$
and the y-axis indicates the probability prescribed by
$\tilde{\pi}_{\mathrm{D},\tilde{\bm{\theta}}^{(\mathrm{D})}}$ to the stop
action $\mathfrak{S}$.

Using this parameterization, t-fp learns the best response strategies
$\tilde{\pi}_{\mathrm{D},\tilde{\bm{\theta}}^{(\mathrm{D})}}$ and
$\tilde{\pi}_{\mathrm{A},\tilde{\bm{\theta}}^{(\mathrm{A})}}$ by iteratively
updating the threshold vectors $\tilde{\bm{\theta}}^{(\mathrm{D})}$ and
$\tilde{\bm{\theta}}^{(\mathrm{A})}$ through stochastic approximation. To
update the threshold vectors, t-fp simulates $\Gamma$, which allows to
evaluate the objective functions
$J_{\mathrm{D}}(\tilde{\pi}_{\mathrm{D},\tilde{\bm{\theta}}^{(\mathrm{D})}},\pi_{\mathrm{A}})$
and
$J_{\mathrm{A}}(\pi_{\mathrm{D}},\tilde{\pi}_{\mathrm{A},\tilde{\bm{\theta}}^{(\mathrm{A})}})$
(16)–(17). The obtained values of $J_{\mathrm{D}}$ and $J_{\mathrm{A}}$ are
then used to estimate the gradients
$\nabla_{\tilde{\bm{\theta}}^{(\mathrm{D})}}J_{\mathrm{D}}$ and
$\nabla_{\tilde{\bm{\theta}}^{(\mathrm{A})}}J_{\mathrm{A}}$ using the
Simultaneous Perturbation Stochastic Approximation (spsa) gradient estimator
(lines 10-19 in Algorithm 1) [100, §2] [101, §3]. Next, the estimated
gradients are used to update $\tilde{\bm{\theta}}^{(\mathrm{D})}$ and
$\tilde{\bm{\theta}}^{(\mathrm{A})}$ through stochastic gradient ascent (line
20).

The above procedure of estimating gradients and updating
$\tilde{\bm{\theta}}^{(\mathrm{D})}$ and $\tilde{\bm{\theta}}^{(\mathrm{A})}$
continues for a given number of iterations (lines 9-21). After these
iterations have finished, the threshold vectors
$\tilde{\bm{\theta}}^{(\mathrm{D})}$ and $\tilde{\bm{\theta}}^{(\mathrm{A})}$
are added to buffers $\Theta^{(\mathrm{D})}$ and $\Theta^{(\mathrm{A})}$,
which contain the vectors learned in previous iterations of t-fp (line 22).
Finally, the t-fp iteration step is completed by having both players update
their strategies based on the empirical distributions over the past vectors in
the buffers (lines 24-25).

The sequence of iteration steps described above continues until the strategies
have sufficiently converged to a Nash equilibrium (lines 6-27). (In Algorithm
1, $\mathcal{U}_{k}(\\{-1,1\\})$ denotes a $k$-dimensional discrete
multivariate uniform distribution on $\\{-1,1\\}$ and $\pi_{-i}$ denotes the
strategy of player $j\in\mathcal{N}\setminus\\{i\\}$.)

Algorithm 1 t-fp: Threshold Fictitious Self-Play

Input
$\Gamma,N$: the posg and $\\#$ best response iterations
$a,c,\lambda,A,\epsilon,\delta$: scalar coefficients
Output
$(\pi^{*}_{\mathrm{D}},\pi^{*}_{\mathrm{A}})$: an approximate Nash equilibrium

1:procedure t-fp

2: $\tilde{\bm{\theta}}^{(\mathrm{D})}\sim\mathcal{U}_{L}(\\{-1,1\\})$,
$\quad\tilde{\bm{\theta}}^{(\mathrm{A})}\sim\mathcal{U}_{2L}(\\{-1,1\\})$

3:
$\Theta^{(\mathrm{D})}\leftarrow\\{\tilde{\bm{\theta}}^{(\mathrm{D})}\\},\quad\Theta^{(\mathrm{A})}\leftarrow\\{\tilde{\bm{\theta}}^{(\mathrm{A})}\\},\quad\hat{\delta}\leftarrow\infty$

4:
$\pi_{\mathrm{D}}\leftarrow\text{{EmpiricalDistribution}($\Theta^{(\mathrm{D})}$)}$

5:
$\pi_{\mathrm{A}}\leftarrow\text{{EmpiricalDistribution}($\Theta^{(\mathrm{A})}$)}$

6: while $\hat{\delta}\geq\delta$ do

7: for $i\in\\{\mathrm{D},\mathrm{A}\\}=\\{1,2\\}$ do

8: $\tilde{\bm{\theta}}_{(1)}^{(i)}\sim\mathcal{U}_{iL}(\\{-1,1\\})$

9: for $n\in\\{1,\ldots,N\\}$ do

10: $a_{n}\leftarrow\frac{a}{(n+A)^{\epsilon}},\quad
c_{n}\leftarrow\frac{c}{n^{\lambda}}$

11: for $k\in\\{1,\ldots,iL\\}$ do

12: $(\Delta_{n})_{k}\sim\mathcal{U}_{1}(\\{-1,1\\})$

13: end for

14: $R_{high}\sim
J_{i}(\pi_{i,\tilde{\bm{\theta}}^{(i)}_{(n)}}+c_{n}\Delta_{n},\pi_{-i})$

15: $R_{low}\sim
J_{i}(\pi_{i,\tilde{\bm{\theta}}^{(i)}_{(n)}}-c_{n}\Delta_{n},\pi_{-i})$

16: for $k\in\\{1,\ldots,iL\\}$ do

17: $G\leftarrow\frac{R_{high}-R_{low}}{2c_{n}(\Delta_{n})_{k}}$

18:
$\left(\hat{\nabla}_{\tilde{\bm{\theta}}^{(i)}_{(n)}}J_{i}(\pi_{i,\tilde{\bm{\theta}}^{(i)}_{(n)}},\pi_{-i})\right)_{k}\leftarrow
G$

19: end for

20:
$\tilde{\bm{\theta}}^{(i)}_{(n+1)}=\tilde{\bm{\theta}}^{(i)}_{(n)}+a_{n}\hat{\nabla}_{\tilde{\bm{\theta}}^{(i)}_{(n)}}J_{i}(\pi_{i,\tilde{\bm{\theta}}^{(i)}_{(n)}},\pi_{-i})$

21: end for

22: $\Theta^{(i)}\leftarrow\Theta^{(i)}\cup\tilde{\bm{\theta}}^{(i)}_{(N+1)}$

23: end for

24:
$\pi_{\mathrm{D}}\leftarrow\text{{EmpiricalDistribution}($\Theta^{(\mathrm{D})}$)}$

25:
$\pi_{\mathrm{A}}\leftarrow\text{{EmpiricalDistribution}($\Theta^{(\mathrm{A})}$)}$

26: $\hat{\delta}=\text{{Exploitability}}(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$

27: end while

28: return $(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$

29:end procedure

##  V Emulating the Target Infrastructure
to Instantiate the Simulation
and to Evaluate Learned Strategies

The t-fp algorithm described above approximates a Nash equilibrium of $\Gamma$
by simulating game episodes and updating both players’ strategies through
stochastic approximation. t-fp requires the observation distribution
conditioned on the system state $f_{O\mid s}$ (13)–(14). The emulation system
shown in Fig. 2 allows us to estimate this distribution and later to evaluate
the learned strategies.

This section describes the emulation system, our method for estimating
$f_{O\mid s}$, and our method for evaluating defender strategies.

###  V-A Emulating the Target Infrastructure

The emulation system executes on a cluster of machines that runs a
virtualization layer provided by Docker containers and virtual links [102].
The system implements network isolation and traffic shaping using network
namespaces and the netem module in the Linux kernel [103]. Resource allocation
to containers, e.g. cpu and memory, is enforced using cgroups.

The network topology of the emulated infrastructure is shown in Fig. 1 and its
configuration is given in Appendix C. The emulation system includes the
clients, the attacker, the defender, network connectivity, and $31$ devices of
the target infrastructure (e.g. application servers and the gateway). The
software functions on the emulation system replicate important components of
the target infrastructure, such as, web servers, databases, and the Snort
idps, which is deployed using Snort’s community ruleset v2.9.17.1.

We emulate connections between servers 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 [104, 105, 106].)

Technical documentation and application programming interfaces (apis) of the
emulation system are available in [107].

###  V-B Emulating the Client Population

The client population is emulated by processes in Docker containers. Clients
interact with application servers through the gateway by performing a sequence
of functions on a sequence of servers, both of which are selected uniformly at
random from Table 2. Client arrivals per time-step are emulated using a
stationary Poisson process with mean $\lambda=20$ and exponentially
distributed service times with mean $\mu=4$. The duration of a time-step is
$30$ seconds.

Functions | Application servers
---|---
http, ssh, snmp, icmp | $N_{2},N_{3},N_{10},N_{12}$
irc, postgres, snmp | $N_{31},N_{13},N_{14},N_{15},N_{16}$
ftp, dns, telnet | $N_{10},N_{22},N_{4}$
TABLE 2: Emulated client population; each client invokes functions on
application servers.

###  V-C Emulating Defender and Attacker Actions

The defender and the attacker observe the infrastructure continuously and take
actions at time-steps $t=1,2,\ldots,T$. During each step, the defender and the
attacker perform one action each.

The defender executes either a continue action or a stop action. A continue
action is virtual in the sense that it does not trigger any function in the
emulation. A stop action, however, invokes specific functions in the emulated
infrastructure. We have implemented $L=7$ stop actions for the defender, which
are listed in Table 3. The first stop action revokes user certificates and
recovers user accounts expected to be compromised by the attacker. The second
stop action updates the firewall configuration of the gateway to drop traffic
from IP addresses flagged by the idps. Stop actions $3$–$6$ trigger the
dropping of traffic that generates idps alerts of priorities $1$–$4$. The
final stop action blocks all incoming traffic. (Note that according to Snort’s
terminology, $1$ is the highest priority. We inverse the labeling in our
framework for convenience.)

Stop index | Action
---|---
$1$ | Revoke user certificates
$2$ | Blacklist IPs
$3$ | Drop traffic that generates idps alerts of priority $1$
$4$ | Drop traffic that generates idps alerts of priority $2$
$5$ | Drop traffic that generates idps alerts of priority $3$
$6$ | Drop traffic that generates idps alerts of priority $4$
$7$ | Block gateway

TABLE 3: Defender commands executed on the emulation system. Type | Actions
---|---
Reconnaissance |  tcp syn scan, udp port scan,
|  tcp null scan, tcp xmas scan, tcp fin scan,
| ping scan, tcp connection scan, vulscan
Brute-force attack |  telnet, ssh, ftp, cassandra,
|  irc, mongodb, mysql, smtp, postgres
Exploit |  cve-2017-7494, cve-2015-3306,
|  cve-2010-0426, cve-2015-5602,
|  cve-2014-6271, cve-2016-10033
|  cve-2015-1427, cwe-89
TABLE 4: Attacker commands executed on the emulation system; exploits are
identified according to their corresponding vulnerability and its identifier
in the Common Vulnerabilities and Exposures (cve) database [108] and in the
Common Weakness Enumeration (cwe) list [109].

Like the defender, the attacker executes either a stop action or a continue
action during each time-step. The attacker can only take two stop actions
during a game episode. The first determines when the intrusion starts and the
second when it terminates (see §III).

During an intrusion, the attacker executes a sequence of commands, drawn
randomly from all of the commands listed in Table 4. (Detailed descriptions of
all commands are available in Appendix E). The first command in this sequence
is executed when the attacker takes the first stop action. A further command
is invoked whenever the attacker takes a continue action.

###  V-D Estimating the idps Alert Distribution

At the end of every time-step, the emulation system collects the number of
idps alerts with priorities $1$–$4$ that occurred during the time-step. These
values are then used to compute the metric $o_{t}$, which contains the total
number of idps alerts, weighted by priority.

Figure 8: Empirical distributions of $o_{t}$ when no intrusion occurs
($s_{t}=0$) and during intrusion ($s_{t}=1$); the black lines show the fitted
Gaussian mixture models.

For the evaluation reported in this paper we collect measurements from
$23,000$ time-steps. Using these measurements, we apply expectation-
maximization [110] to fit Gaussian mixture distributions $\hat{f}_{O\mid 0}$
and $\hat{f}_{O\mid 1}$ as estimates of $f_{O\mid 0}$ and $f_{O\mid 1}$
(13)–(14).

Fig. 8 shows the empirical distributions and the fitted models over the
discrete observation space $\mathcal{O}=\\{1,2,\ldots,9000\\}$.
$\hat{f}_{O\mid 0}$ and $\hat{f}_{O\mid 1}$ are Gaussian mixtures with two and
three components, respectively. Both mixtures have most probability mass
within $0$–$1000$. $\hat{f}_{O\mid 1}$ also has substantial probability mass
at larger values.

The stochastic matrix with the rows $\hat{f}_{O\mid 0}$ and $\hat{f}_{O\mid
1}$ has about $72\times 10^{6}$ second-order minors, which are almost all non-
negative. This suggests to us that the tp-2 assumption in Theorem 1 can be
made.

###  V-E Running a Game Episode

During a game episode, the state evolves according to the dynamics defined by
(2)–(6), the defender’s belief state evolves according to (15), the players’
rewards are calculated using the reward function $\mathcal{R}$ (7)–(12), the
defender’s observations are obtained from $f_{O}$ (13)–(14), and the actions
of both players are determined by their respective strategies. If the game
runs in the emulation system, the players’ actions include executing
networking and computing functions (see Tables 3–4), and the observations from
$f_{O}$ are obtained through reading log files and metrics of the emulated
infrastructure. (To collect the logs and system metrics from the emulation, we
run software sensors that write to a distributed queue implemented with Kafka
[111].) In the case of a game in the simulation system, the observations are
instead sampled from the estimated distribution $\hat{f}_{O}$.

##  VI Learning Nash Equilibrium Strategies for the Target Infrastructure

Our approach to finding near-optimal defender strategies includes: (i)
emulating the target infrastructure to obtain statistics for instantiating the
simulation system; (ii) learning Nash equilibrium strategies using the t-fp
algorithm in §IV; and (iii) evaluating learned strategies on the emulation
system in §V (see Fig. 2). This section describes the learning process and the
evaluation results of the intrusion response use case.

###  VI-A Learning Equilibrium Strategies through Self-Play

Figure 9: Learning curves from the self-play process with t-fp; the red curve
shows simulation results and the blue curves show emulation results; the
purple, orange, and black curves relate to baseline strategies; the figures
show different performance metrics: exploitability (34), episodic reward, and
the length of intrusion; the curves indicate the mean and the $95\%$
confidence interval over four training runs with different random seeds.

We run t-fp for $500$ iteration steps to estimate a Nash equilibrium using the
iterative method in §IV-B, which is sufficient to meet the termination
condition (line 6 in Algorithm 1). These iteration steps generate a sequence
of strategy pairs
$(\pi_{\mathrm{D}},\pi_{\mathrm{A}})_{1},\allowbreak(\pi_{\mathrm{D}},\pi_{\mathrm{A}})_{2},\allowbreak\ldots,\allowbreak(\pi_{\mathrm{D}},\pi_{\mathrm{A}})_{500}$.

At the end of each iteration step, we evaluate the current strategy pair
$(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$ by running $500$ evaluation episodes in
the simulation system and $5$ evaluation episodes in the emulation system.
This process allows us to produce learning curves for different performance
metrics (see Fig. 9).

The $500$ training iterations and the associated evaluations constitute one
training run. We run four training runs with different random seeds. A single
training run takes about $5$ hours of processing time in the simulation
system. In addition, it takes around $12$ hours to evaluate the strategies on
the emulation system. The hyperparameters of t-fp are listed in Appendix B.

Computing environment for simulation and emulation. The environment for
running simulations and training strategies is a tesla p100 gpu.

The emulated infrastructure is deployed on a server with a $24$-core intel
xeon gold $2.10$ GHz cpu and $768$ gb ram. Documentation of the emulation
system is available in [107].

The code for the simulation system and the measurement traces for the
intrusion response use case are available at [112]. They can be used to
validate our results and to extend this research.

Convergence metric for t-fp. To estimate the convergence of the sequence of
strategy pairs generated by t-fp, we use the approximate exploitability metric
$\hat{\delta}$ [113]:

$\displaystyle\hat{\delta}=J_{\mathrm{D}}(\hat{\pi}_{\mathrm{D}},\pi_{\mathrm{A}})+J_{\mathrm{A}}(\pi_{\mathrm{D}},\hat{\pi}_{\mathrm{A}})$
(34)

where $\hat{\pi}_{i}$ denotes an approximate best response strategy for player
$i$ and the objective functions $J_{\mathrm{D}}$ and $J_{\mathrm{A}}$ are
defined in (16) and (17), respectively. The closer $\hat{\delta}$ becomes to
$0$, the closer $(\pi_{\mathrm{D}},\pi_{\mathrm{A}})$ is to a Nash
equilibrium.

Baseline algorithms. We compare the performance of t-fp with that of two
popular algorithms in previous work that use reinforcement learning and study
use cases similar to ours [74, 114, 115, 95, 116]. The first algorithm is
Neural Fictitious Self-Play (nfsp) [117], which is a general fictitious self-
play algorithm that does not exploit the threshold structures expressed in
Theorem 1. The second algorithm is Heuristic Search Value Iteration (hsvi) for
one-sided posgs [115], which is a state-of-the-art dynamic programming
algorithm for one-sided posgs.

Defender baseline strategies. We compare the dynamic defender strategies
learned through t-fp with three static baseline strategies. The first baseline
prescribes the stop action when an idps alert occurs, i.e., when $o_{t}>0$.
The second baseline is derived from the Snort idps, which is a de-facto
industry standard and can be considered state-of-the-art for our use case.
This baseline uses the Snort idps’s recommendation system and takes a stop
action when Snort has dropped $100$ IP packets (see Appendix C for the Snort
configuration). The third baseline assumes prior knowledge of the intrusion
time and performs all $L$ stops during the $L$ subsequent time-steps.

Although a growing body of work uses reinforcement learning and game theory to
find intrusion response strategies (see §VII for a review of the related
work), a direct comparison between the defender strategies learned in our
framework and those found in previous work is not feasible for two reasons.
First, nearly all of the prior works have developed defender strategies for
custom simulations [11, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 35, 37,
36, 73, 74, 40, 41, 65, 63, 66, 76, 75, 118, 119, 120, 121, 122, 71, 72, 123,
124, 125, 8, 126, 127, 11, 128, 129, 130, 57, 77, 78] and there is no obvious
way to map their solutions to an emulated environment like ours (see Fig. 1
and Appendix C). Second, the few prior works that study emulated
infrastructures similar to ours either consider static attackers in fully
observed environments [30, 31, 32, 131, 33, 38, 39, 53, 50] or focus on use
cases that are different from the one considered in this article [131, 132].

###  VI-B Evaluating the Learned Strategies

Figure 10: Probability of the stop action $\mathfrak{S}$ by the learned
equilibrium strategies in function of $b(1)$ and $l$; the left and middle
plots show the attacker’s stopping probability when $s=0$ and $s=1$,
respectively; the right plot shows the defender’s stopping probability.

Figure 11: Comparison between t-fp and two baseline algorithms: nfsp and hsvi;
all curves show simulation results; the red curve relates to t-fp; the blue
curve to nfsp; the purple curve to hsvi; the left plot shows the approximate
exploitability metric (34) and the right plot shows the hsvi approximation
error [115]; the curves depicting t-fp and nfsp show the mean and the $95\%$
confidence interval over four training runs with different random seeds.

Figure 9 shows the learning curves of the strategies obtained during the t-fp
self-play process and the baselines introduced above. The red curve represents
the results from the simulator; the blue curves show the results from the
emulation system; the purple curves give the performance of the Snort idps
baseline; the orange curves relate to the baseline strategy that mandates a
stop action when an idps alert occurs; and the dashed black curve gives the
performance of the baseline strategy that assumes prior knowledge of the
intrusion time.

We note that all learning curves in Fig. 9 converge, which suggests that the
learned strategies converge as well. (Fig. 9 only shows the first $120$
iterations of the $500$ iterations we performed, as the curves converge after
$100$ iterations.) Specifically, we observe that the approximate
exploitability (34) 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 emulation system. Further, we see
from the plot in the middle that both baseline strategies show decreasing
performance as the attacker updates its strategy. In contrast, the defender
strategy learned through t-fp improves its performance over time. This shows
the benefit of a game-theoretic approach where the defender strategy is
optimized against a dynamic attacker. Lastly, we notice that the average
intrusion length when the defender follows the learned defender strategy and
the Snort idps baseline strategy is $2$ and $3$, respectively (right plot). In
comparison, the average intrusion length when the defender follows the
baseline strategy $o_{t}>0$ is close to $0$, which indicates that it tends to
prescribe all stop actions before an intrusion occurs.

Figure 10 represents the strategies learned through t-fp in a simple form. The
y-axis shows the probability of a stop action and the x-axis shows the
defender’s belief $b(1)\in\mathcal{B}$ that an intrusion occurs. The
strategies are clearly stochastic. This is consistent with Theorem 1.A, which
predicts a mixed Nash equilibrium. Further, Theorem 1.B predicts that the
defender’s stopping probability is increasing with respect to $b(1)$ and
decreasing with $l$, which is visible in the right plot. Similarly, Theorem
1.C predicts that the attacker’s stopping probability decreases with the
defender’s stopping probability when $s=0$ and increases when $s=1$, which can
be seen in the left and the middle plot.

Figure 11 compares t-fp with the two baseline algorithms nfsp and hsvi on the
simulator. nfsp implements fictitious self-play and can thus be compared with
t-fp with respect to approximate exploitability (34). We observe in the left
plot that t-fp converges much faster than nfsp. We explain the rapid
convergence of t-fp by its design, which exploits structural properties of the
stopping game.

The right plot shows that hsvi reaches an hsvi approximation error below $5$
within an hour of processing time. Based on the recent literature we
anticipated a much longer processing time [88, 95]. This suggests to us that
t-fp and hsvi have similar convergence properties. A more detailed comparison
between t-fp and hsvi is hard to perform due to the different nature of the
two algorithms.

Figure 12 shows the estimated value function of the game
$\hat{V_{l}^{*}}:\mathcal{B}\rightarrow\mathbb{R}$ (23), where
$\hat{V_{l}^{*}}(b(1))$ is the expected cumulative reward when the game starts
in the belief state $b(1)$, the defender has $l$ stops remaining, and both
players follow optimal (equilibrium) strategies.

We see in Fig. 12 that $\hat{V_{l}^{*}}$ is piece-wise linear and convex, as
expected from the theory of one-sided posgs [88]. The figure indicates that
$\hat{V_{l}^{*}}(b(1))\leq 0$ for all $b(1)\in\mathcal{B}$ and that
$\hat{V_{l}^{*}}(1)=0$ for all $l\in\\{1,\ldots,L\\}$. Further, we note that
the value of $\hat{V_{l}^{*}}$ is minimal when $b(1)$ is around $0.25$ and
that the values for $l=1$ and $l=7$ are very close.

$\hat{V}^{*}_{7}(b(1))$$\hat{V}^{*}_{1}(b(1))$$1$$b(1)$$0$$-0.25$

Figure 12: The value function $\hat{V_{l}^{*}}(b(1))$ (23) computed through
the hsvi algorithm with approximation error $4$; the blue and red curves
relate to $l=7$ and $l=1$, respectively.

That $\hat{V_{l}^{*}}(b(1))\leq 0$ for all $b(1)\in\mathcal{B}$ and all
$l\in\\{1,\ldots,L\\}$ has an intuitive explanation. For any $b(1)$, the
attacker has the option to never attack if $s=0$ or to abort an attack if
$s=1$. Both options yield a cumulative reward less than or equal to $0$
(7)–(12). As a consequence, $\hat{V_{l}^{*}}(b(1))\leq 0$ for any optimal
attacker strategy and all $b(1)\in\mathcal{B}$ and $l\in\\{1,\ldots,L\\}$.
(Recall that the attacker aims to minimize reward.)

The fact that $\hat{V_{l}^{*}}(b(1))=0$ when $b(1)=1$ can be understood as
follows. $b(1)=1$ means that the defender knows that an intrusion occurs and
will take defensive actions (see Theorem 1.B). Hence, when $b(1)=1$, the only
way for the attacker to avoid detection is to abort the intrusion, which
causes the game to end and yields a reward of zero, i.e.
$\hat{V_{l}^{*}}(1)=0$ for all $l\in\\{1,\ldots,L\\}$.

We interpret the fact that
$\operatorname*{arg\,min}_{b(1)}\hat{V_{l}^{*}}(b(1))$ is around $0.25$ as
follows. The value of $b(1)$ that obtains the minimum corresponds to the
belief state where the attacker achieves the lowest expected reward in the
game. Negative rewards in the game are obtained when the defender mistakes an
intrusion for no intrusion and vice versa (7)–(12). As a consequence, the
attacker prefers belief states where the defender has a high uncertainty, e.g.
$b(1)=0.5$. At the same time, the attacker does not want $b(1)$ to be so large
that the defender performs all its defensive actions before it gets a chance
to attack, which can explain why we find the minimum to be around $0.25$
rather than $0.5$.

Lastly, Fig. 13 shows the percentage of blocked attacker and client traffic
when running repeated game episodes in the emulation system with different
defender strategies. The x-axis shows the running time and the y-axis shows
the percentage of blocked traffic per second.

We observe in the upper plot that all defender strategies block some client
traffic, which is expected considering the false idps alarms generated by the
clients (see Fig. 8). (The defender actions that cause traffic to be dropped
are listed in Table 3.) The $o_{t}>0$ baseline strategy blocks the most client
traffic and the Snort idps baseline strategy blocks the least, slightly less
than the equilibrium strategy learned through t-fp.

We further observe in the lower plot that the equilibrium strategy learned by
t-fp blocks the most attacker traffic and that the $o_{t}>0$ baseline strategy
blocks the least. This suggests to us that the equilibrium strategy balances
well the trade-off between blocking clients and the attacker based on the
reward function (7)–(12). In comparison, the $o_{t}>0$ baseline implements a
trivial defense strategy that blocks nearly all traffic, and the Snort idps
baseline blocks too little traffic, failing to stop the intrusion.

Figure 13: Percentage of blocked attacker and client traffic in the emulation
system; the blue curves show results from the equilibrium strategy learned via
t-fp; the purple, orange, and black curves relate to baseline strategies.

###  VI-C Discussion of the Evaluation Results

In this work, we propose a framework for analyzing and solving the intrusion
response use case, which we validate both theoretically and experimentally via
simulation and emulation. The key findings can be summarized as follows:

(i) Our framework is able to efficiently approximate optimal defender
strategies for a practical IT infrastructure (see Fig. 9). While we have not
evaluated the learned strategies in the target infrastructure due to safety
reasons, the fact that they achieve almost the same performance in the
emulated infrastructure as in the simulator gives us confidence that the
obtained strategies would perform as expected in the target infrastructure.

(ii) The theory of optimal stopping provides insight about optimal strategies
for attackers and defenders, which enables efficient computation of near-
optimal strategies through self-play reinforcement learning (see Fig. 11).
This finding can be explained by the threshold structures of the optimal
stopping strategies, which drastically reduce the search space of possible
strategies (see Theorem 1 and Algorithm 1).

(iii) The learned strategies can be efficiently implemented using the
threshold properties. The computational complexity, which is dominated by the
computation of the belief state, is upper bounded by
$O(k|\mathcal{S}|^{2}|\mathcal{A}_{\mathrm{A}}|)$ where $k$ is a constant
(15).

(iv) Static defender strategies’ performance deteriorate against a dynamic
attacker, whereas defender strategies obtained through t-fp improve over time
(see the middle plot in Fig. 9). This finding is consistent with previous
studies that use game-theoretic approaches (e.g. [70, 71]) and suggests
limitations of static defense systems, such as the Snort idps.

##  VII Related Work

Since the early 1990s, there has been a broad interest in automating network
security functions, especially in the areas of intrusion detection, intrusion
prevention, and intrusion response.

In the area of intrusion detection, the traditional approach has been to use
packet inspection and static rules for detection of intrusions [81, 133, 1].
The main drawback of this approach lies in the need for domain experts to
configure the rule sets. As a consequence, much effort has been devoted to
developing statistical methods for detecting intrusions. Examples of
statistical methods include anomaly detection methods (e.g. [134]), change-
point detection methods (e.g. [135]), Bayesian methods (e.g. [136]), hidden
Markov modeling methods (e.g. [137]), deep learning methods (e.g. [138, 139]),
and threat intelligence methods (e.g. [15]). As a result of this effort, all
mainstream idss today have statistical components for automated detection of
intrusions [140, 81, 141, 80, 142].

In contrast to intrusion detection, intrusion prevention and response usually
remains a manual process performed by network administrators. Current ipss and
irss can be configured with rules to automatically match response actions to
known intrusion types, but they have no means to find effective response
actions in an automatic way [81, 79, 143, 144]. The problem of automatically
finding response actions is an active area of research that uses concepts and
methods from various fields, most notably from reinforcement learning (see
surveys [17, 18, 145] and textbook [146]), control theory (see surveys [3, 4,
147] and example [64]), causal modeling (see example [9]), game theory (see
textbooks [7, 148, 149, 150]), graph theory (see examples [151, 152]), fuzz
testing (see examples [153, 154]), formal synthesis (see example [155]),
attack graphs (see example [144]), artificial intelligence (see surveys [156,
157] and textbook [158]), and evolutionary methods (see examples [5, 6]).

While the research reported in this paper is informed by all the above works,
we limit the following discussion to prior work that uses game-theoretic
models and centers around finding security strategies through automatic
control and reinforcement learning.

###  VII-A Game-Theoretic Modeling in Network Security

Since the early 2000s, researchers have studied automated security through
modeling attacks and response actions on an IT infrastructure as a game
between an attacker and a defender (see textbooks [7, 148, 149, 150]). The
game is modeled in different ways depending on the use case. Examples from the
literature include: advanced persistent threat games [70, 71, 72, 119, 120,
75, 56, 159], honeypot placement games [123, 124, 125], resource allocation
games [160, 40], authentication games [8], distributed denial-of-service games
[131, 126], situational awareness games [161, 162], moving target defense
games [163, 118], jamming games [78], and intrusion response games [127, 11,
30, 128, 129, 130, 122, 132, 47, 52, 76, 57, 77]. These games are formulated
using various models from the game-theoretic literature. For example:
Stochastic Games (sgs) (see e.g. [8, 72, 127, 130, 57, 78]), extensive-form
games (see e.g. [129, 7]), Blotto games (see e.g. [40]), differential games
(see e.g. [121, 77]), hypergames (see e.g. [119, 120]), posgs (see e.g. [126,
11, 30, 47, 52]), Stackelberg games (see e.g. [126, 128, 132]), graph-based
games (see e.g. [160, 118]), evolutionary games (see e.g. [121, 122]),
continuous-kernel games (see e.g. [129]), rivalry games (see e.g. [56]), and
Bayesian games (see e.g. [163]).

This paper differs from the works referenced above in two main ways. First, we
model the intrusion response use case as an optimal stopping game. The benefit
of our model is that it provides insight into the structure of best response
strategies through the theory of optimal stopping. Second, we evaluate
obtained strategies on an emulated IT infrastructure. This contrasts with most
of the prior works that use game-theoretic approaches, which either evaluate
strategies analytically or in simulation [70, 71, 72, 123, 124, 125, 8, 126,
127, 11, 128, 129, 130, 122, 121, 120, 119, 118, 75, 76, 56, 159, 57, 78].

Game-theoretic formulations based on optimal stopping theory can be found in
prior research on Dynkin games [60, 164, 165, 166, 167]. Compared to these
articles, our approach is more general by (i) allowing each player to take
multiple stop actions within an episode; and (ii) by not assuming a game of
perfect information. Another difference is that the referenced articles either
study purely mathematical problems or problems in mathematical finance. To the
best of our knowledge, we are the first to apply the stopping game formulation
to the use case of intrusion response.

Our stopping game has similarities with the flipit game [70] and signaling
games [168], both of which are commonplace in the security literature (see
survey [169] and textbooks [7, 148, 149, 150]). Signaling games have the same
information asymmetry as our game and flipit uses the same binary state space
to model the state of an attack. The main differences are as follows. flipit
models the use case of advanced persistent threats and is a symmetric non-
zero-sum game. In contrast, our game models an intrusion response use case and
is an asymmetric zero-sum game. Lastly, compared to signaling games, the main
difference is that our game is a sequential and simultaneous-move game.
Signaling games, in comparison, are typically two-stage games where one player
moves in each stage.

Previous game-theoretic studies that use emulation systems similar to ours are
[131] and [132]. Specifically, in [131], a denial-of-service use case is
formulated as a signaling game, for which a Nash equilibrium is derived. The
equilibrium is then used to design a defense mechanism that is evaluated in a
software-defined network emulation based on mininet [170]. Compared to this
paper, the main differences are that we focus on a different use case than
[131] and that our solution method is based on reinforcement learning.

Similar to this paper, the authors of [132] formulate an intrusion response
use case as a posg where the defender observes alerts from a Snort idps [81].
In contrast to our approach, however, the approach of [132] assumes access to
attack-defense trees designed by human experts. Another difference between
this paper and [132] is the posg. The posg in [132] has a larger state space
than the posg considered in this paper. Although this makes the posg in [132]
more expressive than ours, it also makes computation of optimal defender
strategies intractable. In fact, to estimate optimal defender strategies, the
authors of [132] are forced to approximate their model with one that has a
smaller state space and is fully observed. In comparison, we are able to
efficiently approximate equilibria of our game, without relying on model
simplifications and without assuming access to attack-defense trees designed
by human experts.

###  VII-B Control Theory for Automated Intrusion Response

Control theory provides a well-established mathematical framework for studying
automatic systems. Classical control systems involve actuators in the physical
world (e.g. electric power systems [171]) and many studies have focused on
applying control theory to automate intrusion responses in cyber-physical
systems (see surveys [172, 173, 174]).

The control framework can also be applied to computing systems and interest in
control theory among researchers in IT security is growing (see survey [4]).
As opposed to classical control theory, which is focused on continuous-time
systems, the research on applying control theory to computing systems is
focused almost entirely on discrete-time systems. The main reason being that
measurements from computer systems are solicited on a sampled basis, which is
best described by a discrete-time model [147, 175].

Previous works that apply control theory to the use case of intrusion response
include: [63, 64, 65, 66, 176, 177, 178]. All of which model the problem of
selecting response actions as the problem of controlling a discrete-time
dynamical system and obtain optimal defender strategies through dynamic
programming.

The main limitation of the works referenced above is that dynamic programming
does not scale to problems of practical size due to the curse of
dimensionality [179, 180].

###  VII-C Reinforcement Learning for Automated Intrusion Response

Reinforcement learning has emerged as a promising approach to approximate
optimal control strategies in scenarios where exact dynamic programming is not
applicable, and fundamental breakthroughs demonstrated by systems like alphago
in 2016 [181] and openai five in 2019 [182] have inspired us and other
researchers to study reinforcement learning with the goal to automate security
functions (see surveys [17, 18]).

A large number of studies have focused on applying reinforcement learning to
use cases similar to the intrusion response use case we discuss in this paper
[11, 12, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54,
76, 10, 67, 57]. These works use a variety of models, including mdps [22, 25,
27, 28, 33, 36, 38, 44, 53, 54, 67], sgs [20, 11, 30, 35, 47, 76, 69], attack
graphs [37], Petri nets [45], and pomdps [12, 29, 23, 10], as well as various
reinforcement learning algorithms, including Q-learning [20, 22, 25, 73, 42,
45, 50, 67], sarsa [23], ppo [11, 12, 37, 36, 39], hierarchical reinforcement
learning [27], dqn [28, 38, 39, 40, 41, 47, 53], Thompson sampling [29],
muzero [30], nfq [31], ddqn [33, 52], nfsp [74, 114], a2c [44], a3c [51], and
ddpg [32, 35].

This paper differs from the works referenced above in three main ways. First,
we model the intrusion response use case as a partially observed stochastic
game. Most of the other works model the use case as a single-agent mdp or
pomdp. The advantage of the game-theoretic model is that it allows finding
defender strategies that are effective against a dynamic attacker, i.e. an
attacker that adapts its strategy in response to the defender strategy.

Second, in a novel approach, we derive structural properties of optimal
defender strategies in the game using optimal stopping theory.

Third, our method to find effective defender strategies includes using an
emulation system in addition to a simulation system. The advantage of our
method compared to the simulation-only approaches [11, 12, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 35, 37, 36, 73, 74, 40, 41, 46, 47, 48, 52, 54, 54, 76,
67, 57] is that the parameters of our simulation system are determined by
measurements from an emulation system instead of being chosen by a human
expert. Further, the learned strategies are evaluated in the emulation system,
not in the simulation system. As a consequence, the evaluation results give
higher confidence of the obtained strategies’ performance in the target
infrastructure than what simulation results would provide.

Some prior work on automated learning of security strategies that make use of
emulation are: [50], [30], [31], [32], [33], [38], [49], [51], [53], [55], and
[39]. They either emulate software-defined networks based on mininet [170] or
use custom testbeds. The main differences between these efforts and the work
described in this article are: (i) we develop our own emulation system which
allows for experiments with a large variety of exploits; (ii) we focus on a
different use case (most of the referenced works study denial-of-service
attacks); (iii) we do not assume that the defender has perfect observability;
(iv) we do not assume a static attacker; and (v) we use an underlying
theoretical framework to formalize the use case, derive structural properties
of optimal strategies, and test these properties in an emulation system.

Finally, [183], [184], and [185] describe efforts in building emulation
platforms for reinforcement learning and cyber defense, which resemble our
emulation system. In contrast to these articles, our emulation system has been
built to investigate the specific use case of intrusion response and forms an
integral part of our general solution method (see Fig. 2).

##  VIII Conclusion and Future Work

In this work, we combine a formal framework with a practical evaluation to
address the problem of automated intrusion response. We formulate the
interaction between an attacker and a defender as an optimal stopping game.
This formulation gives us insight into the structure of optimal strategies,
which we prove to have threshold properties. Based on this knowledge, we
develop a fictitious self-play algorithm, Threshold Fictitious Self-Play
(t-fp), which learns near-optimal strategies in an efficient way. The results
from running t-fp show that the learned strategies converge to an approximate
Nash equilibrium and thus to near-optimal strategies (see Fig. 9). The results
also demonstrate that t-fp converges faster than a state-of-the-art fictitious
self-play algorithm by taking advantage of threshold properties of optimal
strategies (see Fig. 11). The threshold properties further enable us to
provide a graphic representation of the learned strategies in a simple form
(see Fig. 5 and Fig. 10).

To assess the learned strategies in a real environment, we evaluate them in a
system that emulates our target infrastructure (see Fig. 1). The results show
that the strategies achieve almost the same performance in the emulated
infrastructure as in the simulation. This gives us confidence that the
obtained strategies would perform as expected in the target infrastructure,
which is not feasible to evaluate directly.

We plan to continue this work in several directions. First, we will extend the
current model of the attacker and the defender, which currently captures only
timing of actions, to include decisions about a range of attacker and defender
actions. Second, we plan to combine the strategies learned through our
framework with techniques for online play, such as rollout [186]. Third, we
plan to study techniques that allow to obtain defender strategies that
generalize to a variety of infrastructure configurations and topologies.
Fourth, we intend to extend our framework to an online-learning setting where
the defender strategies co-evolve with changes in the target infrastructure.

##  IX Acknowledgments

This research has been supported in part by the Swedish armed forces and was
conducted at KTH Center for Cyber Defense and Information Security (CDIS). The
authors would like to thank Pontus Johnson for his useful input to this
research, and Forough Shahab Samani and Xiaoxuan Wang for their constructive
comments on a draft of this paper. The authors are also grateful to Branislav
Bosanský for sharing the code of the hsvi algorithm for one-sided posgs and to
Jakob Stymne for contributing to our implementation of nfsp.

##  Appendix A Proofs

###  A-A Proof of Theorem 1.A

  * Proof.

Since the posg $\Gamma$ in (1) is finite and $\gamma\in(0,1)$, the existence
proofs in [86, §3] and [88, Thm. 2.3] apply, which state that a mixed Nash
equilibrium exists. For the sake of brevity we do not restate the proofs,
which are based on formulating the posg as a finite strategic form game and
appealing to Nash’s theorem [83, Thm. 1].

We prove that a pure Nash equilibrium exists when $s=0\iff b(1)=0$ using a
proof by construction. It follows from (7)–(12) and (18) that the pure
strategy defined by $\bar{\pi}_{\mathrm{D}}(0)=\mathfrak{C}$ and
$\bar{\pi}_{\mathrm{D}}(b(1))=\mathfrak{S}\iff b(1)>0$ is a best response for
the defender against any attacker strategy when $s=0\iff b(1)=0$. Similarly,
given $\bar{\pi}_{\mathrm{D}}$, we conclude from (7)–(12) and (19) that the
pure strategy defined by $\bar{\pi}_{\mathrm{A}}(b(1),0)=\mathfrak{C}$ and
$\bar{\pi}_{\mathrm{A}}(b(1),1)=\mathfrak{S}$ for all $b(1)\in[0,1]$ is a best
response for the attacker. Hence,
$(\bar{\pi}_{\mathrm{D}},\bar{\pi}_{\mathrm{A}})$ is a pure Nash equilibrium
(20). ∎

###  A-B Proof of Theorem 1.B.

  * Proof.

Given the posg $\Gamma$ (1) and a fixed attacker strategy $\pi_{\mathrm{A}}$,
any best response strategy for the defender
$\tilde{\pi}_{\mathrm{D}}\in\mathscr{B}_{\mathrm{D}}(\pi_{\mathrm{A}})$ is an
optimal strategy in a pomdp $\mathcal{M}^{P}$ (see §IV). Hence, it is
sufficient to show that there exists an optimal strategy
$\pi_{\mathrm{D}}^{*}$ in $\mathcal{M}^{P}$ that satisfies (28). Conditions
for (28) to hold and the existence proof are given in our previous work
[10][Thm 1.C]. Since $f_{O\mid s}$ is tp-2 by assumption and all of the
remaining conditions hold by definition of $\Gamma$ (1), the result follows. ∎

###  A-C Proof of Theorem 1.C.

Given the posg $\Gamma$ (1) and a fixed defender strategy $\pi_{\mathrm{D}}$,
any best response strategy for the attacker
$\tilde{\pi}_{\mathrm{A}}\in\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})$ is an
optimal strategy in an mdp $\mathcal{M}$ (see §IV). Hence, it is sufficient to
show that there exists an optimal strategy $\pi_{\mathrm{A}}^{*}$ in
$\mathcal{M}$ that satisfies (29)–(30). To prove this, we use properties of
$\mathcal{M}$’s value function $V_{\pi_{\mathrm{D}},l}^{*}$ (22).

We use the value iteration algorithm to establish properties of
$V_{\pi_{\mathrm{D}},l}^{*}$ [89, 90]. Let $V_{\pi_{\mathrm{D}},l}^{k}$,
$\mathscr{S}^{k,(\mathrm{A})}_{s,l,\pi_{\mathrm{D}}}$, and
$\mathscr{C}^{k,(\mathrm{A})}_{s,l,\pi_{\mathrm{D}}}$, denote the value
function, the stopping set (25), and the continuation set (27) at iteration
$k$ of the value iteration algorithm, respectively. Then,
$\lim_{k\rightarrow\infty}V_{\pi_{\mathrm{D}},l}^{k}=V_{\pi_{\mathrm{D}},l}^{*}$,
$\lim_{k\rightarrow\infty}\mathscr{S}^{k,(\mathrm{A})}_{s,l,\pi_{\mathrm{D}}}=\mathscr{S}^{(\mathrm{A})}_{s,l,\pi_{\mathrm{D}}}$,
and
$\lim_{k\rightarrow\infty}\mathscr{C}^{k,(\mathrm{A})}_{s,l,\pi_{\mathrm{D}}}$
$=\mathscr{C}^{(\mathrm{A})}_{s,l,\pi_{\mathrm{D}}}$ [89, Thm 6.3.1][90, Thm.
7.6.2-7.6.3]. We define
$V_{\pi_{\mathrm{D}},l}^{0}\big{(}$$(s,b(1))$$\big{)}=0$ for all
$b(1)\in[0,1]$, $s\in\mathcal{S}$ and $l\in\\{1,\ldots,L\\}$.

Towards the proof of Theorem 1.C, we state the following six lemmas.

######  Lemma 1.

Given any defender strategy $\pi_{\mathrm{D}}$,
$V^{*}_{\pi_{\mathrm{D}},l}\big{(}$$s,b(1)\big{)}$ $\geq 0$ for all
$s\in\mathcal{S}$ and $b(1)\in[0,1]$.

  * Proof.

Consider $\bar{\pi}_{\mathrm{A}}$ defined by
$\bar{\pi}_{\mathrm{A}}(0,\cdot)=\mathfrak{C}$ and
$\bar{\pi}_{\mathrm{A}}(1,\cdot)=\mathfrak{S}$. Then it follows from (7)–(12)
that for any $\pi_{\mathrm{D}}\in\Pi_{\mathrm{D}}$, any $s\in\mathcal{S}$, and
any $b(1)\in[0,1]$, the following holds:
$V^{\bar{\pi}_{\mathrm{A}}}_{\pi_{\mathrm{D}},l}(s,b(1))\geq 0$. By
optimality, $V^{\bar{\pi}_{\mathrm{A}}}_{\pi_{\mathrm{D}},l}(s,b(1))\leq
V^{*}_{\pi_{\mathrm{D}},l}(s,b(1))$. Hence,
$V^{*}_{\pi_{\mathrm{D}},l}(s,b(1))\geq 0$. ∎

######  Lemma 2.

$V^{*}_{\pi_{\mathrm{D}},l}\big{(}$$b(1),1\big{)}$ is non-increasing with
$\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ and non-decreasing with
$l\in\\{1,\ldots,L\\}$.

  * Proof.

We prove this statement by mathematical induction. For $k=1$, we know from
(7)–(12) that $V^{1}_{\pi_{\mathrm{D}},l}\big{(}$$1$, $b(1)\big{)}$ is non-
increasing with $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ and non-decreasing
with $l$.

For $k>1$, $V^{k}_{\pi_{\mathrm{D}},l}$ is given by:

$\displaystyle
V^{k}_{\pi_{\mathrm{D}},l}\big{(}b(1),1\big{)}=\max\Big{[}0,-\mathcal{R}\big{(}1,(\mathfrak{C},a^{(\mathrm{D})})\big{)}$
(35) $\displaystyle+(1-\phi_{l})\sum_{o}f_{O}(o\mid
1)V^{k-1}_{l-a^{(\mathrm{D})}}\big{(}b(1),1\big{)}\Big{]}$

The first term inside the maximization in (35) is trivially non-increasing
with $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ and non-decreasing with $l$.
Assume by induction that the statement of Lemma 2 holds for
$V^{k-1}_{\pi_{\mathrm{D}},l}\big{(}$$s$, $b(1)\big{)}$. Then the second term
inside the maximization in (35) is non-increasing with
$\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ and non-decreasing with $l$ by
(7)–(12) and the induction hypothesis. Hence,
$V^{k}_{\pi_{\mathrm{D}},l}\big{(}$$s$, $b(1)\big{)}$ is non-increasing with
$\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ and non-decreasing with $l$ for all
$k\geq 0$. ∎

######  Lemma 3.

If $f_{O}$ is tp-2 and $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ is increasing
with $b(1)$, then $V_{\pi_{\mathrm{D}},l}(b(1),1)\geq\sum_{o}f_{O}(o\mid
1)V_{\pi_{\mathrm{D}},l}(b^{o}(1),1)$, where $b^{o}(1)$ denotes $b(1)$ updated
with (15) after observing $o\in\mathcal{O}$.

  * Proof.

Since $f_{O}$ is tp-2, it follows from [90, Thm. 10.3.1, pp. 225 and 238] and
[10, Lemma 4, pp. 12] that given two beliefs $b^{\prime}(1)\geq b(1)$ and
given two observations $o\geq\bar{o}$, the following holds for any
$k\in\mathcal{O}$ and $l\in\\{1,\ldots,L\\}$: $b^{\prime,o}(1)\geq b^{o}(1)$,
$\mathbb{P}[o\geq k\mid b^{\prime}(1)]\geq\mathbb{P}[o\geq k\mid b(1)]$, and
$b_{a}^{o}(1)\geq b_{a}^{\bar{o}}(1)$.

Since $\pi_{\mathrm{D}}$ is increasing with $b(1)$ and
$V_{\pi_{\mathrm{D}},l}(b(1),1)$ is decreasing with $b(1)$ (Lemma 2), it
follows that $\mathbb{E}_{o}[b^{o}(1)]\geq b(1)$, and thus
$V_{\pi_{\mathrm{D}},l}(b(1),1)\geq\sum_{o}f_{O}(o\mid
1)V_{\pi_{\mathrm{D}},l}(b^{o}(1),1)$. ∎

######  Lemma 4.

If $f_{O}$ is tp-2, $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))=1$, and
$\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ is increasing with $b(1)$, then
$V^{*}_{\pi_{\mathrm{D}},l}\big{(}$$s,$$b(1)\big{)}$$=0$ and for any
$\tilde{\pi}_{\mathrm{A}}\in\mathscr{B}_{\mathrm{A}}(\pi_{\mathrm{D}})$,
$\tilde{\pi}_{\mathrm{A}}$$(1,$$b(1))$$=\mathfrak{S}$.

  * Proof.

From (21)–(23) we know that $\tilde{\pi}_{\mathrm{A}}(b(1),1)=\mathfrak{S}$
iff:

$\displaystyle\frac{\mathrm{R}_{\mathrm{st}}}{l}+(\phi_{l}-1)\sum_{o}f_{O}(o\mid
1)V^{*}_{\pi_{\mathrm{D}},l-a^{(1)}}(b^{o}(1),1)\geq 0$ (36)

We know that $\mathrm{R}_{\mathrm{st}}\geq 0$ (see §III). Further, since
$f_{O}$ is tp-2, $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))=1$, and since
$\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ is increasing with $b(1)$, we have
by Lemma 3 that $\mathbb{E}_{o}[\pi_{\mathrm{D}}(\mathfrak{S}\mid
b^{o}(1))]=1$. As a consequence, the second term in the left-hand side of (36)
is zero. Hence, the inequality holds and $\tilde{\pi}_{\mathrm{A}}(b(1),1)=1$,
which implies that $V^{*}_{\pi_{\mathrm{D}},l}\big{(}$$s,b(1)\big{)}=0$. ∎

######  Lemma 5.

Given any defender strategy $\pi_{\mathrm{D}}\in\Pi_{\mathrm{D}}$, if
$\pi^{*}_{\mathrm{A}}(b(1),1)=\mathfrak{S}$, then
$\pi^{*}_{\mathrm{A}}(b(1),0)=\mathfrak{C}$.

  * Proof.

$\pi^{*}_{\mathrm{A}}$$(1,$$b(1))$$=\mathfrak{S}$ implies that
$V^{*}_{\pi_{\mathrm{D}},l}$$(1,$$b(1))$$=0$. Hence, it follows from Lemma 3
that:

$\displaystyle(1-\phi_{l})\sum_{o\in\mathcal{O}}f_{O}(o\mid
1)V^{*}_{\pi_{\mathrm{D}},l}(b^{o},1)\leq 0$ (37)
$\displaystyle\implies\sum_{o\in\mathcal{O}}f_{O}(o\mid
1)V^{*}_{\pi_{\mathrm{D}},l}(b^{o},1)\leq\sum_{o\in\mathcal{O}}f_{O}(o\mid
0)V^{*}_{\pi_{\mathrm{D}},l}(b^{o},0)$
$\displaystyle\implies\pi^{*}_{\mathrm{A}}(b(1),0)=\mathfrak{C}$

∎

######  Lemma 6.

If $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ is non-decreasing with $b(1)$ and
$f_{O}$ is tp-2, then
$V^{*}_{\pi_{\mathrm{D}},l}\big{(}$$b(1),0\big{)}-V^{*}_{\pi_{\mathrm{D}},l}\big{(}$$b(1),1\big{)}$
is non-decreasing with $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$.

  * Proof.

We prove this statement by mathematical induction. Let
$W^{k}_{\pi_{\mathrm{D}},l}(b(1))$
$=V^{k}_{\pi_{\mathrm{D}},l}\big{(}$$b(1),0\big{)}-V^{k}_{\pi_{\mathrm{D}},l}\big{(}$$b(1),1\big{)}$.
For $k=1$, it follows from (7)–(12) that $W^{1}_{\pi_{\mathrm{D}},l}(b(1))$ is
non-decreasing with $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))\in[0,1]$. Assume
by induction that the statement of Lemma 6 holds for
$W^{k-1}_{\pi_{\mathrm{D}},l}(b(1))$. We show that then the statement holds
also for $W^{k}_{\pi_{\mathrm{D}},l}(b(1))$.

There are three cases to consider:

    * –

If
$b(1)\in\mathscr{S}^{k,(\mathrm{A})}_{0,l,\pi_{\mathrm{D}}}\cap\mathscr{C}^{k,(\mathrm{A})}_{1,l,\pi_{\mathrm{D}}}$,
then:

$\displaystyle W^{k}_{\pi_{\mathrm{D}},l}(b(1))=\mathrm{R}_{\mathrm{int}}+$
(38) $\displaystyle\pi_{\mathrm{D}}(\mathfrak{S}\mid
b(1))\left(\frac{\mathrm{R}_{\mathrm{st}}}{l}-\frac{\mathrm{R}_{\mathrm{cost}}}{l}-\mathrm{R}_{\mathrm{int}}\right)$

The right-hand side of (38) is non-decreasing with
$\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ since
$\frac{\mathrm{R}_{\mathrm{st}}}{l}-\frac{\mathrm{R}_{\mathrm{cost}}}{l}-\mathrm{R}_{\mathrm{int}}\geq
0$ (see §III).

    * –

If
$b(1)\in\mathscr{C}^{k,(\mathrm{A})}_{0,l,\pi_{\mathrm{D}}}\cap\mathscr{C}^{k,(\mathrm{A})}_{1,l,\pi_{\mathrm{D}}}$,
then using (3) and (15):

$\displaystyle
W^{k}_{\pi_{\mathrm{D}},l}(b(1))=\pi_{\mathrm{D}}(\mathfrak{S}\mid
b(1))\Big{(}\frac{\mathrm{R}_{\mathrm{st}}}{l}-\frac{\mathrm{R}_{\mathrm{cost}}}{l}$
(39)
$\displaystyle-\mathrm{R}_{\mathrm{int}}\Big{)}+V^{k-1}_{\pi_{\mathrm{D}},l}\big{(}b(1),1\big{)}\Big{)}+\mathrm{R}_{\mathrm{int}}+\sum_{o}\Big{(}f_{O}(o\mid
0)\cdot$ $\displaystyle
V^{k}_{\pi_{\mathrm{D}},l}\big{(}b^{o}(1),0\big{)}-(1-\phi_{l})f_{O}(o\mid
1)V^{k}_{\pi_{\mathrm{D}},l}\big{(}b^{o}(1),1\big{)}\Big{)}$

The first term in the right-hand side of (39) is non-decreasing with
$\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ since
$\frac{\mathrm{R}_{\mathrm{st}}}{l}-\frac{\mathrm{R}_{\mathrm{cost}}}{l}-\mathrm{R}_{\mathrm{int}}\geq
0$ (see §III) and $V^{k-1}_{\pi_{\mathrm{D}},l}\big{(}b(1),1\big{)}\geq 0$ (it
is a consequence of Lemma 1 and (21)–(23)). The second term is non-decreasing
with $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ by the induction hypothesis and
the assumption that $f_{O}$ is tp-2.

    * –

If
$b(1)\in\mathscr{C}^{k,(\mathrm{A})}_{0,l,\pi_{\mathrm{D}}}\cap\mathscr{S}^{k,(\mathrm{A})}_{1,l,\pi_{\mathrm{D}}}$,
then:

$\displaystyle
W^{k}_{\pi_{\mathrm{D}},l}(b(1))=\pi_{\mathrm{D}}(\mathfrak{S}\mid
b(1))\left(-\frac{\mathrm{R}_{\mathrm{cost}}}{l}\right)$ (40)
$\displaystyle+\sum_{o}f_{O}(o\mid
0)V^{k}_{\pi_{\mathrm{D}},l}\big{(}b^{o}(1),0\big{)}$
$\displaystyle=\pi_{\mathrm{D}}(\mathfrak{S}\mid
b(1))\left(-\frac{\mathrm{R}_{\mathrm{cost}}}{l}\right)+\sum_{o}\Big{(}f_{O}(o\mid
0)\cdot$ (41) $\displaystyle
V^{k}_{\pi_{\mathrm{D}},l}\big{(}b^{o}(1),0\big{)}-(1-\phi_{l})f_{O}(o\mid
1)V^{k}_{\pi_{\mathrm{D}},l}\big{(}b^{o}(1),1\big{)}\Big{)}$

The first term in the right-hand side of (40) is non-decreasing with
$\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ since
$-\frac{\mathrm{R}_{\mathrm{cost}}}{l}\geq 0$. The second term is non-
decreasing with $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ by the induction
hypothesis and the assumption that $f_{O}$ is tp-2. (41) follows from Lemma 3
and the fact that
$b(1)\in\mathscr{S}^{k,(\mathrm{A})}_{1,l,\pi_{\mathrm{D}}}$.

The other cases, e.g.
$b(1)\in\mathscr{S}^{k,(\mathrm{A})}_{0,l,\pi_{\mathrm{D}}}\cap\mathscr{S}^{k,(\mathrm{A})}_{1,l,\pi_{\mathrm{D}}}$,
can be discarded due to Lemma 5. Hence, $W^{k}_{\pi_{\mathrm{D}},l}(b(1))$ is
non-decreasing with $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ for all $k\geq
0$. ∎

We now use Lemmas 1-6 to prove Theorem 1.C. The main idea behind the proof is
to show that the stopping sets in state $s=1$ have the form:
$\mathscr{S}^{(\mathrm{A})}_{1,l,\pi_{\mathrm{D}}}=[\tilde{\beta}_{1,l},1]$,
and that the continuation sets in state $s=0$ have the form:
$\mathscr{C}^{(\mathrm{A})}_{0,l,\pi_{\mathrm{D}}}=[\tilde{\beta}_{0,l},1]$,
for some values
$\tilde{\beta}_{0,1},\tilde{\beta}_{1,1},\ldots,\tilde{\beta}_{0,L},\tilde{\beta}_{1,L}\in[0,1]$.

  * Proof of Theorem 1.C.

We first show that $1\in\mathscr{S}^{(\mathrm{A})}_{1,l,\pi_{\mathrm{D}}}$ and
that $1\in\mathscr{C}^{(\mathrm{A})}_{0,l,\pi_{\mathrm{D}}}$. Since
$\pi_{\mathrm{D}}(\mathfrak{S}\mid 1)=1$, it follows from Lemma 4 that
$1\in\mathscr{S}^{(\mathrm{A})}_{1,l,\pi_{\mathrm{D}}}$ and as a consequence
of (21)–(23) we have that $\tilde{\pi}_{\mathrm{A}}(b(1),0)=\mathfrak{C}$ iff:

$\displaystyle\sum_{o}f_{O}(o\mid 0)V^{*}_{\pi_{\mathrm{D}},l-1}(b^{o}(1),0)-$
$\displaystyle f_{O}(o\mid 1)V^{*}_{\pi_{\mathrm{D}},l-1}(b^{o}(1),1)\geq 0$
(42)

The left-hand side of the above equation is positive since a) $f_{O}$ is
assumed to be tp-2; b) $\sum_{o}f_{O}(o\mid
0)V^{*}_{\pi_{\mathrm{D}},l-1}(b^{o}(1),0)\geq 0$ (Lemma 1); and c)
$f_{O}(o\mid 1)V^{*}_{\pi_{\mathrm{D}},l-1}(1,$$b^{o}(1))=0$ (Lemma 3). Hence,
$1\in\mathscr{C}^{(\mathrm{A})}_{0,l,\pi_{\mathrm{D}}}$.

Now we show that
$\mathscr{S}^{(\mathrm{A})}_{1,l,\pi_{\mathrm{D}}}=[\tilde{\beta}_{1,l},1]$
and that
$\mathscr{C}^{(\mathrm{A})}_{0,l,\pi_{\mathrm{D}}}=[\tilde{\beta}_{0,l},1]$
for some values
$\tilde{\beta}_{0,1},\tilde{\beta}_{1,1},\ldots,\tilde{\beta}_{0,L},\tilde{\beta}_{1,L}\in[0,1]$.
From (21)–(23) we know that $\tilde{\pi}_{2}(b(1),1)=\mathfrak{S}$ iff:

$\displaystyle\mathbb{E}_{\pi_{\mathrm{D}}}\Big{[}\mathcal{R}\big{(}1,(a^{(\mathrm{D})},\mathfrak{C})\big{)}+$
(43) $\displaystyle(\phi_{l}-1)\sum_{o}f_{O}(o\mid
1)V^{*}_{\pi_{\mathrm{D}},l-a^{(\mathrm{D})}}(b^{o}(1),1)\Big{]}\geq 0$

The first term in the left-hand side of (43) is increasing with $b(1)$
(7)–(12). Further, it follows from Lemma 2 that the second term is decreasing
with $b(1)$. Hence, we conclude that if
$\tilde{\pi}_{\mathrm{A}}(b(1),1)=\mathfrak{S}$, then for any
$b^{\prime}(1)\geq b(1)$,
$\tilde{\pi}_{\mathrm{A}}(b^{\prime}(1),1)=\mathfrak{S}$. As a consequence,
there exist values $\tilde{\beta}_{1,1},\ldots,\tilde{\beta}_{1,L}$ such that
$\mathscr{S}^{(\mathrm{A})}_{1,l,\pi_{\mathrm{D}}}=[\tilde{\beta}_{1,l},1]$.

Similarly, from (21)–(23) we know that
$\tilde{\pi}_{\mathrm{A}}(b(1),0)=\mathfrak{C}$ iff:

$\displaystyle\mathbb{E}_{\pi_{\mathrm{D}}}\Big{[}\sum_{o}f_{O}(o\mid
0)V^{*}_{\pi_{\mathrm{D}},l-a^{(\mathrm{D})}}(b^{o}(1),0)$ (44)
$\displaystyle-f_{O}(o\mid
1)V^{*}_{\pi_{\mathrm{D}},l-a^{(\mathrm{D})}}(b^{o}(1),1)\Big{]}\geq 0$

Since $f_{O}$ is tp-2 and $\pi_{\mathrm{D}}(\mathfrak{S}\mid b(1))$ is
increasing with $b(1)$, the left-hand side in (44) is decreasing (it follows
from Lemma 2 and Lemma 6). Hence, we conclude that if
$\tilde{\pi}_{\mathrm{A}}(b(1),0)=\mathfrak{C}$, then for any
$b^{\prime}(1)\geq b(1)$,
$\tilde{\pi}_{\mathrm{A}}(b^{\prime}(1),0)=\mathfrak{C}$. As a result, there
exist values $\tilde{\beta}_{0,1},\ldots,\tilde{\beta}_{0,L}$ such that
$\mathscr{C}^{(\mathrm{A})}_{0,l,\pi_{\mathrm{D}}}=[\tilde{\beta}_{0,l},1]$. ∎

##  Appendix B Hyperparameters

Game Parameters | Values
---|---
$\mathrm{R}_{\mathrm{st}},\mathrm{R}_{\mathrm{cost}},\mathrm{R}_{\mathrm{int}}$,$\gamma$, $\phi_{l}$, $L$ |  $20$, $-2$, $-1$, $0.99$, $1/2l$, $7$
t-fp Parameters | Values
$c,\epsilon,\lambda,A,a,N,\delta$ |  $10$, $0.101$, $0.602$, $100$, $1$, $50$, $0.2$
nfsp Parameters | Values
lr rl, lr sl, batch, # layers |  $10^{-2}$,$5\cdot 10^{-3}$, $64$, $2$
# neurons, $\mathcal{M}_{RL}$, $\mathcal{M}_{SL}$ |  $128$, $2\times 10^{5}$, $2\times 10^{6}$,
$\epsilon$, $\epsilon$-decay, $\eta$ |  $0.06$, $0.001$, $0.1$
hsvi Parameter | Value
$\epsilon$ | $3$

TABLE 5: Hyperparameters of the posg and the algorithms used for evaluation.

The hyperparameters used for the evaluation in this paper are listed in Table
5 and were obtained through grid search.

##  Appendix C Configuration of the Infrastructure in Fig. 1

The configuration of the target infrastructure shown in Fig. 1 is available in
Table 6.

ID (s) | OS:Services:Exploitable Vulnerabilities
---|---
$N_{1}$ |  ubuntu 20:snort (community ruleset v2.9.17.1),ssh:-
$N_{2}$ |  ubuntu 20:ssh,http Erl-Pengine,dns:cwe-1391
$N_{4}$ |  ubuntu 20:http flask,telnet,ssh:cwe-1391
$N_{10}$ |  ubuntu 20:ftp,mongodb,smtp,tomcat,ts 3,ssh:cwe-1391
$N_{12}$ |  jessie:ts 3,tomcat,ssh:cve-2010-0426,cwe-1391
$N_{17}$ |  wheezy:apache 2,snmp,ssh:cve-2014-6271
$N_{18}$ |  debian 9.2:irc,apache 2,ssh:cwe-89
$N_{22}$ |  jessie:proftpd,ssh,apache 2,snmp:cve-2015-3306
$N_{23}$ |  jessie:apache 2,smtp,ssh:cve-2016-10033
$N_{24}$ |  jessie:ssh:cve-2015-5602,cwe-1391
$N_{25}$ |  jessie: elastic,apache 2,ssh,snmp:cve-2015-1427
$N_{27}$ |  jessie:samba,ntp,ssh:cve-2017-7494
$N_{3}$,$N_{11}$,$N_{5}$-$N_{9}$ |  ubuntu 20:ssh,snmp,postgres,ntp:-
$N_{13-16}$,$N_{19-21}$,$N_{26}$,$N_{28-31}$ |  ubuntu 20:ntp, irc, snmp, ssh, postgres:-

TABLE 6: Configuration of the target infrastructure (Fig. 1).

##  Appendix D Distributions of Infrastructure Metrics

The emulation system (see Fig. 2) collects hundreds of metrics every time-
step. To measure the information that a metric provides for detecting
intrusions, we calculate the Kullback-Leibler (kl) divergence
$D_{\mathrm{KL}}(f_{O\mid 0}\parallel f_{O\mid 1})$ between the distribution
of the metric when no intrusion occurs $f_{O\mid s=0}$ and during an intrusion
$f_{O\mid s=1}$:

$\displaystyle D_{\mathrm{KL}}(f_{O\mid 0}\parallel f_{O\mid 1})$
$\displaystyle=\sum_{o\in\mathcal{O}}f_{O\mid 0}(o)\log\left(\frac{f_{O\mid
0}(o)}{f_{O\mid 1}(o)}\right)$ (45)

Here $O$ denotes the random variable representing the value of the metric and
$\mathcal{O}$ is the domain of $O$.

Figure 14 shows empirical distributions of the collected metrics with the
largest kl divergence. We see that the idps alerts have the largest kl
divergence and thus provide the most information for detecting intrusions.

Figure 14: Empirical distributions of selected infrastructure metrics; the red
and blue lines show the distributions when no intrusion occurs and during
intrusion, respectively.

##  Appendix E Attacker Actions

The attacker actions and their descriptions are listed in Table 7.

Action | Description
---|---
tcp scan |  tcp port scan by sending syn or empty packets (nmap)
udp port scan |  udp port scan by sending udp packets (nmap)
ping scan | IP scan with icmp ping messages
vulscan | vulnerability scan using nmap
brute-force attack | performs a dictionary attack against a login service (nmap)
cve-2017-7494 exploit | uploads malicious binary to the samba service and executes it
cve-2015-3306 exploit | uses the mod_copy in proftpd for remote code execution
cve-2014-6271 exploit | uses a vulnerability in bash for remote code execution
cve-2016-10033 exploit | uses phpmailer for remote code execution
cve-2015-1427 exploit | uses elasticsearch for remote code execution
cwe-89 exploit | injects malicious SQL code to execute code remotely

TABLE 7: Descriptions of the attacker actions.

## References

  * [1] A. Fuchsberger, “Intrusion detection systems and intrusion prevention systems,” _Inf. Secur. Tech. Rep._ , vol. 10, no. 3, p. 134–139, Jan. 2005\.
  * [2] S. Ayoubi, N. Limam, M. A. Salahuddin, N. Shahriar, R. Boutaba, F. Estrada-Solano, and O. M. Caicedo, “Machine learning for cognitive network management,” _IEEE Communications Magazine_ , vol. 56, no. 1, pp. 158–165, 2018.
  * [3] M. Rasouli, E. Miehling, and D. Teneketzis, “A supervisory control approach to dynamic cyber-security,” in _Decision and Game Theory for Security_ , 2014\.
  * [4] E. Miehling, M. Rasouli, and D. Teneketzis, _Control-Theoretic Approaches to Cyber-Security_. Cham: Springer International Publishing, 2019, pp. 12–28.
  * [5] R. Bronfman-Nadas, N. Zincir-Heywood, and J. T. Jacobs, “An artificial arms race: Could it improve mobile malware detectors?” in _2018 Network Traffic Measurement and Analysis Conference (TMA)_ , 2018.
  * [6] U.-M. O’Reilly and E. Hemberg, “An artificial coevolutionary framework for adversarial ai,” in _AAAI Fall Symposium: ALEC_ , 2018.
  * [7] T. Alpcan and T. Basar, _Network Security: A Decision and Game-Theoretic Approach_ , 1st ed. USA: Cambridge University Press, 2010.
  * [8] S. Sarıtaş, E. Shereen, H. Sandberg, and G. Dán, “Adversarial attacks on continuous authentication security: A dynamic game approach,” in _Decision and Game Theory for Security_ , Cham, 2019, pp. 439–458.
  * [9] A. Andrew, S. Spillard, J. Collyer, and N. Dhir, “Developing optimal causal cyber-defence agents via cyber security simulation,” in _Proceedings of the ML4Cyber workshop, ICML 2022, Baltimore, USA, July 17-23, 2022_. PMLR, 2022.
  * [10] K. Hammar and R. Stadler, “Intrusion prevention through optimal stopping,” _IEEE Transactions on Network and Service Management_ , vol. 19, no. 3, pp. 2333–2348, 2022.
  * [11] ——, “Finding effective security strategies through reinforcement learning and Self-Play,” in _International Conference on Network and Service Management (CNSM 2020)_ , Izmir, Turkey, 2020.
  * [12] ——, “Learning intrusion prevention policies through optimal stopping,” in _International Conference on Network and Service Management (CNSM 2021)_ , Izmir, Turkey, 2021, https://arxiv.org/pdf/2106.07160.pdf.
  * [13] P. Johnson, R. Lagerström, and M. Ekstedt, “A meta language for threat modeling and attack simulations,” in _Proceedings of the 13th International Conference on Availability, Reliability and Security_ , ser. ARES 2018, New York, NY, USA, 2018.
  * [14] N. Wagner, C. c. Şahin, M. Winterrose, J. Riordan, J. Pena, D. Hanson, and W. W. Streilein, “Towards automated cyber decision support: A case study on network segmentation for security,” in _2016 IEEE Symposium Series on Computational Intelligence (SSCI)_ , 2016.
  * [15] C. Wagner, A. Dulaunoy, G. Wagener, and A. Iklody, “Misp: The design and implementation of a collaborative threat intelligence sharing platform,” in _Proceedings of the 2016 ACM on Workshop on Information Sharing and Collaborative Security_ , ser. WISCS ’16. New York, NY, USA: Association for Computing Machinery, 2016, p. 49–56.
  * [16] R. S. Sutton and A. G. Barto, _Introduction to Reinforcement Learning_ , 1st ed. Cambridge, MA, USA: MIT Press, 1998\.
  * [17] T. T. Nguyen and V. J. Reddi, “Deep reinforcement learning for cyber security,” _IEEE transactions on neural networks and learning systems_ , vol. PP, 2021.
  * [18] Y. Huang, L. Huang, and Q. Zhu, “Reinforcement learning for feedback-enabled cyber resilience,” _Annual Reviews in Control_ , 2022.
  * [19] K. Hammar and R. Stadler, “An online framework for adapting security policies in dynamic it environments,” in _2022 18th International Conference on Network and Service Management (CNSM)_ , 2022, pp. 359–363.
  * [20] R. Elderman, L. J. J. Pater, A. S. Thie, M. M. Drugan, and M. Wiering, “Adversarial reinforcement learning in a cyber security simulation,” in _ICAART_ , 2017.
  * [21] J. Schwartz, H. Kurniawati, and E. El-Mahassni, “Pomdp + information-decay: Incorporating defender’s behaviour in autonomous penetration testing,” _Proceedings of the International Conference on Automated Planning and Scheduling_ , vol. 30, no. 1, Jun. 2020.
  * [22] F. M. Zennaro and L. Erdodi, “Modeling penetration testing with reinforcement learning using capture-the-flag challenges and tabular q-learning,” _CoRR_ , 2020, https://arxiv.org/abs/2005.12632.
  * [23] M. N. Kurt, O. Ogundijo, C. Li, and X. Wang, “Online cyber-attack detection in smart grid: A reinforcement learning approach,” _IEEE Transactions on Smart Grid_ , vol. 10, no. 5, pp. 5174–5185, 2019.
  * [24] W. Blum, “Gamifying machine learning for stronger security and ai models,” 2021, microsoft Research.
  * [25] A. Ridley, “Machine learning for autonomous cyber defense,” 2018, the Next Wave, Vol 22, No.1 2018.
  * [26] M. Zhu, Z. Hu, and P. Liu, “Reinforcement learning algorithms for adaptive cyber defense against heartbleed,” in _Proceedings of the First ACM Workshop on Moving Target Defense_ , ser. MTD ’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 51–58.
  * [27] K. Tran, A. Akella, M. Standen, J. Kim, D. Bowman, T. Richer, and C.-T. Lin, “Deep hierarchical reinforcement agents for automated penetration testing,” 2021, https://arxiv.org/abs/2109.06449.
  * [28] R. Gangupantulu, T. Cody, P. Park, A. Rahman, L. Eisenbeiser, D. Radke, and R. Clark, “Using cyber terrain in reinforcement learning for penetration testing,” 2021, https://arxiv.org/abs/2108.07124.
  * [29] Z. Hu, M. Zhu, and P. Liu, “Adaptive cyber defense against multi-stage attacks using learning-based pomdp,” _ACM Trans. Priv. Secur._ , vol. 24, no. 1, Nov. 2020.
  * [30] J. Gabirondo-López, J. Egaña, J. Miguel-Alonso, and R. Orduna Urrutia, “Towards autonomous defense of sdn networks using muzero based intelligent agents,” _IEEE Access_ , vol. 9, pp. 107 184–107 199, 2021.
  * [31] I. Akbari, E. Tahoun, M. A. Salahuddin, N. Limam, and R. Boutaba, “Atmos: Autonomous threat mitigation in sdn using reinforcement learning,” in _NOMS IEEE/IFIP Network Operations and Management Symposium_ , 2020, pp. 1–9.
  * [32] Y. Liu _et al._ , “Deep reinforcement learning based smart mitigation of ddos flooding in software-defined networks,” in _2018 IEEE 23rd International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD)_ , 2018, pp. 1–6.
  * [33] T. V. Phan and T. Bauschert, “Deepair: Deep reinforcement learning for adaptive intrusion response in software-defined networks,” _IEEE Transactions on Network and Service Management_ , pp. 1–1, 2022.
  * [34] K. Hammar and R. Stadler, “A system for interactive examination of learned security policies,” in _NOMS 2022-2022 IEEE/IFIP Network Operations and Management Symposium_ , 2022, pp. 1–3.
  * [35] L. Zhang, Y. Pan, Y. Liu, Q. Zheng, and Z. Pan, “Multiple domain cyberspace attack and defense game based on reward randomization reinforcement learning,” 2022.
  * [36] A. Dutta, E. Al-Shaer, and S. Chatterjee, “Constraints satisfiability driven reinforcement learning for autonomous cyber defense,” _CoRR_ , vol. abs/2104.08994, 2021.
  * [37] Y. Du, Z. Song, S. Milani, C. Gonzales, and F. Fang, “Learning to play an adaptive cyber deception game,” _The 13th Workshop on Optimization and Learning in Multiagent Systems, AAMAS 2022_ , 2022.
  * [38] N. M. Yungaicela-Naula, C. Vargas-Rosales, J. A. Pérez-Díaz, and D. F. Carrera, “A flexible sdn-based framework for slow-rate ddos attack mitigation by using deep reinforcement learning,” _Journal of Network and Computer Applications_ , vol. 205, p. 103444, 2022.
  * [39] M. Zolotukhin, S. Kumar, and T. Hämäläinen, “Reinforcement learning for attack mitigation in sdn-enabled networks,” in _2020 6th IEEE Conference on Network Softwarization (NetSoft)_ , 2020, pp. 282–286.
  * [40] T. Zhu, D. Ye, Z. Cheng, W. Zhou, and P. S. Yu, “Learning games for defending advanced persistent threats in cyber systems,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , 2022.
  * [41] Y. Liu, K.-F. Tsang, C. K. Wu, Y. Wei, H. Wang, and H. Zhu, “Ieee p2668-compliant multi-layer iot-ddos defense system using deep reinforcement learning,” _IEEE Transactions on Consumer Electronics_ , pp. 1–1, 2022.
  * [42] R. R. dos Santos, E. K. Viegas, A. O. Santin, and V. V. Cogo, “Reinforcement learning for intrusion detection: More model longness and fewer updates,” _IEEE Transactions on Network and Service Management_ , pp. 1–1, 2022.
  * [43] H. Liu, Y. Li, J. Mårtensson, L. Xie, and K. H. Johansson, “Reinforcement learning based approach for flip attack detection,” in _2020 59th IEEE Conference on Decision and Control (CDC)_ , 2020.
  * [44] R. Maeda and M. Mimura, “Automating post-exploitation with deep reinforcement learning,” _Computers & Security_, vol. 100, 2021.
  * [45] J. A. Bland, M. D. Petty, T. S. Whitaker, K. P. Maxwell, and W. A. Cantrell, “Machine learning cyberattack and defense strategies,” _Computers & Security_, vol. 92, p. 101738, 2020.
  * [46] L. Huang and Q. Zhu, “Radams: Resilient and adaptive alert and attention management strategy against informational denial-of-service (idos) attacks,” _Computers & Security_, vol. 121, p. 102844, 2022.
  * [47] X. Liu, H. Zhang, S. Dong, and Y. Zhang, “Network defense decision-making based on a stochastic game system and a deep recurrent q-network,” _Computers & Security_, vol. 111, p. 102480, 2021.
  * [48] P. Zhang, C. Wang, C. Jiang, and A. Benslimane, “Security-aware virtual network embedding algorithm based on reinforcement learning,” _IEEE Transactions on Network Science and Engineering_ , vol. 8, no. 2, pp. 1095–1105, 2021.
  * [49] J. Khoury and M. E. B. Nassar, “A hybrid game theory and reinforcement learning approach for cyber-physical systems security,” _NOMS 2020 - 2020 IEEE/IFIP Network Operations and Management Symposium_ , pp. 1–9, 2020.
  * [50] S. Wang, Q. Pei, J. Wang, G. Tang, Y. Zhang, and X. Liu, “An intelligent deployment policy for deception resources based on reinforcement learning,” _IEEE Access_ , vol. 8, pp. 35 792–35 804, 2020.
  * [51] Y. Han _et al._ , “Reinforcement learning for autonomous defence in software-defined networking,” in _Decision and Game Theory for Security_ , 2018, pp. 145–165.
  * [52] Y. Guo, Z. Wu, L. Tian, Y. Wang, J. Xie, Y. Du, and Y. Zhang, “Network security defense decision-making method based on stochastic game and deep reinforcement learning,” _Security and Communication Networks_ , vol. 2021, p. 2283786, 2021.
  * [53] S. Iannucci, E. Casalicchio, and M. Lucantonio, “An intrusion response approach for elastic applications based on reinforcement learning,” _2021 IEEE Symposium Series on Computational Intelligence (SSCI)_ , pp. 01–10, 2021.
  * [54] S. Iannucci, O. D. Barba, V. Cardellini, and I. Banicescu, “A performance evaluation of deep reinforcement learning for model-based intrusion response,” _2019 IEEE 4th International Workshops on Foundations and Applications of Self* Systems (FAS*W)_ , pp. 158–163, 2019.
  * [55] M. Wolk, A. Applebaum, C. Dennler, P. Dwyer, M. Moskowitz, H. Nguyen, N. Nichols, N. Park, P. Rachwalski, F. Rau, and A. Webster, “Beyond cage: Investigating generalization of learned autonomous network defense policies,” 2022.
  * [56] L. Zhang, T. Zhu, F. K. Hussain, D. Ye, and W. Zhou, “Defend to defeat: Limiting information leakage in defending against advanced persistent threats,” _IEEE Transactions on Information Forensics and Security_ , pp. 1–1, 2022.
  * [57] Y. Zhang and J. Liu, “Optimal decision-making approach for cyber security defense using game theory and intelligent learning,” _Security and Communication Networks_ , vol. 2019, p. 3038586, Dec 2019.
  * [58] G. Dulac-Arnold, N. Levine, D. J. Mankowitz, J. Li, C. Paduraru, S. Gowal, and T. Hester, “Challenges of real-world reinforcement learning: definitions, benchmarks and analysis,” _Machine Learning_ , vol. 110, no. 9, pp. 2419–2468, 2021.
  * [59] A. Wald, _Sequential Analysis_. Wiley and Sons, New York, 1947.
  * [60] E. Dynkin, “A game-theoretic version of an optimal stopping problem,” _Dokl. Akad. Nauk SSSR_ , vol. 385, pp. 16–19, 1969.
  * [61] A. N. Shiryaev, “On optimum methods in quickest detection problems,” _Theory Probab. Appl._ , vol. 8, no. 1, pp. 22–46, 1963.
  * [62] K. Hammar and R. Stadler, “A software framework for building self-learning security systems,” 2022, https://www.youtube.com/watch?v=18P7MjPKNDg.
  * [63] S. Iannucci, Q. Chen, and S. Abdelwahed, “High-performance intrusion response planning on many-core architectures,” in _2016 25th International Conference on Computer Communication and Networks (ICCCN)_ , 2016, pp. 1–6.
  * [64] O. P. Kreidl and T. M. Frazier, “Feedback control applied to survivability: a host-based autonomic defense system,” _IEEE Transactions on Reliability_ , vol. 53, pp. 148–166, 2004.
  * [65] S. Iannucci and S. Abdelwahed, “A probabilistic approach to autonomic security management,” in _2016 IEEE International Conference on Autonomic Computing (ICAC)_ , 2016, pp. 157–166.
  * [66] E. Miehling, M. Rasouli, and D. Teneketzis, “A pomdp approach to the dynamic defense of large-scale cyber networks,” _IEEE Transactions on Information Forensics and Security_ , vol. 13, no. 10, 2018.
  * [67] A. Applebaum, C. Dennler, P. Dwyer, M. Moskowitz, H. Nguyen, N. Nichols, N. Park, P. Rachwalski, F. Rau, A. Webster, and M. Wolk, “Bridging automated to autonomous cyber defense: Foundational analysis of tabular q-learning,” in _Proceedings of the 15th ACM Workshop on Artificial Intelligence and Security_ , ser. AISec’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 149–159.
  * [68] Y. Shi, Y. E. Sagduyu, T. Erpek, and M. C. Gursoy, “How to attack and defend nextg radio access network slicing with reinforcement learning,” _IEEE Open Journal of Vehicular Technology_ , pp. 1–11, 2022.
  * [69] K. Hughes, K. McLaughlin, and S. Sezer, “A model-free approach to intrusion response systems,” _Journal of Information Security and Applications_ , vol. 66, p. 103150, 2022.
  * [70] M. van Dijk, A. Juels, A. Oprea, and R. L. Rivest, “Flipit: The game of “stealthy takeover”,” _Journal of Cryptology_ , no. 4, Oct 2013.
  * [71] L. Huang and Q. Zhu, “A dynamic games approach to proactive defense strategies against advanced persistent threats in cyber-physical systems,” _Computers & Security_, vol. 89, p. 101660, 11 2019.
  * [72] S. Sengupta, A. Chowdhary, D. Huang, and S. Kambhampati, _General Sum Markov Games for Strategic Detection of Advanced Persistent Threats Using Moving Target Defense in Cloud Networks_ , 10 2019.
  * [73] Q. Xu, Z. Su, and R. Lu, “Game theory and reinforcement learning based secure edge caching in mobile social networks,” _IEEE Transactions on Information Forensics and Security_ , vol. 15, 2020.
  * [74] K. Li, B. Jiu, W. Pu, H. Liu, and X. Peng, “Neural fictitious self-play for radar anti-jamming dynamic game with imperfect information,” _IEEE Transactions on Aerospace and Electronic Systems_ , pp. 1–1, 2022.
  * [75] L. Huang and Q. Zhu, “A dynamic games approach to proactive defense strategies against advanced persistent threats in cyber-physical systems,” _Computers & Security_, vol. 89, p. 101660, 2020.
  * [76] B. Wang, Y. L. Sun, M. Sun, and X. Xu, “Game-theoretic actor–critic-based intrusion response scheme (gtac-irs) for wireless sdn-based iot networks,” _IEEE Internet of Things Journal_ , vol. 8, pp. 1830–1845, 2021.
  * [77] X. An, F. Lin, S. Xu, L. Miao, C. Gong, and L. Ma, “A novel differential game model-based intrusion response strategy in fog computing,” _Sec. and Commun. Netw._ , vol. 2018, jan 2018.
  * [78] E. Altman, K. Avrachenkov, and A. Garnaev, “A jamming game in wireless networks with transmission cost,” in _NET-COOP_ , 2007.
  * [79] Trellix, “Trellix intrusion prevention system,” 2022.
  * [80] W. Inc, “Wazuh - the open source security platform,” 2022.
  * [81] M. Roesch, “Snort - lightweight intrusion detection for networks,” in _Proceedings of the 13th USENIX Conference on System Administration_ , ser. LISA ’99. USA: USENIX Association, 1999, p. 229–238.
  * [82] K. Hammar and R. Stadler, “Learning security strategies through game play and optimal stopping,” in _Proceedings of the ML4Cyber workshop, ICML 2022, Baltimore, USA, July 17-23, 2022_. PMLR, 2022.
  * [83] J. F. Nash, “Non-cooperative games,” _Annals of Mathematics_ , vol. 54, pp. 286–295, 1951.
  * [84] J. von Neumann, “Zur Theorie der Gesellschaftsspiele. (German) [On the theory of games of strategy],” vol. 100, pp. 295–320, 1928.
  * [85] L. S. Shapley, “Stochastic games,” _Proceedings of the National Academy of Sciences_ , vol. 39, no. 10, pp. 1095–1100, 1953.
  * [86] J. Hespanha and M. Prandini, “Nash equilibria in partial-information games on markov chains,” in _Proceedings of the 40th IEEE Conference on Decision and Control (Cat. No.01CH37228)_ , vol. 3, 2001.
  * [87] R. Bellman, “A markovian decision process,” _Journal of Mathematics and Mechanics_ , vol. 6, no. 5, pp. 679–684, 1957.
  * [88] K. Horák, “Scalable algorithms for solving stochastic games with limited partial observability,” Ph.D. dissertation, 2019.
  * [89] M. L. Puterman, _Markov Decision Processes: Discrete Stochastic Dynamic Programming_ , 1st ed., USA, 1994.
  * [90] V. Krishnamurthy, _Partially Observed Markov Decision Processes: From Filtering to Controlled Sensing_. Cambridge University Press, 2016.
  * [91] G. Peskir and A. Shiryaev, _Optimal stopping and free-boundary problems_ , ser. Lectures in mathematics (ETH Zürich). Springer, 2006.
  * [92] Y. Chow, H. Robbins, and D. Siegmund, “Great expectations: The theory of optimal stopping,” 1971.
  * [93] T. Nakai, “The problem of optimal stopping in a partially observable markov chain,” _Journal of Optimization Theory and Applications_ , vol. 45, no. 3, pp. 425–442, Mar 1985.
  * [94] V. Krishnamurthy, A. Aprem, and S. Bhatt, “Multiple stopping time pomdps: Structural results & application in interactive advertising on social media,” _Automatica_ , vol. 95, pp. 385–398, 2018.
  * [95] K. Horák, B. Bosanský, V. Kovarík, and C. Kiekintveld, “Solving zero-sum one-sided partially observable stochastic games,” _CoRR_ , vol. abs/2010.11243, 2020.
  * [96] J. Goldsmith and M. Mundhenk, “Competition adds complexity,” in _Advances in Neural Information Processing Systems_ , J. Platt, D. Koller, Y. Singer, and S. Roweis, Eds., vol. 20. Curran Associates, Inc., 2007.
  * [97] C. H. Papadimitriou and J. N. Tsitsiklis, “The complexity of markov decision processes,” _Math. Oper. Res._ , vol. 12, p. 441–450, Aug. 1987.
  * [98] G. W. Brown, “Iterative solution of games by fictitious play,” 1951, activity analysis of production and allocation.
  * [99] Y. Shoham and K. Leyton-Brown, _Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations_. Cambridge, UK: Cambridge University Press, 2009.
  * [100] J. C. Spall, “Multivariate stochastic approximation using a simultaneous perturbation gradient approximation,” _IEEE TRANSACTIONS ON AUTOMATIC CONTROL_ , vol. 37, no. 3, pp. 332–341, 1992.
  * [101] J. Spall, “Implementation of the simultaneous perturbation algorithm for stochastic optimization,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 34, no. 3, pp. 817–823, 1998.
  * [102] D. Merkel, “Docker: lightweight linux containers for consistent development and deployment,” _Linux journal_ , vol. 2014, p. 2, 2014.
  * [103] S. Hemminger, “Network emulation with netem,” _Linux Conf_ , 2005.
  * [104] T. Kushida and Y. Shibata, “Empirical study of inter-arrival packet times and packet losses,” in _Proceedings of the 22nd International Conference on Distributed Computing Systems_ , 2002, p. 233–240.
  * [105] V. Paxson, “End-to-end internet packet dynamics,” in _IEEE/ACM Transactions on Networking_ , 1997, pp. 277–292.
  * [106] E. O. Elliott, “Estimates of error rates for codes on burst-noise channels,” _The Bell System Technical Journal_ , vol. 42, no. 5, 1963.
  * [107] K. Hammar, “Cyber security learning environment,” 2023, https://limmen.dev/csle/.
  * [108] T. M. Corporation, “Cve database,” 2022, https://cve.mitre.org/.
  * [109] ——, “Cwe list,” 2023, https://cwe.mitre.org/index.html.
  * [110] A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” _Journal of the Royal Statistical Society: Series B_ , vol. 39, pp. 1–38, 1977.
  * [111] J. Kreps, “Kafka : a distributed messaging system for log processing,” 2011.
  * [112] K. Hammar and R. Stadler, “gym-optimal-intrusion-response,” 2021, https://github.com/Limmen/gym-optimal-intrusion-response.
  * [113] F. Timbers, E. Lockhart, M. Schmid, M. Lanctot, and M. Bowling, “Approximate exploitability: Learning a best response in large games,” _CoRR_ , vol. abs/2004.09677, 2020.
  * [114] W. Xue, Y. Zhang, S. Li, X. Wang, B. An, and C. K. Yeo, “Solving large-scale extensive-form network security games via neural fictitious self-play,” 2021\.