Using of Learning Automata in Sybil Attack Detection and Reduces Errors of Detection Sybil Attack in Wireless Sensor Networks
A.Sarmast1, M. R. Meybodi2
1Department of Computer Engineering, Islamic Azad University, Science and Research Branch,Dezful, Iran
2Computer Engineering and IT Department, Amirkabir University of Technology, Tehran, Iran
Institute for Studies in Theoretical Physics and Mathematics (IPM), School of Computer Science, Tehran, Iran
Abstract
Wireless sensor networks, consist a set of sensors with the limited resources (processing power, receive power and data transmission) ,to collecting information in environments such as military surveillance and forest fire monitoring. In these networks different security attacks occur and that why using security procedures and attack detection consideration has been taken. One of these attacks is Sybil attack in which malicious node which forges a large number of fake identities in order to disrupt the network’s protocols. . This article provides a way in order to detect malicious nodes that by using of learning automata identify nodes to detect attacks that first, Operation Sybil attack detection correctly done and secondly, detection errors that leading to incorrect selection Sybil nodes to a minimum reach. In order to implement and to evaluate the proposed algorithm we use J-SIM simulator. Simulation results and analytical model shows that the proposed algorithm fully diagnosed the attack and error rate of attack detection is very low.
Keywords: Sybil attack detection, learning automata, network security, wireless sensor networks
1. Introduction
Wireless sensor networks in recent years,by many researchers have been considered. These networks includes a set of sensors with limited resources that are in unattended environments such as military or medical environment to monitor performance environments[1]. The autonomous operation of networks and their limited resources has caused widespread and diverse attacks against these networks. One of these attacks is Sybil attack in which malicious nodes producing fake IDs or by using ID authorized network nodes attempting to send information. In fact, from a same physical location by several ID, send are done and recipient of this package assume that the sent packages from different locations and physical identity have been sent. With this attack, attackers can control part or take in the whole network. Sybil attack cause failure in many network protocols, such as data aggregation, voting, fair resources allocation and miss behavior detection [2]. This article introduces a method for detecting the Sybil attack by using learning automata. In this approach, the sensor nodes using its learning automata learn that choose nodes participate in diagnosis that first actively participates in the Sybil attack detection and secondly cause to reduce Sybil attack errors. In order to implement and proposed algorithm simulation we use the J-SIM simulator[7]. Our Evaluation criteria are attack detection rate and error rate of attack detection.
2. Related work
In [4] for the first time review the Sybil attack and expression was that peer to peer systems due to distributed nature of these networks this probability is very high that the sensor nodes can act with several fake identities to introduce themselves to the network. In [6] was expressed that wireless sensor networks because of a distributed and unreliable environment, so influenced of Sybil attack. To defend against this attack also using of cryptography keys and nodes authentication mechanism has been suggested that because of sensor nodes restriction limited in storage and computational resources, is not suitable and from the other direction use of encryption keys can not always detect and prevent attacks cause of Sybil. In [2] some algorithms are proposed in order to mitigate this attack, Such as Radio Resource testing methods. In this method is assumed that each node in network can not through more than one radio channel simultaneously send. In order to Sybil attack detection, nodes that perform attack detection, to each near node allocate unique channel and they will send acknowledgement in specified time. Then attack detector randomly listens to channel of nodes and waiting for Ack massage. If Ack massage of selected channel not received in given time, detector of attack guess desired node that not sends Ack massage is Sybil node. The reason is malicious node that does Sybil attack, can not simultaneously with fake ID’s send massage. Problem of this method is that requires many resources for allocation separated channel and on the other hand, increase sending massage in network. In other method that explained in article is random key pre-distribution that sink node pre distribute randomly number keys(k) to each node from one key pool which consist of m keys. In this method The number, m, is chosen such that two nodes will share at least one key with some probability after they pick their keys. The identity of the node is then combined with the particular set of keys which it chooses. In this way, any node can be authenticated by verifying some or all of the keys which it claims to possess. Another method based on fingerprint to authentication of network nodes in [3] is proposed where each sensor consist of one fingerprint that according information is calculated. Each sensor node has a social fingerprint which is computed based on the neighborhood information through superimposed s-disjunct code. A malicious node cannot have the valid social fingerprint of other neighborhoods or communities which the originate node does not belong to. If the malicious node pretend to be the members of other communities and transmit messages to the other members, the fingerprint inconsistency will occur. The legitimate nodes will raise an alarm to the sink and sink remove it from network. In [5, 8] there are methods to confront Sybil attack where use received signal strength indicator in order to detect the Sybil attack. In these methods recipient node of data packet, save the received signal strength rate of receiver node with node ID in table. If packet receives to same received signal strength and different ID, it detected invalid and is Sybil attack. In [8] this method presented by using of jakes channel model and it is based on sensor network with clustering structure that attention to impact of error due to fading and path loss in communication signal. In [9] a method to detect of Sybil attack is presented where gather paths information by swarm intelligence during network activity and Sybil node using energy changes during activity in network is identified.
3. Learning Automata
Learning automata is an abstract model which randomly selects one action out of its finite set of actions and performs it on a random environment[11,12].Environment then evaluates the selected action and responses to the automata with a reinforcement signal.Based on selected action, and received signal, the automata updates its internal state and selects its next action. Figure 1 depicts the relationship between an automata and its environment. Environment can be defined by the triple E≡α,β,c where α≡α1,α2,…,αr represents a finite input set,β1,β2,…,βmrepresents the outputset, and c≡c1,c2,…,cris a set of penalty probabilities, where each element ci of c corresponds to one input action αi . Environments in which β can take only binary values 0 or 1 are referred to as P -models. A further generalization of the environment allows finite output sets with more than two elements that take values in the interval [0, 1]. Such an environment is referred to as Q-model. Finally, when the output of the environment is a continuous random variable which assumes values in the interval [0, 1], it is referred to as an S-model. Learning automata are classified into fixed-structure stochastic, and variablestructure stochastic. In the following, we consider only variable-structure automata.A variable-structure automata is defined by the quadruple α,β,p,T in which α≡α1,α2,…,αr represents the action set of the automata, β≡β1,β2,…,βm represents the input set, p≡p1,p2,…,pr represents the action probability set, and finally pn+1=αn,βn,pn represents the learning algorithm. This automata operates as follows. Based on the action probability set p,automata randomly selects an action αi , and performs it on the environment. After receiving the environment's reinforcement signal, automaton updates its action probability set based on equation (1) for favorable responses, and equation (2) for unfavorable ones.
P_i (n+1) P_i (n)a[1-P_i (n) ]
(1)
P_j (n+1)=(1-a) P_j (n) ∀j j≠i
P_i (n+1)=(1-b) P_i (n)
(2)
P_j (n)=(b/(r-1))+(1-b) P_j (n) ∀j≠i
In these two equations, a and b are reward and penalty parameters respectively. For a = b, learning algorithm is called LR−P[1], for a < b, it is called LRεP[2], and for b = 0, it is called LR−I[3].
4. Network model and assumptions
Large number of sensor nodes is distributed with a static environment. Network model ishomogeneousand all sensor nodes have the same and limited resources. Only the sink node has unlimited resources. Communications network is done as a multhop. sink node not affected by adversary.
5. Proposed algorithm
Channel model used in this article is jakeschannel [15].in this model the received signal strength indicator in receiver show withRSSIr based on the relationship (3) can be expressed.
RSSIr=RSSIt×Gchda=10logPr×Gchda (3)
In this relation, RSSIt is same as Received Signal Strength Indicator, Pr received signal power, Gch channel gain, d node distance of transmitter and receptor and a is is distance-power descending. Model of Sybil attack in this paper referring to the categories in [2] based on direct attack, and is according fake ID’s so that malicious node producing fake ID’s from one place send information to network authorizednode, and so pretend to ID’s belonged to nodes in different places. We assume an initial set of nodes that are not sybil node. new nodes are introduced some of which can be sybil. New nodes may be arriving to the network also due to topology-control and sleep-wake up protocols [5]. Some of these new nodes may be sybil. Note that sybil nodes can vary their transmission power between transmissions to trick other nodes.
5.1. Detection of Sybil attack
First the network area as a virtual grid is considered. Square cells dimension so selected that nodes in cells as a Community of Attack Detection(CAD) are considered. Length side of cells must so selected that distance maximum among two nodes in cell is equal m(Transmission range of each node). Figure 1 show, How to implement a virtual grid in network and distance maximum of each node in CAD. According to this figure, cell side length and Transmission range of each node is written as relation (4) that (t) is Cell side length parameter.
Figure.1. Network area with 5×5 virtual grid dimensions
m2=(t)2+(t)2⇒t=m2 (4)
With this assumption that before data sent step and network setup time, there is not the possibility of adversary physical access to network and network nodes and no possibility of attack event[18]. Regard to tinit as network setup time, nodes are set timer so called Tset. With this requirement that (tinit tset), in time tset, each nodes based on location know the CAD number. Each node sending broadcast massage, containing its location and CAD number, to near nodes, nodes build table so called LCHK, each record from LCHK table of node is related to node data within the community. Fields in this table include geographic coordinates of the desired node, intended node ID, node energy and amount RSSI receive of node, so based on received data of node. Each node knows the CAD nodes in tset time and saves in L list. After determination of desired list, node with highest energy level in CAD, selected as master node in Sybil attack detection, that so called PRX1 . This node is equipped to learning automata that number of actions of this automata equal to members of CAD, that each action of in automata correspond with CAD member. After end time test, randomly one of automata action is selected. in order to choose learning automata actions,probability vector determine by relation(5). In this term, n number of list member and i number of learning automata actions. Selected node with learning automata called PRX2.
∀i i≤n Pi=1n (5)
Choice of PRX1 is such that select randomly participate detector of Sybil attack. It is proved that theoretically, there are at least 4 node to detct of Sybil attack based on received RSSI from data packet is required and actually two differential node is enough. All of existing nodes in L list, has duties received RSSI of each packet that obtained from node in its cell and Compare with existing RSSI in LCHK table. This comparison because of that if massages sending to faked ID’s with malicious node, if equality of faked ID with valid ID attack can be detected. But only PRX1 and PRX2 actively participate in attack detection. In order to detect attack in term that faked ID with malicious node randomly are different from network valid ID’s, we use ratio values of received RSSI in differential nodes. It is because of attack detection in term that Sybil node with different powers with each ID, can be proceed of sending data.
Figure.2.two node detector PRX1 and PRX2 and sybil node with two fake ID’s s1 and s2
In Fig2,first sybil node that is in communication range of PRX1 and PRX2,broadcast message using by s1 identity.RSSI value received from this message associated with node ID of sybil node recorded in LCHK table by both attack detector.then PRX2 sends this values to PRX1.after Sybil node broadcast another message using by S2 identity,PRX2 sends this values from S2 to PRX1 again.in this situation PRX1 can be detection Sybil attack using by relation(6).
RSSIPRX1S1RSSIPRX2S1=RSSIPRX1S2RSSIPRX2S2 (6)
In this relation RSSIji is amount of receiving RSSI from node i by nodes j , If both side of relation (6) is equal and lack of error in detect action of attack Sybil detect that , we studyit in next section , ID’s S1 and S2 detect as a forge ID’s and detect the Sybil attack is done . In this situation node PRX1 send Sybil node ID’s to its member CAD. Member nodes, inform existing of Sybil ID’s , with sending broadcast massages to next nodes that locate on next CADs . Then PRX1 reward Corresponding action with proposal node automata and choose this node again as a attack detector and remove node Sybil IDs from list. And if error occur in attack detection by PRX2, penalty corresponding action with it and will be select another node randomly. This work continue so that nodes give more reward duration a time take apart by more probability as a detector node. In fact node PRX 1 was learns by own learning automata to select some nodes for doing sybil attack detection action with the least attack detection errors.