# Detecting and Preventing Sybil Attacks in Wireless Sensor Networks Using Message Authentication and Passing Method

Authors: Udaya Suriya Raj Kumar Dhamodharan; Rajamani Vayanaperumal
Journal: The Scientific World Journal
 (2015)

---

## Abstract

Wireless sensor networks are highly indispensable for securing network protection. Highly critical attacks of various kinds have been documented in wireless sensor network till now by many researchers. The Sybil attack is a massive destructive attack against the sensor network where numerous genuine identities with forged identities are used for getting an illegal entry into a network. Discerning the Sybil attack, sinkhole, and wormhole attack while multicasting is a tremendous job in wireless sensor network.  Basically a Sybil attack means a node which pretends its identity to other nodes.  Communication to an illegal node results in data loss and becomes dangerous in the network. The existing method Random Password Comparison has only a scheme which just verifies the node identities by analyzing the neighbors. A survey was done on a Sybil attack with the objective of resolving this problem. The survey has proposed a combined CAM-PVM (compare and match-position verification method) with MAP (message authentication and passing) for detecting, eliminating, and eventually preventing the entry of Sybil nodes in the network.  We propose a scheme of assuring security for wireless sensor network, to deal with attacks of these kinds in unicasting and multicasting.


---

## Body

## 1. Introduction

A wireless sensor network consists of applications such as environmental monitoring, target tracking, health monitoring, and other various maintenance options. Implementation and topology creation have become significant activities in modern research work [1]. The usage of wireless sensor network in a variety of applications is highly important with the emphasis on ensuring security. Still, Prevention and detection of malicious attacks of all levels may be high or low in wireless sensor network [2]. A variety of attacks on the network like wormholes, sinkhole, Sybil, sleep, and selective forward attacks in the network are being observed. Many researchers have identified their own infrastructures which have portable devices, used in various trade services in decentralized and scalable methods. Some of the devices are capable of synchronization without the use of the internet for multiuser applications. They are used for finding the exact location in the algorithms that enhance the accuracy. The Sybil attacker misleads other nodes by showing wrong ID or duplicate ID of the users who are aware of the nodes in the wireless sensor network.In the latest network environment, alien nodes can appear in disguise in various identities and act as original nodes. Basically, there is no common master node in social and defense network for monitoring communication between network nodes intense [3]. The analysis of peer-to-peer network shows that these networks show the existence of these network logical functionalities or the virtual networks coventry exist, that is, the networks built on the top of other networks as in the internet. The network node addresses are based on the logical ID for structuring and forming networks [4].The nodes in wireless sensor network are not in a fixed infrastructure, whether single-hop, multihop communication, base station, gateways, and access points [5]. Basically, wireless sensor networks have a smaller infrastructure which could be noninfrastructure networks. The term ad hoc implies the establishment for a special purpose and for applications such as tracking, function approximation and edge detection, monitoring environment, and security domain in the homeland. The application of wireless sensor network, resembling a military force, monitors absence of restriction on the infrastructure as well as in the intermediate hop nodes [6].This paper deals with one of the hazardous security threats known as Sybil attack and proposes an algorithm known as message authentication and passing method to hinder a Sybil attack in a wireless sensor network. The rest of the paper is presented as follows: Section2 defines the materials and methods of the Sybil attack; Section 3 defines the results and discussions. Section 4 provides conclusions and indications of future work.


## 2. Materials and Methods

Sybil attack is a matter of critical importance and consternation in network security leading to many fake identities that can cause disruption in the network [7]. Sybil attack occurs mostly during broadcasting and it functions without individual verification and identity comparison of communication entities [8]. The attacker node can acquire many identities. That entity in the system can endeavor to influence the Sybil attacker due to the awareness of only others in each entity via messages in the communication channel [9]. The attacker nodes are launched inside and outside the route as well as wireless sensor networks. The monitoring node specially identifies the attacker node on a unicast as well as in a multicast scenario. Here, [10] author proposes an authentication framework which can ensure hindrance to or mitigation of security attacks on wireless sensor network.


### 2.1. Security Attacks on WSN

Various types of malicious activities are patent in wireless sensor network. Some of these are created in terms of nodes while others are created in a network, data link, and application layers. Some are created in the physical state [11].The attacks are currently classified as active and passive. The former is created by deployment of illegal information in the network that can affect it. Sybil, sinkhole, and eavesdropper are some of the active attacks. Passive attacks are those which are meant to affect the network resources such as lifetime and network size.


### 2.2. Sybil Attack

A node or a device takes many identities that may not necessarily be lawful. It does not impersonate any node, but fast it only assumes the identity of another among several nodes, causing redundancies in the routing protocol. Sybil attacks degrade data integrity, security, and resource utilization. It can also perform storage, routing mechanisms, air resource allocation, and misbehavior detection. In a sensor network hundreds of sensor nodes form the communication network. The wireless communication between these sensor nodes passes through a central station. These nodes communicate with a specified of nodes of a specified number [12]. There are many encryption techniques available to prevent external attack on the nodes, but nodes in the communication network can also mount an attack. One of these insider attacks is called a Sybil attack [13–15] in which the node that spoofs the other node is called Sybil node S and the other one is a normal node N. In a proper communication system only N nodes should communicate with one another. But here, S node comes in another form of its own as an internal known node and launches an attack on the network. The Sybil node tries to communicate with neighboring nodes by using the identity of the normal node and in the process a single node gives many identities in the area to other nodes in the network which is illegal. A Sybil node can be formed as a new identity or as a pilfering legal identity. It is, therefore, considered an additional entity of a misbehaving node. This causes confusion in the network and it gets collapsed. A faulty node which enters into the network with different IDs is shown in Figure 1.Figure 1
Sybil attacks with multiple ID.As a result Sybil attacks are classified into two forms on the basis of the manner of attack on the network. They are as follows.(i) Direct Attack and Indirect Attack. In a direct attack, the real nodes communicate directly with Sybil nodes, whereas, in an indirect attack, the communication is done through a malicious node.(ii) Fabricated Attack and Stolen Identity Attack. Legal identities of nodes are used to create new illegal nodes. That is to say, a sensor node which has an ID of 16-bit integers creates the same ID of 16 bits, which are fabricated nodes. The IDs stolen by the Sybil node are destroyed by checking the identity replication [16].


### 2.3. Existing Methodology

Random Password Generation (RPC) algorithm focuses on the various traffic levels and security during data transmission in WSN. RPC algorithm generates the routing table which holds information about deployed nodes. The intermediate nodes in the route are identified between source and destination. The intermediate node’s information is compares with RPC database during communication among nodes, based on the comparison results it decides whether Sybil or normal node. RPC also generates the route by adding the genuine node in its path from source to destination node using several subprocedures [17].


### 2.4. Proposed Approach

The main objective of this paper is to design and develop an algorithm for detecting and preventing Sybil attacks in wireless sensor network. It is referred to message authentication and passing algorithm. Creation of Sybil activity through use of the other personal identities is well known. Most of the existing research deals with the detection of the Sybil attack through verification of identities.


#### 2.4.1. Network Model

In this paper,N numbers of nodes are deployed in the network randomly under the control of and an administrator. These are well configured, energy efficient, and promising nodes in the network. During node creation, each node will receive a H
E
L
L
O message from the B
S with a timestamp message indicating the node creation time (birth time) in the network. The entire node responds to the BS with a RES message with ID, timestamp, and location. Then this information is stored in a i
N
O
D
E
I
N
F
O
_
t
a
b
l
e under the control of the administrator of the network. The entire network model is presented as G
=
{
N
1
,
N
2
,
…
,
N
i
,
…
,
N
m
,
B
S
,
A
d
m
i
n
} where m is the number of nodes in the network. Each node is deployed in the network as L
o
c
a
t
i
o
n
N
i
=
rand
⁡
(
x
)
,
rand
⁡
(
y
), where X
,
Y is any location within the network area. TheBS sends a HELLO packet to all the newly created nodes in the network which can be written as(1)
B
S
M
s
g
,
τ
∑
i
=
1
m
N
i
,
where
N
1
,
N
2
,
…
,
N
i
,
…
,
N
m
are  Nodes
.And, each node in the network is sending aRES packet to theBS which can be written as N
i
RES
B
S, where the HELLO andRES packet consist of node ID and the timestamp. H
E
L
L
O
=
τ
N
i and R
E
S
=
(
I
D
N
i
,
τ
N
i
), where N
i denotes the i
t
h node, τ
(
N
i
) denotes timestamp of the i
t
h node, and I
D
(
N
i
) denotes identity of the i
t
h node. The parameters such as ID and τ are used to verify that the node is a Sybil or not. CAM-PVM algorithm for Sybil detection.In networkG, a node S needs to transmit a data to a node D. So, it is necessary to discover a route from S to D through an N-hop intermediate node. The number of intermediate nodes depends on the network size. The routing mechanism used in this paper follows AODV protocol. During this process, current information about the intermediate nodes (ID, timestamp) is tentatively stored in a routing table named as i
R
O
U
T
I
N
G
_
t
a
b
l
e.The duration between the route discovery and data transmission in the discovered route is very small. While data transmission, thei
R
O
U
T
I
N
G
_
t
a
b
l
e data entries are compared with the entries available in the i
N
O
D
E
I
N
F
O
_
t
a
b
l
e shown in Table 1, where it helps to identify the duplicate nodes with id, timestamp, and the location. For example, G
=
{
N
1
,
N
2
,
…
,
N
i
,
…
,
N
m
}
N
3 is considered source node, N
9 the destination node, and the intermediate nodes are N
5, N
7, and N
8. The route discovered from N
3 to N
9 is N
3
→
N
5
→
N
7
→
N
8
→
N
9. The i
R
O
U
T
I
N
G
_
t
a
b
l
e of the discovered route is shown in Table 2, which comprises the original node ID, timestamp [
τ
], location, and the current timestamp during the time of route discovery.Table 1
iNODEINFO_table.
Node ID
N
1
N
2
N
3
N
4
N
5
N
6
N
7
N
8
N
9
N
10
τ
11:00
11:02
11:30
11:37
11:41
11:43
11:56
11:59
12:04
12:06
X
34
67
87
123
154
23
18
54
62
59
Y
11
33
54
67
89
123
131
145
165
154Table 2
i
R
O
U
T
I
N
G
_
t
a
b
l
e.
Node ID
N
3
N
5
N
7
N
8
N
9
τ
11:30
11:41
11:56
11:59
12:04
X
87
154
18
54
62
Y
54
89
131
145
165
τ
1:01
1:04
1:05
1:06
1:06Now during the data transmission, the discovered route is verified by comparing current intermediate node information with thei
R
O
U
T
I
N
G
_
t
a
b
l
e by updating the node entries. From Table 3, it is clear that the N
7 information is replicated; it is found that the information of the replica node does not match the original N
7 information in i
N
O
D
E
I
N
F
O
_
t
a
b
l
e.Table 3
NodeN
2 is the Sybil, acting as N
7.
Node ID
N
3
N
5
N
7
[
N
2
]
N
7
N
8
N
9
τ
11:30
11:41
11:02
11:56
11:59
12:04
X
87
154
67
18
54
62
Y
54
89
33
131
145
165
τ
1:01
1:04
1:05
1:05
1:06
1:06Sybil activity is identified with application of the CAM-PVM algorithm and is detected in the network. To provide prevention for Sybil activity, another MAP algorithm is applied along with CAM-PVM for prevention of Sybil activity. MAP comprises unicast as well as multicast based communication in the network. The algorithm for CAM-PVM and MAP is given below.Compare and Match-Position Verification Method (CAM-PVM)
(1)
L
e
t
G
=
N
1
,
N
2
,
N
3
,
…
,
N
m
(2)
L
e
t
B
S
,
A
d
m
i
n
b
e
t
h
e
w
e
l
l
c
o
n
f
i
g
u
r
e
d
n
o
d
e
s
(3)
f
o
r
i
=
1
t
o
m // Nodes are placed
randomly
(4)
N
i
←
L
o
c
a
t
i
o
n
(
rand
⁡
X
,
rand
⁡
Y
)
(5)
I
D
(
N
i
←
i
);
(6)
E
n
d
L
o
o
p
(7)
Let Li be the set of link between pair of nodes in the network
(8)
N
i
→
B
S
(
M
s
g
,
τ
)// For every nodes N
i
(9)
U
∗
→
m
i
n
i
m
u
mdistance(N
i, N
i
+
1)
(10)
N
i
R
E
S
B
S
;
R
E
S
=
I
D
,
τ
,
X
,
Y;
(11)
R
E
S
→
i
N
O
D
E
I
N
F
O
_
t
a
b
l
e
(12)
E
n
d
L
o
o
p
(13)
S
u
U
∗
→
S
(14)
S
→
R
T
(
S
)
(15)
N
i
+
1
→
N
i
τ
(16)
τ
c
=
(
I
D
,
X
,
Y
,
τ
)
(17)
U
∗
→
D
(18)
f
o
r
i
=
S
t
o
D //Route Discovery
(19)
R
T
(
S
)
N
i;
(20)
L
i
→
N
i
,
N
i
+
1;
(21)
R
E
S
→
i
R
O
U
T
I
N
G
_
t
a
b
l
e
(22)
E
n
d
L
o
o
p
(23)
f
o
r
i
=
S
t
o
D// Data transmission
(24)
i
f
(
c
u
r
r
e
n
t
N
i
.
i
n
f
o
=
=
iROTINGtable==iNODEINFOtable)then
(25)
i
f
c
u
r
r
e
n
t
N
i
.
i
n
f
o
=
=
i
R
O
U
T
I
N
G
t
a
b
l
e
=
=
i
N
O
D
E
I
N
F
O
t
a
b
l
e
t
h
e
n
(26)
N
i
d
a
t
a
N
i
+
1
(27)
e
l
s
e
(28)
N
i
+
1
i
s
b
l
o
c
k
e
d
a
s
S
y
b
i
l
N
o
d
e
(29)
E
n
d
L
o
o
p
(30)
i
R
O
U
T
I
N
G
t
a
b
l
e entries clear
(31)
EndThe CAM-PVM algorithm is used during the discovery and data transmission in the network, where the node’s information is checked from theBS
i
N
O
D
E
I
N
F
O
_
t
a
b
l
e. After verification of CAM-PVM algorithm, the algorithm collects the ID, timestamp, and current location information of the nodes and compares with initial information when they are registered. The results of the CAM-PVM algorithm can provide only the trusted nodes in the route to ensure secured data transmission. Otherwise the particular nodes are treated as unknown nodes such as Sybil and data transmission in the current is stopped and alternate path is selected.Application of CAM-PVM is a time consuming process and also cost effective. So, that prevention device is suggested in this paper to eliminate Sybil activity. Each node should communicate by passing the authentication message. In case the source node suspects the destination dynamically, we can make use of the CAM-PVM with MAP algorithm for comparing and for message authentication to check whether the current node is Sybil or not. Where in the networkG, a node N
i passes the data to node N
j the node N
i sends a request message to node N
j with its key, as m
s
g
(
N
i
), which is generated by theBS while registering in the network G. Node N
j (destination node) submits its key message with m
s
g
(
N
j
), and later, both keys are verified by the base station and an ok signal produced for sharing the data and any other information. Data transmission occurs between N
i
,
N
j once they get the signal from the base station. The pseudocode uses for the message authentication and passing method are given below in detail.Message Authentication and Passing (MAP)
(1)
G
=
N
0
,
N
1
,
N
2
,
…
,
N
n
(2)
f
o
r
I
=
1
t
o
n
(3)
r
t
a
b
l
e
=
a
d
d
r
e
c
(
N
i
(
i
d
)
,
N
i
(
x
)
,
N
i
(
y
)
,
N
i
(
m
s
g
)
)
// node id,x, y values of i
t
h node
(4)
E
n
d
(5)
f
o
r
I
=
1
t
o
n
(6)
f
o
r
J
=
1
t
o
n
(7)
N
i
→
S
e
n
d
r
e
q
u
e
s
t
→
N
j
(8)
N
j
→
S
e
n
d
a
c
c
e
p
t
a
n
c
e
→
N
i
(9)
I
f
m
s
g
N
i
,
m
s
g
N
j
e
x
i
s
t
s
(
r
t
a
b
l
e
)
) then
(10)
N
i
→
S
e
n
d
(
d
a
t
a
P
→
N
j
)
(11)
E
l
s
e
(12)
C
h
o
o
s
e
t
h
e
n
e
x
t
n
e
i
g
h
b
o
r
(13)
E
n
d
I
f
(14)
E
n
d
f
o
r
J
(15)
E
n
d
f
o
r
I
(16)
End


## 2.1. Security Attacks on WSN

Various types of malicious activities are patent in wireless sensor network. Some of these are created in terms of nodes while others are created in a network, data link, and application layers. Some are created in the physical state [11].The attacks are currently classified as active and passive. The former is created by deployment of illegal information in the network that can affect it. Sybil, sinkhole, and eavesdropper are some of the active attacks. Passive attacks are those which are meant to affect the network resources such as lifetime and network size.


## 2.2. Sybil Attack

A node or a device takes many identities that may not necessarily be lawful. It does not impersonate any node, but fast it only assumes the identity of another among several nodes, causing redundancies in the routing protocol. Sybil attacks degrade data integrity, security, and resource utilization. It can also perform storage, routing mechanisms, air resource allocation, and misbehavior detection. In a sensor network hundreds of sensor nodes form the communication network. The wireless communication between these sensor nodes passes through a central station. These nodes communicate with a specified of nodes of a specified number [12]. There are many encryption techniques available to prevent external attack on the nodes, but nodes in the communication network can also mount an attack. One of these insider attacks is called a Sybil attack [13–15] in which the node that spoofs the other node is called Sybil node S and the other one is a normal node N. In a proper communication system only N nodes should communicate with one another. But here, S node comes in another form of its own as an internal known node and launches an attack on the network. The Sybil node tries to communicate with neighboring nodes by using the identity of the normal node and in the process a single node gives many identities in the area to other nodes in the network which is illegal. A Sybil node can be formed as a new identity or as a pilfering legal identity. It is, therefore, considered an additional entity of a misbehaving node. This causes confusion in the network and it gets collapsed. A faulty node which enters into the network with different IDs is shown in Figure 1.Figure 1
Sybil attacks with multiple ID.As a result Sybil attacks are classified into two forms on the basis of the manner of attack on the network. They are as follows.(i) Direct Attack and Indirect Attack. In a direct attack, the real nodes communicate directly with Sybil nodes, whereas, in an indirect attack, the communication is done through a malicious node.(ii) Fabricated Attack and Stolen Identity Attack. Legal identities of nodes are used to create new illegal nodes. That is to say, a sensor node which has an ID of 16-bit integers creates the same ID of 16 bits, which are fabricated nodes. The IDs stolen by the Sybil node are destroyed by checking the identity replication [16].


## 2.3. Existing Methodology

Random Password Generation (RPC) algorithm focuses on the various traffic levels and security during data transmission in WSN. RPC algorithm generates the routing table which holds information about deployed nodes. The intermediate nodes in the route are identified between source and destination. The intermediate node’s information is compares with RPC database during communication among nodes, based on the comparison results it decides whether Sybil or normal node. RPC also generates the route by adding the genuine node in its path from source to destination node using several subprocedures [17].


## 2.4. Proposed Approach

The main objective of this paper is to design and develop an algorithm for detecting and preventing Sybil attacks in wireless sensor network. It is referred to message authentication and passing algorithm. Creation of Sybil activity through use of the other personal identities is well known. Most of the existing research deals with the detection of the Sybil attack through verification of identities.


### 2.4.1. Network Model

In this paper,N numbers of nodes are deployed in the network randomly under the control of and an administrator. These are well configured, energy efficient, and promising nodes in the network. During node creation, each node will receive a H
E
L
L
O message from the B
S with a timestamp message indicating the node creation time (birth time) in the network. The entire node responds to the BS with a RES message with ID, timestamp, and location. Then this information is stored in a i
N
O
D
E
I
N
F
O
_
t
a
b
l
e under the control of the administrator of the network. The entire network model is presented as G
=
{
N
1
,
N
2
,
…
,
N
i
,
…
,
N
m
,
B
S
,
A
d
m
i
n
} where m is the number of nodes in the network. Each node is deployed in the network as L
o
c
a
t
i
o
n
N
i
=
rand
⁡
(
x
)
,
rand
⁡
(
y
), where X
,
Y is any location within the network area. TheBS sends a HELLO packet to all the newly created nodes in the network which can be written as(1)
B
S
M
s
g
,
τ
∑
i
=
1
m
N
i
,
where
N
1
,
N
2
,
…
,
N
i
,
…
,
N
m
are  Nodes
.And, each node in the network is sending aRES packet to theBS which can be written as N
i
RES
B
S, where the HELLO andRES packet consist of node ID and the timestamp. H
E
L
L
O
=
τ
N
i and R
E
S
=
(
I
D
N
i
,
τ
N
i
), where N
i denotes the i
t
h node, τ
(
N
i
) denotes timestamp of the i
t
h node, and I
D
(
N
i
) denotes identity of the i
t
h node. The parameters such as ID and τ are used to verify that the node is a Sybil or not. CAM-PVM algorithm for Sybil detection.In networkG, a node S needs to transmit a data to a node D. So, it is necessary to discover a route from S to D through an N-hop intermediate node. The number of intermediate nodes depends on the network size. The routing mechanism used in this paper follows AODV protocol. During this process, current information about the intermediate nodes (ID, timestamp) is tentatively stored in a routing table named as i
R
O
U
T
I
N
G
_
t
a
b
l
e.The duration between the route discovery and data transmission in the discovered route is very small. While data transmission, thei
R
O
U
T
I
N
G
_
t
a
b
l
e data entries are compared with the entries available in the i
N
O
D
E
I
N
F
O
_
t
a
b
l
e shown in Table 1, where it helps to identify the duplicate nodes with id, timestamp, and the location. For example, G
=
{
N
1
,
N
2
,
…
,
N
i
,
…
,
N
m
}
N
3 is considered source node, N
9 the destination node, and the intermediate nodes are N
5, N
7, and N
8. The route discovered from N
3 to N
9 is N
3
→
N
5
→
N
7
→
N
8
→
N
9. The i
R
O
U
T
I
N
G
_
t
a
b
l
e of the discovered route is shown in Table 2, which comprises the original node ID, timestamp [
τ
], location, and the current timestamp during the time of route discovery.Table 1
iNODEINFO_table.
Node ID
N
1
N
2
N
3
N
4
N
5
N
6
N
7
N
8
N
9
N
10
τ
11:00
11:02
11:30
11:37
11:41
11:43
11:56
11:59
12:04
12:06
X
34
67
87
123
154
23
18
54
62
59
Y
11
33
54
67
89
123
131
145
165
154Table 2
i
R
O
U
T
I
N
G
_
t
a
b
l
e.
Node ID
N
3
N
5
N
7
N
8
N
9
τ
11:30
11:41
11:56
11:59
12:04
X
87
154
18
54
62
Y
54
89
131
145
165
τ
1:01
1:04
1:05
1:06
1:06Now during the data transmission, the discovered route is verified by comparing current intermediate node information with thei
R
O
U
T
I
N
G
_
t
a
b
l
e by updating the node entries. From Table 3, it is clear that the N
7 information is replicated; it is found that the information of the replica node does not match the original N
7 information in i
N
O
D
E
I
N
F
O
_
t
a
b
l
e.Table 3
NodeN
2 is the Sybil, acting as N
7.
Node ID
N
3
N
5
N
7
[
N
2
]
N
7
N
8
N
9
τ
11:30
11:41
11:02
11:56
11:59
12:04
X
87
154
67
18
54
62
Y
54
89
33
131
145
165
τ
1:01
1:04
1:05
1:05
1:06
1:06Sybil activity is identified with application of the CAM-PVM algorithm and is detected in the network. To provide prevention for Sybil activity, another MAP algorithm is applied along with CAM-PVM for prevention of Sybil activity. MAP comprises unicast as well as multicast based communication in the network. The algorithm for CAM-PVM and MAP is given below.Compare and Match-Position Verification Method (CAM-PVM)
(1)
L
e
t
G
=
N
1
,
N
2
,
N
3
,
…
,
N
m
(2)
L
e
t
B
S
,
A
d
m
i
n
b
e
t
h
e
w
e
l
l
c
o
n
f
i
g
u
r
e
d
n
o
d
e
s
(3)
f
o
r
i
=
1
t
o
m // Nodes are placed
randomly
(4)
N
i
←
L
o
c
a
t
i
o
n
(
rand
⁡
X
,
rand
⁡
Y
)
(5)
I
D
(
N
i
←
i
);
(6)
E
n
d
L
o
o
p
(7)
Let Li be the set of link between pair of nodes in the network
(8)
N
i
→
B
S
(
M
s
g
,
τ
)// For every nodes N
i
(9)
U
∗
→
m
i
n
i
m
u
mdistance(N
i, N
i
+
1)
(10)
N
i
R
E
S
B
S
;
R
E
S
=
I
D
,
τ
,
X
,
Y;
(11)
R
E
S
→
i
N
O
D
E
I
N
F
O
_
t
a
b
l
e
(12)
E
n
d
L
o
o
p
(13)
S
u
U
∗
→
S
(14)
S
→
R
T
(
S
)
(15)
N
i
+
1
→
N
i
τ
(16)
τ
c
=
(
I
D
,
X
,
Y
,
τ
)
(17)
U
∗
→
D
(18)
f
o
r
i
=
S
t
o
D //Route Discovery
(19)
R
T
(
S
)
N
i;
(20)
L
i
→
N
i
,
N
i
+
1;
(21)
R
E
S
→
i
R
O
U
T
I
N
G
_
t
a
b
l
e
(22)
E
n
d
L
o
o
p
(23)
f
o
r
i
=
S
t
o
D// Data transmission
(24)
i
f
(
c
u
r
r
e
n
t
N
i
.
i
n
f
o
=
=
iROTINGtable==iNODEINFOtable)then
(25)
i
f
c
u
r
r
e
n
t
N
i
.
i
n
f
o
=
=
i
R
O
U
T
I
N
G
t
a
b
l
e
=
=
i
N
O
D
E
I
N
F
O
t
a
b
l
e
t
h
e
n
(26)
N
i
d
a
t
a
N
i
+
1
(27)
e
l
s
e
(28)
N
i
+
1
i
s
b
l
o
c
k
e
d
a
s
S
y
b
i
l
N
o
d
e
(29)
E
n
d
L
o
o
p
(30)
i
R
O
U
T
I
N
G
t
a
b
l
e entries clear
(31)
EndThe CAM-PVM algorithm is used during the discovery and data transmission in the network, where the node’s information is checked from theBS
i
N
O
D
E
I
N
F
O
_
t
a
b
l
e. After verification of CAM-PVM algorithm, the algorithm collects the ID, timestamp, and current location information of the nodes and compares with initial information when they are registered. The results of the CAM-PVM algorithm can provide only the trusted nodes in the route to ensure secured data transmission. Otherwise the particular nodes are treated as unknown nodes such as Sybil and data transmission in the current is stopped and alternate path is selected.Application of CAM-PVM is a time consuming process and also cost effective. So, that prevention device is suggested in this paper to eliminate Sybil activity. Each node should communicate by passing the authentication message. In case the source node suspects the destination dynamically, we can make use of the CAM-PVM with MAP algorithm for comparing and for message authentication to check whether the current node is Sybil or not. Where in the networkG, a node N
i passes the data to node N
j the node N
i sends a request message to node N
j with its key, as m
s
g
(
N
i
), which is generated by theBS while registering in the network G. Node N
j (destination node) submits its key message with m
s
g
(
N
j
), and later, both keys are verified by the base station and an ok signal produced for sharing the data and any other information. Data transmission occurs between N
i
,
N
j once they get the signal from the base station. The pseudocode uses for the message authentication and passing method are given below in detail.Message Authentication and Passing (MAP)
(1)
G
=
N
0
,
N
1
,
N
2
,
…
,
N
n
(2)
f
o
r
I
=
1
t
o
n
(3)
r
t
a
b
l
e
=
a
d
d
r
e
c
(
N
i
(
i
d
)
,
N
i
(
x
)
,
N
i
(
y
)
,
N
i
(
m
s
g
)
)
// node id,x, y values of i
t
h node
(4)
E
n
d
(5)
f
o
r
I
=
1
t
o
n
(6)
f
o
r
J
=
1
t
o
n
(7)
N
i
→
S
e
n
d
r
e
q
u
e
s
t
→
N
j
(8)
N
j
→
S
e
n
d
a
c
c
e
p
t
a
n
c
e
→
N
i
(9)
I
f
m
s
g
N
i
,
m
s
g
N
j
e
x
i
s
t
s
(
r
t
a
b
l
e
)
) then
(10)
N
i
→
S
e
n
d
(
d
a
t
a
P
→
N
j
)
(11)
E
l
s
e
(12)
C
h
o
o
s
e
t
h
e
n
e
x
t
n
e
i
g
h
b
o
r
(13)
E
n
d
I
f
(14)
E
n
d
f
o
r
J
(15)
E
n
d
f
o
r
I
(16)
End


## 2.4.1. Network Model

In this paper,N numbers of nodes are deployed in the network randomly under the control of and an administrator. These are well configured, energy efficient, and promising nodes in the network. During node creation, each node will receive a H
E
L
L
O message from the B
S with a timestamp message indicating the node creation time (birth time) in the network. The entire node responds to the BS with a RES message with ID, timestamp, and location. Then this information is stored in a i
N
O
D
E
I
N
F
O
_
t
a
b
l
e under the control of the administrator of the network. The entire network model is presented as G
=
{
N
1
,
N
2
,
…
,
N
i
,
…
,
N
m
,
B
S
,
A
d
m
i
n
} where m is the number of nodes in the network. Each node is deployed in the network as L
o
c
a
t
i
o
n
N
i
=
rand
⁡
(
x
)
,
rand
⁡
(
y
), where X
,
Y is any location within the network area. TheBS sends a HELLO packet to all the newly created nodes in the network which can be written as(1)
B
S
M
s
g
,
τ
∑
i
=
1
m
N
i
,
where
N
1
,
N
2
,
…
,
N
i
,
…
,
N
m
are  Nodes
.And, each node in the network is sending aRES packet to theBS which can be written as N
i
RES
B
S, where the HELLO andRES packet consist of node ID and the timestamp. H
E
L
L
O
=
τ
N
i and R
E
S
=
(
I
D
N
i
,
τ
N
i
), where N
i denotes the i
t
h node, τ
(
N
i
) denotes timestamp of the i
t
h node, and I
D
(
N
i
) denotes identity of the i
t
h node. The parameters such as ID and τ are used to verify that the node is a Sybil or not. CAM-PVM algorithm for Sybil detection.In networkG, a node S needs to transmit a data to a node D. So, it is necessary to discover a route from S to D through an N-hop intermediate node. The number of intermediate nodes depends on the network size. The routing mechanism used in this paper follows AODV protocol. During this process, current information about the intermediate nodes (ID, timestamp) is tentatively stored in a routing table named as i
R
O
U
T
I
N
G
_
t
a
b
l
e.The duration between the route discovery and data transmission in the discovered route is very small. While data transmission, thei
R
O
U
T
I
N
G
_
t
a
b
l
e data entries are compared with the entries available in the i
N
O
D
E
I
N
F
O
_
t
a
b
l
e shown in Table 1, where it helps to identify the duplicate nodes with id, timestamp, and the location. For example, G
=
{
N
1
,
N
2
,
…
,
N
i
,
…
,
N
m
}
N
3 is considered source node, N
9 the destination node, and the intermediate nodes are N
5, N
7, and N
8. The route discovered from N
3 to N
9 is N
3
→
N
5
→
N
7
→
N
8
→
N
9. The i
R
O
U
T
I
N
G
_
t
a
b
l
e of the discovered route is shown in Table 2, which comprises the original node ID, timestamp [
τ
], location, and the current timestamp during the time of route discovery.Table 1
iNODEINFO_table.
Node ID
N
1
N
2
N
3
N
4
N
5
N
6
N
7
N
8
N
9
N
10
τ
11:00
11:02
11:30
11:37
11:41
11:43
11:56
11:59
12:04
12:06
X
34
67
87
123
154
23
18
54
62
59
Y
11
33
54
67
89
123
131
145
165
154Table 2
i
R
O
U
T
I
N
G
_
t
a
b
l
e.
Node ID
N
3
N
5
N
7
N
8
N
9
τ
11:30
11:41
11:56
11:59
12:04
X
87
154
18
54
62
Y
54
89
131
145
165
τ
1:01
1:04
1:05
1:06
1:06Now during the data transmission, the discovered route is verified by comparing current intermediate node information with thei
R
O
U
T
I
N
G
_
t
a
b
l
e by updating the node entries. From Table 3, it is clear that the N
7 information is replicated; it is found that the information of the replica node does not match the original N
7 information in i
N
O
D
E
I
N
F
O
_
t
a
b
l
e.Table 3
NodeN
2 is the Sybil, acting as N
7.
Node ID
N
3
N
5
N
7
[
N
2
]
N
7
N
8
N
9
τ
11:30
11:41
11:02
11:56
11:59
12:04
X
87
154
67
18
54
62
Y
54
89
33
131
145
165
τ
1:01
1:04
1:05
1:05
1:06
1:06Sybil activity is identified with application of the CAM-PVM algorithm and is detected in the network. To provide prevention for Sybil activity, another MAP algorithm is applied along with CAM-PVM for prevention of Sybil activity. MAP comprises unicast as well as multicast based communication in the network. The algorithm for CAM-PVM and MAP is given below.Compare and Match-Position Verification Method (CAM-PVM)
(1)
L
e
t
G
=
N
1
,
N
2
,
N
3
,
…
,
N
m
(2)
L
e
t
B
S
,
A
d
m
i
n
b
e
t
h
e
w
e
l
l
c
o
n
f
i
g
u
r
e
d
n
o
d
e
s
(3)
f
o
r
i
=
1
t
o
m // Nodes are placed
randomly
(4)
N
i
←
L
o
c
a
t
i
o
n
(
rand
⁡
X
,
rand
⁡
Y
)
(5)
I
D
(
N
i
←
i
);
(6)
E
n
d
L
o
o
p
(7)
Let Li be the set of link between pair of nodes in the network
(8)
N
i
→
B
S
(
M
s
g
,
τ
)// For every nodes N
i
(9)
U
∗
→
m
i
n
i
m
u
mdistance(N
i, N
i
+
1)
(10)
N
i
R
E
S
B
S
;
R
E
S
=
I
D
,
τ
,
X
,
Y;
(11)
R
E
S
→
i
N
O
D
E
I
N
F
O
_
t
a
b
l
e
(12)
E
n
d
L
o
o
p
(13)
S
u
U
∗
→
S
(14)
S
→
R
T
(
S
)
(15)
N
i
+
1
→
N
i
τ
(16)
τ
c
=
(
I
D
,
X
,
Y
,
τ
)
(17)
U
∗
→
D
(18)
f
o
r
i
=
S
t
o
D //Route Discovery
(19)
R
T
(
S
)
N
i;
(20)
L
i
→
N
i
,
N
i
+
1;
(21)
R
E
S
→
i
R
O
U
T
I
N
G
_
t
a
b
l
e
(22)
E
n
d
L
o
o
p
(23)
f
o
r
i
=
S
t
o
D// Data transmission
(24)
i
f
(
c
u
r
r
e
n
t
N
i
.
i
n
f
o
=
=
iROTINGtable==iNODEINFOtable)then
(25)
i
f
c
u
r
r
e
n
t
N
i
.
i
n
f
o
=
=
i
R
O
U
T
I
N
G
t
a
b
l
e
=
=
i
N
O
D
E
I
N
F
O
t
a
b
l
e
t
h
e
n
(26)
N
i
d
a
t
a
N
i
+
1
(27)
e
l
s
e
(28)
N
i
+
1
i
s
b
l
o
c
k
e
d
a
s
S
y
b
i
l
N
o
d
e
(29)
E
n
d
L
o
o
p
(30)
i
R
O
U
T
I
N
G
t
a
b
l
e entries clear
(31)
EndThe CAM-PVM algorithm is used during the discovery and data transmission in the network, where the node’s information is checked from theBS
i
N
O
D
E
I
N
F
O
_
t
a
b
l
e. After verification of CAM-PVM algorithm, the algorithm collects the ID, timestamp, and current location information of the nodes and compares with initial information when they are registered. The results of the CAM-PVM algorithm can provide only the trusted nodes in the route to ensure secured data transmission. Otherwise the particular nodes are treated as unknown nodes such as Sybil and data transmission in the current is stopped and alternate path is selected.Application of CAM-PVM is a time consuming process and also cost effective. So, that prevention device is suggested in this paper to eliminate Sybil activity. Each node should communicate by passing the authentication message. In case the source node suspects the destination dynamically, we can make use of the CAM-PVM with MAP algorithm for comparing and for message authentication to check whether the current node is Sybil or not. Where in the networkG, a node N
i passes the data to node N
j the node N
i sends a request message to node N
j with its key, as m
s
g
(
N
i
), which is generated by theBS while registering in the network G. Node N
j (destination node) submits its key message with m
s
g
(
N
j
), and later, both keys are verified by the base station and an ok signal produced for sharing the data and any other information. Data transmission occurs between N
i
,
N
j once they get the signal from the base station. The pseudocode uses for the message authentication and passing method are given below in detail.Message Authentication and Passing (MAP)
(1)
G
=
N
0
,
N
1
,
N
2
,
…
,
N
n
(2)
f
o
r
I
=
1
t
o
n
(3)
r
t
a
b
l
e
=
a
d
d
r
e
c
(
N
i
(
i
d
)
,
N
i
(
x
)
,
N
i
(
y
)
,
N
i
(
m
s
g
)
)
// node id,x, y values of i
t
h node
(4)
E
n
d
(5)
f
o
r
I
=
1
t
o
n
(6)
f
o
r
J
=
1
t
o
n
(7)
N
i
→
S
e
n
d
r
e
q
u
e
s
t
→
N
j
(8)
N
j
→
S
e
n
d
a
c
c
e
p
t
a
n
c
e
→
N
i
(9)
I
f
m
s
g
N
i
,
m
s
g
N
j
e
x
i
s
t
s
(
r
t
a
b
l
e
)
) then
(10)
N
i
→
S
e
n
d
(
d
a
t
a
P
→
N
j
)
(11)
E
l
s
e
(12)
C
h
o
o
s
e
t
h
e
n
e
x
t
n
e
i
g
h
b
o
r
(13)
E
n
d
I
f
(14)
E
n
d
f
o
r
J
(15)
E
n
d
f
o
r
I
(16)
End


## 3. Results and Discussion

The entire system model is simulated using NS2 software with 25 nodes with a network size of 1200 × 1200. Each sensor node behaves under AODV (Ad Hoc on Demand Vector) protocol. All nodes are constructed under a singleBS. In this network model, node 17 is ready to receive the data from node 0. When node 0 sends a REQ message to node 17, that node sends aRES message to node 0 back. This can be sensed by node 11 which sends aRES message with the label of node 17. This can be traced while node 11 is unable to submit its authenticated key value which belongs to node 17. So it is detected as a Sybil node and rejects node 11 from the network. In this paper, the efficiency of the network is calculated by comparing the throughput before and after inclusion of message authentication and passing algorithm in the network functionality. This is described in detail in Figure 2.Figure 2
Simulation of identifying Sybil node.As the proposed approach is meant to ensure detection and prevention of the Sybil node, the performance can be analyzed by calculating the average delay of data packet transfer, throughput, malicious node, and other necessary factors for judging the quality of service of a routing protocol. In this paper, Figure3 shows the average delay of the data packet transfer of the network before deployment of the message authentication and passing algorithm where data packets of different sizes are transmitted at different intervals of time. The behavior of Sybil nodes resembles dispatch of data at any time from any location and that would disturb the original nodes in the network. The figure shows the average delay is very less after applying the MAP algorithm.Figure 3
Comparison of average delay of data packet transfer between existing method RPC with CAM-PVM and MAP.In order to check the performance evaluation, a large number of nodes are deployed in the network and the detection rates of the Sybil nodes. A number of iterations can be made with different numbers of nodes in the network as shown by the performance. With the increase in the number of nodes, there is also an increase in the number of misbehaving nodes, which obviously affects the data and results in data loss. The throughput of the proposed approach before and after deployment with the routing protocol is calculated. In existing Random Password Comparison method, the throughput will be 74% whereas in case of CAM-PVM it will be 85% and in MAP it will be 95%. It shows the efficiency of the proposed approach. The comparison of throughput between existing method with CAM-PVM and MAP is shown in Figure4.Figure 4
Comparison of throughput between existing RPC method with CAM-PVM and MAP.Once a detection procedure is deployed during transmission, it detects the Sybil node and avoids transmission through that attacker node. Data loss can be thwarted through detection. In this scenario the number of times for consumption should be considered for the improvement of the quality of service. The detection rate of the Sybil attack is more accurate, but considering waste of time in such a kind of situation, prevention as a factor that directly eliminates the Sybil nodes is the deciding factor in the place of detection. Subsequent elimination of the procedure message authentication and passing method for prevention of the Sybil attack is applicable, but the detection rate is smaller compared to CAM-PVM and other existing methods. There is a clear indication of this fact. The same simulation is repeated forn number of nodes with n number of times in network simulation software. Table 4 shows the comparison of CAM-PVM with message authentication and passing method.Table 4
Comparison of Sybil node with existing RPC method with CAM-PVM and MAP.
Number of nodes
10
20
30
40
50
60
70
80
90
100
Sybil nodes
2
4
6
8
10
12
14
16
18
20
RPC
1
2
3
4
6
8
9
10
11
12
CAM-PVM
2
3
4
5
7
9
10
11
12
13
MAP
2
3
5
6
8
10
12
13
15
18Simulation is also carried out in multiple rounds where the number of nodes deployed that are different for each round and there is a difference in the number of Sybil nodes according to the normal nodes. Here we had conducted a simulation of our proposed algorithm by assigning 2 Sybil nodes for each 10 nodes and forward our simulation process up to 100 nodes starting from 10 nodes. Table4 shows our simulation result for Sybil node detection from which we can clearly say that our MAP algorithm produces 30% more detection accuracy compared with the CAM-PVM algorithm and existing RPC methods. In case of least Sybil nodes both algorithms produce same results but when the number of malicious nodes increased the performance of CAMPVM gets decrease while our algorithm maintains its consistency. The performance is comparatively good in message authentication and passing method. The optimized and compared output of the MAP with CAM-PVM algorithm and existing RPC method is given in the graphical representation as shown in Figure 5.Figure 5
Number of Sybil node detection with existing RPC method with proposed between CAM-PVM and MAP.Figure6 shows the comparison of detection rate with existing RPC methods with proposed CAM-PVM and MAP. In existing RPC method, the detection rate was only 60% whereas in proposed CAM-PVM the detection rate was 75% and in MAP the detection rate was 90%. It shows the efficiency of the proposed approach. The performance comparisons show three categories in which the performance values are compared using the existing methodology. The three factors are data packet transfer; throughput and detection of malicious node are computed and compared. In the first methodology, average delay of data packet transfer between existing RPC method with proposed method. The average delay is calculated as successful data packet transmission. In the second methodology throughput is calculated between the source nodes to destination node. By comparison with the existing system throughput will be 74% whereas in CAM-PVM is taking 85% and message authentication and passing method 95% of the total time. In the third methodology, the detection of malicious node comparison between the existing system is 60% whereas in CAM-PVM detects 65% of malicious node whereas the message authentication and passing method detects 90% of the malicious node. Hence message authentication and passing method is considered a better method than the CAM-PVM even under this criterion.Figure 6
Comparison of detection rate with existing RPC method with proposed CAM-PVM and MAP.


## 4. Conclusions

In this paper the message authentication and passing method is applied for checking the trustworthiness or otherwise for a Sybil node. The action of a node as a Sybil node with duplicate ID and information can happen only when the node has complete information about other nodes. Verification of the node needs the application of CAM-PVM. Instead of wasting time for CAM-PVM to check each and every node, the message authentication and passing procedure is applied for authentication prior to communication. If a node does not have any authorization by the network or by the base station, it cannot communicate with any other node in the network. The message authentication and passing method is so effective and is known for more time consuming than any other method.Message authentication and passing method requires modification and reduction in time consumption and for cost effectiveness. The size of the network is not a constraint. The throughput of the network should be higher than the other security algorithm which is applied earlier in the network security.



---

*Source: 841267-2015-07-05.xml*