The Price of Pessimism for Automated Defense ^††thanks: Funded by the Auerbach Berger Chair in Cybersecurity held by Spiros Mancoridis, at Drexel University

This work evaluates the “price of pessimism”, a phenomenon wherein the a priori assumption about an adversary’s knowledge of a system results in a suboptimal response pattern. In particular, this manuscript contributes the following:

1. 1.

   For reinforcement learning agents in a stochastic Bayesian game, optimizing against a worst-case adversary leads to suboptimal policy convergence.

2. 2.

   Defending agents trained against attacking agents that learn are also highly capable against algorithmic attackers even when they have not seen those algorithmic attackers during training.

3. 3.

   An extension of the YAWNING-TITAN [5] reinforcement learning framework for training independent attacking and defending agents

4. 4.

   A novel use of the Bayes-Hurwicz criterion for parameterizing attacker decision making under uncertainty

The state space $S$ of this game consists of a network graph $G=(V,E)$, where each $v\in V$ is a defender-owned computer and each edge $e\in E$ is a tuple indicating a network connection between two nodes $(u,v);u,v\in V$. The state of each machine $v\in V$ is a tuple $(v_{p},v_{\alpha},v_{\delta})$.

• •

  $v_{p}\in[0,1]$ is the “vulnerability” of a node: the probability that a basic attack will be successful

• •

  $v_{\alpha}=\{0,1\}$ is the “true” state of compromise and is visible only to the attacker

• •

  $v_{\delta}=\{0,1\}$ is the defender-visible state of compromise

At each time step, with probability $q$, an “alert” is generated independent of attacker or defender action that sets $v_{\delta}=1$ even if the true compromise state $v_{\alpha}=0$, corresponding to a false positive alert. This phenomenon is justified and described in further depth in Section 3.4.

The attacker’s action space, $A_{\alpha}$ consists of actions on elements of $V$ subject to visibility constraints. We define a “compromised” node as a node that the attacker has gained access to and thus has $v_{\alpha}=1$. An “accessible” node is any node with some edge connecting it to any compromised node. The observable state space of an attacker, $S_{\alpha}$ consists of all compromised nodes and all accessible nodes. The attacker’s action space consists of the following actions, which each incur some cost $c$:

• •

  Basic Attack: Compromise an accessible $v\in V$ with probability $v_{p}$.

• •

  Zero-day Attack: Compromise an accessible $v\in V$ as if $v_{p}=1$.

• •

  Move: Move from some compromised $v\in V$ to another compromised $v^{\prime}\in V$

• •

  Do Nothing: Take no action

• •

  Execute: End the game and realize rewards for all compromised $v\in V$

Attacker types inform what exactly their objectives are and may influence the categories of malware used e.g., coin miner, ransomware, backdoor. Moreover, the attacker’s type informs the utility function of the attacker and the cost of each action. For some attacker types, e.g., cybercriminals using ransomware, there is a clear utility: the ransom paid by the victim. However, other attacker types may aim to steal private information that is not be directly convertible to currency. The estimation of these utility functions is thus type-specific, though any compromised machine will confer nonzero utility to the attacker.

For our purposes, we assume that the attacker is a ransomware attacker and aims to compromise as many machines as possible and end the game before the defender can remove them from the system. Assuming unit reward for each node, this means that for a network of size $n$, the attacker’s reward at any time if they take the Execute action or control an attacker-defined percentage of the network is:

Where $T$ is the final timestep of the game and $c_{t}$ is the cost of the action taken at time $t$. We note that our reward function in Section 5 uses a scaling factor for the value of $v_{i\alpha}$ in lieu of unit value, and that this function also holds in cases where each node has a different value.

The defender’s action space, $A_{\delta}$ consists of actions on $V$ and $E$. Although the defender can take only one action at each time step, they may take that action on a set of nodes or edges. The defender’s observable space, $S_{\delta}$ consists of the entirety of $E$ and the number of alerts, $v_{delta}$, for all $v\in V$ at all times. Specifically, the defender may:

• •

  Reduce Vulnerability: For some $v\in V$, slightly decrease the probability that a basic attack will be successful

• •

  Make Node Safe: For some $v\in V$, reduce the probability that a basic attack will be successful to 0.01

• •

  Restore Node: For some $v\in V$, reset the node to its initial, uncompromised state, including the probability that a basic attack will be successful

• •

  Scan: With some probability, detect the true compromised status of each $v\in V$

• •

  Do Nothing: Take no action

The objective of cybersecurity, broadly, is to maintain the confidentiality, availability, and integrity [4] of a system. The defender’s utility thus arises from the availability of resources. Each action has some cost $c$ associated with it, where the impact of the action being taken on the availability of that resource on the system dictates $c$. For example, the Reduce Vulnerability and Make Node Safe actions are very similar, but the Reduce Vulnerability action incurs a much smaller cost under default YAWNING-TITAN settings. The defender’s utility $u_{\delta}$ is a fixed-value reward for eliminating the adversary or withstanding the attack minus the sum of all costs associated with the actions taken during the course of the game.

Security detections are not infallible, and some number of both false positives – detections that alert on benign behavior, and false negatives – failures to detect malicious behavior, must be expected. Attackers are incentivized to and have adopted techniques like using cloud infrastructure and software as a service (SaaS) providers to conduct attacks [15] and the use of legitimate executables or “lolbins” for malicious purposes  [19]. Attackers seek to blend in, so detection of malicious behavior that is similar to benign behavior is important for defenders. Since there is no way to definitively determine whether or not a program is malicious, these rules and algorithms yield some number of false positive alerts. The empirical rate of these false positive alerts, according to surveys, appears to be somewhere between 20% [27] and 32% [18]. In cases where some number of alerts are not an indicator of actual attack activity, any probabilistic approach to network security must grapple with this noise. The security game setting has modeled this sort of behavior in the realm of deception and counter-deception. Work by Nguyen and Yadav [23] shows that while attacker payoffs are improved by deception, learning defenders can reduce the value of this deception.

Assuming that an attacker’s behavior is detected with some probability $p$, then there is an independent probability of false positives $q$. Letting $p$ and $q$ characterize two independent Bernoulli processes that may each yield an alert, we can treat the emission of an alert as the joint probability of these two processes. The probability of an alert occurring at all is thus $p+q-pq$, as described in earlier work by the authors [14]. The expected probability that a particular alert is attributable to benign activity is $(1-p)q$. For simplicity, we assume that $p$ and $q$ are the same across all nodes.

In the absence of the noise assumption, attacker-defender interaction becomes a game of Cops and Robbers on a graph [29] where a defender can eliminate the attacker by finding the “cop number” – the number of nodes required to “surround” the attacker and eliminate all of their access at once – for the subgraph the attacker has explored. This is still an extremely challenging problem, since even without noise, the defender only has a belief about the extremal edges of that subgraph and finding the attacker’s possible subgraphs has exponential complexity. As a result, the importance of an assumption about noise relates with assumptions about under what circumstances a defender realizes a reward.

In non-cooperative game theory, two players are playing a game and each seeks to optimize against some utility function. This comes, of course, with the implicit assumption that both players know they are playing a game. In cybersecurity games, when modeling the beliefs of the defender, we frequently imply that the defender knows an attacker is present a priori. In reality, attackers are not always present in our system, and this has a substantial impact on defender expectations. Clearly, any response taken when an attacker is not present incurs a cost and yields no reward.

Let $\mu\in[0,1]$ be the probability that an attacker is present in a system. If our game has alert probability $p$ and no noise – that is, $q=0$ – then although we know the probability of an alert is $\mu p$, the occurrence of an alert allows us to set $\mu=1$ and the defender can directly pursue the attacker as described in Section 3.4. Assuming noise is present in the system, the probability of an alert occurring at any time step is then

In this setting, since an attacker may not be present, the probability of a false positive event occurring at any time step is

In real-world settings, attackers are unaware of parameters like $p$ and $q$, so they cannot ex ante optimize their actions and must instead seek to achieve their goal by balancing the risk of being caught with the need to achieve their goal. Thus, the “optimistic”, from the defender’s perspective, zero knowledge setting is the most consequential for generating real security impacts. In the zero knowledge setting, the defender is still armed with full knowledge and chooses some threshold for $\mu$ to take an action. However, the attacker does not know any of the parameters of the network and must balance exploration and exploitation given only the state, as each action they take may alert the defender of their presence. Given their limited information, they can use the Restricted Bayes/Hurwicz criterion [11] to choose their action.

The attacker has some initial probability distribution $\hat{P}$ over their actions indicating the probability they will take an action at a given time step given a state. The coefficient of pessimism $\delta$ corresponds to the attacker’s belief about the value of $\mu$, which we write $\hat{\mu}$. Due to the limited signal available to the attacker, the confidence parameter $\gamma$ should be monotonically decreasing over time as they observe likely defender actions. For notational simplicity, we set $\delta=1-\hat{\mu}$ and write the criterion as follows:

At the start of the game, the attacker must estimate the probability of an alert occurring when they take an action. The attacker knows that false positive alerts occur and can infer that they need to establish some value that reflects Equation 1. In the absence of any information about the defender’s configuration, the attacker must sample some value $\hat{\phi}\in[0,1]$. The use of the PERT distribution [9], a special case of the Beta distribution, is well-motivated from operations research. We allow the minimum and maximum value in the range $[0,1]$ and set the $b$ parameter of the distribution to the midpoint $0.5$. The initial value of $\hat{\mu}$ can be similarly sampled.

When the attacker observes a signal from a defender – that is, when the defender takes some action on an attacker-controlled node, the attacker updates their belief about $\hat{\mu}$, and reduces $\gamma$, since they are less confident in their initial distribution over their actions. This update process follows Algorithm 1. In order to conduct this update, the attacker estimated alert generation probability $\hat{\phi}$ is used alongside their estimate of the defender’s belief about an attacker’s presence, $\hat{\mu}$ since the attacker has no knowledge of the number of alerts and must instead construct a Bayesian estimate $\hat{Al}$ given these parameters.

In the full-knowledge case with thresholding, the best response dynamics are determined exactly by expectation and the parameters of the network [14]. However, this work considers a significantly expanded state space where both attackers and defenders have a richer action space. In both the full-knowledge and zero-knowledge case, the attacker’s choice of action depends on the state and any actions observed from the defender. The zero-knowledge case in particular is highly dependent on the establishment of good prior distributions. Prior distributions can be given exogenously or can be learned. In our case, we elect to learn $\hat{P},\bar{P},\text{\@text@baccent{$P$}}$ via simulation. The results of this simulation are described in Section 5.1.

The attacker must consider three distributions when playing the game: $\hat{P},\bar{P},\text{\@text@baccent{$P$}}$. For the “best case” distribution $\bar{P}$, we train an attacking agent against a defender whose only action is to do nothing. For the “worst case” distribution $̱P$, we train an attacking agent against a defender who has access to both attacker and defender observation spaces and thus has full-knowledge of the attacker’s moves and the network. The remainder of this subsection describes the training of the model $\hat{P}$ is drawn from.

Our setting assumes an adversary who uses ransomware, where the attacking player “wins” when they control more than 80% of the network. For each training episode, we instantiate a random entrypoint for the attacker on a 50-node network whose edges are randomly generated to ensure the network has 60% connectivity, and that there are no unconnected nodes. We leverage proximal policy optimization (PPO) [26] for our learning agents in two settings:

1. 1.

   Optimistic (zero-knowledge): The attacking agent can see only the nodes they control and adjacent nodes. They cannot see the vulnerability status of any nodes.

2. 2.

   Pessimistic (full-knowledge): the attacking agent has access to the same information and observation space as the defending agent.

In accordance with our modeling assumptions, the attacking and defending player simultaneously decide their moves for timestep $t$ from their action space. Each agent is trained in either the optimistic or pessimistic environment for 3000 episodes and evaluated for 500 episodes across randomly generated environments in both the optimistic and pessimistic setting. Based on empirical results from experiments in the environment, the actor learning rate is set to 0.0002 and the critic learning rate is set to 0.0005. Higher learning rates were tried and led to fast convergence to suboptimal policies, as PPO assumes full observability to achieve globally optimal policies and our environment is only partially observable. Values for all hyperparameters and action costs for both players were fixed across all settings and are included in Tables 2 and 2.

Evaluating reinforcement learning findings is notoriously difficult. Therefore, in line with Agarwal et al. [1], we look to more robust measurements that capture the uncertainty in results. Specifically, in addition to standard evaluation metrics, we consider also score distributions and the interquartile mean across evaluation runs. These metrics help capture the stochasticity in the task and normalize our results. Smoothed training curves in the optimistic setting are shown in Figure 2; the pessimistic setting is shown in Figure 2. The average rewards and interquartile mean for evaluation of the defending agents trained in the optimistic and pessimistic settings achieved each of the two evaluation settings are shown in Figure 3 and Figure 4. Score distributions are captured in Figure 5.

We observe in Figures 2 and 2 that the attacker generally starts out with a poor reward, but learns how to attack the target within 500 epochs. In the optimistic setting, the defender initially starts out with a very high level of reward but once the attacker begins winning more often, they must adapt their strategy, with rewards for both agents converging around epoch 3000. In the pessimistic setting, the defender similarly starts with a reasonably high reward, but the attacker quickly learns how to overcome the defender’s strategy. In this setting, the defender does not rebound and instead settles into a local optimum – minimizing the magnitude of loss rather than continuing to explore for a strategy that eliminates the attacker. Longer runs – up to 10000 training epochs – were attempted, but the pessimistic defender’s policy in those cases achieved even worse evaluation results than the defender trained for 3000 epochs. Note that the reward scale for attackers and defenders is not the same and defenders cannot achieve the extreme rewards that attackers do.

What we find from our evaluation is that the defending agent trained in the pessimistic setting performs worse on average than the defending agent trained in the optimistic setting. Across both evaluation settings, the optimistic defender is more robust in general and performs significantly better on average across all settings, as we can observe from Figures 3 and 4. Note that a negative score implies that the attacker is winning more often than the defender, while a positive score implies that the defender is winning more often. Each defender performs relatively better in the setting they were trained in and experiences less variance, as we can see the relative stability between the mean and interquartile mean for in-domain settings. Interestingly, both optimistic and pessimistic defenders perform well against the NSARed attacker, suggesting that training against learning agents offers substantial benefit over training against more “static” algorithmic attackers.

The score distributions in Figure 5 demonstrate the impact of the pessimistic defender’s convergence. While the optimistic defender has a fairly broad, relatively normal distribution in both settings, the pessimistic defender’s probability density is highly concentrated just below zero in domain and widely distributed across highly negative and highly positive out of distribution. This underscores the robustness of the optimistic defender and indicates that in training, the pessimistic defender converges to a policy that expects to achieve a negative reward and seeks to minimize that negative reward, rather than a policy that expects a positive reward and seeks to maximize it. Since the defender’s win condition depends on eliminating the attacker or surviving 500 episodes, this “loss minimization” policy leads to suboptimal performance against learning attackers.

To explain the difference in outcomes and what is learned in training, we can examine the differences in actions taken by the optimistic and pessimistic defenders. We find that the pessimistic defender agent uses the more expensive “restore node” action at a higher frequency than the optimistic agent, while the optimistic agent spends more turns on reducing the vulnerability of nodes and making nodes safe. This is likely an artifact of the attacker in the pessimistic setting having access to significantly more information, requiring a more aggressive response to forestall an attacker win. The distribution of action usage for both agents across all evaluations is shown in Table 3.

In the interest of ensuring our action costs do not have an undue influence on our results, we perform our same reinforcement learning evaluation for our pessimistic setting. We vary two parameters – “connectivity” and “security” – over the range $(0,1]$, with a floor of 0.000001 to avoid division by zero. To establish the robustness of the model, we multiply the cost of each action by the ratio of connectivity and security such that the importance of security is nearly zero, the cost of actions becomes very high and when the value of connectivity is nearly zero, the cost of actions approaches zero, given fixed security value. We find that there is a nearly linear pattern relating the cost of actions to rewards, but the learned policy remains stable, provided the relative costs of actions is fixed and is not degenerate even near extremal values.

As mentioned in Section 4.1, attackers in the real world do not have the luxury of training their priors to convergence against a target and must combine their prior knowledge with what is observed during an attack. Since the attacker is making decisions under uncertainty, some criterion must be used to allow them to do that subject to their own parameters. Using the pretrained, frozen models from Section 5.1, we consider how the application of the Restricted Bayes/Hurwicz criterion for the attacker as defined in Equation 3 impacts the outcomes of the attacking player. Aside from the use of the Restricted Bayes/Hurwicz criterion for the attackers, all of the defender and environmental evaluation settings remain the same.

The attacking agent draws independent prior $\hat{\mu}$ and $\hat{\phi}$ values from PERT distributions in accordance with Algorithm 1 at the start of each round and updates their $\hat{\mu}$ at each timestep if defender activity is observed – that is, if the defender takes an action that removes access to an attacker controlled node. For each evaluation scenario, the relevant trained attacker model – zero knowledge or full knowledge – is used to establish $\hat{P}$, $\bar{P}$, and $̱P$ for the observed state of the game. Specifically, each policy model $\hat{\pi},\bar{\pi},\text{\@text@baccent{$\pi$}}$ accepts an attacker-observed state $S_{t}$ and outputs a distribution over the attacker’s action space $A_{\alpha}$ such that $\hat{\pi}(S_{t})\sim\hat{P}$, $\bar{\pi}(S_{t})\sim\bar{P}$, and $\text{\@text@baccent{$\pi$}}(S_{t})\sim\text{\@text@baccent{$P$}}$. The attacker leverages these model outputs and the values of $\hat{\mu}$, and $\gamma$ with Equation 3 to determine their next best action.

Interquartile mean evaluation rewards for the attacker, shown in Figure 6, illustrate the impact of restricted Bayes/Hurwicz. Against the optimistic defender, the use of restricted Bayes/Hurwicz yields marginally worse performance for the zero-knowledge (in-domain) attacker, but marginally better performance for the full-knowledge (out-of-domain) attacker. Against the pessimistic defender, the pure zero-knowledge attacker performs incredibly well, and using Bayes/Hurwicz somewhat negatively impacts the attacker’s interquartile mean reward. While the full-knowledge (in-domain) attacker performs worse overall against the pessimistic defender, the pure strategy is better than using Bayes-Hurwicz, as we would expect.

Results for defenders against both base attackers and those using restricted Bayes/Hurwicz are shown in Figure 7, and reflect the information from Figure 4. The optimistic defender experiences a marginal improvement against the restricted Bayes/Hurwicz attackers in both the zero knowledge and full knowledge case. Meanwhile, the pessimistic defender performs slightly better against the restricted Bayes/Hurwicz attacker in the full knowledge (in-domain) case, but significantly worse against the restricted Bayes/Hurwicz attacker in the zero knowledge (out-of-domain) case.