Learning Movement Strategies for Moving Target Defense
Authors: Sailik Sengupta
Subbarao Kambhampati
Venue:  (2021)
Keywords: Multi-agent Reinforcement Learning
Moving Target Defense
Stackelberg Security

Abstract: The field of cybersecurity has mostly been a cat-and-mouse game with the discovery of new attacks leading the way. To take away an attacker's advantage of reconnaissance, researchers have proposed proactive defense methods such as Moving Target Defense (MTD). To find good movement strategies, researchers have modeled MTD as leader-follower games between the defender and a cyber-adversary. We argue that existing models are inadequate in sequential settings when there is incomplete information about rational adversary and yield sub-optimal movement strategies. Further, while there exists an array of work on learning defense policies in sequential settings for cyber-security, they are either unpopular due to scalability issues arising out of incomplete information or tend to ignore the strategic nature of the adversary simplifying the scenario to use single-agent reinforcement learning techniques. To address these concerns, we propose (1) a unifying game-theoretic model, called the Bayesian Stackelberg Markov Games (BSMGs), that can model uncertainty over attacker types and the nuances of an MTD system and (2) a Bayesian Strong Stackelberg Q-learning (BSS-Q) approach that can, via interaction, learn the optimal movement policy for BSMGs within a reasonable time. We situate BSMGs in the landscape of incomplete-information Markov games and characterize the notion of Strong Stackelberg Equilibrium (SSE) in them. We show that our learning approach converges to an SSE of a BSMG and then highlight that the learned movement policy (1) improves the state-of-the-art in MTD for web-application security and (2) converges to an optimal policy in MTD domains with incomplete information about adversaries even when prior information about rewards and transitions is absent.

Under review as a conference paper at ICLR 2021
LEARNING MOVEMENT STRATEGIES FOR MOVING TARGET DEFENSE
Anonymous authors Paper under double-blind review
ABSTRACT
The field cybersecurity has mostly been cat-and-mouse game with the dis- covery of new attacks leading the way. To take away an attacker's advantage reconnaissance, researchers have proposed proactive defense methods such as Moving Target Defense (MTD). To find good movement strategies, researchers have modeled MTD as leader-follower games between the defender and cyber- adversary. We argue that existing models are inadequate in sequential settings when there is incomplete information about a rational adversary and yield sub-optimal movement strategies. Further, while there exists array of work on learning defense policies in sequential settings for cyber-security, they are either unpopular due to scalability issues arising out of incomplete information or tend to ignore the strategic nature of the adversary simplifying the scenario to use single-agent reinforcement learning techniques. To address these concerns, we propose (1) a unifying game-theoretic model, called the Bayesian Stackelberg Markov Games (BSMGs), that can model uncertainty over attacker types and the nuances an MTD system and (2) a Bayesian Strong Stackelberg Q-learning (BSS-Q) approach that can, via interaction, learn the optimal movement policy for BSMGs within a reasonable time. We situate BSMGs in the landscape of incomplete infllmeaiioooootooonn Markov games and characterize the notion of Strong Stackelberg Equilibrium (SSE) in them. We show that learning approach converges then highlight that the learned movement policy (1) improves the state-of-the-an in MTD for web-application security and (2) converges to an optimal policy in MTD domains with incomplete information about adversaries even when prior information about rewards and transitions absent.
SSE of a BSMG and
INTRODUCTION
The complexity of modern-day software technology has made the goal of deploying fully secure cyber-systems impossible. Furthermore, an attacker often has ample time to explore a deployed system before exploiting it. To level the playing field, researchers have introduced the idea of proactive cyber defenses such as Moving Target Defense. In Moving Target Defense (MTD), the defender shifts between various configurations of the cyber-system (1). This makes the attacker's knowledge, gathered during the reconnaissance phase. useless at attack time as the system may have shifted new configuration in the window between reconnaissance and attack. To ensure that an MTD system is effective at maximizing security and minimizing the impact on the system's 's performance, the consideration of an optimal movement strategy important (2: 3).
MTD systems render themselves naturally to game-theoretis formulation- modeling the cyber- system as a two-player game between the defender and an attacker is commonplace. The expectation that the equilibrium of these games yields an optimal (mixed) strategy that guides the defender on how to move their dynamic syber-system in the presence of a strategic and rational adversary. The notion of Strong Stackelberg Equilibrium predominantly underlies the definition of optimal strategies in these settings (4; 5) as the defender deploys a system first (acting as leader) while the attacker, who seeks attack the deployed system, assumes the role of the follower. In many real-world scenarios, single-stage normal-form games do not provide sufficient expressiveness to capture the switching costs of actions (4; 6) or reason about the adversary's sequential behavior (7; 8). On the other hand, works that consider modeling the MTD as multi-stage stochastic game (9; 10; 11; 8), do not model incomplete information about adversaries. a key aspect of the single-stage normal-form

---

Under review as a conference paper at ICLR 2021
33.3%
50%
25%
25%
33.3%)
33.3%
A
39%
48%
45%
2.5%
25%
25%
25%
35%
25%
48%
Env
x
x
Figure 1: The defender starts with an uniform random strategy (x²);; it switches to possible configuration of a software system with equal probability in each state. Then, the defender, upon interactions with environment and simulation of adversary in their head, adapts its strategy at every step and finally converges to the Strong Stackelberg Eq. (SSE) of the BSMG yielding x².
formalism (known as Bayesian Stackelberg Games (BSG) (12; 6)). To address these concerns about expressiveness, while remaining scalable for use in cyber-security settings, we propose the unifying framework of Bayesian Stackelberg Markov Games (BSMG). We show that BSMGs can be used to model various Moving Target Defense scenarios, capturing the uncertainty over attacker types and sequential impacts of attacks and switching defenses. We characterize the notion of optimal strategy as the Strong Stackelberg Equilibrium of BSMGs and show that the robust (movement) strategy improves the state-of-the-art found by previous game-theoretic modeling.
While multi-stage game models are ubiquitous in security settings, expecting experts to provide detailed models about rewards and system transitions is considered unrealistic. Thus, researchers have considered techniques in reinforcement learning to learn optimal movement policies over time (13; 14; 15; 16). Unfortunately, these works ignore (I) the strategic nature and the rational behavior of an adversary and (2) the incomplete knowledge a defender may possess about their opponent. This, as we show in our experiments, results in new attack surface where the defender's movement policy can be exploited by an adversary. To mitigate this, we bridge the knowledge gap between existing work, and techniques multi-agent reinforcement learning by proposing a Bayesian Strong Stackelberg Q-learning (BSS-Q) approach (graphically shown in Figure 1). First, we can show that BSS-Q converges to the Strong Stackelberg Equilibrium of BSMGs. Second, we design an Open-AI gym (17) style multi-agent environment for two Moving Target Defenses (one for web-application and the other for cloud-network security) and compare the effectiveness of policies learned by BSS-Q against existing state-of-te sire--ofthhe ffftth-art art static policies and other reinforcement learning agents.
In the next section, we motivate the need for a unifying framework and formally describe the proposed game-theoretic model of BSMGs. We briefly discuss how Moving Target Defenses modeled as BSGMs. We then introduce the Bayesian Strong Stackelberg Q-learning approach and show that converges the SSE of BSMGs, followed by section showcasing experimental results. Finally, before concluding, we discuss related work.
BAYESIAN STACKELBERG MARKOV GAMES (BSMGs)
Markov Games (MGs) (18) are used to model multi-agent interactions in sequential planning problems. Under this framework, a player can reason about the behavior of other agents (co-operative or adversarial) and come up with policies that adhere some notion of equilibrium (where agent can gain by deviating away from the action or strategy profile). While MGs have been widely used model adversarial scenarios, they suffer from two major shortcomings- (1) they do not consider incomplete information about the adversary (19; 7: 20; 13) and/or (2) they consider weak threat models where the attacker has no information about the defender's policy (21; 14). On the other hand, Bayesian Stackelberg Games (22; 6) are a single-stage same-theoretic formalism that addresses both of these concerns but cannot be trivially generalized sequential settings.
2

---

Under review as a conference paper at ICLR 2021
To overcome these challenges of expressiveness required for Moving Target Defenses (MTDs) while ensuring scalability, we introduce the formalism of Bayesian Stackelberg Markov Games (BSMGs). BSMGs extend Bayesian Stackelberg Games (BSGs) multi-stage sequential games. While one can consider using existing formalism in Markov Games that capture incomplete information, they face severe scalability issues and have thus been unpopular in cyber-security domains (we discuss how BSMG is situated in this landscape of models in section 5). In the context of Moving Target Defense (MTD), BSMG acts as a unifying framework helping us characterize optimal movement policies against strategic adversaries, capture transition dynamics and costs of the underlying cyber-system, aid in reasoning about stronger threat models, and consider incomplete information about strategic adversaries. Formally, BSMG can be represented by the tuple (P, θ, A, T ,²)) where,
P= A A2. A.)) where D denotes the leader (defender) and A denotes the follower (attacker), In our model, only the second player has types.
S (2, . are k (finite) states of the game, + = 10,.02... .0, denotes & probability distributions (for k states) over the attackers and (s)s) denotes the probability of i-th attacker type in state
} denotes the action set of the player and A' (s)s represents the set of actions/pure strategies available to player i in state s.
A AAP.AAA
r'( a², ..i.,ss s') represents the probability of reaching a state s' E S from the state s E S when the DD chooses a² and attacker type choose the action a<:
U (UP, U- ward/utility of 'D and an attacker type A; respectively if, in state 8, actions a and a are chosen by the players,
U } where UP (s, (s,uP, a²) and (', aP, ,aA,) represents the re-
>" + (0, 1) the discount factor for player i. We will assume that 7. =7: =%
In BSMGs the individual stage games constitute normal-form Bayesian games with distribution over attacker types; this is in contrast to the unit probability over a single adversary type in MGs. Both in physical-security (22) and cyber-security (6) domains, defenders are known to have knowledge about follower types, a classic case of knownn-mkkrowss BSMGs provide the expressive power to represent this information; precisely 02 represents the probability estimate with which defender believes certain kind of adversary is encountered in particular state of the game.
Note that defender is expected deploy a system first. Thus, a strong threat model assumes that all the attacker types A; know the defender's policy, making the Bayesian notion of Stackelberg Equilibrium an appropriate solution concept for such games. For a normal-form game, let a defender's mixed policy be denoted as and let us denote an attacker type A,'s 4 response set (i.e. set of best responses to x) as R (x)). If the response set for all adversary types is singleton, then the action profile (z,, R2 (x), ... Rt (x)) constitutes a Stackelberg Equilibrium of the normal-form game (23). When the response set contains more than one action, the final response chosen can yield different rewards for D. In such cases, popular assumption made in general-sum games is to consider the response that results in the optimal rewards for D; this is termed as the Strong Stackelberg Equilibrium (SSE) (24; 22; 4; 6). In contrast to the notion of Weak Stackelberg Equilibrium, which considers the pessimistic case, an SSE is guaranteed to exist and yields a unique game value to the defender regardless of the particular SSE chosen (25; 26). Thus, we consider SSES as the solution concept in BSMGs and highlight a few properties about player strategies at equilibrium for BSMGs (the proofs are deferred to Appendix A).
Lemma 1. For a given policy of the leader/defender in BSMG, every follower/attacker type will have a deterministic policy in all states s e S that an optimal response.
Corollary 1. For an SSE policy of the defender, denoted as x, each attacker type A, has deterministic best policy q: The action profile (Ir, .1......................... qe) denotes the SSE of the BSMG.
Lemma 2. If an action profile (z. .1..... 9:) yields the equilibrium values V.D and V:A. to the players and is an SSE of BSMG, then Vs E S (r(s), Bayesian game represented by the Q-values Q. (s), Qz1,, (s) vi tI.
.s))s) is an SSE of the bi-matrix
When the parameters of a game are provided up-front, an approach similar to calculating Strong Stackelberg Equilibrium in Bayesian Games (12) alongside Mixed- Mixed-Integer Non-Linear Programming
3

---

Under review as a conference paper at ICLR 2021
approaches (7) or Bellman-style approaches for Markov Games (20) can be leveraged to find the defender's s policy. In contrast, when came-parameter are difficult to provide upfront but interaction with an environment is considered possible, we can resort reinforcement learning techniques. Before proposing our model-fre multi-agent reinforcement learning method in the next section, we briefly discuss how the various MTDs, used later the experiments, are modeled as BSMGs.
2.1 MODELING MOVING TARGET DEFENSE SCENARIOS AS BSMGs
Moving Target Defense (MTD) is defined by the tuple (C, M) where C' represents the set of configurations system can choose to be in, I'' represents a timing function that determines when system switches and M represents a movement function that determines the movement policy (3). We assume a constant function T for switching (the game clock) and discuss how we can leverage C to model the states and the actions of our BSMG. Finally, we leverage existing knowledge, discussed in literature, to model the follower types for particular MTD scenario.
2.1.1 MTD FOR
SECURITY
In (6), the authors model an MTD for web-applications as Bayesian Stackelberg Game (BSG) (22). In addition, they consider the performance impact of movement between configurations (downtime, service latency, etc.) when coming up with movement policy. Given this utility is function of two-stage strategy, this information can't 't be accurately modeled by a single-stage normal-fome BSG that results in state-agnostic sub-optimal policy. Clearly, the BSMG, given its sequential nature, is better suited to capture this information.
The BSMG has ICI states, each representing configuration of the MTD system. Each configuration has an equal probability of being the start state in an episode and there exists no terminal state. In each state, 8 S, (s) = C, i.e. the defender can choose move to any configuration (this includes remaining in the same state). The three attacker types are denoted as A A2, A3} } and the probability distribution, provided in (6), over these types in-state s represented is 0z. The adversary's action sets, denoted by (A- AA)), represent mined CVEs from the National Vulnerability Database (27) (similar to (6)). As per the original domain, the distribution over attacker types (and
the follower's ' attack set) remain the same in all states of the BSMG.
2.1.2 MTD AGAINST MULTI-STAGE ATTACKS
MTD for cloud networks has modeled the problem of placing Intrusion Detection Systems (IDSs) as a Markov Game (21; 20). The key objective of these works is to minimize the performance impact of deployed defense configuration while ensuring security is maximized. While BSMGs allow us to represent uncertainty over attacker types, existing formulations consider single follower types, thereby boiling down to MG. Although will use an MG for this scenario, note that our framework capable of incorporating ongoing research on the characterizing attacker types in the context of cyher-systems (28).
Attack graphs are an attack representation method used to capture possible attack paths through a network (29). Nodes of this attack graph, that describe physical locations in the cloud system and an attacker's ' privilege level, constitute the states of our BSMG, similar to the MG formulation in (20). The defender's actions in a state A represents IDS that can be deployed in the state identify possible exploits and the attacker's 's actions represent the possible exploits, which are obtained by considering CVEs effective against the defender's 's cloud system.
BAYESIAN STRONG STACKELBERG Q-LEARNING IN BSMGs
While game-theoretic formalism has been used to model various cyber-security scenarios (30; 31; 6). it is impractical to expect security experts provide the parameters of the game upfront (13; 15; 16). In the context of Moving Target Defense (MTD) in particular, determining the impact of various attacks, the asymmetric impacts of particular defense on performance, and the switching cost of a system are better obtained via interaction with an environment. Further, there exists uncertainty regarding the success of an attack (eg. a buffer overflow attack may need significant tinkering for it to
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Bayesian Strong Stackelberg Q-learning (BSS-Q) for BSMGs.
1: In: (P,S, A, θ 7), mt mtd_sim, a, num _em_episodes
2: Out: Policies of the players æ for D, o² Vi E A
3: while num n seee_eeesossssseee > 0 do
4: s + sample start state from S
5: while 8 & terminal state OR !max_eep seax_eps_een do i k- sample attacker type using 0g from a aat
6:
7:
a & e-greedy sampling form r(s), (s(s rD ,d, , f- -mmdd sim.act(s, a aaa)
8:
9:
QD + (1-1a1aa ai-aa)DDisss
AA) tapp PVP
10:
Q4. + 11-1aja (11-)((01 (s, at1)+ + +almd: + AP (5')
11:
(x, 9z), (VD, VAii t solve Bayesian Stackelberg Game(Q QA1)V)
12: end while
13: end while
be successful) and also the success of defense mechanisms (eg. Intrusion Detection Systems based on machine learning can be inaccurate) which can be better inferred via repeated interactions.
In existing works on MTD, the goal. in the presence of (1) game parameters and (2) incomplete information about adversary, is to learn robust policy that works best, in expectation, against all adversaries. When modeled as a multi-agent reinforcement learning problem, an interesting distinction ensues. If the defender gets interact with the environment and an actual adversary, they can update their incomplete information about the adversary, leading to a Bayesian style update regarding the attacker types in the new state returned by the environment (14). Unfortunately, reinforcement learning methods, which are often sample-inee cunple-inefficieet, will require abundant interaction with real- world adversary; an impossible feat in cyber-security scenarios. Thus, the best the defender can do is to simulate a rational adversary in their head. Given the adversary's 's type is unknown during the policy learning phase, the defender needs to sample an attacker from the set of attacker types in each state of the game to eventually learn a robust policy in each state.
To learn robust policy, we consider the use of a Multi-agent Reinforcement Learning approach for BSMG. Specifically, given the inherent leader-follower paradigm present in our setting, we propose the use of a Bayesian Strong Stackelberg Q-learning (BSS-Q) approach for BSMGs discussed in algorithm 1. The approach is similar to existing work in multi-agent reinforcement learning (MARL) and considers a Bellman-style Q-learning approach for calculating the agent policies over time. In lines 9 and 10, we update the Q-values for the players D and adversary type A; in the state using the rewards obtained by acting in the environment. Since we simulate the adversary, we can select an action its behalf and send it across to the simulator mtd_ s sim. Given mt d sim which has an idea whether the attack succeeded or failed, it can send us back the attacker's reward. In existing works on MARL, they make default assumption that the defender gets the attacker's 's reward even when the adversary is not simulated (32). While this assumption is somewhat justified in the context of constant-sum or common-payoff games, it becomes unrealistic in the context of general-sum games.
In line 11, we use a Bayesian Stackelberg Game solver to calculate the BSS of the normal form Bayesian bi-matrix game defined by the Q-values in state It is known that finding an SSE of Bayesian Stackelberg Game is NP-hard and thus, the computation in line 10 might seem prohibitive. In practice, as shown in our experiments, compact representation help in computing the value and the policy within second even for web-application domains with more than 300 executable attack actions (6). Note that even though only one follower type acts in the environment, the change in the defender's 's policy because of this can lead to the other follower types switching their actions. Hence, solving the Bayesian stage game (in its full glory) becomes essential to converge to SSE policy of the BSMG (and batch update methods, which can speed-up computation, become less reliable). Methods that scale-up equilibrium computation in security games (4) rely on known reward structure. Unfortunately, this makes it difficult to justify their use in our setting, where the rewards are unknown and thus, may have an arbitrary reward structure.
the scenario as a MILP (22) can
If interaction with adversary is possible, the defender should consider Bayesian style update of the parameters 0, depending on observed action and the observed reward after line 10.
5

---

Under review as a conference paper at ICLR 2021
Delender's reward
agent
B55 0
URS-
BEXPO
S-FTT
20
60
600
812
20 -0
10
850
20
-10
50
20
40
60
F0
edlsodes
episodes
episocies
eptcodes
Figure 2: The defender's value in the four states of the BSMG modeling the MTD for web-applications when using BSS Q-learning (blue) compared Uniform Random Strategy (orange) (34), Bayesian version of EXP-Q learning (green) (13) and the optimal stage-agnostic strategy (red) (6).
Note that one can choose to move the attacker type sampling (Line 6) outside the inner while loop. This would imply sampling an attacker for each episode and interacting with them, making it easier to understand that the attacker type can plan for future rewards (when y >> 0) and come up with far-sited strategies. Given that an attacker type used it own Q-value and value functions for updating its Q-values (Line 10), sampling done is each state (i.e. inside the nested while loop) still ensures that the attacker types are not myopic. Further, sampling in each states results in the defender not over- wer--itting one attacker in one episode and then having adjust it policy for different attacker in the next one which can lead to a slower convergence. Now, we show that our method converges to the optimal policy at Bayesian Strong Stackelberg Equilibrium.
Proposition 1. (Convergence Result) The Bayesian Strong Stackelberg Q-learning approach converges to the BSS of a BSMG. (The detailed proof can be found in Appendix A.)
Proof Sketch. We show that for all the players (i.e. the defender and the individual attacker types) (1) the Q-value calculation (that uses the game values of the future states, denoted as an operator) is a real contraction operator and the (2) update process (Line 9-10 of algorithm 1) converges to fixed point. While the proof skeleton is similar to the one in (33), the proof is more complex due to the presence of multiple attacker types. In proving (I), we need reason about Bayesian stage games. D
4 EXPERIMENTS
We conduct experiments to understand the effectiveness of the learned movement policies for two MTD scenarios. As many existing baselines can't handle unknown utilities and transition dynamics, we develop an OpenAl style (17) game simulator that is aware of the underlying game parameters but interacts with the learning agents only via selected public-facing APIs. This helps us compare against baselines that assume game parameters are available. While the impacts of attack actions obtained in the simulator using the Common Vulnerability Scoring Service (CVSS), consider real system interaction, pending investigation, to obtain less-informative and sparse rewards. More details about the game simulator and additional experiments can be found in the supplementary material. For both experiments, the defender (who samples a follower type in each interaction) is single-thread process and regardless of their own policy, are pitted against strategic and ration adversary. The code used Gurobi for solving the Bayesian Stackelberg Game (BSG) game in line 11 of algorithm 1 and ran on Intel Xeon(R) CPU ES-2643 v3 @ 3.40GHz with 64GB RAM.
MTD FOR -EB-APPLICATIONS
We use the game parameters obtained in (6) to design game simulator. The simulator, given the current state and the defender's action, lets us return the switching costs as a part of the reward obtained via interaction with the environment. The game has four states, each representing full-stack configuration of the system- [pyy, MySQL)<py, PostgreSQL) MySQL) PostgreSQL)). We consider three attacker types- A, (database hacker) with 269 actions, A (script kiddie) with 34 actions, and Ay (mainstream hacker) with 48 actions (detailed CVE-list can be found in the supplementary material).

---

Under review as a conference paper at ICLR 2021
state
state
state
Detender's reward
agant
B65-Q
URS
EXP-Q
-5
Nosh-Q
-10
20
10
60
100
0
10
80
100
20
60
80
100
opisades
cp
apisodes
Figure 4: Values in the BSMG-based MTD for IDS placement when using BSS Q-learning (blue) compared to Uniform Random Strategy (orange), EXP-Q learning (green) and Nash Q-learning (red).
The defender's policy in each state is mixed strategy that directs how to switch to different configuration, while an attacker type's policy prioritizes attacks that cause maximum damage. In Figure 2, we plot the defender's reward (over trials) in this BSMG for our BSS-Q learning agent and other baselines. In each setting, we use a discount factor of y = 0.8, an exploration rate of e = 0.1 (that gradually decays to 0.05) and initiate the agents with uniform random strategy (except in the case of S-OPT explained as follow). The average time used by the methods for one trial are is shown in Figure 3. We will now explain all the baselines considered.
Static Movement Policies These defense policies, evident from its name, are determined up-front (using game parameters pro- vided initially) and do not change. The placebo baseline, used as a sanity check in the context of MTDs, is the Uniform Random Strat- egy (URS); it selects each action in state with equal probability (34). Then, we consider the state-agnostic optimal policy (S-OPT) determined by the game-theorete formulation of the MTD with switching costs (6); this is the state-of-the-arr art movement policy in this scenario.
Agents
Time (sec)
Static
84.097 + 0.157
B-EXP-Q BSS-Q
224.827 + 1.449
151.127 13.403
B-Nash-Q
> 3600
Figure 3: Run-time of the learn- ing agents for 80 episodes.
Learning Agents In (13), the authors leverage adversarial multi-arm bandits in learning policies for agent in Markov Security Games. While the paper draws inspiration from works in Stackelberg Security Games (4), the EXP Q-learning approach does not consider (1) a strategic adversary that can adapt (2) uncertainty over attacker types. We adapt their algorithm for BSMGs by ensuring that the update to the sum of rewards is weighed by the attacker type's s probability. We call this the Bayesian EXP Q-learning agent (B-EXP-Q). The Bayesian Nash Q-learning (B-Nash-Q) (14), even after remove the Bayesian update of 0., does not scale for this domain and thus, can only be compared against in simple toy domains (a non-Bayesian version is discussed for the other MTD).
In Figure 2, we see that the BSS Q-learning agent outperforms URS in all the states of the BSMG and better than B-EXP-Q and S-OPT in 82 and 83, attaining reward close O, which is the maximum reward possible in this game. In so and $1. the B- B-EXP-Q agent, similar to the BSS-Q agent, converges an optimal movement strategy. Meanwhile, in $3, the best response of the attacker results in lower rewards for particular defense action, in turn making this action less probable. As soon as the defender switches to more promising action, the attacker changes their response to yield a low value for that action. It should be no surprise that defense strategies learned via single-agent RL methods (eg. (13; 15; 16)) are prone to be exploitable against strategic opponents in cyber-security scenarios. The existence of such cycle makes the learned policy exploitable, resulting in low rewards consistently. In such cases, even the URS yields better rewards because its lack bias makes it less exploitable. The S-OPT, described in (6), yields strategy that moves between two MTD configurations represented by 82 and 83. As such a strategy can never find itself in any other state of the game, to be fair, we ensure that the start state in each episode is uniformly sampled from 82, 83- Thus S-OPT has no footprint in the states So and 51. As stated before, the S-OPT strategy, a resultant of the state-agnostic theeetthereeic formulation, is doomed to be sub-optimal. Unsurprisingly, the policy learned by BSS-Q is shown to be better in $2 and $3. A drop in rewards near episode 70 in $1 for BSS-Q Q can be attributed the discovery of powerful attacks by two follower types in one trail.
7

---

Under review as a conference paper at ICLR 2021
MTD FOR IDS PLACEMENT
We consider the General-Sum Markov Game formulated in (20). As described earlier, this domain has four states, of which, one is terminal state. As the set of follower types in this game in singleton, the BSMG model boils down to Markov Game. Hence, the vanilla EXP-Q agent can be used (albeit against rational follower). The URS baseline remains unchanged, S-OPT deems to exist and instead of Bayesian Nash, we can consider the relatively more scalable Nash Q-learning (Nash-Q) agent (35).
The rewards obtained by the various agents in the three non-terminal states of the game are plotted in Figure 4. We do not plot the rewards obtained by the model- inference algorithm in (20) because the policy learnt by the proposed BSS-Q agent eventually converges an optimal policy at SSE (plotting both results in overlapping graphs after BSS-Q converges, hampering readability). Given the domain has relatively fewer actions, we average the reward over 10 trials; each trial had 100 episodes and with an exploration rate of 0.1 and a discount factor of 0.8.
The BSS Q-learning agent outperforms the two previous baselines- URS and EXP-Q- in at least one of the three states. In this setting, the Stackelberg threat model adversely affects the policy learned by EXP-Q resulting in consistent low rewards for states 81 and $2. While (20) shows that the SSE S NE for the MG owing to the structure of the defender's strategy sets, we see that Nash-Q performs slightly worse the BSS-Q in state 81. This happens because the existence of multiple Nash Equilibria throws-off Nash-Q Q from the optimal reward path (36). Similar rewards are observed in all other states.
5 DISCUSSION AND RELATED WORK
The Landscape of Existing Games We seek to an- swer two questions- where does our BSMG fit in and why it is useful. In Figure 5, we graphically situate BSMG in the landscape of existing work. BSMG, as seen in the experiments, can generalize Markov Games (18) (and therefore. MDP). Instead of assuming infi- nite reasoning capabilities required for Bayesian Nash equilibrium (37), Bayesian Markov Game considers sce- narios where players have finite levels of belief' about other players(s) (38). On the other hand, Markov Games with Imperfect Information (MGIIs) assumes a Marko- vian property over the state, the observations, and the joint set of actions; this results in reasoning over op- ponent types and allows them to decompose Partially Observable Stochastic Games (POSGs) (39) into set of Bayesian stage-games games (40). In BSMGs, the assump- tion of a pre-specified distribution over attacker types helps us (1) avoid reasoning over the nested belief space, and (2) can be interpreted as the private information of the opponent in MGIIs (and POSGs) as being provided upfront. Thus, BSMG becomes a special case of MGII and BMG with the added semantics of leader-follower interaction. Our assumptions (about modeling imperfect information) helps our game be scalable while providing adequate expressive power in the context of MTDs.
POSG
MGII
BMG
BSMG
MG
MDP
Figure 5: Situating BSMGs in the land- scape of game-theoretic models that cap- ture incomplete information.
Multi-agent Reinforcement Learning in Markoy Games A standard solution strategy in MGs, when т and U are unknown but a simulator is available, is to adapt the Bellman's 's update used in the single-agent Markov Decision Processes (MDPs) for multi-agent reinforcement learning to learn equilibrium policies (36). In the context of MARL, researchers have investigated different notions of equilibrium. The min-max Q-learning is meaningful when the game has a zero-sum reward structure (41). On the other hand, Nash Q-learning, introduced in (35), has been categorized into two types by (42)- Friend, where the game defined by the Q-values always allows for an optimal joint action profile, and Foe, where the game admits a saddle point solution. The convergence of these algorithms is mostly shown by the fact that Q-values of the states in self-play, given infinite exploration, approach the correct Q-values (i.e. calculated Q-values if all the parameters of the game
8

---

Under review as a conference paper at ICLR 2021
were provided upfront), The convergence of Nash Q-learning in the context of general-sum games becomes difficult because of the existence of multiple equilibria and the lack of a common incentive or co-ordination amidst agents (36). In correlated equilibrium (CE) Q-learning (43), authors assume the existence of a correlation device accessible to both players. However, the authors show that the learned strategies of the players converge an uncorrelated equilibrium. On the other hand, in Stackelberg Q-learning (32), there exists leader-follower paradigm among the players, i.e ,hhe leader's strategy can be observed by follower before the latter commits to an action. Convergence guarantees in self-play, although popular, become less meaningful when action sets of the players different (defense configuration vs. exploits) and game utilities have a general-sum reward structure.
Leader-follower scenarios Researchers have investigated solution concepts in the context of Stochastic games with multiple followers, but do not model incomplete information about them." 2 The interaction is generally modeled as a Semi-Markov Decision Process (44) and improvements consider (1) multiple followers (45), (2) factored state spaces (46), (3) methods based on deep reinforcement learning (47; 48) etc.
Reinforcement Learning in MTDs Works that are precursors to our BSS-Q learning approach are the min-max Q-learning (21) in the context of complete information MGs and the Bayesian Nash Q-learning (14) for dynamic placement of sensors. Recent works that model the multi-agent cyber-scenarios as an MDPs (RL in Flip-it games (15)) or POMDPs (RL for MTDs (16)) generate policies that can be exploited by strategic adversary.
CONCLUSION
We proposed Bayesian Stackelberg Markov Game (BSMG) that considers the leader-follower scenario and uncertainty over adversary types in Markov Games. We showed that BSMGs are unified framework to characterize optimal movement policies in Moving Target Defenses (MTDs) and then proposed a Bayesian Strong Stackelberg Q-learning (BSS-Q) approach learn robust policies when the rewards and transitions are absent. We showed that BSS-Q learning converges to the SSE of the BSMG. Experiments conducted in two cyber-sccurity scenarios- MTD for web-application and MTD for cloud-networks- showed that policies learned using BSS-Q outperform existing baselines. Supplementary material contains proofs, environment details and additional experiments.
REFERENCES
[1] Sushil Jajodia, Anup K Ghosh, Vipin Swarup, Cliff Wang, and X Sean Wang. Moving target defense: creating asymmetric uncertainty for cyber threats, volume 54. Springer Science & Business Media, 2011.
[2] Sailik Sengupta. Moving target defense: symbiotic framework for ai & security. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 1861-1862. International Foundation for Autonomous Agents and Multiagent Systems, 2017.
[3] Sailik Sengupta, Ankur Chowdhary, Abdulhakim Sabur, Adel Alshamrani, Dijiang Huang. and Subbarao Kambhampati. A survey of moving target defenses for network security. IEEE Communications Surveys & Tutorials, 2020.
[4] Arunesh Sinha, Thanh H Nguyen, Debarun Kar, Matthew Brown, Milind Tambe, and Albert Xin Jiang. From physical security cybersecurity. Journal of Cybersecurity, 1(1):19-35, 2015.
[5] Satya Gautam Vadlamudi, Sailik Sengupta, Marthony Taguinod, Ziming Zhao, Adam Doupé Gail-Joon Ahn, and Subbarao Kambhampati. Moving target defense for web applications using bayesian stackelberg games. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pages 1377-1378, 2016.
[6] Sailik Sengupta, Satya Gautam Vadlamudi, Subbarao Kambhampati, Adam Doupé, Ziming Zhao, Marthony Taguinod, and Gail-Joon Ahn. A game theoretic approach to strategy generation
2 Extending the uncertainty over follower-types BSMGs multiple followers results scalability issues.

---

Under review as a conference paper at ICLR 2021
for moving target defense in web applications. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 178-186. International Foundation for Autonomous Agents and Multiagent Systems, 2017.
[7] Yevgeniy Vorobeychik and Satinder Singh. Computing stackelberg equilibria in discounted stochastic games. In Twenty-Sixth AAAI Conference Artificial Intelligence, 2012.
[8] Ankur Chowdhary, Sailik Sengupta, Dijiang Huang, and Subbarao Kambhampati. Markov game modeling of moving target defense for strategic detection of threats in cloud networks. arXiv preprint arXiv: /1/..9962.. 2018.
(9] Hoda Maleki, Saeed Valizadeh, William Koch, Azer Bestavros, and Marten van Dijk. Markov modeling of moving target defense games. In Proceedings of the 2016 ACM Workshop on Moving Target Defense, pages 81-92, 2016.
[10] Quanyan Zhu and Tamer Başar. Game-theoretic approach to feedback-driven multi-stage moving target defense. In International conference on decision and game theory for security, pages 246-263. Springer, 2013.
[11] Henger Li, Wen Shen, and Zizhan Zheng. Spatial-temporal moving target defense: markov stackelberg game model. arXiv preprint arXiv:2002.103990 2020.
[12] Praveen Paruchuri, Jonathan P Pearce, Janusz Marecki, Milind Tambe, Fernando Ordonez, and Sarit Kraus. Playing games for security: An efficient exact algorithm for solving bayesian stack- elberg games. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems- Volume 2. pages 895-902. International Foundation for Autonomous Agents and Multiagent Systems, 2008
[13] Richard Klima, Karl Tuyls, and Frans Olichock. Markoy security games: Learning in spatial security problems. In NIPS Workshop Learning, Inference and Control of Multi-Agent Systems (2016), pages 1-8,20 2016.
[14] Xiaofan He, Huaiyu Dai. Peng Ning, and Rudra Dutta. Dynamic ids configuration in the presence of intruder type uncertainty. In 2015 IEEE Global Communications Conference (GLOBECOM), pages 1-6. IEEE, 2015.
[15] Lisa Oakley and Alina Oprea. Playing adaptively against stealthy opponents: A reinforcement learning strategy for the flipit security game. arXiv preprint arXiv: 1938, 2019.
[16] Taha Eghtesad, Yevgeniy Vorobeychik, and Aron Laszka. Deep reinforcement learning based adaptive moving target defense. arXiv preprint arXiv: 1911,1191 2019.
[17] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint
2016.
[18] Lloyd Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):1095-11 1100, 1953.
[19] Joshua Letchford and Vincent Conitzer. Solving security games on graphs via marginal probabilities. In Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013.
[20] Sailik Sengupta, Ankur Chowdhary, Dijiang Huang, and Subbarao Kambhampati. General sum markov games for strategic detection of advanced persistent threats using moving target defense in cloud networks. In International Conference Decision and Game Theory for Security, pages 492-512. Springer, 2019.
[21] Quanyan Zhu and Tamer Başar. Dynamic bosecy-based ids configuration. In Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 8600-8605. IEEE, 2009.
[22] Praveen Paruchuri, Jonathan Pearce, Janusz Marecki, Milind Tambe, Fernando Ordonez, and Sarit Kraus. Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games. In AAMAS, 2008, pages 895- 902, 2008
10

---

Under review as a conference paper at ICLR 2021
[23] George Leitmann. On generalized stackelberg strategies. Journal of Optimization Theory and Applications, 26(4):637-643, 1978.
[24] Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy commit to. In Proceedings of the 7th ACM Conference on Electronic Commerce, EC "06, pages 82-90, New York, NY, USA, 2006. ACM.
[25] BV Stengel and Zamir. Leadership with commitment to mixed strategies. CDAM Research Report LSE-CDAM-20004 2004.
[26] Tamer Basar al. Lecture notes non-cooperative game theory. Game Theory Module the Graduate Program in Network Mathematics, pages 3-6, 2010.
[27] National vulnerability database. https: /ttp///vvd.... www.wdiiiitt..... wirist.gon gov. Accessed: 2020-4-23.
[28] Anjon Basak, Jakub Cerný, Marcus Gutierrez, Shelby Curtis, Charles Kamhoua, Daniel Jones, Branislav Bošanský, and Christopher Kiekintveld. An initial study of targeted personality models in the flipit game. In International Conference on Decision and Game Theory for Security, pages 623-636. Springer, 2018.
[29] Oleg Sheyner. Joshua Haines, Somesh Jha, Richard Lippmann, and Jeannette M Wing. Au- tomated generation and analysis of attack graphs. In Proceedings 2002 IEEE Symposium Security and Privacy, pages 273-284. IEEF, 2002.
[30] Kevin M Carter, James F Riordan, and Hamed Okhravi. A game theoretic approach to strategy determination for dynamic platform defenses. Proceedings of the First ACM Workshop on Moving Target Defense, pages 21-30, 2014.
[31] Aaron Schlenker, Omkar Thakoor, Haifeng Xu, Fei Fang, Milind Tambe, Long Tran-Thanh, Phebe Vayanos, and Yevgeniy Vorobeychik. Deceiving cyber adversaries: A game theoretic approach. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 892-900. International Foundation for Autonomous Agents and Multiagent Systems, 2018
[32] Ville Könönen. Asymmetric multiagent reinforcement learning. Web Intelligence and Agent Systems: An international journal, 202):105-121, 2004.
[33] Csaba Szepesvári and Michael Littman. A unified analysis of reinforcement-leariing algorithms. Neural computation, 118))2017-20000 1999.
[34] Rui Zhuang, Scott A DeLoach, and Xinming Ou. Towards a theory of moving target defense. In Proceedings of the First ACM Workshop on Moving Target Defense, pages 31-40, 2014.
[35] Junling Hu, Michael P Wellman, et al. Multiagent reinforcement learning: theoretical framework and an algorithm. In ICML, volume 98, pages 242-250. Citeseer, 1998.
[36] Yoav Shoham, Rob Powers, and Trond Grenager. Multi-agent reinforcement learning: a critical survey. Web manuscript, 2003.
[37] Willemien Kets. Finite depth of reasoning and equilibrium play in games with incomplete information. Technical report, Discussion Paper, Center for Mathematical Studies in Economics
and and....011.. 2013.
[38] Muthukumaran Chandrasekaran, Yingke Chen, and Prashant Doshi. On markov games played by bayesian and boundedly- players. Thirty-Fine First AAAI Conference on Artificial Intelligence, 2017.
[39] Harold William Kuhn and Albert William Tucker. Contributions to the Theory of Games, volume 2. Princeton University Press, 1953.
[40] Liam MacDermed, Charles Isbell, and Lora Weiss. Markov games of incomplete information for multi-agent reinforcement learning. In Workshops at the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
11

---

Under review as a conference paper at ICLR 2021
[41] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[42] Michael L Littman. Friend-or-foe q-learning in general-sum games. In ICML, volume 1, pages 322-328, 2001.
[43] Amy Greenwald, Keith Hall, and Roberto Serrano. Correlated q-learning. In ICML, volume 20, page 242, 2003.
[44] Kurian Tharakunnel and Siddhartha Bhattacharyya. Leader-follower semi-markov decision problems: theoretical framework and approximate solution. In 2007 IEEE International Symposium Approximate Dynamic Programming and Reinforcement Learning, pages 111- 118. IEEE, 2007.
[45] Chi Cheng, Zhangqing Zhu, Bo Xin, and Chunlin Chen. multi-agent reinforcement learning algorithm based stackelberg game. In 2017 6th Data Driven Control and Learning Systems (DDCLS), pages 727-732. IEEE, 2017.
[46] Régis Sabbadin and Anne-France Viet. Leader-follower mdp models with factored state space and many followers-folloers abstraction, structured dynamics and state aggregation. In Proceedings of the Twenty-second European Conference on Artificial Intelligence, pages 116 124. IOS Press, 2016.
[47] Tianmin Shu and Yuandong Tian. M Mind-aware multi-agent management reinforcement learning. arXiv preprint arXiv: 1810.00 0100000147 2018.
[48] Zhenyu Shi, Runsheng Yu, Xinrun Wang, Rundong Wang, Youzhi Zhang, Hanjiang Lai, and An. Learning expensive coordination: An event-based deep rl approach. In International Conference Learning Representations, 2019
[49] Joel Brynielsson and Stefan Arnborg. Bayesian games for threat prediction and situation analysis. In International Conference on Information Fusion. Citeseer, 2004.
A APPENDIX PROOFS
In this section, we present the proofs associated with the lemmas that characterize follower strategies and Strong Stackelberg Equilibrium (SSE) Bayesian Stackelber Markov Games (BSMGs). We then show that, under specific conditions, the SSE Q-Learning (SSE-Q) converges to the SSE of BSMGs.
Lemma 1. For a given policy of the leader/defenderr in BSMG, every follower/attacker type will have a deterministic policy Vs E S.
We note that BSMGs adhere to the Markovian nature and thus, a leader's policy is a Markov stationary policy (7). For each follower type, a modified state transition function r' that accounts for (1) the original transition and (2) the leader policy constitutes a Markov Decision Process (MDP) (i.e. r' = == r.. This guarantees that each follower type has a deterministic best-response policy given a leader's policy.
Corollary 1. For an SSE policy of the defender, denoted as æ, each attacker type A, has deterministic policy 4: The action (x, -1. 4:) denotes the SSE of the BSMG.
We can now extend results known for Markov Games with a single follower type with a singleton response where the distinction between Strong and Weak SE does not arise (32).
An action profile (Ir, .......)e)) that yields the equilibrium values V.P and V.A. to the players is at SSE of BSMG, ifl'vs E S (I(s), q game represented by the Q-values Q2, (s),Q2, (s).
Lemma 2.
is an SSE of the bi-matrix Bayesian
First, note that a follower type can have a pure strategy response that corresponds to a Strong Stackelberg Equilibrium for single-stage normal-form games. Given a defender's policy, the attacker solves a linear (reward) maximization that always has a pure strategy in support of an optimal mixed strategy (22). Hence, (s) is a pure-strategy of the bi-matrix game represented by the Q-values
12

---

Under review as a conference paper at ICLR 2021
state s. This ensures that the SSE of the BSMG (Corollary and the SSE of the bi-matrix games in each state admit pure-strategy for the individual follower types.
We will now prove the lemma in the forward direction by considering proof by contradiction. Let us assume that (1) (xt, 91,..., Qt) is an SSE action profile of BSMG with equilibrium values V2.g. Vp but, (2) 3s S for which (z(s). 91 (s)....................) (c(s) is not the SSE of the bi-matrix Bayesian game defined by the Q-values of s. If it were given that an SSE is bound to exist for the bi-matrix Bayesian game and it yields the highest unique pay-off to the players in bi-matrix Bayesian game, player p (D or A;) should switch from their current strategy to an SSE in state 8. This would clearly yield values higher than Vi. (s) for that state. This violates (I) because V (s) was the equilibrium values of the BSMG corresponding to an SSE policy that has unique optimal value. Thus, (I) implies (2).
A similar proof by contradiction can be constructed for the backward direction. Briefly, if the strategy in the states constitute SSE of the stage game but are not an SSE of the BSMG, it must be possible switch the strategy in least one state yield the higher value guaranteed by the SSE of the BSMG. But if that is the case, the original assumption that the initial strategy in that state is an SSE contradicted.
A.1 PROPOSITION (CONVERGENCE RESULTS)
Our proof of convergence is inspired from the initial work by (33). Let us call the Q-value update step as process - Q where Q represents the space of Q-values. Formally we can express the update equation for the leader D as,
2(QP:t(s, as a = (P a + +
Where V/ represents the leader's ' game value in the Bayesian Stackelberg Game (BSG) defined by Q-values and the distribution over follower types in state sT+1- With some abuse notation, we can drop the arguments (s, a a for both the functions Q" and U and rewrite the above equation by expanding the value function as follows.
Q(QP*)= - + +V (ST+1)
To prove convergence of the functionnoperrtor//peeess conditions hold (as described in (33); the other two conditions mentioned hold trivially in setting, as it holds the case of other Q-learning approaches).
Ω we need to show the following two
(1) The following processes converge to fixed point.
Q
(1 (1-ar) + ATD()D Vi
º = (1 (1-a7)Q² + arQ((QA) Vi
where Qeee represents the Q-values at SSE of the BSMG.
(2) The process Q is a real contraction operator.
[[((Q) !(())l S allQ @1l AQ, E
where < a < 1 and || denotes the supremum operator over the vector space Q.
To prove the conditions in (1), we leverage the Condition Averaging Lemma stated in (33) and thus, have to show that,
Q E(
QA: EIN(Q stc) ) Vi
where the expectation is over the states reached. To show this, we first expand the right hand side of the equation and showing that this expansion is equal to the left hand side.
E((() = UD + E(V
UD + EVV (s'))
UD + Σ 7 VD (s')
=QDA
13

---

Under review as a conference paper at ICLR 2021
where see indicates the game value of the defender SSE. V state represent the value at SSE. The final equality is result of the Bellman equation for multi-agent settings. It is easy see that the same line of reasoning holds for all all follower types.
V. because the Q-matrices in all
To prove the condition in (2), we will first expand the Left Hand Side (LHS) followed by the expansion of the Right Hand Side (RHS). Then we will show that a stricter case the inequality satisfied. We first show this for the follower and then, for the leader.
[ - !((A1111
max (S(QQA R(x))) - QQQ44 R())))
max (VA, (5') p.( (s'))
= max max 4 (5', , R (x)) max Q ( (1 (x)))
7 max Q x. Rh (r)) max Q (s' n., (x)))
The first equality is based on the use the supremum operator. Given that the max occurs for some without loss of generality, can assume this state is going state s'. In similar way, we can expand the RHS for the follower.
al allQA. @1111
max (8, - -QA1(s,,, 4
max max (s', ( 9))
II
max (5, (A Q (s' x, R (x)))
(2)
Note that we now have stricter version of the RHS. If we can now show that Equation 1 S Equation 2, then we can prove condition (2) holds for the Q-values of all follower types. Given 0 S y < we can consider y. Now we have,
7( max ( (((x))) max @Ai RA(())))
a( (max ( (5 RA (x)) - max ( RA:
a
max (Q (5', RA (x)) (
I allQA: QA111
The first inequality holds because in the second step, one can select two different æ-s to minimize the difference while in the third step, one is constrained to select the same for both the Q-values.
Now, we show that also a contraction operator for the Q-values of the defender. Showing the property holds is difficult to show for individual follower types because of the Bayesian nature of the game. It is possible to show this for a transformed attacker conjured using the Harsanyi transformation (49). In this setting, the single attacker type has actions that cross product of the action of all other players and the utilities of the Q-value matrix is the expected Q-value over the original attacker types. Given this single attacker type, use Q" denote the Q-values against this new transformed attacker. Given the solver we are using in our BSS Q-learning approach in calculating SSE of the BSG stage games is equivalent the SSE of this transformed game (22), showing Ω is contraction operator for Q' is sufficient to show convergence. We use AA in the superscripts to denote value for this transformed attacker type.
14

---

Under review as a conference paper at ICLR 2021
-(10)--(Q")) - max (s, R
max (VD (8)) (D()))
? max max Σ ('()) (5) max Σ 0'51000 (x,,,,
7( (mxx
Σ 0'('))DD RD((1)) max Σ RP((()
= a( max
Σ
(x)) max
max ( 0'')
(x)) Σ (6
(s) (x)) (s,
max max
- [0())))(()a
max max II max
(Q" (s.2.94) - (2(5,2.011)
max max max qdd
= aal@p Q
If we were now consider Q Qase for all the player and player types, then the Q-values learned by our method will approach Qeee- While this completes our convergence proof, we note that convergence rate depends two factors. First, Selecting randomly among best-responses, even if multiple exist, for the follower results in slower convergence. Selecting consistently in some order (eg. first after sorting the response set) results in faster convergence. Note that random selection does not cause issues beyond slowing down convergence because for each follower type, given a leader's s strategy, regardless of the best response strategy selected, the game value for both players remains the same due to nature of SSE (25; 26). Second, similar line of reasoning for the defender concludes that pre-defined selection mechanism can result in faster convergence.
B APPENDIX ENVIRONMENT DESCRIPTION
In this section, we first describe the Open-AI style game-simulator interface that can be used by the learning agents. We then briefly describe how some of the simulator functionalities are provided for the domains and future directions this regard.
def get_ get_states
return []
***
@Input None
@output
Returns list (essentially set). consisting of states in the game.
**
10
11 def get_start_statel/
12
return
14 н*.
15 @input
16 None
BOutput
A start state start_$ S denoting the start state for episode.
19
15

---

Under review as a conference paper at ICLR 2021
20
21 def get_actions ()
22
(return [[ [I, OI, 1, (11)
a**
25 @Input
26 None
27
puutput
A list with the first element representing attacker actions and the second element representing defender actions. The first 1ist can further decomposed in to set of lists representing actions for each attacker/follover type.
31 def is_end (8)
32
33 return True/False
Iinut
36
A state 8 S.S.
37
@Output
38 AsserticnError if sgS.
True if the input state end_$ C S
40 False otherwise
41
42
43 def act (8, aA.0A.)).
45
return Ro. 8141
46
47
@Input
A state SE S, defender's action ap, attacker/follower/ action aAr the attacker type 8
49 puutput
50
AsserticnError if 8 & ap (or aa) is not defender (or attackez type
5) action.
Rv Defender's utility
52
RA Attacker's a utility
53
8141 Next state
54
B. MOVING TARGET DEFENSE FOR WEB-APPLICATE
As mentioned earlier, we leverage the fully specified game domain from (6) to build the simulator. In the context of the simulator functions, the get_etet_ttt stttte method returns four states of the system. Each state of the defender constitutes choosing implementation language (Php python) and database technology (SQL or PoLtgreSQL) that can be used to host web-application.
The get_start__tteeeeeeeeeee implying the system can start in any one of the four configurations. We allow a user to override the global variable that describes the set of start states because, in the context of certain baseline strategies such as BSG formulation (6). they consider only a sub-set of the MTD configurations. start find itself
staar_state method of the game simulator returns on of the four states at random,
Thus, strategy that places zero probability of switching configuration in the configuration.
The get_actt_eeoeeeee actt_ctti ions method returns the of actions available the attacker types and the defender. Similar to the original game designed in (6), we pair up an attacker types expertise level and a set of technologies it has expertise to the Common Vulnerabilities and Exploits (CVEs) mined from the NVD database to define their attack set. For the defender, the four configurations it can choose constitute the attack set.
The is_end always returns False in this setting as the game has not terminal state and the goal of the defender to continuously keep moving the system. While we can stop when policy converges for
16

---

Under review as a conference paper at ICLR 2021
state
Dellndderss reaurd
apent
855-0
URS
BERRQ
epteodies
eotsodess.o
Figure 6: Comparing BBS-Q with URS (orange) and EXP-Q learning (green) MTD for web- applications with switching costs incorporated in the transition function of BSMGs.
our proposed BSS-Q algorithm, for the other algorithm, owing to the lack of convergence guarantees, we run it for a predefined number of episodes.
The act method considers the action of the defender and the attacker's actions to determine the impact. Ideally, this can be done by deploying the system on new configuration and then sending out an actual request to the web-service with the attack folder as part of a request. Then, depending on the return, decide the attack was successful or not. While we seek to generate class of attacks that represent the 300+ CVEs used in the domain, this was out of scope for this work. Further, the attack success or failure might only give a binary indication of the rewards fro the attacker, which constitutes sparse signal and treats impactful and trivial attacks under the same umbrella. To address this, we leverage the Common Vulnerability Scoring Service (CVSS) and use the Impact score as the attacker type reward if the chosen attack is expected work the defense configuration being deployed. We use the current state of the system and the defender action to compute the cost of the movement. Ideally, we want determine this by running system with multiple virtual machines- one hosting the current configuration and the other bringing ap). The time taken in bringing up the new configuration and then the amount of packets dropped or the extra resources used in the switching should all be part of the switching costs. While one can come up with an elaborate procedure to do so, this beyond the present scope of our paper and we consider the costs calculated based on configuration-be based similarity (6) configurations that are more dissimilar incur higher switching costs.
the next configuration (determined by
B.1.1 REAL-TIME DECISION BASED ON SWITCHING COST THRESHOLD
We consider different perspective on switching costs that is possible to represent using BSMG but cannot be captured by existing work in (6). In this setting, we do not capture the switching cost as part of the reward metrie, but use it to guide the transition dynamics of the underlying environment. Precisely, when an act API is called, we use the defender's action up to perform the switch. While performing the switch action, if we observe drop in the successful processing of packets or an increase in the response latency, calibrated by a threshold, we abort the move action and stay in the same state. This introduces stochasticity in the underlying environment, which, as per the domain in (6), was initially deterministic. We use the existing switching cost to guide the transition dynamics, i.e. expensive switches have a higher probability of failing to execute the switch and thus, remain in the same state.
Experimental Results In Figure 6, we plot the rewards obtained by the proposed BSS Q-learning agent in comparison to the baselines described in the paper- namely the Uniform Random Strategy (URS) and the adversarial multi-arm bandit based EXP-Q learning agent. We igmore the ttae-aagoottic optimal policy in this setting because it only expects to see itself in two configuration of the system and thus, becomes sub-optimal in this setting given the stochastic nature of the environment (that it cannot even model). We use discount factor of 0.8, exploration rate of 0.15 (that decays gradually to 0.05 and learning rate of 0.06.
Similar to our results in the scenario described in the paper, BSS-Q gathers higher reward, over six trails, than URS. In this setting, it performs better than EXP-Q in three states Sp. S2 and sy (the margin of improvement being significantly better in So and 82).
17

---

Under review as a conference paper at ICLR 2021
Attacker
Admin
1: Exploit-LDAP
Monitor-LDAP
CVE-2016-5199
LDAP
2: Exploit-FTP
3: Exploit-Web
CVE-2015-3308
CVE-2017-5045
Monitor-Wei
4: EXploit-LDAP
FTP
Web
Server
Server
Monitor-FTP
Figure 7: An example cloud system highlighting its network structure, the attacker and defender (admin) agents and the possible attacks and monitoring mechanisms (20).
B.2 MOVING TARGET DEFENSE FOR PLACEMENT OF INTRUSION DETECTION SYSTEMS IN CLOUD NETWORKS
Before describing the design of the simulator, we provide the underlying cloud network, scenario, derived from the modeling in (20), in Figure 7. This scenario, via two transformation steps- first, to an attack graphs and then to Markov Game can be used to build our game simulator. For details of this process, we refer the reader look at (20).
The slssssttttstaaseee method of the game simulator returns the single start state that represents the case where an attacker has user access to the LDAP server on the public facing interface of the network system.
The get_ ons returns the set of attack actions, discovered using vulnerability scanners on the cloud system and a part of the attack graph representation in (20), that are possible for an attacker to execute in a given state of the cloud network system. The action set for the defender indicates the set of Intrusion detection systems they can place and no-op action implying that they may not choose to place an IDS system at all.
The is end returns single state of the BSMG. This state represents the condition where the attacker has administrator access on the file server.
The act method considers the action of the defender and the attacker's actions to determine if the attack action is detected. Ideally, we want to play the defender's 's strategy of placing IDS system and then execute the attack action chosen by the attacker. While this needs entire cloud network setup with Virtual Machines (VMs), we use similar resources used in (20) to determine the utilities and the transition. If the IDS placed is able to detect the exploit, return a reward proportional to the effort required by the attacker in executing the attack action. This, similar to (20), is determined using the exploitability score of the CVE determined from the Common Vulnerability Scoring System (CVSS). If the IDS systems fails to detect the attack, then the attacker has an impact proportional to the base score obtained from CVSS which considers both the impact and the complexity of the attack vector. Futher, the game transitions into new state where the attacker has either escalated privileges on the same VM (or physical server) or gets access to a new VM on the cloud. The defender besides the impact score, which represents the security impact, considers the impact network bandwidth if they deploy a Network Intrusion Detection System (NIDS) and impact on memory or CPU resources if they deploy a Host-based Intrusion Detection System (HIDS). We use the scaling used in (20) to come up with single utility value for the defender.
18


Reviews:
[{"review_id": "mB69N-XeDm6", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "High-level summary:\nThis paper introduces a Bayesian Stackelberg Markov Game (BSMG) model that considers a defender’s uncertainty over attackers’ types when implementing defensive strategies. It also proposes to use a Bayesian Strong Stackelberg Q-learning method to learn defense policies by first simulating an adversary to obtain feedback of an attack and then computing the Bayesian Strong Stackelberg Equilibrium for the BSMG with a solver. In this way, this work relaxes the assumption that the defender knows attackers’ types in existing game-theoretic models for moving target defense.\n\nStrength:\nThis paper proposes a game-theoretic model for MTD that learns adversary types via repeated interactions with a simulated attacker. It introduces a Bayesian Strongly Stackellberg Q-learning method that converges to the Bayesian Strong Stackelberg Equilibrium of the BSMG. Empirical results show that the proposed method has advantages over several baselines, such as static policies (URS) and adaptive policies (e.g., B- EXP-Q and B-Nash-Q).\n\nWeakness:\nThe BSMG model itself is incremental since it does not provide any additional interesting insights other than adding the Bayesian and Stackelberg assumption into a Markov game. Regarding the solution, it is unclear to me why vanilla Q-learning instead of other advanced RL algorithms (say, the sample efficient RL variant STEVE by Beckman et al. 2018) is appropriate in their solution (especially when sample efficiency is important here). In the experiments, while it is helpful to compare BSS-Q with several existing baselines, it is unclear whether the performance of BSS-Q is comparable to the Bayesian Stackelberg Game model when the defender has complete information about the attackers’ types. This comparison will generate insights into to what extend the knowledge of attackers’ types influences the effectiveness and efficiency of the defender’s defense mechanisms.\n\nMinor:\nFigures 2 and 4 (also Figure 6  in the appendix) are barely legible. The fonts are too small.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "lJzqJIE9I15", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper studies the problem of learning how to adapt the defense methods in the domain of cybersecurity. The paper proposes a new model called Bayesian Stackelberg Markov Games (BSMG) to capture the uncertainty of the attacker's types as well as their strategic behaviors. The authors design Bayesian Strong Stackelberg Q-learning that can converge to the optimal movement policy for BSMG. The empirical studies verify the support the theoretical results.\n\nDetailed Comments:\n\nThe empirical results give evidence that the proposed method is effective in practice. However, the reviewer had a hard time to understand the model of BSMGs and how the attackers behave in this model. \n\n1. Given the definition of \\Theta, i.e., the probability distribution of the attackers, it seems that the attacker is freshly drawn for each round according to \\theta_k if the state is s_k, and the distribution is independent of the game history. However, the state transition function \\gamma depends on the attacker's type and action, which is very confusing. If the attacker's type is redrawn in each round, then how should the attackers reason about their strategies for the current round? Are they myopic? But this contradicts with the description of Algorithm 1 in which the Q-value of the attacker's are computed, which implies that the attackers care about the future. Could you clarify on this?\n\n2. Is it necessary to assume that the discounting factor for all attackers are the same? Does the result depend on this assumption?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "OIqDBeexvZ-", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors model a problem of responding to an attacker in a Stackelberg bayesian setting with an MDP. The authors provide a Q-learning-like solution to the problem, its convergence to a Stackelberg equilibrium asymptotically, and some experiments to show the performance of the proposed method.\n\nI think that the pros of this paper are the formal and precise characterization of the analysed problem as an MDP with adversaries, but, in my opinion, this does not constitute enough novelty to be published at ICLR. Moreover, I have some doubts also on the significance of the provided experiments.\n\nThe proof of Proposition 1 is key in the results provided by the paper. I think that its proof should be moved to the main paper and, due to the fact that it is not easy to follow, to be revised to improve readability. Moreover, I would like you to state explicitly the difference in the proof w.r.t. the one present in (48).\n\nThe experimental evidence you provided does is not statistically significant. Even if the expected value of the different states in the settings you tackled is larger for the proposed method, the confidence intervals do not provide enough evidence that the proposed method is performing better than the baseline. This dramatically compromises the strength of the experimental results you provided.\n\nI think that a strong assumption of the proposed framework is the knowledge of the attackers' distributions. Indeed, usually one has only a little information about the behaviour of the attackers. Do you think it is possible to extend what you proposed also to a setting in which the attackers' distribution is unknown?\n\nDo you think it is possible to evaluate also the loss due to lack of information (regret) in your setting?\n\n\nMinor:\nsection 5 -> Section 5\neg. -> e.g.,\nalgorithm 1 -> Algorithm 1\ncan’t -> cannot\n\nYou should proofread the appendix and check it for errors (e.g., \"0 \\geq \\gamma < 1\")\n\n---------------------------------------------------------------------------------------------------------------------\nAfter rebuttals:\nThe authors made put a significant effort to improve the submission, but I am still non convinced by the experimental results they are presenting. For instance, in Figure 4 there is no way of distinguish between BSS and Nash-Q. I suggest you to increment the repetitions of the experiment to highlight the improvement of your method over the literature ones.", "extra_scores": {}, "extra_text": {}}, {"review_id": "9zQhZsTOaf", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#########################\nPAPER SUMMARY\n#########################\n\nThis paper proposes the game-theoretic model of Bayesian Stackelberg Markov Games (BSMGs), a generalization of Markov games, as a formalism for studying Moving Target Defense (MTD) systems, a type of defender-attacker game with applications to cybersecurity. An algorithm for finding the Stackelberg equilibrium in BSMGs, called Bayesian Strong Stackelberg Q-Learning (BSS-Q) is proposed, and an OpenAI Gym-style environment for testing the derived policies in particular MTD settings is introduced, which allows for empirical evaluation of the policies' effectiveness. The paper then shows experimental results supporting the BSS-Q algorithm's success at finding the Strong Stackelberg Equilibrium of BSMGs.\n\n#########################\nSTRONG POINTS\n#########################\n\n- Unifying reinforcement learning with leader-follower games is an interesting direction for research.\n- The introduction of new learning environments for these settings is itself a potentially valuable contribution.\n- The inclusion of the parameters used for the experiments in Section 4 (i.e., discount rate, etc.) aids reproducibility.\n\n#########################\nWEAK POINTS\n#########################\n\n- The lack of code with the submission doesn't allow for independent verification of the experiments, or for examining the learning environments that have been introduced. \n- The sensitivity of the experimental results to choice of parameters is not included. Which choices of parameters mattered and why?\n- The discussion in paragraph 3 of page 5 about solving the Bayesian Stackelberg game is unsatisfying; it appears that BSS-Q can only tractably find a solution when the domain is relatively small. Given that the paper claims that a MILP formulation allows for this to be solved effectively in the test domains, then there should be a more detailed discussion of why the test domains presented here are broadly representative of the types of problems that BSS-Q would be expected to be used for solving.\n- The experimental results are not presented with sufficient clarity (see the \"Questions for Authors\" below).\n    \n#########################\nDECISION RECOMMENDATION\n#########################\n\nI recommend rejecting the paper, because I believe that the contributions are not sufficiently broad as to warrant acceptance. In addition, the experimental results are not described in sufficient detail to give confidence about their significance.\n\n#########################\nQUESTIONS FOR AUTHORS\n#########################\n\n- Can the authors clarify what is meant on page 16, line 1 by \"borrowing the game domain\": which parts of the cited framework does the system presented in this paper reuse and what has been added?\n- What does training of an agent in the system look like? Is learning taking place? It appears, from page 6, line -17, that there is a decay of exploration rate. But what is the training process? Isn't the difficult part of the learning process already handled by the Bayesian Stackelberg game solver?\n- The number of trials used in the experiments is inconsistent. Why are 6 trials used in Figure 2 (MTD for Web Applications) while 10 trials are used in Figure 4 (MTD for IDS Placement)? What exactly is a \"trial\" here - is it a training run, a test run with a trained agent, etc.? If a trial corresponds to a training run, then 100 episodes seems like far too few for agents to learn (at least that is the the case in most other RL domains). \n- For each algorithm, Figures 2 and 4 show very similar rewards across the episodes. Does this mean that no learning is taking place for any of the algorithms? If these are test results (i.e., the agents have been trained using these algorithms), then what did the training process look like?\n- What does the \"time taken by the agents\" (Figure 3) signify?\n- The choice of baselines here seems to be too weak; as the paper says in paragraph 2 of page 7, the poor performance of baselines is expected, since they are not modeling adversaries at all. \n\n#########################\nADDITIONAL FEEDBACK\n#########################\n\nStyle suggestions: \n- In Figure 1, move the numbers in the graphs on the right-hand side to outside the chart when that part of the chart is too small to contain the numbers.\n- Page 13, line -2: The PDF links for Equation 1 and 2 don't appear to be correct; also (1) and (2) are overloaded in this proof, referring both to the conditions for convergence near the top of page 13 and to Equations (1) and (2). This should be clarified for easier reading and for removing ambiguity.\n\nTypographical errors:\n- Page 2, line -4: \"Bayesian Stackelberg Games (22; 6) is\" should be \"Bayesian Stackelberg Games (22; 6) are\"\n- Page 3, line 1: \"extends\" should be \"extend\"\n- Page 3, line 24: a word like \"domains\" is missing after \"physical (22) and cyber-security (6)\"\n- Page 4, line 15: \"can is better\" should be \"is better\"\n- Page 4, lines -5 and -4: \"the goal\" is repeated twice; one of these should be removed\n- Page 7, line -6: \"throws of Nash-Q\" should be rephrased\n- Page 8, line 31: there should be no hyphen in \"multiple followers\"\n- Page 13, line -2: \"Note the\" should be \"Note that\"\n- Page 17, line 9: \"propose\" should be \"proposed\"\n\n#########################\nPOST-REBUTTAL UPDATE\n#########################\n\nThank you to the authors for your detailed responses and for uploading your code. (Minor point: your README assumes that the GNOME desktop environment is being used; you may want to make the instructions platform-independent.) My main concerns about the learning process described in the paper remain. The authors indicate in their response that \"it is difficult to quantify which is the most challenging part of the learning process\". This makes it much more difficult to reason about whether the learning process is primarily about using the Bayesian Stackelberg game solver, and whether the interaction with the environment (given the limited number of trials) provides limited benefit.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new game-theoretic model, Bayesian Stackelberg Markov Game (BSMG), for designing defense strategies while accounting for the defender's uncertainty over attackers' types. The paper also proposes a learning approach, Bayesian Strong Stackelberg Q-learning (BSS-Q), to learn the optimal policy for BSMGs. It is shown that BSS-Q converges to an equilibrium asymptotically. Experimental results are provided to demonstrate the effectiveness of BSS-Q in the context of web application security. Overall this is an interesting approach and an important direction of research. However, the reviewers raised several concerns, and there was a clear consensus that the paper is not yet ready for publication. The specific reasons for rejection include the following: (i) the experimental results are not presented with sufficient clarity, no statistical significance tests are performed, and the choice of baselines is weak; (ii) the contributions are not sufficiently broad, the learning process described in the paper is unclear, and the framework requires a strong assumption of knowing the attackers' distributions. I want to thank the authors for actively engaging with the reviewers during the discussion phase. The reviewers have provided detailed feedback in their reviews, and we hope that the authors can incorporate this feedback when preparing future revisions of the paper.

Decision: Reject