8.4. Defining and Solving the Game

To compute the expected attacker behavior by means of a stochastic game, the procedure is as follows.

Step 1: Identify the Game Elements

The first step is to identify the game elements. From the stochastic model, pick all states in S where the system is vulnerable to intrusions. Each of these states can be viewed as a game element Γ_i in a two-player, zero-sum stochastic game with state set Γ. For example, in Figure 8.6, the gray states V, L, and IS represent states where the system is vulnerable to one or more attack actions. Hence, the set of game elements for this model is Γ = {Γ_V,Γ_L, Γ_IS}. Note that even though the system state space S may be very large, the corresponding set with game elements Γ will often contain only a subset of all the states in S, as the example indicates.

Figure 8.6. State transition model of DNS server with game elements identified.

[View full size image]

Step 2: Construct the Action Sets

The next step is to construct the action sets A and D. Set A consists of all possible attack actions. For all transitions out of the game element states, which represent intrusions, identify the corresponding attack actions. Note that A must also contain an “inaction,” which we will denote by Φ, to represent that an attacker may not take any action at all. We use A_i = {a₁,...,a_m} to refer to the set of actions available in game state i. All actions will not necessarily be available in all states (i.e., A_i ⊆ A, however, A_i ∩Φ = Φ). For instance, in Figure 8.6, the complete action set is A = {a₁,a₂,a₃,Φ}, where A_V = {a₁,Φ}, A_L = {a₂,a₃,Φ}, and A_IS = {a₃,Φ}.

Let π_i be a probability distribution over the action set A_i. In a game theoretic context, π_i = (π_i(a₁),...,π_i(a_m)) is called the attack strategy of Γ_i. Hence, π_i(a_k) ϵ π_i will be the probability that an attacker chooses action a_k when the system is in state i, as previously discussed. One must have 0 ≤ π_i(a_k) ≤ 1, ∀π_i(a_k) ϵ π_i and ϵa_k π_i(a_k) = 1, ∀ Γ_i ϵ Γ. The attack probability vectors π_i will now represent the degree of hostility in the network environment, or equivalently, the aggressiveness of the attackers targeting the system. The smaller the π_i(a_k), the less probability of the particular attack a_k in system state i and, hence, the smaller the corresponding failure rate will be.

Set D consists of all possible defense actions, where D_i = {d₁,...,d_m} is the set of actions available in state i. The system defense strategy of Γ_i is θ_i = (θ_i(d₁),...,θ_i(d_m)). Hence, θ_i(d_k) ϵ θ_i is the probability that an IDS alarm indicating action a_k will be triggered in system state i. As for A_i, also D_i must contain an Φ element, since there may not be any reaction at all from the system. Also 0 ≤ θ_i(d_k) ≤ 1, ∀ θ_i(d_k) ϵ θ_i and ∑_dk θ_i(d_k) = 1, ∀Γ_i ϵ Γ.

A strategy is stationary if, for all states i, the corresponding strategy vector is independent of time. To avoid the mathematical obstacles of dynamic strategies, only stationary attack and defense strategies will be considered in this chapter.

Step 3: Assign the Outcome Values

To model the attacker’s motivation, we make use of the reward and cost concept introduced in Section 8.3. As previously discussed, an outcome of a game element is a possible consequence of a play of the game, as experienced by an attacker. For each game element Γ_i, we assign an outcome value to each attack action and defense action pair (a_k,d_l). These values will be denoted r_kl or c_kl, depending on whether the outcome represents a reward or cost respectively. Since the game is zero-sum, we do not need to assign outcome values for the system; consequently, in our game model an attacker’s gain will be the system’s loss and vice versa.

As an example, the possible outcomes from game element Γ_V in Figure 8.6 are depicted in Figure 8.7. Since an attacker has two actions to choose between, A_V = {a₁,Φ}, and there are two possible response actions, D_V = {d₁,Φ}, there are four possible outcomes from that particular play. It could be argued that since nothing happens if the attacker does not take any action, the outcomes from the action pairs (Φ,d₁) and (Φ,Φ) do not make any sense from an attacker’s point of view. We counter this by pointing out that what we aim to compute from Γ_V is the expected attacker behavior in terms of strategy π_V = (π_V(a₁),π_V(Φ)), which an attacker decides to adopt before the attack. So, if we assign a reward to the action pair (Φ,d₁), it implies that if the attacker decides not to attack the system, no matter what, and that all the attacks will always be detected, then the attacker will experience this outcome as a gain: “It’s good that I didn’t try to attack the system, since I would have been detected if I did.” This will be the case even though the system never gets a chance to actually detect any attack. The same line of reasoning is valid for the (Φ,Φ) outcome.

Step 4: Compute the Transition Probabilities

Given that an attack action is chosen in state i, and that the intrusion is successful and remains undetected, the system may transfer to another state j where the game can continue. The transition probability between game element Γ_i and Γ_j, denoted p_ij(a_k,d_l), can be computed by conditioning on the chosen action a_k and the system response d_l. For example, if the system in Figure 8.6 is in state V and an attacker decides to attack the system, and the action remains undetected, then π_V(a₁|(a₁,Φ)) = 1. It is obtained from the Markov properties of the system that the probability of going from state V to L when an attack takes place becomes:

Equation 8.15

Here, φ_VG, μ_S, and μ_H are the rates of the competing events, which may disturb the attack. Hence, Eq. 8.15 is the probability that the game will continue in state L. Note that one must have p_ij(a_k,d_l) ≥ 0 and , ∀Γ_i ϵ Γ.

Recall that A_i and D_i are the action sets associated with state i. The possible outcomes of each game element Γ_i can now be represented by a |A_i| × |D_i| matrix, which has the form

Equation 8.16

where γ_kl is the total outcome associated with the action pair (a_k,d_l). The entries in Eq. 8.16, representing state i, are of the form

Equation 8.17

for which r_kl ≥ 0 and c_kl ≤ 0. When solving the game, the Γ_j element in Eq. 8.17 must be replaced by a value, as will be explained in the next subsection. The first case in Eq. 8.17 applies if the outcome represents a successful and undetected attack action. The attacker receives an immediate reward r_kl and there is also a possibility of future rewards, since the system may move to another game state. The second case normally applies if an attack action is detected, but can also apply if an attacker resigns even though any of the possible attacks would have been undetected. The attacker receives a cost c_kl. Implicitly, the formulation in Eq. 8.17 means that the game will end if an attack is detected and reacted to, if the attacker resigns, or if the system does not transfer to another game state, which will happen with probability 1 – ∑_jp_ij(a_k,d_l).

Step 5: Solve the Game

The last step is to solve the game. Here, solving means to compute the best strategies for the players who participate in the game. Our model relies on the basic assumption of game theory, which states that a rational player will always try to maximize his or her own reward. For each system state i, which is modeled as a game element Γ_i, we can therefore expect an attacker to behave in accordance with the probability distribution π_i = (π_i(a₁),...,π_i(a_m)) that maximizes E(π_i,θ_i), where:

Equation 8.18

Recall that we use zero-sum game elements to model the interactions between an attacker and the system. This implies that an attacker who does not know the defense strategy θ_i will think of the system as a counterplayer in the game who tries to minimize the attacker’s reward. Hence, the optimal attack strategy of Γ_i, and its corresponding defense strategy, are obtained by solving

Equation 8.19

These strategies will be denoted and , respectively. The value of game element Γ_i, denoted V(i), is defined as the expected outcome when and are used, that is,

Equation 8.20

The purpose of the stochastic game model is to predict the complete set of attack probability vectors to be used in the system rate matrix Q. To find the strategies for all game elements in the stochastic game, one can use Algorithm 8.1, which is based on the Shapley algorithm [29]. The functions Value[Γ_i] and Solve[Γ_i] refer to standard algorithms for solving zero-sum matrix games by linear programming. The former returns the expected value in Eq. 8.20 when an attacker and the system use their optimal strategies, whereas the latter returns the attacker’s optimal strategy itself as resulting from Eq. 8.19. Note that Algorithm 8.1 replaces the game element Γ_j in Eq. 8.17 with its value component V(j) iteratively when solving the stochastic game. For further details on the underlying assumptions and solution of the stochastic game model, the reader is referred to Owen [30, pp. 96–101].

We believe that the optimal attack strategy set will be a good indication of the expected attack probabilities for the vulnerable system states. This is because π* gives a lower bound on the attacker outcome, regardless of the system defense strategy. When following π*, the attacker has no reason to change strategy—the no-regrets property of game theory. This property means that the attacker has maximized his or her expected outcome from the attack, regardless if his or her actions are successful or not. Several experienced researchers indicate that this search for guarantees is a very strong motivation of human behavior. Assuming that the attacker population targeting the system will make rational choices relative to their objectives, their collected behavior will, in the long run, gravitate toward the optimal attack strategy [31].

Algorithm 8.1. Compute Expected Attacker Strategy

Require: (Γ,A,D,γ,p) {a stochastic game}
							Ensure: π* {the optimal attack strategy}
  Initialize the value vector V = {V(i)} arbitrarily
							repeat
							for each game element Γi ϵ Γ do
							for all γkl
								do
							replace all Γj in Eq. 8.16 with V(j)
							end for
							compute the matrix γi(V) = [Γkl],
							end for
							for each game element Γi ϵ Γ do
							update the value vector V(i) ← Value[Γi(V)]
							end for
							until
								V(i) = Value[Γi(V)], ∀Γi ϵ Γ
							for each game element Γi ϵ Γ do
							
							end for
							return the set of equilibrium vectors