The Sleep Deprivation Attack in Sensor Networks: Analysis and Methods of Defense

Abstract

The ability of sensor nodes to enter a low power sleep mode is very useful for extending network longevity. We show how adversary nodes can exploit clustering algorithms to ensure their selection as cluster heads for the purpose of launching attacks that prevent victim nodes from sleeping. We present two such attacks: the barrage attack and the sleep deprivation attack. The barrage attack bombards victim nodes with legitimate requests, whereas the sleep deprivation attack makes requests of victim nodes only as often as in necessary to keep the victims awake. We show that while the barrage attack causes its victims to spend slightly more energy, it is more easily detected and requires more effort on behalf of the attacker. Thus, we have focused our research on the sleep deprivation attack. Our analysis indicates that this attack can nullify any energy savings obtained by allowing sensor nodes to enter sleep mode. We also analyze three separate methods for mitigating this attack: the random vote scheme, the round robin scheme, and the hash-based scheme. We have evaluated these schemes based upon their ability to reduce the adversary's attack, the amount of time required to select a cluster head, and the amount of energy required to perform each scheme. We have found that of the three clustering methods analyzed, the hash-based scheme is the best at mitigating the sleep deprivation attack.

1. Introduction

Power management is a major research issue in sensor networks, given that sensor nodes are constrained to operate upon limited battery supplies. In general, the total energy consumption of a sensor node can be categorized into the following three groups: 1) energy spent on computations, 2) energy used to communicate, and 3) energy spent as a result of the node's sleeping patterns. In this paper we focus on the ability of sensor nodes to enter a low power sleep mode for the purpose of extending the longevity of the network. It is widely accepted that this is an important issue, as sensor nodes spend most of their time in sleep mode, allowing the overall lifetime of the node to be greatly extended [3, 8, 11, 17, 28, 30].

The ability of sensor nodes to enter a sleep mode becomes a serious concern for sensor networks deployed in unattended and hostile environments. Limited tamper resistance inherent to a low cost sensor node leaves the node vulnerable to being compromised by an adversary [8, 9, 36]. Through compromised nodes, an adversary may launch security attacks against the sensor network ranging from the physical layer to the application layer. Due to the vast variety and novelty of attacks, we believe no single solution can address all the attacks. As such, we limit our work to addressing a specific type of attack aimed at disrupting the power management protocol in sensor applications such as target tracking.

We present two attacks that prevent victim nodes from sleeping: the barrage attack and the sleep deprivation attack. In the barrage attack, the victim is barraged with seemingly legitimate requests; however, the purpose of these requests is to waste the victim's limited power supply by causing it to stay out of its sleep mode and perform energy intensive operations. In the sleep deprivation attack, the malicious node makes requests to victim nodes only as often as is necessary to keep the victims awake. Thus victim nodes are kept awake, but are not made to perform energy intensive operations as is the case in the barrage attack. From our analysis, we have found that while the barrage attack causes its victims to spend slightly more energy, it is more easily detected and requires much more effort on behalf of the attacker. For these reasons, we have focused our research on the sleep deprivation attack.

To further analyze the sleep deprivation attack, we have used a clustering based target tracking network as the basis for our analytical model. It was the decision of the authors to utilize a specific application rather than a more general model in order to grant the reader further insight into the mechanisms of the sleep deprivation attack. Note that while our analysis was done based upon a particular implementation of target tracking, our results are readily applicable to any clustering based sensor network application. We show that for one set of network parameters, an adversary can double the power consumption of a 400 node network with as few as 20 compromised nodes. Further, we show that a single adversary node can simultaneously attack as many as 150 victims and still outlive its victims.

Given the detrimental effect of the sleep deprivation attack, we have analyzed three separate defense mechanisms to mitigate this attack: the random vote scheme, the round robin scheme, and the hash-based scheme. We have evaluated these schemes based upon their ability to mitigate the adversary's attack and the amount of time required to select a cluster head. We have found that of the three clustering methods analyzed, the hash-based scheme is the best at mitigating the sleep deprivation attack. Given the viability of the hash-based scheme, we have also analyzed the amount of energy it requires to select a cluster head.

The remainder of this article is organized as follows. In Section 2 we discuss related works. In Section 3 we introduce the framework used to perform our analysis. In Section 4 we compare the barrage attack and the sleep deprivation attack. In Section 5 we further analyze the sleep deprivation attack and in Section 6 we discuss methods to mitigate this attack. In Section 7 we make our conclusions.

2. Related Work

2.1 Sleep Deprivation Attack

The idea of the sleep deprivation attack was first proposed by Stajano [32, 33]. The victim of this attack is a battery powered computing device, such as a sensor node, which attempts to remain in a low power sleep mode for as long as possible without adversely affecting the nodes' applications. The attacker launches a sleep deprivation attack by interacting with the victim in a manner that appears to be legitimate; however, the purpose of the interactions is to keep the victim node out of its power conserving sleep mode. Thus, this attack can be used to dramatically reduce the lifetime of the victim. Further, this attack is difficult to detect given that it is carried out solely through the use of seemingly innocent interactions.

The work by Krishnaswami is one of the few works that has attempted to quantify the impact of sleep deprivation attacks on energy-constrained devices [22]. The approach used by Krishnaswami consisted of measuring the difference between the average power consumption of laptops and PDAs while the devices were idle (but not in sleep mode) and when the devices were under attack. We find Krishnaswami's approach to be overly simplistic in how devices were attacked. The adversary gives the victim a task that is specifically designed to burn inordinately large amounts of energy. Such an attack could be easily detected given that sensor nodes are by necessity, very diligent about their power management. We claim that a much more difficult to detect attack would be to have the adversary focus on keeping the victim out sleep mode, rather than try to have the victim actively processing.

2.2 Cluster Head Selection

In sensor networks, clustering is used to organize sensor nodes into groups based in part on their physical proximity [8]. One of the nodes in the cluster is delegated the task of being the cluster head. The main benefit of clustering is that it enables data fusion [4], whereby redundant data is pruned from the network. In the case of target tracking, several nodes may detect the same target. It is wasteful for each of these sensor nodes to transmit identical tracking information to a centralized data processor. A more efficient solution is to have a group of nodes perform local processing of sensor data and transmit a single message.

In the clustering algorithm proposed in [10], clusters are formed by having each sensor node wait a random amount of time. If a node has not had the opportunity to join a cluster after this random amount of time, then it can declare itself to be a cluster head and subsequently start soliciting neighboring nodes to join its cluster. To maintain the cluster, the cluster head will select its own successor. We foresee two vulnerabilities with this approach. First, during cluster formation, an adversary could ensure its selection as cluster head by immediately soliciting other nodes to join its cluster. Second, once an adversary node has been selected as cluster head, it can remain cluster head indefinitely by never selecting a successor. Consequently, this approach readily allows an adversary to launch a sleep deprivation attack.

In [1], each node declares itself a cluster head with a probability p. Each cluster head will then solicit any other node within k hops to join its cluster. Nodes receiving multiple solicitations join the closest cluster available. A node that has not received a cluster solicitation within a certain amount of time will then declare itself to be a cluster head, and will solicit other sensor nodes within k hops to join its cluster. Clearly this algorithm is vulnerable to a sleep deprivation attack by allowing a malicious node to simply declare itself a cluster head.

There are many other distributed clustering algorithms and sensor network applications that rely upon clustering (e.g. [1, 2, 12, 14–16, 19]), each of which assumes that participating nodes will act honestly. Thus, an adversary can exploit each of these algorithms to ensure its selection as cluster head. Given that clustering is a widely used algorithm, it is crucial to make it secure.

2.3 Target Tracking

For didactic purpose, we pose our discussion of the sleep deprivation attack within the context of a sensor network executing a distributed clustering target tracking application; however, our results are more generally applicable to any algorithm that relies upon clustering.

Target tracking research has focused on such issues as increasing the fidelity of sensor data, reducing redundant data, and reducing energy consumption. Since many of these algorithms [13, 25, 27, 31, 37–39] rely on a trusted cluster head, they are all susceptible to the sleep deprivation attack.

3. System Modelling

3.1 Model Assumptions

3.1.1 Node and Network Characteristics

We consider the placement of sensor nodes to be spread uniformly at random throughout a square region. The sensor nodes operate on non-renewable batteries; once a node exhausts its battery it is considered to be dead. To preserve their battery power, sensor nodes will cycle in and out of a low-power sleep state.

We assume the presence of a publish/subscribe routing protocol [18, 20]. A publish/subscribe protocol has two network primitives, a publish method and a subscribe method. The subscribe method is used by individual nodes to indicate their desire to receive data fitting a specified description. In our model, sensor nodes subscribe to all track records within z meters of their position. When a local group of nodes detects a target they will share sensor readings. One of these nodes is then elected as cluster head. This node aggregates the sensor data on behalf of the cluster and forms a track record. The track record is sent to all subscribed nodes by repeatedly invoking the publish method. The publish method is invoked one time for each subscribed node. For simplicity, we assume that track records are sent reliably (i.e., a track record will always reach its recipient node despite network errors or sleeping sensor nodes).

We assume a homogeneous network, where a cluster head is identical to any other node in the cluster in terms of capacity and resources. For simplicity we shall assume that nodes within the same cluster can communicate directly. This assumption could be relaxed by allowing multihop communication.

3.1.2 Security Assumption and Attack Model

We assume that sensor nodes do not have significant tamper resistance. Thus, an adversary is capable of compromising sensor nodes [8, 9, 36]. That is, the adversary can obtain data, keys, and the code inside compromised nodes. To launch attacks, the adversary reprograms the compromised nodes with malicious code and then redeploys them into the network. Compromised sensor nodes may launch attacks in different layers in the protocol stack, e.g., channel jamming in the physical layers [36], disrupting the collaboration of sensor nodes in the MAC layer protocol [7, 23, 29], attacking the routing protocol [21], jeopardizing the localization service [6, 24], or the sensor data [34]. Due to the diversity and novelty of attacks, no one-for-all solution exists. All of the aforementioned attacks have been addressed separately. As such, although compromised nodes (including cluster heads) may launch various attacks, in this work we limit our focus to identifying, analyzing, and defending against the attacks that specifically target the network's power management protocols.

We assume each sensor node is assigned a unique ID prior to deployment. Further, sensor nodes cannot impersonate uncompromised nodes. Preventing impersonation could be accomplished by requiring every node to authenticate its messages using pairwise keys shared with receiver nodes [26, 40]. This assumption ensures that a compromised node can only submit a single vote in a cluster head selection algorithm, such as the algorithm described in Section 6.3.

We consider the placement of adversary nodes to be uniformly random; this reflects the adversary's desire to spread its nodes in order to maximize their impact. In this article the terms malicious nodes and adversary nodes are synonymous to such compromised nodes.

3.2 Sensor Node States

To help quantify the impact of an adversary attack we have partitioned the nonadversary sensor nodes into three separate states: sleep, idle, and receive (note that the lack of a transmit state reflects the fact that nonadversary nodes do not generate network traffic in our model; we have made this assumption to help illuminate the impact of an adversary attack better). As Table 1 indicates, the state of a sensor node is defined by the status of its CPU and wireless radio. Accordingly, we consider the behavior of sensor nodes to cycle between the sleep state and the idle state, staying in each state for fixed time quantums. A sensor node in the idle state will enter the receive state upon receipt of a track record. This will only occur when the sensor node is subscribed to an adversary node. Once a sensor node has received a track record it will stay in idle mode for an extended period of time.

TABLE 1

Nonadversary Node State Space

Mode	CPU Status	Radio Status
Sleep	Sleep Mode	Off
Idle	On	Standby
Receive	On	Receiving

Similarly, we have partitioned the adversary nodes into two states: sleep, and transmit. Table 2 indicates the status of the CPU and wireless radio for each state. In order for an adversary node to maximize its energy, it will transmit track records to each of its subscribed nodes in rapid succession and then go to sleep.

TABLE 2

Adversary Node State Space

Mode	CPU Status	Radio Status
Sleep	Sleep Mode	Off
Transmit	On	Transmitting

To make our analysis realistic we have used values taken from actual sensor node specifications as seen in Table 3. We were able to obtain actual values for power, data rate [8], and packet size [5]. Given symmetric upload and download speeds for each link, we derived t _rs , the time required to send or receive a packet. The timing values in Table 3 (t _a , t _ar , and t _slp ) are based upon ongoing experiments being performed at our lab.

TABLE 3

Model Parameters

Param	Value	Description
P idle	300 mW	Power in idle mode
P slp	1 mW	Power in sleep mode
P rcv	440 mW	Power in receive mode
P snd	510 mW	Power in send mode
R	10 kbps	Data transmission rate
T size	296 bytes	Track record size
t rs	236.8 ms	Time to send/receive track record
t idle	1 s	Time spent in idle mode
t ar	60 s	Time spent waiting for a target
t slp	1 s	Time spent in sleep mode

In Fig. 1 we illustrate what we consider normal sensor node behavior when no tracking is occuring. A sensor node alternates between sleep mode for t_slp seconds and idle mode for t_idle seconds.

In Fig. 2 we illustrate the behavior that a sensor node would exhibit upon receiving a single track record (represented pictorially by “TR” in the figure). Initially the sensor node is alternating between sleep and idle states, until its idle state is cut short by receipt of a track record. After t_rs seconds, the node has received the entire track record and has determined that a possible target is coming its way. After waiting t_ar seconds for a target, the node determines it is safe to go back to sleep. At this point the node resumes the behavior exhibited by Fig. 1. There are three important observations to note. First, only a cluster head will generate a track record. Second, a track record is the only message that will interfere with a sensor node's sleep cycle. Third, t_ar is much larger than is depicted in Figs. 2 and 3.

FIGURE 1

Timing diagram of normal node behavior when no tracking is occurring.

FIGURE 2

Timing diagram of normal node behavior after receiving track record.

FIGURE 3

Timing diagram of node under sleep deprivation attack.

Figure 3 illustrates a sensor node being victimized by a sleep deprivation attack. The attacker sends the victim a track record every t_ar + t_rs seconds. Each time the victim is just about to decide that it can go to sleep mode, it receives another track record. Thus the victim is kept perpetually awake.

Figure 4 shows a sensor node that is under a barrage attack. Notice that the adversary sends the victim track records as rapidly as possible (i.e., every t_rs seconds).

FIGURE 4

Timing diagram of node under barrage attack.

4. Comparison of Sleep Deprivation Attack and Barrage Attack

In this section we explain the tradeoffs between the sleep deprivation attack and the barrage attack. Further, we explain why the sleep deprivation attack would be the preferable method of attack from the perspective of the attacker.

In both the sleep deprivation attack and the barrage attack the victim will never enter its low power sleep mode. The difference between the two attacks is that the victim of a barrage attack will be actively performing work, whereas the victim of a sleep deprivation attack will, for the most part, remain idle. In this section we investigate the difference between these two attacks based upon the following: 1) the victim's power consumption, 2) detectability of the attack, and 3) the power required of the adversary.

4.1 Power Consumption of Victim

Consider the following scenario. A particular sensor node cycles in and out of its low power sleep mode. The proportion of time that the sensor node is asleep versus awake is denoted by the variable x. This sensor node has been given a small workload, thus it spends 300 mW in idle mode and 1 mW in sleep mode, giving the following equation denoting the sensor node's average power consumption in mW:

$$300(1-x)+1x.$$

(1)

Thus this node spends 1 mw of power when x = 0 and it spends 300 mw of ow power when x = 1.

Now consider if this same node was victimized by a sleep deprivation attack or a barrage attack. In the sleep deprivation attack, the adversary will interact with the sensor node intermittently so that it will never go to sleep, thus the victim will spend an average of 300 mW of power. Alternatively, if the adversary was to utilize a barrage attack, the victim will be constantly receiving messages, causing it to spend 440 mW of power. Clearly the victim of a sleep deprivation attack spends slightly less power than the victim of a barrage attack. It is also clear that the relative impact of either attack is directly proportional to x.

4.2 Detectability

An energy draining attack must remain undetected for as long as possible in order to waste a maximum amount of energy. An easily detected attack allows the victim to rapidly take remedial action, such as ignoring the requests of a detected attacker, before the attack can cause significant damage.

We speculate that the sleep deprivation attack would be much more difficult to detect than the barrage attack based on the observation that it generates messages at relatively infrequent rate. Using the parameters in Table 3, the barrage attack requires 254 messages to be sent every minute, whereas the sleep deprivation attack only requires a single message to be sent.

4.3 Energy Required of Attacker

Since the adversary nodes are compromised sensor nodes, they would be more likely to perform an attack that can cause a lot of damage without requiring a lot of energy to perform.

In a barrage attack the adversary has to transmit a network message every t_rs seconds, whereas in sleep deprivation attack the adversary only has to generate a network message every t_rs + t_ar seconds. Thus, the adversary has to spend a lot more power to launch the barrage attack. Considering that the adversary could simultaneously launch sleep deprivation attacks upon multiple sensor nodes for less power consumption than would be required to launch a barrage attack on a single node, it seems likely that the battery-constrained adversary nodes would prefer the sleep deprivation attack.

5. Sleep Deprivation Attack

In Section 4 we showed that the sleep deprivation attack is a serious threat to a sensor network given that it nullifies any energy savings that would have been obtained by the victim's low power sleep mode. In this section we illustrate how an adversary can utilize the security vulnerabilities inherent to distributed cluster formation for the purpose of launching a sleep deprivation attack. We show that the sleep deprivation attack can as much as double the overall power consumption of a 400 node network. Further, we find that this can be accomplished with as few as 20 adversary nodes.

To quantify the impact of this attack we measure the average node's power consumption. This is a useful metric because it measures the network-wide impact of the adversary's attack. As a point of clarification, only the power consumption of non-adversary nodes will be measured in this metric.

5.1 Derivation of Model

We now derive the equations that we have used to analyze the impact of the sleep deprivation attack.

5.1.1 Probability of Subscribing to an Adversary Node

Using a geometric argument, the probability that a sensor node will be subscribed to an adversary cluster head, given that each node is deployed in a square region of length L and each node subscribes to all track records within a radius of size z < L, is:

$$(\pi z^2)/L^2.$$

(2)

The complement of this equation gives the probability that a sensor node is not subscribed to a particular adversary node. Given C, adversary nodes with uniformly random placement, the probability that a given node will be subscribed to at least one malicious cluster head is:

$$p=1-(1-(\pi z^2)/L^2{)}^C.$$

(3)

Note that this analysis will be slightly skewed due to fringe effects. Nodes on the edges of the network are less likely to be in contact with a adversary cluster head. However, only for small networks will these fringe effects be substantial, and thus we shall ignore their effects in our analysis.

5.1.2 Power Consumption of Nonadversary Nodes

To determine the average node's power consumption we have partitioned sensor nodes into two groups: those that are subscribed to adversary cluster heads and those that are not.

Nodes that are not subscribed to an adversary cluster head alternate between the idle state for t_idle seconds and the sleep state for t_slp seconds. Thus, the rate that these nodes expend energy is:

$$P_{nrm}=\frac{t_{idle}\hspace{0.17em}{P}_{idle}+t_{slp}\hspace{0.17em}{P}_{slp}}{t_{idle}\hspace{0.17em}{t}_{slp}}.$$

(4)

Nodes that are subscribed to an adversary cluster head alternate between an extended idle state for t_ar seconds and the receive state for t_r seconds. Thus, nodes subscribed to a malicious cluster head expend energy at the following rate:

$$P_{atk}=\frac{t_{ar}\hspace{0.17em}{P}_{idle}+t_{rs}\hspace{0.17em}{P}_{rev}}{t_{ar}\hspace{0.17em}{t}_{rs}}.$$

(5)

Utilizing the equations for p, P_nrm, and P_atk, it is straightforward to attain the average power consumption for non-adversary nodes:

$$P_{avg}=p{P}_{atk}+(1-p)P_{nrm}.$$

(6)

5.1.3 Power Consumption of Adversary Nodes

Assume each adversary node goes through two states: first it sends out a track record to each of its subscribed nodes and then it sleeps. Adversary nodes send these messages as rapidly as possible in order to maximize sleep time. This is modeled by each adversary node sending x such messages to x victim nodes. As Fig. 3 indicates, the victims have to receive track records every t_ar + t_rs seconds to be coerced into staying out of sleep mode. Thus, the adversary spends xt_rs seconds sending messages and t_ar + t_rs — xt_rs seconds sleeping. Therefore, the total power required of the adversary is:

$$P_{adv}=\frac{x{t}_{rs}{P}_{snd}+(t_{ar}+t_{rs}-x{t}_{rs})P_{slp}}{t_{ar}+t_{rs}}.$$

(7)

5.1.4 Impact of Attack

Figure 5 illustrates the effect of malicious nodes on a network containing 400 legitimate nodes for different subscription radii (i.e., z). Our results indicate that as more malicious nodes are inserted, the average power consumption increases asymptotically to P_idle, meaning that at some point every sensor node will never go to sleep. We have also observed that it is desirable to keep z as small as possible to minimize the effect of malicious nodes. Unfortunately, this also reduces the ability of tracking nodes to give each other advance notice of a potential target. Thus, a network designer should carefully consider the implications of selecting a particular subscription radius.

FIGURE 5

Effect of subscription radius in sleep deprivation attack.

5.1.5 Feasibility of Attack

To show that the attack is viable for an adversary to perform, we utilize the equation for P_adv to show the energy required for the attacker to launch the attack. In Fig. 6 we have plotted the energy required of an adversary node to attack various numbers of victims. From our analysis, an adversary node could simultaneously attack up to 150 nodes before its power consumption became higher than that of its victims, and thus from a power perspective this attack does not require the attacker to expend a great deal of energy. Therefore, we conclude that the sleep deprivation attack enables the adversary to cause a lot of damage without expending a lot of effort.

FIGURE 6

Energy required for attacker to launch attack upon differing numbers of victims.

6. Secure Cluster Head Selection

We have shown that the sleep deprivation attack greatly increases the sensor network's power consumption without requiring excessive power to be consumed by the adversary. To launch this attack, the adversary nodes must become cluster heads, which we have shown to be exceptionally easy. In this section we propose several algorithms that make it much more difficult for the adversary to become a cluster head, and consequently, these techniques greatly reduce the impact of the sleep deprivation attack. We assume adversary nodes are interested in increasing their chances at becoming cluster heads. Thus, we do not consider an attack where the adversary intentionally delays cluster head selection.

6.1 Random Vote Cluster Head Selection

We have observed that clustering algorithms rely on the honesty of all participating nodes, allowing a malicious node to generate false information to ensure its selection as cluster head. The random vote scheme counteracts this characteristic by randomizing cluster head selection.

6.1.1 Overview of Random Vote Scheme

A group of local nodes using the random vote scheme form a cluster by performing the following steps:

Each node locally broadcasts its unique ID.

Each node uses a pseudorandom number generator to pick the ID of the local node it desires to become the next cluster head.

Nodes locally broadcast the ID of their desired cluster head.

Each node repeats step 2 until a single node attains a majority of votes. This node will become the next cluster head.

Each sensor node is only allowed to cast one vote at a time. However, in the case of a tie, the nodes will restart the algorithm at step 2. We refer to the execution of steps 2 through 4 as a round or iteration. Thus, the random vote algorithm is potentially composed of several rounds.

6.1.2 Analysis of Random Vote's Effectiveness at Increasing Attack Tolerance

For simplicity we have assumed that the N legitimate nodes and the C compromised nodes in the network have been evenly divided into G clusters. Thus, we assume that there are n legitimate nodes per cluster and c malicious nodes per cluster.

To determine the effectiveness of the random vote scheme, we have derived an equation indicating the probability that any of the malicious nodes in the cluster will be selected as cluster head, given that i out of n nonmalicious nodes have voted for it. The adversarial nodes in the local cluster wait until all other nodes have voted so that they can all vote for the adversary node that currently has the most votes. The probability that this node attains a majority of the n + c votes is modeled with a binomial distribution as follows:

$$p_{rand,c}=\sum _{i=\left[\frac{n+c}{2}\right]-c+1}^n(\genfrac{}{}{0ex}{}{n}{i}){\frac{1}{n+c}}^i{(1-\frac{1}{n+c})}^{n-i}.$$

(8)

Similarly, the probability that any of the n nonadversary nodes are selected as a cluster head is:

$$p_{rand,n}=(\genfrac{}{}{0ex}{}{n}{1})\sum _{i=\left[\frac{n+c}{2}\right]+1}^n(\genfrac{}{}{0ex}{}{n}{i}){\frac{1}{n+c}}^i{(1-\frac{1}{n+c})}^{n-i}.$$

(9)

The equations for p_rand,c and p_randy,n are only for a single iteration of the algorithm. We utilize the three state Markov chain in Fig. 7 to determine the probability of either an adversary node or a non-adversary node being elected once the algorithm has completed. In this figure, the states s_c and s_n represent the selection of a malicious node as cluster head and selection of a legitimate node as cluster head respectively. State s_u represents any intermediate iterations where the algorithm fails to select a cluster head. Further, s_u is also the initial state of the algorithm. We denote the steady state probability that a legitimate node is selected as cluster head as p_rand,n′ and the steady state probability that an adversary node is selected as cluster head as p_rand,c′.

FIGURE 7

Markov chain representation of random selection of cluster heads.

In an argument similar to what was used to formulate p, the probability of a legitimate node being subscribed to at least one cluster containing adversary nodes is:

$$p^{\prime }=1-{(1-\frac{\pi z^2}{L^2})}^{\frac{C}{c}}.$$

(10)

The product of p_rand,c and p′ gives the probability that a legitimate node is subscribed to an adversary cluster head. Using this product, the network's average power consumption is:

$$P_{avg,rv}=p^{\prime }{p}_{rand,c}{P}_{atk}+(1-p^{\prime }{p}_{rand,c})P_{nrm}.$$

(11)

Without any defense mechanism in place, a malicious node is selected as cluster head with a probability of 1. In Fig. 8 we illustrate p′ as a function of the number of compromised nodes in the cluster (c) and the total number of nodes in the cluster (n + c). This graph shows that, given a single adversary node in a cluster, the random vote scheme nearly halves the probability that the adversary node will be selected as cluster head. However, this probability jumps to nearly 1 when multiple adversary nodes are located in the same cluster. It may startle the reader to see that when n + c is even the adversary appears to have a better chance of becoming a cluster head. This is a direct result of the difference between attaining a majority for odd and even numbers.

FIGURE 8

Probability that the random vote scheme selects an adversary cluster head.

In order for this algorithm to be complete, any of the n + c nodes in the local cluster must attain a majority of the votes, otherwise the nodes will keep voting. We can model this phenomenon using expected value as follows:

$$I=\sum _{x=1}^{\mathrm{\infty }}x(p_{rand,n}+p_{rand,c}){(1-p_{rand,n}-p_{rand,c})}^{x-1}=\frac{1}{p_{rand,n}+p_{randmc}}.$$

(12)

In Fig. 9 we utilized equation I to investigate the amount of time the random vote algorithm requires to complete when we vary the parameters n and c. If a vote message is represented in 30 bytes, it would take about 24 ms to transmit a single vote. Since each round requires n + c votes, this graph indicates that the random vote algorithm requires an acceptable amount of time to complete for moderate sized clusters (i.e., n < 7). However, for clusters where there are more than 7 nodes, the algorithm incurs too much latency. For example, when there are 10 nodes in the cluster, the algorithm would require an average of 166s to complete.

FIGURE 9

Time required for random vote algorithm to complete.

6.2 Round Robin Cluster Head Selection

The lack of scalability in the random vote clustering algorithm of Section 6.1 caused us to consider another approach to secure cluster formation. The round robin scheme is based on the observation that if each node maintained more state, i.e., if clusters were maintained for long periods of time, a more scalable solution would be possible. With such a scheme, cluster heads could be elected in a round robin fashion.

The round robin scheme operates in two phases. The first phase is a bootstrapping phase where the initial clusters are formed. The second phase is a maintenance phase, during which the precise membership of each cluster is updated due to node mobility, addition of new nodes to the network, and removal of nodes from the network.

6.2.1 Analytical Model

Assuming an average of c adversary nodes and n legitimate nodes in each cluster, the proportion of time that the c adversary nodes can launch a sleep deprivation attack from a particular cluster is:

$$p_{c,rr}=\frac{c}{c+1}.$$

(13)

In Fig. 10 we have used the equation for p_c,rr to see how likely the round robin scheme is to elect an adversary cluster head. Comparison of Figs. 10 and 8 illustrates that the round robin scheme makes it much more difficult for the adversary to become a cluster head. In fact, the adversary nodes are just as likely to become a cluster head as is any other node.

FIGURE 10

Probability that round robin scheme selects an adversary cluster head.

A nice property of the round robin scheme is that it only requires a single iteration to select a cluster head. Each node must keep track of exactly which nodes are in the cluster and which node is the current cluster head. Thus, when a new cluster head is needed, each node can independently determine who the new cluster head should be. However, this scheme requires that each sensor node must maintain a list indicating which nodes are in its cluster at all times. Such a list would require an unrealistic amount of per-node storage for larger clusters.

6.3 Hash-Based Cluster Head Selection

The lack of scalability that daunts the random vote scheme in Section 6.1 and the excessive overhead inherent to the round robin scheme in Section 6.2 motivated us to come up with the hash-based cluster head selection scheme, which we shall call the hash-based scheine for brevity. This scheme performs dynamic clustering in an attack and fault tolerant manner without excessive overhead.

6.3.1 Hashed Clustering Overview

In this scheme, each node generates a random number and then broadcasts their number's hash. This allows each node to commit to their particular number without revealing it until all participating nodes have likewise committed. This process ensures that a cluster head is selected at random, so long as there is at least one “honest” node participating in the algorithm.

To prevent a malicious node from claiming to be multiple nodes, we assume that every message has been authenticated using an authenticated broadcast scheme such as μTESLA [26].

The hash algorithm operates by having each participating node execute the following steps:

Generate an integer, r_i, using a pseudorandom number generator and locally broadcast a commit message of the form 〈ID, H (ID, r _i )〉, where ID denotes the node's identifier and H (·) denotes a fixed length collision-resistant hash function.

Wait for enough time to pass, T_o, that it is sufficiently unlikely that any more commit messages will be received. Then locally broadcast a list message 〈(ID₁, &, ID_Y)〉, where (ID_t, &, ID_Y) is a list of all IDs extracted from step 1, including the nodes own ID as well.

For each list message received, verify that the local list of IDs is the same as the received list of IDs. Send a request commit message to any node whose ID is listed in another node's list message, but is not listed in the node's own list of IDs: 〈ID_dest〉.

For each request commit message received whose ID_dest field matches the node's own ID, reply by repeating the original commit message.

Wait for T_o seconds to pass. Then locally broadcast a reveal message, to disclose r _i : 〈ID, r _i 〉.

Verify each r _i with its associated commit message.

Wait for T_o seconds to pass. If any reveal messages have not been received, transmit a request reveal message: 〈H (ID, r _i )〉.

Any node that has a verified r _i can respond to a request reveal message.

Given Y participating nodes, the cluster head will be the node whose ID matches the following result:

$$Mod(\left(\sum _{i=1}^Y{r}_i\right),Y)+1$$

The key observation regarding the security of this scheme is that every participating node must send out its commit message prior to receiving any reveal messages. This can be ensured with a high likelihood by selecting a sufficiently high value for T_o. Alternatively, this security could be guaranteed by building a communication scheme that is amenable to sensor networks and provides end-to-end reliability by utilizing current research efforts [30, 35].

6.3.2 Likelihood of an Adversary Cluster Head

In this section we analyze the likelihood of an adversary node being elected cluster head in the hash-based scheme.

Notice that the output of the hash-based scheme (i.e., step 9) will be a random integer so long as at least one of the participating nodes is not an adversary node. This is because a random number added to a nonrandom number yields a random number. Thus, the malicious nodes will not affect the random output of the hash-based scheme by colluding. As the following equation indicates, the probability that a adversary node is selected to become a cluster head is the same as any node in the cluster:

$$p_{c,h}=\frac{c}{c+n}.$$

(14)

Notice that the probability that an adversary becomes cluster head in the hash-based scheme is the same as in the round robin scheme (i.e., p_c,h = p_c,rr). Thus, Fig. 10 also applies to the hashed-based scheme.

6.3.3 Algorithm Latency

In this section we derive a timing model to show that the hash scheme is capable of forming clusters in a reasonable amount of time. Consider the hashing scheme within the context of a simple communication model, where R is the rate at which data can be transmitted and the total number of nodes that are participating in the algorithm is n + c. In the hash algorithm, each of the n + c nodes must generate a commit, list, and a reveal message. The total amount of time spent transmitting n + c packets, each of which contains M_size bits, is:

$$T_{sndV}=(n+c).\frac{M_{size}}{R}.$$

(15)

The probability that a given message is not received by at least one of the n + c − 1 other nodes is p_e. In this case, the node will have to retransmit the message. The average number of times a given message is transmitted until it is correctly received by all interested nodes is approximated as:

$$N_{rsnd1}=+\sum _{i=1}^{\mathrm{\infty }}{ip}_e^i=1+\frac{p_e}{{(p_e-1)}^2}.$$

(16)

Each of the n + c nodes generates a single commit message and a single reveal message. To account for reliable transmission, each of these messages will be transmitted an average of N_rsndl times, giving the total number of commit messages and reveal messages as:

$$N_{rComAll}=N_{rRevAll}=(n+c).N_{rsnd1}.$$

(17)

There is sufficient redundancy in having each node generate a list message, that we assume each unreceived commit and reveal message will be detected. Each node transmits its list message only once. Thus, N_ListALL, the total number of list messages generated, is n + c.

Each commit and reveal causes a request message with probability p_e. Thus, the average number of request commit messages and request reveal messages is:

$$N_{rRRAll}=p_e.N_{rRevAll}=N_{rRCALL}=p_e.N_{rComAll}.$$

(18)

The sum of all commit, reveal, list, request commit, and request reveal messages gives N_rsndALL, the total number of packets transmitted by n + c nodes on average. Given a transmission rate of R, the total time spent by n + c nodes communicating a total of N_rsndAll packets is:

$$T_{rsndAll}=\frac{N_{rsndAll}\cdot M_{size}}{r}.$$

(19)

We estimate T_o with the amount of time required to reliably transmit n + c messages:

$$T_o\approx \frac{(n+c)\cdot N_{rsnd1}\cdot M_{size}}{R}.$$

(20)

While not included in our model, the actual value for T_o also depends upon the expected size of a cluster, which is dependent upon sensor range and the density of nodes in the network. Further, the time spent waiting in step 2 would be slightly less than it would be in steps 5 and 7 as there are not retransmissions occurring during step 2. Since there are three points in which the nodes wait for a time period of T_o, and we have the total time spend communicating, the total time spent by the algorithm is:

$$T_{total}=3\cdot T_o+T_{rsndAll}.$$

(21)

In Fig. 11 we used the equation for T_total to illustrate the time that could be expected for the hash-based algorithm to execute. Each grouping of six bars corresponds to a different choice of p_e and M_size. In order rom left to right, we have used (p_e = .1, M_size = 400). (p_e = .01, M_size = 400), (p_e = .1, M_size = 300), (p_e = .01, M_size = 300). Within each grouping we varied the number of nodes within the cluster (i.e., n + c) from 5 to 10. We do not consider which nodes amongst these n + c nodes are adversary nodes, as doing so does not change the amount of time the hash-based algorithm requires to complete. The most important feature that this figure indicates is that the amount of time required to select a cluster head in the hash-based scheme scales linearly with the number of nodes in the cluster. Thus, this approach is scalable. We also note that even with a very high error probability (i.e., p_e = .1) our scheme completes in a reasonable amount of time.

FIGURE 11

Time required for hash-based scheme to select a cluster head.

6.3.4 Determining Energy Consumption

To determine the energy consumed by the hash scheme, we perform an average case analysis upon a single node. Note that we assume that communication energy dominates computational energy.

Given that a sensor node on average transmits a total of N_rsndAll/ (n + c) messages, the total energy that a node expends transmitting is:

$$E_{trans}=P_{snd}\cdot \frac{T_{rsndAll}}{n+c}.$$

(22)

We assume that a node not sending a message is actively listening to the network: and the amount of energy spent receiving is:

$$E_{rcv}=(T_{total}-T_{rsndAll})\cdot P_{rcv}.$$

(23)

Thus, the total energy spent by a single node in the hash algorithm is:

$$E_{total}=E_{rcv}+E_{trans}.$$

(24)

In Fig. 12 we have utilized equation E_total to determine the energy required for a node participating in the cluster head selection algorithm. This graph uses the same data points used in Fig. 11, except the y-axis of this graph refers to the total energy expended by a single node participation in cluster head selection. We can see from this graph that the hash-based scheme does not require excessive energy consumption on behalf of participating nodes, and thus is amenable for use in sensor networks.

FIGURE 12

Per-node energy required for hash-based scheme to select a cluster head.

7. Conclusions

In this paper we have shown a novel attack that an adversary can exploit upon sensor network applications that utilize distributed clustering. This attack, called the sleep deprivation attack, exploits the fact that conventional clustering algorithms rely upon the honesty of participating nodes. Thus, a malicious node can ensure its selection as cluster head, and consequently, it can launch a sleep deprivation attack against the network. In this attack, a malicious cluster head sends vietim nodes seemingly legitimate messages; however, the purpose of these messages is to keep its victims out of their low power sleep mode. The end result of this attack is greatly reduced node lifetime, potentially partitioning the network into disjointed pieces.

We also explain why an adversary would utilize a sleep depriation attack, by comparing it to a more aggressive attack where the victim nodes are barraged with requests. We have found that the sleep deprivation attack is attractive (from the perspective of an attacker) due to its low cost in terms of energy and communication. Further, this attack is not readily detected.

Given the dire consequences of this attack, we have proposed three schemes by which its impact can be reduced: 1) the random vote scheme, 2) the round robin scheme, and 3) the hashed-based scheme. We have found that the hashed-based scheme is superior to the other two methods in terms of resilience towards attack and required overhead.