#  Learning Intrusion Prevention Policies
through Optimal Stopping

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>

(June 11, 2021)

###### Abstract

We study automated intrusion prevention using reinforcement learning. In a
novel approach, we formulate the problem of intrusion prevention as an optimal
stopping problem. This formulation allows us insight into the structure of the
optimal policies, which turn out to be threshold based. Since the computation
of the optimal defender policy using dynamic programming is not feasible for
practical cases, we approximate the optimal policy through reinforcement
learning in a simulation environment. To define the dynamics of the
simulation, we emulate the target infrastructure and collect measurements. Our
evaluations show that the learned policies are close to optimal and that they
indeed can be expressed using thresholds.

###### Index Terms:

Network Security, automation, optimal stopping, reinforcement learning, Markov
Decision Processes

††publicationid: pubid: 978-3-903176-31-7 ©2021 IFIP

##  I Introduction

An organization’s security strategy has traditionally been defined,
implemented, and updated by domain experts [1]. Although this approach can
provide basic security for an organization’s communication and computing
infrastructure, a growing concern is that infrastructure update cycles become
shorter and attacks increase in sophistication. Consequently, the security
requirements become increasingly difficult to meet. As a response, significant
efforts are made to automate security processes and functions. Over the last
years, research directions emerged to automatically find and update security
policies. One such direction aims at automating the creation of threat models
for a given infrastructure [2]. A second direction focuses on evolutionary
processes that produce novel exploits and corresponding defenses [3]. In a
third direction, the interaction between an attacker and a defender is modeled
as a game, which allows attack and defense policies to be analyzed and
sometimes constructed using game theory [4, 5]. In a fourth direction,
statistical tests are used to detect attacks [6]. Further, the evolution of an
infrastructure and the actions of a defender is studied using the framework of
dynamical systems. This framework allows optimal policies to be obtained using
methods from control theory [7] or dynamic programming [8, 9]. In all of the
above directions, machine learning techniques are often applied to estimate
model parameters and policies [10, 11].

Many activities center around modeling the infrastructure as a discrete-time
dynamical system in the form of a Markov Decision Process (MDP). Here, the
possible actions of the defender are defined by the action space of the MDP,
the defender policy is determined by the actions that the defender takes in
different states, and the security objective is encoded in the reward
function, which the defender tries to optimize.

To find the optimal policy in an MDP, two main methods are used: dynamic
programming and reinforcement learning. The advantage of dynamic programming
is that it has a strong theoretical grounding and oftentimes allows to derive
properties of the optimal policy [12, 13]. The disadvantage is that it
requires complete knowledge of the MDP, including the transition
probabilities. In addition, the computational overhead is high, which makes it
infeasible to compute the optimal policy for all but simple configurations
[14, 13, 8]. Alternatively, reinforcement learning enables learning the
dynamics of the model through exploration. With the reinforcement learning
approach, it is often possible to compute close approximations of the optimal
policy for non-trivial configurations [10, 15, 14, 16]. As a drawback,
however, theoretical insights into the structure of the optimal policy
generally remain elusive.

In this paper, we study an intrusion prevention 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 a possible attacker
while, at the same time, providing a service to a client population. The
infrastructure includes a public gateway through which the clients access the
service and which also is open to a plausible attacker. The attacker decides
when to start an intrusion and then executes a sequence of actions that
includes reconnaissance and exploits. Conversely, the defender aims at
preventing intrusions and maintaining the service to its clients. It monitors
the infrastructure and can block outside access to the gateway, an action that
disrupts the service but stops any ongoing intrusion. What makes the task of
the defender difficult is the fact that it lacks direct knowledge of the
attacker’s actions and must infer that an intrusion occurs from monitoring
data.

We study the use case within the framework of discrete-time dynamical systems.
Specifically, we formulate the problem of finding an optimal defender policy
as an optimal stopping problem, where stopping refers to blocking access to
the gateway. Optimal stopping is frequently used to model problems in the
fields of finance and communication systems [17, 18, 6, 19]. To the best of
our knowledge, finding an intrusion prevention policy through solving an
optimal stopping problem is a novel approach.

By formulating intrusion prevention as an optimal stopping problem, we know
from the theory of dynamic programming that the optimal policy can be
expressed through a threshold that is obtained from observations, i.e. from
infrastructure measurements [13, 12]. This contrasts with prior works that
formulate the problem using a general MDP, which does not allow insight into
the structure of optimal policies [10, 11, 20, 21].

To account for the fact that the defender only has access to a limited number
of measurements and cannot directly observe the attacker, we model the optimal
stopping problem with a Partially Observed Markov Decision Process (POMDP). We
obtain the defender policies by simulating a series of POMDP episodes in which
an intrusion takes place and where the defender continuously updates its
policy based on outcomes of previous episodes. To update the policy, we use a
state-of-the-art reinforcement learning algorithm. This approach enables us to
find effective defender policies despite the uncertainty about the attacker’s
behavior and despite the large state space of the model.

We validate our approach to intrusion prevention for a non-trivial
infrastructure configuration and two attacker profiles. Through extensive
simulation, we demonstrate that the learned defender policies indeed are
threshold based, that they converge quickly, and that they are close to
optimal.

We make two contributions with this paper. First, we formulate the problem of
intrusion prevention as a problem of optimal stopping. This novel approach
allows us a) to derive properties of the optimal defender policy using results
from dynamic programming and b) to use reinforcement learning techniques to
approximate the optimal policy for a non-trivial configuration. Second, we
instantiate the simulation model with measurements collected from an emulation
of the target infrastructure, which reduces the assumptions needed to
construct the simulation model and narrows the gap between a simulation
episode and a scenario playing out in a real system. This addresses a
limitation of related work that rely on abstract assumptions to construct the
simulation model [10, 11, 20, 21].

Attacker

Clients $\ldots$

Defender$1$IDS $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 use case.

##  II The Intrusion Prevention Use Case

We consider an intrusion prevention 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,
at the same time, providing a service to a client population (Fig. 1). The
infrastructure includes a set of servers that run the service and an intrusion
detection system (IDS) that logs events in real-time. Clients access the
service through a public gateway, which also is open to the attacker.

We assume that the attacker intrudes into the infrastructure through the
gateway, performs reconnaissance, and exploits found vulnerabilities, while
the defender continuously monitors the infrastructure through accessing and
analyzing IDS statistics and login attempts at the servers. The defender has a
single action to stop the attacker, which involves blocking all outside access
to the gateway. As a consequence of this action, the service as well as any
ongoing intrusion are disrupted.

When deciding whether to block the gateway, the defender must balance two
objectives: to maintain the service to its clients and to keep a possible
attacker out of the infrastructure. The optimal policy for the defender is to
maintain service until the moment when the attacker enters through the
gateway, at which time the gateway must be blocked. The challenge for the
defender is to identify the precise time when this moment occurs.

In this work, we model the attacker as an agent that starts the intrusion at a
random point in time and then takes a predefined sequence of actions, which
includes reconnaissance to explore the infrastructure and exploits to
compromise the servers.

We study the use case from the defender’s perspective. The evolution of the
system state and the actions by the defender are modeled with a discrete-time
Partially Observed Markov Decision Process (POMDP). The reward function of
this process encodes the benefit of maintaining service and the loss of being
intruded. Finding an optimal defender policy thus means maximizing the
expected reward. To find an optimal policy, we solve an optimal stopping
problem, where the stopping action refers to blocking the gateway.

##  III Theoretical Background

This section contains background information on Markov decision processes,
reinforcement learning, and optimal stopping.

###  III-A Markov Decision Processes

A Markov Decision Process (MDP) models the control of a discrete-time
dynamical system and is defined by a seven-tuple
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},\mathcal{P}^{a_{t}}_{s_{t},s_{t+1}},\mathcal{R}^{a_{t}}_{s_{t},s_{t+1}},\gamma,\rho_{1},T\rangle$
[22, 23]. $\mathcal{S}$ denotes the set of states and $\mathcal{A}$ denotes
the set of actions. $\mathcal{P}^{a_{t}}_{s_{t},s_{t+1}}$ refers to the
probability of transitioning from state $s_{t}$ to state $s_{t+1}$ when taking
action $a_{t}$ (Eq. 1), which has the Markov property
$\mathbb{P}\left[s_{t+1}|s_{t}\right]=\mathbb{P}\left[s_{t+1}|s_{1},\ldots,s_{t}\right]$.
Similarly, $\mathcal{R}^{a_{t}}_{s_{t},s_{t+1}}\in\mathbb{R}$ is the expected
reward when taking action $a_{t}$ and transitioning from state $s_{t}$ to
state $s_{t+1}$ (Eq. 2). If $\mathcal{P}^{a_{t}}_{s_{t},s_{t+1}}$ and
$\mathcal{R}^{a_{t}}_{s_{t},s_{t+1}}$ are independent of the time-step $t$,
the MDP is said to be stationary. Finally, $\gamma\in\left(0,1\right]$ is the
discount factor, $\rho_{1}:\mathcal{S}\rightarrow[0,1]$ is the initial state
distribution, and $T$ is the time horizon.

$\displaystyle\mathcal{P}^{a_{t}}_{s_{t},s_{t+1}}=\mathbb{P}\left[s_{t+1}|s_{t},a_{t}\right]$
(1)
$\displaystyle\mathcal{R}^{a_{t}}_{s_{t},s_{t+1}}=\mathbb{E}\left[r_{t+1}|a_{t},s_{t},s_{t+1}\right]$
(2)

The system evolves in discrete time-steps from $t=1$ to $t=T$, which
constitute one episode of the system.

A Partially Observed Markov Decision Process (POMDP) is an extension of an MDP
[24, 13]. In contrast to an MDP, in a POMDP the states are not directly
observable. A POMDP is defined by a nine-tuple
$\mathcal{M}_{\mathcal{P}}=\langle\mathcal{S},\mathcal{A},\mathcal{P}^{a_{t}}_{s_{t},s_{t+1}},\mathcal{R}^{a_{t}}_{s_{t},s_{t+1}},\gamma,\rho_{1},T,\mathcal{O},\mathcal{Z}\rangle$.
The first seven elements define an MDP. $\mathcal{O}$ denotes the set of
observations and
$\mathcal{Z}(o_{t+1},s_{t+1},a_{t})=\mathbb{P}[o_{t+1}|s_{t+1},a_{t}]$ is the
observation function, where $o_{t+1}\in\mathcal{O}$, $s_{t+1}\in\mathcal{S}$,
and $a_{t}\in\mathcal{A}$.

The belief state $b_{t}\in\mathcal{B}$ is defined as
$b_{t}(s)=\mathbb{P}[s_{t}=s|h_{t}]$ for all $s\in\mathcal{S}$. The belief
space $\mathcal{B}=\Delta(\mathcal{S})$ is the unit
$(|\mathcal{S}|-1)$-simplex [25, 26], where $\Delta(\mathcal{S})$ denotes the
set of probability distributions over $\mathcal{S}$. $b_{t}$ is a sufficient
statistic of the state $s_{t}$ based on the history $h_{t}$ of the initial
state distribution, the actions, and the observations:
$h_{t}=(\rho_{1},a_{1},o_{1},\ldots,a_{t-1},o_{t})\in\mathcal{H}$. By defining
the state at time $t$ to be the belief state $b_{t}$, a POMDP can be
formulated as a continuous-state MDP:
$\mathcal{M}=\langle\mathcal{B},\mathcal{A},\mathcal{P}^{a_{t}}_{b_{t},b_{t+1}},\mathcal{R}_{b_{t},b_{t+1}}^{a_{t}},\gamma,\rho_{1},T\rangle$.

The belief state can be computed recursively as follows [13]:

$\displaystyle b_{t+1}(s_{t+1})$
$\displaystyle=C\mathcal{Z}(o_{t+1},s_{t+1},a_{t})\sum_{s_{t}\in\mathcal{S}}\mathcal{P}^{a_{t}}_{s_{t}s_{t+1}}b_{t}(s_{t})$
(3)

where $C=1/\sum_{s_{t+1}\in S}\mathcal{Z}(o_{t+1},s_{t+1},a_{t})\sum_{s_{t}\in
S}\mathcal{P}_{s_{t},s_{t+1}}^{a_{t}}b_{t}(s_{t})$ is a normalizing factor
independent of $s_{t+1}$ to make $b_{t+1}$ sum to $1$.

###  III-B The Reinforcement Learning Problem

Reinforcement learning deals with the problem of choosing a sequence of
actions for a sequentially observed state variable to maximize a reward
function [14, 16]. This problem can be modeled with an MDP if the state space
is observable, or with a POMDP if the state space is not fully observable.

In the context of an MDP, a policy is defined as a function
$\pi:\\{1,\ldots,T\\}\times\mathcal{S}\rightarrow\Delta(\mathcal{A})$, where
$\Delta(\mathcal{A})$ denotes the set of probability distributions over
$\mathcal{A}$. In the case of a POMDP, a policy is defined as a function
$\pi:\mathcal{H}\rightarrow\Delta(\mathcal{A})$, or, alternatively, as a
function
$\pi:\\{1,\ldots,T\\}\times\mathcal{B}\rightarrow\Delta(\mathcal{A})$. In both
cases, a policy is called stationary if it is independent of the time-step
$t$.

An optimal policy $\pi^{*}$ is a policy that maximizes the expected discounted
cumulative reward over the time horizon $T$:

$\displaystyle\pi^{*}$
$\displaystyle\in\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{\pi}\left[\sum_{t=1}^{T}\gamma^{t-1}r_{t}\right]$
(4)

where $\Pi$ is the policy space, $\gamma$ is the discount factor, $r_{t}$ is
the reward at time $t$, and $\mathbb{E}_{\pi}$ denotes the expectation under
$\pi$.

It is well known that optimal deterministic policies exist for MDPs and POMDPs
with finite state and action spaces [23, 13]. Further, for stationary MDPs and
POMDPs with infinite or random time-horizons, optimal stationary policies
exist [23, 13].

The Bellman equations relate any optimal policy $\pi^{*}$ to the two value
functions $V^{*}:\mathcal{S}\rightarrow\mathbb{R}$ and
$Q^{*}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, where $\mathcal{S}$
and $\mathcal{A}$ are state and action spaces of an MDP [27]:

$\displaystyle V^{*}(s_{t})$
$\displaystyle=\displaystyle\max_{a_{t}\in\mathcal{A}}\mathbb{E}\big{[}r_{t+1}+\gamma
V^{*}(s_{t+1})|s_{t},a_{t}\big{]}$ (5) $\displaystyle Q^{*}(s_{t},a_{t})$
$\displaystyle=\mathbb{E}\big{[}r_{t+1}+\gamma
V^{*}(s_{t+1})|s_{t},a_{t}\big{]}$ (6) $\displaystyle\pi^{*}(s_{t})$
$\displaystyle\in\operatorname*{arg\,max}_{a_{t}\in\mathcal{A}}Q^{*}(s_{t},a_{t})$
(7)

Here, $V^{*}(s_{t})$ and $Q^{*}(s_{t},a_{t})$ denote the expected cumulative
discounted reward under $\pi^{*}$ for each state and state-action pair,
respectively. In the case of a POMDP, the Bellman equations contain $b_{t}$
instead of $s_{t}$. Solving the Bellman equations (Eqs. 5-6) means computing
the value functions from which an optimal policy can be obtained (Eq. 7).

Two principal methods are used for finding an optimal policy in a MDP or
POMDP: dynamic programming and reinforcement learning.

First, the dynamic programming method (e.g. value iteration [12, 23]) assumes
complete knowledge of the seven-tuple MDP or the nine-tuple POMDP and obtains
an optimal policy by solving the Bellman equations iteratively (Eq. 7), with
polynomial time-complexity per iteration for MDPs and PSPACE-complete time-
complexity for POMDPs [28].

Second, the reinforcement learning method computes or approximates an optimal
policy without requiring complete knowledge of the transition probabilities or
observation probabilities of the MDP or POMDP. Three classes of reinforcement
learning algorithms exist: value-based algorithms, which approximate solutions
to the Bellman equations (e.g. Q-learning [29]); policy-based algorithms,
which directly search through policy space using gradient-based methods (e.g.
Proximal Policy Optimization (PPO) [30]); and model-based algorithms, which
learn the transition or observation probabilities of the MDP or POMDP (e.g.
Dyna-Q [16]). The three algorithm types can also be combined, e.g. through
actor-critic algorithms, which are mixtures of value-based and policy-based
algorithms [16]. In contrast to dynamic programming algorithms, reinforcement
learning algorithms generally have no guarantees to converge to an optimal
policy except for the tabular case [31, 32].

###  III-C Markovian Optimal Stopping Problems

Optimal stopping is a classical problem in statistics with a developed theory
[33, 34, 35, 12, 23]. Example applications of this problem are: selling an
asset [12], detecting distribution changes [6], machine replacement [13],
valuing a financial option [17], and choosing a candidate for a job (the
secretary problem) [23].

Different versions of the problem can be found in the literature. Including,
discrete-time and continuous time, finite horizon and infinite horizon,
single-stop and multiple stops, fully observed and partially observed,
independent and dependent, and Markovian and non-Markovian. Consequently,
there are also different solution methods, most prominent being the martingale
approach [35] and the Markovian approach [34, 12, 23]. In this paper, we
consider a partially observed Markovian optimal stopping problem in discrete-
time with a finite horizon and a single stop action.

A Markovian optimal stopping problem can be seen as a specific kind of MDP or
POMDP where the state of the environment evolves as a discrete-time Markov
process $(s_{t})_{t=1}^{T}$ which is either fully or partially observed [23,
13]. At each time-step $t$ of this decision process, two actions are
available: “stop” and “continue”. The stop action causes the interaction with
the environment to stop and yields a stopping-reward. Conversely, the continue
action causes the environment to evolve to the next time-step and yields a
continuation-reward. The stopping time $\tau$ is a random variable dependent
on $s_{1},\ldots,s_{t}$ and independent of $s_{t+1},\ldots s_{T}$ [35].

The objective is to find a stopping policy $\pi(s_{t})\mapsto\\{S,C\\}$ that
maximizes the expected reward, where $\pi(s_{t})=S$ indicates a stopping
action. This induces the following maximization at each time-step before
stopping (the Bellman equation [27]):

$\displaystyle\max\Bigg{[}\underbrace{\mathbb{E}\left[\mathcal{R}^{S}_{ss^{\prime}}\right]}_{\text{stopping
reward}},\underbrace{\mathbb{E}\left[\mathcal{R}^{C}_{ss^{\prime}}+\gamma
V^{*}(s^{\prime})\right]}_{\text{continuation reward}}\Bigg{]}$ (8)

To solve the maximization above, standard solution methods for MDPs and POMDPs
can be applied, such as dynamic programming and reinforcement learning [12,
18]. Further, the solution can be characterized using dynamic programming
theory as the least excessive (or superharmonic) majorant of the reward
function, or using martingale theory as the Snell envelope of the reward
function [36, 35].

##  IV Formalizing The Intrusion Prevention Use Case and Our Reinforcement
Learning Approach

In this section, we first formalize the intrusion prevention use case
described in Section II and then we introduce our solution method.
Specifically, we first define a POMDP model of the intrusion prevention use
case. Then, we describe our reinforcement learning approach to approximate the
optimal defender policy. Lastly, we use the theory of dynamic programming to
derive the threshold property of the optimal policy.

###  IV-A A POMDP Model of the Intrusion Prevention Use Case

We model the intrusion prevention use case as a partially observed optimal
stopping problem where an intrusion starts at a geometrically distributed time
and the stopping action refers to blocking the gateway (Fig. 2). This type of
optimal stopping problem is often referred to as a quickest change detection
problem [35, 34, 6].

To formalize this model, we use a POMDP. This model includes the state space
and the observation space of the defender. It further includes the initial
state distribution, the defender actions, the transition probabilities, the
observation function, the reward function, and the optimization objective.

$\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}}}$Intrusion event
time-step $t=1$Intrusion ongoing $t$$t=T$Early stopping times Stopping times
that interrupt the intrusion Episode

Figure 2: Optimal stopping formulation of intrusion prevention; the horizontal
axis represents time; $T$ is the time horizon; the episode length is $T-1$;
the dashed line shows the intrusion start time; the optimal policy is to stop
at the time of intrusion.

####  IV-A1 States $\mathcal{S}$, Initial State Distribution $\rho_{1}$, and
Observations $\mathcal{O}$

The system state $s_{t}$ is defined by the intrusion state
$i_{t}\in\\{0,1\\}$, where $i_{t}=1$ if an intrusion is ongoing. Further, we
introduce a terminal state $\emptyset$, which is reached either when the
defender stops or when the attacker completes an intrusion. Thus,
$\mathcal{S}=\\{0,1\\}\cup\emptyset$.

At time $t=1$ no intrusion is in progress. Hence, the initial state
distribution is the degenerate distribution $\rho_{1}(s_{1}=0)=1$.

The defender has a partial view of the system state and does not know whether
an intrusion is in progress. Specifically, if the defender has not stopped, it
observes three counters $o_{t}=(\Delta x_{t},\Delta y_{t},\Delta z_{t})$. The
counters are upper bounded, where $\Delta x_{t}\in\\{0,,\ldots,X_{max}\\}$,
$\Delta y_{t}\in\\{0,\ldots,Y_{max}\\}$, $\Delta
z_{t}\in\\{0,\ldots,Z_{max}\\}$ denote the number of severe IDS alerts,
warning IDS alerts, and login attempts generated during time-step $t$,
respectively. Otherwise, if the defender has stopped, it observes
$o_{t}=s_{t}=\emptyset$. Consequently,
$\mathcal{O}=\\{0,\ldots,X_{max}\\}\times\\{0,\ldots,Y_{max}\\}\times\\{0,\ldots,Z_{max}\\}\cup\emptyset$.

####  IV-A2 Actions $\mathcal{A}$

The defender has two actions: “stop” ($S$) and “continue” ($C$). The action
space is thus $\mathcal{A}=\\{S,C\\}$.

####  IV-A3 Transition Probabilities $\mathcal{P}^{a}_{ss^{\prime}}$

We model the start of an intrusion by a Bernoulli process $(Q_{t})_{t=1}^{T}$,
where $Q_{t}\sim Ber(p=0.2)$ is a Bernoulli random variable. The time $t$ of
the first occurrence of $Q_{t}=1$ is the change point representing the start
time of the intrusion $I_{t}$, which thus is geometrically distributed, i.e.
$I_{t}\sim Ge(p=0.2)$ (Fig. 3). As the geometric distribution has the
memoryless property, the intrusion start time is Markovian.

We define the transition probabilities
$\mathcal{P}^{a_{t}}_{s_{t}s_{t+1}}=\mathbb{P}\left[s_{t+1}|s_{t},a_{t}\right]$
as follows:

$\displaystyle\mathbb{P}\left[\emptyset\middle|\cdot,S\right]=\mathbb{P}\left[\emptyset\middle|\emptyset,\cdot\right]=1$
(9) $\displaystyle\mathbb{P}\left[0\middle|0,C\right]=1-p$ (10)
$\displaystyle\mathbb{P}\left[1\middle|0,C\right]=p$ (11)
$\displaystyle\mathbb{P}\left[1\middle|1,C\right]=1$ (12)

All other transitions have probability $0$.

Eq. 9 defines the transition probabilities to the terminal state $\emptyset$.
The terminal state is reached when taking the stop action $S$. Eq. 10-12
define the transition probabilities when taking the continue action $C$. Eq.
10 captures the case where no intrusion occurs and where $i_{t+1}=i_{t}=0$;
Eq. 11 captures the start of an intrusion where $i_{t}=0,i_{t+1}=1$; and Eq.
12 describes the case where an intrusion is in progress and $i_{t+1}=i_{t}=1$.

####  IV-A4 Observation Function $\mathcal{Z}(o^{\prime},s^{\prime},a)$

We assume that the number of IDS alerts and login attempts generated during a
single time-step are random variables $X\sim f_{X}$, $Y\sim f_{Y}$, $Z\sim
f_{Z}$, dependent on the intrusion state and defined on the sample spaces
$\Omega_{X}=\\{0,1,\ldots,X_{max}\\}$, $\Omega_{Y}=\\{0,1,\ldots,Y_{max}\\}$,
and $\Omega_{Z}=\\{0,1,\ldots,Z_{max}\\}$. Consequently, the probability that
$\Delta x$ severe alerts, $\Delta y$ warning alerts, and $\Delta z$ login
attempts are generated during time-step $t$ is $f_{XYZ}(\Delta x,\Delta
y,\Delta z|i_{t})$.

We define the observation function
$\mathcal{Z}(o^{\prime},s^{\prime},a)=\mathbb{P}[o^{\prime}|s^{\prime},a]$ as
follows:

$\displaystyle\mathcal{Z}\big{(}(\Delta x,\Delta y,\Delta
z),i_{t},C\big{)}=f_{XYZ}(\Delta x,\Delta y,\Delta z|i_{t})$ (13)
$\displaystyle\mathcal{Z}\big{(}\emptyset,\emptyset,\cdot\big{)}=1$ (14)

Figure 3: Left: the reward function for the stop and continue actions; the
intrusion starts at $t=29$; right: the cumulative distribution function (CDF)
of the intrusion start time.

####  IV-A5 Reward Function $\mathcal{R}_{s}^{a}$

The reward function is parameterized by the reward that the defender receives
for stopping an intrusion ($R_{st}=100$), the loss of stopping before an
intrusion has started ($R_{es}=-100$), the reward for maintaining service
($R_{sla}=10$), and the loss of being intruded ($R_{int}=-100$), respectively.

We define the deterministic reward function
$\mathcal{R}^{a_{t}}_{s_{t}}=r(s_{t},a_{t})$ to be (Fig. 3):

$\displaystyle r\left(\emptyset,\cdot\right)=0$ (15) $\displaystyle
r\left(i_{t},S\right)=\mathbbm{1}_{i_{t}=0}R_{es}+\mathbbm{1}_{i_{t}=1}R_{st}$
(16) $\displaystyle
r\left(i_{t},C\right)=R_{sla}+\mathbbm{1}_{i_{t}=1}R_{int}$ (17)

Eq. 15 states that the reward in the terminal state is zero. Eq. 16 indicates
that stopping an intrusion incurs a reward but stopping before an intrusion
starts yields a loss, where $S$ is the stop action and $\mathbbm{1}$ is the
indicator function. Lastly, as can be seen from Eq. 17, the defender receives
a positive reward for maintaining service and a loss for taking the continue
action $C$ while under intrusion. This means that the maximal reward is
received if the defender stops when an intrusion starts.

####  IV-A6 Time Horizon $T_{\emptyset}$

The time horizon is defined by the time-step when the terminal state
$\emptyset$ is reached, which is a random variable $T_{\emptyset}$. Since we
know that the expectation of the intrusion time $I_{t}$ is finite, we conclude
that the horizon is finite for any policy $\pi_{\theta}$ that is guaranteed to
stop: $\mathbb{E}_{\pi_{\theta}}\left[T_{\emptyset}\right]<\infty$.

####  IV-A7 Policy Space $\Pi_{\theta}$, and Objective $J$

Since the POMDP is stationary and the time horizon $T_{\emptyset}$ is not pre-
determined, it is sufficient to consider stationary policies. Further,
although an optimal deterministic policy exists [23, 13], we consider
stochastic policies to allow smooth optimization. Specifically, we consider
the space of stationary stochastic policies $\Pi_{\theta}$ where
$\pi_{\theta}\in\Pi_{\theta}$ is a policy
$\pi:\mathcal{H}\rightarrow\Delta(\mathcal{A})$, which is parameterized by a
vector $\theta\in\mathbb{R}^{d}$.

The optimal policy $\pi^{*}_{\theta}\in\Pi_{\theta}$ maximizes the expected
cumulative reward over the random horizon $T_{\emptyset}$:

$\displaystyle
J(\theta)=\mathbb{E}_{\pi_{\theta}}\left[\sum_{t=1}^{T_{\emptyset}}\gamma^{t-1}r(s_{t},a_{t})\right],\text{
}\pi^{*}=\operatorname*{arg\,max}_{\pi_{\theta}\in\Pi_{\theta}}J(\theta)$ (18)

where we set the discount factor $\gamma=1$.

Eq. 18 defines the objective of the optimal stopping problem. In the following
section, we describe our approach for solving this problem using reinforcement
learning.

###  IV-B Our Reinforcement Learning Approach

Since the POMDP model is unknown to the defender, we use a model-free
reinforcement learning approach to approximate the optimal policy.
Specifically, we use the state-of-the-art reinforcement learning algorithm PPO
[30] to learn a policy $\pi_{\theta}:\mathcal{H}\mapsto\mathcal{A}$ that
maximizes the objective in Eq. 18.

Due to computational limitations (i.e. finite memory), we summarize the
history $h_{t}=(a_{1},o_{1},a_{2},o_{2},\ldots,a_{t-1},o_{t})$ by a vector
$\hat{h}_{t}=(x_{t},y_{t},z_{t},t)$, where $x_{t},y_{t},z_{t}$ are the
accumulated counters of the observations $o_{i}=(\Delta x_{i},\Delta
y_{i},\Delta z_{i})$ for $i=1,\ldots,t$: $x_{t}=\sum_{i=1}^{t}\Delta x_{i}$,
$y_{t}=\sum_{i=1}^{t}\Delta y_{i}$, $z_{t}=\sum_{i=1}^{t}\Delta z_{i}$.

PPO implements the policy gradient method and uses stochastic gradient ascent
with the following gradient [30]:

$\displaystyle\nabla_{\theta}J(\theta)$
$\displaystyle=\mathbb{E}_{\pi_{\theta}}\Bigg{[}\underbrace{\nabla_{\theta}\log\pi_{\theta}(a|\hat{h})}_{\text{actor}}\underbrace{A^{\pi_{\theta}}(\hat{h},a)}_{\text{critic}}\Bigg{]}$
(19)

where
$A^{\pi_{\theta}}(\hat{h}_{t},a_{t})=Q^{\pi_{\theta}}(\hat{h}_{t},a_{t})-V^{\pi_{\theta}}(\hat{h}_{t})$
is the so-called advantage function [37]. We implement $\pi_{\theta}$ with a
deep neural network that takes as input the summarized history $\hat{h}_{t}$
and produces as output a discrete conditional probability distribution
$\pi_{\theta}(a_{t}|\hat{h}_{t})$ that is computed with the softmax function.
The neural network structure of $\pi_{\theta}$ follows an actor-critic
architecture and computes a second output (the critic) that estimates the
value function $V_{\theta}^{\pi_{\theta}}(\hat{h}_{t})$, which in turn allows
to estimate $A^{\pi_{\theta}}(\hat{h}_{t},a_{t})$ in Eq. 19 using the
generalized advantage estimator $\hat{A}_{GAE}^{\pi_{\theta}}$ [37].

The hyperparameters of our implementation are given in Appendix -B and were
decided based on smaller search in parameter space.

The defender policy is learned through simulation of the POMDP. First, we
simulate a given number of episodes. We then use the episode outcomes and
trajectories to estimate the expectation of the gradient in Eq. 19. Then, we
use the estimated gradient and the PPO algorithm [30] with the Adam optimizer
[38] to update the policy. This process of simulating episodes and updating
the policy continues until the policy has sufficiently converged.

###  IV-C Threshold Property of the Optimal Policy

The policy that solves the optimal stopping problem is defined by the
optimization objective in Eq. 18. From the theory of dynamic programming, we
know that this policy satisfies the Bellman equation [22, 12, 13, 25]:

$\displaystyle\pi^{*}\big{(}b(1)\big{)}$
$\displaystyle=\operatorname*{arg\,max}_{a\in\mathcal{A}}\Bigg{[}r\big{(}b(1),a\big{)}+\sum_{o\in\mathcal{O}}\mathbb{P}[o|b(1),a]V^{*}\big{(}b_{o}^{a}(1)\big{)}\Bigg{]}$
(20)

where $b(1)=\mathbb{P}[s_{t}=1|h_{t}]$ is the belief that the system is in
state $1$ based on the observed history
$h_{t}=(a_{1},o_{1},\ldots,a_{t-1},o_{t})$. Consequently, $b(0)=1-b(1)$ (see
Section III-A for an overview of belief states). Moreover, $b^{a}_{o}(1)$ is
the belief state updated with the Bayes filter in Eq. 3 after taking action
$a$ and observing $o$. Further, $r\big{(}b(1),a\big{)}$ is the expected reward
of taking action $a$ in belief state $b(1)$, and $V^{*}$ is the value
function.

We use Eq. 20 to derive properties of the optimal policy. Specifically, we
establish the following structural result.

######  Theorem 1.

There exists an optimal policy $\pi^{*}$ which is a threshold policy of the
form:

$\displaystyle\pi^{*}\big{(}b(1)\big{)}=\begin{dcases}S\text{
(stop)}&\quad\text{if $b(1)\geq\alpha^{*}$}\\\ C\text{
(continue)}&\quad\text{otherwise}\end{dcases}$ (21)

where $\alpha^{*}$ is a threshold.

###### Proof.

See Appendix -A. ∎

Theorem 1 states that there exists an optimal policy which stops whenever the
posterior probability that an intrusion has started based on the history of
IDS alerts and login attempts exceeds a threshold level $\alpha^{*}$. This
implies that the optimal policy is completely determined by $\alpha^{*}$ given
that $b(1)$ is known. Since $b(1)$ is computed from the history of
observations, it also implies that the optimal defender policy can expressed
as a threshold function based on the observed infrastructure metrics.

##  V Emulating the Target Infrastructure to Instantiate the Simulation

To simulate episodes of the POMDP we must know the distributions of alerts and
login attempts. We estimate these distributions using measurements from an
emulation system. This procedure is detailed in this section.

###  V-A Emulating the Target Infrastructure

The emulation system executes on a cluster of machines that runs a
virtualization layer provided by Docker [39] containers and virtual
connections. The emulation is configured following the topology in Fig. 1 and
the configuration in Appendix -C. It emulates the clients, the attacker, and
the defender, as well as $31$ physical components of the target infrastructure
(e.g application servers and the gateway). Each physical entity is emulated
using a Docker container. The containers replicate important functions of the
target infrastructure, including web servers, databases, SSH servers, etc.

The emulation evolves in discrete time-steps of $30$ seconds. During each
time-step, the attacker and the defender can perform one action each.

####  V-A1 Emulating the Client Population

The client population is emulated by three client processes that interact with
the application servers through different functions at short intervals, see
Table 1.

Client | Functions | Application servers
---|---|---
$1$ | HTTP, SSH, SNMP, ICMP | $N_{2},N_{3},N_{10},N_{12}$
$2$ | IRC, PostgreSQL, SNMP | $N_{31},N_{13},N_{14},N_{15},N_{16}$
$3$ | FTP, DNS, Telnet | $N_{10},N_{22},N_{4}$

TABLE 1: Emulated client population; each client interacts with application
servers using a set of functions.

####  V-A2 Emulating the Attacker

The start time of an intrusion is controlled by a Bernoulli process as
explained in Section IV. We have implemented two types of attackers,
NoisyAttacker and StealthyAttacker, both of which execute the sequence of
actions listed in Table 2. The actions consist of reconnaissance commands and
exploits. During each time-step, one action is executed.

The two types of attackers differ in the reconnaissance command. NoisyAttacker
uses a TCP/UDP scan for reconnaissance while StealthyAttacker uses a ping-
scan. Since the ping-scan generates fewer IDS alerts than the TCP/UDP scan, it
makes the actions of StealthyAttacker harder to detect.

Time-steps $t$ | Actions
---|---
$1$–$I_{t}\sim Ge(0.2)$ | (Intrusion has not started)
$I_{t}+1$–$I_{t}+7$ |  Recon, brute-force attacks (SSH,Telnet,FTP)
| on $N_{2},N_{4},N_{10}$, login($N_{2},N_{4},N_{10}$),
| backdoor($N_{2},N_{4},N_{10}$), Recon
$I_{t}+8$–$I_{t}+11$ | CVE-2014-6271 on $N_{17}$, SSH brute-force attack on $N_{12}$,
| login ($N_{17},N_{12}$), backdoor($N_{17},N_{12}$)
$I_{t}+12$–$X+16$ | CVE-2010-0426 exploit on $N_{12}$, Recon
| SQL-Injection on $N_{18}$, login($N_{18}$), backdoor($N_{18}$)
$I_{t}+17$–$I_{t}+22$ |  Recon, CVE-2015-1427 on $N_{25}$, login($N_{25}$)
|  Recon, CVE-2017-7494 exploit on $N_{27}$, login($N_{27}$)

TABLE 2: Attacker actions to emulate an intrusion.

####  V-A3 Emulating Actions of the Defender

The defender takes an action every time-step. The continue action has no
effect on the emulation. The stop action changes the firewall configuration of
the gateway and drops all incoming traffic.

###  V-B Estimating the Distributions of Alerts and Login Attempts

In this section, we describe how we collect data from the emulation and how we
use the data to estimate the distributions of alerts and login attempts.

Metric | Command in the Emulation
---|---
Login attempts | cat /var/log/auth.log
IDS Alerts | cat /var/snort/alert.csv
TABLE 3: Commands used to measure the emulation.

Figure 4: Empirical distributions of IDS alerts (top row) and login attempts
on two servers (bottom row); the graphs include several distributions that are
superimposed.

Figure 5: Learning curves; the graphs show from left to right: episodic
reward, length of an episode, empirical detection probability, empirical early
stopping probability, and the number of steps between the start of an
intrusion and the stop action; the curves show the averages and the standard
deviations of three training runs with different random seeds.

####  V-B1 Measuring the Number of IDS alerts and Login Attempts in the
Emulation

At the end of every time-step, the emulation system collects the metrics
$\Delta x$, $\Delta y$, $\Delta z$, which contain the alerts and login
attempts that occurred during the time-step. The metrics are collected by
parsing the output of the commands in Table 3. For the evaluation reported in
this paper, we collected measurements from $11000$ time-steps.

####  V-B2 Estimating the Distributions of Alerts and Login Attempts of the
Target Infrastructure

Using the collected measurements, we compute the empirical distribution
$\hat{f}_{XYZ}$, which is our estimate of the corresponding distribution
$f_{XYZ}$ in the target infrastructure. For each $(I_{t},t)$ pair, we obtain
one empirical distribution.

Fig. 4 shows some of these distributions, which are superimposed. Although the
distribution patterns generated during an intrusion and during normal
operation overlap, there is a clear difference.

###  V-C Simulating Episodes of the POMDP

During a simulation of the POMDP, the system state evolves according the
dynamics described in Section IV and the observations evolve according to the
estimated distribution $\hat{f}_{XYZ}$. In the initial state, no intrusion
occurs. In every episode, either the defender stops before the intrusion
starts or exactly one intrusion occurs, the start of which is determined by a
Bernoulli process (see Section IV).

A simulated episode evolves as follows. During each time-step, if an intrusion
is ongoing, the attacker executes an action in the predefined sequence listed
in Table 2. Subsequently, the defender samples an action from the defender
policy $\pi_{\theta}$. If the action is stop, the episode ends. Otherwise, the
simulation samples the number of alerts and login attempts occurring during
this time-step from the empirical distribution $\hat{f}_{XYZ}$. It then
computes the reward of the defender using the reward function defined in
Section IV. The activities of the clients are not explicitly simulated but are
implicitly represented in $\hat{f}_{XYZ}$. The sequence of time-steps
continues until the defender stops or an intrusion completes, after which the
episode ends.

##  VI Learning Intrusion Prevention Policies using Simulation

To evaluate our reinforcement learning approach for finding defender policies,
we simulate episodes of the POMDP where the defender policy is updated and
evaluated. We evaluate the approach with respect to the convergence of
policies and compare the learned policies to two baselines and to an ideal
policy which presumes knowledge of the exact time of intrusion.

The evaluation is conducted using a Tesla P100 GPU and the hyperparameters for
the learning algorithm are listed in Appendix -B. Our implementation as well
as the measurements for the results reported in this paper are publicly
available [40].

###  VI-A Evaluation Setup

We train two defender policies against NoisyAttacker and StealthyAttacker
until convergence, which occurs after some $400$ iterations. In each
iteration, we simulate $4000$ time-steps and perform $10$ updates to the
policy. After each iteration, we evaluate the defender policy by simulating
$200$ evaluation episodes and compute various performance metrics.

We compare the learned policies with two baselines. The first baseline is a
policy that always stops at $t=6$, which corresponds to the immediate time-
step after the expected time of intrusion $\mathbb{E}[I_{t}]=5$ (see Section
IV). The policy of the second baseline always stops after the first IDS alert
occurs, i.e. $(x+y)\geq 1$.

To evaluate the stability of the learning curves’ convergence, we run each
training process three times with different random seeds. One training run
requires approximately six hours of processing time on a P100 GPU.

###  VI-B Analyzing the Results

The red curves in Fig. 5 show the performance of the learned policy against
NoisyAttacker, and the blue curves show the policy performance against
StealthyAttacker. The purple and the orange curves give the performance of the
two baseline policies. The dashed black curves give an upper bound on the
performance of the optimal policy $\pi^{*}$, which is computed assuming that
the defender knows the exact time of intrusion.

The five graphs in Fig. 5 show that the learned policies converge, and that
they are close to optimal in terms of achieving maximum reward, detecting
intrusion, avoid stopping when there is no intrusion, and stopping right after
an intrusion starts. Further, the learned policies outperform both baselines
by a large margin (leftmost graph in Fig. 5).

The performance of the learned policy against NoisyAttacker is better than
that against StealthyAttacker (leftmost graph in Fig. 5). This indicates that
NoisyAttacker is easier to detect for the defender. For instance, the learned
policy against StealthyAttacker has a higher probability of stopping early
(second rightmost graph of Fig. 5). This can also be seen in the second
leftmost graph of Fig. 5, which shows that, on average, the learned policy
against StealthyAttacker stops after $5$ time-steps and the learned policy
against NoisyAttacker stops after $6$ time-steps.

Looking at the baseline policies, we can see that the baseline $t=6$ stops too
early in $50$ percent of the episodes, and the $(x+y)\geq 1$ baseline stops
too early in $80$ percent of the episodes (second rightmost graph in Fig. 5).

##  VII Threshold Properties of the Learned Policies and Comparison with the
Optimal Policy

softthresholds neverstop severe alerts $x$warning alerts $y$warning alerts
$y$severe alerts $x$

Figure 6: Probability of the stop action by the learned policies in function
of the number of alerts $x,y$ and login attempts $z$.

When analyzing the learned policies, we find that they can be expressed
through thresholds, just like the optimal policy (Section IV-C). However, in
contrast to the optimal policy, the learned thresholds are based on the
observed counters of alerts and login attempts rather than the belief state
(which is unknown to the defender). Specifically, the top left graph in Fig. 6
shows that the learned policies against both attackers implement a soft
threshold by stopping with high probability if the number of alerts
($x_{t}+y_{t}$) exceeds $130$. This indicates that if the total number of
alerts is above $130$, an intrusion has started, i.e. $x_{t}+y_{t}$ is used to
approximate the posterior $b_{t}(1)$.

Moreover, the graphs in Fig. 6 also show the relative importance of severe
alerts $x_{t}$, warning alerts $y_{t}$, and login attempts $z_{t}$ for policy
decisions. Specifically, it can be seen that $x_{t}$ has the highest
importance, $y_{t}$ has a lower importance, and $z_{t}$ has the least
importance for policy decisions.

We also see that the learned policy against NoisyAttacker is associated with a
higher alert threshold than that of StealthyAttacker (top left graph in Fig.
6). This is consistent with our comment in Section V-A2 that StealthyAttacker
is harder to detect.

Lastly, Fig. 7 suggest that the thresholds of the learned policies are indeed
close to the threshold of the optimal policy. For instance, the policy learned
against NoisyAttacker stops immediately after the optimal stopping time.

optimal stopping earlystopping close to optimalstopping

Figure 7: Comparison of the learned policies $\pi_{\theta}$ and an upper bound
on the optimal policy $\pi^{*}$ for $4$ sample episodes where the intrusions
start at $i_{t}=2,4,6,8$.

##  VIII Related Work

The problem of automatically finding security policies has been studied using
concepts and methods from different fields, most notably reinforcement
learning, game theory, dynamic programming, control theory, attack graphs,
statistical tests, and evolutionary computation. For a literature review of
deep reinforcement learning in network security see [15], and for an overview
of game-theoretic approaches see [4]. For examples of research using dynamic
programming, control theory, attack graphs, statistical tests, and
evolutionary methods, see [8], [7], [9], [6], and [3].

Most research on reinforcement learning applied to network security is recent.
Prior work that most resembles the approach taken in this paper includes our
previous research [10] and the work in [11], [21], [20], [19], [41], and [42].
All of these papers focus on network intrusions using reinforcement learning.

This paper differs from prior work in the following ways: (1) we formulate
intrusion prevention as an optimal stopping problem ([19] uses a similar
approach); (2) we use an emulated infrastructure to estimate the parameters of
our simulation model, rather than relying on abstract assumptions like [10,
11, 20, 19, 41, 42]; (3) we derive a structural property of the optimal
policy; (4) we analyze the learned policies and relate them to the optimal
policy, an analysis which prior work lacks [10, 11, 20, 41, 42]; and (5) we
apply state-of-the-art reinforcement learning algorithms, i.e. PPO [30],
rather than traditional ones as used in [11, 20, 19, 21, 41, 42].

Optimal stopping has previously been applied to model problems in in different
domains, including finance [17], queuing systems [18], and attack detection
[6]. We believe we are first in using optimal stopping to model intrusion
prevention.

##  IX Conclusion and Future Work

In this paper, we proposed a novel formulation of the intrusion prevention
problem as one of optimal stopping. This allowed us to state that the optimal
defender policy can be expressed using a threshold obtained from
infrastructure measurements. Further, we used reinforcement learning to
estimate the optimal defender policies in a simulation environment. In
addition to validating the predictions from the theory, we learned from the
simulations a) the relative importance of measurement metrics with respect to
the threshold level and b) that different attacker profiles can lead to
different thresholds of the defender policies.

We plan to extend this work in three directions. First, the model of the
defender in this paper is simplistic as it allows only for a single stop
action. We plan to increase the set of actions that the defender can take to
better reflect today’s defense capabilities, while still keeping the structure
of the stopping formulation. Second, we plan to extend the observation
capabilities of the defender to obtain more realistic policies. Third, in the
current paper, the attacker policy is static. We plan to extend the model to
include a dynamic attacker that can learn just like the defender. This
requires a game-theoretic formulation of the problem.

##  X 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 useful input to this research,
and Forough Shahab Samani and Xiaoxuan Wang for their constructive comments to
an earlier draft of this paper.

###  -A Proof of Theorem 1

We will work our way to the proof of Theorem 1 by establishing some initial
results.

######  Lemma 1.

It is optimal to stop in belief state $b(1)$ iff:

$\displaystyle b(1)\geq$ (22)
$\displaystyle\frac{110+\displaystyle\sum_{o\in\mathcal{O}}V^{*}\big{(}b_{o}^{C}(1)\big{)}\Big{(}p\mathcal{Z}(o,1,C)+(1-p)\mathcal{Z}(o,0,C)\Big{)}}{300+\displaystyle\sum_{o\in\mathcal{O}}V^{*}\big{(}b_{o}^{C}(1)\big{)}\Big{(}p\mathcal{Z}(o,1,C)+(1-p)\mathcal{Z}(o,0,C)-\mathcal{Z}(o,1,C)\Big{)}}$

###### Proof.

Considering both actions of the defender ($\mathcal{A}=\\{S,C\\}$), we derive
from the Bellman equation (Eq. 20):

$\displaystyle\pi^{*}\big{(}b(1)\big{)}$ (23)
$\displaystyle=\operatorname*{arg\,max}_{a\in\mathcal{A}}\Bigg{[}r\big{(}b(1),a\big{)}+\sum_{o\in\mathcal{O}}\mathbb{P}[o|b(1),a]V^{*}\big{(}b_{o}^{a}(1)\big{)}\Bigg{]}$
$\displaystyle=\operatorname*{arg\,max}\Bigg{[}\underbrace{r\big{(}b(1),S\big{)}}_{a=S},\underbrace{r\big{(}b(1),C\big{)}+\sum_{o\in\mathcal{O}}\mathbb{P}[o|b(1),C]V^{*}\big{(}b_{o}^{C}(1)\big{)}}_{a=C}\Bigg{]}$
$\displaystyle=\operatorname*{arg\,max}\Bigg{[}\underbrace{b(1)200-100}_{\text{\normalsize$\omega$}},\underbrace{10-b(1)100+\sum_{o\in\mathcal{O}}\mathbb{P}[o|b(1),C]V^{*}\big{(}b_{o}^{C}(1)\big{)}}_{\text{\normalsize$\epsilon$}}\Bigg{]}$

In the above equation, $\omega$ is the expected reward for stopping and
$\epsilon$ is the expected cumulative reward for continuing. If
$\epsilon=\omega$, both actions of the defender, continuing and stopping,
maximize the expected cumulative reward. If $\omega\geq\epsilon$, it is
optimal for the defender to stop.

Next, we use
$\mathbb{P}[o|b(1),a]=\sum_{s\in\mathcal{S}}\sum_{s_{\prime}\in\mathcal{S}}b(s)\mathcal{P}^{a}_{ss^{\prime}}\mathcal{Z}(o,s^{\prime},a)$
and $\mathcal{S}=\\{0,1\\}$ to obtain:

$\displaystyle\pi^{*}\big{(}b(1)\big{)}$ (24)
$\displaystyle=\operatorname*{arg\,max}\Bigg{[}b(1)200-100,10-b(1)100+\sum_{o\in\mathcal{O}}\mathbb{P}[o|b(1),C]V^{*}\big{(}b_{o}^{C}(1)\big{)}\Bigg{]}$
$\displaystyle=\operatorname*{arg\,max}\Bigg{[}b(1)200-100,10-b(1)100+\sum_{o\in\mathcal{O}}V^{*}\big{(}b_{o}^{C}(1)\big{)}$
$\displaystyle\bigg{(}b(1)\mathcal{Z}(o,1,C)+(1-b(1)\big{)}\Big{(}p\mathcal{Z}(o,1,C)+(1-p)\mathcal{Z}(o,0,C)\Big{)}\bigg{)}\Bigg{]}$
$\displaystyle=\operatorname*{arg\,max}\Bigg{[}b(1)200-100,10+b(1)\bigg{(}-100+\sum_{o\in\mathcal{O}}V^{*}\big{(}b_{o}^{C}(1)\big{)}\Big{(}\mathcal{Z}(o,1,C)$
$\displaystyle-\big{(}p\mathcal{Z}(o,1,C)+(1-p)\mathcal{Z}(o,0,C)\big{)}\Big{)}\bigg{)}$
$\displaystyle+\sum_{o\in\mathcal{O}}V^{*}\big{(}b_{o}^{C}(1)\big{)}\bigg{(}p\mathcal{Z}(o,1,C)+(1-p)\mathcal{Z}(o,0,C)\bigg{)}\Bigg{]}$

This implies that it is optimal to stop in belief state $b(1)$ iff:

$\displaystyle b(1)200-100\geq
10+b(1)\bigg{(}-100+\sum_{o\in\mathcal{O}}V^{*}\big{(}b_{o}^{C}(1)\big{)}\Big{(}\mathcal{Z}(o,1,C)$
$\displaystyle-\big{(}p\mathcal{Z}(o,1,C)+(1-p)\mathcal{Z}(o,0,C)\big{)}\Big{)}\bigg{)}$
$\displaystyle+\sum_{o\in\mathcal{O}}V^{*}\big{(}b_{o}^{C}(1)\big{)}\bigg{(}p\mathcal{Z}(o,1,C)+(1-p)\mathcal{Z}(o,0,C)\bigg{)}$
(25)

By rearranging terms, we get:

$\displaystyle b(1)\geq$ (26)
$\displaystyle\underbrace{\frac{110+\displaystyle\sum_{o\in\mathcal{O}}V^{*}\big{(}b_{o}^{C}(1)\big{)}\Big{(}p\mathcal{Z}(o,1,C)+(1-p)\mathcal{Z}(o,0,C)\Big{)}}{300+\displaystyle\sum_{o\in\mathcal{O}}V^{*}\big{(}b_{o}^{C}(1)\big{)}\Big{(}p\mathcal{Z}(o,1,C)+(1-p)\mathcal{Z}(o,0,C)-\mathcal{Z}(o,1,C)\Big{)}}}_{\text{\normalsize$\alpha_{b(1)}$}}$

∎

Lemma 1 shows that the optimal policy is determined by the scalar thresholds
$\alpha_{b(1)}$. Specifically, it is optimal to stop in belief state $b(1)$ if
$b(1)\geq\alpha_{b(1)}$. We conclude that the stopping set $\mathscr{S}$—the
set of belief states $b(1)\in[0,1]$ where it is optimal to stop—is:

$\displaystyle\mathscr{S}=\left\\{b(1)\in[0,1]:b(1)\geq\alpha_{b(1)}\right\\}$
(27)

Similarly, the continuation set $\mathscr{C}$—the set of belief states where
it is optimal to continue—is $\mathscr{C}=[0,1]\setminus\mathscr{S}$.

Building on the above analysis, the main idea behind the proof of Theorem 1 is
to show that the stopping set $\mathscr{S}$ has the form
$\mathscr{S}=[\alpha^{*},1]$, where $0\leq\alpha^{*}\leq 1$ is the stopping
threshold. Towards this goal, we state the following two lemmas.

######  Lemma 2.

The following lemma is due to Sondik [43].

The optimal value function:

$\displaystyle
V^{*}(b_{t})=\max_{a_{t}\in\mathcal{A}}\mathbb{E}\left[r_{t+1}+V^{*}(b_{t+1})|b_{t},a_{t}\right]$
(28)

is piecewise linear and convex with respect to $b\in\mathcal{B}$.

###### Proof.

See [43] or [13, pp. 155, Theorem 7.4.1]. ∎

######  Lemma 3.

The stopping set $\mathscr{S}$ is a convex subset of the belief space
$\mathcal{B}$.

###### Proof.

A general proof is given in [13]. We restate it here to show that it holds in
our case.

To show that the stopping set $\mathscr{S}$ is convex, we need to show that
for any two belief states $b_{1},b_{2}\in\mathscr{S}$, any linear combination
of $b_{1},b_{2}$ is also in $\mathscr{S}$. That is,
$b_{1},b_{2}\in\mathscr{S}\implies\lambda
b_{1}+(1-\lambda)b_{2}\in\mathscr{S}$ for any $\lambda\in[0,1]$.

Since $V^{*}(b)$ is convex (Lemma 2), we have by definition of convex sets
that:

$\displaystyle V^{*}(\lambda b_{1}+(1-\lambda)b_{2})$
$\displaystyle\leq\lambda V^{*}(b_{1})+(1-\lambda)V(b_{2})$ (29)

Further, as $b_{1},b_{2}\in\mathscr{S}$ by assumption, the optimal action in
$b_{1}$ and $b_{2}$ is the stop action $S$. Thus, we have that
$V^{*}(b_{1})=Q^{*}(b_{1},S)=100b_{1}(1)-100b_{1}(0)$ and
$V^{*}(b_{2})=Q^{*}(b_{2},S)=100b_{2}(1)-100b_{2}(0)$. Hence:

$\displaystyle V^{*}\big{(}\lambda b_{1}(1)+(1-\lambda)b_{2}(1)\big{)}$ (30)
$\displaystyle\leq\lambda
V^{*}\big{(}b_{1}(1))+(1-\lambda)V^{*}(b_{2}(1)\big{)}$ (31)
$\displaystyle=\lambda Q^{*}(b_{1},S)+(1-\lambda)Q^{*}(b_{2},S)$ (32)
$\displaystyle=\lambda\big{(}100b_{1}(1)-b_{1}(0)100\big{)}+(1-\lambda)\big{(}100b_{2}(1)-b_{2}(0)100\big{)}$
(33) $\displaystyle=Q^{*}\big{(}\lambda b_{1}+(1-\lambda)b_{2},S\big{)}$ (34)
$\displaystyle\leq V^{*}\big{(}\lambda b_{1}(1)+(1-\lambda)b_{2}(1)\big{)}$
(35)

where the last inequality is because $V^{*}$ is optimal. Thus we have that
$Q^{*}\big{(}\lambda b_{1}+(1-\lambda)b_{2},S\big{)}=V^{*}\big{(}\lambda
b_{1}(1)+(1-\lambda)b_{2}(1)\big{)}$. This means that if
$b_{1},b_{2}\in\mathscr{S}$, then $\lambda
b_{1}+(1-\lambda)b_{2}\in\mathscr{S}$ for any $\lambda\in[0,1]$. Hence,
$\mathscr{S}$ is convex. ∎

Now we use Lemma 3 to prove Theorem 1.

###### Proof of Theorem 1.

The proof of Theorem 1 follows the same argument as the proof in [13,
Corollary 12.2.2, pp. 258].

The belief space $\mathcal{B}=[0,1]$ is defined by $b(1)\in[0,1]$. In
consequence, using Lemma 3, we have that the stopping set $\mathscr{S}$ is a
convex subset of $[0,1]$. That is, $\mathscr{S}$ has the form
$[\alpha^{*},\beta^{*}]$ where $0\leq\alpha^{*}\leq\beta^{*}\leq 1$. Thus, to
show that the optimal policy is of the form:

$\displaystyle\pi^{*}\big{(}b(1)\big{)}=\begin{dcases}S&\quad\text{if
$b(1)\geq\alpha^{*}$}\\\ C&\quad\text{otherwise}\end{dcases}$ (36)

it suffices to show that $\beta^{*}=1$, i.e.
$\mathscr{S}=[\alpha^{*},\beta^{*}]=[\alpha^{*},1]$.

If $b(1)=1$, then the Bellman equation states that:

$\displaystyle\pi^{*}(1)$
$\displaystyle=\operatorname*{arg\,max}_{a\in\mathcal{A}}\Bigg{[}r(1,a)+\sum_{o\in\mathcal{O}}\mathbb{P}[o|1,a]V^{*}\big{(}b_{o}^{a}(1)\big{)}\Bigg{]}$
(37)
$\displaystyle=\operatorname*{arg\,max}\Bigg{[}\underbrace{100}_{a=S},\underbrace{-90+\sum_{o\in\mathcal{O}}\mathcal{Z}(o,1,C)V^{*}\big{(}b_{o}^{C}(1)\big{)}}_{a=C}\Bigg{]}$
(38)

Since $s=1$ is an absorbing state until the terminal state is reached, we have
that $b_{o}^{C}(1)=1$ for all $o\in\mathcal{O}$. This follows from the
definition of $b_{o}^{C}$ (Eq. 3). Consequently, we get:

$\displaystyle\pi^{*}(1)$
$\displaystyle=\operatorname*{arg\,max}\Bigg{[}100,-90+\sum_{o\in\mathcal{O}}\mathcal{Z}(o,1,C)V^{*}\big{(}b_{o}^{C}(1)\big{)}\Bigg{]}$
(39) $\displaystyle=\operatorname*{arg\,max}\Bigg{[}100,-90+V^{*}(1)\Bigg{]}$
(40)

Finally, since $V^{*}(1)\leq 100$, we conclude that:

$\displaystyle\pi^{*}(1)$
$\displaystyle=\operatorname*{arg\,max}\Bigg{[}100,-90+V^{*}(1)\Bigg{]}=S$
(41)

This means that $\pi^{*}(1)=S$, hence $b(1)=1$ is in the stopping set, i.e.
$1\in\mathscr{S}$. As $1\in\mathscr{S}$, and since $\mathscr{S}$ is a convex
subset $[\alpha^{*},\beta^{*}]\subseteq[0,1]$, we have that $\beta^{*}=1$.
Then it follows that $\mathscr{S}=[\alpha^{*},\beta^{*}]=[\alpha^{*},1]$. ∎

##### An Example to Illustrate Theorem 1

To illustrate the implications of Theorem 1, consider the following example.

The observation $o_{t}$ is the number of IDS alerts that were generated during
time-step $t$, which is an integer scalar in the observation space
$\mathcal{O}=\\{0,\ldots,5\\}$. Further, assume that the observation function
$\mathcal{Z}(o^{\prime},s^{\prime},a)$ is defined using the discrete uniform
distribution $\mathcal{U}(\\{a,b\\})$ as follows.

$\displaystyle\mathcal{Z}(o^{\prime},0,C)$
$\displaystyle=\mathcal{U}(\\{0,4\\})$ no intrusion (42)
$\displaystyle\mathcal{Z}(o^{\prime},1,C)$
$\displaystyle=\mathcal{U}(\\{0,5\\})$ intrusion (43)
$\displaystyle\mathcal{Z}(\emptyset,\emptyset,\cdot)$ $\displaystyle=1$ (44)

The rest of the POMDP follows the definitions in Section IV.

Due to the small observation space, the optimal policy can be computed using
dynamic programming and value iteration. In particular, we apply Sondik’s
value iteration algorithm [43] to compute the optimal value function
$V^{*}\big{(}b(1)\big{)}$ as well as the optimal thresholds $\alpha_{b(1)}$
(Fig. 8).

$\alpha^{*}$$\mathscr{C}$$\mathscr{S}$

Figure 8: Left: optimal stopping thresholds $b(1)-\alpha_{b(1)}$, if
$b(1)-\alpha_{b(1)}\geq 0$ it is optimal to stop; right: the piecewise linear
and convex optimal value function $V^{*}(b(1))$.

As can be seen in Fig. 8, $b(1)-\alpha_{b(1)}$ is increasing in $b(1)$ and
there exists a unique minimum belief point $b(1)\approx 0.357$ such that
$b(1)\geq\alpha_{b(1)}$, which we denote by $\alpha^{*}$. Hence the stopping
set is the convex set $\mathscr{S}=[0.357,1]$, and the continuation set
$\mathscr{C}$ is the set $\mathscr{C}=[0,0.357)$.

###  -B Hyperparameters: Table 4

Parameters | Values
---|---
$\gamma$, lr $\alpha$, batch, # layers, # neurons, clip $\epsilon$ |  $1$, $5\cdot 10^{-4}$, $4\cdot 10^{3}$, $3$, $64$, $0.2$
$X_{max},Y_{max},Z_{max}$, GAE $\lambda$, ent-coef, activation |  $10^{3}$, $10^{3}$, $10^{3}$, $0.95$, $5\cdot 10^{-4}$, ReLU

TABLE 4: Hyperparameters of the learning algorithm.

###  -C Configuration of the Infrastructure in Fig. 1: Table 5

ID (s) | OS:Services:Exploitable Vulnerabilities
---|---
$1$ | Ubuntu20:Snort(community ruleset v2.9.17.1),SSH:-
$2$ | Ubuntu20:SSH,HTTP Erl-Pengine,DNS:SSH-pw
$4$ | Ubuntu20:HTTP Flask,Telnet,SSH:Telnet-pw
$10$ | Ubuntu20:FTP,MongoDB,SMTP,Tomcat,Teamspeak3,SSH:FTP-pw
$12$ | Jessie:Teamspeak3,Tomcat,SSH:CVE-2010-0426,SSH-pw
$17$ | Wheezy:Apache2,SNMP,SSH:CVE-2014-6271
$18$ | Deb9.2:IRC,Apache2,SSH:SQL Injection
$22$ | Jessie:PROFTPD,SSH,Apache2,SNMP:CVE-2015-3306
$23$ | Jessie:Apache2,SMTP,SSH:CVE-2016-10033
$24$ | Jessie:SSH:CVE-2015-5602,SSH-pw
$25$ | Jessie: Elasticsearch,Apache2,SSH,SNMP:CVE-2015-1427
$27$ | Jessie:Samba,NTP,SSH:CVE-2017-7494
$3$,$11$,$5$-$9$ | Ubuntu20:SSH,SNMP,PostgreSQL,NTP:-
$13$-$16$,$19$-$21$,$26$,$28$-$31$ | Ubuntu20:NTP, IRC, SNMP, SSH, PostgreSQL:-

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

## 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] 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.
  * [3] 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.
  * [4] T. Alpcan and T. Basar, _Network Security: A Decision and Game-Theoretic Approach_ , 1st ed. USA: Cambridge University Press, 2010.
  * [5] 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.
  * [6] A. G. Tartakovsky, B. L. Rozovskii, R. B. Blažek, and H. Kim, “Detection of intrusions in information systems by sequential change-point methods,” _Statistical Methodology_ , vol. 3, no. 3, 2006.
  * [7] W. Liu and S. Zhong, “Web malware spread modelling and optimal control strategies,” _Scientific Reports_ , vol. 7, p. 42308, 02 2017.
  * [8] M. Rasouli, E. Miehling, and D. Teneketzis, “A supervisory control approach to dynamic cyber-security,” in _Decision and Game Theory for Security_. Cham: Springer International Publishing, 2014, pp. 99–117.
  * [9] 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.
  * [10] K. Hammar and R. Stadler, “Finding effective security strategies through reinforcement learning and Self-Play,” in _International Conference on Network and Service Management (CNSM 2020)_ , Izmir, Turkey, 2020.
  * [11] 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.
  * [12] D. P. Bertsekas, _Dynamic Programming and Optimal Control_ , 3rd ed. Belmont, MA, USA: Athena Scientific, 2005, vol. I.
  * [13] V. Krishnamurthy, _Partially Observed Markov Decision Processes: From Filtering to Controlled Sensing_. Cambridge University Press, 2016.
  * [14] D. P. Bertsekas and J. N. Tsitsiklis, _Neuro-dynamic programming._ Belmont, MA: Athena Scientific, 1996.
  * [15] T. T. Nguyen and V. J. Reddi, “Deep reinforcement learning for cyber security,” _CoRR_ , vol. abs/1906.05799, 2019.
  * [16] R. S. Sutton and A. G. Barto, _Introduction to Reinforcement Learning_ , 1st ed. Cambridge, MA, USA: MIT Press, 1998\.
  * [17] J. du Toit and G. Peskir, “Selling a stock at the ultimate maximum,” _The Annals of Applied Probability_ , vol. 19, no. 3, Jun 2009.
  * [18] A. Roy, V. S. Borkar, A. Karandikar, and P. Chaporkar, “Online reinforcement learning of optimal threshold policies for markov decision processes,” _CoRR_ , vol. abs/1912.10325, 2019.
  * [19] 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.
  * [20] F. M. Zennaro and L. Erdodi, “Modeling penetration testing with reinforcement learning using capture-the-flag challenges and tabular q-learning,” _CoRR_ , vol. abs/2005.12632, 2020.
  * [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, pp. 235–243, Jun. 2020.
  * [22] R. Bellman, “A markovian decision process,” _Journal of Mathematics and Mechanics_ , vol. 6, no. 5, pp. 679–684, 1957.
  * [23] M. L. Puterman, _Markov Decision Processes: Discrete Stochastic Dynamic Programming_ , 1st ed. USA: John Wiley and Sons, Inc., 1994.
  * [24] R. A. Howard, _Dynamic Programming and Markov Processes_. Cambridge, MA: MIT Press, 1960.
  * [25] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra, “Planning and acting in partially observable stochastic domains,” USA, 1996.
  * [26] K. Åström, “Optimal control of markov processes with incomplete state information,” _Journal of Mathematical Analysis and Applications_ , vol. 10, no. 1, pp. 174–205, 1965.
  * [27] R. Bellman, _Dynamic Programming_. Dover Publications, 1957.
  * [28] C. H. Papadimitriou and J. N. Tsitsiklis, “The complexity of markov decision processes,” _Math. Oper. Res._ , vol. 12, p. 441–450, Aug. 1987.
  * [29] C. Watkins, “Learning from delayed rewards,” Ph.D. dissertation, 1989.
  * [30] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _CoRR_ , 2017.
  * [31] T. Jaakkola, M. Jordan, and S. Singh, “Convergence of stochastic iterative dynamic programming algorithms,” in _Advances in Neural Information Processing Systems_ , vol. 6, 1994.
  * [32] H. Robbins and S. Monro, “A Stochastic Approximation Method,” _The Annals of Mathematical Statistics_ , vol. 22, no. 3, pp. 400 – 407, 1951.
  * [33] A. Wald, _Sequential Analysis_. Wiley and Sons, New York, 1947.
  * [34] A. N. Shirayev, _Optimal Stopping Rules_. Springer-Verlag Berlin, 2007, reprint of russian edition from 1969\.
  * [35] G. Peskir and A. Shiryaev, _Optimal stopping and free-boundary problems_ , ser. Lectures in mathematics (ETH Zürich). Springer, 2006.
  * [36] J. L. Snell, “Applications of martingale system theorems,” _Transactions of the American Mathematical Society_ , vol. 73, no. 2, 1952.
  * [37] J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel, “High-dimensional continuous control using generalized advantage estimation,” in _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2016.
  * [38] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” 2014, international Conference for Learning Representations, San Diego.
  * [39] D. Merkel, “Docker: lightweight linux containers for consistent development and deployment,” _Linux journal_ , vol. 2014, no. 239, p. 2, 2014.
  * [40] K. Hammar and R. Stadler, “gym-optimal-intrusion-response,” 2021, https://github.com/Limmen/gym-optimal-intrusion-response.
  * [41] W. Blum, “Gamifying machine learning for stronger security and ai models,” 2019\.
  * [42] A. Ridley, “Machine learning for autonomous cyber defense,” 2018, the Next Wave, Vol 22, No.1 2018.
  * [43] E. J. Sondik, “The optimal control of partially observable markov processes over the infinite horizon: Discounted costs,” _Operations Research_ , vol. 26, no. 2, pp. 282–304, 1978.