VOL 2 .
NO 3
e-ISSN : 2549-9904
ISSN : 2549-9610
INTERNATIONAL JOURNAL ON INFORMATICS VISUALIZATION
Sybil Node Detection in Mobile Wireless Sensor Networks Using Observer Nodes Mojtaba Jamshidi #.
Milad Ranjbari *.
Mehdi Esnaashari **.
Nooruldeen Nasih Qader ***.
Mohammad Reza Meybodi **** Department of Electrical.
Computer and IT Engineering.
Qazvin Branch.
Islamic Azad University.
Qazvin.
Iran *Department of Computer Engineering.
Arak Branch.
Islamic Azad University.
Arak.
Iran Faculty of Computer Engineering.
Toosi University of Technology.
Tehran.
Iran
***
Computer Science Department.
University of Human Development.
Iraq
****
Computer Engineering and Information Technology Department.
Amirkabir University of Technology.
Tehran.
Iran E-mail: jamshidi.
mojtaba@gmail.
com, miladranjbari@gmail.
com, esnaashari@kntu.
qader@uhd.
iq, mmeybodi@aut.
AbstractAi Sybil attack is one of the well-known dangerous attacks against wireless sensor networks in which a malicious node attempts to propagate several fabricated identities.
This attack significantly affects routing protocols and many network operations, including voting and data aggregation.
The mobility of nodes in mobile wireless sensor networks makes it problematic to employ proposed Sybil node detection algorithms in static wireless sensor networks, including node positioning.
RSSI-based, and neighbour cooperative algorithms.
This paper proposes a dynamic, light-weight, and efficient algorithm to detect Sybil nodes in mobile wireless sensor networks.
In the proposed algorithm, observer nodes exploit neighbouring information during different time periods to detect Sybil nodes.
The proposed algorithm is implemented by J-SIM simulator and its performance is compared with other existing algorithm by conducting a set of experiments.
Simulation results indicate that the proposed algorithm outperforms other existing methods regarding detection rate and false detection rate.
Moreover, they also showed that the mean detection rate and false detection rate of the proposed algorithm are respectively 99% and less than 2%.
KeywordsAi Wireless sensor networks.
Sybil attack, mobile node, observer node.
from legitimate nodes in other areas of the network.
When this malicious node simultaneously propagates several IDs, this attracts a lot of traffic, since legitimate neighbour nodes assume that each ID (Sybil nod.
corresponds to an individual physical node.
whereas, all the IDs (Sybil node.
correspond to one and only one hardware node.
Therefore, this attack can significantly disrupt routing protocols and even operations, including voting, misbehavior detection, data aggregation, and reputation evaluation .
We must note that many algorithms .
have been proposed to detect Sybil nodes in static wireless sensor networks, which cannot be integrated into mobile ones.
The reason is that most of these algorithms are based on node positioning or identify Sybil nodes based on RSSI or neighbor cooperation.
however, the mobility of nodes (Sybil and non-Sybi.
in mobile wireless sensor networks can disrupt the execution of these algorithms.
Also, in .
algorithms are proposed for detecting Sybil nodes in mobile sensor networks.
In .
, a centralized INTRODUCTION Type wireless sensor networks are ad hoc wireless networks, which contain hundreds to thousands of cheap sensor nodes.
Sensor nodes have constraints including energy, memory, radio range, and power computation.
According to these constraints, the broadcast nature of wireless communications, and the lack of resistance of sensor nodes against adversary tampering, security has become an important and challenging issue in these networks .
, .
Sybil attack .
is one of the important attacks affecting the network layer .
In Sybil attack, the adversary captures a legitimate node in the network and reprograms it .
s a malicious nod.
or inserts a legitimate node as a malicious one in the network.
After deployment in the network operational environment, this malicious node propagates several IDs .
rom here on referred to as "Sybil nodes"), which are fabricated by the adversary or stolen algorithm is proposed which includes 3 phases of clustering, selecting nodes in the vicinity of Sybil node, and routing So, it cannot be a proper algorithm.
In .
, another centralized algorithm is proposed which is based on nodesAo registration in a base station.
This algorithm is based on a base station so faces with scalability issue.
In .
, our previous algorithm is proposed which is uses a distributed labeling mechanism to assigned bit label to nodes based on their movement.
This algorithm requires exchanging so many messages between the watchdog nodes which increases communication overheads and power consumption as a result.
Added to this, the algorithm has a relatively low Sybil nodes detection rate.
Therefore, this paper proposes a novel light-weight algorithm to detect Sybil nodes in mobile wireless sensor networks using observer nodes.
The proposed algorithm is not based on node positioning.
RSSI, or authentication methods and only detects Sybil nodes by monitoring the network traffic.
The rest of this paper is organized as follows.
Section II presents previous work, system assumption, attack model, symbols, and the proposed algorithm.
Section i discusses the performance evaluation and simulation results.
The paper is concluded in Section IV.
through their energy changes in the course of network Also, in .
, some other algorithms are proposed for detecting Sybil nodes in mobile sensor networks, the mechanism, and limitation of which are explained in the previous section.
In .
, a mechanism based on evaluating trust values of neighbor nodes is proposed to detect Sybil nodes in wireless sensor networks.
The nodes with the trust values less than a threshold value are detected as Sybil nodes.
In .
, a message authentication algorithm is proposed for detecting Sybil nodes in wireless sensor networks.
This algorithm uses message authentication and passing procedure for authentication prior to communication.
In .
, a Random Password Generation (RPG) algorithm is proposed that analyze the traffic levels to defend against Sybil attack.
, a location algorithm is proposed that uses the characteristics of received signal powers of the nodes to detect Sybil nodes.
In .
, a rule-based anomaly detection system is proposed which relies on an Ultra-Wide Band (UWB) ranging-based detection algorithm to defend against Sybil attack.
In .
, a one-way key chain ID authentication algorithm is proposed to decrease the probability for attackers to lunch Replica and Sybil attacks which used elliptic curve discrete logarithm problem and node neighbor relationship to authorized nodes.
II.
MATERIAL AND METHOD
System Assumptions In this study, it is assumed that the total number of nodes is N = SN ON (SN is the number of normal sensor nodes and ON is the number of observer node.
Observer nodes periodically monitor the network traffic and detect Sybil All sensor nodes .
ormal and observe.
are randomly distributed in a two-dimensional region.
Sensor nodes are mobile and move in the environment during the network lifetime according to mobility models, e.
random waypoint.
Nodes have a unique ID and are unaware of their location.
Nodes communicate through a wireless radio channel and employ an Omni-directional mode broadcast.
The radio range of all nodes is fixed and equal to r.
moreover, it is assumed that if necessary, observer nodes utilize multi-hop reactive routing algorithms to make a route for them to Furthermore, it is assuming that normal sensor nodes are not tamper-resistant and an adversary can capture a node to access its confidential information and reprogram it.
In contrast, it is assumed that observer nodes are tamper-resistant and adversaries cannot decrypt and reprogram them.
In this section, we first present some existing algorithms which are proposed to defend against Sybil attack in wireless sensor networks.
Then, we present the preliminaries of the proposed algorithm, including assumptions, attack model, and symbols.
Finally, the proposed algorithm is presented.
Related Work Sybil attack was first introduced by Douceur in .
where it is noted that peer-to-peer networks are vulnerable to this In .
Karlof stated that the attack can affect routing protocols of sensor networks.
First.
Newsome et al.
analyzed Sybil attack to wireless sensor networks systematically and introduced mechanisms like key predistribution, radio source test, identity registration, and remote authentication code to deal with the attack.
In .
, an RSSI-based locating algorithm is proposed that uses the RSSI proportion of several receivers to estimate the location of nodes in a network.
In .
, the locating mechanism proposed in .
is used for detecting Sybil nodes.
Algorithm .
uses four location-aware nodes .
rackAing node.
capable of hearing packets throughout the network.
Tracking nodes cooperate to locate any nodes sending This is sufficient to detect Sybil nodes since all of them positioned in nearby locations.
RSSI-based algorithms also cannot be an appropriate solution since radio signals are prone to be interfered with by the environment, as a result, the detection precision of such algorithms is affected.
In .
, algorithms are proposed for detecting Sybil nodes in cluster-based sensor networks.
Algorithms proposed in .
use the concept of common neighbors to detect Sybil nodes.
In .
, another algorithm is proposed for detecting Sybil attack to multicast routing protocols based on geographic location.
In .
, a method is developed which collects routesAo information using Swarm Intelligence algorithm during network operation and detects Sybil nodes Attack Model The attacked model considered in this study based on the taxonomies in .
includes direct, simultaneous Sybil attack and fabricated IDs.
It is assumed that the network is insecure and nodes may be captured by adversaries.
A node captured by an adversary is called a malicious node and the rest are called normal nodes.
Each malicious node propagates several IDs (Sybil node.
Moreover, it is assumed that each malicious node propagates at least Tmin Sybil IDs.
Similar to normal sensor nodes, malicious nodes are also mobile in the network environment.
According to .
, the adversary can disrupt network operations in two ways using the Sybil In the first case, the adversary captures a large number of nodes in the network, reprograms them as malicious nodes, and re-injects them, such that each malicious node propagates few Sybil IDs .
2 or .
In this case, security algorithms hardly detect Sybil nodes and even some methods, including .
, may not detect them.
However, it is difficult and time consuming for the adversary to capture, decrypt, reprogram, and control a large number of normal nodes in the network.
The second case is when an adversary captures a smaller number of normal nodes and reprograms them as malicious ones, such that each malicious node propagates a larger number of Sybil IDs.
Similar to .
, the proposed algorithm assumes that the adversary follows the second case.
Similar to normal and observer nodes, malicious nodes are also mobile in the network environment.
Moreover, it is assumed that at each stage of mobility and reaching a new location in the network, each node propagates a AuHelloAy message, route request, etc.
this in fact is one of the requirements of mobile wireless sensor networks, so that each node can identify its current neighbours at any moment and if necessary, communicate or establish security keys with them, generate its routing table, .
It is clear that in this case when each malicious node enters a new location in the network, it should transmit a "Hello" message, route request, etc.
for all its Sybil IDs.
(Simultaneous Sybil attack model .
The proposed algorithm uses this type of propagated messages to detect Sybil nodes.
The Proposed Algorithm The main notion of the proposed algorithm is inspired by the number of node occurrences in the neighborhood of observer nodes.
As it was mentioned, we have two types of sensor nodes in the proposed algorithm .
ormal and observer Normal sensor nodes perform the network mission, including collecting information, sending data to the base station, etc.
and the observer nodes periodically monitor the network traffic and identify Sybil nodes.
Fig 1 presents a flowchart of the proposed algorithm.
The proposed algorithm consists of two phases.
The network traffic monitoring phase and the Sybil node detection phase, which are both performed by observer nodes.
In what follows, these two phases are explained.
Phase 1: after deployment in the network environment, sensor nodes begin to transmit packets .
acket containing the data.
AuHelloAy packetAy, route request packet, etc.
) and move in the corresponding environment.
Each observer node has a vector .
ith n entrie.
in its memory, called history, which stores the occurrences of other nodes in its Accordingly, during each time period t, if a node like u appears in its neighborhood, each observer node adds a unit to the field corresponding to node u in its history Time period t is selected large enough to allow observing the behavior of all Sybil IDs corresponding to a malicious node, including data transmission.
AuHelloAy messages, route requests, etc.
In other words, time distance t is selected large enough to reveal all Sybil IDs corresponding to their malicious node.
Since after entering a new location in the network, all normal and Sybil sensor nodes send packets .
AuHelloAy packe.
, if an observer node is present in that location, it records the entrance of new nodes to that location in its history vector.
Therefore, after P time periods of network lifetime, observer nodes will contain the occurrences of other nodes in their neighborhoods in their history.
Phase 2: after running the first phase, in order to detect Sybil nodes, each observer node u navigates its history vector and generates distinct sets of node IDs, such that each set includes the IDs of nodes, which appeared for an equal number in the node u's neighborhood.
subsequently, the observer node stores the sets, whose members are larger or equal to Tmin, as suspicious Sybil nodes in a list of sets, called suspicious_list.
Since it is assumed that each malicious node propagates at least Tmin Sybil IDs.
Therefore, for each observer node, the suspicious_list contains sets, whose members are suspected to be Sybil.
Assuming that malicious nodes a and b propagate Sybil nodes {S a .
S a ,.
S ia },{S b .
S b ,.
S bj } : i, j C Tmin , since all Sybil nodes Symbols A History: a vector in the memory of each observer node to keeps necessary information about movements of normal nodes.
A P: the number of monitoring iterations of network traffic by observer nodes .
he number of iterations in the first phase of the proposed algorith.
A Tmin: minimum number of Sybil IDs propagated by a malicious node.
A {S1m .
S 2m ,.
S m : Sybil IDs propagated by malicious A A A A A A A A A A node m.
Suspicious_list: a list in the memory of observer nodes to temporary store the ID of suspected Sybil Setui : set number i in the suspicious_list of observer node u.
Sybil_listu: a list containing the Sybil node detected by observer node u.
d: the diameter of the network.
A : the average number of neighbors of a node in the ON: the number of observer sensor nodes in the SN: the number of normal sensor nodes in the N: the total number of nodes in the network (N = SN ON).
M: the number of malicious nodes in the network S: the number of Sybil IDs propagated by each malicious node.
r: radio range of the nodes.
correspond to one malicious node, and thus, they move together, the occurrences of nodes .
S1a .
S2a ,.
Sia } will be equal in the neighborhood of observer node u .
A time.
Moreover, the occurrences of nodes .
S1b .
S 2b ,.
S bj } will also be equal in the neighborhood of observer node u .
A time.
Therefore, all nodes .
S a .
S a ,.
S ia } are placed in a set and all .
S1b .
S 2b ,.
S bj } are stored in another in the suspicious_list of observer node u.
Moreover, there may be some normal nodes, which have been present in the neighborhood of u for an equal number of times .
or A ).
Therefore, in addition to Sybil node IDs, sets in the suspicious_list of u will also contain the IDs of normal Accordingly, the false detection rate is increased if an observer node independently marks all IDs in its suspicious_list as Sybil nodes.
two sets is larger or equal to Tmin .
After this operation, if the number of remaining members in Set ui in larger or equal to Tmin , its content is added to the set of Sybil IDs of observer node u .
alled Sybil_list.
Node u repeats this operation for all sets in its suspicious_list.
Finally.
Sybil_listu will contain the IDs that are detected as Sybil by u.
Fig.
presents the pseudo-code for the main core of the second phase of the proposed algorithm.
node u for each Setui in it ' s Suspicious _ list Do for each node v Do for each Setvj in Suspicious _ list v Do if ( Setui AO Setvj C Tmin ) then Setui = Setui AO Setvj if ( Setui C Tmin ) then Sybil _ list u = Sybil _ list u Ai Setui Fig.
3 Pseudo-code for the second phase of the proposed algorithm i.
RESULTS AND DISCUSSION
In this section, we first evaluate the overhead of proposed algorithm in terms of memory, communication, and Then, we simulate the proposed algorithm and evaluate its detection rate through some experiments.
also compare its detection rate with the other existing Overhead Evaluation Memory overhead: since the proposed algorithm is only executed by observer nodes, memory overhead only corresponds to those nodes and normal ones bear no overhead by the proposed algorithm.
In the proposed algorithm, each observer node requires a space of order O(SN) to store the occurrences of other nodes in its history Moreover, in the Sybil node detection phase .
arking Sybil node.
, each observer node requires generating distinct sets of node IDs and temporary store its suspicious_list and those of other observer nodes in its memory to perform intersection on them.
At this stage, memory overhead reaches O(ON C SN ) .
However, since after detecting Sybil nodes, observer nodes free the space of suspicious_lists and distinct sets, the memory overhead imposed by the proposed algorithm on observer nodes can be considered of order O(SN).
Since observer nodes are only responsible for monitoring and detecting Sybil nodes and no memory is consumed for other operations in the network, including data aggregation, clustering, etc.
, thus, they will have sufficient free memory to store the history vector.
Communication overhead: energy consumption of an algorithm is critical due to the limitation of sensor nodes' Since sending packets consumes far much energy in comparison to other operations such as receiving or computing, therefore the number of transmitted packets imposed upon the network during execution of a certain algorithm is considered as a significant criterion.
The first Fig.
2 Flowchart of the proposed algorithm In order to increase detection accuracy, observer nodes cooperate to detect Sybil nodes.
More specifically, observer nodes send their suspicious_lists to each other.
They first utilize a multi-hop reactive routing algorithm, e.
, to generate routes between themselves and then exchange their suspicious_lists through them.
After receiving all suspicious_lists .
rom other observer node.
, an observer node begins to detect Sybil nodes.
More specifically, each observer node intersects the suspicious_lists of other observer nodes and its own to mark Sybil nodes.
The intersection operation is performed by each observer node u by navigating other sets in the suspicious_lists received from other observer nodes, e.
Set vj , for each existing set in its own list, e.
Setui and inserting the IDs resulting from intersecting these two sets in Setui , if the intersection of these Experiment 1: this experiment aims to evaluate the proposed algorithm regarding the detection rate of Sybil In this experiment, the number of sensor nodes is N=300, from which 5 are observer nodes (ON=.
Moreover, the number of Sybil IDs propagated by each malicious node is changed from 10 to 20 .
ith an increase step of .
The detection rate of Sybil nodes by the proposed algorithm is evaluated for time periods of 25 to 300 and the results are presented in Fig.
Experiment results indicate that changing the number of Sybil IDs has no effect on the detection rate of the proposed algorithm and this measure is higher than 99% after 200 time periods.
Detection Rate (%) phase of the proposed algorithm imposes no considerable communication overhead to the network and the only communication overhead of the proposed algorithm corresponds to sending suspicious_lists by observer nodes in the second phase.
Each observer node should send its suspicious_list to other observer nodes in a multi-hop Assuming that the diameter of the network is d, each observer node should send its suspicious_list to other observer nodes by (ON Oe .
C d transmissions.
Therefore, the total imposed communication overhead is (ON C (ON Oe .
C d ) .
We must note that the proposed algorithm will also have the communication overhead corresponding to running the reactive routing algorithm to find a route between observer Moreover, the number of observer nodes is very smaller than that of normal nodes in the network ( ON AA SN ).
Computational overhead: the proposed algorithm imposes no computational overhead to the normal sensor In the first phase of the proposed algorithm, each observer node will have a computational overhead of O( P C N CA ) to store information in its history vector.
The reason is that during each iteration of the first phase of the proposed algorithm, for each of its current neighbours, e.
the observer node navigates its history vector and adds a unit to the index corresponding to a.
in the second phase, each observer node first navigates its history vector and creates distinct sets of node IDs, which is feasible with a time order of O(N) .
aving an auxiliary space of order O(N)).
The observer node should then select suspicious sets from these distinct ones and add them to its suspicious_list, which is possible with a time order of O(N).
Finally, the observer node should detect Sybil nodes according to its suspicious_list and those of other observer nodes and by performing the aforementioned intersection operation in fig.
Assuming that the suspicious_list of each observer node has k sets on average, thus, each observer node performs intersection and Sybil node detection in a time order of O.
2 C ON ) .
Time periods (P) Fig.
4 Detection rate of the proposed algorithm for various rounds and Sybil Experiment 2: this experiment investigates the effect of the number of observer nodes on the detection rate of the proposed algorithm.
In this experiment.
S=20, and N=300, the number of observer nodes is changed from 2 to 10 .
ith an increase step of .
, and its effect is evaluated on the detection rate of Sybil nodes during time periods 25 to 300.
Fig.
4 presents the results of this experiment.
As we can see, for different values of ON .
he number of observer node.
, after 150 time periods, the detection rate of the proposed algorithm is higher than 90% and after 200 time periods, it is higher than 99%.
The result of this experiment shows that the detection rate of Sybil nodes is increased by reducing the number of observer nodes and conversely, decreased by increasing their number.
The reason is that observer nodes cooperate and perform an intersection operation on distinct sets .
uspicious_lists of observer node.
to detect Sybil Therefore, with a smaller number of observer nodes, the intersection of distinct sets will have a larger number of members, which increases both the detection rate and false detection rate .
s experiment .
Of course, after 200 time periods, the detection rate is higher than 99% for different numbers of observer nodes.
Moreover.
Fig.
5 presents the performance of the proposed and other existing algorithms regarding detection As we can see, the detection rate of Sybil nodes .
n averag.
by algorithm .
and the proposed algorithm is about 99%.
Whereas, detection rates of other algorithms are less than 99%.
However, algorithm .
is only applicable in Simulation Results The proposed algorithm was simulated by J-SIM simulation .
and its performance was compared with other algorithms .
, 10, 15, 16, 21, and .
by conducting a set of experiments.
The evaluated measures are as follows.
Detection Rate: the percentage of Sybil nodes, which are detected by a security algorithm.
False Detection Rate: a percentage of normal nodes, which are falsely detected as Sybil nodes by a security algorithm.
It is assumed that the network consists of N sensor nodes, which are randomly scattered in 100y100 square meters.
The operational area includes M=5 malicious nodes, which are randomly scattered in the network environment.
Parameter Tmin is set to 10.
Each malicious node propagates S fabricated IDs.
All nodes .
ormal and maliciou.
have the same radio range equal to 10 meters.
Moreover, the mobility model considered in .
is used to model the nodes` mobility in the network environment.
In order to insure the credibility of results, each simulation is repeated 100 times and the final results are achieved by averaging these 100 repetitions.
be 5% after 500 periods and less than 10% for the state of S C 12 after 1000 periods.
Of course, the criterion rate would tend to zero for all values of S C 10 by increasing the number of periods.
For instance, false detection rate for S= 18 and S=20 respectively would be 0.
3% and 0.
1% after 1000 Detection Rate (%) static wireless sensor networks.
Experiment results indicate the desirable performance of the proposed algorithm regarding the detection rate of Sybil nodes.
Time periods (P) Fig.
5 Comparison of the proposed algorithm with the other existing algorithms in terms of average detection rate.
Fig.
5 The effect of the number of observer nodes on the detection rate of the proposed algorithm False Detection Rate (%) Experiment 3: this experiment aims to evaluate the false detection rate of the proposed algorithm.
The number of nodes in this experiment is also N=300.
Moreover, the number of Sybil IDs propagated by malicious nodes is assumed S=20, observer nodes are changed from 4 to 10 .
ith increase step of .
, and its effect on the false detection rate of the proposed algorithm is evaluated in time periods 100 to 1000.
Fig.
6 presents the experimental results.
As we can see, a larger number of observer nodes reduces false detection rate, since observer nodes cooperate and intersect to detect Sybil nodes.
Experiment results indicate that if ON=10, after 500 time periods, the false detection rate is about 5% and after 900 time periods, this measure is about Furthermore.
Fig.
7 presents the false detection rate, on average case, of the proposed and the other algorithms.
The average false detection rates of the algorithms in .
are about 0%, algorithm .
and the proposed algorithm are about 2%, and the other algorithms are more than 2%.
Experiment 4: This experiment examined the effect of the number of Sybil IDs issued by malicious nodes (S) on the false detection rate of the proposed algorithm.
We set N=300 and ON=10 in the experiment, changed the number of Sybil IDs issued by any malicious node from 10 to 20 .
ith increment .
and then evaluated its effect on the false detection rate of the proposed algorithm for the periods 100 Fig.
8 depicts the results of the experiment.
demonstrated by the experiment results, false detection rate decreases with the increase of the number of the node Sybil IDs issued by malicious nodes.
However, the reduced number of the Sybil IDs issued by malicious nodes led to the increased rate of the criterion.
The reason may be that whatever the number of the Sybil IDs is less, more IDs may be wrongly detected as Sybil with regard to the form of intersecting and detection of the Sybil nodes that were described in the second phase of the proposed algorithm.
However, the false detection rate for the state of S A 18 may Time periods (P) Fig.
6 The effect of the number of observer nodes on the detection rate of the proposed algorithm.
Fig.
7 Comparison of the proposed algorithm with the other existing algorithms in terms of average false detection rate.
False Detection Rate (%) .
Time periods (P) .
Fig.
8 The effect of parameter S on false detection rate of the proposed .
IV.
CONCLUSIONS
This paper proposed a distributive, light-weight, and efficient algorithm to detect Sybil nodes in mobile wireless sensor networks.
In this algorithm, during different time periods, observer nodes store the occurrences of other nodes in a vector called history.
In order to detect Sybil nodes, observer nodes cooperate and identify Sybil node IDs based on the content of history vectors.
The proposed algorithm was simulated and its performance was compared with that of other algorithms .
, 10, 15, 16, 21, and .
by conducting a set of experiments.
Experiment results indicate the desirable performance of the reposed algorithm regarding detection rate and false detection rate.
REFERENCES