9.1 Attack on Link Quality Measurement

The packet reception ratio (PRR) has been widely used as an indicator of the link reliability in multihop wireless networks. It has been shown that routing performance is significantly improved by considering the link PRR information. For example, expected transmission count (ETX)-based routing achieves much higher throughput than traditional minimum-hop routing protocols in wireless mesh networks (Couto et al. 2003). The ETX is defined as , where pf and pr is the forward and reverse link PRR, respectively. Recent work in sensor networks (Sang et al. 2007) suggests a link metric (ETF), expected number of transmissions over forward links, which only considers forward link PRR. State-of-the-art geographic routing protocols (Seada et al. 2004; Zeng et al. 2007b) and most opportunistic routing protocols (Biswas and Morris 2005; Zeng et al. 2007a) rely on link quality information to make routing decisions.

Providing accurate link quality measurement (LQM)1 is essential to ensure the correct operation of the above protocols/schemes. Furthermore, LQM is also important in supporting QoS guarantees in multihop wireless networks. Lastly, accurate long-term statistics about link-quality information are necessary to diagnose a network to identify the source of network failures and reduce the management overhead.

The existing LQM mechanisms proposed in the literature (Couto et al. 2003; Kim and Shin 2006; Sang et al. 2007) can be generally classified into three types: active, passive, and cooperative (Kim and Shin 2006). For broadcast-based active probing (Couto et al. 2003), each node periodically broadcasts hello/probing packets and its neighbors record the number of received packets to calculate the PRRs from the node to themselves. In passive probing (Kim and Shin 2006), the real traffic generated in the network is used as probing packets without introducing extra overhead. For cooperative probing (Kim and Shin 2006), a node overhears the transmissions of its neighbor to estimate the link quality from the neighbor to itself.

However, for any of the existing LQM mechanisms, the inherent common fact is that a node's knowledge about the forward PRR from itself to its neighbor is informed by the neighbor. Since multihop wireless networks are generally deployed in an ad hoc style or in untrusty environments, nodes may be compromised and act maliciously. This receiver-dependent measurement opens up a door for malicious attackers to report a false measurement result, thus disturbing the routing decision for all the PRR-based protocols. For example, in Figure 9.1, suppose A is the source and D is the destination, and the actual PRR is indicated above each link in Figure 9.1(a). The ETF-based shortest path routing would select the path A → B → D, because it has the lowest ETF path cost. However, if C is a malicious node, and reports to A that the PRR from A to itself is 0.9 (indicated below the link in Figure 9.1(b)), then A would select path A → C → D. In such a way, a suboptimal path is selected between A and D, thus degrading routing performance. More seriously, C attracts all the traffic from A, then with the control of the traffic, it can further maliciously drop the packets.

Figure 9.1 A four-node example. (a) The actual PRR on each link is indicated, and the ETF-based routing selects the optimal path A → B → D. (b) The malicious node C bluffs A into believing that the PRR from A to C is 0.9, then the ETF-based routing would select the suboptimal path A → C → D. Reproduced by permission of © 2008.

To the best of our knowledge, none of the existing work addresses security vulnerabilities in the existing LQM mechanisms. As LQM is becoming an indispensable component in multihop wireless networks, it is necessary to make this component work securely and provide actual and accurate PRR information.

In this chapter, we analyze the security vulnerabilities in the existing LQM mechanisms. We then propose a broadcast-based secure LQM mechanism, which prevents the malicious attacker from reporting a higher PRR than the actual one. This framework can be easily applied to unicast-based and cooperative LQM mechanisms.

The rest of this section is organized as follows. Section 9.1.1 introduces the existing link quality measurement mechanisms and point out their security pitfalls. The performance degradation of opportunistic routing as well as traditional routing is demonstrated in Section 9.1.2. We then propose a broadcast-based secure LQM (SLQM) mechanism and analyze its security strength and overhead in Section 9.1.3.

9.1.1 Existing Link Quality Measurement Mechanisms and Vulnerabilities

This section gives an overview of the existing LQM mechanisms and analyzes their security vulnerabilities. According to the type of probing packets, LQM can be classified into broadcast-based and unicast-based probing. While based on the generation source of probing packets, LQM can also be categorized into active, passive, and cooperative probing (Kim and Shin 2006).

9.1.1.1 Broadcast-Based Active Probing

For broadcast-based active probing (Couto et al. 2003), each node broadcasts link probes of a fixed size, at an average period τ (e.g. 1 second). Every node remembers the probes it receives during the last w seconds (e.g. 10 seconds), allowing it to calculate the PRR from the measuring node at any time t as: , where count(t − w, t) is the number of probes received during the window w, and w/τ is the number of probes that should have been received. In the case of two neighboring nodes A and B, this technique allows A to measure the PRR from B to A, and B to measure the PRR from A to B. Each probe sent by a node A contains the number of probing packets received by A from each of its neighbors during the last w seconds. This allows each neighbor of A to calculate the forward link PRR to A whenever it receives a probe from A.

The security vulnerability in the broadcast-based active probing is that a malicious node can easily report a false measurement result. For example, if node B is an attacker, it can bluff A into believing that the PRR from A to itself is 1 by claiming that it received w/τ packets in the last probing window w.

9.1.1.2 Unicast-Based Passive Probing

Unicast-based passive probing (Kim and Shin 2006) makes use of the real unicast traffic as the “natural” probing packets without incurring extra overhead. It is applicable when there is enough unicast traffic on a measured unidirectional link. It runs as follows: for instance, suppose node A has enough traffic to node B. Then, A gets the information about the number of successful transmissions (Ns) and the total number of transmissions (Nt) from its MAC's MIB (Management Information Base) for the traffic. At the end of an update period, the PRR is derived as , and is further smoothed by moving average (Kim and Shin 2006).

For unicast-based passive probing, it is hard but not impossible for an attacker to cheat on the link quality. In 802.11 (802.11b 1999 n.d.), the Distributed Coordination Function (DCF) defines two access mechanisms for packet transmissions: basic access mechanism, and RTS/CTS access mechanism. We analyze the security vulnerability of the unicast-based passive probing under these two access mechanisms as follows.

In the basic access mechanism, a sender starts the transmission of a DATA frame after it senses the channel is idle for a while. Upon successful decoding the whole DATA frame, the receiver sends an ACK frame back to the sender, indicating successful reception of the DATA frame. In this case, even when it can not decode the whole data frame, a receiver may decode some parts of it (Jamieson and Balakrishnan 2007). So it is possible for a malicious receiver to figure out the sender's address and send back an ACK to claim a correct reception even when it receives a corrupted data frame.

The RTS/CTS access mechanism uses a four-way handshake in order to reduce bandwidth loss due to the hidden terminal problem. Unlike the case with the basic access mechanism, a sender will send a RTS frame to the receiver before it sends out the DATA frame. Upon successful reception of the RTS frame, the receiver then sends a CTS frame back to the sender. The sender can start sending the DATA frame after the reception of the CTS frame. As in the basic access mechanism, upon successful reception of the DATA frame, the receiver sends an ACK frame back to the sender. In this case, by receiving the RTS, a malicious receiver can figure out the sender's address, so even it receives a corrupted data frame, it can still claim a successful reception by sending back an ACK.

In summary, although a sender estimates the link quality based on its own MIB information in the unicast-based passive probing, this information is still dependent on the feedback (ACK) from the receiver. A malicious receiver may still be able to make use of the ACK to bluff the sender into believing that there exists a high-quality link from the sender to the receiver.

9.1.1.3 Cooperative Probing

Cooperative probing (Kim and Shin 2006) is used when there is not enough unicast traffic from a measuring node to its neighbor, but there is enough to others. For example, a measuring node A has two one-hop neighbors, B and C. A has no egress traffic to C, but it has egress traffic to B. The neighbor node (C) with no traffic to it from the measuring node (A) is called a “cooperative” node. Due to the broadcast nature of wireless media, the node C can overhear the traffic from the measuring node A to B. This traffic is called cross traffic. The overhearing result is then used for the measuring node to derive the quality of link A → C. Kim and Shin (2006) assume that node C cannot receive duplicate frames from its MAC layer even in the promiscuous mode, the retransmitted packets are not used for measurements. So node A counts first-time successful transmissions (Cc) within the cross traffic. In the update period, a report of overheard results (Ca) from C is sent to A, and then the PRR in this period is calculated as .

To attack cooperative probing, similar to the unicast-based passive probing, a malicious “cooperative” node does not need to decode the whole data frame correctly. As long as it can figure out the sender's address and the status (0/1) of the “retry” bit in the data frame, it can increase its count of Ca.

9.1.1.4 Unicast-Based Active Probing

When there is no egress/cross traffic, unicast-based active probing can be applied (Kim and Shin 2006). For example, if node A has no traffic to B or C, A initiates a unicast-based active probing on link A → B by generating unicast probing packets. Then, the link quality from A to B is measured by the same way as passive probing. At the same time, the quality of link A → C can be measured by cooperative probing. In this way, unicast-based active probing acts similarly as the broadcast-based active probing, with difference in that in unicast-based probing the receiver need send back an ACK to the sender when it receives the data frame correctly and the sender will retransmit data frames when no ACK receives, while in broadcast-based active probing, any node does not need to send ACK.

For unicast-based active probing, the security vulnerabilities in measuring the link quality from the measuring node (e.g. A) to the intended receiver (e.g. B) and to the “cooperative” node (e.g. C) are the same as the that in unicast-based passive probing and “cooperative” probing, respectively.

To sum up, all the existing LQM mechanisms cannot prevent a receiver cheating on the PRR. The inherent fact is that the receiver can claim a correct data frame reception without showing any evidence. To fix this vulnerability, we propose a broadcast-based secure LQM (SLQM) mechanism based on the challenge-response mechanism in Section 9.1.3. We will show that this broadcast-based mechanism can be easily applied to unicast-based and cooperative SLQM mechanisms. Before we show the solution, we would like to demonstrate the performance degradation of opportunistic routing and traditional routing under the LQM attacks.

9.1.2 Performance Demonstration

In this section, we simulate shortest anypath routing (Laufer and Kleinrock 2008), and ETF-based traditional shortest path routing (Sang et al. 2007) in a static multihop wireless network scenario to demonstrate the performance degradation of PRR-based routing protocols when malicious nodes intend to report a false PRR. The simulations are implemented within the GloMoSim simulator (Zeng et al. 1998). The candidate coordination protocol, FSA, introduced in Chapter 6 is used for opportunistic routing. IEEE 802.11b (http://standards.ieee.org/). is used as the MAC layer protocol for traditional routing. The simulated network has 50 stationary nodes randomly uniformly distributed in a d × d m2 square region. We vary d as 1600, 1800, 2000, and 2200 to examine the routing performance under different node densities. We set the carrier sensing threshold as −100 dbm. The data transmission rate is 11 mbps, and the signal receiving threshold is −83 dbm. The ACK transmission rate is 1 mbps with a signal-receiving threshold of −94 dbm. The frame reception decision is based on the SNR threshold and receiving threshold. When the SNR is larger than a threshold and the signal receiving power is above the corresponding threshold, the frame is received without error. Otherwise the frame is corrupted and dropped. To simulate a randomly lossy channel, we assume a Ground Reflection (Two-Ray) path loss model and Ricean fading model with K = 4 (Rappaport 1996) for signal propagation.

The broadcast-based LQM is used to measure the PRR on each link, such that each node broadcasts one probing packet per second, and for every 10 s (measurement period), each node reports to its neighbors the PRR on the link from the neighbors to itself. Each node updates the PRR value to its neighbors according to Equation (9.2) when it receives the report from its neighbors. The α in Equation (9.2) is chosen to be 0.9.

For normal operation (without attacks) we assume that nodes faithfully report the measured PRR. For nonsecured LQM, we assume malicious nodes will always report a 0.95 PRR no matter what the actual one is. The malicious nodes are randomly distributed in the network. To study the impact of number of malicious nodes on the performance, we vary the proportion (Pm) of malicious nodes as 0.1 and 0.3. We randomly choose ten communication pairs in the network. The application traffic takes the form of CBR (constant bit rate) flows. The packet interval of each CBR flow is 200 ms with each packet of 512 bytes. The whole simulation duration is 55 s with 30 s warm-up time, and the CBR flows start around the 30th second and end at the 50th second. Each point in the plotted results represents an average of 20 simulation runs with different seeds. Since the traffic demand is below the network capacity, the throughput performance under attack is almost the same as that under normal case. However, because some packets are routed through a suboptimal route, the end-to-end delay under attack is longer than the normal case.

Figure 9.2 shows the average end-to-end delay of the ten flows under different node densities and different portions of malicious nodes. We can see that for traditional routing, the end-to-end delay can be increased by up to 20% compared with the normal case even when there are 30% malicious nodes in the network. The opportunistic routing shows more resilience to the link quality bluffing attack. The delay performance is nearly not changed when 10% of the nodes (five nodes) are malicious in the network. When 30% of the nodes are malicious, the delay is increased by up to 10%. For both routing protocols, the delay increases when the portion of malicious nodes increases. The simulation results indicate the importance of securing LQM mechanism in order to ensure an optimal performance of traditional routing and opportunistic routing. Next, we propose a broadcast-based link-quality measurement mechanism.

Figure 9.2 Average end-to-end delay of opportunistic routing and traditional routing under link quality bluffing attack.

9.1.3 Broadcast-Based Secure Link Quality Measurement

In this section, we propose a broadcast-based secure LQM mechanism, and then analyze its security strength and its computation, storage, and communication overhead. In this volume, we assume that a malicious node always wants to report a higher PRR than the actual measured one, thus disturbing PRR-based routing performance. We also assume that a unique pairwise key has been established between each pair of neighbors. The neighborhood pairwise key establishment mechanisms have been extensively studied in multihop wireless networks (Eschenauer and Gligor 2002).

9.1.3.1 Broadcast-Based SLQM Framework

Assume a node A has N one-hop neighbors A1, A2, …, AN and needs to measure the link PRR (pi) to each of its neighbors (Ai). As in Kim and Shin (2006), the measurement is done periodically. Each measurement period consists of three consecutive phases: probing, reporting, and updating phases, which are described as follows.

Probing phase: In this phase, A broadcasts Ns packets to its neighbors. In the jth packet rj, it embeds a random number. It keeps the broadcasted packets in its buffer within this measurement period. Receiver Ai only stores the XOR-ed result (Ri) of all the correctly received packets, and the corresponding indicator vector Vi defined in Equation (9.1) that indicates the index of the received packet. Note that Ai can compute the XOR-ed result on the fly whenever it receives a new probing packet.

9.1

where Vi(j) is the jth bit from the higher (left) end of the vector Vi.

Reporting phase: When the probing phase is ended, each neighbor Ai sends A a report Repi := {Hi, Vi}, where is a keyed hash of Ri with the pairwise key shared between A and Ai. The hash function can be any of the existing cryptographic hash functions, such as MD5(http://tools.ietf.org/html/rfc1321).

Updating phase: On receiving Ai's report, A figures out how many and which packets Ai receives by examining the positions of bit ‘1’s in vector Vi. Since A keeps all the packets that it broadcasted, it computes by doing XOR of the packets that Ai claims it received. A then computes . If , A accepts this report; otherwise, it rejects the report. Suppose A counts there are bit ‘1’s in Vi, after A accepts the report, A calculates the PRR in this measurement period. A moving average method is further used to smooth the measured result. Denote the measured result in the kth measurement period as pi[k], the smoothed PRR, , at the end of the kth period is calculated as

9.2

where α is a smoothing constant in the range of (0,1).

Figure 9.3 shows an example of the broadcast-based SLQM mechanism in a measurement period. Suppose in the measuring phase, A broadcasts five probing packets (r1, …, r5), and Ai receives the packets r1, r3, and r5. In the reporting phase, Ai calculates , then sends Hi and a five-bit vector Vi = 10101 back to A. When it receives the Hi and Vi, A examines Vi and gets the indices (u1, …, uc) of the packets Ai claims it receives, then calculates . If , A accepts Ai's report; otherwise, it rejects it.

Figure 9.3 Probing and reporting phases of secure link quality measurement between A and Ai in a measurement period. Reproduced by permission of © 2008.

9.1.3.2 Security Strength

We now analyze the security strength of our broadcast-based SLQM mechanism. This mechanism achieves the security goal that prevents a malicious attacker from reporting a higher PRR than the actual one. We assume Ai is malicious in the following discussion.

First, it is computationally impossible for Ai to guess the packets that it does not receive, even when Ai overhears the other's report. For example, in Figure 9.3, if Ai wants to claim it receives r1, r3, r4, r5, it needs to create a hash value . Since it has no idea what r4 is, the only thing it can do is to guess r4. However, it is hard to make a correct guess due to the weak collision resistance property of the hash function. Given x = (r1 ⊕ r3 ⊕ r4 ⊕ r5), it is hard to find a , such that . Even Ai overhears Aj's report indicating that Aj receives r4, Ai still cannot get any information about r4 because of the one-way property of the hash function.

Second, our mechanism prevents Ai from replaying its own or another neighbor's report. According to the randomness embedded in each probing packet, even if Ai receives all the probing packets in some measurement period, it cannot replay this report in the following measurement period. Furthermore, if Ai replays Aj's report, this report cannot pass the verification by A, because A uses instead of to verify Ai's report.

9.1.3.3 Computation, Storage and Communication Overhead

Computation overhead: On the sender side, A needs to generate a random number sequence. According to its computation and storage capability, A can generate a large random number sequence to be used for several measurement periods, and refresh this sequence when it is used up. Any of the existing efficient pseudorandom number generators, such as the linear congruential generator (Greenberger 1961), can serve this purpose. To do the verification, A only needs to do XOR and hash operations, which are computationally efficient. On the receiver side, to create the report digest, each neighbor only needs to do a hash computation.

Storage overhead: On the sender side, A only needs to store the generated random numbers. Suppose the length of each random number is Lr bytes, the probing packet broadcast rate is B packet/second, and the probing phase is P seconds. Then, in a measurement period, A needs S = Lr · B · P bytes storage space. For example, if Lr = 16, B = 1, and P = 10, S = 160 bytes, which is supportable even on sensor nodes.

Communication overhead: The communication overhead of our SLQM mechanism is comparable to any existing broadcast-based probing mechanism, such as that in Couto et al. (2003). As the probing packet broadcast rate is usually low, e.g. B = 1, SLQM introduces very light local traffic into the network.

9.1.3.4 Applicability

As discussed above, our SLQM mechanism has very low computation, storage and communication overheads, so it is applicable to resource-constraint networks, such as wireless sensor networks, as well as more powerful networks, such as wireless mesh networks. Basically, broadcast-based SLQM can be implemented at application, networking and MAC layers. Our SLQM framework can also be easily applied to unicast-based and cooperative LQM with a slight modification: we embed a random number in each unicast packet (including retransmitted packets at MAC layer). For unicast-based SLQM, we can ask the receiver to attach a hash value of the received packet in the corresponding ACK. For cooperative probing, the cooperative receiver does the same thing as the broadcast-based SLQM.