Detecting and Defending against Replication Attacks in Wireless Sensor Networks

Abstract

Wireless sensor networks are susceptible to node replication attacks due to their unattended nature. Existing replicas detection schemes can be further improved in regard of detection probabilities, detection overheads, and the balance of detection overheads among sensor nodes. In this paper, we make the following contributions: first, we point out the unrealistic assumption that the replica node would behave honestly as the benign sensor nodes; thus the existing detection schemes would fail if the replica nodes cheat or collude with the compromised node. Then, we propose a location-binding symmetric key scheme forcing the replica nodes to be inserted only in the vicinity of the compromised node. Later, a detecting scheme is presented to inspect the location claims within the neighborhood. Finally, analysis shows that our scheme helps to detect and defend against replication attacks effectively and efficiently. Extensive simulations are conducted and the results show that the detection overheads are low and evenly distributed among all the sensor nodes.

1. Introduction

Wireless sensor networks (WSNs) are generally deployed in the unattended environments for some missions, such as environment monitoring and enemy surveillance. The unattended nature and the lack of tamper-resistant hardware cause wireless sensor networks to be vulnerable to various insider attacks, threatening the operation of WSNs.

Replication attack is one of the insider threats. The attacker captures one or more sensor nodes, tampers with them and obtains the credential materials, such as the identity and keys, then clones some nodes as replica nodes, and surreptitiously inserts these replicas in the network. Subsequently, the attacker may launch a variety of insidious attacks, such as data injection, selecting forwarding, routing loop, or even topology partition. Just as shown in Figure 1, a network was formed by the normal nodes (without frame). The captured and compromised nodes are represented in the solid frame, and replica nodes are represented in the dashed frame.

Figure 1

Replication attacks in wireless sensor network.

Thus, detection of replica nodes becomes one research hotspot in WSN [1]. The first distributed replication detection schemes RM and LSM were proposed by Parno et al. [2]. In RM scheme, nodes broadcast to neighboring nodes the location claim message signed by ID-based public key scheme. Then the neighbors forward such received claim message with a specified probability to randomly selected network nodes, which act as witness. According to the birthday paradox [1], the nodes owning the same ID would select same witness nodes with a big probability. These witness nodes eventually detect replicas successfully. To further increase the detection probability, LSM scheme is also proposed. In this scheme, the nodes in the forwarding path of the claim messages also store and compare the messages. Thus witness line segment is formed from the source to the destination; then the witness line of the same ID will cross at some node with a large probability and the node at the cross point acts as the witness node. Compared with RM scheme, the detection probability is increased at the cost of memory storage. However, LSM scheme has the crowded-center problem because the witness line is prone to cross at the center of network with a big probability.

2. Related Work

The existing detection schemes can be classified as centralized approaches and distributed approaches.

2.1. Centralized Detection Approaches

The schemes in [3–6] assume a central base station to conduct the detection. Choi et al. [3] proposed to detect the replica nodes by set. The network is divided into disjoint subregions. A header node is enumerated to report the member list to the base station in each subregion. The reports from all of the header nodes are computed by set. The intersection of two sets is checked; any nonempty intersection implies the existence of the replica sensor node. Brooks et al. [4] proposed a centralized scheme to detect replication attacks by using random key predistribution. Every sensor node should report the usage of its keys. If the usage of some key exceeded the threshold, then the sensor node was identified to be suspicious. Ho et al. [5] presented a SPRT method for replica detection in mobile sensor networks, in which the base station checks whether the speeds of the mobile sensor nodes exceed the threshold. Based on a state-of-the-art signal processing technique, compressed sensing, Yu et al. [6] proposed CSI to detect replication attacks.

2.2. Distributed Detection Approaches

In distributed approaches [2, 7–14], the replication attacks detection is conducted by reporting the location claim messages to randomly chosen witness nodes in the network. Paradoxes of the location claims indicate the detection of replication attacks. To further improve the detection probability, Conti et al. [7] proposed RED scheme, in which a random seed was shared and upgraded in the network. The same random seed and the same pseudorandom function result in the same witness node chosen by replica nodes and the compromised node. But it is difficult to share and upgrade such random seed across the whole network. Zhu et al. [8] proposed another detection scheme by using localized multicast. Ho et al. [9] proposed to take advantage of the group deployment knowledge to further raise detection probability and lower detection overheads. Zhang et al. [10] proposed four detection schemes, B-MEM, BC-MEM, C-MEM, and CC-MEM, to address the cross-over problem and the crowded-center problem in the detection. Li and Gong [11] proposed RDE scheme to utilize the local neighborhood geographic information for replication attacks detection. Zeng et al. [12] proposed two detection schemes, RAWL and TRAWL, to distribute the witness sensor node to the network. Wang and Shi [13] introduced mobile patrollers to detect replica nodes; the result shows this solution is effective and also energy efficient to prolong the lifetime of network. Xing and Cheng [14] proposed two replication detection schemes from both the time domain and the space domain in MANETs (mobile ad hoc networks). The basic idea is to utilize a cryptographic one-way hash function to force the replica sensor nodes to keep on generating paradoxes.

It is assumed by existing schemes that compromised sensor node and the replica node carry out the detection procedures honestly. However, it is not always true; it is more likely that the program code in the compromised sensor node and the replica sensor node has been modified by the attacker for the purpose of escaping from being detected. To make things worse, the replica node may collude with the compromised node, which will lead to the failure of existing detection schemes.

In this work, we seek to detect and defend against the replication attacks with fewer communication, computation, and memory overheads than previous works. We propose a location-binding pairwise key scheme, forcing the attacker to insert the replica nodes to the vicinity of the compromised node. Then, the neighbor sensor nodes around the replica sensor nodes are the first possible witnesses to detect the replication attacks.

The remainder of this paper is organized as follows: the next section illustrates the network model and assumptions; Section 4 proposes our location-binding pairwise key management scheme which is used in our scheme to defend against the replication attacks; Section 5 presents our replicas detection scheme; Section 6 analyzes the security and efficiency of our scheme, and extensive simulations supporting the analytical findings are also shown. Discussion follows in Section 7. Section 8 concludes the proposed scheme.

3. Network Model and Assumptions

In this paper, we assume that there are only stationary sensor nodes in the wireless sensor network. We also assume that the communications between the stationary sensor nodes are bi-directional, which is also an assumption of most of previous detection schemes.

Stationary nodes can get their geographic location by using positioning device (e.g., GPS device) or positioning algorithms [15–18]. Also, we assume that all the sensor nodes are loosely time synchronized using time synchronization techniques, such as [19, 20]. Consider

$$\begin{array}{cc}& f\left(\alpha ,\beta \right)={\sum }_{i,j=\mathrm{0}}^{t-\mathrm{1}}{a}_{ij}{\alpha }^i{\beta }^j.\end{array}$$

(1)

Prior to network deployment, we assume that a trusted authority (TA) chooses one t-degree bivariate symmetric polynomial in (1) with the coefficients $a_{ij}\hspace{0.17em}\hspace{0.17em}(0\le i,j\le t-1)$ over the finite field $\text{GF}(q)$ , where q is a prime large enough to accommodate the keys. The symmetry of the polynomial assures the equation $f(\alpha ,\beta )=f(\beta ,\alpha )$ , which also implies the equation of the coefficients $a_{ij}=a_{ji}$ . Also, TA select a cryptographic one-way hash function $h(·)$ , which maps arbitrary-length input into fixed-length output. TA preloads every sensor node with the symmetric polynomial $f(\alpha ,\beta )$ and the hash function $h(·)$ . Table 1 lists all the relevant symbols and the corresponding meaning.

Table 1

Notation summary.

Notation	Meaning
n	Total number of sensor nodes
$u,v,w$	Sensor nodes $u,v,\text{and}\hspace{0.17em}\hspace{0.17em}w$
$u_r$	Replica sensor node of u
$u_w$	Witness sensor node of u and $u_r$
$f(\alpha ,\beta )$	Bi-variate symmetric polynomial
$h(x)$	One-way hash function
$K_u(\beta )$	Key ring polynomial of sensor node u
${\text{ID}}_u$ , ${\text{ID}}_v$ , ${\text{ID}}_w$	Respective identity of sensor nodes $u,v,\text{and}\hspace{0.17em}\hspace{0.17em}w$
$K_{uv}$ , $K_{uw}$ , $K_{vw}$	Pairwise key between sensor nodes $u,v,\text{and}\hspace{0.17em}\hspace{0.17em}w$
Δ	Tolerance of time synchronization
R	Sensor communication range
B	Average number of sensor nodes in the communication range
N	Number of witness sensor nodes
d	Distance between u and $u_r$
γ	The ratio of d to R
S	Area of the deployment region of the network
$S_s$ , $S_c$ , $S_w$	Area of sensor communication, blind zone, and witness zone

4. Location-Binding Pair-Wise Key Scheme

Most of the existing detection schemes explore the public key algorithms for encryption and digital signature. Even if public key algorithms are feasible and available in wireless sensor networks, the large computation overheads will exhaust the limited battery power and pose great challenges to the resource-limited sensor nodes.

Due to the low cost, small factor, and limited resources in the sensor nodes, symmetric encryption algorithms are more suitable for wireless sensor networks. In [21], the key management in distributed sensor networks is studied. Fei et al. [22] proposed a time-space related symmetric key predistribution scheme. Wang et al. [23] proposed an updateable key management scheme with intrusion tolerance through symmetric polynomial and one-way hash chain.

We assume the sensor nodes adopt a location-binding pair-wise key scheme (LBK), which tightly binds the sensor node's identity with its geographical location to resist against node capture and replica nodes. In the following, we first propose our location-binding pair-wise key management scheme.

4.1. Sensor Deployment and Localization

After sensor nodes are deployed into the targeted region, each sensor node carries out the bootstrap procedure as described by Algorithm 1. The sensor node obtains its geographical location $(x,y)$ . Then, the sensor nodes use their location $(x,y)$ and the collision-resistant one-way hash function $h(·)$ to compute its identity as $\text{ID}=h(x||y)$ , where $||$ denotes message concatenation. In this way, we bind each sensor node's identity tightly with its geographic location to resist against replication attack.

Algorithm 1: Sensor node bootstrap procedure.

(1)  Start timeout timer   $T\mathit{1}$

(2)  Get the location $l_u=$    $(x,y)$

(3)  Compute sensor identity ${\text{ID}}_u=h$ (x $\parallel y)$

(4)  if   $(T\mathit{1})$   then

(5)   Compute key ring polynomial $K_u(\beta )=f({\text{ID}}_u,\beta )$

(6)   Erase the symmetric polynomial $f(\alpha ,\beta )$

(7)  else

(8)   Erase the symmetric polynomial $f(\alpha ,\beta )$

(9)   Halt

(10)  end if

Once the identity is generated, a sensor node, for example, sensor node u, generates its key ring polynomial $K_u(\beta )=f({\text{ID}}_u,\beta )$ , then erases the symmetric polynomial $f(\alpha ,\beta )$ permanently.

All the sensor nodes are required to conduct the previous process within short time duration $T1$ lest the attacker captures the symmetric polynomial.

4.2. Neighborhood Pairwise Key Establishment

Every sensor node broadcasts its identity within its radio range to establish its neighborhood. Then each sensor node uses its neighbor lists to calculate the relevant pair-wise key for encryption and decryption. For example, every sensor node establishes pair-wise keys with its neighboring sensor node according to Algorithm 2.

Algorithm 2: Direct neighborhood pair-wise key establishment.

(1)  Broadcast $({\text{ID}}_u,l_u)$

(2)  Initialize and start timeout timer $T\mathit{2}$

(3)   $c=\mathit{0}$

(4)  while   $(T\mathit{2}\hspace{0.17em}\hspace{0.17em}\&\&\hspace{0.17em}\hspace{0.17em}c<t-\mathit{1})$   do

(5)    Receive   $({\text{ID}}_v,l_v)$ from a neighbor node

(6)    If   $\left|l_u-l_v\right|\le R$ and ${\text{ID}}_v$ not in the neighbor list

(7)      Compute pair-wise key $K_{uv}=K_u({\text{ID}}_v)$

(8)      Store ${\text{ID}}_v$ and $K_{uv}$

(9)       $c=c+\mathit{1}$

(10)    end if

(11)  end while

(12)  Erase the key ring polynomial $K_u$ (β)

To defend against node attacks from compromising t sensor nodes and deriving the symmetric polynomial $f(\alpha ,\beta )$ , every sensor node, for example, sensor node u, is required to get its geographic location and computes its key ring polynomial $K_u(\beta )$ within a time limit $T1$ after bootstrap. Once $K_u(\beta )$ is generated or $T1$ expires every sensor node erases the relevant polynomial $f(\alpha ,\beta )$ permanently. Algorithm 1 describes such a bootstrap procedure.

Also, every sensor node, for example, sensor node u, should establish neighborhood and compute the pair-wise keys with at most $t-1$ neighbor nodes within a time limit $T2$ after key ring polynomial $K_u(\beta )$ is generated. Once keys are computed or $T2$ expires every sensor node erases its key ring polynomial $K_u(\beta )$ permanently. In this way, even if the attacker compromises a sensor node, $t-1$ keys are not enough to deduce the key ring polynomial $K_u(\beta )$ . Algorithm 2 details the whole process.

For those sensor nodes that have more than $t-1$ neighbor nodes, the pair-wise keys can be negotiated through the common neighbor nodes in their neighborhood. For example, in Figure 2, sensor node u has more than $t-1$ neighbor nodes, in which sensor node v has already established the pair key $K_{uv}$ with node u according to Algorithm 1; also node v has established pair-wise key $K_{vw}$ with node w, while sensor node u has to negotiate with node w to share a pair-wise key. The negotiation needs 4 steps as shown in Figure 2:

• (1)

node u sends a negotiation request message to node w, including the identity of u and w, the message type (Nego_Req), the neighbor list of node u, and a nonce. The nonce is used to defend against replay attack;

(2)

node w receives node u's neighbor list, chooses one common node, for example, node v, generates the shared key $K_{uw}$ randomly, and answers node u with the answer message, including the identity of u and w, the message type (Nego_Anw), and the secret part, which contains node v's identity, the nonces of nodes u and w, encrypted with the shared key $K_{uw}$ ;

(3)

node w sends a message to node v, which includes the identities of nodes w and v, the message type (Nego_Ask), and the secret part, containing the identity of nodes u and v, the nonce of w, and the shared key $K_{uw}$ , encrypted with the shared key $K_{vw}$ ;

(4)

node v replies to node u with a message, including the identities of v and w, the message type (Nego_Rly), and the secret part, which contains the identities of w and u, the shared key $K_{uw}$ , and the nonce of node w, encrypted with the shared key $K_{uv}$ .

Figure 2

Pair-wise key negotiation.

Node u decrypts to get $K_{uw}$ and then decrypts the secret part of message from node w to verify the identity of node v and the nonce of node w. If the verifications pass, then node u stores ${\text{ID}}_w$ and $K_{uw}$ ; otherwise node w is removed from the neighbor list of node u.

5. Replicas Detection

Replica nodes detection can be conducted right after the sensor nodes are initialized and location-based pair-wise keys are generated. Node location inspection is carried out to detect the forged nodes who claim to have the benign nodes' location. If the node passes location inspection, then the encrypted messages are deciphered using the pair-wise key according to the node's identity. If this decryption fails, then the node is identified as a replica node.

Because of the above pair-wise key scheme and the location-binding sensor nodes' identity, the attacker is restricted in placing the replica nodes after compromising benign nodes and making replicas. The best strategy for the attacker is to put the replica nodes in the vicinity of the compromised node. This way, the replica nodes can utilize the stolen credentials to communicate with the neighbor sensor nodes of the compromised node and hide in the network without being detected.

Thus, the replica nodes are restricted to a region around the sensor node. Based on this idea, we propose a replication detection scheme within neighborhood.

Every sensor node broadcasts location claim message to its neighborhood periodically:

$$\begin{array}{cc}& {\text{Message}}_u:\left({\text{ID}}_u,l_u,t_u,\text{MAC}\right).\end{array}$$

(2)

${\text{ID}}_u$ , $l_u$ , $t_u$ , and MAC denote the identity, location, time, and message authentication code, respectively. The sensor nodes in the neighborhood carry out Algorithm 3 to conduct replication attack detection.

Algorithm 3: Neighborhood detection of replication attack.

Input:   ${\text{ID}}_u,l_u,t_u,\text{MAC}$

Output:  detection result: 0 = not a replica node, 1 = replica, 2 = N/A (not available)

 (1)    function   $\text{NDRA}({\text{ID}}_u,l_u,t_u,\text{MAC})$

 (2)     if   $h({\text{ID}}_u\parallel l_u\parallel t_u)\ne \text{MAC}$    and   $\left|t_u-t_v\right|>\mathrm{\Delta }$   then

 (3)      return 2

 (4)     end if

 (5)     if   $|l_u-l_v|>R$   and  h(x∥y) $\ne {\text{ID}}_u$   then

 (6)      return 1

 (7)     end if

 (8)      return 0

 (9)    end function

When the sensor node v receives a message from its neighbor node u, it computes the distance to check whether or not the claim is issued from its neighbor sensor nodes. If this check fails, the sensor node who issued this location claim is identified as a replica node.

6. Analysis and Simulations

To inspect our defending and detection scheme, both numerical and simulations results are shown in this section. First, we give the security analysis in Section 6.1, then the numerical results follow in Section 6.2, and simulation results are shown in Section 6.3.

6.1. Security Analysis

Definition 1.

The communication coverage of a sensor node is a circle with center at the sensor node and radius equal to the communication range R. The area is written as $S_s$ .

The sensor nodes in the communication coverage of sensor node u are neighbor sensor nodes of u.

Definition 2.

Blind zone is defined as the common communication coverage of sensor node u and its replica sensor node $u_r$ . Sensor nodes in the blind area cannot distinguish sensor nodes u and $u_r$ . This zone and its area are written as $S_c$ .

Definition 3.

Witness zone is defined as the region in the communication coverage of sensor node $u_r$ but not in the communication coverage of sensor node u. Sensor nodes in the witness zone, written as witness sensor nodes, can detect the replica sensor node $u_r$ . This zone and its area are written as $S_w$ .

We also have the following facts.

•  

Fact 1. Replica node $u_r$ can be detected if and only if at least one witness sensor node exists in witness zone.

 

Fact 2. Sensor node u and its replica node $u_r$ can collude if and only if there are only two sensor nodes in the blind zone: u and $u_r$ .

Scenario 1: The Distance between u and $u_r$ : $d\le R$ . If the attacker compromises sensor node u, then it makes one replica node $u_r$ , deploys $u_r$ in a distance $d\le R$ , just as shown in Figure 3(a). Then node $u_r$ shares the same credentials as u. The common neighbor nodes in the blind zone cannot distinguish u from $u_r$ . While sensor node in the witness zone of node $u_r$ can detect the forged geographic location of node $u_r$ . So, if the attacker wants to make $u_r$ undetected, he must make sure that there are no sensor nodes in the witness zone $S_w$ . Thus, replica node $u_r$ can cheat the sensor nodes in the blind zone $S_c$ using the legitimate security credentials.

Figure 3

Replication node $u_r$ in three scenarios.

In scenario 1, u and $u_r$ cannot collude, because sensor nodes in the blind zone can detect the colluding message in which the identities are the same. So, if u wants to collude with $u_r$ , there should be no sensor nodes other than u and $u_r$ in the blind zone $S_c$ .

Lemma 4.

Replica sensor node $u_r$ stays undetected and colludes with sensor node u, if and only if $N=1$ ; that is, replica sensor node $u_r$ has only one neighbor sensor node u.

Proof.

This lemma holds according to Fact 1 and Fact 2.

This lemma indicates that it's difficult for the attacker to insert replica sensor node $u_r$ in the sensor network ensuring that $u_r$ stays undetected and colludes with u.

Lemma 5.

If replica sensor node $u_r$ stays undetected and does not collude with sensor node u, then replica sensor node $u_r$ can cheat all the sensor nodes in the blind zone of sensor node u and replica sensor node $u_r$ .

Proof.

This lemma holds trivially.

This lemma means that we need some new schemes to detect the replica sensor node $u_r$ .

Scenario 2: The Distance between u and $u_r\text{:}\hspace{0.17em}R<d\le 2R$ . In Figure 3(b), if replica node $u_r$ is placed at a distance $d\in (R,2R]$ away from sensor node u, then node u and node $u_r$ cannot communicate directly, but there are still possibilities that u and $u_r$ share common neighbor nodes. Even though compared with scenario 1, the common area between node u and node $u_r$ is smaller, the threats of replication attacks still exist.

Lemma 6.

If replica sensor node $u_r$ is inserted at a distance $R<d\le 2R$ away from u, then u and $u_r$ cannot collude.

Proof.

This lemma holds trivially.

Scenario 3: The Distance between u and $u_r\text{:}\hspace{0.17em}d>2R$ . In Figure 3(c), if the replica node $u_r$ is deployed away from node u at a distance larger than $2R$ , then node $u_r$ not only cannot communicate with node u directly, but also shares no common neighbor node with node u. So, node $u_r$ will have to establish pair-wise keys with neighbor nodes around, the identity of $u_r$ is the same with u; and it is easy to be detected. But if the attacker changes node $u_r$ 's identity, it is impossible to deduce the key ring polynomial without the symmetric polynomial. So, node $u_r$ can only eavesdrop on the communications around itself, whereas it cannot decrypt any of the messages without relevant pair-wise key. Actually, node $u_r$ is isolated to die. The attacker would not benefit too much from scenario 3.

Lemma 7.

In scenario 3 with $u-u_r$ distance $d>2R$ , $u_r$ can stay undetected if and only if $u_r$ is isolated without any neighbor sensor nodes.

Proof.

This lemma holds according to Fact 1.

6.2. Numerical Discussion

In this section, we execute the mathematical analysis to get the numerical results of our proposed defending and detection scheme.

Given that there are n sensor nodes evenly distributed in the network, the area of network deployment region is S, the communication radius of the radio is R, and the detection probability in three scenarios is calculated as follows.

The blind zone in scenario 1 and scenario 2 is the common communication area between the benign node u and the replication node $u_r$ , which can be computed as in (3). Then the area of the witness zone of $u_r$ can be computed by (4). In Figure 4, the common area $S_c$ can be computed as

$$\begin{array}{l}{S}_c=\mathrm{2}\left(\text{area}\hspace{0.17em}\hspace{0.17em}\text{of}\hspace{0.17em}\hspace{0.17em}\text{sector}\hspace{0.17em}\hspace{0.17em}\text{AuB}-\text{area}\hspace{0.17em}\hspace{0.17em}\text{of}\hspace{0.17em}\hspace{0.17em}\text{triangle}\hspace{0.17em}\hspace{0.17em}\text{AuB}\right)\hfill \\ =\mathrm{2}\left(\left(\frac{\mathrm{2}\beta }{\mathrm{2}\pi }\right)\times \pi R^{\mathrm{2}}-\left(\frac{1}{2}\right)\times \left(\frac{d}{2}\right)\times \mathrm{2}\left(\sqrt{R^{\mathrm{2}}-{\left(\frac{d}{\mathrm{2}}\right)}^{\mathrm{2}}}\right)\right)\hfill \\ =\mathrm{2}\left(\left(\text{arccos}\left(\frac{d}{2R}\right)÷\pi \right)\times \pi R^{\mathrm{2}}-\mathrm{0.25}d\times \left(\sqrt{\mathrm{4}{R}^{\mathrm{2}}-d^{\mathrm{2}}}\right)\right),\hfill \\ S_c=\mathrm{2}{R}^{\mathrm{2}}\text{arccos}\left(\frac{d}{2R}\right)-\mathrm{0.5}d\sqrt{\mathrm{4}{R}^{\mathrm{2}}-d^{\mathrm{2}}}.\hfill \end{array}$$

(3)

Figure 4

Blind zone $S_c$ and witness zone $S_w$ .

Sensor nodes in the blind zone cannot distinguish sensor node u from replica node $u_r$ ; however, the sensor nodes in the witness zone can detect the replica node $u_r$ by checking the distance between the claimed location of $u_r$ . So, to detect $u_r$ , the more nodes in the witness zone, the better. Once the sensor nodes are deployed in the region, the detection relies more on the area of the witness zone. The area of the witness zone can be calculated as

$$\begin{array}{l}{S}_w=S_s-S_c\hfill \\ =\pi R^{\mathrm{2}}-\mathrm{2}{R}^{\mathrm{2}}\text{arccos}\left(\frac{d}{\mathrm{2}R}\right)+\mathrm{0.5}d\sqrt{\mathrm{4}{R}^{\mathrm{2}}-d^{\mathrm{2}}}.\hfill \end{array}$$

(4)

The number of sensor nodes depends on the distribution of the sensor nodes in the deployment area. Suppose that the sensor nodes are evenly distributed in the area. Then the density of sensor nodes is $n/S$ and the sensor nodes in the witness zone can be computed as

$$\begin{array}{cc}& N=\left(\pi R^{\mathrm{2}}-\mathrm{2}{R}^{\mathrm{2}}\text{arccos}\left(\frac{d}{\mathrm{2}R}\right)+\mathrm{0.5}d\sqrt{\mathrm{4}{R}^{\mathrm{2}}-d^{\mathrm{2}}}\right)\times \left(\frac{n}{S}\right).\end{array}$$

(5)

To detect the replica node $u_r$ , the number of sensor nodes in the witness zone must be greater than or equal to 1 as in the inequality

$$\begin{array}{cc}& N\ge \mathrm{1}.\end{array}$$

(6)

To facilitate our analysis, we let γ denote the ratio between the distance of $u-u_r$ and the communication radius R as in (7). In scenario 1 and scenario 2, γ is in the range of 0 to $2\hspace{0.17em}\hspace{0.17em}(0\le \gamma \le 2)$ , while in scenario 3, γ is greater than 2. Consider

$$\begin{array}{cc}& \gamma =\frac{d}{R}.\end{array}$$

(7)

Also, we let B denote the average number of sensor nodes in the communication range. B can be derived as in (8). The greater B is, the more neighbor sensor nodes exist:

$$\begin{array}{cc}& B=\frac{\pi R^{\mathrm{2}}}{S}\times n.\end{array}$$

(8)

Then (5) can be rewritten as function of γ and B, yielding

$$\begin{array}{cc}& N=\left(\frac{\mathrm{1}}{\pi }\right)\times B\times \left(\pi -\mathrm{2}\hspace{0.17em}\text{arccos}\left(\mathrm{0.5}\gamma \right)+\mathrm{0.5}\gamma \sqrt{\mathrm{4}-{\gamma }^{\mathrm{2}}}\right).\end{array}$$

(9)

We can see from (9) that the number of witness sensor nodes on the replica node $u_r$ is only related with B and γ. Figure 5 shows that the number of witness sensor nodes changes with γ and B, where B is assumed to be in the range of 0 to 10. Figure 6 shows that the number of the witness nodes changes with the ratio γ when fixing B to 1, 5, and 10, respectively.

Figure 5

The number of witness nodes.

Figure 6

Number of witness nodes.

If N is greater than or equal to 1, it means that the replica node $u_r$ would be detected definitely. Otherwise, there would be some false positives in the detection scheme. To ensure a 100% detection probability without false positives, B and γ should satisfy the inequality

$$\begin{array}{cc}& N\ge \mathrm{1},\\ \left(\frac{\mathrm{1}}{\pi }\right)\times B\times \left(\pi -\mathrm{2}\hspace{0.17em}\text{arccos}\left(\mathrm{0.5}\gamma \right)+\mathrm{0.5}\gamma \sqrt{\mathrm{4}-{\gamma }^{\mathrm{2}}}\right)\ge \mathrm{1},\\ B\ge \frac{\pi }{\left(\pi -\mathrm{2}\hspace{0.17em}\text{arccos}\left(\mathrm{0.5}\gamma \right)+\mathrm{0.5}\gamma \sqrt{\mathrm{4}-{\gamma }^{\mathrm{2}}}\right)}.\end{array}$$

(10)

This means that we can get higher detection probability by increasing the density of sensor nodes. Meanwhile, it also means that the attacker has to insert the replica node close to the compromised sensor node u to stay undetected. The closer the replica node is to the compromised node, the less the potential threat of the replication attacks is

At last, we let P denote the detection probability as in (11). Figure 7 shows that the detection probability changes with the ratio γ when B is fixed to be 1, 5, and 10, respectively. Consider

$$\begin{array}{cc}& P=\{\begin{array}{cc}N,\hfill & B<\frac{\pi }{\left(\pi -\mathrm{2}\hspace{0.17em}\text{arccos}\left(\mathrm{0.5}\gamma \right)+\mathrm{0.5}\gamma \sqrt{\mathrm{4}-{\gamma }^{\mathrm{2}}}\right)},\hfill \\ 1,\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(11)

Figure 7

Detection probability.

6.3. Detection Performance

To inspect the detection scheme, simulations in different scenarios are carried out in the NS2 network simulator [24].

6.3.1. Replication Detection

In the simulations, the WSN deployment area is 5000 meters both in the width and in the length. The wireless nodes' physical radio model is TwoWayGround and the MAC layer protocol is IEEE 802.11. In NS2, the default communication radius of the wireless node is 250 meters.

Simulations are conducted in two network deployments; there are 100 sensor nodes in one deployment, while there are 1000 sensor nodes in the other deployment. In both deployments, the sensor nodes are distributed randomly with a uniform distribution. There is only one replica sensor node in every round of the simulations; the replica sensor node claims to own a location-binding identity, but the identity is forged. The average count of neighbor nodes can be computed with (7), yielding the average sensor nodes count; $B=0.7854$ and $B=7.854$ , respectively.

We carried out 100 rounds simulations in both deployments. The detection probability was computed as the ratio of the successful detection rounds to the total 100 rounds. We change the distance ratio γ defined in (6) from 0.0125, 0.025, 0.05, 0.1, 0.2, 0.5, 1.0, 1.5 to 2.0 in the simulations, in order to examine the detection probability in 3 scenarios.

The results are shown in Figure 8, in which the analytical results are also shown for comparison. It can be seen that the larger the ratio γ is, the larger the detection probability is, which fits the analytical results.

Figure 8

Simulation results and analytical results.

6.3.2. Detection Overhead

At last, simulations are carried out to analyze the detection costs of our scheme. In the simulations, the total number of sensor nodes is fixed to $n=1000$ ; only one replica node is randomly selected from all the sensor nodes.

Figure 9 shows the results. Every stationary sensor node has to send about 1 data packet to its neighbor sensor nodes, while it has to receive about at most 7 data packets from its neighbor nodes on average. That is, in total, at most 8 data packets have to be transmitted on average.

Figure 9

Detection overheads.

7. Comparison with Related Work

In our scheme, every sensor node asynchronously reports its location-based identity to its neighbor nodes and also has to receive claim messages from all its neighbor nodes. The total communication and computation overheads incurred by the detection are $O(B)$ . Memory requirement to store the pair-wise keys with neighbor nodes in every sensor node is $O(B)$ .

The detection algorithm is executed by every node in the network in a distributed manner, eliminating the packets forwarding in the network. Thus, the detection overheads are well balanced over the network.

Table 2 compares the detection overheads with RM [2], LSM [2], RED [7], and CSI [6] schemes, in which B represents the average number of sensor nodes in the communication range.

Table 2

Comparison with other schemes.

	Communications	Memory
RM [2]	$O(n)$	$O(\sqrt{n}$ )
LSM [2]	$O(\sqrt{n})$	$O(\sqrt{n})$
RED [7]	$O(\sqrt{n})$	$O(1)$
CSI [6]	$O(logn)$	—
Our scheme	$O(B)$	$O(B)$

As distributed approaches, RM [2], LSM [2], and RED [7] all assume public key schemes, which poses great challenges to the resource-limited sensor nodes. Yet, as a centralized scheme, CSI assumes the base station to conduct detection, which has the common problems of centralized approaches, such as single-point failure and unbalanced overheads among the sensor networks [1].

8. Conclusions

We present a detecting and defending scheme against replication attacks within neighborhood by using location-binding symmetric key scheme. The replica nodes are restricted to the vicinity of the compromised node. The location claim messages would not be forwarded, eliminating the overheads of other sensor nodes out of the neighborhood.

The analysis results show that the average number of sensor nodes and the distance between the compromised sensor node and the replica node determine the detection probability. The greater sensor nodes is, the higher the number of the detection probability; the farther apart the compromised node is from the replica node, the higher the detection probability is. Simulation results confirm the analytical findings. Compared with previous replica detection schemes, our scheme greatly lowers relevant detection overheads.