基于核Fisher判别分析的无线传感器网络入侵检测算法*

胡志鹏，魏立线* ，申军伟，杨晓元，2

(1．武警工程学院电子技术系网络与信息安全武警部队重点实验室，西安710086;2．西安电子科技大学网络信息安全教育部重点实验室，西安710071)

无线传感器网络(WSN)是由部署在检测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织网络系统，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并以无线通信的方式发送给观察者。无线传感器网络应用极其广泛，可用于军事侦查、环境监测和医疗卫生等众多领域［1］。

无线传感器网络一般部署在无人值守的环境中，网络部署区域的开放特性和无线通信的广播特性给网络带来了极大的安全隐患［2－3］。尽管对传统网络入侵检测技术的研究已较为成熟，但是由于无线传感器节点资源(如电源能量、通信能力和计算能力等)严重受限，使得传统网络中各种入侵检测技术无法运用在无线传感器网络中。

目前针对无线传感器网络入侵检测提出了不少方法，常见的方法包括以下几种。Denning［4］提出了五种统计分析方法，其中常用的有操作模型和基于马尔科夫模型。操作模型主要针对系统中事件计数进行度量，当需要进行分析的某个参数超过阈值的时候，就认为发生了异常。基于马尔科夫模型将不同类型的事件定义为状态变量，并用状态转移矩阵描述状态之间的转移概率。该模型可以发现异常的用户命令和事件序列，而不仅仅局限于单个事件，它研究的对象往往是一些离散的事件流。Wenke Lee研究组和Stephanie Forrest研究组［5］主要是使用数据挖掘的分析方法，采用人工智能、机器学习等技术高度自动化的分析原有的数据，做出归纳性的推理，并从中挖掘出潜在的模式，预测出行为。除了以上检测方法外，还有利用神经网络、优先状态自动机、计算机免疫系统和基于代理等技术进行无线传感器网络的入侵检测［6］。

本文提出了一种基于核Fisher判别分析的无线传感器网络入侵检测算法，利用核Fisher判别分析对比传感器节点数据和已建立的入侵行为特征来判断是否存在入侵行为。实验表明:本算法具有较低的误报率和较高的检测精度，同时也能降低检测节点的能量消耗。

1 无线传感器网络入侵检测模型

本文中的无线传感器网络模型是一个被均匀的部署在某区域的无线传感器网络。这个网络可以划分为若干个簇。每个簇内的节点又可以划分为簇头节点和普通节点，簇头节点负责协调和控制簇内节点及其数据的融合，同时还要负责和Sink节点的通信。该网络模型如图1所示。

图1 网络结构

其中Sink节点不受电量、存储空间和计算能力等的限制，可以单独运行一套复杂的入侵检测算法。由于该节点收集的信息比其它节点收集的信息要完整和全面的多，所以它能够更容易的检测出网络中存在的入侵行为。一旦Sink节点检测出网络的异常行为，就会通过消息通知相应的簇头节点，簇头节点在收到来自Sink节点的消息后，会将此消息在簇内进行广播，这样簇内所有的节点就都会收到参数调整的消息，之后簇内入侵检测算法的参数就会得到相应的调整，检测节点就会用新的参数进行检测。

每一个簇内包含N个节点作为入侵检测节点，如果一个簇内负责检测入侵行为的节点中有超过R个节点认为某一个节点是入侵节点，本算法就认定此节点为入侵节点。可以将入侵节点的密钥注销，或在路由表中将其删除［7］。具体流程如图2所示。

图2 入侵检测流程图

2 无线传感器网络入侵检测算法

2．1 无线传感器网络中存在的入侵行为

检测节点可以收集表1中所列出的各种信息以便检测各种类型的网络入侵行为［8］。

表1 检测信息

通过对每个检测节点监测到的数据进行对比，就可以发现入侵行为，比如说，黑洞攻击就是无条件丢弃数据包，导致与其通信的节点在不停地进行重传，以达到耗尽与其通信节点能量的目的，所以监测丢包率可以判断是否发生了这类攻击。

2．2 核Fisher判别分析原理

假设节点Xi上的多个网络属性形成一个d维的向量，d为被监视属性的个数。一个簇内进行监测的节点的个数为n，其中n1个属于收集到的正常工作节点ω1类的样本记为个属于一种入侵节点ω2类的样本记为。如果能正确区分正常通信节点与入侵节点的数据，就能够实现对入侵行为的检测。

核Fisher线性判别就是一种能够实现对数据分类的算法，该算法需要解决的问题是找到一个最好的投影方向(如图3)，使样本在这个方向上的投影能最容易分开［8］。

图3 核Fisher线性判别的基本原理

寻找最好投影方向的问题，就是最大化广义Rayleigh商:

分别是样本的类间散度矩阵和类内散度矩阵，而mi是各类样本的均值向量，即

因此最大化J(ω)的本质是要找到一个最好的方向来最大化投影后的类间散度，同时最小化这个方向上的类内散度。

首先通过非线性映射，将输入数据映射到一个高维特征空间中。设φ是输入空间到某个特征空间F的非线性映射，要找到F中的线性判别需要最大化

这里ω∈F，Sb和Sw是F中相应类间散度矩阵和类内散度矩阵，即

其中

通常F的维数很高，不能直接求解。因此使用非线性支持向量机的核方法。这种方法是寻找算法的一种表达式，仅仅计算训练样本的点积运算，就能够解决由于维数太高而无法计算的问题。通过使用Mercer核函数来实现，这些核函数k(x，y)计算了某个特征空间 F的点积运算，即 k(x，y)=(φ(x)，φ(y))。本文使用RBF核函数

为了找到特征空间F的Fisher判别，首先得到按照输入样本的点积形式表示式(3)的表达式，然后用某个核函数来替代其中的点积运算。根据再生核理论，F空间的任何解ωφ都是F空间中的训练样本的线性组合，即

利用展开式(6)和式(7)，并用核函数代替点积，于是有

式(3)中分子，利用式(4)和式(8)，可写为

其中 M=(M1－M2)(M1－M2)T。

式(3)中分母，利用式(6)、式(7)及式(9)中的变换，得到

I是单位矩阵，Yi是所有元素为1/nj的矩阵。

将式(9)和式(10)代入式(3)，得到特征空间F的核Fisher判别分析，即最大化

求解可以通过求矩阵N－1M的特征值和特征向量就可求得上式的最优解。

x到ω投影为

在实际应用中为了防止N非正定，可以给N加上一个单位阵的倍数，即用矩阵Nμ代替矩阵N

I是单位矩阵。

2．3 基于二叉树的KFDA多分类方法

由于核Fisher判别方法是针对二分类的情况，对于多分类的情况，可以将多类问题分解为多个二分类问题，本文使用二叉树方法，每个分类器可以将一类数据的样本分开。具体地说，就是在一个k类分类问题中，先将k类问题进行排序，将第1类与第2…k类样本进行训练，作为第1个分类器，然后将第2类与第3…k类样本进行训练，作为第2个分类器，最后直到把k类数据分开。以4类分类问题为例，多类分类的二叉树结构如图4所示［9］。

图4 4分类KFDA二叉树结构

3 仿真实验

使用MATLAB2010b和NS2为仿真实验平台，实验用数据来自KDDCup99网络入侵检测数据集。KDDCup99是国际上最权威的入侵检测测试数据集［10］。

3．1 实验数据处理

KDDCup99数据集中包含了多种攻击方式，主要可以分为4大类攻击数据，Probe、Dos、U2R和R2L，还包含了正常通信的数据，因此可以用这5类数据进行实验。

由于 Spoofed、Altered、Replayed Routing Information、Sinkhole、Sybil、Wormholes、Acknowledgment Spoofing这几种攻击在入侵前要进行探测，所以把它们归为Probe攻击;Sinkhole、Wormholes and Hello Floods归为U2R 攻击，Spoofed、Replayed Routing Information、Sinkhole、Hello Floods这几种攻击是针对系统缺陷进行攻击，把它们归为R2L攻击，还有DOS攻击［11］。

传统的网络入侵检测算法很多，几乎任何一种分类方法都可以应用其中，如果采用传统的网络入侵检测算法，则需要检测节点单独运行一套完整的分类算法。因为无线传感器网络中的节点能量有限、计算能力有限，所以大多算法不能很好的应用其中。就是针对传感器的这个特点，才使用了核Fisher判别分析方法。

本算法最大的优点是将整个计算过程和通信耗能都分为两个部分，使绝大部分计算和通信能耗都集中在了资源不受限制的Sink节点，这样就大大减少了检测节点的负担。在计算方面，首先令Sink节点对数据进行特征提取，即使用核Fisher判别方法，计算出最优方向ω∈F，ω的计算量对于无线传感器网络中普通节点来说是较为巨大的，本文将ω的计算交给计算能力不受限制的Sink节点处理，把Sink节点计算出的ω广播给簇内各检测节点，网络中检测节点只需要将收集到的各个节点的数据利用式(12)计算出样本在ω方向上的投影，然后利用这些投影点进行分类，由于得到的投影是一维模式，所以只需要找到一个合适的阈值即可分类。进行上述处理就把分类器的计算拆分为了两个部分:(1)计算ω;(2)计算ω方向上的投影并分类。而检测节点只需要做第2个部分的计算，因此大大减少了检测节点的计算量。在通信能耗方面，通信能量主要是被发送信号所消耗，而接收信号所需能量是发送信号能耗的三分之一，这样就使得通信中的能量消耗由资源不受限的Sink节点承担。从而又大大减少了检测节点的通信耗能。

3．2 性能测试

首先将核Fisher判别方法仿真实验，然后将其检测结果与BP网络、SVM方法进行对比。四类攻击分别使用核Fisher判别方法、BP网络、SVM［12］进行处理后的检测率和误检测率如表2所示。

表2 检测率与误检率

通过实验结果对比，可以看出本方案在检测精度上明显高于BP网络、和SVM。通过实验结果分析，对于Probe攻击、R2L攻击、DOS攻击可以有效检测，并且误检率很低，但是对于U2R攻击，3种方法的检测率都普遍较低，并且误检率很高，主要原因是由于U2R类型攻击样本较少，分类器训练不足，导致检测率不高。可见训练样本对检测较果起着至关重要的作用。

3．3 检测平均能量

为了评估节点的平均能量开销，统计了无攻击无检测、无攻击有检测和有攻击无检测这3种情况下的能耗。因为算法中大部分计算在资源不受限制的Sink节点中进行，所以，当检测节点运行入侵检测算法时，通信增加的能耗要远大于计算增加的能耗。因此在讨论能耗问题时只考虑检测过程中的通信能耗。Chndrakasan［13－14］提出了一种能量消耗模型:

传感器节点发送k比特数据所消耗的能量为

传感器节点接收k比特数据所消耗的能量为

其中εamp是信号放大器的放大倍数，Estatic是发送电路和接收电路的能耗，d是信号的发送距离。

通过仿真实验，入侵检测系统耗能如图5所示。

图5 能量消耗

从图5中可以看出，在系统运行的初期，耗能比较大，这是由于系统要提取特征，建立特征库，并将特征向量广播给检测节点。经过一段时间后，能耗降低，这是因为系统进入检测阶段，通信开销减少。但是以后每经过一个时间段，节点就会出现一个耗能高峰，这是因为经过一段时间，系统需要重新收集信息、建立特征库、并广播特征向量。因为整个算法中，绝大部分计算集中于资源不受限制的Sink节点。现有的方案都将整个入侵检测算法集中在检测节点上，造成检测计算量过大。通信能耗仅是接收特征向量，而特征向量仅仅是一个N维数组，数据量极小，所以通信耗能也保持在一个较低水平。这样就大大增加了无线传感器网络的寿命，检测算法能在高检测率的同时保持相对较低的能耗。

4 结论

本文针对无线传感器网络自身的特点，将核Fisher判别分析运用到无线传感器网络入侵检测，提出了一种高效的入侵检测算法，能够有效的检测出入侵行为，并具有较低的能耗。实验表明，该算法最大的优点是检测率高，检测节点能耗低。但是对于U2R类攻击本算法检测率较低，对于篡改攻击，伪造攻击还未能检测。因此，如何对U2R攻击方式进行有效的检测是下一步研究工作的重点。

［1］ Akyildiz I F，Su W，Sankarasubramaniam Y，et al．Wireless Sensor Network:A Survey on Sensor Network［J］．IEEE Communications Magazine，2002，40(8):102－114．

［2］ 王颖，李国瑞．基于分组的无线传感器网络入侵检测方案［J］．传感技术学报，2007，20(3):677－681．

［3］ 王培，周贤伟，覃伯平．基于多代理的无线传感器网络入侵检测系统研究［J］．传感技术学报，2009，22(6):878－882．

［4］ Denning D．EAn Intrusion Detection Model．IEEE Transactions on Software Engineering［J］．1987，13(2):222－232．

［5］ Lee W，Stolfo S J，Mok K W．Adaptive Intrusion Detection:A Data Mining Approach．Artificial Intelligence Review［J］．2002，14:533－567．

［6］ 刘帅．无线传感器网络中能量有效的入侵检测研究［D］．湖南大学硕士学位论文，2007:15－41．

［7］ 邢利．无线传感器网络入侵检测方法的研究［D］．北京工业大学硕士学位论文，2009:13－44．

［8］ Li Guorui．A Distributed Intrusion Detection Scheme for Wireless Sensor Networks［J］．IEEE DOI10．1109/ICDCS．Workshops．2008．191545－0678/08:310－314．

［9］ 李映，李焦成．基于核Fisher判别分析的目标识别［J］．西安电子科技大学学报(自然科学版)2003，14(4):179－181．

［10］ Downard I．Simulating Sensor Networks in NS－2［J］．Technical Report NRL/FR/5522－04－10073，Naval Research Laboratory，Washington，D．C．U．S．A．，May 2004．1－5．

［11］祝琦，宋如顺，姚永仙．无线传感器网络中基于SVM的合作型入侵检测系统［J］．计算机应用研究，2010，27(4):1489－1492．

［12］陈俊丽，焦李成．支撑矢量机的分类机理研究［J］．西安电子科技大学学报，2000，27(SUP):106－110．

［13］ Yan K Q，Wang S C，Liu C W．A Hybrid Intrusion Detection System of Cluster-based Wireless Sensor Networks［C］//Proceedings of the International Multi Conference of Engineers and Computer Scientists，2009，1:978－986．

［14］ Heinzelman W B，Chndrakasan A P，Balakrishnan H．An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］．IEEE Transaction on Wireless Coinmunications，2002，1(4):660－670．