Wormhole attacks can negatively affect the localization in wireless sensor networks. A typical wormhole attack can be launched by two colluding attackers, one of which sniffs packets at one point in the network and tunnels them through a wired or wireless link to another point, and the other relays them within its vicinity. In this paper, we investigate the impact of the wormhole attack on the localization and propose a novel distance-consistency-based secure localization scheme against wormhole attacks, which includes three phases of wormhole attack detection, valid locators identification and self-localization. The theoretical model is further formulated to analyze the proposed secure localization scheme. The simulation results validate the theoretical results and also demonstrate the effectiveness of our proposed scheme.
1. Introduction
Wireless sensor networks (WSNs) [1] consist of a large amount of sensor nodes which cooperate among themselves by wireless communications to solve problems in fields such as emergency response systems, military field operations, and environment monitoring systems. Nodal localization is one of the key techniques in WSNs. Most of current localization algorithms estimate the positions of location-unknown nodes based on the position information of a set of nodes (locators) and the internode measurements such as distance measurements or hop counts. Localization in WSNs has drawn growing attention from the researchers, and comprehensive approaches [2‐6] are proposed. However, most of the localization systems are vulnerable under the hostile environment where malicious attacks, such as the replay attack or compromise attack [7], can disturb the localization procedure. Security, therefore, becomes a significant concern of the localization process in hostile environment.
The wormhole attack is a typical kind of secure attacks in WSNs. It is launched by two colluding external attackers [7] which do not authenticate themselves as legitimate nodes to the network. When starting a wormhole attack, one attacker overhears packets at one point in the network, tunnels these packets through the wormhole link to another point in the network, and the other attacker broadcasts the packets among its neighborhood nodes. This can cause severe malfunctions on the routing and localization procedures in WSNs. Khabbazian et al. [8] point out how the wormhole attack impacts on building the shortest path in routing protocols. For the localization procedure under wormhole attacks, some range-free approaches [9, 10] have been proposed. We will propose a range-based secure localization scheme under wormhole attacks in this paper.
Anzeige
To prevent the effect of wormhole attack on the range-based localization, we propose a distance-consistency-based secure localization scheme including three phases: wormhole attack detection, valid locators identification and self-localization. The wormhole attack detection is designed to detect different types of wormhole attacks. For the valid locators identification, different identification schemes are proposed under different wormhole attacks. Both basic approach and enhanced approach are devised using these identification schemes. We formulate the theoretical model to analyze the probability of detecting wormhole attacks and the probability of successfully identifying all valid locators. Simulation results show the effectiveness of our proposed scheme and validate the theoretical results.
As a summary, this paper makes the following contributions:
(i)
a novel wormhole attack detection scheme is proposed to detect the existence of a wormhole attack and to further determine the type of the wormhole attack;
(ii)
a basic identification approach is designed to identify the valid locators for the sensor. Two independent algorithms are proposed to handle different wormhole attacks;
(iii)
an enhanced identification approach is developed which achieves better performances than the basic approach;
(iv)
theoretical analysis on the probability of detecting wormhole attacks and the probability of successfully identifying all valid locators are conducted and verified by simulations.
(v)
simulations are conducted to further demonstrate the effectiveness of the proposed secure localization schemes.
The remainder of this paper is organized as follows. In Section 2, we discuss the related work on the secure localization. Section 3 describe the network model and the attack model of the system. The secure localization scheme is proposed in Section 4. Section 5 gives the theoretical analysis and Section 6 presents the simulation results. Section 7 concludes the paper and outlines our future work.
Anzeige
2. Related Work
The secure localization in hostile environment has been investigated for several years and many secure localization systems have been proposed [11, 12].
To resist the compromise attack, Liu et al. [13] propose the range-based and range-free secure localization schemes, respectively. For the range-based scheme, a Minimum Mean Square Estimation method is used to filter out inconsistent beacon signals. For the range-free scheme, the nodes adopt the voting-based location estimation which can ignore the minor votes imposed by the malicious nodes. SPINE [7] utilizes the verifiable multilateration and verification of positions of mobile devices into the secure localization in the hostile network. The mechanism in [14] introduces a set of covert base stations (CBS), whose positions are unknown to the attackers, to check the validity of the nodes. ROPE [15] is a robust positioning system with a location verification mechanism that verifies the location claims of the sensors before data collection. A suit of techniques in [16] are introduced to detect malicious beacons which can negatively affect the localization of nodes by providing incorrect information. TSCD [17] proposes a novel secure localization approach to defend against the distance-consistent spoofing attack using the consistency check on the distance measurements.
To detect the existence of wormhole attacks, researchers propose some wormhole attack detection approaches. In [18], packet leashes based on the notions of geographical and temporal leashes are proposed to detect the wormhole attack. Wang and Bhargava [19] detect the wormhole attack by means of visualizing the anomalies introduced by incorrect distance measurements between two nodes caused by the wormhole attack. Reference [20] further extends the method in [19] for large scale network by selecting some feature points to reduce the overlapping issue and preserving the major topology features. In [21], a detection scheme is elaborated by checking whether the maximum number of independent neighbors of two nonneighbor nodes is larger than the threshold.
To achieve secure localization in a WSN suffered from wormhole attacks, SeRLoc [9] first detects the wormhole attack based on the sector uniqueness property and communication range violation property using directional antennas, then filters out the attacked locators. HiRLoc [10] further utilizes antenna rotations and multiple transmit power levels to improve the localization resolution. The schemes in [13] can also be applied into the localization against wormhole attacks. However, SeRLoc and HiRLoc need extra hardware such as directional antennae, and cannot obtain satisfied localization performance in that some attacked locators may still be undetected. Reference [13] requires a large amount of computation and possibly becomes incompetent when malicious locators are more than the legitimate ones. In [22], Chen et al. propose to make each locator build a conflicting-set and then the sensor can use all conflicting sets of its neighboring locators to filter out incorrect distance measurements of its neighboring locators. The limitation of the scheme is that it only works properly when the system has no packet loss. As the attackers may drop the packets purposely, the packet loss is inevitable when the system is under a wormhole attack. Compared to the scheme in [22], the distance-consistency-based secure localization scheme proposed in this paper can obtain high localization performance when the system has certain packet losses. Furthermore, it works well even when the malicious locators are more than the legitimate ones, which causes the malfunction of the scheme in [13].
3. Problem Formulation
In this section, we build the network model and the attack model, describe the related definitions, and analyze the effect of the wormhole attack on the range-based localization, after which we classify the locators into three categories.
3.1. Network Model
Three different types of nodes are deployed in the network, including locators, sensors, and attackers. The locators, with their own locations known in advance (by manual deployment or GPS devices), are deployed independently in the network with the probability of Poisson distribution. Each locator has a unique identification. The attackers collude in pairs to launch a wormhole attack to interfere with the self-localization of the sensors. All the nodes in the network are assumed to have the same transmission range . However, the communication range between two wormhole attackers can be larger than , as they can communicate with each other using certain communication technique.
The sensors measure the distances to their neighboring locators using the Received Signal Strength Indicator (RSSI) method; the measurement error of the distance follows a normal distribution , where the mean value and the standard deviation is within a threshold. The sensors estimate their locations using the Maximum Likelihood Estimation (MLE) method [3]: Assume that the coordinates of the neighboring locators of the sensor are , respectively, and the distance measurements from the locators to the sensor are , the location of the sensor satisfies
(1)
By subtracting the last equation from each of the rest in (1), we can obtain the following equations represented as a linear equation , where
(2)
Using the MLE method, the location of the sensor can be obtained as .
3.2. Attack Model
The network is assumed to be deployed in hostile environment where wormhole attacks exist to disrupt the localization of sensors. During the wormhole attack, one attacker sniffs packets at one point in the network and tunnels them through the wormhole link to another point. Being as external attackers that cannot compromise legitimate nodes or their cryptographic keys, the wormhole attackers cannot acquire the content, for example, the type of the sniffed packets. However, the attackers may drop off the received packets randomly which severely deteriorates the sensor's localization process. We assume that the length of the wormhole link is larger than so that the endless packet transmission loop caused by both attackers is avoided.
The wormhole attack endured by a node can be classified into duplex wormhole attack and simplex wormhole attack according to the geometrical relation between the node and the attackers. A node is under a duplex wormhole attack when it lies in the common transmission area of these two attackers; a node is under a simplex wormhole attack when it lies in the transmission area of only one of these two attackers but not in the common transmission area of both. Figure 1 shows the impact of the wormhole attack on the distance measurement of the sensor. When measuring the distance, the sensor broadcasts a request signal and waits for the responding beacon signals from the locators within its neighboring vicinity, based on which the sensor can use the RSSI method to estimate the distances to neighboring locators. For the duplex wormhole attack as shown in Figure 1(a), when sends a beacon message to the sensor , will only get the distance measurement as instead of the actual distance because the RSSI received by just reflects the propagational attenuation from to . For 's beacon message, as the packet will travel through two different paths to reach , and , respectively, will obtain two distance measurements and . For 's beacon message, it travels through three paths to reach , , , and , respectively, thus will get three distance measurements as , and . For the simplex wormhole attack as shown in Figure 1(b), when receives the beacon message from , it will measure the distance to as . For , two different distance measurements and will be obtained. Thus, the locators which can communicate with the sensor via the wormhole link will introduce incorrect distance measurements.
All the locators that can exchange messages with the sensor, either via the wormhole link or not, are called neighboring locators (-locators) of the sensor. Among these neighboring locators, the ones that can exchange messages with the sensor via the wormhole link are called dubious locators (-locators), as their distance measurements may be incorrect and distort the localization; the locators that lie in the transmission range of the sensor are called valid locators (-locators), as the sensor can obtain correct distance measurements with respect to them and assist the localization.
In this paper, we denote the set of -locators, -locators, and -locators as , and . For the scenario in Figure 1(a), , , and . It is obvious that .
4. Secure Localization Scheme Against Wormhole Attack
As the -locators will negatively affect the localization of the sensor, it is critical for the sensor to identify the -locators before the self-localization. In this section, we propose a novel secure localization scheme against wormhole attacks, which includes three phases shown in Figure 2, namely the wormhole attack detection, valid locators identification and self-localization.
Figure 2
Flow chart of the proposed secure localization scheme.
×
(i)
Wormhole Attack Detection: The sensor detects the existence of a wormhole attack using the proposed detection schemes, and identifies whether it is under a duplex wormhole attack or a simplex wormhole attack.
(ii)
Valid Locators Identification: Corresponding to the duplex wormhole attack and the simplex wormhole attack, the sensor identifies the -locators using different identification approaches.
(iii)
Self-localization: After identifying enough -locators, the sensor conducts the self-localization using the MLE method with correct distance measurements.
4.1. Wormhole Attack Detection
We assume that each locator periodically broadcasts a beacon message within its neighboring vicinity. The beacon message will contain the ID and location information of the source locator. When the network is threatened by a wormhole attack, some affected locators will detect the abnormality through beacon message exchanges. The following scenarios are considered abnormal for locators: a locator receives the beacon message sent by itself; a locator receives more than one copy of the same beacon message from another locator via different paths; a locator receives a beacon message from another locator, whose location calculated based on the received message is outside the transmission range of receiving locator. When the locator detects the message abnormality, it will consider itself under a wormhole attack. Moreover, if the locator detects the message abnormality under the first scenario, that is, the locator receives the beacon message sent by itself, it will further derive that it is under a duplex wormhole attack. The beacon message has two additional bits to indicate these two statuses for each locator:
(i)
detection bit: this bit will be set to 1 if the locator detects the message abnormality through beacon message exchanges; otherwise, this bit will be 0;
(ii)
type bit: this bit will be 1 if the locator detects itself under a duplex wormhole attack; otherwise, this bit will be 0.
When the sensor performs self-localization, it broadcasts a Loc_req message to its -locators. As soon as the locator receives the Loc_req message from the sensor, it replies with an acknowledgement message Loc_ack similar to the beacon message, which includes the ID and location information of the locator. The Loc_ack message also includes above two status bits. When the sensor receives the Loc_ack message, it can measure the distance from the sending locator to itself using the RSSI. The sensor also calculates the response time of each -locator based on the Loc_ack message using the approach in [17] to countervail the random delay on the MAC layer of the locator: when broadcasting the Loc_req packet, the sensor records the local time . Every locator gets the local time by time-stamping the packet at the MAC layer (i.e., the time when the packet is received at the MAC layer) instead of time-stamping the packet at the application layer. Similarly, when responding to the Loc_ack packet, the locator puts the local time at the MAC layer; both and are attached in the Loc_ack packet. When receiving the Loc_ack packet, the sensor gets its local time , and calculates the response time of the locator as . Note that this response time only eliminates the random delay at the MAC layer of the locators, but not the delay affected by attackers.
When conducting the localization, the sensor may also detect the message abnormality when it receives the Loc_req message sent by itself. Moreover, the sensor can check the detection bit of the Loc_ack message to decide if its -locator is under a wormhole attack or not.
We propose to use the following two detection schemes for the sensor to detect the wormhole attack.
Detection Scheme D1
If the sensor detects that it receives the Loc_req message sent from itself, it can determine that it is currently under a duplex wormhole attack. For example, when the sensor is under the duplex wormhole attack as shown in Figure 1(a), the Loc_req message transmitted by the sensor can travel from via the wormhole link to and then arrive at after being relayed by . Similarly, the Loc_req message can also travel from through the wormhole link to and then be received by . Thus, can determine that it is currently under a duplex wormhole attack.
Detection Scheme D2
If the sensor detects that the detection bit of the received Loc_ack message from any -locator is set to 1, can determine that it is under a simplex wormhole attack. Note that when using detection scheme D2, the sensor may generate a false alarm if the sensor is outside the transmission areas of the attackers but any of its -locators is inside the transmission areas of the attackers. However, this will only trigger the validate locators identification process but not affect the self-localization result.
The pseudocode of the wormhole attack detection is shown in Algorithm 1. The sensor broadcasts a Loc_req message for self-localization. When receiving the Loc_req message, each -locator replies a Loc_ack message with the status bits indicating whether it has detected the abnormality. The sensor measures the distances to its -locators based on the Loc_ack messages using RSSI method and calculates the response time of each -locator. If the sensor receives the Loc_req message sent by itself (detection scheme D1), it determines that it is under a duplex wormhole attack. Otherwise, if the sensor is informed by any -locator that the abnormality is detected (detection scheme D2), it declares that it is under a simplex wormhole attack. If no wormhole attack is detected, the sensor conducts the MLE localization.
Algorithm 1: Wormhole attack detection scheme.
1: Sensor broadcasts a Loc_req message.
2: Each -locator sends a Loc_ack message to the sensor,
including the message abnormality detection result.
3: Sensor waits for the Loc_ack messages to measure the
distance to each -locator and to calculate the response
time of each -locator.
4: if sensor detects the attack using scheme D1 then
5: A duplex wormhole attack is detected.
6: else if sensor detects the attack using scheme D2 then
7: A simplex wormhole attack is detected.
8: else
9: No wormhole attack is detected.
10: end if
4.2. Basic Valid Locators Identification Approach
4.2.1. Duplex Wormhole Attack
When detecting that it is currently under a duplex wormhole attack, the sensor tries to identify all its -locators before the self-localization. Take in Figure 1(a) for example, when receiving the Loc_req message from the sensor, will respond a Loc_ack message to the sensor. As the sensor lies in the transmission range of , the Loc_ack message can be received by the sensor directly. In addition, the Loc_ack message can also travel from via the wormhole link to then arrive at the sensor. Therefore, the sensor can receive the Loc_ack message from for more than once. However, there will be three different scenarios: the locator lies in the transmission range of the sensor and its message is received by the sensor for three times (such as in Figure 1(a)); the locator lies out of the transmission range of the sensor and its message is received by the sensor for twice (such as in Figure 1(a)); the locator lies in the transmission range of the sensor and its message is received by the sensor for twice (such as in Figure 1(a)). We can see that and are -locators, but not . The sensor will use the following valid locator identification scheme to find the -locators.
Identification Scheme I1
When the sensor is under a duplex wormhole attack, if the sensor receives the Loc_ack message of an -locator for three times and the type bit in the Loc_ack message is set to 1, this -locator will be considered as a -locator (such as in Figure 1(a)). As the sensor only countervails the MAC layer delay of the locators but not that of the attackers when calculating the response time, the message traveling via the wormhole link has taken a longer response time. Thus, the distance measurement based on the Loc_ack message from this -locator which takes the shortest response time will be considered correct. If the sensor receives the Loc_ack message of an -locator just twice and the type bit in the Loc_ack message is set to 1, this -locator will be treated as a -locator (such as in Figure 1(a)). For the last scenario, if the sensor receives the Loc_ack message of an -locator twice and the type bit in the Loc_ack message is set to 0, this -locator will be considered as a -locator, and the distance measurement based on the Loc_ack message with a shorter response time will be considered as correct (such as in Figure 1(a)).
Distance Consistency Property of Valid Locators
Assuming a set of locators and corresponding measured distances , where is the location of locator and is the measured distance from the sensor to , . Based on and , the estimated location of the sensor is . The mean square error of the location estimation is . The distance consistency property of valid locators states that the mean square error of the location estimation based on the correct distance measurements is lower than a small threshold while the mean square error of the location estimation based on the distance measurements which contains some incorrect ones is not lower than the threshold.
We can further identify more -locators using the distance consistency property of valid locators.
Identification Scheme I2
If the sensor has determined no less than two valid locators using identification scheme I1, it can identify other valid locators by checking whether the distance estimation is consistent. A predefined threshold of the mean square error is determined, that is, a distance estimation with a mean square error smaller than is considered to be consistent. As shown in Figure 1(a), the sensor can identify and as -locators and obtain the correct distance measurements to them. For other undetermined locators, the sensor can identify them one by one. For example, to check whether is a -locator, the sensor can estimate its own location based on the distance measurements to and . As the distance measurement to is incorrect, the mean square error of the estimated distance measurements may exceed , which means that is not a -locator. When the sensor checks the distance consistency of , and , it can get that the mean square error is lower than , thus is treated as a -locator, and the distance measurement to is correct. After checking each of the undetermined -locators, the sensor can identify all -locators with the correct distance measurements.
4.2.2. Simplex Wormhole Attack
If the sensor detects that it is under a simplex wormhole attack, it will adopt the following valid locators identification schemes.
Identification Scheme I3
When the sensor under a simplex wormhole attack as shown in Figure 1(b), if the sensor receives the Loc_ack message of an -locator twice, this -locator will be considered as a -locator. For example, when in Figure 1(b) replies a Loc_ack message to the sensor, this message will travel through two different paths to the sensor, one directly from to the sensor and the other from to via the wormhole link to the sensor. Therefore, the sensor can conclude that is a -locator. To further obtain the correct distance measurement to , the sensor compares the response times of the Loc_ack message from through different paths, and the distance measurement with a shorter response time is considered correct. Similarly, can also be identified as a -locator and its correct distance measurement can be obtained.
The following spatial property can also be used to identify -locators:
Spatial Property
The sensor cannot receive messages from two -locators simultaneously if the distance between these two -locators is larger than .
Identification Scheme I4
When the sensor is under a simplex wormhole attack as shown in Figure 1(b), if the spatial property is violated by two -locators, it is obviously that one of them is a -locator and the other is a -locator. Take and in Figure 1(b) for example, the distance between them is larger than , after receiving Loc_ack messages from them, the sensor can detect that the spatial property does not hold by these two -locators. The response times of both -locators can be used to differentiate the -locator from the -locator. As the Loc_ack message from travels via the wormhole link to the sensor, it will take a longer response time than that from . The sensor will regard as a -locator and as a -locator because has a shorter response time. The distance measurement to is also considered correct.
We can also use the distance consistency property of valid locators to identify more -locators when the sensor is under a simplex wormhole attack.
Identification Scheme I5
When the sensor is under a simplex wormhole attack, similar to identification scheme I2, if the sensor detects at least two -locators using identification schemes I3 and I4, it can identify other -locators based on the distance consistency property of -locators. Take the scenario in Figure 1(b) for example, the sensor can identify , and as -locators and obtain the correct distance measurements to them. The sensor can further identify other -locators by checking the distance consistency. A mean square error smaller than can be obtained when the sensor estimates its location based on , and because they are all -locators. So the sensor can conclude that is a -locator and the distance measurement to is correct.
The procedure of basic valid locators identification approach is listed in Algorithm 2: If the sensor detects that it is under a duplex wormhole attack, it will conduct identification scheme I1 to detect -locators. As the distance consistency check needs as least three locators, if the sensor identifies no less than two -locators, it can use identification scheme I2 to identify other -locators. On the other hand, if the sensor detects that it is under a simplex wormhole attack, it adopts identification schemes I3 and I4 to identify the -locators. After that, if at least two -locators are identified, the sensor conducts identification scheme I5 to detect other -locators.
In the basic valid locators identification approach, if the sensor identifies less than three -locators, it will terminate the self-localization because the MLE method used in the self-localization needs at least three distance measurements. However, when using the identification schemes based on distance consistency property of -locators, many -locators may not be identified if the threshold of mean square error, , is set inappropriately a small value.
To overcome the above problem, we propose an enhanced valid locators identification approach which can adaptively adjust the threshold to make the sensor easier to identify more -locators: If the sensor detects that it is under a duplex wormhole attack, it conducts identification scheme I1 to detect -locators. If the sensor identifies no less than two -locators, it repeats to identify other -locators using identification scheme I2 and update the with an increment of until at least three -locators are identified or is larger than . On the other hand, if the sensor detects that it is under a simplex wormhole attack, it adopts schemes I3 and I4 to identify the -locators. If at least two -locators are identified, the sensor repeats to conduct scheme I5 to detect other -locators and update with an increment of until at least three -locators are identified or is larger than . The procedure of the enhanced valid locators identification approach is listed in Algorithm 3.
10: Conduct schemes I3 and I4 to identify -locators.
11: if the identified -locators 2 then
12: repeat
13: Conduct scheme I5 to identify other -locators.
14:
15: until the identified -locators 3 or
16: end if
17: end if
After the wormhole attack detection and valid locators identification, the sensor can identify -locators from its -locators. Furthermore, the sensor can estimate the correct distance measurements to the -locators. When the sensor obtains at least three correct distance measurements to its -locators, it conducts the MLE localization based on these distance measurements and the locations of the corresponding -locators.
5. Theoretical Analysis
In this section, we formulate the mathematical models for the probability of wormhole attack detection and the probability of successfully identifying all the -locators. To simplify our description, we denote the disk centered at with radius as . The overlapped region of the transmission areas of two attackers is denoted as and the overlapped region of the transmission areas of attacker and sensor is denoted as , which are illustrated in Figure 3.
Figure 3
Theoretical analysis of the mathematical model of a wormhole attack.
×
5.1. Probability of Wormhole Attack Detection
For the probability of the wormhole attack detection, we denote it as , including the probability of the duplex wormhole attack detection and the probability of the simplex wormhole attack detection . Thus,
(3)
For , it equals to the probability that the sensor lies in the region . Therefore,
(4)
Here,
(5)
where is the length of the wormhole link.
For , the probability that the sensor lies in region in Figure 3 equals to . When the sensor lies in this region, the sensor can detect the wormhole attack only if at least one locator lies in or each of the regions and in Figure 3 has at least one locator, which means that the -locators can detect the abnormality and inform the sensor. We define the event that at least one locator lies in as and the event that each of the regions and in Figure 3 has at least one locator as . Thus,
(6)
As the locators follow Poisson distribution, we get
(7)
where is the density of the locators. Therefore, the probability that the sensor can detect the simplex wormhole attack can be expressed as follows:
(8)
Therefore, we can get
(9)
5.2. Probability of Successfully Identifying All -locators
For the probability that the sensor can successfully identify all the -locators, we denote it as . Similarly,
(10)
where is the probability that the sensor can successfully identify all the -locators when under a duplex wormhole attack, and is for the simplex wormhole attack.
The probability that the sensor is under a duplex wormhole attack equals to as shown in Figure 3. The sensor is capable of successfully identifying all the -locators under a duplex wormhole attack means that it can identify at least two -locators using identification scheme I1. That is, the region in Figure 1(a) has at least two locators. Thus,
(11)
where
(12)
and is the area of in Figure 1(a). We can approximate by
(13)
where
(14)
We can get
(15)
When the sensor is under a wormhole attack, the probability that it lies in the domain in Figure 3 equals to . When lying in the domain, if the sensor can identify at least two -locators using identification schemes I3 and I4, it can successfully identify other -locators. Assuming that the sensor can identify -locators using scheme I3 and identify -locators using scheme I4, the probability that the sensor can identify at least two -locators using schemes I3 and I4 is calculated as
(16)
where
(17)
Here, is the region in which is more than away from at least one of the locators in , that is the area of the corresponding shading region in Figure 3. Note that if any locator lies in , the sensor can identify it as a -locator using identification scheme I4.
Thus,
(18)
where
(19)
Therefore, we can obtain
(20)
6. Simulation Evaluation
In this section, we present the simulation results to demonstrate the effectiveness of the proposed secure localization scheme and to validate our theoretical results. The network parameters are set as follows: the transmission range of all types of nodes is identical and is set to 15 m; the density of locators /m2 (with the average degree around 4); the standard deviation of the distance measurement ; the label of the axis denotes the ratio of the length of the wormhole link (i.e., the distance between two attackers) to the transmission range. The threshold for the distance consistency . For the enhanced secure localization scheme, and .
Figure 4 demonstrates the performance comparison of the probability of detecting the wormhole attack between our scheme and SeRLoc scheme. It can be observed that our scheme obtains a good performance with the probabilities higher than 98% for different values of . Although both schemes have the similar performance when , our scheme outperforms SeRLoc scheme, especially when .
Figure 4
Probability of wormhole attack detection: Our scheme versus SeRLoc scheme.
×
Figure 5 demonstrates the validity of our theoretical analysis on the probability of the wormhole attack detection. We find that the maximum difference between the simulation and the theoretical result is smaller than 0.4%, which indicates that the theoretical result matches the simulation result very well.
Figure 5
Probability of wormhole attack detection: Simulation versus Theoretical.
×
Figure 6 shows the performance comparison, in terms of the probability of successful localization, of our proposed basic scheme, SeRLoc scheme, the consistency scheme [13], and the scheme without any detection process when the sensor is under a wormhole attack. The SeRLoc scheme first identifies some -locators using the sector uniqueness property and communication range violation property, then conducts self-localization based on the rest locators. However, SeRLoc scheme does not distinguish the duplex wormhole attack and simplex wormhole attack, and the communication range violation property may be invalid under the duplex wormhole attack. The consistency scheme identifies the -locators based on the consistency check of the estimation result. The locator which is the most inconsistent one will be considered as a -locator. In this simulation, the localization result is considered successful when , where (and ) denotes the localization error with (and without) using the secure localization scheme, is the factor of localization error tolerance (0.1 in our simulations). The performance of the scheme without any detection process shows the severe impact of the wormhole attack on the localization process, which makes the localization totally defunct when is larger than 2. Figure 6 shows that our proposed scheme obtains much better performance than the other schemes.
Figure 6
Probability of successful localization.
×
In Figure 7, we compare the basic secure localization scheme with the enhanced secure localization scheme. The enhanced scheme outperforms the basic scheme a bit higher (with the maximum improvement of about 3%) when .
Figure 7
Probability of successful localization: Basic scheme versus Enhanced scheme.
×
Figure 8 shows the performance of successful localization of the enhanced scheme under different locator densities. It demonstrates that the increase of the locator density has a greater improvement when than when .
Figure 8
Probability of successful localization under different locator densities.
×
Figure 9 is to validate the correctness of the theoretical result of the probability of successfully identifying all -locators. The maximum difference between the simulation and the theoretical result is about 4%, showing that the theoretical result matches the simulation result well.
Figure 9
Probability of successfully identifying all-locators: Simulation versus Theoretical.
×
7. Conclusion and Future Work
In this paper, we analyze the impact of the wormhole attack on the range-based localization. We propose a novel distance-consistency-based secure localization mechanism against wormhole attacks including the wormhole attack detection, valid locators identification and self-localization. To analyze the performance of our proposed scheme, we build the theoretical model for calculating the probability of detecting the wormhole attack and the probability of identifying all -locators. We also present the simulation results to demonstrate the out-performance of our schemes and the validity of the proposed theoretical analysis. Although the proposed approach is described based on the RSSI method, it can be easily applied to the localization approaches based on the time-of-arrival (ToA) or time-difference-of-arrival (TDoA) methods.
In the future, our work will focus on the secure localization when the sensor is under multiple wormholes' attack simultaneously. We also intend to consider the secure localization when different nodes have different transmission ranges.
Acknowledgments
This work is supported in part by Grants PolyU 5236/06E, PolyU 5243/08E, A-PJ16, NSFC 60873223, NSFC 90818010, and ZJU-SKL ICT0903.
Open Access
This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (
https://creativecommons.org/licenses/by/2.0
), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
. However, the communication range between two wormhole attackers can be larger than
, as they can communicate with each other using certain communication technique.
, where the mean value
and the standard deviation
is within a threshold. The sensors estimate their locations using the Maximum Likelihood Estimation (MLE) method [3]: Assume that the coordinates of the
neighboring locators of the sensor are
, respectively, and the distance measurements from the
locators to the sensor are
, the location of the sensor
satisfies
, where
.
so that the endless packet transmission loop caused by both attackers is avoided.
sends a beacon message to the sensor
,
will only get the distance measurement as
instead of the actual distance
because the RSSI received by
just reflects the propagational attenuation from
to
. For
's beacon message, as the packet will travel through two different paths to reach
,
and
, respectively,
will obtain two distance measurements
and
. For
's beacon message, it travels through three paths to reach
,
,
, and
, respectively, thus
will get three distance measurements as
, and
. For the simplex wormhole attack as shown in Figure 1(b), when
receives the beacon message from
, it will measure the distance to
as
. For
, two different distance measurements
and
will be obtained. Thus, the locators which can communicate with the sensor via the wormhole link will introduce incorrect distance measurements.
-locators) of the sensor. Among these neighboring locators, the ones that can exchange messages with the sensor via the wormhole link are called dubious locators (
-locators), as their distance measurements may be incorrect and distort the localization; the locators that lie in the transmission range of the sensor are called valid locators (
-locators), as the sensor can obtain correct distance measurements with respect to them and assist the localization.
-locators,
-locators, and
-locators as
, and
. For the scenario in Figure 1(a),
,
, and
. It is obvious that
.
-locators will negatively affect the localization of the sensor, it is critical for the sensor to identify the
-locators before the self-localization. In this section, we propose a novel secure localization scheme against wormhole attacks, which includes three phases shown in Figure 2, namely the wormhole attack detection, valid locators identification and self-localization.
-locators using different identification approaches.
-locators, the sensor conducts the self-localization using the MLE method with correct distance measurements.
a locator receives the beacon message sent by itself;
a locator receives more than one copy of the same beacon message from another locator via different paths;
a locator receives a beacon message from another locator, whose location calculated based on the received message is outside the transmission range of receiving locator. When the locator detects the message abnormality, it will consider itself under a wormhole attack. Moreover, if the locator detects the message abnormality under the first scenario, that is, the locator receives the beacon message sent by itself, it will further derive that it is under a duplex wormhole attack. The beacon message has two additional bits to indicate these two statuses for each locator:
-locators. As soon as the locator receives the Loc_req message from the sensor, it replies with an acknowledgement message Loc_ack similar to the beacon message, which includes the ID and location information of the locator. The Loc_ack message also includes above two status bits. When the sensor receives the Loc_ack message, it can measure the distance from the sending locator to itself using the RSSI. The sensor also calculates the response time of each
-locator based on the Loc_ack message using the approach in [17] to countervail the random delay on the MAC layer of the locator: when broadcasting the Loc_req packet, the sensor records the local time
. Every locator gets the local time
by time-stamping the packet at the MAC layer (i.e., the time when the packet is received at the MAC layer) instead of time-stamping the packet at the application layer. Similarly, when responding to the Loc_ack packet, the locator puts the local time
at the MAC layer; both
and
are attached in the Loc_ack packet. When receiving the Loc_ack packet, the sensor gets its local time
, and calculates the response time of the locator as
. Note that this response time only eliminates the random delay at the MAC layer of the locators, but not the delay affected by attackers.
-locator is under a wormhole attack or not.
detects that it receives the Loc_req message sent from itself, it can determine that it is currently under a duplex wormhole attack. For example, when the sensor is under the duplex wormhole attack as shown in Figure 1(a), the Loc_req message transmitted by the sensor can travel from
via the wormhole link to
and then arrive at
after being relayed by
. Similarly, the Loc_req message can also travel from
through the wormhole link to
and then be received by
. Thus,
can determine that it is currently under a duplex wormhole attack.
detects that the detection bit of the received Loc_ack message from any
-locator is set to 1,
can determine that it is under a simplex wormhole attack. Note that when using detection scheme D2, the sensor may generate a false alarm if the sensor is outside the transmission areas of the attackers but any of its
-locators is inside the transmission areas of the attackers. However, this will only trigger the validate locators identification process but not affect the self-localization result.
-locator replies a Loc_ack message with the status bits indicating whether it has detected the abnormality. The sensor measures the distances to its
-locators based on the Loc_ack messages using RSSI method and calculates the response time of each
-locator. If the sensor receives the Loc_req message sent by itself (detection scheme D1), it determines that it is under a duplex wormhole attack. Otherwise, if the sensor is informed by any
-locator that the abnormality is detected (detection scheme D2), it declares that it is under a simplex wormhole attack. If no wormhole attack is detected, the sensor conducts the MLE localization.
-locator sends a Loc_ack message to the sensor,
-locator and to calculate the response
-locator.
-locators before the self-localization. Take
in Figure 1(a) for example, when receiving the Loc_req message from the sensor,
will respond a Loc_ack message to the sensor. As the sensor lies in the transmission range of
, the Loc_ack message can be received by the sensor directly. In addition, the Loc_ack message can also travel from
via the wormhole link to
then arrive at the sensor. Therefore, the sensor can receive the Loc_ack message from
for more than once. However, there will be three different scenarios:
the locator lies in the transmission range of the sensor and its message is received by the sensor for three times (such as
in Figure 1(a));
the locator lies out of the transmission range of the sensor and its message is received by the sensor for twice (such as
in Figure 1(a));
the locator lies in the transmission range of the sensor and its message is received by the sensor for twice (such as
in Figure 1(a)). We can see that
and
are
-locators, but not
. The sensor will use the following valid locator identification scheme to find the
-locators.
-locator for three times and the type bit in the Loc_ack message is set to 1, this
-locator will be considered as a
-locator (such as
in Figure 1(a)). As the sensor only countervails the MAC layer delay of the locators but not that of the attackers when calculating the response time, the message traveling via the wormhole link has taken a longer response time. Thus, the distance measurement based on the Loc_ack message from this
-locator which takes the shortest response time will be considered correct. If the sensor receives the Loc_ack message of an
-locator just twice and the type bit in the Loc_ack message is set to 1, this
-locator will be treated as a
-locator (such as
in Figure 1(a)). For the last scenario, if the sensor receives the Loc_ack message of an
-locator twice and the type bit in the Loc_ack message is set to 0, this
-locator will be considered as a
-locator, and the distance measurement based on the Loc_ack message with a shorter response time will be considered as correct (such as
in Figure 1(a)).
and corresponding measured distances
, where
is the location of locator
and
is the measured distance from the sensor to
,
. Based on
and
, the estimated location of the sensor is
. The mean square error of the location estimation is
. The distance consistency property of valid locators states that the mean square error of the location estimation based on the correct distance measurements is lower than a small threshold while the mean square error of the location estimation based on the distance measurements which contains some incorrect ones is not lower than the threshold.
-locators using the distance consistency property of valid locators.
of the mean square error is determined, that is, a distance estimation with a mean square error smaller than
is considered to be consistent. As shown in Figure 1(a), the sensor can identify
and
as
-locators and obtain the correct distance measurements to them. For other undetermined locators, the sensor can identify them one by one. For example, to check whether
is a
-locator, the sensor can estimate its own location based on the distance measurements to
and
. As the distance measurement to
is incorrect, the mean square error of the estimated distance measurements may exceed
, which means that
is not a
-locator. When the sensor checks the distance consistency of
, and
, it can get that the mean square error is lower than
, thus
is treated as a
-locator, and the distance measurement to
is correct. After checking each of the undetermined
-locators, the sensor can identify all
-locators with the correct distance measurements.
-locator twice, this
-locator will be considered as a
-locator. For example, when
in Figure 1(b) replies a Loc_ack message to the sensor, this message will travel through two different paths to the sensor, one directly from
to the sensor and the other from
to
via the wormhole link to the sensor. Therefore, the sensor can conclude that
is a
-locator. To further obtain the correct distance measurement to
, the sensor compares the response times of the Loc_ack message from
through different paths, and the distance measurement with a shorter response time is considered correct. Similarly,
can also be identified as a
-locator and its correct distance measurement can be obtained.
-locators:
-locators simultaneously if the distance between these two
-locators is larger than
.
-locators, it is obviously that one of them is a
-locator and the other is a
-locator. Take
and
in Figure 1(b) for example, the distance between them is larger than
, after receiving Loc_ack messages from them, the sensor can detect that the spatial property does not hold by these two
-locators. The response times of both
-locators can be used to differentiate the
-locator from the
-locator. As the Loc_ack message from
travels via the wormhole link to the sensor, it will take a longer response time than that from
. The sensor will regard
as a
-locator and
as a
-locator because
has a shorter response time. The distance measurement to
is also considered correct.
-locators when the sensor is under a simplex wormhole attack.
-locators using identification schemes I3 and I4, it can identify other
-locators based on the distance consistency property of
-locators. Take the scenario in Figure 1(b) for example, the sensor can identify
, and
as
-locators and obtain the correct distance measurements to them. The sensor can further identify other
-locators by checking the distance consistency. A mean square error smaller than
can be obtained when the sensor estimates its location based on
, and
because they are all
-locators. So the sensor can conclude that
is a
-locator and the distance measurement to
is correct.
-locators. As the distance consistency check needs as least three locators, if the sensor identifies no less than two
-locators, it can use identification scheme I2 to identify other
-locators. On the other hand, if the sensor detects that it is under a simplex wormhole attack, it adopts identification schemes I3 and I4 to identify the
-locators. After that, if at least two
-locators are identified, the sensor conducts identification scheme I5 to detect other
-locators.
detects a duplex wormhole attack then
-locators.
-locators
2 then
-locators.
detects a simplex wormhole attack then
-locators.
-locators
2 then
-locators.
-locators, it will terminate the self-localization because the MLE method used in the self-localization needs at least three distance measurements. However, when using the identification schemes based on distance consistency property of
-locators, many
-locators may not be identified if the threshold of mean square error,
, is set inappropriately a small value.
to make the sensor easier to identify more
-locators: If the sensor detects that it is under a duplex wormhole attack, it conducts identification scheme I1 to detect
-locators. If the sensor identifies no less than two
-locators, it repeats to identify other
-locators using identification scheme I2 and update the
with an increment of
until at least three
-locators are identified or
is larger than
. On the other hand, if the sensor detects that it is under a simplex wormhole attack, it adopts schemes I3 and I4 to identify the
-locators. If at least two
-locators are identified, the sensor repeats to conduct scheme I5 to detect other
-locators and update
with an increment of
until at least three
-locators are identified or
is larger than
. The procedure of the enhanced valid locators identification approach is listed in Algorithm 3.
detects a duplex wormhole attack then
-locators.
-locators
2 then
-locators.
-locators
3 or
detects a simplex wormhole attack then
-locators.
-locators
2 then
-locators.
-locators
3 or
-locators from its
-locators. Furthermore, the sensor can estimate the correct distance measurements to the
-locators. When the sensor obtains at least three correct distance measurements to its
-locators, it conducts the MLE localization based on these distance measurements and the locations of the corresponding
-locators.
-locators. To simplify our description, we denote the disk centered at
with radius
as
. The overlapped region of the transmission areas of two attackers is denoted as
and the overlapped region of the transmission areas of attacker
and sensor
is denoted as
, which are illustrated in Figure 3.
, including the probability of the duplex wormhole attack detection
and the probability of the simplex wormhole attack detection
. Thus,
, it equals to the probability that the sensor lies in the region
. Therefore,
is the length of the wormhole link.
, the probability that the sensor lies in region
in Figure 3 equals to
. When the sensor lies in this region, the sensor can detect the wormhole attack only if at least one locator lies in
or each of the regions
and
in Figure 3 has at least one locator, which means that the
-locators can detect the abnormality and inform the sensor. We define the event that at least one locator lies in
as
and the event that each of the regions
and
in Figure 3 has at least one locator as
. Thus,
is the density of the locators. Therefore, the probability that the sensor can detect the simplex wormhole attack can be expressed as follows:
-locators
-locators, we denote it as
. Similarly,
is the probability that the sensor can successfully identify all the
-locators when under a duplex wormhole attack, and
is for the simplex wormhole attack.
as shown in Figure 3. The sensor is capable of successfully identifying all the
-locators under a duplex wormhole attack means that it can identify at least two
-locators using identification scheme I1. That is, the region
in Figure 1(a) has at least two locators. Thus,
domain in Figure 3 equals to
. When lying in the
domain, if the sensor can identify at least two
-locators using identification schemes I3 and I4, it can successfully identify other
-locators. Assuming that the sensor can identify
-locators using scheme I3 and identify
-locators using scheme I4, the probability that the sensor can identify at least two
-locators using schemes I3 and I4 is calculated as
is the region in
which is more than
away from at least one of the locators in
, that is the area of the corresponding shading region
in Figure 3. Note that if any locator lies in
, the sensor can identify it as a
-locator using identification scheme I4.
of all types of nodes is identical and is set to 15 m; the density of locators
/m2 (with the average degree around 4); the standard deviation of the distance measurement
; the label
of the
axis denotes the ratio of the length of the wormhole link (i.e., the distance between two attackers) to the transmission range. The threshold for the distance consistency
. For the enhanced secure localization scheme,
and
.
. Although both schemes have the similar performance when
, our scheme outperforms SeRLoc scheme, especially when
.
-locators using the sector uniqueness property and communication range violation property, then conducts self-localization based on the rest locators. However, SeRLoc scheme does not distinguish the duplex wormhole attack and simplex wormhole attack, and the communication range violation property may be invalid under the duplex wormhole attack. The consistency scheme identifies the
-locators based on the consistency check of the estimation result. The locator which is the most inconsistent one will be considered as a
-locator. In this simulation, the localization result is considered successful when
, where
(and
) denotes the localization error with (and without) using the secure localization scheme,
is the factor of localization error tolerance (0.1 in our simulations). The performance of the scheme without any detection process shows the severe impact of the wormhole attack on the localization process, which makes the localization totally defunct when
is larger than 2. Figure 6 shows that our proposed scheme obtains much better performance than the other schemes.
.
than when
.
-locators. The maximum difference between the simulation and the theoretical result is about 4%, showing that the theoretical result matches the simulation result well.
-locators: Simulation versus Theoretical.
-locators. We also present the simulation results to demonstrate the out-performance of our schemes and the validity of the proposed theoretical analysis. Although the proposed approach is described based on the RSSI method, it can be easily applied to the localization approaches based on the time-of-arrival (ToA) or time-difference-of-arrival (TDoA) methods.