14-05-2013, 03:04 PM
Mechanism Design-Based Secure Leader Election Model for Intrusion Detection in MANET
Abstract
In this paper, we study leader election in the presence of selfish nodes for intrusion detection in mobile ad hoc networks
(MANETs). To balance the resource consumption among all nodes and prolong the lifetime of an MANET, nodes with the most
remaining resources should be elected as the leaders. However, there are two main obstacles in achieving this goal. First, without
incentives for serving others, a node might behave selfishly by lying about its remaining resources and avoiding being elected. Second,
electing an optimal collection of leaders to minimize the overall resource consumption may incur a prohibitive performance overhead, if
such an election requires flooding the network. To address the issue of selfish nodes, we present a solution based on mechanism
design theory. More specifically, the solution provides nodes with incentives in the form of reputations to encourage nodes in honestly
participating in the election process. The amount of incentives is based on the Vickrey, Clarke, and Groves (VCG) model to ensure
truth-telling to be the dominant strategy for any node. To address the optimal election issue, we propose a series of local election
algorithms that can lead to globally optimal election results with a low cost. We address these issues in two possible application
settings, namely, Cluster-Dependent Leader Election (CDLE) and Cluster-Independent Leader Election (CILE). The former assumes
given clusters of nodes, whereas the latter does not require any preclustering. Finally, we justify the effectiveness of the proposed
schemes through extensive experiments.
INTRODUCTION
UNLIKE traditional networks, the Mobile Ad hoc Networks
(MANETs) have no fixed chokepoints/bottlenecks
where Intrusion Detection Systems (IDSs) can be
deployed [3], [7]. Hence, a node may need to run its own
IDS [14], [1] and cooperate with others to ensure security
[15], [26]. This is very inefficient in terms of resource
consumption since mobile nodes are energy-limited. To
overcome this problem, a common approach is to divide the
MANET into a set of 1-hop clusters where each node
belongs to at least one cluster. The nodes in each cluster
elect a leader node (cluster head) to serve as the IDS for the
entire cluster. The leader-IDS election process can be either
random [16] or based on the connectivity [19]. Both
approaches aim to reduce the overall resource consumption
of IDSs in the network. However, we notice that nodes
usually have different remaining resources at any given
time, which should be taken into account by an election
scheme. Unfortunately, with the random model, each node
is equally likely to be elected regardless of its remaining
resources.
Motivating Example
Fig. 1 illustrates an MANET composed of 10 nodes labeled
from N1 to N10. These nodes are located in five 1-hop
clusters where nodes N5 and N9 belong to more than one
cluster and have limited resources level. We assume that
each node has different energy level, which is considered as
private information. At this point, electing nodes N5 and N9
as leaders is clearly not desirable since losing them will
cause a partition in the network and nodes will not be able
to communicate with each other. However, with the
random election model [16], nodes N5 and N9 will have
equal probability, compared to others, in being elected as
leaders. The nodes N5 and N9 will definitely be elected
under the connectivity index-based approach due to their
connectivity indexes [19].
Possible Applications of Leader Election
Scheme
The problem of selfishness and energy balancing exists in
many other applications to which our solution is also
applicable. Like in IDS scheme, leader election is needed
for routing [5] and key distribution [6], [10] in MANET. In
key management, a central key distributor is needed to
update the keys of nodes. In routing, the nodes are grouped
into small clusters and each cluster elects a cluster head
(leader) to forward the packets of other nodes. Thus, one
node can stay alive, while others can be in the energy-saving
mode. The election of a leader node is done randomly, based
on connectivity (nodes’ degree) or based on a node’s weight
(here, the weight refers to the remaining energy of a node
[34]). We have already pointed out the problems of random
model and connectivity model. We believe that a weightbased
leader election should be the proper method for
election. Unfortunately, the information regarding the
remaining energy is private to a node, and thus, not
verifiable. Since nodes might behave selfishly, they might
lie about their resource level to avoid being the leader if there
is no mechanism to motivate them. Our method can
effectively address this issue.
Paper Outline
The rest of this paper is organized as follows: Section 2
formulates the problem. Section 3 describes our leader
election mechanism where the cost of analysis function,
reputation model, and payment design are given. Section 4
analyzes our mechanisms against selfish and malicious
nodes. Section 5 devises the election algorithm needed to
handle the election process. Section 6 provides the proof of
correctness and security properties of the algorithm.
Section 7 presents empirical results. Section 8 reviews
related work. Finally, Section 9 concludes the paper and
discusses our future work.
PROBLEM STATEMENT
We consider an MANET where each node has an IDS and a
unique identity. To achieve the goal of electing the most
cost-efficient nodes as leaders in the presence of selfish and
malicious nodes, the following challenges arise: First, the
resource level that reflects the cost of analysis is considered
as a private information. As a result, the nodes can reveal
fake information about their resources if that could increase
their own benefits. Second, the nodes might behave
normally during the election but then deviate from normal
behavior by not offering the IDS service to their voted nodes.
LEADER ELECTION MECHANISM
In this section, we present our leader election mechanism
for truthfully electing the leader nodes. To make the paper
self-contained, the background on mechanism design is
given in Section 3.1. Section 3.2 formulates our model using
the standard mechanism design notations. To achieve the
design goal, the cost of analysis function is given in
Section 3.3 followed by the reputation system model given
in Section 3.4. Finally, the design of the payment for the
two models is given in Section 3.5.
Mechanism Design Background
Mechanism design is a subfield of microeconomics and game
theory [21]. Mechanism design uses game theory [25] tools to
achieve the desired goals. The main difference between
game theory and mechanism design is that the former can be
used to study what could happen when independent players
act selfishly. On the other hand, mechanism design allows a
game designer to define rules in terms of the SCF such that
players will play according to these rules. The balance of IDS
resource consumption problem can be modeled using
mechanism design theory with an objective function that
depends on the private information of the players. In our
case, the private information of the player is the cost of
analysis which depends on the player’s energy level. Here,
the rational players select to deliver the untruthful or
incomplete information about their preferences if that leads
to individually better outcomes [31]. The main goal of using
mechanism design [17] is to address this problem by:
1) designing incentives for players (nodes) to provide
truthful information about their preferences over different
outcomes and 2) computing the optimal system-wide
solution, which is defined according to (1).
Reputation System Model
Before we design the payment, we need to show how the
payment in the form of reputation can be used to: 1) motivate
nodes to behave normally and 2) punish the misbehaving
nodes. Moreover, it can be used to determine whom to trust.
To motivate the nodes in behaving normally in every election
round, we relate the cluster’s services to nodes’ reputation.
This will create a competition environment that motivates the
nodes to behave normally by saying the truth. To enforce our
mechanism, a punishment system is needed to prevent nodes
from behaving selfishly after the election. Misbehaving
nodes are punished by decreasing their reputation, and
consequently, are excluded from the cluster services if the
reputation is less than a predefined threshold. As an
extension to our model, we can extend our reputation system
to include different sources of information such as routing
and key distribution with different assigned weights.
CILE Payment Design
In CILE, each node must be monitored by a leader node that
will analyze the packets for other ordinary nodes. Based on
the cost of analysis vector C, nodes will cooperate to elect a
set of leader nodes that will be able to analyze the traffic
across the whole network and handle the monitoring
process. This increases the efficiency and balances the
resource consumption of an IDS in the network. Our
mechanism provides payments to the elected leaders for
serving others (i.e., offering the detection service). The
payment is based on a per-packet price that depends on the
number of votes the elected nodes get. The nodes that do not
get any vote from others will not receive any payment. The
payment is in the form of reputations, which are then used to
allocate the leader’s sampling budget for each node. Hence,
any node will strive to increase its reputation in order to
receive more IDS services from its corresponding leader.
LEADER ELECTION ALGORITHM
To run the election mechanism given in Section 3, we
propose a leader election algorithm that helps to elect the
most cost-efficient leaders with less performance overhead
compared to the network flooding model. We devise all the
needed messages to establish the election mechanism taking
into consideration cheating and presence of malicious
nodes. Moreover, we consider the addition and removal
of nodes to/from the network due to mobility reasons.
Finally, the performance overhead is considered during the
design of the given algorithm where computation, communication,
and storage overhead are derived.
Abstract
In this paper, we study leader election in the presence of selfish nodes for intrusion detection in mobile ad hoc networks
(MANETs). To balance the resource consumption among all nodes and prolong the lifetime of an MANET, nodes with the most
remaining resources should be elected as the leaders. However, there are two main obstacles in achieving this goal. First, without
incentives for serving others, a node might behave selfishly by lying about its remaining resources and avoiding being elected. Second,
electing an optimal collection of leaders to minimize the overall resource consumption may incur a prohibitive performance overhead, if
such an election requires flooding the network. To address the issue of selfish nodes, we present a solution based on mechanism
design theory. More specifically, the solution provides nodes with incentives in the form of reputations to encourage nodes in honestly
participating in the election process. The amount of incentives is based on the Vickrey, Clarke, and Groves (VCG) model to ensure
truth-telling to be the dominant strategy for any node. To address the optimal election issue, we propose a series of local election
algorithms that can lead to globally optimal election results with a low cost. We address these issues in two possible application
settings, namely, Cluster-Dependent Leader Election (CDLE) and Cluster-Independent Leader Election (CILE). The former assumes
given clusters of nodes, whereas the latter does not require any preclustering. Finally, we justify the effectiveness of the proposed
schemes through extensive experiments.
INTRODUCTION
UNLIKE traditional networks, the Mobile Ad hoc Networks
(MANETs) have no fixed chokepoints/bottlenecks
where Intrusion Detection Systems (IDSs) can be
deployed [3], [7]. Hence, a node may need to run its own
IDS [14], [1] and cooperate with others to ensure security
[15], [26]. This is very inefficient in terms of resource
consumption since mobile nodes are energy-limited. To
overcome this problem, a common approach is to divide the
MANET into a set of 1-hop clusters where each node
belongs to at least one cluster. The nodes in each cluster
elect a leader node (cluster head) to serve as the IDS for the
entire cluster. The leader-IDS election process can be either
random [16] or based on the connectivity [19]. Both
approaches aim to reduce the overall resource consumption
of IDSs in the network. However, we notice that nodes
usually have different remaining resources at any given
time, which should be taken into account by an election
scheme. Unfortunately, with the random model, each node
is equally likely to be elected regardless of its remaining
resources.
Motivating Example
Fig. 1 illustrates an MANET composed of 10 nodes labeled
from N1 to N10. These nodes are located in five 1-hop
clusters where nodes N5 and N9 belong to more than one
cluster and have limited resources level. We assume that
each node has different energy level, which is considered as
private information. At this point, electing nodes N5 and N9
as leaders is clearly not desirable since losing them will
cause a partition in the network and nodes will not be able
to communicate with each other. However, with the
random election model [16], nodes N5 and N9 will have
equal probability, compared to others, in being elected as
leaders. The nodes N5 and N9 will definitely be elected
under the connectivity index-based approach due to their
connectivity indexes [19].
Possible Applications of Leader Election
Scheme
The problem of selfishness and energy balancing exists in
many other applications to which our solution is also
applicable. Like in IDS scheme, leader election is needed
for routing [5] and key distribution [6], [10] in MANET. In
key management, a central key distributor is needed to
update the keys of nodes. In routing, the nodes are grouped
into small clusters and each cluster elects a cluster head
(leader) to forward the packets of other nodes. Thus, one
node can stay alive, while others can be in the energy-saving
mode. The election of a leader node is done randomly, based
on connectivity (nodes’ degree) or based on a node’s weight
(here, the weight refers to the remaining energy of a node
[34]). We have already pointed out the problems of random
model and connectivity model. We believe that a weightbased
leader election should be the proper method for
election. Unfortunately, the information regarding the
remaining energy is private to a node, and thus, not
verifiable. Since nodes might behave selfishly, they might
lie about their resource level to avoid being the leader if there
is no mechanism to motivate them. Our method can
effectively address this issue.
Paper Outline
The rest of this paper is organized as follows: Section 2
formulates the problem. Section 3 describes our leader
election mechanism where the cost of analysis function,
reputation model, and payment design are given. Section 4
analyzes our mechanisms against selfish and malicious
nodes. Section 5 devises the election algorithm needed to
handle the election process. Section 6 provides the proof of
correctness and security properties of the algorithm.
Section 7 presents empirical results. Section 8 reviews
related work. Finally, Section 9 concludes the paper and
discusses our future work.
PROBLEM STATEMENT
We consider an MANET where each node has an IDS and a
unique identity. To achieve the goal of electing the most
cost-efficient nodes as leaders in the presence of selfish and
malicious nodes, the following challenges arise: First, the
resource level that reflects the cost of analysis is considered
as a private information. As a result, the nodes can reveal
fake information about their resources if that could increase
their own benefits. Second, the nodes might behave
normally during the election but then deviate from normal
behavior by not offering the IDS service to their voted nodes.
LEADER ELECTION MECHANISM
In this section, we present our leader election mechanism
for truthfully electing the leader nodes. To make the paper
self-contained, the background on mechanism design is
given in Section 3.1. Section 3.2 formulates our model using
the standard mechanism design notations. To achieve the
design goal, the cost of analysis function is given in
Section 3.3 followed by the reputation system model given
in Section 3.4. Finally, the design of the payment for the
two models is given in Section 3.5.
Mechanism Design Background
Mechanism design is a subfield of microeconomics and game
theory [21]. Mechanism design uses game theory [25] tools to
achieve the desired goals. The main difference between
game theory and mechanism design is that the former can be
used to study what could happen when independent players
act selfishly. On the other hand, mechanism design allows a
game designer to define rules in terms of the SCF such that
players will play according to these rules. The balance of IDS
resource consumption problem can be modeled using
mechanism design theory with an objective function that
depends on the private information of the players. In our
case, the private information of the player is the cost of
analysis which depends on the player’s energy level. Here,
the rational players select to deliver the untruthful or
incomplete information about their preferences if that leads
to individually better outcomes [31]. The main goal of using
mechanism design [17] is to address this problem by:
1) designing incentives for players (nodes) to provide
truthful information about their preferences over different
outcomes and 2) computing the optimal system-wide
solution, which is defined according to (1).
Reputation System Model
Before we design the payment, we need to show how the
payment in the form of reputation can be used to: 1) motivate
nodes to behave normally and 2) punish the misbehaving
nodes. Moreover, it can be used to determine whom to trust.
To motivate the nodes in behaving normally in every election
round, we relate the cluster’s services to nodes’ reputation.
This will create a competition environment that motivates the
nodes to behave normally by saying the truth. To enforce our
mechanism, a punishment system is needed to prevent nodes
from behaving selfishly after the election. Misbehaving
nodes are punished by decreasing their reputation, and
consequently, are excluded from the cluster services if the
reputation is less than a predefined threshold. As an
extension to our model, we can extend our reputation system
to include different sources of information such as routing
and key distribution with different assigned weights.
CILE Payment Design
In CILE, each node must be monitored by a leader node that
will analyze the packets for other ordinary nodes. Based on
the cost of analysis vector C, nodes will cooperate to elect a
set of leader nodes that will be able to analyze the traffic
across the whole network and handle the monitoring
process. This increases the efficiency and balances the
resource consumption of an IDS in the network. Our
mechanism provides payments to the elected leaders for
serving others (i.e., offering the detection service). The
payment is based on a per-packet price that depends on the
number of votes the elected nodes get. The nodes that do not
get any vote from others will not receive any payment. The
payment is in the form of reputations, which are then used to
allocate the leader’s sampling budget for each node. Hence,
any node will strive to increase its reputation in order to
receive more IDS services from its corresponding leader.
LEADER ELECTION ALGORITHM
To run the election mechanism given in Section 3, we
propose a leader election algorithm that helps to elect the
most cost-efficient leaders with less performance overhead
compared to the network flooding model. We devise all the
needed messages to establish the election mechanism taking
into consideration cheating and presence of malicious
nodes. Moreover, we consider the addition and removal
of nodes to/from the network due to mobility reasons.
Finally, the performance overhead is considered during the
design of the given algorithm where computation, communication,
and storage overhead are derived.