Sage Journals: Discover world-class research

Abstract

Existing end-to-end security mechanisms are vulnerable to path-based denial of service attacks (PDoS). If checking integrity and authenticity of a message is done only at the final destination, the intermediate nodes are going to forward bogus packets injected by an adversary many hops before they are detected. Therefore, the adversary can easily overwhelm intermediate nodes by bogus or replayed packets. This attack exhausts the nodes along the path. In addition, other downstream nodes that depend on the exhausted nodes as intermediate nodes will be isolated, and they have to find alternative paths. Regarding broadcast traffic that originated from the base station, if packets were injected by an adversary, the whole network's nodes will be exhausted. Therefore, there is a need to enable intermediate nodes to filter out bogus packets. We adopted a link layer security scheme to enable en route intermediate nodes to filter out any bogus or replayed packet as soon as it is injected into the network. Our scheme can handle different types of traffic. Simulation results show that our algorithm outperforms the one-way hash chain (OHC) algorithm and that it is more scalable.

1. Introduction

With the rapid development and wide application of wireless sensor networks (WSN), more and more security problems are emerging. Due to the unique characteristics and challenges in WSN, traditional security techniques used in traditional networks cannot be directly applied. First, sensor devices are limited in their energy, computation, and communication capabilities. Second, sensor nodes are often deployed in accessible areas which make the sensors vulnerable to physical attacks. Third, since the communication medium in WSN is a broadcast wireless medium, adversaries can easily eavesdrop on, intercept, inject, and alter transmitted data. Moreover, adversaries can overwhelm intermediate nodes with bogus or replayed packets to drain their batteries and waste network bandwidth. In addition to that, the adversary can make the victim node store invalid information to exhaust its memory and, therefore, leave no room for storing useful information.

In the case of wireless medium and due to physical constraints of sensors, a security threat can be classified as a path-based denial of service attack (PDoS). In PDoS, an adversary overwhelms sensor nodes by flooding a multihop communication path with either replayed packets or injected spurious packets. Consequently, the energy of the victim nodes will be exhausted. The bogus packets may be dropped out by the end destination if there are sequencing and authentication data in the packets, but after attacking the whole path. A PDoS attack in broadcast traffic affects the whole network; if an adversary is close to the base station and sends malicious packets on behalf of the base station to be broadcasted, all nodes will forward these packets. Therefore, the entire network will be affected by this attack.

Figure 1 shows a PDoS attack example. The adversary node sends too many bogus packets to the base station in a multi hops path. Therefore, the energy of the nodes in the path will be exhausted. Moreover, the traffic from other nodes that depend on one or more of these nodes as downstream nodes will be blocked, and alternative paths will be needed. Thus, PDoS attacks can disable a much wider region rather than a single path.

Figure 1

PDoS attack effects: an adversary will exhaust the victim nodes' energy and block the rejected traffic.

The danger of a PDoS attack is exacerbated due to its easiness to launch and its high effects on large portions of the network. Any adversary node can repeat the transmission of packets or inject bogus packets, which will be forwarded many hops before being detected by the destination. These bogus packets exhaust the energy of the intermediate nodes, especially from those nodes that are close to the base station, because they are intermediate to too many nodes. Consequently, they will die faster, and their downstream nodes will not be able to send packets to the base station because of the tree nature of sensor networks.

Existing end-to-end security mechanisms fail to prevent such attacks. Therefore, we adopted in this work a link layer security approach. It depends on the idea that there will be a shared key between the two ends of each hop, and a shared sequence counter that is attached to each packet after incrementing and encrypting it. For broadcast traffic, we will use the one-way hash chains (OHCs) concept to prevent nodes from forwarding bogus or replayed packets which are generated by an adversary on behalf of the base station.

Our contribution is summarized in five folds. First, any intermediate node will be able to filter out bogus packets as soon as they are injected in the network. Second, we handle four types of traffic. Third, the introduced algorithm is lightweight in memory, communication, and processing requirements which makes it suitable to WSN. Moreover, it is scalable to large network sizes. Finally, it tolerates the loss of multiple packets without weakening the security of the solution.

The rest of this paper is organized as follows. Next section presents summary of related work. System model is introduced in Section 3. After that, the proposed algorithm for handling PDoS is introduced in Section 4. Section 5 is devoted to presenting the simulation results and the comparison with the OHC algorithm. Finally, we conclude the paper in Section 6.

2. Related Work

There is a set of proposed ways to detect spurious packets and to filter them out [1]. One way is using public key. The source signs the packet using the private key. Every intermediate node will be able to verify the signature because it has the public key of the source. But, due to the high constraints of sensors and the fact that asymmetric cryptography is power/memory thirsty, it cannot be used in WSN.

Another solution is to establish a shared key between the source node and every intermediate node in the path to the destination. The sender appends to the packet a message authentication code (MAC) value for every intermediate node. When an intermediate node receives the packet, it checks its related MAC value and forwards it if it has a valid MAC value. This solution suffers from high overhead because it adds a MAC for every intermediate node. Also, the source node has to know the whole path in advance, and should establish keys with these intermediate nodes [1].

Another possible solution is to use a shared path key for the whole path from the source to the destination, where one MAC can be used for each packet. However, the source node still has to establish the path in advance, and revealing or tampering with the shared key from any node in the path will make the whole path attacked [1].

Zhu et al. [2] named this attack as “false data injection attack”. They proposed an interleaved hop-by-hop authentication scheme that guarantees that the base station can detect any injected false data packet when no more than a certain number of nodes (t) are compromised. Furthermore, they provided an upper bound (B) on the number of hops that a false data packet could be forwarded before it is detected and dropped when there are up to t colluding compromised nodes. This scheme requires that $t + 1$ nodes agree on the report to consider it a valid report. Also, this scheme requires that each node shares keys with each of its neighboring nodes and also with associated nodes that are multihops away ( $t + 1$ hops), which is high overhead. In addition, the sensor that senses an event, computes three MACs for this event, and the en route nodes compute four MACs for every packet. Also, each packet has $t + 2$ MACs. They tried to reduce the size of these MACs, but on the cost of security. In our approach, every node including the source decrypts and encrypts one value, and only this encrypted value is attached to the packet. Moreover, their protocol may be even more prone to DoS attacks. A compromised node can inject bad data or a bad signature for an event, and since one MAC will not match at the base station, the base station will reject the entire event even though there may have been $t - 1$ noncompromised nodes that reported the event successfully. In our approach, the packet will not be forwarded except if it is a valid one.

Ye et al. [3] proposed a statistical en route detection scheme called SEF, which allows both the base station and en route nodes to detect false data with a certain probability. SEF uses Bloom filter to reduce the size of MACs and ensure their security. However, there are several problems, first, it is probabilistic, and therefore some packets still will not be filtered as opposed to our approach that is deterministic. Second, the bogus packets will be forwarded multiple hops before they are detected. Our approach filters the packet as soon as it is injected.

The aforementioned algorithms do not handle broadcast traffic which is of higher effect. Also, they suffer from high communication and computation overhead. Our approach handles four types of traffic including the broadcast traffic and is scalable and lightweight.

TinySec [4] is targeted at the security of link layer communication, where it focused on detecting malicious messages as early as possible to avoid committing resources to deliver these messages to the destination. But, it did not deal with replay attacks. Moreover, they assumed that there is one key shared among all the nodes in the network. This is not robust, because a single captured node compromises the security of the entire system. In our approach, we assume that there is a key that is shared among every two nodes form the edges of a hop. We use a lightweight key management protocol [5] that achieves that.

Deng et al. [1] proposed the OHC algorithm that deals with PDoS attacks which is based on one-way hash chain (OHC). They tried to filter any injected false data packet as soon as the packet is injected. Every source node maintains two long OHCs (control and data OHCs), and each of the en route nodes initialized with verifier values of the two chains that are related to the source node.

This algorithm assumes that for a source node (S) to communicate with the base station (B), an end-to-end path must be securely established as: S $\to n_{1} \to n_{2} \to \dots \to n_{m} \to$ B, where $n_{1}$ , $n_{2}$ , $\dots n_{m}$ are intermediate nodes. The setup needs every intermediate node to store a verifier value ( $K_{s}$ ) about the OHC sequence of S, which is equal to the initial value of the OHC ( $K_{i}$ ). To bootstrap the initial OHC number, the base station applies μTESLA secure broadcast mechanism.

When any intermediate node ( $n_{k}$ ) along the path receives a packet (i) from the source (S) with a value ( $K_{s}$ ), it will verify that $K_{s} = F (K_{i})$ where $K_{i}$ is the value of the OHC sent by the source previously, and F is an irreversible one way hash function. If the verification was successful, $n_{k}$ will validate the packet, forward it to the next intermediate node, and set $K_{s}$ to the new value ( $K_{i}$ ). To tolerate the loss of a sequence of up to w packets, $n_{k}$ will apply F up to w times on $K_{i}$ to check that $K_{s} = F (F \dots (F (K_{i})))$ . If the verification failed after w times, $n_{k}$ will drop the packet (“broken OHC problem”) and will need resynchronization with the source. Algorithm 1 shows the pseudocode for the OHC algorithm. We will show by simulation and discussion in Section 5 that our algorithm outperforms the OHC algorithm.

Algorithm 1: OHC algorithm.

(1) SourceNode ← ReceivedPacket.Source;

(2) TempOHC ← ReceivedPacket.OHCValue;

(3) OHCVerified ← false;

(4) for $i = 1$ up to w do

(5) if F(TempOHC) = SourceNode.OHCVerifierValue then

(6) SourceNode.OHCVerifierValue ← ReceivedPacket.OHCValue;

(7) OHCVerified ← True;

(8) Exit for;

(9) else

(10) TempOHC ←F(TempOHC);

(11) end if

(12) end for

(13) if (OHCVerified = false) then

(14) Drop the packet and subsequent packets until new OHC value of

the source is received in the coming OHC refresh cycle;

(15) end if

3. System Model

We made the following assumptions. (1)

There is a base station that collects sensing results from the nodes and sends to them some queries.

(2)

The network is dense, which means that the removal of a sensor or a set of sensors will not make the WSN disconnected and isolate parts of the WSN.

(3)

Before deployment, nodes are initialized with shared keys with the base station and the initial μTESLA parameters.

(4)

Every node knows its position, which may be achieved using GPS devices or using localizing protocols.

(5)

Nodes are globally addressable. There are several approaches for globally addressable communications infrastructure such as geographically addressed networking using GPSR as a routing protocol [6], a geographic hash table (GHT) as an address lookup service [7], geographic routing without location information [8], graph embedding for routing [9], and many other protocols that use shared key between a node and the base station like SPINS [10].

To achieve basic security functions like authentication, confidentiality, semantic security, end-to-end freshness, data integrity, and key setup between two nodes, we used some other existing protocols including SPINS (which is composed of two building blocks, SNEP and μTESLA) [10], Whisper [11], and OHST [12].

In our work, we use SNEP for sending sensor readings, request/reply packets between the sensor and the base station, or between any two neighboring sensors. SNEP guarantees one-to-one authentication, confidentiality, integrity, weak freshness, and semantic security. We also use μTESLA for broadcast authentication. OHST will be used in order to store long sequences of one-way hash chains that we need in our algorithm for the μTESLA and for PDoS handling. In addition, it will be used in the OHC algorithm to store the long one-way hash chains of sensor nodes. The OHST algorithm stores very long OHC in small memory while verifying a value from the OHC does not take a long time.

4. A New Protocol for Defending PDoS Attack (NPfDPDoS)

We adopted a link layer security approach. The two nodes which form the edges of every hop, share a key and two counters. The counter value is incremented after each transmission. Every node shares keys with some of its neighbors (reliable neighbors). To achieve redundancy and availability in case some nodes die, we need at least two reliable neighbors for each node in the direction of the base station; a main next hop node to the base station, and an alternative next hop node in the direction of the base station. We will show how to achieve this requirement in an efficient manner with small overhead. In addition, every node shares two counters with each reliable node (one for each direction). Some of the proposed algorithms handled only one-to-one traffic [2, 3, 13]. We will show how to deal with the following types of traffic. (1)

Node to base station: for example, traffic that carries sensor readings.

(2)

Base station to node: for example, traffic that handles querying a node or sending a request or reply.

(3)

Base station broadcast to all nodes: for example, traffic for initializing nodes or synchronizing them.

(4)

Node to node: for example, traffic between neighboring nodes that share a key.

4.1. Node to Base Station Traffic

When any sensor detects an event generated by a target node and wants to send the measured value in a packet to the base station, it forwards the packet to one of its reliable neighbors and appends to the packet the value of the counter that is shared with that neighbor (upper association node). The counter value must be sent encrypted using the key shared with the upper association node.

When an intermediate node ( $n_{k}$ ) receives a packet from the lower association node ( $n_{k - 1}$ ), it first decrypts the counter using the key shared with $n_{k - 1}$ . To tolerate the loss of w packets, if the decrypted counter value is away by w from the last verified counter shared with $n_{k - 1}$ , the packet will be considered valid and fresh, and $n_{k}$ will update the shared counter of $n_{k - 1}$ to be the one decrypted from the packet. Then, $n_{k}$ removes the appended encrypted counter from the packet, and appends the value of the counter shared with its upper association node ( $n_{k + 1}$ ) after encrypting it. The encryption is done using the shared key between $n_{k}$ and $n_{k + 1}$ . After that, $n_{k}$ forwards the packet to $n_{k + 1}$ , which will do the same steps that were done by $n_{k}$ . And so on until it reaches the base station.

If the value of the decrypted counter differs from the last verified counter by more than w, the packet freshness is denied, and the node needs to resynchronize its shared counter with the previous node. A DoS attack can be done by changing the value of the encrypted counter, even if the attacker does not know the value. In this case, the victim node will try to resynchronize the counter value. To prevent this attack, the node will not send re-synchronizing packets unless the difference between the decrypted counter and the last verified counter is less than a very large value (x). We will choose x such that it is larger than any predicted number of lost packets, while not weakening the security of the protocol. For example, if we selected $x = {(10)}^{6}$ , the probability that an 8-byte encrypted counter is modified by the adversary will be considered valid = ${(10)}^{6} / {(2)}^{64}$ , which is very small, and it is infeasible to have a loss of one million of consecutive packets on a specific hop during the life time of a sensor.

The process will be repeated until the packet reaches the base station. Therefore, every intermediate node ( $n_{k}$ ) decrypts the counter attached with the packet. If it is larger than the last verified value by a difference, say w, the value is considered valid and the packet is considered fresh. If the difference is larger than w and less than x, the node needs to resynchronize the counter with its neighboring node. Otherwise, the packet is considered bogus, and it will be dropped. If the packet is valid, sensor $n_{k}$ will remove the attached encrypted counter from the packet and replace it with the encrypted value of its shared counter with the next hop node. The base station will not check the shared counter with the previous node because it will check the MAC value in the packet using the shared key with the source node.

4.2. Base Station to Node Traffic

This will be handled exactly in the same way as the node-to-base station traffic. When the base station wants to send a packet to a node, it appends the encrypted value of the shared counter with the upper association node and forwards the packet to this node. Every intermediate node does the same steps by checking the counter value and appending its own encrypted counter using the shared key with the upper association node. When the destination node that receives the packet, it does not check the encrypted counter, but instead, it checks the MAC value as it has fresh information sent by the base station.

4.3. Base Station Broadcast to all Nodes Traffic

In broadcast traffic, every node receives a packet will broadcast it to all of its neighbors. Therefore, the packet will be passed between nodes which do not share keys between them, and the previous approach does not work. Instead, we will use the concept of one-way hash chain sequence (OHC). The base station maintains a long OHC and each node stores a verifier of this OHC sequence, which is represented by the last verified OHC value. Sensor nodes will be initialized with the initial value of the base station OHC before deployment.

OHC is a very long sequence of values like the one used in μTESLA [10]. To generate an OHC, first, a value ( $V_{n}$ ) is randomly selected. Then, and using a one-way hash function (F), it is very easy to calculate $V_{n - 1}, V_{n - 2}, \dots, V_{i + 1}, V_{i}, \dots, V_{1}$ , where $V_{i} = F (V_{i + 1})$ . However, it is infeasible to calculate $V_{i + 1}$ from $V_{i}$ . The base station maintains a one-way hash chain. When it needs to broadcast a packet, it attaches with it a value from the OHC, such that it attaches $V_{1}$ with the first packet, and $V_{i}$ with the $i th$ packet and so on.

Every broadcasted packet from the base station includes a value from the OHC sequence. This value is self-authenticated because from the value ( $V_{i}$ ), we can easily calculate the stored verifier value $(V_{i - 1})$ , and it is infeasible to calculate ( $V_{i + 1}$ ). If a node verified that the OHC value is valid ( $V_{i - 1}$ is generated from $V_{i}$ ), it broadcasts the packet to its neighbors and stores this OHC value as the new verifier. Otherwise, it discards the packet. In this way, we discard any repeated packet because it will not generate the verifier OHC. In addition, the adversary cannot generate bogus packets to be as legal packets because it is infeasible to calculate the next OHC value from the previous values.

The node tolerates the loss of w packets by trying to verify the sent OHC by applying the function F up to w times. If more than w packets were lost (Broken OHC), the node will ask the base station about the value of the current OHC for the base station. To do this, the node uses SNEP packets and “Node to base station” method to prevent PDoS attacks to this packet.

A broken OHC attack in broadcast traffic is less probable than in unicast traffic, because every node receives a packet, will broadcast it. Consequently, the packet reaches to each node through multiple paths. But, this attack could still happen in case of jamming the whole region around a node. However in this case, the effect will not be accumulated to next nodes since the packet will be broadcasted to the next nodes through some other paths, and they will not lose the OHC synchronization.

4.4. Node to Node Traffic

The fourth type of traffic is between two neighbors who share a key between them. These nodes will use the normal SNEP packets because there are no intermediate nodes. Therefore, the MAC calculated using the shared key between these two nodes with the shared counter, which is incremented after each transmission, will prevent bogus and replayed packets.

Algorithm 2 shows the pseudocode for the NPfDPDoS when a packet that originated from the BS to be broadcasted is received by any node. In Algorithm 3, node r receives a packet from node $r - 1$ and will forward it to node $r + 1$ . The subscript ( $r - 1$ , r) means the shared value between node $r - 1$ and node r.

Algorithm 2: NPfDPDoS broadcast traffic handling.

(1) TempOHC ← ReceivedPacket.OHCValue

(2) OHCVerified ← false

(3) for $i = 1$ up to wdo

(4) if (F(TempOHC) = OHCVerifierValue) then

(5) OHCVerifierValue ← ReceivedPacket.OHCValue

(6) OHCVerified ← True

(7) Exit for

(8) else

(9) TempOHC ←F(TempOHC)

(10) end if

(11) end for

(12) if OHCVerified = false then

(13) Resynchronize OHCValue with the base station using a SNEP packet

(14) end if

Algorithm 3: BS-to-node or node-to-BS traffic handling on intermediate node r.

(1) TempCounter ← Decrypt(ReceivedPacket.EncryptedCounter, ${Key}_{r - 1, r}$ )

(2) if ${VerifiedCounter}_{r - 1, r} < TempCounter < {VerifiedCounter}_{r - 1, r} + w$ then

(3) ${VerifiedCounter}_{r - 1, r}$ ← TempCounter

(4) ReceivedPacket.EncryptedCounter = Encrypt( ${SharedCounter}_{r, r + 1}$ + 1, ${Key}_{r, r + 1}$ )

(5) Forward ReceivedPacket to node ( $r + 1$ )

(6) else if ${VerifiedCounter}_{r - 1, r} < TempCounter < {VerifiedCounter}_{r - 1, r}$ + X then

(7) Resynchronize Counter Value with the node ( $r - 1$ )

(8) else

(9) Drop the packet

(10) end if

4.5. Routing Decision

Routing is not within the scope of our algorithm. However, for packets forwarding, we chose geographic routing where each node knows its position and its neighbors' positions. When a node wants to forward a packet to the destination, it forwards the packet to a reliable node that has the least distance, that is higher than the average distance of the neighbors, in the direction of the destination.

4.6. Resilience to Path Changes

End-to-end route paths may change due to the changes in the transmission range of a sensor node, irregularity of transmission ranges, death of sensor nodes, or due to any other reason. Path changes could be affected by some new nodes that join the network. These nodes need to be bootstrapped with a shared key with the next hop nodes. Hence, they will use the random key predistribution methods to achieve a shared key with at least one neighbor [14–16]. After that, our key management algorithm, that is described in [5] to do key setup between this node and the other nodes, could be used. We showed in [5] that the node will have a shared key with most of its neighbors with small overhead, that is, by exchanging a small number of packets between neighbors.

On the other hand, nodes may die due to many reasons such as energy loss, node compromise, damage, or any other reason. Here there will be three possibilities. (1)

The dead node is the main next hop node along the path to the base station: the node will use the alternative path node as the new main next hop node. Then, it checks its neighbors' table to find another reliable node along the direction of the base station to be used as a new alternative node. If there is no such node, it should do key setup with another node with the help of the base station as a trusted third party.

(2)

The dead node is the alternative next hop node along the path to the base station: the node will check its neighbors' table to find another reliable node along the direction of the base station to be used as a new alternative node. If there is no such node, it will do key setup with another neighbor node with the help of the base station as a trusted third party.

(3)

The dead node is any other node: in this case, the node will not take any action.

Therefore, every node will always maintain at least two reliable neighbors in the direction of the base station. The reliable neighbors to a node are the neighboring nodes that it shares keys with; one will be the main next hop and the other will be an alternative path. When the main next hop node dies, the alternative path node will be the new main next hop node and the node will look for a new alternative path. Consequently, the node can continue its work without being affected by PDoS attacks since there is always a reliable next hop node. Using our key management algorithm [5], the node sends on average of around 90 packets to do key setup with 70% of its neighbors which are enough to maintain the NPfDPDoS until the network dies. Those packets are sent locally within the neighbors.

5. Simulation Results

We implemented the NPfDPDoS and the OHC [1] algorithms using J-Sim simulator [17]. WSNs are complex systems that are extremely difficult to analyze using theoretical tools. Therefore, we have conducted simulation studies to evaluate the performance of NPfDPDoS and the OHC algorithms. We have conducted all simulation on a PC running windows XP and Java 2 runtime environment standard edition v.1.4.

For security functions and implementations, we used the JSAFE package from B-Safe [18]. This package is written in Java. It provides most of the basic security functions. We have used the following functions from this package. (1)

MD5 for authentication and message digest.

(2)

RC5 (16, 16, 32) for message encryption and confidentiality.

(3)

Random functions for randomization.

The overhead that must be taken into account while designing a security algorithm is the combination of CPU, memory, and transmissions. Therefore, we will compare the NPfDPDoS with the OHC algorithm according to these three factors.

5.1. CPU Execution Time Overhead

Both of NPfDPDoS and the OHC algorithms try to tolerate packets loss. In the OHC algorithm, every lost packet that originated from a specific source node will make every upstream node check the OHC one extra time, and every check will take around 1.5 ms according to [1]. If there is no loss, every hop will take 1.5 ms for checking the OHC value. Also, to generate each OHC value on the source node, it needs 16 ms. On the other hand, NPfDPDoS requires 1.5 ms for every hop regardless of the packets loss. This 1.5 ms is for decrypting the counter per hop. To show the effect of packets loss on the end-to-end delay, some packets were chosen randomly to be as lost packets such that the loss rate is satisfied. Figure 2 below shows the average end-to-end delay and its relation with the number of hops that a packet travels from the source to the destination for different loss rates. We refer here to the delay as the extra delay that the algorithm adds, we did not include in this delay the time for transmission, reception, or packets handling.

Figure 2

Influence of loss rate on average end-to-end delay and its relation with the number of hops.

As we can see from Figure 2, end-to-end delay in NPfDPDoS increases linearly with the increase of the number of hops, with a rate of 1.5 ms per hop. Whereas, the OHC algorithm has bad performance on high loss rates and long distances. Their approach needs 16 ms for generating the OHC value and then every intermediate node will consume at least 1.5 ms for checking the OHC. If there are i lost packets after a node ( $n_{k}$ ) (e.g., by jamming the medium between $n_{k}$ and $n_{k - 1}$ ), every node after $n_{k}$ will take $1.5 * i$ ms to check the OHC. If there are j hops to the destination after $n_{k}$ , the packet will take $j * i * 1.5$ ms after node $n_{k}$ for checking the OHC.

5.2. Memory Overhead

The second type of overhead is memory overhead. NPfDPDoS does not need high storage overhead on sensor nodes because every node stores some information about some of its neighbors including the following. (1)

The key: assuming that the key length is 8 bytes (DES key).

(2)

Two shared counters: the node's shared counter and the other node shared counter, 8 bytes long each.

Therefore, every node stores 24 bytes about each node it shares a key with. On the other hand, in the OHC algorithm, every intermediate node along the path from a source to the base station stores the OHC_C (control) and the OHC_D (data) verifier values (8 Bytes each) about that source node. Therefore, the storage overhead increases on the nodes closer to the base station because these nodes that are closer to the base station are intermediate to too many nodes.

In this experiment, the transmission range of sensor nodes selected to be 40 m. Figure 3 shows the average storage overhead in the OHC algorithm as a function of the number of nodes.

Figure 3

Influence of the number of nodes on the average storage overhead for the OHC algorithm.

As we can see in the OHC algorithm, storage overhead increases with the number of nodes. Therefore, storage overhead is highly correlated with the number of nodes in the network. WSN are usually much larger than 300 nodes, but due to simulator restrictions and the computing power of the computer that was used in the simulations, we restricted our work to 300 nodes. We should add to this overhead the sizes of ${OHC}_{D}$ and OHC_C that every source node has to store in the OHC algorithm. Each of these requires 913 bytes for an OHC of length 2²² using the optimal hash sequence traversal algorithm [12]. Therefore, we should add to the figure 1826 bytes of overhead for each source node in the OHC algorithm.

NPfDPDoS does not need any global information; it only needs some information about some of its neighbors. Therefore, it is not affected by the number of nodes in the network or the distance from the base station. Figure 4 shows the influence of the number of nodes in the network on the storage overhead in our protocol. Storage overhead equals the number of reliable neighbors multiplied by 24 bytes to be stored about each reliable neighbor.

Figure 4

Influence of the number of nodes on the average storage overhead for the NPfDPDoS algorithm.

As we can see from Figure 4, the number of neighbors that have a shared key, and hence the storage overhead, is not correlated to the number of nodes in the network. At most, a node may have 13 reliable neighbors, so it needs $13 * 24 = 312$ bytes.

It is worths mentioning that in NPfDPDoS, the neighbors table is small (around 312 bytes), which can set in the node's RAM (4 KB) whereas in the OHC algorithm the nodes table in every intermediate node cannot be stored in the RAM. Therefore, it will store the remaining data in the flash memory (128 KB), and switching between the RAM and the flash memory is needed which is expensive [19]. Also, in NPfDPDoS, not all entries are needed at the time; a node needs only those neighbors that are next intermediate nodes. The others may be needed later when some nodes die. Those can stay in the secondary storage until needed, while in the OHC, the needed entries depend on the sources that send packets which cannot be predicted (it depends on the generated events).

5.3. Transmission Overhead

Using our key management algorithm [5], the node sends on average around 90 packets to do key setup with 70% of its neighbors which are enough to maintain the NPfDPDoS until the network dies. Those packets are locally sent within the neighbors. In the OHC algorithm, every node needs 4 packets between the node and the base station and vice versa for setup of the OHC_C and OHC_D, also two packets between the node and the base station and vice versa on every OHC refresh which is done on periodic basis. Moreover, the loss of a multihop packet requires overhead that equals a factor multiplied by the overhead that is required for loss of local packets. This factor is proportional to the length of the path.

Furthermore, the overhead that we have added to every packet is the encrypted counter in the case of node to base station or base station to node traffic and the OHC value in the case of broadcast traffic.

5.4. Discussion

The OHC algorithm deals only with one type of traffic, which is the traffic from a node to the base station. It does not deal with the traffic from the base station to a node (one-to-one), base station to all nodes (broadcast), or traffic between neighboring nodes. Also, in the OHC algorithm, there is a need to initialize the intermediate nodes along a path with the OHC_C and OHC_D values of the source. They supposed that the base station will send μTESLA packets for initializing the intermediate nodes, which is very difficult as the base station will have to know the positions of nodes that are randomly deployed. Also, μTESLA requires synchronization between the base station and the nodes, and it requires a number of packets to be sent end-to-end for initialization.

In case of broken OHC where more than w packets are lost, re-synchronizing the OHC is needed. The OHC algorithm solves the broken OHC by a periodic OHC refresh. Refreshing needs the transmission of two packets from the node to the base station and vice versa. On the other hand, NPfDPDoS does not need any periodic event or global interaction of nodes or base station. Also, it tolerates larger values of w. If more than w packets are lost, the node immediately asks its neighbor about the counter value in a secure way and without dropping packets.

Proposed solutions for network maintenance in the OHC algorithm that are needed when new nodes join the network are not efficient. In their “OHC proactive bootstrapping” approach, a node needs to store extra information about the source nodes that are not intermediate to them and it requires the nodes to always monitor the traffic that is not intended to them. In the “lazy OHC bootstrapping” approach, there are some nodes that will be affected by the PDoS attack, so it will not prevent the attack completely.

6. Conclusion

We have presented a new protocol for preventing PDoS attacks in WSN by filtering any bogus or replayed packet as soon as it is injected in the network. We handled four types of traffic including broadcast traffic that has higher effects as it affects the whole network, whereas most other existing algorithms do not give attention to broadcast traffic.

In end-to-end security, the final destination is the only entity that is able to check the authenticity, confidentiality, and the integrity of a packet. Therefore, they are vulnerable to PDoS attacks. For this reason, we have adopted a link layer security scheme to enable en route intermediate nodes to filter out any bogus or replayed packet.

We have shown by extensive simulation that in our algorithm, end-to-end delay is not affected by the loss rate or by the number of hops. We also showed that CPU, memory, and transmission overheads are small compared to the OHC algorithm.

References

Deng

Han

Mishra

Defending against path-based dos attacks in wireless sensor networks

Proceedings of 3rd ACM Workshop on Security of Ad Hoc and Sensor Networks (SASN ′05)

November 2005

ACM

89 96

2-s2.0-33745969132

10.1145/1102219.1102235

Zhu

Setia

Jajodia

Ning

An interleaved hop-by-hop authentication scheme for filtering of injected false data in sensor networks

Proceedings of IEEE Symposium on Security and Privacy

May 2004

259 271

2-s2.0-3543056512

Luo

Zhang

Statistical en-route filtering of injected false data in sensor networks

IEEE Journal on Selected Areas in Communications 2005 23 4 839 850

2-s2.0-17144429277

10.1109/JSAC.2005.843561

Karlof

Sastry

Wagner

TinySec: a link layer security architecture for wireless sensor networks

Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys ′04)

November 2004

ACM

162 175

2-s2.0-26444574670

Al-Jarrah

Saifan

A novel key management algorithm in sensor networks

Proceedings of the 6th International Conference on Advances in Mobile Computing and Multimedia

2008

ACM

291 294

Karp

Kung

H. T.

GPSR: greedy perimeter stateless routing for wireless networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM ′00)

August 2000

ACM

243 254

2-s2.0-0034547115

Ratnasamy

Karp

Yin

Estrin

Govindan

Shenker

GHT: a geographic hash table for data-centric storage

Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications

September 2002

ACM

78 87

2-s2.0-0036983290

Rao

Ratnasamy

Papadimitriou

Shenker

Stoica

Geographic routing without location information

Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom ′03)

September 2003

ACM

96 108

2-s2.0-1542329085

Newsome

Song

GEM: Graph EMbedding for routing and data-centric storage in sensor networks without geographic information

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys ′03)

November 2003

ACM

76 88

2-s2.0-18844435123

10.

Perrig

Szewczyk

Tygar

J. D.

Wen

Culler

D. E.

SPINS: security protocols for sensor networks

Wireless Networks 2002 8 5 521 534

2-s2.0-0036738266

10.1023/A:1016598314198

11.

Naik

Arora

Bapat

Gouda

Whisper: local secret maintenance in sensor networks

Proceedings of Workshop on Principles of Dependable Systems

2003

12.

Jakobsson

Fractal hash sequence representation and traversal

Proceedings of IEEE International Symposium on Information Theory (ISIT ′02)

July 2002

437

2-s2.0-0036352143

13.

Przydatek

Song

Perrig

SIA: secure information aggregation in sensor networks

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys ′03)

November 2003

ACM

255 265

2-s2.0-18844457825

14.

Chan

Perrig

Song

Random key predistribution schemes for sensor networks

Proceedings of IEEE Symposium on Security and Privacy

May 2003

197 213

2-s2.0-0038487088

15.

Eschenauer

Gligor

V. D.

A key-management scheme for distributed sensor networks

Proceedings of the 9th ACM Conference on Computer and Communications Security

November 2002

ACM

41 47

2-s2.0-0038341106

16.

Chen

S. H. S.

A key management scheme for wireless sensor networks using deployment knowledge

17.

Sobeih

Hou

J. C.

Kung

L. C.

Zhang

Chen

W. P.

Tyan

H. Y.

Lim

J-Sim: a simulation and emulation environment for wireless sensor networks

IEEE Wireless Communications 2006 13 4 104 119

2-s2.0-33748340248

10.1109/MWC.2006.1678171

18.

http://www.rsasecurity.com/support/

19.

Dai

Neufeld

Han

ELF: an efficient log-structured flash file system for micro sensor nodes

Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys ′04)

November 2004

ACM

176 187

2-s2.0-27644461868

A Novel Algorithm for Defending Path-Based Denial of Service Attacks in Sensor Networks

Abstract

1. Introduction

2. Related Work

Algorithm 1: OHC algorithm.

3. System Model

4. A New Protocol for Defending PDoS Attack (NPfDPDoS)

4.1. Node to Base Station Traffic

4.2. Base Station to Node Traffic

4.3. Base Station Broadcast to all Nodes Traffic

4.4. Node to Node Traffic

Algorithm 2: NPfDPDoS broadcast traffic handling.

Algorithm 3: BS-to-node or node-to-BS traffic handling on intermediate node r.

4.5. Routing Decision

4.6. Resilience to Path Changes

5. Simulation Results

5.1. CPU Execution Time Overhead

5.2. Memory Overhead

5.3. Transmission Overhead

5.4. Discussion

6. Conclusion

References