Coexistence with malicious and selfish nodes in wireless ad hoc networks: A Bayesian game approach

Abstract

Mobile ad hoc networks are self-organized systems of nodes or installations, all cooperating to provide network functions such as routing and forwarding. Utilized in open environments, mobile ad hoc networks are vulnerable to attack by malicious nodes, causing harm or disorder. These nodes do not reveal their identities while disrupting service. Thus, early detection is important. The network may also contain selfish nodes, installations that choose to conserve power resources rather than provide network function. Identification of selfish nodes, too, is necessary so that functional nodes do not waste resources attempting to communicate with them. In this article, malicious and selfish node detection is modeled as a Bayesian game with imperfect information. In this attacker/defender game, the defender is unsure of the type of its opponent and must select strategies based on this incomplete information. Malicious nodes attempt to avoid detection by masquerading as regular nodes, providing useful network function at interval. This contribution to the network may, however, be entirely necessary in a mobile ad hoc environment with extremely limited resources and selfish nodes. In this article, we propose a more robust model than previous works that is capable of identifying any type of installation found in a mobile ad hoc environment. We demonstrate that selfish and malicious nodes can be successfully identified through our proposed attacker/defender game. In addition, we show that once identified, a malicious node may be exploited if the benefit it provides to the network is greater than the damage accrued. We evaluate our model using simulations. Our simulations show that our proposed model is beneficial because it improves network performance while conserving power resources.

Keywords

Ad hoc networks mobile ad hoc networks game theory Baysian game theory security of mobile ad hoc networks selfish and malicious nodes

Introduction

Mobile ad hoc networks (MANETs) are self-organized systems in which network operation is provided through collaboration of nodes within a neighborhood. Each node agrees to perform network functions such as routing and forwarding with other nodes in the network, without prior trust. Typically, all nodes are programmed to maximize a particular utility function by choosing strategies to maximize a payoff. Usually, a node's utility function is the benefit that node derives from other nodes in the network. That is, providing useful and efficient communication between nodes is any individual node's utmost priority. There may, however, be nodes in the network with other utility functions. A selfish node may choose not to forward packets as a means to conserving power. This node's utility function would then be to minimize its power usage. This would degrade network throughput, make routing almost impossible, or in the worst case immobilize the network as a whole. It is important to note that selfish nodes may only choose to communicate with a certain probability, based on the node's current power constraints. They do not necessarily always decline communication. It is possible that there exist some nodes in the network whose utility function is to maximize harm and disorder to the network. These nodes, called malicious nodes, can mount attacks that compromise individual nodes or degrade the overall network performance. All the while, they avoid being caught and isolated. Malicious nodes do not reveal their identities, but rather try to conceal them, masquerading as traditional nodes.

To counter malicious nodes and promote proper network activity, there must be nodes that monitor and evaluate their neighbors. Nevertheless, detection and differentiation between types of nodes has challenges. First, monitoring neighboring nodes is expensive. Monitoring entails a node listen to the channel and process the information sent by nodes under suspicion. This consumes both processing and reserve power, thus continuous monitoring is impractical. To improve monitoring efficiency, a game theory-based approach is suggested. Given the current state of the channel of communication, games would determine whether a node should monitor or not monitor the channel. Second, malicious nodes can disguise themselves. To reduce the likelihood of being detected, a malicious node can behave like a regular node and attack the network only when it believes it is not being monitored. Moreover, malicious nodes have the additional strategy of fleeing to avoid isolation. That way the node can return to its malicious behavior with a new location and clean history in the network. This strategy is referred to as “Hit and Run” and comes with its own associated cost.¹ That is, the energy spent to change locations. Third, the randomness and unreliability of the wireless channel will inflate the uncertainty of the monitoring and detection process. In some cases it is nearly impossible to determine whether a packet was dropped as a result of wireless error or malicious intent.

In any case, detection is not our ultimate goal. We must next determine how to respond to malicious and selfish nodes. In most cases, a malicious node is isolated upon detection. However, there may be situations in which the malicious nodes can be kept in the network and made use of, coexistence. We rely on the fact that a malicious node does not know if it has been identified or not. Hence, the node will continue to provide useful network function under the assumption that it is avoiding detection. Thus we can exploit the node to improve network throughput as long as the benefits to the network outweigh the damage. In a network with limited resources, the involuntary benefit that malicious nodes provide can be substantial and necessary. These networks have limited numbers of nodes and possibly many selfish nodes, unwilling to cooperate. However, this gives monitoring nodes the additional task to determining when to terminate its coexistence and isolate the opposing node. A malicious node is isolated and banned from the network when the damage it inflicts on the network outweigh the involuntary benefit it provides. A selfish node will be banned when the likelihood that it will participate in network activity drops below a particular threshold.

We model the interactions between nodes as an attacker/defender game of incomplete information. The defender, or monitoring node, attempts to glean the type of the attacker: selfish or malicious based only on its actions. Game theory approaches are taken to select strategies for the defending node based on its current belief of the type of its opponent. Unlike previous work, we consider the attacking player to be of either malicious or selfish type. Others such as Liu et al.² and Wang et al.³ differentiate between nodes of malicious or regular type. They define regular nodes as nodes that always choose to participate. We believe that our model is more robust as our definition of selfish nodes can include nodes that always participate, as well as nodes that participate only a portion of the time. Other researchers consider only opponents which are either selfish or not.^2–6,7,8 We show that monitoring nodes are able to accurately distinguish between selfish and malicious types of nodes and respond accordingly. In addition, nodes are evaluated to decide whether they should be included in the network or banned from all activities. Our static model and some preliminary results have appeared in the study by Roles and ElAarag.⁹

The rest of the article is organized as follows. In the section Related works, we discuss recent research in this area of work. The section Game model introduces our proposed Bayesian game of detection. In the section Bayesian Nash equilibrium analysis, we derive a Bayesian Nash equilibrium (BNE) from our detection game. The section Belief update and dynamic Bayesian games presents our dynamic Bayesian game. In the section Simulation and result, we present our simulation and results. The final section concludes the paper.

Related works

Game theory has proven as an excellent tool for both modeling and solving problems in wireless networks. Problems such as agent negotiation,¹⁰ routing algorithms,¹¹ risk assessment,¹² access admission control,¹³ congestion control,¹⁴ and even wireless jamming¹⁵ have all been modeled or solved using various game theory techniques. Roy et al.¹⁶ provide an excellent survey paper of game theory as applied to network security. The paper details the theory behind a number of popular games and reveals examples of how they are used in network security. Uses include detecting cyber intrusion, denial of service attacks, and even intrusion detection in MANETs. Another interesting survey paper comes from Agrawal and Lingawar,¹⁷ who discuss gray hole, wormhole, black hole attacks, and other attacks in MANETs. Unlike the previous survey paper, Agrawal does not detail game theory techniques, but reviews how to analyze and detect various attacks using the tool NS2. The most informative survey paper, however, comes from Manshaei et al.¹⁸ They bring substantially more detail to the problems solved by game-theoretic techniques and introduce a number of new topics including security at the MAC (media access control) layer, cryptography, and anonymity.

Srivastava et al.¹⁹ add yet another survey of game theory as applied to wireless ad hoc networks, however, presents little information unattainable from the other survey papers.

There has been a great deal of research on understanding the selfish nature of nodes in ad hoc networks. Recall, a selfish node is one that chooses to decline communication with other nodes as a means of saving power and self-preservation. We contest that it is important to identify these nodes because they waste the resources of neighboring nodes attempting to communicate with them. Monitoring nodes must evaluate selfish installations, in addition to malicious ones, and determine whether they are benefitting or impeding the network as a whole. Komali et al.²⁰ discuss the selfish behavior of nodes in ad hoc and mesh networks and suggest a topology control algorithm that examines energy efficiency in the network and forces cooperation of particular nodes. Urpi ⁸ too discusses selfishness in ad hoc networks and also concludes that forcing communication between nodes is the only effective method of ensuring throughput in the network. Rather than forcing communication for selfish nodes, Marden and Effros²¹ suggest a game-theoretic approach. Under their model, the input is the number of wireless transmissions required in the problem. The distributed algorithm then determines the best way to satisfy the input while minimizing the cost to individual nodes. However, we are not only interested in selfish behavior, but malicious behavior as well.

Several works have studied the incentives nodes have to cooperate with their neighbors.^1–3 These works, however, model a selfish or malicious node as never cooperative. This model is too simple and inapplicable in real-world applications. Many others focus on modeling cooperation and selfishness in a network using game-theoretic approaches.^4–8 In these games, nodes decide whether to forward or not forward a packet based on a cost and benefit model. Their cost being the energy consumption necessary to forward the packet and benefits being improved network throughput and collaboration with neighboring nodes. In each, they show that enforcing cooperation between nodes can improve throughput, but nodes may exhaust their power storage and retreat from the network. These works, however, do not consider the existence of malicious nodes capable of disguising their presence by providing useful network function. It is unrealistic to consider a malicious node as always attacking or a selfish node as always declining. We must consider the multitude of actions these types of nodes may choose to take. Liu and Zang²⁵ develop a game-theoretic model which is capable of inferring the intent, objectives, and strategies of an attacker in a wireless ad hoc network. They found that the generality of their model allowed for its application in a variety of types of attacks and even tested the system on a denial of service attack. We would like to cultivate a similar level of generality in our model, as the type and severity of a malicious attack could come in a variety of forms.

Li and Wu¹ suggest a dynamic Bayesian game framework to analyze the interactions between regular and malicious nodes in MANETs. In this system, regular nodes form beliefs to evaluate the type of its opponent, refusing communication with identified malicious nodes. The malicious node regularly evaluates the risk of being caught and chooses when to flee and restart at another location. The paper, however, considers only interactions between two nodes. Their game is not applicable in a multi-user, real-world environment. Liu et al.² also suggest a Bayesian game. In their model, the attacker seeks to inflict the most damage without being detected and the defender tries to monitor and isolate nodes while conserving energy expenditure. They demonstrated that detection is feasible in both static and dynamic Bayesian models, concluding that a hybrid strategy is most effective. Theodorakopoulos and Baras present a similar work.

Their model, however, appears over simplified as it only considers two factors in the decision-making process: benefit to the network and energy expenditure.²⁶ Wang et al. demonstrate a more robust model, although considers only the case of two nodes as do Li and Wu¹ and Liu et al.² Wang³ develops a malicious node detection system played by a regular node and malicious node. Both players' strategies are based on Bayesian games of imperfect information in addition to a post-game played by the regular node upon detection to allow for coexistence with malicious nodes. Simulation results show that the perfect Nash equilibrium achieved in the post-game helps to extend the length of games and improve the throughput of the network.

Unlike previous work, we study the interactions of malicious and selfish types of nodes, together, in an ad hoc network. This generalizes the model as every node in an ad hoc network is inherently selfish. That is, every node seeks to maximize its particular payoff function. As well, we suggest a method of determining the benefit and damage a particular node inflicts on the network so that beneficial selfish and malicious nodes can be utilized to improve the throughput of the network.

Game model

We consider a MANET which contains a number of nodes connected with each other. Nodes can dynamically leave or join the network during movement. We assume authentication measures are in place, for example, public key-based authentication. When a node newly joins the network, other nodes authenticate the node and set their beliefs toward the newcomer to an initial value. We distinguish between three types of nodes: benevolent, malicious, and selfish nodes.

The actions of each node are rational and are governed by their underlying utility function. A rational action may be to refuse cooperation with other nodes if battery constraints become too limited. Table 1 presents the types of nodes and their associated pure strategies.

Table 1.

Pure strategy profiles for each type of node.

Type of node	Pure strategies
Benevolent	Monitor, Idle
Malicious	Attack, Disguise
Selfish	Participate, Decline

We define a benevolent node as one which always cooperates in network function and regularly monitors the channel. A benevolent node may choose to ban nodes that have been identified as malicious if the damage they cause to the network is greater than the benefit they provide.

Similarly, selfish nodes may be banned from the network for not participating enough. Forcing cooperation between benevolent nodes and others allows the nodes more opportunity to update their beliefs about opponents. These nodes, therefore, require either extended battery life or a permanent power source. A benevolent node has two pure strategies: Monitor or Idle. Each has an associated cost to the node. Monitoring, for instance, is a costly measure (e.g., consumes the node's power) and nodes cannot afford to monitor all the time. We must therefore develop a method in which benevolent nodes monitor only part of the time. A node who has evaluated the safety of the channel may choose to remain idle and conserve power for a short period. However, careful monitoring may reveal a trusted node to in fact be malicious.

Malicious nodes seek to cause damage and disorder to the network; however, they can avoid detection by disguising themselves as regular nodes. Thus, its pure strategies are Attack and Disguise. A malicious node attacks to waste resources and disrupt network operation. Attacks can come in a variety of forms including denial-of-service at different network layers, packet dropping, and routing disruption at the network layer. We must therefore develop a method of measure of how much damage is inflicted by various attacks. Like benevolent nodes, malicious nodes form beliefs about other nodes in the network. The malicious node tracks the benevolent node's trust opinion, evaluating the risk of being caught. A malicious node seeks to disguise itself if it is monitored by a benevolent node and attacks the network if it is not monitored.

Finally, we are left with selfish nodes. These nodes never intentionally cause harm to the network, but may reduce the effectiveness of the network by choosing to not participate with other nodes. Thus, the pure strategies for selfish nodes are Participate or Decline. Some nodes may choose to never participate in network functions such as forwarding packets and routing.

These nodes only slow down the network and waste the resources of other nodes attempting to communicate with it. Thus, they should be kicked from the network to prevent further waste. On the other hand, there may be selfish nodes that always participate in the network. Monitoring these nodes would be a waste of resources, so we do so rarely. However, most selfish nodes will strike a balance, participating in the network part of the time and retreating within itself the rest of the time. Like the two previous types of nodes, selfish nodes have profit and costs associated to their actions.

To simplify the interactions among the nodes, we consider a two-player game played by nodes i and j. The types of these nodes are private information, not available to the opponent.

Because the type of each player is hidden, and observation of the opponent is not accurate, it is a Bayesian game with imperfect information. Bayesian games are a combination of game theory and probability theory that allows incomplete information to be taken into account and influences future decisions.¹ In these games, players are allowed to have some private information (e.g., the type of the node in question) that affects the progress of the game. Players form beliefs about the private information of their opponent and respond accordingly. Their beliefs are represented as probability distributions and are updated using Bayes' rule as new information is learned.

As our detection game will always be played between two nodes with incomplete information, we look to a special category of Bayesian game called a signaling game. A signaling game is played between a sender and receiver. The sender has a certain type and knows the type of the receiver. Based on this information the receiver sends a message. However, the receiver does not know the type of the sender and can only observe the messages sent to it. The receiver must observe the messages sent to it and determine what actions to take in response. In our detection game, the sender, node i, can be malicious with probability α, or selfish with probability (1 − α). In our detection game, the sender knows that the receiving node is benevolent. It also knows that the receiving node believes the sender is malicious with probability α. The receiver/benevolent node knows only its current belief about the type of the sender and must choose a response based on this incomplete information. Once the benevolent node is certain of the type of its opponent, it will evaluate the benefit and damage that node causes. If the damage to the network is greater than the benefit, the node will be banned. Otherwise, the identified node will remain in the network and continue to be evaluated.

To further construct the game, we define the following values. Let W refer to the payoff of a malicious node if it successfully attacks. The cost of mounting such an attack is Ca. In the case that a malicious node chooses to disguise itself in the network it will incur a cost of Cd.

Likewise, regular nodes incur the same cost for providing network function. Let M refer to the payoff of a regular node if it chooses to participate in the network at the time it is monitored. For the defending node, j, the cost of monitoring the channel is given by Cm. S is the benefit a defending node receives from successfully detecting a regular node being selfish. Table 2 illustrates the notation used to represent the profits and costs of nodal interactions.

Table 2.

Summary of notation used in the model.

Symbolic notation	Definition
Cm	Cost associated with monitoring and analyzing the channel
Ca	Cost of mounting an attack against the network
Cd	Cost of providing effective useful network operation
W	Measure of the degree of damage inflicted to the network by malicious nodes
M	Measure of the benefit to the network provided by regular nodes participating
S	Measure of the benefit of detecting a selfish node

Figure 1 illustrates the extensive form of the static Bayesian detection game.

Figure 1.

Extensive form of static Bayesian detection game .

The actions chosen by nodes are given by their action profiles ai and aj for nodes i and j, respectively. Hence, for the action profile (ai, aj) = (Attack, Idle), the utility for a successful attack by node i is W−Ca. The loss for node j is −W because j is idle and cannot detect the attack. Similarly, if the action profile is (ai, aj) = (Attack, Monitor), the attacking node i loses W + Ca. The node suffers a loss because it chooses to attack at the same time it is being monitored. The defending node j will gain W−Cm because it is monitoring at the time of the attack and thus detected the attack. This can be seen in Table 3, which illustrates the costs and profits associated with the interactions between benevolent and malicious nodes. Notice that the payoffs in Table 3 indicate that node j benefits the most from playing Monitor if i plays Attack and from choosing Idle if j chose Disguise. Similarly, node i benefits the most by playing Attack when j plays Idle and by choosing Disguise when j plays Monitor.

Table 3.

Strategic form of detection game where i = malicious and j = benevolent.

	Monitor	Idle
Attack	−W−Ca, W−Cm	W−Ca, −W
Disguise	−Cd, −Cm	−Cd, 0

Table 4 indicates the strategic form of our static Bayesian detection game where node i is selfish and node j is benevolent. The payoffs indicate that Participate is i's best response to j playing Monitor and that Decline is i's best response to j playing Idle. Likewise, Monitor is j's best response to i playing Decline and Idle is j's best response to i playing Participate. We can see that if the action profile is (Participate, Monitor) then node i receives a payoff of M−Cd. The node benefits M because it will gain better standing with j for participating in network function. It loses Cd for providing that function. The payoff of node j is M−Cm because it too benefits from useful network function and loses power by monitoring. We assume this will always be a positive number. That is, M > Cm. This assumption simplifies our later pure-strategy Nash equilibrium.

Table 4.

Strategic form of detection game where i = selfish and j = benevolent.

	Monitor	Idle
Participate	M−Cd, M−Cm	M−Cd, 0
Decline	0, S−Cm	0, 0

Notice that the action profile (Decline, Idle) results in a zero payoff for both nodes. Neither can be penalized for simply doing nothing.

Bayesian Nash equilibrium analysis

We begin our analysis on the detection game from the extensive form of the static Bayesian game as illustrated in Figure 1. In our attacker/defender game, the attacker would like to play a Bayesian strategy to minimize its chances of being detected and the defender would like to play a Bayesian strategy in order to maximize its chance of detecting attacks. Because we are playing a signaling game, the attacking player, i, knows that the type of its opponent is benevolent. Node j, however, believes that node i is regular (selfish) with probability (1−α) and malicious with probability α. To solve this game, we are interested in finding the possible BNE. We define a BNE as a strategy profile in which each player's prescribed strategy is a best response to the strategies of the other players in the Bayesian game.²⁷ In other words, neither player can change strategies and improve their payoff. Nash equilibrium can be reached in either a pure context in which players always choose one particular strategy or in a mixed context where players choose strategies with certain probability. In a static game, the BNE is the Nash equilibrium given the beliefs of both nodes.

First, we will consider only the pure strategies. If player i plays its pure strategy pair (Attack if malicious, Participate if selfish), then the expected payoff of defender j playing its pure strategy Monitor is given as

E_{j} (Monitor) = α (W - Cm) + (1 - α) (M - Cm)

(1)

Likewise, j's expected payoff of playing its pure strategy Idle is

E_{j} (Idle) = α (- W) + (1 - α) (0)

(2)

Setting these two equations equal to each other, we get

α = \frac{Cm - M}{2 W - M}

(3)

Therefore, if $E_{j} (Monitor) > E_{j} (Idle)$ or if $α > \frac{Cm - M}{2 W - M}$ then the best response of player j is to play Monitor. However, if defender j plays Monitor, Attack will no longer be the best response for the malicious type of player i, and it will move to play Disguise instead. Therefore, {(Attack if malicious, Participate if selfish), Monitor} is not a BNE. But, if $α \leq \frac{Cm - M}{2 W - M}$ , then the best response for defender j is to play Idle. If this were the case, then Participate would no longer be the best strategy for the selfish type of player and it would move to play Decline. Recall, M > Cm. Otherwise, we would have a BNE. Thus, {(Attack if malicious, Participate if selfish), Idle} is a BNE.

Now we consider the pure strategy pair (Attack if malicious, Decline if selfish) played by player i. The expected payoff of defender j playing its pure strategy Monitor is

E_{j} (Monitor) = α (W - Cm) + (1 - α) (S - Cm)

(4)

and the expected payoff of playing its pure strategy Idle is

E_{j} (Idle) = α (- W) + (1 - α) (0)

(5)

Again, setting these equal to each other gives

α = \frac{Cm - S}{2 W - S}

(6)

Thus, if $E_{j} (Monitor) > E_{j} (Idle)$ or if $α > \frac{Cm - S}{2 W - S}$ , then the best response for player j is to play Monitor. However, like the previous case, the defender will move to play Disguise and so {(Attack if malicious, Decline if selfish), Monitor} is not a BNE. If we have $α \leq \frac{Cm - S}{2 W - S}$ then the best response for player j is to play Idle. This is a BNE because the best response of player i is to either continue playing Attack or to continue to playing Decline. So {(Attack if malicious, Decline if selfish), Idle} is a BNE.

We now know that if the malicious player i always plays Attack, then the only BNE exists where the selfish type plays Decline and the best response by defender j is to play Idle. Now we must consider those situations in which the malicious type of player always plays Disguise. First we consider the pure strategy pair (Disguise if malicious, Decline if selfish) for player i. The expected payoff for j playing the pure strategy Monitor would then be

E_{j} (Monitor) = α (- Cm) + (1 - α) (S - Cm)

(7)

and the expected payoff of playing its pure strategy Idle is

E_{j} (Idle) = α (0) + (1 - α) (0)

(8)

Setting these two equations equal to each other we get

α = \frac{Cm - S}{S}

(9)

Therefore, if $E_{j} (Monitor) > E_{j} (Idle)$ or if $α > \frac{Cm - S}{S}$ then the best response of player j is Monitor. This is a BNE because neither the malicious nor selfish type of player can do better by changing strategy. However, if we have that α $\leq \frac{Cm - S}{S}$ then the best response for player j is to play Idle. If player j chooses to play Idle, then the best response of the malicious type of player is to switch to Attack. Hence, {(Disguise if malicious, Decline if selfish), Idle} is not a BNE and {(Disguise if malicious, Decline if selfish), Monitor} is a BNE.

Finally, the last pure strategy combination we must consider for player i is (Disguise if malicious, Participate if selfish). If the defending node determines that the best response to player i's strategy is to play Idle, then the malicious type of node would move to play Attack instead. If the defending node deems its best response to play Monitor, then we have again a BNE.

We have shown that there exists a number of BNE for particular pure strategy profiles meeting certain criteria. Now we seek to find a mixed-strategy BNE for the cases that did not result in a pure-strategy BNE. For this we must introduce two new belief probabilities to our defender and one to our attacker. Let

p: be the belief of defender j about the probability with which player i will play Attack

q: be the belief of defender j about the probability that player i plays Participate

r: be the belief of attacker i about the probability that player j plays Monitor.

Hence, the expected payoff for player j playing Monitor is

\begin{matrix} E_{j} (Monitor) = α p (W - Cm) + α (1 - p) (- Cm) \\ + (1 - α) q (M - Cm) + (1 - α) (1 - q) (S - Cm) \end{matrix}

(10)

and the expected payoff of defender j playing Idle is

\begin{matrix} E_{j} (Idle) = α p (- W) + α (1 - p) (0) + (1 - α) q (0) \\ + (1 - α) (1 - q) (0) \end{matrix}

(11)

By imposing $E_{j} (Monitor) = E_{j} (Idle)$ , we get the that the malicious player should play Attack with probability p and that the selfish type of player should play Participate with probability q so that

2 α pW + (1 - α) q (M - S) - α S = Cm - S

(12)

We determine the probability that a malicious node will Attack similarly. The expected value of a malicious node playing Attack is

E_{i} (Attack) = r (- W - Ca) + (1 - r) (W - Ca)

(13)

and the expected value of playing Disguise is

E_{i} (Diguise) = r (- Cd) + (1 - r) (- Cd)

(14)

As before, we impose $E_{i} (Attack) = E_{i} (Disguise)$ , and get that the defending player should play Monitor with probability

r = \frac{Cd + W - Ca}{2 W}

(15)

Recall Table 3. Notice that the payoffs for a selfish node are the same whether its opponent plays Monitor or Idle. Thus, the probability that j will play Monitor does not affect nodes of the selfish type.

Thus, the strategy pair ((p if malicious, q if selfish), r, α) is a mixed-strategy BNE if equations (12) and (15) are satisfied.

In summary, our static Bayesian detection game has four pure-strategy BNEs. Table 5 details the four pure-strategy equilibria found. Notice these form two situations. One, the malicious type of node plays Attack and the defending node plays Idle. Two, the malicious type of node plays Disguise and the defending node plays Monitor. These situations result in pure-strategy BNEs, regardless of the play made by the selfish type of node. There also exists a mixed-strategy BNE for which the defender j plays Monitor with a probability derived from its beliefs p, q, and α and the attacker i plays Attack with a probability based on its belief, r, and neither player can improve their payoff by changing strategies. The mixed-strategy BNE is governed by equations (12) and (15).

Table 5.

List of pure-strategy Nash equilibrium found.

Pure-strategy Nash equilibrium
{(Attack if malicious, Participate if selfish), Idle}
{(Attack if malicious, Decline if selfish), Idle}
{(Disguise if malicious, Participate if selfish), Monitor}
{(Disguise if malicious, Decline if selfish), Monitor}

Belief update and dynamic Bayesian games

The previously described static Bayesian game is a one-stage game in which both attacker and defender attempt to maximize their payoff based on a fixed prior belief set about the type of their opponent. In addition, we have illustrated the equilibria associated with these prior belief sets. Due to the difficulty in assigning accurate probabilities for each player's beliefs, we extend the static Bayesian game to a multi-stage dynamic Bayesian game in which each player updates its belief probabilities in response to actions taken by its opponent and its previously held belief.

We assume that the static Bayesian game is repeatedly played at each time slot tk, where k = 0, 1, 2, … The payoffs of the players in each stage game have no discount. That is to say that the payoffs will remain the same for every stage game. In addition, an arbitrary interval of T seconds may be selected for each stage game and we consider the game to have an infinite horizon as any node will not know when its neighboring nodes will leave the network.

Furthermore, we assume that the identities of players do not change as the game progresses. Thus, our model relies on authentication measures to counteract impersonation attacks, spoofing, and Sybil attacks.²⁸ During each stage, players will interpret all incoming messages from neighboring nodes and update their probability distributions according to Bayes' theorem.

We construct our belief updating rules based on Bayes' theorem. For each node, its belief {benevolent:{α: probability of malicious opponent, (1−α): probability of selfish opponent} and malicious:{r: probability of opponent monitoring, (1−r): probability of opponent not monitoring}} can be determined by its most recently updated belief and the interpretation of actions. We do not consider the case of a selfish node because selfish nodes do not form beliefs about their neighbors. Thus, we write the belief of a benevolent node at the (t + 1)th stage as

\begin{matrix} α_{(t + 1)} = {\begin{matrix} P (malicious | attack) = \frac{α_{t} p_{t}}{α_{t} p_{t} + {(1 - α)}_{t} (0)} = 1 \\ P (malicious | disguise) = \frac{α_{t} {(1 - p)}_{t}}{α_{t} {(1 - p)}_{t} + {(1 - α)}_{t} q_{t}} \end{matrix} \end{matrix}

(16)

\begin{matrix} (1 - α)_{(t + 1)} = {\begin{matrix} P (selfish | participate) = \frac{{(1 - α)}_{t} q_{t}}{α_{t} {(1 - p)}_{t} + {(1 - α)}_{t} q_{t}} \\ P (selfish | decline) = \frac{{(1 - α)}_{t} {(1 - q)}_{t}}{α_{t} {(1 - p)}_{t} + {(1 - α)}_{t} {(1 - q)}_{t}} \end{matrix} \end{matrix}

(17)

We can then use these updated probabilities to recalculate the supplementary belief set {p: probability of attack, (1 − p): probability of disguise, q: probability of participate, (1 − q): probability of decline} as follows:

p_{(t + 1)} = P (attack | α_{t}) = \frac{p_{t} α_{t}}{p_{t} α_{t} + {(1 - p)}_{t} α_{t}}

(18)

q_{(t + 1)} = P (participate | (1 - α)_{t}) = \frac{q_{t} {(1 - α)}_{t}}{q_{t} {(1 - α)}_{t} + {(1 - q)}_{t} {(1 - p)}_{t}}

(19)

Similarly, we write the belief set of a malicious node at the (t + 1)th stage as

\begin{matrix} r_{(t + 1)} = {\begin{matrix} P (monitor | participate) = \frac{r_{t} q_{t}}{r_{t} q_{t} + {(1 - r)}_{t} q_{t}} \\ P (monitor | decline) = \frac{r_{t} * 0}{r_{t} * 0 + {(1 - r)}_{t} {(1 - q)}_{t}} = 0 \end{matrix} \end{matrix}

(20)

\begin{matrix} (1 - r)_{(t + 1)} = {\begin{matrix} P (idle | participate) = \frac{{(1 - r)}_{t} q_{t}}{{(1 - r)}_{t} q_{t} + r_{t} * 1} \\ P (idle | decline) = \frac{{(1 - r)}_{t} {(1 - p)}_{t}}{{(1 - r)}_{t} {(1 - p)}_{t} + r_{t} * 0} = 1 \end{matrix} \end{matrix}

(21)

These equations for building and updating belief probabilities constitute what we refer to as a belief system. We define a belief system to be a function that assigns each belief probability distribution over the histories in the set. Every node's set of belief distributions are assigned initial values at the start of the game. Players update this set by observing actions in the current stage game and the previous belief it holds. Beliefs are the result of previous situations and can be backtracked to the initial belief and action observed. Therefore, the current belief set and observed action can fully represent the histories in the information sets, and those information sets can be reached with positive probabilities if the strategies are carefully designed.

Simulation and results

The strategies outlined in the previous sections have been implemented on a custom simulator based on ds, developed by Dr. Li Wu.²⁹ Wu's simulator contains methods only for generating arbitrary numbers of nodes and placing them within a rectangular area. Thus, we implemented the communication between neighboring nodes via Directed Sequence Distance Vector Routing in addition to our model specifications. Simulations are conducted in randomly generated MANETs. We assume that any node only has access to the packets directly addressed to it.

A specified number of wireless nodes are randomly placed in a 900 m × 900 m region with a transmission range of 300 m. Once placed, nodes communicate with neighbors to build routing tables by broadcasting network probe packets. Each node stores the minimum number of hops to reach the destination node as well as the next node in the path. If a node receives a packet destined for a neighbor then it refers to its routing tables and forwards the packet to the next node in the path to the destination node.

Each simulation is repeated 500 times, and the average is taken and used for results. We set the number of malicious nodes in the network to 20, the number of benevolent nodes is 20, and the remaining 20 nodes are of selfish type. For every benevolent node, its beliefs are initialized to α = 0.2, p = 0.5, and q = 0.5. The beliefs of the malicious nodes are initialized to r = 0.5 and q = 0.5. In addition, the constants (which do not change throughout the simulation) are set to Cm = 3, Ca = 5, Cd = 1, W = 8, M = 2, and S = 4. Simulations showed that changing these constants had little effect on the results.

In Figure 2, we illustrate the change in belief of any particular benevolent node, i, interacting with any malicious node, j. The figure illustrates two plots for the belief of node i over time. The first plot details the belief set of a benevolent node updated with our static model, while the second plot describes the same belief updated using our dynamic model.

Figure 2.

Belief of a benevolent node about the type of its opponent (malicious) as the game progresses.

Notice, both plots quickly reach a steady-state value of about 0.95, indicating a strong likelihood that the opposing installation is malicious. Our static model plot reaches this steady state earlier as continuous monitoring of opponents offers more chances to detect malicious activity.

Nevertheless, our dynamic model is able to identify the malicious installation only a few stage games behind its static counterpart. This tells us that our dynamic model is capable of identifying malicious installations within a reasonable amount of time. Figure 3, on the other hand, plots the belief of a particular malicious installation as it interacts with benevolent nodes over time. The graph shows that malicious nodes are capable of identifying their monitoring counterparts within a timely manner as well. Notice, the malicious node identifies its opponent to be likely monitoring earlier in the static model than in the dynamic one. This makes sense as the benevolent player monitors constantly in the static model. This gives the malicious player more opportunities to recognize its opponent's strategy.

Figure 3.

Belief of a malicious node about the strategy of its opponent (benevolent) as the game progresses.

Now that we are certain that our model allows for identification of malicious and benevolent entities, we study its performance. First, we must define some terminology. We define goodput (G) to be the quotient of the number of legitimate packets and the total number of packets to travel through the network. Throughput (T) is defined as the total number of legitimate (non-malicious) packets divided by time. A higher value for throughput indicates better performance in the network and higher values in goodput point to less waste of network resources. In Figures 4 and 5, we analyze the goodput and throughput of our network as the threshold for banning malicious installations varies. The threshold for banning is a maximum tolerance level allowed for a benevolent node's belief p, the likelihood that the opposing player will play attack. If p reaches a certain threshold, we ban the installation. Figure 4 plots the goodput in relation to the ban threshold. Notice that goodput falls as the threshold increases. If we have a low value for the threshold, then nodes are banned as soon as they take any malicious actions, thus goodput is high because malicious installations are removed from the network quickly. However, if the threshold is high, then the malicious nodes are left in the network longer and goodput degrades as there are more attack packets in circulation. Our proposed dynamic model is only slightly worse than our static model as non-continuous monitoring allows malicious nodes to stay in the network slightly longer.

Figure 4.

Goodput as the threshold for banning possibly malicious installations increases.

Figure 5.

Change in throughput as the threshold for banning possibly malicious installations increases.

Figure 5 indicates the changes in throughput as the threshold for banning varies. However, we see the opposite effect as the previous. That is, throughput increases as the threshold rises. Consider the case in which the threshold is 0.5. The throughput is low because malicious nodes will be excluded from the network early on in the game. Thus, we are losing all the legitimate packets generated from malicious nodes attempting to hide within the network.

Conversely, if the threshold is set to 1.0, then malicious nodes will stay in the network much longer before being removed. Hence, the Disguise strategy of these installations will increase the number of legitimate packets and therefore improve throughput. This is our motivation behind our goal of coexistence. If we only exclude those installations that attack the network regularly, then we can significantly improve throughput in comparison to models that instantly ban nodes that have been identified as malicious. For this reason, we fix the threshold in future results at 0.75 so that we balance the gain in throughput with the loss in goodput.

In Figures 6 and 7, we show the effect of varying the number of benevolent nodes in the network on the goodput and throughput. The number of devices of malicious or selfish type is equally divided between 40 remaining installations. Figure 6 details goodput. Notice that goodput increases as the number of benevolent nodes increases. This makes sense as an increase in the population of monitoring installations will reduce the time that malicious nodes are left in the network, thus reducing the number of non-legitimate packets. Similarly, throughput increases as the number of benevolent nodes rises. This increase in the number of legitimate packets per unit of time is the result of two factors. First, benevolent nodes generate or forward only legitimate messages. Second, increasing the number of benevolent nodes reduces the time that malicious installations exist in the network. Thus, reducing the number of legitimate packets lost to malicious attacks. Therefore, we can conclude that increasing the number of monitoring nodes improves the network as a whole.

Figure 6.

Goodput as the number of benevolent nodes varies.

Figure 7.

Throughput as the number of benevolent nodes varies.

We show the effect of changing the number of malicious nodes in the network on throughput and goodput in Figures 8 and 9. In both cases, the number of benevolent nodes is held constant at 20, along with 20 selfish installations. Goodput decreases as the number of malicious nodes increases. This is the result of an increase in the total number of non-legitimate packets in the network originating from the rising number of malicious nodes. Likewise, throughput decreases for the same reason.

Figure 8.

Goodput as the number of malicious nodes varies.

Figure 9.

Throughput as the number of malicious nodes varies.

Notice in Figures 2 –9, our dynamic model performed slightly worse than our static model. We consider these acceptable losses as the goal of our dynamic model is to conserve power by monitoring only a portion of the time. Thus, it is necessary to show that our model does in fact conserve power. Figure 10 shows the total power usage of a particular benevolent node over time. Recall, the data are the result of an average over 500 iterations. It is clear that at any point in time, the total power usage generated by our dynamic model is lower than that of the static one. The difference between these two rises as the length of the game increases. Therefore, we have shown that our dynamic model achieves adequate values for goodput and throughput in addition to conserving power for benevolent installations.

Figure 10.

Total power usage of a benevolent node as the game progresses.

Conclusion

In this article, we have discussed the importance of identifying both malicious and selfish nodes in wireless ad hoc networks. We have developed a model based on Bayesian games with incomplete information that is capable of modeling interactions of any type of node found in an ad hoc environment. Additionally, we have found four pure-strategy BNEs in which neither attacker nor defender can change their strategy to improve their payoff. As well, we establish a dynamic-strategy BNE in which players choose actions with a particular probability based on the likely probability distribution of their opponent. In either case we were able to verify the existence of a Nash equilibrium between the attacking and defending players in which no player can advance their payoff. We proved through rigorous simulation that our proposed benevolent node is capable of determining the types of nodes in the network within a reasonable timeframe while conserving power. Additionally, we showed that throughput can be improved by coexisting with malicious nodes that seldom attack.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Li F and Wu J. Hit and run: a Bayesian game between regular and malicious nodes in MANETs. In: Sensor, mesh and ad-hoc communications and networks, June 2008. IEEE.

Liu Y, Camaniciu C and Man H. A Bayesian game approach for intrusion detection in wireless ad-hoc networks. In: GameNets ‘06 Proceedings from the 2006 workshop on game theory for communications and networks, 2006. New York: ACM Press.

Wang W, Chatterjee M and Kwiat K. Coexistence with malicious nodes: a game theoretic approach. In: GameNets ‘09 Proceedings from the international conference on game theory and networks, May 2009, pp. 277–286. Istanbul, Turkey: IEEE.

Buttyan

Hubaux

. Stimulating cooperation in self-organizing mobile ad-hoc networks. ACM Mobile Netw Appl 2003; 8: 579–592.

Felegyhazi

Hubaux

Buttyan

. Nash equilibria of packet forwarding strategies in wireless ad-hoc networks. IEEE Trans Mobile Comput 2006; 5: 1–14.

Srinivasan

Nuggehalli

Chiasserini

C-F

et al.

An analytical approach to the study of cooperation in wireless ad-hoc networks. IEEE Trans Commun 2005; 4: 722–733.

Cai J and Pooch U. Allocate fair payoff for cooperation in wireless ad-hoc networks using Shapley value. In: Proceedings of the 18th international parallel and distributed processing symposium (IPDPS'04), Santa Fe, NM, 26–30 April 2004, pp.219–227. IEEE.

Urpi A, Bonuccelli M and Giordano S. Modeling cooperation in mobile ad-hoc networks: a formal description of selfishness. In: WiOpt'03 workshop: modeling and optimization in mobile, wireless networks, March 2003.

Roles JA, ElAarag H and Friedman E. A Bayesian game approach to coexistence with malicious and selfish nodes in wireless ad-hoc networks. Proceedings of communication and networking symposium (CNS'14), International Society of Modeling and Simulation 2014 Spring Simulation Multiconference, Tampa, FL, 13–16 April, 2014. ACM.

10.

Bian Z and Luo J. A cooperative game model for agent negotiation in network service. In: Proceedings of the 10th international conference on computer supported cooperative work in design, 2006, 447–458, IEEE.

11.

Su J, Liu W and Yue K. A network routing algorithm based on the coalitional game theory. In: International conference on computational intelligence and natural computing, 2009, pp.409–412. IEEE.

12.

It W, Xia S, Zhang C, et al. A network security risk assessment framework based on game theory. In: Second international conference on future generation communication and networking, 2008, pp.249–253. IEEE.

13.

Charilas D, Markaki O, Tragos E. A theoretical scheme for applying game theory and network selection mechanisms in access admission control. In: 3rd International symposium on wireless pervasive computing, Santorini, Greece, 2008, pp.303–307.

14.

Li Z and Jin Z. A wireless ad-hoc network congestion control algorithm based on game theory. In: International conference on future computer science and applications, 2011. IEEE.

15.

Yang

Xue

Zhang

et al.

Coping with a smart jammer in wireless networks: a Stackelberg game approach. IEEE Trans Wireless Commun 2013; 12: 4038–4047.

16.

Roy S, Ellis C, Shiva S, et al. A survey of game theory as applied in network security. In: Proceedings of the 43rd Hawaii international conference on system sciences, 2010, pp.1–10.

17.

Agrawal

Lingawar

. Applications of NS2 to overcome computer network attacks. World Res J Comput Architect 2012; 1: 6–10 .

18.

Manshaei

Zhu

Alpcan

et al.

Game theory meets network security and privacy. ACM Comput Survey 2011, pp. 45: 1–39, .

19.

Blanc

Liu

Vahdat

. Designing incentives for peer-to-peer routing. In: Proceedings of IEEE INFOCOM, Miami, FL, March 2005, pp. 374–385.

20.

Komali R, MacKenzie A and Mahonen P. On selfish, local information, and network optimality: a topological control example. In: Proceeding of 18th international conference on computer communications and networks, 2009, IEEE, pp.1–7.

21.

Xiao

Shan

Ren

. Game theory models for IEEE 802.11 DCF in wireless ad-hoc networks. IEEE Radio Commun 2005; 43: 22–26.

22.

Marden J and Effros M. The price of selfishness in network coding. IEEE workshop on network coding, theory and applications, IEEE, 2009, pp.2349–2361.

23.

Nurmi P. Modeling routing in wireless ad-hoc networks with dynamic Bayesian games. In: Sensor and ad-hoc communications and networks, 2004. IEEE SECON 2004. 2004 First annual IEEE communications society conference, October 2004, pp.63–70.

24.

Liu

Zang

. Incentive-based modeling and inference of attacker intent, objectives, and strategies. ACM Trans Inf Syst Security 2005, pp. 8: 78–118.

25.

Srivastava

Neel

MacKenzie

et al.

Using game theory to analyze wireless ad hoc networks. IEEE Commun Surveys Tutorials 2005; 7: 46–56.

26.

Theodorakopoulos G and Baras J. Malicious users in unstructured networks. In: IEEE international conference on computer communications, May 2007, pp.884–891. IEEE.

27.

Watson

. Strategy: an introduction to game theory, New York, NY: W. W. Norton & Company, 2008. .

28.

Douceur J. The Sybil attack. In: First international workshop on peer-to-peer systems, ACM, 2002, pp.640–651.

29.

Wu L. DS simulator, http://sourceforge.net/projects/wrss (8 April 2013, accessed December 2013).