Exposing Surveillance Detection Routes via Reinforcement Learning, Attack Graphs, and Cyber Terrain

Reinforcement learning (RL) problems involve an agent, interacting with an environment, and transiting from one state to another until it reaches the goal state [5]. The agent receives rewards for taking actions with the overall goal to achieve maximum cumulative rewards. Environments are normally modeled as MDPs, which can be defined by a tuple $\{S,A,R,P,\gamma\}$ where S denotes the set of possible states and A denotes the set of possible actions, R represents the distribution of reward given any state-action pair, P represents transition probability and $\gamma$ is discount factor. The goal of the agent is to learn an optimal policy $\pi$ that maps states to actions. As so, the RL algorithm is to learn an optimal policy to select actions and maximize the expected cumulative discounted reward:

In (deep) Q-learning, the optimal policy can be defined by two terms, the value function and Q-value function. The value function shows how good the state is and it is defined as the expected cumulative reward from following the policy from the state

The Q-value function, on the other side, is defined as the expected cumulative reward given both parts of the state-action pair

It satisfies the Bellman equation

Thus, the optimal policy $\pi^{*}$ corresponds to taking the best action in any state as specified by $Q^{*}$.

For a more complex problem where the state or action space is large enough so that computing every state-action pair is infeasible, neural networks become a powerful function estimator in deep Q-learning (DQL) [6, 7]. The optimal Q-values are estimated by a neural network parameterized by $\theta$:

where $y_{i}=\mathbb{E}_{s^{\prime}\sim\epsilon}[r+\gamma\max_{a^{\prime}}Q^{*}(s^{\prime},a^{\prime};\theta_{i-1})|s,a]$

During the backward pass, the gradients can be calculated as

Though RL has been pursued as a tool for penetration testing recently, the approaches to model the network vary significantly. Alternative methods to modeling penetration testing including hypothesis generation, ontology-based, attack trees and attack graphs. Hypothesis generation model [8] is an organizational network presentation for cyber defense while ontology-based models [9] focus more on the semantics of penetration testing. However, neither of them contains any structural information about the network itself. While both attack trees [10] and attack graphs do provide structural representation of the network, attack graphs are more generative and attack trees are special cases of attack graphs. As a result, attack graph are the most recognized method for the modeling of penetration testing environment [11].

The use of deep RL for attack graphs has seen recent development. Other than Ghanem and Chen [12], the authors in the RL for attack graphs literature use fully observable MDPs to model networks. Many authors use the Common Vulnerability Scoring System (CVSS) to furnish their MDPs (CVSS-MDPs). Yousefi et al. provide the earliest work doing so in deep RL for penetration testing [13]. Hu et al. extend the use of the CVSS by proposing to use exploitability scores weight rewards [14]. Gangupantulu et al. [15, 16] and Cody et al. [17] explicitly extend the methods of Hu et al. with concepts of terrain. Gangupantulu et al. advocate defining models of terrain in terms of the rewards and transition probabilities of MDPs, first in the case of firewalls as obstacles [15], then in the case of lateral pivots nearby key terrain [16]. Cody et al. apply these concepts to exfiltration [17]. Other authors either handcraft the MDP or do not remark on how its components are estimated.

Many authors apply generic deep Q learning (DQN) [6, 7] to solve point-to-point network traversal tasks [13, 18, 19, 14, 15]. Typically the terminal state is unknown and solutions take the form of individual paths. Others develop domain-specific modifications for deep RL including the double agent architecture [3], a hierarchical action decomposition approach [20], and various improvements to DQN termed NDSPI-DQN [21]. Another line of research focuses on developing more specific penetration testing tasks. A number of authors define more specific tasks by reward engineering and other modifications to the MDP including formulations of capture the flag [22], crown jewel analysis [16], and discovering exfiltration paths [17]. This paper extends this line of research with a methodology for exposing SDR.

Gangupantulu et al. [15] proposed that cyber terrain can be modeled into CVSS-MDPs by adding transition probabilities for traversing firewalls and negative rewards for different protocols. Cody et al. [17] later modeled the services-based defensive terrain in CVSS-MDPs based on the assumption that the attackers can infer the presence of defenses terrain based on the services running on a host. We adopt their methods and classify the services into four categories: authentication, data, security and common. Our reward hierarchy assigns -6 for authentication, -4 for data and -2 for security and common. Moreover, the type of actions has an effect on the rewards. n+1 (-1, -3 and -5) is assigned for scanning action while n (-2, -4 and -6) is assigned for exploiting action.

In our surveillance detection routes (SDR) algorithm (Algorithm 1), we have a target node of interest which we want to explore all the services running on it. The goal of SDR is to gain the service information of the target node along with maximizing service information discovery along other areas of the network while being cautious and not triggering any defensive terrain area. We give a discovery reward of 100 to the target node when all its service have been discovered. To encourage the service discovery the agent receives a +1 reward for each service discovered on a node. The algorithm is divided into two phases - a warm-up phase and a training phase.

In the warmup phase, we want to update our goal for the RL agent to not only gain information of just the target node but also other nodes from where we receive positive reward indicating that the defense terrain allows us to access this area. The following steps are taken in the warmup phase:

• •

  We define a certain number of episodes for warmup phase in the training configuration.

• •

  In the warmup episodes the RL agent does not learn (no weight updates) but only monitors positive reward during an episode.

• •

  If the RL agent receives a positive reward from a scanning action, then that node is added to the goal along with the target node and its reward for compromise is set to 100.

• •

  The algorithm allows only one node (which gives out the maximum positive reward) from each subnet to be part of the goal as gaining control of one node in a subnet is enough to gain service information of the entire subnet.

At the end of the warmup phase, we have these dynamic nodes along with the target node of which we must gain the service information to reach the goal. The number of dynamic nodes being a part of the goal decreases as the scale value of defense terrain increases. Therefore, we limit the agent’s exploration capability as we increase the scale value of defense terrain.

In the training phase, the agent interacts with network in an episodic fashion to learn which is the best possible path to gain service information of all the target nodes identified during the warmup phase.

Conventionally, DQN is the most basic algorithm used for modeling RL on penetration testing. Nguyen at al. proposed a method that utilizes two A2C agents: one called the structural agent that learns the structural information about subnets, hosts and firewalls as well as the connections between them. The other called the exploiting agent selects actions to take and the target of them. Their method solves the scalability problem of DQN to some extent and has a better capacity for large networks. We improve upon this method by applying proximal policy optimization (PPO) instead of A2C for both of the agents. PPO is an advanced RL algorithm known for its convergence speed, stability and sample efficiency. It optimizes the following clipped surrogate objective function to prevent performance collapse caused by a large policy update:

where $\rho_{t}(\theta)=\pi_{\theta}(a_{t}|s_{t})/\pi_{\theta_{\mathrm{old}}}(a_{t}|s_{t})$ is the probability ratio of the new policy over the old policy. The advantage function $A_{t}$ is often estimated using the generalized advantage estimation [23], truncated after $T$ steps:

The same network framework as in Cody et al [17] is used for our experiment but with different configurations in defense mechanism. To simulate real-world network conditions, there are layers of defenses between the Internet and the innermost private network. Systems that require Internet to provide service (HTTP, email) are most vulnerable to attack; and are typically in the Demilitarized Zone (DMZ) with limited access to private network resources. The private, internal networks are separated from the DMZ with firewalls that apply rules that only allow connections to specific internal servers/services. VPN services to the internal network is protected with VPN Management Firewalls that apply network rules allowing only authorized and authenticated user traffic to traverse internally over an encrypted connection. Internal network subnets are separated based on access rules and allow traffic to egress to the Internet if it is authorized, as well as applying rules for network traversal between subnets. Finally, access to the innermost subnet is controlled by a firewall that allows only authorized traffic in or out, and only to specific hosts.

These security controls were known and applied by the designers but were intentionally left unknown to the model to provide an accurate simulation of an attacker exploring an unknown network environment.

The hosts are each represented as an 1D vector that encodes its status (compromised, reachable, discovered or not) and configurations (address, services, OS and processes). Next, our environment combines all vectors of hosts in the network as a entire state tensor. Our action space contains 6 primitive actions for scanning, exploiting and privilege escalation.

For these experiments, the initial host is set at (1, 0) while the terminal host is set as (3, 1), (8, 2) or (9, 2). Here, the host (x, y) refers to the host indexed by $y$ in subnet $x$. The initial host is compromised, reachable and discovered by default so that it allows the agent to perform further exploration, thus the simulation assumes the attacker already has gained this foothold in the network. The goal of SDR is to explore all the services of the target host. And a high positive reward (100) is assigned if the goal is reached.

The experiment is conducted on the single-agent A2C model and two variants of the double agent (DA) architecture[3]. In the original double agent model, DA-A2C, both the structuring and the exploiting agents are trained using the A2C algorithm. To achieve better sample efficiency and training stability, we combine the PPO algorithm [4] with the DA architecture and build a DA-PPO model, where both RL agents are trained using PPO. We use Adam as the optimizer of our network. The A2C model is trained for 4000 episodes and the two double agent models are trained for 8000 episodes with a maximum of 3000 steps in each episode. The episode terminates either when the goal is reached or when the step limit is reached. Both the A2C model and the structuring agent of the DA models use deep neural networks (DNNs) with three fully connected layers of 64, 32 and 1 and the exploiting agent of the DA models use a DNN with two fully connected layers of size 10 and 1. All DNNs use tanh activation functions for non-output layers and softmax for the output layer.

We train the A2C, DA-A2C, DA-PPO to convergence. Our surveillance detection algorithm is run on four different scales values namely 1, 3, 5 and 11 for host (9,2) (8,2), and (3,1). For host (9,2) and (8,2) we run an extra scale of 15. The scale values were experimental in nature and each scale defines a certain drop in exploration of the network. When the scale value increases, the agent becomes more risk-averse and thus keeps on reducing the amount of exploration.