An Instance⁃Learning⁃Based Intrusion⁃Detection System for Wireless Sensor Networks

Shuai Fu，Xiaoyan Wang，and Jie Li

（1.Department of Computer Science，University of Tsukuba，Tsukuba，Japan；2.Information Systems Architecture Science Research Division，National Institute of Informatics，Tokyo，Japan）

An Instance⁃Learning⁃Based Intrusion⁃Detection System for Wireless Sensor Networks

Shuai Fu1，Xiaoyan Wang2，and Jie Li1

（1.Department of Computer Science，University of Tsukuba，Tsukuba，Japan；2.Information Systems Architecture Science Research Division，National Institute of Informatics，Tokyo，Japan）

This paper proposes an instance⁃learning⁃based intrusion⁃detection system（IL⁃IDS）for wireless sensor networks（WSNs）.The goal of the proposed system is to detect routing attacks on a WSN.Taking an existing instance⁃learning algorithm for wired networks as our basis，we propose IL⁃IDS for handling routing security problems in a WSN.Attacks on a routing protocol for a WSN include black hole attack and sinkhole attack.The basic idea of our system is to differentiate the changes between secure instances and attack instances.Considering the limited resources of sensor nodes，the existing algorithm cannot be used directly in a WSN.Our system mainly comprises four parts：feature vector selection，threshold selection，instance data processing，and instance determina⁃tion.We create a feature vector form composed of the attributes that changes obviously when an attack occurs within the network. For the data processing in resource⁃constrained sensor nodes，we propose a data⁃reduction scheme based on the clustering algo⁃rithm.For instance determination，we provide a threshold⁃selection scheme and describe the concrete⁃instance⁃determination mechanism of the system.Finally，we simulate and evaluate the proposed IL⁃IDS for different types of attacks.

WSN；security；intrusion⁃detection system；instance learning；black hole

1 Introduction

W ireless sensor networks（WSNs）contain a num⁃ber of distributed sensors that are constrained in terms of energy，memory，computation，and bandwidth（PCs）.The development of WSNs was motivated by military applications，such as battlefield sur⁃veillance.Now，WSNs are widely used for industrial and civil⁃ian applications，including industrial process monitoring and control，machine health monitoring，and environment and habi⁃tat monitoring.

As WSNs have developed，security problems in WSNs have attracted more and more attention.Currently，most research on these problems is focused on prevention mechanisms，such as secure routing protocols，cryptography，and authentication. Such meechanisms are usually the first line of defense；howev⁃er，because of the particularities of WSNs，we cannot rely on intrusion⁃prevention techniques alone.In practical situations，intrusion⁃detection systems are needed to detect both known security exploits and novel attacks that have not yet been expe⁃rienced.

Intrusion⁃detection is the process of identifying activities that violate the security policy of the system［1］.Such tech⁃ niques are traditionally categorized as anomaly detection and misuse detection.Anomaly detection is based on the normal behavior of the subject；any action that significantly deviates from this normal behavior is considered intrusive.Misuse de⁃tection catches intrusions in terms of the characteristics of known attacks or system vulnerabilities.Any action that con⁃forms to the pattern of a known attack or vulnerability is con⁃sidered intrusive［2］.

There are many intrusion⁃detection algorithms，but few of them are designed for WSNs.We propose an instance learning⁃based intrusion⁃detection system（IL⁃IDS）based on an existing instance⁃based learning algorithm［3］for a wireless sensor net⁃works.

2 Related Works

Our proposed intrusion⁃detection system is mainly designed for routing security in a WSN.In this section，we introduce sev⁃eral kinds of attack against a WSN and summarize related works on intrusion⁃detection systems for WSNs.

2.1 Routing Attacks on a Wireless Sensor Network

Before describing intrusion⁃detection algorithms，it is neces⁃sary to introduce several kinds of routing attack on a WSN. Such attacks include bogus routing information，selective⁃for⁃warding，sinkhole attack，Sybil attack，worm hole attack，and hello flood attack（Table 1）.

▼Table 1.Types of routing attack on a WSN

2.2 Intrusion Detection for a WSN

The intrusion⁃detection system designed by C.E.Loo et al. is based on a fixed⁃width clustering algorithm［4］.The audit da⁃ta is divided into different clusters with fixed widths.The au⁃thors assume that less than y%of the data consists of abnormal traffic samples and label the cluster normal or anomalous ac⁃cording to the point number of the cluster.Then，the authors decide whether newly observed data is normal or not by com⁃puting the distance to the cluster.

The other work is an intrusion⁃detection system designed by K.Ioannis et al.［5］.The authors use each node in the WSN to monitor whether its neighbors forward messages received from it.Looking at the transmission rate，the authors can determine which nodes are compromised.However，this kind of approach only focuses on selective⁃forwarding attacks and black hole at⁃tacks.

3 System Design

We propose an IL⁃IDS based on an existing instance⁃learn⁃ing algorithm.Because of resource constraints in terms of ener⁃gy，memory，computational speed，and bandwidth in a WSN，we modify the algorithm to make it suitable for the WSN.Here，we describe the four aspects of the algorithm：

·feature vector selection.This involves constructing feature vectors that show the network state.An obvious change in the feature vector means that an attack is occuring in the network.

·threshold selection.This involves determining the threshold r used to label instances as normal or not.

·Instance data processing.This involves collecting instance data and reducing instance samples for WSNs.

·Intrusion⁃detection process.This involves using the con⁃ crete processes from data collection to determine whether a newly observed instance is normal or not.

3.1 Feature Vector Selection

Constructing the sequence of feature vectors is an important issue.Feature vectors need to be designed so that they change obviously when an attack occurs.The feature vector we select⁃ed is shown in Table 2.

The features are classified as traffic⁃related or non⁃traffic⁃re⁃lated.Traffic⁃related features describe conditions of the traffic flow through the node，and non⁃traffic⁃related features de⁃scribe the routing conditions of the sensor node.From the defi⁃nition of similarity，the two adjacent features interact with each other.

The ten features in Table 1 correspond to the feature vector X=（x0，x1，...，x9）.If behavior is abnormal，the attributes of fe⁃ature vector change obviously.

In the instance⁃based learning algorithm，a change in the feature vector means the similarity becomes less than normal. In addition，by computing the similarity between normal data and abnormal data，we can infer whether a new instance repre⁃sents abnormal behavior.

3.2 Threshold Selection

Selecting the threshold r requires a judgment to be made on whether the feature vector is normal or abnormal.Furthermore，determination of r depends on the tolerance of the routing pro⁃tocol to errors and attacks.From simulation，we obtained many data samples and found that they followed a normal distribu⁃tion.The threshold can be determined by a confidence level. In simulation，we made r to be 0.05.If the difference between the similarity and maximum similarity is greater than r，the ob⁃served instance is different from the sample instance.It is nec⁃essary to verify r through simulation.

3.3 Instance Data Processing

First，we count the attributes in Table 1 every fixed interval T and obtain the results as feature vectors.From experiments，we obtain the data sequences D.However，this creates a prob⁃lem because we cannot store all the audit data in the sensor—its memory is too small.The instances of data processing is on⁃ly the data reduction；therefore，we use a clustering algorithm to reduce the number of samples and only use several instanc⁃es to represent all of them.The data reduction can be divided into two parts：adding instances into clusters and updating the centers of clusters.

▼Table 2.Make⁃up of the feature vector

In Algorithm1，we have an instance collection D｛Y1，Y2，...，Yn｝，where Y is a sample of a feature vector and Yi=＜y1，y2，...，yl＞.We randomly choose several instances to be the centroids of the clusters in D.These centroids have the smallest mean distance to all the other instances in the cluster and form a centroid collection Cen｛C1，C2，...，Cm｝.Our aim is to represent all instances by the centroid collection.

After creating the centroid collection，we add each instance into the clusters by computing the distance to the centroid of the cluster and finding DistanceCen（Yi）， where DistanceCen（Yi）=minC∈Cen｛Distance（Yi，Ci）｝.Each instance should belong to the cluster with the shortest distance between the instance and its centroid.

Algorithm 1：Instance Collection

Input：Instances collection D｛Y1，Y2，...，Yn｝，where Yi=＜y1，y2，...，yl＞

Randomly choose minstances in D get the collection of centroids Cen｛C1，C2，...，Cm｝；

Where Cirepresents the centroid of clusteri｛Ci｝；

The number of instances in clusteri：mi；

The radius of clusteri：Ri；

while Di≠Φdo

Then we update the centroid and radius of the cluster.If there is only one instance in the cluster，the new radius is the distance between the two instances.Otherwise，we compute the distance between every two instances in the cluster and make the instance that is the closest mean distance to all other instances in the cluster the new centroid.We do this until all the instances are added to clusters.

3.4 Intrusion-Detection Process

Intrusion detection can be divided into two steps：1）data col⁃lection and processing and 2）instance determination.Each sensor node can count the values of parameters in the feature vector.For each node in T，we obtain a sample of the feature vector.Over time，each node can collect and process a mass of instance data.This data is processed in three steps：

1）Data is transmitted to the base station.

2）The base station clusters the data according to Algorithm 1.

3）The centroid collection is stored in each sensor node.

After audit data is processed and stored，we monitor the re⁃lated data in each T and obtain a new observed feature vector. Then，we compute Sim（X，Dcent）and Dist（X，Dcent）.If Dist（X，Dcent）is greater than the radius of the centroid collec⁃tion，X is abnormal；otherwise，we compare Sim（X，Dcent）with r.If Sim（X，Dcent）＞r，then X is normal.The system described above is shown in Fig.1.

4 Performance Evaluation

4.1 Parameter Settings

As shown in Table 3，we set 300 nodes randomly distribut⁃ed over 500×500 m2.These nodes included one base station and one compromised node.The compromised node generated a black hole and affected the nodes near it.The sensor nodes used the Constant Bit Rate（CBR）transport protocol and theAd hoc On⁃Demand Distance Vector（AODV）routing protocol. The movement of all nodes except the base station was random⁃ly generated.

▼Table 3.Parameter settings

4.2 Performance Metrics

In the simulation，we used three metrics to evaluate system performance and the usability of the algorithm in the WSN：1）similarity of observed instances，2）number of packets received every interval，and 3）rate of intrusion detection.We defined the similarity between two instances.The smaller the similari⁃ty，the more possible it was that an observed instance was as an attack.The number of packets received is the most impor⁃tant characteristic in feature vectors for a black hole attack. The more obviously the number of packets received changes，the greater the possibly a black hole attack is occurring in the WSN.Then we reviewed the rate of the intrusion⁃detection sys⁃tem during a black hole attack or sinkhole attack.

4.3 Simulation Results

We simulated two kinds of attack against a WSN：black hole and sinkhole.

4.3.1 Black Hole Attack

In a selective⁃forwarding attack，malicious nodes may refuse to forward certain messages and simply drop them（black hole），which means that they are not propagated any further.For ex⁃ample，a malicious node behaves like a black hole and refuses to forward every packet it sees.We instigate a black hole at⁃tack in a WSN by making the malicious node drop packets. The impact on the sensor network was not obvious；only the number of packets received by the neighbor of the malicious node was reduced（Fig.2）.Table 4 shows one node’s feature vectors for secure and attack scenarios.If there is a black hole node near the observed node，the number of data packets re⁃ceived decreases because the malicious node does not forward any packets and just drops them.

We observe the change of packets received for secure and at⁃tack scenarios.When an attack occurs，the number of packets received changes markedly.

4.3.2 Sinkhole Attack

The main purpose of a sinkhole attack is to lure all traffic from nodes in a region to a compromised node.This is achieved by forging or altering route packet information to make a compromised node look very attractive to the routing al⁃gorithm.Neighboring nodes assume that the compromised node is the best path to their destinations.A sinkhole attack can also be a platform for other attacks，e.g.，a selective⁃for⁃warding attack［6］.Because all the traffic flows through the compromised node，a selective⁃forwarding attack is more effec⁃tive and easier to launch.

We simulated a sinkhole attack in the malicious node，which broadcasted high⁃quality routing packets in order to at⁃tract its neighbor.The effect increased when combined with a sink hole based on a black hole.

Fig.3 shows the result of 75 attacking instances under sink hole attack.Fig.4 shows that similarity for a sink hole is smaller than that for a black hole attack.

5 Conclusion

In this paper，we propose an IL⁃IDS for WSNs.Because of resource constraints on sensor nodes，the existing intrusion⁃de⁃tection algorithm cannot be directly used in a WSN.Our pro⁃posed IL⁃IDS comprises a feature vector and threshold⁃selec⁃tion scheme，a data⁃reduction method，and a detailed work pro⁃cess of the system.Through simulation，we show that the per⁃formance of our intrusion⁃detection system for black hole at⁃tacks and sinkhole attacks.

▼Table 4.Feature vectors in one node for secure and attack scenarios

［1］P.Ning and S.Jajodia.Intrusion detection techniques［Online］.Available：http：// discovery.csc.ncsu.edu/Courses/csc774⁃S03/IDTechniques.pdf

［2］C.Karl of and D.Wagner，“Secure routing in wireless sensor networks：attacks and countermeasures，”in Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications，Anchorage，AK，USA，2003，pp. 113-127.doi：10.1109/SNPA.2003.1203362.

［3］T.Lane and C.E.Brodley，“Temporal sequence learning and data reduction for anomaly detection，”ACM Transactions on Information and System Security，vol. 2，no.3，pp.295-331.doi：10.1145/322510.322526.

［4］C.E.Loo，M.Y.Ng，C.Leckie，and M.palaniswami，“Intrusion detection for routing attacks in sensor networks，”International Journal of Distributed Sensor Networks，vol.2，no.4，pp.313-332，2006.

［5］K.Ioannis，T.Dimitrou，and F.C Freiling，“Towards intrusion detection in wire⁃less sensor networks，”in 3th European Conference on Wireless Sensor Networks（EWSN’07），Delft，the Netherlands，2007.

［6］Ian F.Akyildiz，W.Su，Y.Sankarasubramaniam，and E.Cayirci，“Wireless sen⁃ sor networks：A survey，”Computer Networks Elsevier Journal，vol.38，no.4，pp. 393-422，2002.

Manuscript received：2015⁃04⁃10

Biographiesphies

Shuai Fu（fs0818@gmail.com）received his MS degree in computer sceince from University of Tsukuba，Japan.He is currently a PhD candidate in the Department of Computer Science，University of Tsukuba.His research interests include security and mobility management in wireless networks.

Xiaoyan Wang（wxyability@hotmail.com）received his BE degree from Beihang Uni⁃versity，China，in 2004.He received his ME and PhD degrees from the University of Tsukuba，Japan，in 2010 and 2013.He is currently assistant professor in the Infor⁃mation Systems Architecture Science Research Division，National Institute of Infor⁃matics，Japan.His research interests include wireless communications and net⁃works，with an emphasis on cognitive radio networks，game theory approaches，and cooperative communications.

Jie Li（lijie@cs.tsukuba.ac.jp）received his BE degree in computer science from Zhejiang University，China.He received his ME degree in electronic engineering and communication systems from China Academy of Posts and Telecommunica⁃tions，Beijing.He received his Dr.Eng.degree from the University of Electro⁃Com⁃munications，Japan.He is currently a profesor in the Department of Engineering，In⁃formation and Systems，University of Tsukuba，Japan.His research interests include mobile distributed computing and networking，network security，mobile cloud com⁃puting，OS，modeling and performance evaluation of information systems.He is a se⁃nior member of IEEE and ACM and a member of Information Processing Society of Japan.He has served as a secretary for Study Group on System Evaluation of IPSJ and has been on several editorial boards of IPSJ journals.He has been on the steer⁃ing committees of the SIG of System EVAluation（EVA）of IPSJ，SIG of DataBase System（DBS）of IPSJ，and SIG of MoBiLe Computing and Ubiquitous Communica⁃tions of IPSJ.He has co⁃chaired several international symposiums and workshops. He has also been in the program committees of several international conferences，in⁃cluding IEEE INFOCOM，IEEE ICDCS，IEEE ICC，IEEE GLOBECOM，and IEEE MASS.

Roundup Call for Papers ZTE Communications Special Issue on Smart City： Key Technologies and Practices

Though the smart city has been one of the hottest fields due to its great potentials to make our world smarter and more efficient with using digital technologies，it is still necessary to clarify what are fundamental infrastructures and platforms as well as successful practices for truly smart cities.Therefore，the ZTE special issue is focused on key technologies and representative practices in building smart cities.We solicit papers in the topics including but not limited to the following：

·Survey/Review of Smart City Technologies and Applications

·Smart City Infrastructures for Sensing，Networking，IoT，Cloud，etc.

·Smart City Platforms for Programming，Big Data Processing，Services，etc.

·Smart City Practices，Cases Studies and Applications

Paper Submissions

Prepare your paper with using the template and following the guideline below.

Template：http：//cis.k.hosei.ac.jp/～jianhua/zte/template.docx

Guideline：http：//cis.k.hosei.ac.jp/～jianhua/zte/guideline.pdf

Send your paper via email attachment to the SI’s editors

Important Dates

Paper Submission Due：August 15，2015

Paper Review Notification：September 10，2015

Semi⁃Final Manuscript Submission：September 30，2015

Final Manuscript Editing and Proofreading：November 15，2015

Paper Publication and Special Issue Printing：December 15，2015

Guest Editors

Jianhua Ma，Hosei University，Japan（Email：jianhua@hosei.ac.jp）

Weifeng Lv，Beihang University，China（Email：lwf@buaa.edu.cn）