基于条件随机场的实时入侵检测系统框架实现

顾佼佼，姜文志，栗 飞，胡文萱

（海军航空工程学院 a.兵器科学与技术系；b.指挥系；c.外训系，山东 烟台 264001）

0 引言

入侵检测就是对入侵计算机和网络资源的行为进行识别和响应的处理过程，预防破坏计算机系统的完整性、机密性及资源的可用性的行为。如今随着信息化进程的不断推进，不断复杂化的网络架构和愈加方便的无线接入对构建有效检测入侵攻击的高效网络入侵检测系统提出了重大挑战。

目前入侵检测主要使用的分析方法有两种[1]：基于签名的方法和基于异常的方法。基于签名的方法是通过在审计模式中搜索已知的入侵模式来检测入侵，这是大部分商业IDS采用的分析方法。基于签名的系统能有效的检测模式库中已有的入侵，搜索到相同的模式并匹配后即可确认攻击，然而，对不在模式库中的入侵行为则无能为力，即便攻击模式中的一点微小变动都有可能导致模式匹配失败。特征库需要不断更新才能够检测出新的攻击，构建成本太高，灵活性和自适应性比较差，系统漏报多。Snort就是基于模式匹配的系统之一。基于异常的方法则可检测未知的攻击方式，它试图检测系统行为的异常模式，其依靠的不是识别产生审计模式的过程而是分析审计模式的属性，这种方法主要是应用数据挖掘及机器学习领域的技术，在实际IDS中应用较少。常用的数据挖掘方法[2]是关联规则，还有基于分类方法和序列标注方法。分类法是研究的最多的一种，常见的有决策树方法、贝叶斯分类[3]、神经网络、回归分析、支持向量机等。序列标记方法有马尔科夫链、隐马尔科夫模型[4]等。

现在网络入侵的手段有多种，攻击方式综合化和复杂化，为了最大限度地提高攻击检测的准确率，现有系统一般采用基于签名和异常方法并存的方式。然而，准确率和效率仍不令人满意。漏报率、误报率高，预警能力差仍是系统的瓶颈所在。

在分析了目前网络入侵检测的困难性基础上，提出应用条件随机场(Conditional Random Fields，CRFs)来对网络入侵进行检测并建立一个层叠CRFs模型来检测入侵的框架。在KDD 1999数据上实验并与其他方法比较表明，此方案优于其他检测方法。

1 条件随机场

1.1 基础

条件随机场模型[5]是近年来提出的一种机器学习方法，用于在给定需要标记的观察序列的条件下，计算整个标注序列的联合概率分布。Lafferty 等人定义CRFs为指数形式分布，这就使得不同状态下的不同特征的权值可以相互平衡。它是由隐马尔科夫模型(Hidden Markov Model，HMM)、最大熵马尔科夫模型(Maximum Entropy Markov Model，MEMM)逐级发展而来，并克服了二者的缺陷。CRFs是一种判别式模型，采用的是无向图分布，没有严格的独立性假设，可以任意选取特征。隐马尔科夫模型是生成模型，它针对联合概率 p (y,x) 建模，在模型中作了若干独立性假设，而条件随机场模型直接对所求的条件概率 p (y|x) 进行建模，在给定观察序列x条件下推导标签序列y，这使得CRFs模型可以避免独立性假设并捕获不同特征之间的关系。而且因为CRFs 采用了全局归一化的方法，避免了最大熵马尔科夫模型中的标签偏置问题。故条件随机场模型在标注上优于隐马尔科夫和最大熵马尔科夫等模型,取得较好的效果。

CRFs的结构可以是任意的图结构，当图形中各输出节点被连接成一条线性链的情况下，CRFs假设在各输出节点之间存在一阶马尔科夫独立性。链式CRFs是最常用的结构之一。在给定观察序列x，线性链的CRFs 定义状态序列y的条件概率为

式中：fk(e,y|e,x)为状态转移特征函数；gk(v,y|v,x)为状态特征函数；λk、μk分别是fk(e,y|e,x)和gk(v,y|v,x)的特征权重。

条件随机场模型训练主要有两个基本任务：特征选择和参数评估。特征选择就是选一个能表达这个随机过程的统计特征的集合，参数评估是指为入选的每个特征估计权重。一般采用极大似然估计方法来计算特征权重，从训练数据中计算出 θ=(λ1,λ2,…;μ1,μ2,…)。CRFs指数模型为凸函数，可以采用迭代方法找到全局最优解。目前常用的是L-BFGS 迭代方法。链式CRFs图示如图1，黑色代表隐藏节点，白色代表观察节点。

图1 一阶链式CRFs图形结构

1.2 应用

条件随机场模型强大的特征描述能力和克服标注偏置问题的特性，使其成为近几年机器学习领域的热点，并在若干领域得到成功应用。如计算语言学[6]、生物信息学、语音识别、图像目标识别等。虽然CRFs在模型训练上稍有逊色，但作为一种新模型和新技术，CRFs还大有潜力可挖，在各分类问题上有广阔的应用前景。

在入侵检测系统中，审计模式数据是以一些复杂关联的特征来表示的[7]。隐马尔科夫模型方法能够处理多个特征，但它将特征之间看成是相互独立的。忽略特征之间的关系会严重影响入侵检测系统的检测能力。例如，考虑“协议类型”和“网络流量”，当这些特征被单独分析时，它们并不能提供有助于入侵检测的有用信息，特征之间相关性的丢失会使准确率降低。但是如果将二者联合起来分析的话就会提供一些有意义的可帮助检测的细节信息。此外，它还不能处理观察输出之间的长距离依赖关系。

CRFs模型可在不作独立性假设的前提下有效处理多个特征间的关系，而不将特征间看成相互独立，能处理观察序列中的长距离触发关系。为有效检测入侵，提高攻击检测效率，必须对特征间的关系进行有效处理，该文利用条件随机场模型进行入侵检测实验，并与其他检测方法进行对比，实验证明该模型可取得最高效能。

2 基于层叠CRFs的入侵检测框架

2.1 应用CRFs

入侵检测本质上是一个分类问题，从网络上的大量记录中分类出正常请求及各种攻击。网络上的攻击方式很多，国际知识发现和数据挖掘工具竞赛KDD cup(International Knowledge Discovery and Data Mining Tools Competition)1999年的参赛入侵检测数据集中将常见攻击分为4大类：DoS(Denial of Service)、Probe(Surveillance/Probing)、R2L(Remote->Local)、U2R(User->Root)，如表1所示。

表1 KDD 中攻击分类

目前的入侵检测系统，像是基于决策树、基于朴素贝叶斯分布的，这些方法的最大缺陷就是它们将特征视作相互独立的，忽略特征之间的关系会严重影响分类器的性能。此处选用CRFs模型就是因为这个模型能够捕获到各特征之间的相关性，故本文采用CRFs模型来检测入侵。

如图2、3所示，特征“持续时间”、“协议”、“服务”、“源字节数”用来分辨攻击事件与正常事件。利用这些特征即可定义特征函数来共同确认攻击以提高检测效率。所以CRFs能就不同特征间的关系进行建模，这是现在的一些入侵检测模型所没有考虑的，或只考虑一个特征，如基于系统调用序列提取特征建立特征库，主要是利用时间按序列分析；或如同朴素贝叶斯分类器那样假设特征之间相互独立。

图2 攻击事件

图3 正常事件

2.2 层叠CRFs模型

在使用全部特征进行试验时，效果较之前的方法已有提高，但模型的训练效率偏低，模型本身就决定了其时间复杂度和空间复杂度非常高，这样模型无法及时更新，如何提高其训练效率，使之实现轻量化是实用该模型的一大挑战。从理论上讲，特征多则可利用的上下文信息多，识别效果会更好，但实际情况是随着特征数量的增多会产生大量冗余信息，影响识别速度和精度。现在的入侵检测系统，无论是基于网络还是基于主机，或二者兼有，都是使用一个入侵检测器(分类器)来检测多种攻击。也就是用一个分类器来分类 5种模式(Normal，Probe，DoS，R2L，U2R)，因为不同的攻击方式需要不同的特征来识别，在五分类问题中混杂的大量特征没有针对性，且大量特征会导致训练时间及空间爆炸式增长，甚至一些不相关特征会对特定攻击方式的识别产生干扰作用。笔者在分析了目前入侵检测系统的困难性基础上，进一步提出了基于层叠条件随机场的方案框架，分别针对每类入侵方式单独训练并应用CRFs模型。

笔者将原本的五分类问题转化为4层二分类(正常，某类特定攻击)问题，即将系统分成 4个子系统，每一层子系统负责检测一类特定的攻击类型。每一层是由3部分组成：特征选择模块、训练模块、检测模块。针对不同的入侵方式为子系统选择有利于检测该类入侵的特征，然后训练CRFs模型进行入侵检测。训练数据为正常审计数据及该类攻击数据记录，入侵检测算法流程如图4所示。

图4 入侵检测流程

这样做有两大优势，一是每一层的训练都只用了对检测该类入侵有关键作用的少数特征，这样可以更有针对性的处理此类入侵并可减少训练复杂度。系统更加灵活具有伸缩性，子系统的数量及处理的先后顺序可以按照需求变动。而且上一级子系统可以在检测到异常时就及时拦截，可快速反应并减少了下一级的负担。这种分而治之的思想有效的简化了整个框架的训练时间和空间复杂度问题，既提高了检测准确率又提高了系统效率。

2.3 特征选取

此处每一层的特征如表2所示，理论上特征模板是选择越多效果就越好的，但想要建立一组包含所有可能的模板是难以实现的，特征模板过于稀少又会影响识别效果。此处在总结前人研究的基础上，通过分析及大量相关实验，综合考虑确定了以人工选择为主，实验调整为辅的选择策略，筛选对入侵具有侦测性的特征。

表2 Probe、DOS、R2L、U2R检测选取特征

笔者尝试过采用自动选择特征，用Mallet Tool进行实验，选择方法尝试过多种，如文献[8]中所述方案，时间效率相当但准确率相差甚远；采用过前馈神经网络计算特征权重，筛选高权重特征，入侵检测准确率没有明显提高；尝试主成分分析法(Principle Component Analysis，PCA)[9]来降维，自动选择特征，主成分分析法将多个可能相互关联的特征转化成少数不相关联的主成分，这掩盖了CRFs模型强大的特征描述能力，CRFs的优点本身就是捕获特征之间的相关性，而主成分分析后的特征之间是相互独立的，这样的特征完全发挥不出CRFs模型的优势。故采取基于领域经验知识进行人工选择特征。例如Probe攻击，探测目标网络的信息，那“连接时间”、“源字节数”等就是有用特征，而“创建文件数量”、“访问文件数量”就不会提供有用的信息。

3 实验

实验采用KDD cup 1999年的竞赛入侵检测数据集作为训练和检测数据，该数据集包含了一个在军用网环境中的仿真数据集，内含多种模拟攻击。在实验时采用的是其单独提供的10%训练数据集和10%测试数据集，该数据是从KDD cup 1999的完整训练数据集合中随机抽取出来的。每一条连接记录都由41个特征来描述，实验的目的就是尽可能准确的检测异常模式，定位攻击。

实验采用CRF++工具集来训练模型，训练前用weka[10]对数据集作预处理，使之符合CRF++的输入规范。实验分2大块，一是用全部特征和训练集包括所有入侵的数据来训练模型，再就是针对每一层子系统选取不同的特征集，利用正常数据和该类攻击数据分别训练。因入侵检测系统的实际性能只取决于测试时的时间效能，在测试时该框架的运行效率很高，能达到部署实用的标准，故此处只检验准确率，在有实用价值的基础上将框架实现为完整系统时效率会更高。

选用的特征模板如表3所示。

表3 选用特征示例

实验结果采用准确率(Precision)、召回率(Recall)和F-1值来评估，

TP是被检测出来的入侵事件，FP是被误判为入侵事件的正常事件，FN没有被检测出来的入侵事件，β是准确率和召回率的比率权重，一般设为1。

实验结果如表4所示，对于DoS攻击各种检测准确率相差不大，CRFs模型在检测U2R攻击时的表现相比其他方法有很大提高。层叠模型相比于其他方法都要好。从KDD 1999检测数据上的结果和与其他方法的对比可以看出，层叠CRFs模型可有效的检测各种攻击。

表4 实验结果

4 结束语

为了从网络环境大量底层信息中正确有效地识别入侵攻击，将层叠CRFs模型应用到入侵检测中，分层处理每一类入侵，其中涉及到了针对每一类攻击构建特征模板，然后逐层进行检测，实验结果证明可取得比以往方法更好的效果。CRFs模型可取得较高检测率和低误报率的原因是它能有效处理特征之间的关系。加之特征选择并分别针对不同入侵方式进行训练可更有针对性，这不仅减轻了系统负担，使系统可适应于高速网络，而且显著提高系统的检测能力，尤其分析序列事件时，可获得相当高的准确率。通过实验，验证了层叠条件随机场模型的有效性和优越性。下一步的研究重点是细化特征模板的选取并尝试自动特征选取来建立更加实用的检测系统。

[1]ANIMESH PATCHA,JUNGMIN PARK.An overview of anomaly detection techniques:existing solutions and latest technological trends[J].Computer Networks,2007,51(12):3448-3470.

[2]TAMAS ABRAHAM.IDDM:Intrusion Detection Using Data Mining Techniques[M].Department of Defence,2007:11-16.

[3]AMOR N B,BENFERHAT S,ELOUEDI Z.Naive Bayes VS decision trees in intrusion detection systems[C]//Proceedings of ACM Symp.Applied Computing.New York,USA:ACM Press,2004:420- 424.

[4]段雪涛,贾春福,刘春波.基于层次隐马尔科夫模型和变长语义模式的入侵检测方法[J].通信学报,2010,31(3):109-114.

[5]JOHN LAFFERTY,ANDREW MCCALLUM,FERNANDO PEREIRA.Conditional random fields:probabilistic models for segmenting and labeling sequence data[C]//ICML.San Francisco,CA,USA:Morgan Kaufmann Publishers Inc.,2001:31-38.

[6]韩雪冬,周彩根.基于CRFs的中文分词算法研究与实现[D].北京:北京邮电大学,2010.

[7]胡广朋,程辉,邵玉宝.基于层叠条件随机场的网络入侵识别[J].江苏科技大学学报:自然科学版,2008,22(5):63-66.

[8]ANDREW MCCALLUM.Efficiently inducing features of conditional random fields[C]//Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence.Acapulco.Mexico:Morgan Kaufmann,2003:403-410.

[9]YACINE BOUZIDA,SYLVAIN GOMBAULT.Eigenconnections to intrusion detection[C]//Yves Deswarte,Lingyu Wang.In Security and Protection in Information Processing Systems.Toulouse,France:Springer Boston,2004:241-258.

[10]IAN H WITTEN,EIBE FRANK.Data Mining:Practical Machine Learning Tools and Techniques[M].3rd ed.Morgan Kaufmann,2011:140-147.