# Quantal Response Equilibrium-Based Strategies for Intrusion Detection in WSNs

Authors: Shigen Shen; Keli Hu; Longjun Huang; Hongjie Li; Risheng Han; Qiying Cao
Journal: Mobile Information Systems
 (2015)

---

## Abstract

This paper is to solve the problem stating that applying Intrusion Detection System (IDS) to guarantee security of Wireless Sensor Networks (WSNs) is computationally costly for sensor nodes due to their limited resources. For this aim, we obtain optimal strategies to save IDS agents’ power, through Quantal Response Equilibrium (QRE) that is more realistic than Nash Equilibrium. A stage Intrusion Detection Game (IDG) is formulated to describe interactions between the Attacker and IDS agents. The preference structures of different strategy profiles are analyzed. Upon these structures, the payoff matrix is obtained. As the Attacker and IDS agents interact continually, the stage IDG is extended to a repeated IDG and its payoffs are correspondingly defined. The optimal strategies based on QRE are then obtained. These optimal strategies considering bounded rationality make IDS agents not always be inDefend. Sensor nodes’ power consumed in performing intrusion analyses can thus be saved. Experiment results show  that the probabilities of the actions adopted by the Attacker can be predicted and thus the IDS can respond correspondingly to protect WSNs.


---

## Body

## 1. Introduction

Recently, Wireless Sensor Networks (WSNs) have attracted considerable concerns owing to their broad applications. Typical examples exist in environment monitoring, health monitoring, earthquake monitoring, objects tracking, and so on [1]. One of the major issues that we must face is how to guarantee security of WSNs before they are widely applied. Similar to traditional networks, there are to realize secure WSNs and prevention- and detection-based mechanisms [2–8]. The prevention-based mechanism, which aims to prevent any attack before it occurs, includes cryptography, key management, and authentication. On the contrary, the detection-based mechanism is to identify specifically those compromised nodes after they have broken down the measures taken by the prevention step. This mechanism is generally applied using Intrusion Detection System (IDS) as the second line of defense, while the prevention-based mechanism is referred to as the first line of defense. With an IDS, key data such as intruder identification, intrusion time, and intrusion activity are provided to mitigate and remedy attack influences.Currently, lots of IDSs [9, 10] have been proposed for various WSNs structures to provide an important security mechanism against both insider and outsider attacks. However, applying an IDS to WSNs is challenging since sensor nodes have resources limited in terms of energy, memory, computation, and communication capacities. Generally, different methods including anomaly-, misuse-, and specification-based detection are computationally expensive, which are particularly costly for small sensor nodes. This situation motivates us to seek optimal strategies of intrusion detection to possibly save sensor nodes’ resources.As a formal and mathematical tool that studies competition among involved individuals, game theory has provided us with an efficient method to explore optimal strategies in the field of intrusion detection of WSNs [11–14]. Nevertheless, game-theoretic approaches have a common assumption in which players are completely rational and the solutions to games are based on Nash Equilibrium (NE). In real-world applications, however, all Attackers (a player in game theory) may not be always rational and they do not even care about being detected. Therefore, NE-based solutions are not suitable for such circumstances and we need a more appropriate method to solve Intrusion Detection Games.Nowadays, Quantal Response Equilibrium (QRE) has turned into a popular alternative to the traditional NE in behavior game theory. The QRE model maintains the assumption that individuals have beliefs that are supported in equilibrium by the strategies that players choose, but with the assumption that players make systematic mistakes or deviations in their choices [15]. There are two reasons resulting in the deviation behavior. One is called bounded rationality. The other is that players’ payoffs are influenced by social preference in which subjects appear altruistic or fair or seek to reciprocate fairness or seek to limit inequality in payoffs [15].In this paper, QRE is adopted to seek optimal strategies of saving IDS agents’ power in WSNs. Considering the characteristics of sensor nodes, we construct a stage Intrusion Detection Game to describe interactions between the Attacker (a player) and IDS agents (the other player). The preference structures for the Attacker and IDS agents are defined, which lead to form payoffs of players. As the stage game evolves (the Attacker and IDS agents interact continually), we extend it to a repeated game and define the corresponding payoffs. We further obtain QRE-based strategies to show how the Attacker and IDS agents will select their actions.To the best of our knowledge, this paper is the first work to focus on exploring QRE-based strategies for intrusion detection in WSNs. The main contributions of this paper are summarized as follows:(1)
we formulate a stage Intrusion Detection Game according to Binmore’s method to study strategies of malicious sensor nodes and IDS agents, which is able to reflect interactions between the Attacker and IDS agents as well as their preferences;(2)
we extend the stage Intrusion Detection Game to a repeated Intrusion Detection Game by redefining the corresponding payoffs, which is able to reflect the reality that malicious sensor nodes and IDS agents interact continually;(3)
instead of NE-based strategies, we obtain QRE-based strategies of the Attacker and IDS agents, which satisfies such a situation to the point that the Attacker and IDS agents always make their decisions with bounded rationality;(4)
we realize an implementation of applying the repeated Intrusion Detection Game to WSNs based on the algorithm of calculating QRE-based strategies that can predict the Attacker’s future behavior.The rest of this paper is organized as follows. In Section2, we overview related work to distinguish the difference between our work and other related works. In Section 3, we construct our stage Intrusion Detection Game for WSNs and extend it to a repeated game. Further, we give a method of calculating QRE-based strategies. In Section 4, we implement an intrusion detection mechanism based on QRE-based strategies and give the corresponding algorithm. In Section 5, we perform experiments to show how the repeated Intrusion Detection Game is actually played. Finally, conclusions are provided in Section 6.


## 2. Related Work

IDSs in WSNs have attracted considerable attention. In the good survey, Butun et al. [5] presented detailed information about IDSs and the applicability of IDSs to WSNs, which are followed by the analysis and comparison of each scheme along with their advantages and disadvantages. Al-Hamadi and Chen [16] considered an optimization problem for the case where a voting-based distributed intrusion detection algorithm is employed to detect and isolate malicious nodes in WSNs. They then can dynamically determine the best redundancy level to apply to multipath routing for achieving the case of intrusion tolerance. In another paper [17], they analyzed dynamic redundancy management of integrated intrusion detection and tolerance, which is to maximize the lifetime of homogeneous clustered WSNs. To cope with potential Denial of Service attacks in WSNs, Cho et al. [18] proposed a partially distributed intrusion detection system with low memory and power requirements. In [19], Farooqi et al. proposed a novel intrusion detection mechanism including online prevention and offline detection for securing WSNs from routing attacks. To obtain efficient performance under limited computation resources of sensor nodes, Kim et al. [20] developed a Wu-Manber algorithm-based network intrusion detection system. By integrating system monitoring modules and intrusion detection modules in WSNs, Sun et al. [21] proposed an extended Kalman filter-based mechanism to detect false injected data. They further combine cumulative summation and generalized likelihood ratio to increase detection sensitivity. Shamshirband et al. [22] developed a cooperative-based fuzzy artificial immune system, in which the Cooperative-Decision-Making Module incorporates the danger detector module with the fuzzy Q-learning vaccination module to produce optimum defense strategies for detecting intrusion in WSNs. In addition, Riecker et al. [23] proposed a lightweight, energy-efficient IDS, where mobile agents are used to detect intrusions based on the energy consumption of the sensor nodes.Since selecting the profitable detection strategy is able to lower resources consumption, game theory has been widely applied to obtain these optimal strategies. For example, the optimal strategies of launching IDS agents installed in sensor nodes are obtained by the signaling game in [24]. To determine the best defense strategies, Huang et al. [25] proposed a Markovian IDS incorporating game theory with anomaly and misuse detection, where Markov decision processes are employed with an attack-pattern-mining algorithm to predict future attack patterns. Moosavi and Bui [26] considered non-zero-sum discounted stochastic games to formally formulate and analyze the intrusion detection problem in WSNs. They assumed that the game data are not to be fully known to the players and achieved a robust optimization approach to address this data uncertainty. On the contrary, a zero-sum stochastic game is applied in [27] to predict malicious behavior of Attackers. In [28], Shen et al. formulate a malware-defense differential game, in which the system can dynamically choose its strategies to minimize the overall cost whereas the malware intelligently varies its strategies over time to maximize this cost, to obtain optimal dynamic strategies for the system. In addition, cooperative games are also applied to formulate intrusion detection problem in WSNs. Shamshirband et al. [29] combined the game-theoretic approach and the fuzzy Q-learning algorithm to implement cooperative defense counter-attack scenarios for the sink node and the base station. The game is composed of three players consisting of sink nodes, a base station, and an Attacker and performs when a victim node in WSNs receives a flooding packet as a DDoS attack beyond a specific alarm event threshold. To obtain secure and reliable defenses of virtual sensor services in cloud-assisted WSNs, Liu et al. [30] proposed a stochastic evolutionary coalition game which is able to decide how evolutionary coalitions should be dynamically formed for reliable virtual-sensor-service composites to deliver data and how to adaptively defend in the face of uncertain attack strategies.Among various game types, a repeated game consists of some number of repetitions of a stage game. Such a game is generally divided into two categories: finitely and infinitely repeated game, depending on whether interactions among players are finite or infinite. Players in a repeated game must consider the effects produced by their current chosen strategies on the opponents’ strategies in subsequent rounds [31]. The same stage game, when played repeatedly, may result in different equilibriums. Therefore, each player must take optimal reactions against the opponent, which will affect one’s payoffs in future.Some applications of repeated game have been devoted to various aspects in wireless networks. Agah and Das [32] formulated a repeated game between IDS and sensor nodes to prevent Denial of Service (DoS) attacks in WSNs. Upon their proposed game, a protocol was proposed to category different sensor nodes based on their behavior. In [33], Pandana et al. proposed a self-learning repeated game framework to overcome selfishness and noncooperation of autonomous nodes in wireless ad hoc networks. The framework ensures the cooperation among nodes for the current packet forwarding and finds the better cooperation probabilities by self-learning algorithms. Chen et al. [34] constructed a repeated game model based on reputation for wireless networks to fully utilize the scarce spectrum resource. The model is able to help multiple primary and secondary users coexist and share the spectrum. Using a repeated game to enforce cooperation among nodes in wireless networks, Kong and Kwok [35] proposed an efficient packet-scheduling algorithm that leads to an equilibrium. Upon the algorithm, the wireless channel resources are fully utilized. The other typical cooperation applications of repeated game are composed of cooperative multicast [36], network selection [37], and power trading [38]. In addition, Sagduyu et al. [39] formulated a repeated game under network uncertainty to deal with jamming attacks in wireless networks. A multiattacker repeated colluding game is proposed in [40] to find subgame equilibriums that indicate the optimal strategies of Attackers. Upon these equilibriums, a security policy is established to detect malicious nodes that collude with each other to launch the selective forwarding attacks. Moreover, cognitive radio users, using a repeated game in [41], can adapt their power by observing the interference from the feedback signals of primary users and transmission rates obtained in the previous stage. Zhu and Martínez [42] developed a repeated game to solve the coverage optimization problem of mobile sensors. To defend against multistage attacks, Luo et al. [43] modeled a two-player non-zero-sum noncooperative dynamic multistage game with incomplete information to find the best actions for defenders. Sun et al. [44], considering inherent uncertainty of nodes in ad hoc networks, proposed a power control mechanism with a dynamic repeated game-theoretic framework. Smith et al. [45] proposed a dynamic noncooperative repeated game for transmitting power control across multi-source-destination distributed wireless networks. Recently, the “zero-determinant strategies” [46–50] of a repeated game have attracted much attention in scientific world. In particular, Farraj et al. [48] employed a repeated game-theoretic formulation to describe the interactions of the parties in cyber-enabled power systems. Transient stabilization over time using zero-determinant strategies is obtained to indicate the potential of the constrained controller.Based on the repeated game, QRE developing the concept of NE considers bounded rationality and thus is profitable to describe the dilemma of security source allocation. To fit the bounded rationality of human adversaries in security game, Yang et al. [51] modeled human behavior of adversaries and provided new mathematical models based on prospect theory and stochastic discrete choice model. A modification of QRE is proposed to develop algorithms that are efficient to compute the best response of the security forces when playing against the different adversaries. In [52], QRE is used to capture players’ bounded rationality and to model internal Attackers’ behavior. The results are able to predict how an internal Attacker will act in future. Then, a detailed game-based detection algorithm taking advantage of these results is described in detail.


## 3. Constructing Intrusion Detection Game for WSNs

### 3.1. Network Model

According to classification based on the installation location of IDS agents, there are purely distributed, purely centralized, and distributed-centralized structures [53]. For the purely distributed situation, each sensor node has been equipped with an IDS agent that locally examines malicious actions from neighboring sensor nodes. On the contrary, for the purely centralized situation, the base station (BS) has been equipped with the IDS agent, where a special protocol is necessary to gather information from sensor nodes to examine the behavior of sensor nodes. In addition, for the distributed-centralized situation, monitor sensor nodes are introduced and have been equipped with IDS agents. Not only do these monitor nodes perform activities like normal nodes, but also they check for intrusion detection.Our network model adopts the same one in [24], as depicted in Figure 1. This model belongs to the distributed-centralized case. However, under clustering hierarchy, each sensor node has been equipped with an IDS agent, which is not the same as the situation where IDS agents are only installed in monitor sensor nodes. When an energy-abundant sensor node is elected as a cluster head (CH), the deployed IDS agent will launch simultaneously while the IDS agents in member sensor nodes are in sleep. Therefore, a CH executes the task of intrusion detection by the IDS agent in addition to aggregating and sending data.Figure 1
Network model [24].


### 3.2. Stage Intrusion Detection Game

Definition 1.
The stage Intrusion Detection Game (IDG) is a 3-tupleG=(N,A,U), where(1)
N={Attackeri,IDSagentj} is a set of players;(2)
A=Ai×Aj, where Ai={Cooperate(C),Preattack(P),Attack(A)} and Aj={Sleep(S),Grant(G),Defend(D)} are the sets of actions adopted by players i and j, respectively;(3)
U=Ui×Uj, where Ui={ui(si):Ai↦R} and Uj={uj(sj):Aj↦R} are the sets of payoffs of players i adopting strategy si and j adopting strategy sj, respectively.In Definition1, we consider that the game is played by the Attacker (i) versus the IDS agents (j). Player i is in fact referred to malicious sensor nodes that have such purposes as to listen to sensor information, devastate a sensor node’s communication abilities, or entirely disable a sensor node. On the other hand, player j is referred to IDS agents that are initially installed in CHs. The goal of our Intrusion Detection Game is, from the view of game theory, to supply optimal strategies for IDS agents in response to the Attacker selecting its strategies dynamically.As an Attacker, playeri has three possible actions. It may take the actionCooperate(C), meaning that it acts normally during communications among other sensor nodes. This action disguises it to avoid being captured by its opponent. However, the intentions of player i are hostile, and therefore its aim is to systematically arrange methods so that it can attack other sensor nodes for its own profits. Generally, it might disclose private information of other sensor nodes for obtaining other information required for it to finish an attack. These actions are known as reconnaissance attacks and can be summarized as the actionPreattack(P). Moreover, an Attacker finally achieve the phase in which the actionAttack(A) is made to obtain its expected profit. This action is without doubt the most threatening action among all. It raises and strengthens the seriousness of the problem and leads to many unexpected results such as a network unavailable for its legitimate sensor nodes, inaccurate sensing information, and leaking private data. In summary, the set of actions of player i is {C,P,A}.To confront Attackers, playerj also has three actions. Due to limited resources in sensor nodes, the strategy that IDS agents are always inDefend is not optimal. Otherwise, cluster heads installed IDS agents will consume their power quickly since processing intrusion detection is generally costly. Player j may therefore take the actionSleep(S) for saving energy. After launching IDS agents, it may grant sensor nodes to continue when no malicious behavior has been discovered. Note that two cases result in the fact that player j takes this actionGrant(G). One case is that the Monitored Events are truly normal. The other is that IDS agents cannot detect the malicious events since any IDS has the false negative rate. In addition, player j will take the actionDefend(D) to stop the work of malicious sensor nodes once violations are detected. In a summary, the set of actions of player j is {S,G,D}.Based on the above analyses, there are nine possible combinations between the Attacker’s actions and the IDS agent’s actions. For example, strategy profile(C,S) means that player i acts normally and player j is in sleep for saving energy. (P,G) means that player i acts in a preattack step and player j grants its opponent to continue for not detecting reconnaissance attacks. (A,D) means that player i performs attacking behavior and player j prevents its opponent from its malicious work to protect sensor nodes.Finally, let us quantify preferences and payoffs of players in the stage IDG. Let the symbols≻ and ~ be the preference and indifference, respectively. For example, if x≻y, then it is said that x is preferred to y.For the player Attacker, it is most profitable to attack successfully the WSNs without being defended. Since the IDS agents taking the actionSleep orGrant cannot defend the Attacker, the preference of strategy profile (A,G) is indifferent to that of (A,S). Its next choice is to take the actionCooperate without being defended. The following preference action isPreattack without any deterrence. The actionAttack that is defended follows the Attacker’s favorite, which is more preferable than the actionCooperate that is defended. Finally, the worst choice is the actionPreattack responded by the actionDefend. The above analyses result in the following preference structure:(1)A,S~A,G≻C,S~C,G≻P,S~P,G≻A,D≻C,D≻P,D.With respect to the player IDS agents, the most preferable profile is the actionCooperate followed by the actionSleep. The following is the actionCooperate followed by the actionGrant since taking the actionGrant spends more power for detection than takingSleep. When it takes the actionDefend, it prefers orderly the actionsAttack,Preattack, andCooperate. It next prefers the actionPreattack followed orderly by the actionsSleep andGrant. The least preferable profile is the actionAttack followed by the actionGrant. Therefore, the preference structure attained is(2)C,S≻C,G≻A,D≻P,D≻C,D≻P,S≻P,G≻A,S≻A,G.According to Binmore’s method [54], rational numbers are assigned to reflect players’ preferences ranked in (1) and (2). Then, after being multiplied with their least common factor, the values of payoff functions ui and uj, free of fractions, can be formed in Table 1.Table 1
Payoff matrix.
S
G
D
C
(6, 8)
(6, 7)
(1, 4)
P
(4, 3)
(4, 2)
(0, 5)
A
(8, 1)
(8, 0)
(2, 6)


### 3.3. Repeated Intrusion Detection Game

In the realistic WSNs, interactions between players Attacker and IDS agents are continually performed. Therefore, the stage IDG will be played more than once and it is reasonable to model these interactions as a repeated game. Generally, a repeated game is a particular style of an extensive form game in which each stage is a repetition of the same strategic-form game. The times of playing a repeated game may be finite or infinite. If the game never ends (Attacker and IDS agent interact forever) or players (Attacker and IDS agent) do not know when the game ends, it is called an infinitely repeated game, which will be employed in this paper. In a repeated game, a strategy is an entire plan of action described in the stage game. When each stage ends, all players are able to observe the consequence of the stage game and make a choice to select the future actions depending on the history of actions. The overall payoff in a repeated game is denoted by a normalized discounted aggregate of the payoff at each stage game. Our repeated Intrusion Detection Game (RIDG) can be defined as follows.Definition 2.
The infiniteδ-discounted RIDG is composed of repeated game G, which is denoted by G(∞,δ), where(1)
the set of players isN defined in Definition 1;(2)
for every playerx∈{i,j}, its overall strategy at the tth stage IDG is sxt=[sx(h0),sx(h1),…,sx(ht)], where hy, y∈{0,1,…,t}, denotes the yth history stage and sx(hy) denotes the strategy adopted by player x at the yth history stage;(3)
for every playerx∈{i,j}, its overall payoff is the δ-discounted average of instant payoffs from each round of the repeated Intrusion Detection Game.Figure2 shows a representation of the RIDG in extensive form. In fact, an Attacker is perfectly aware of IDS agents’ past actions because IDS agents exert actions on the Attacker. In other words, player j’s (IDS agents’) actions are perfectly known by player i (Attacker). On the other hand, player j is imperfectly aware of player i’s past choices because player j judges its opponent’s actions with uncertainty. Consequently, the RIDG belongs to a repeated dynamic game with imperfect information.Figure 2
Repeated Intrusion Detection Game.From Figure2, player i first takes an action at the beginning node. It may select actionCooperate,Preattack, orAttack. Next, player j responds to its opponent with actionSleep,Grant, orDefend. As soon as it selects actionDefend, the game ends. Except for this case, the game will be played repeatedly.Now, let us define players’ payoffs for the repeated IDG. Players Attacker and IDS agents strive to maximize their expected payoffs over multiple rounds of the stage IDG. The expected payoff is generally described as a sum of per-period payoffs, multiplied by a discount factorδ, δ∈[0,1). If the discount factor is not too high, the players then are interested enough in future outcomes of the game. Both players therefore put more weight on the current payoff than on the future payoffs. The total payoff for player x, x∈{i,j}, is given as(3)uxtsx=∑y=0tδyuxysx,where uxy(sx) denotes the payoff obtained by player x, x∈{i,j}, adopting strategy sx at slot time, y, y=0,1,2,…,t. Further, in the repeated game with infinite rounds, the total payoff in (3) is often averaged. Therefore, the average discounted payoff for player x, x∈{i,j}, can be expressed as(4)u-xtsx=1-δ∑y=1tδyuxysx.Next let us analyze the total number of strategy profiles in our RIDG. Generally, as an infinitely repeated game, the total number of strategy profiles at thetth stage is computed by multiplying the number of history strategy profiles at all stages 0, 1, …, t-1, with the number of actions to be played at the tth stage. However, in our RIDG, the actionDefend adopted by player j means that the game ends. In this sense, the number of combined actions excluding the terminal actionDefend is 3×2=6. Therefore, the total number of strategy profiles at the tth stage, nt, can be computed as(5)nt=6×nt-1,t=1,2,3,…,where n0=9.From (5), we can see that the total number of strategy profiles of our RIDG will increase quickly as the number of all repeated stage IDGs grows. As a result, complexity to predict the future behavior of player i by computing the NE of a subgame becomes higher and higher, which motivates us to find an optimal alternative, QRE.


### 3.4. QRE-Based Strategies

QRE for extensive form games is first defined by McKelvey and Palfrey [55], which provides an equilibrium notion with bounded rationality. QRE is not an equilibrium refinement, and it can obtain significantly different results from NE. It is only defined for games with separate strategies, regardless of the fact that there are repeated-strategy analogues. In particular, it is developed as a probabilistic extension of NE and can be used to give reasons why players might systematically deviate from the NE path. This is because players in QRE are assumed to make errors in selecting which strategy to play. The probability of any particular strategy being picked is positively related to the highest expected payoff from that strategy. Therefore, strategy choices in QRE are probabilistic rather than deterministic.The characteristic that QRE provides equilibrium with bounded rationality is realized by introducing a rationality parameter to the payoff. The rationality parameter denoted byλ is changed during the process of QRE converging to the NE. When λ=0, players are completely irrational. This case means that even though a player cannot obtain greater payoff, players Attacker and IDS agents will select another strategy other than the one indicated by NE. On the contrary, when λ→∞, players will follow NE since they become completely rational in this case. So far, the QRE can be calculated by(6)πsxt=exp⁡λ·u-xtsx∑y∈Axexp⁡λ·u-xty,where πsxt is in fact the probability of player x, x∈{i,j}, selecting strategy sx. From (6), QRE-based strategies of players Attacker and IDS agents can be obtained, respectively. In essence, QRE-based strategies are based on the introduction of payoff perturbations associated with actions adopted by players Attacker and IDS agents. The probability of a strategy profile is positively related to the average discounted payoffs held by players. The set of QRE can be regarded as a correspondence mapping the rationality parameter λ into a set of mixed strategy (the probability that each action of IDS agents will be selected by IDS agents) in A.


## 3.1. Network Model

According to classification based on the installation location of IDS agents, there are purely distributed, purely centralized, and distributed-centralized structures [53]. For the purely distributed situation, each sensor node has been equipped with an IDS agent that locally examines malicious actions from neighboring sensor nodes. On the contrary, for the purely centralized situation, the base station (BS) has been equipped with the IDS agent, where a special protocol is necessary to gather information from sensor nodes to examine the behavior of sensor nodes. In addition, for the distributed-centralized situation, monitor sensor nodes are introduced and have been equipped with IDS agents. Not only do these monitor nodes perform activities like normal nodes, but also they check for intrusion detection.Our network model adopts the same one in [24], as depicted in Figure 1. This model belongs to the distributed-centralized case. However, under clustering hierarchy, each sensor node has been equipped with an IDS agent, which is not the same as the situation where IDS agents are only installed in monitor sensor nodes. When an energy-abundant sensor node is elected as a cluster head (CH), the deployed IDS agent will launch simultaneously while the IDS agents in member sensor nodes are in sleep. Therefore, a CH executes the task of intrusion detection by the IDS agent in addition to aggregating and sending data.Figure 1
Network model [24].


## 3.2. Stage Intrusion Detection Game

Definition 1.
The stage Intrusion Detection Game (IDG) is a 3-tupleG=(N,A,U), where(1)
N={Attackeri,IDSagentj} is a set of players;(2)
A=Ai×Aj, where Ai={Cooperate(C),Preattack(P),Attack(A)} and Aj={Sleep(S),Grant(G),Defend(D)} are the sets of actions adopted by players i and j, respectively;(3)
U=Ui×Uj, where Ui={ui(si):Ai↦R} and Uj={uj(sj):Aj↦R} are the sets of payoffs of players i adopting strategy si and j adopting strategy sj, respectively.In Definition1, we consider that the game is played by the Attacker (i) versus the IDS agents (j). Player i is in fact referred to malicious sensor nodes that have such purposes as to listen to sensor information, devastate a sensor node’s communication abilities, or entirely disable a sensor node. On the other hand, player j is referred to IDS agents that are initially installed in CHs. The goal of our Intrusion Detection Game is, from the view of game theory, to supply optimal strategies for IDS agents in response to the Attacker selecting its strategies dynamically.As an Attacker, playeri has three possible actions. It may take the actionCooperate(C), meaning that it acts normally during communications among other sensor nodes. This action disguises it to avoid being captured by its opponent. However, the intentions of player i are hostile, and therefore its aim is to systematically arrange methods so that it can attack other sensor nodes for its own profits. Generally, it might disclose private information of other sensor nodes for obtaining other information required for it to finish an attack. These actions are known as reconnaissance attacks and can be summarized as the actionPreattack(P). Moreover, an Attacker finally achieve the phase in which the actionAttack(A) is made to obtain its expected profit. This action is without doubt the most threatening action among all. It raises and strengthens the seriousness of the problem and leads to many unexpected results such as a network unavailable for its legitimate sensor nodes, inaccurate sensing information, and leaking private data. In summary, the set of actions of player i is {C,P,A}.To confront Attackers, playerj also has three actions. Due to limited resources in sensor nodes, the strategy that IDS agents are always inDefend is not optimal. Otherwise, cluster heads installed IDS agents will consume their power quickly since processing intrusion detection is generally costly. Player j may therefore take the actionSleep(S) for saving energy. After launching IDS agents, it may grant sensor nodes to continue when no malicious behavior has been discovered. Note that two cases result in the fact that player j takes this actionGrant(G). One case is that the Monitored Events are truly normal. The other is that IDS agents cannot detect the malicious events since any IDS has the false negative rate. In addition, player j will take the actionDefend(D) to stop the work of malicious sensor nodes once violations are detected. In a summary, the set of actions of player j is {S,G,D}.Based on the above analyses, there are nine possible combinations between the Attacker’s actions and the IDS agent’s actions. For example, strategy profile(C,S) means that player i acts normally and player j is in sleep for saving energy. (P,G) means that player i acts in a preattack step and player j grants its opponent to continue for not detecting reconnaissance attacks. (A,D) means that player i performs attacking behavior and player j prevents its opponent from its malicious work to protect sensor nodes.Finally, let us quantify preferences and payoffs of players in the stage IDG. Let the symbols≻ and ~ be the preference and indifference, respectively. For example, if x≻y, then it is said that x is preferred to y.For the player Attacker, it is most profitable to attack successfully the WSNs without being defended. Since the IDS agents taking the actionSleep orGrant cannot defend the Attacker, the preference of strategy profile (A,G) is indifferent to that of (A,S). Its next choice is to take the actionCooperate without being defended. The following preference action isPreattack without any deterrence. The actionAttack that is defended follows the Attacker’s favorite, which is more preferable than the actionCooperate that is defended. Finally, the worst choice is the actionPreattack responded by the actionDefend. The above analyses result in the following preference structure:(1)A,S~A,G≻C,S~C,G≻P,S~P,G≻A,D≻C,D≻P,D.With respect to the player IDS agents, the most preferable profile is the actionCooperate followed by the actionSleep. The following is the actionCooperate followed by the actionGrant since taking the actionGrant spends more power for detection than takingSleep. When it takes the actionDefend, it prefers orderly the actionsAttack,Preattack, andCooperate. It next prefers the actionPreattack followed orderly by the actionsSleep andGrant. The least preferable profile is the actionAttack followed by the actionGrant. Therefore, the preference structure attained is(2)C,S≻C,G≻A,D≻P,D≻C,D≻P,S≻P,G≻A,S≻A,G.According to Binmore’s method [54], rational numbers are assigned to reflect players’ preferences ranked in (1) and (2). Then, after being multiplied with their least common factor, the values of payoff functions ui and uj, free of fractions, can be formed in Table 1.Table 1
Payoff matrix.
S
G
D
C
(6, 8)
(6, 7)
(1, 4)
P
(4, 3)
(4, 2)
(0, 5)
A
(8, 1)
(8, 0)
(2, 6)


## 3.3. Repeated Intrusion Detection Game

In the realistic WSNs, interactions between players Attacker and IDS agents are continually performed. Therefore, the stage IDG will be played more than once and it is reasonable to model these interactions as a repeated game. Generally, a repeated game is a particular style of an extensive form game in which each stage is a repetition of the same strategic-form game. The times of playing a repeated game may be finite or infinite. If the game never ends (Attacker and IDS agent interact forever) or players (Attacker and IDS agent) do not know when the game ends, it is called an infinitely repeated game, which will be employed in this paper. In a repeated game, a strategy is an entire plan of action described in the stage game. When each stage ends, all players are able to observe the consequence of the stage game and make a choice to select the future actions depending on the history of actions. The overall payoff in a repeated game is denoted by a normalized discounted aggregate of the payoff at each stage game. Our repeated Intrusion Detection Game (RIDG) can be defined as follows.Definition 2.
The infiniteδ-discounted RIDG is composed of repeated game G, which is denoted by G(∞,δ), where(1)
the set of players isN defined in Definition 1;(2)
for every playerx∈{i,j}, its overall strategy at the tth stage IDG is sxt=[sx(h0),sx(h1),…,sx(ht)], where hy, y∈{0,1,…,t}, denotes the yth history stage and sx(hy) denotes the strategy adopted by player x at the yth history stage;(3)
for every playerx∈{i,j}, its overall payoff is the δ-discounted average of instant payoffs from each round of the repeated Intrusion Detection Game.Figure2 shows a representation of the RIDG in extensive form. In fact, an Attacker is perfectly aware of IDS agents’ past actions because IDS agents exert actions on the Attacker. In other words, player j’s (IDS agents’) actions are perfectly known by player i (Attacker). On the other hand, player j is imperfectly aware of player i’s past choices because player j judges its opponent’s actions with uncertainty. Consequently, the RIDG belongs to a repeated dynamic game with imperfect information.Figure 2
Repeated Intrusion Detection Game.From Figure2, player i first takes an action at the beginning node. It may select actionCooperate,Preattack, orAttack. Next, player j responds to its opponent with actionSleep,Grant, orDefend. As soon as it selects actionDefend, the game ends. Except for this case, the game will be played repeatedly.Now, let us define players’ payoffs for the repeated IDG. Players Attacker and IDS agents strive to maximize their expected payoffs over multiple rounds of the stage IDG. The expected payoff is generally described as a sum of per-period payoffs, multiplied by a discount factorδ, δ∈[0,1). If the discount factor is not too high, the players then are interested enough in future outcomes of the game. Both players therefore put more weight on the current payoff than on the future payoffs. The total payoff for player x, x∈{i,j}, is given as(3)uxtsx=∑y=0tδyuxysx,where uxy(sx) denotes the payoff obtained by player x, x∈{i,j}, adopting strategy sx at slot time, y, y=0,1,2,…,t. Further, in the repeated game with infinite rounds, the total payoff in (3) is often averaged. Therefore, the average discounted payoff for player x, x∈{i,j}, can be expressed as(4)u-xtsx=1-δ∑y=1tδyuxysx.Next let us analyze the total number of strategy profiles in our RIDG. Generally, as an infinitely repeated game, the total number of strategy profiles at thetth stage is computed by multiplying the number of history strategy profiles at all stages 0, 1, …, t-1, with the number of actions to be played at the tth stage. However, in our RIDG, the actionDefend adopted by player j means that the game ends. In this sense, the number of combined actions excluding the terminal actionDefend is 3×2=6. Therefore, the total number of strategy profiles at the tth stage, nt, can be computed as(5)nt=6×nt-1,t=1,2,3,…,where n0=9.From (5), we can see that the total number of strategy profiles of our RIDG will increase quickly as the number of all repeated stage IDGs grows. As a result, complexity to predict the future behavior of player i by computing the NE of a subgame becomes higher and higher, which motivates us to find an optimal alternative, QRE.


## 3.4. QRE-Based Strategies

QRE for extensive form games is first defined by McKelvey and Palfrey [55], which provides an equilibrium notion with bounded rationality. QRE is not an equilibrium refinement, and it can obtain significantly different results from NE. It is only defined for games with separate strategies, regardless of the fact that there are repeated-strategy analogues. In particular, it is developed as a probabilistic extension of NE and can be used to give reasons why players might systematically deviate from the NE path. This is because players in QRE are assumed to make errors in selecting which strategy to play. The probability of any particular strategy being picked is positively related to the highest expected payoff from that strategy. Therefore, strategy choices in QRE are probabilistic rather than deterministic.The characteristic that QRE provides equilibrium with bounded rationality is realized by introducing a rationality parameter to the payoff. The rationality parameter denoted byλ is changed during the process of QRE converging to the NE. When λ=0, players are completely irrational. This case means that even though a player cannot obtain greater payoff, players Attacker and IDS agents will select another strategy other than the one indicated by NE. On the contrary, when λ→∞, players will follow NE since they become completely rational in this case. So far, the QRE can be calculated by(6)πsxt=exp⁡λ·u-xtsx∑y∈Axexp⁡λ·u-xty,where πsxt is in fact the probability of player x, x∈{i,j}, selecting strategy sx. From (6), QRE-based strategies of players Attacker and IDS agents can be obtained, respectively. In essence, QRE-based strategies are based on the introduction of payoff perturbations associated with actions adopted by players Attacker and IDS agents. The probability of a strategy profile is positively related to the average discounted payoffs held by players. The set of QRE can be regarded as a correspondence mapping the rationality parameter λ into a set of mixed strategy (the probability that each action of IDS agents will be selected by IDS agents) in A.


## 4. QRE-Based Intrusion Detection for WSNs

As given in Figure3, we realize an implementation of applying our RIDG to WSNs. The data flow begins with member sensor nodes that are being monitored by the IDS agents installed in the corresponding CH. These member sensor nodes may be normal or malicious, so they take possible actions includingCooperate,Preattack, andAttack. As soon as the IDS agent is woken by events of member sensor nodes, it filters the Monitored Events and employs an IDS engine to judge whether an event is normal or not.Figure 3
Implementation of applying our RIDG to WSNs.Generally, IDS agents have been previously configured to make them more accurate and reliable, through Configuration Data sent byAdministrator. Upon completion of events detection, the relevant results will be temporarily stored for the final decision. On the other hand, the IDS agent starts to initialize game parameters required in Definition 2. It accepts the results of events detection and formulates the RIDG. When the RIDG is constructed at the first stage, preferences and payoffs of two players, which have been stored in theStored Game Data, are manually set byAdministrator. The IDS agent then, employing (6), calculates the QRE probabilities with the events detection results and the stage RIDG. The QRE probabilities attained will be combined with the IDS results, and this combination will be sent to Administrator who may take Control Actions on member sensor nodes through the IDS agent. After one round of RIDG is played, the game parameters will be updated to theStored Game Data. In particular, the payoffs of two players are adjusted according to (4), which will be used in the next stage RIDG. The above process will then be repeated until the IDS agent selects actionDefend. In fact, reaching this point means the end of interactions between players Attacker and IDS agents. Next, we describe the algorithm for the process of QRE-based intrusion detection (Algorithm 1).Algorithm 1:QRE-based intrusion detection algorithm for IDS agents.
(1)t←1;
(2)Initialize game parameters required in Definition 2;
(3)Do UNTIL the end of interactions between players Attacker and the corresponding IDS agent
(4)Woken by Monitored Events;
(5)Judge whether Monitored Events are normal or malicious with the known intrusion detection techniques;
(6)IF the output of detection is malicious THEN
(7)  IF the RIDG is not existed THEN
(8)   Construct the first stage RIDG with game parameters including N, A, and U;
(9)  ELSE
(10)    Obtain the current stage RIDG from theStored Game Data;
(11)     ENDIF
(12)   Computeπsxt according to (6);
(13)   Computeu-xt(sx) according to (4) and store it into the Stored Game Data for the next stage RIDG;
(14)   Combine IDS results andπsxt, and send them to Administrator;
(15)ENDIF
(16)t←t+1;
(17) ENDDO


## 5. Experiments

With Gambit [56], QRE-based strategies are calculated to show us how the RIDG is actually played, as illustrated in Table 2 and Figures 4 and 5. These illustrations show that we are able to predict the Attacker’s actions, so that the corresponding IDS agent can adopt the appropriate action in advance. Calculations begin with equal probabilities for each action. In this manner, every action has a probability of 0.3333 or so, since there are three actions for each player. In addition, the rationality parameter λ starts with λ=0 at step 1.Table 2
QRE calculations for the players Attacker and IDS agents in the RIDG.
Step
λ
Attacker
IDS agents
Cooperate
Preattack
Attack
Sleep
Grant
Defend
1
0
0.333333
0.333333
0.333333
0.333333
0.333333
0.333333
2
0.010248
0.333301
0.327668
0.339031
0.333302
0.329903
0.336795
3
0.021502
0.333192
0.321514
0.345294
0.333192
0.326104
0.340703
4
0.033854
0.332985
0.314843
0.352172
0.332978
0.321894
0.345128
5
0.047402
0.332655
0.307631
0.359715
0.332625
0.317226
0.35015
6
0.062251
0.332172
0.299857
0.367971
0.332088
0.312046
0.355866
7
0.078512
0.331504
0.291508
0.376987
0.331314
0.306297
0.36239
8
0.0963
0.330612
0.28258
0.386808
0.330231
0.299913
0.369856
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
47
3.238326
0.0376928
0.00147867
0.960829
2.83
E
-
07
1.11
E
-
08
1
48
3.502404
0.0292182
0.000880193
0.969902
6.29
E
-
08
1.89
E
-
09
1
49
3.797081
0.021933
0.000492093
0.977575
1.21
E
-
08
2.71
E
-
10
1
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
89
161.049147
1.14
E
-
70
1.30
E
-
140
1
0
0
1
90
177.142263
1.17
E
-
77
1.37
E
-
154
1
0
0
1
91
194.844691
2.40
E
-
85
5.76
E
-
170
1
0
0
1
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
104
672.367387
9.88
E
-
293
0
1
0
0
1
105
739.592327
6.27463
E
-
322
0
1
0
0
1
106
813.539761
0
0
1
0
0
1Figure 4
QRE-based strategies for the player Attacker.Figure 5
QRE-based strategies for the player IDS agents.The trend of actions adopted by the Attacker is shown in Figure4, where y-axis represents the probability the Attacker will select a certain strategy for a given λ. It is remarkable that the probability of the Attacker adopting the actionCooperate orPreattack is gradually decreasing while the probability of the actionAttack is increasing. From Table 2, when λ≈3.238326, the probability of the actionPreattack becomes zero approximately. This case means the actionPreattack has been eliminated from this step. Adapting the Attacker’s strategies continually, it is λ≈161.049147, when the selection by the Attacker of the actionAttack becomes certain. This means that if λ is greater than 161.049147, then the Attacker always selects the actionAttack that is in fact the NE of the stage IDG.Figure5 shows the trend of actions adopted by IDS agents, where the probability of the actionSleep orGrant is decreasing and the probability of the actionDefend is increasing. However, compared to the changeable trend of the selection by the Attacker, the action adopted by the IDS agents converges quickly to the actionDefend that is the NE of the stage IDG. This point, from Table 2, is obtained when λ≈3.238326 for the IDS agents while λ is 161.049147 or so for the Attacker.


## 6. Conclusion

To save sensor nodes’ power, we have put forward a method based on QRE to make IDS agents not always be inDefend. A stage IDG that is able to reflect interactions between the Attacker and IDS agents has been formulated, where we have thoroughly considered players’ preferences and have assigned payoffs of players according to Binmore’s method. To reflect the reality that the Attacker and IDS agents interact continually, we have extended the stage IDG to a repeated IDG and have defined the corresponding payoffs. Further, we have given the method of calculating QRE-based strategies that predict the Attacker’s future behavior. As a result, optimal reactions can be suggested to the IDS agents to protect WSNs.In the future, to extend the current game model RIDG when taking into account multiple Attackers that may collude is an interesting work.



---

*Source: 179839-2015-08-09.xml*