入侵检测算法三大分类

文/焦宝臣 刘振昌 陈诗明 于名飞

入侵检测算法三大分类

文/焦宝臣 刘振昌 陈诗明 于名飞

入侵检测系统（IDS，Intrusion Detection System）就是利用入侵检测技术发现计算机或网络中存在的入侵行为和被攻击的迹象的软硬件系统。区别于防火墙，入侵检测系统是一种主动防御的系统，能够更加及时地主动发现非法入侵并报警和采取应急措施，是人们研究的热点领域。

当前研究入侵检测系统的核心是对其算法的研究，人们的工作也大多集中于此。对于算法研究的目标是降低入侵检测系统的误报、漏报率和提升系统的运行效率。由于各种算法都有其局限性的一面，而具体的网络使用环境各不相同，这也是阻碍入侵检测系统商业应用的重要障碍，寻找一种具有适用性更广泛的算法也是研究工作的重要内容，对当前入侵检测算法研究现状进行综合考虑是十分必要的。本文从当前入侵检测算法的热点领域入手，依据入侵检测系统种类对当前流行的算法进行分类并详细介绍研究现状。

蚁群算法是一种基于生物种群的模拟进化算法，模拟蚁群在寻找食物的过程中总能找到蚁巢和食物源之间的最短路径的方法。

入侵检测算法分类

当前入侵检测算法多种多样，其中以关联规则、聚类和支持向量机等算法为代表的数据挖掘技术是当前研究的重点方面，另外，人工智能算法也在逐渐引起人们的注意。对入侵检测算法进行分类，首先考虑入侵检测系统的分类。入侵检测系统的分类有多种方法，如根据审计对象的不同，可分为基于网络的IDS、基于主机的IDS和基于网络/主机混合型IDS；按照系统的体系结构可以分为集中式和分布式入侵检测系统；按照检测技术可分为误用检测和异常检测两类。由于

检测技术实际上指的就是所使用的入侵检测算法，所以这里主要考虑按照检测技术分成的误用检测和异常检测的分类方法。另外随着人们对人工智能算法在入侵检测系统中应用研究的开展，这类系统呈现出与前两类不同的一些特性。因此将当前入侵检测算法归结为误用检测算法、异常检测算法和人工智能算法三类，具体情况如图1。图1给出了入侵检测算法的分类。下面就误用检测、异常检测和人工智能算法三种入侵检测算法分别进行介绍。

图1 入侵检测算法分类

误用检测算法

误用检测的基本原理是将已知的入侵行为和企图进行特征抽取，提取共同模式并编写进规则库，再将监测到的网络行为与库进行模式匹配，如果特征相同或相似，就认为是入侵行为或者企图，并触发警报。模式匹配是这类系统所采用的方法，如图1所示。

Snort入侵检测系统是一种典型的误用检测系统。它是在Libcap基础上研发的较为成熟的轻量级入侵检测系统，具有尺寸小、易于安装、便于配置、功能强大、使用灵活等特点。该系统采用的算法是模式匹配，因此人们的研究主要是集中在对模式匹配算法的优化上。例如：黄侃【1】对BM算法进行了优化，能够有效节省Snort系统的运算时间，提高系统性能，BM算法是Snort入侵检测系统中重要的字符串匹配算法。郝伟臣【2】给出一种基于哈希算法的匹配算法应用于Snort系统，取得了较好的效果。

该方法具有低误报率的优点，但是不能检测出规则库中不存在的入侵行为和企图，即无法检测未知的攻击。

异常检测算法

异常检测是通过建立一个主体正常行为的模型，将攻击行为作为异常活动从大量的正常活动中检测出来，达到对攻击行为检测的目的，其显著的优点是对未知攻击的检测。

数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们不知道的但又是潜在有用的信息和知识的过程。这一点与异常检测所要求的对未知入侵和威胁的检测是相一致的。随着数据挖掘算法的发展，其在入侵检测领域中的应用愈加深入，受到人们研究的关注。当前流行的数据挖掘技术是异常检测算法研究的主要领域，如图1所示，其中以关联规则、聚类和支持向量机等算法尤其具有代表性。下面就各种有代表性的算法进行介绍。

关联规则

关联规则算法的目的是发现隐藏在大型数据集的各不同属性之间的有意义联系，发现的联系用关联规则或者频繁相集来表示。关联规则的基本形式X→Y，这里X∩Y=Ø。支持度（Support）和置信度（Confidence）是最重要的两个概念，它们的定义：

Support（X→Y）=P(X∪Y) （1）；

Confidence（X→Y）=P(Y│X) （2）。

支持度可以确定规则中出现在给定数据集的频繁程度，置信度可以确定Y出现在包含X的事务中的频繁程度。因此，关联规则算法就是从某事物数据集中发现满足最小支持度和最小置信度的关联规则的过程。

采用关联规则算法对数据进行挖掘主要包括产生频繁项集和产生规则两个步骤。产生频繁项集：从数据集中发现满足最小支持度阈值的项集，即频繁项集。产生规则：从频繁项集中提取出所有满足最小置信度的规则。关联规则算法通常是先产生频繁项集后再产生规则， Apriori及其衍生的相关算法是这种典型的关联规则算法。一般情况频繁项集产生所需要的计算开销要远大于规则产生所需要的计算开销，为了降低运算成本，也可以不生成频繁项集的算法，如FP-Growth算法。

聚类算法

聚类就是按照一定的要求和规律对事物进行区分和分类。由于在聚类的过程中没有任何关于分类的先验知识，仅靠事物间的相似性作为类属划分的准则，因此这是一种无监督的分类方式 。

K-means是经典的聚类算法，它使用简单的迭代将数据集聚成K个类，该算法具有简单、易懂、良好的可伸缩性等显著优点。成为当前入侵检测系统中聚类算法研究方面的重要算法。例如：薛京花【3】等人对K-means算法进行了改进并应用到入侵检测系统中，并取得了明显的效果。

除了K-means算法之外，聚类方法还包括模糊聚类和蚁群聚类算法。传统的聚类分析是一种具有非此即彼的性质的硬划分。但现实中大部分数据对象并没有严格的属性，在形态和类属方面存在着中介性，更适合进行软划分。因此人们开始用模糊的方法来处理聚类问题。模糊C-均值算法是典型的模糊聚类算法。

蚁群算法是一种基于生物种群的模拟进化算法，模拟蚁群在寻找食物的过程中总能找到蚁巢和食物源之间的最短路径的方法。该算法具有分布式并行计算、自适应和易于其他算法相结合的优点。但存在过早限于局部最优解和收敛速度慢的缺陷。

支持向量机

支持向量机（Support Vector Machine, SVM）算法是建立在统计学习理论的基础上，能从大量训练数据中选出很少的一部分用于构建模型，通常对维数不敏感。在当前高速网络环境条件中很难获得完备的训练样本集，同时为了降低部署模型的资源开销，应尽可能地减少在数据挖掘的过程中使用的训练样本数据量。而SVM更适合小样本数据学习，更符合实际高速网络中的现实情况。另一方面，SVM能在很大程度上克服了传统机器学习（神经网络、决策树等）的维数灾难和局部极小等问题，获得比较好的泛化能力。具有良好泛化性能的入侵检测系统对应其实际应用有着重要的意义，是人们研究所期望获得的。综上所述，SVM成为研究构建入侵检测系统的重要算法。例如：李汉彪，刘渊【4】采用多SVM融合的方法，有效地弥补单个SVM检测的局限性，能有效地提高入侵检测率的同时降低误报率。

采用SVM算法构建入侵检测系统，通常需要其他算法对数据样本进行属性约减，降低维数，来提高运行效率。

另外也有利用蚁群、鱼群等生物种群算法对SVM进行改进。例如：杨聪明【5】采用将自组织蚁群聚类算法作为SVM算法中查询策略的方案，把蚁群聚类算法与SVM有效的融合，并应用到入侵检测系统中，获得了较高的检测率和较低的误报率、漏报率，并能提高算法的执行效率。

决策树

决策树是一种树状结构，用于揭示数据中的结构化信息。利用该结构可以将大型记录集分割为相互连接的小记录集，通过每一次连续分割，结果集中的成员彼此变得越来越相似。使用决策树算法可以将数据规则可视化，构造决策树的过程所需的时间也比较短，且输出的结果容易理解。决策树具有分类精度高，操作简单以及对噪声数据有很好健壮性的优点，C4.5、ID3是常见的决策树算法方法。

史珊姗【6】在利用决策树C4.5算法构建入侵检测系统方面做了相关研究。但是C4.5决策树算法在生成树的过程中，需要对样本集进行多次的扫描和排序，导致算法的效率比较低；另外C4.5 算法只适用于可以驻留于内存的数据集，当训练集超过内存的容纳能力时，程序就无法运行，使该算法对硬件要求比较高。

综上所述，异常检测算法主要采用关联规则、聚类、SVM等数据挖掘算法，如图1所示。除上述常用数据挖掘方法之外，还有k-最近临（kNN）、朴素贝叶斯（Nave Bayes）等数据挖掘算法也是被人们应用于入侵检测系统的研究中。根据这些算法的介绍可以得出，提高运行效率，提高准确率，降低误报率是人们对算法研究的目标，然而各种算法本身有着各自的缺陷，限制了传统算法的应用。

人工智能算法

通过前面对传统数据挖掘算法的研究发现，各种算法自身存在着缺陷，研究具有高效率、低误报率和良好泛化特性的算法仍旧是工作的中心。另外，具有分布式架构的入侵检测系统更能适应当前网络实际使用环境的需求，已成为当前入侵检测系统研究的主流构架。因此传统的算法已经不能满足当前入侵检测系统发展需求。随着人工智能的发展，将智能算法运用到入侵检测系统中，将成为入侵检测系统新的研究热点发展方向。免疫方法和神经网络是当前入侵检测系统主流的人工智能算法。

免疫方法

生物免疫系统的核心思想是识别并处理“自己”和“非己”，这与入侵检测系统的工作目标是一致的。生物免疫系统具有识别能力、学习认知能力、多样性、自适应性、自组织性、分布性的特点。其中分布性的特点是指免疫系统可以被视为一个分布式系统，因为免疫分子、免疫器官和免疫细胞不是集中分布在生物体的同一位置，而是分散开的，它们之间是相互独立的处理单元，通过免疫网络相互连接，共通完成比较复杂的免疫功能。这一点与当前构建分布式入侵检测系统的现实需求是一致的。因此利用免疫系统运算原理构建的入侵检测系统具有天然的优势。

姚云志【7】等人根据生物免疫系统与入侵检测系统工作目的的统一性，在结合了否定选择、克隆选择和检测子基因库进化三种免疫机制基础上，提出了一个改进的基于人工免疫的入侵检测新模型。周志凯【8】等人对免疫算法构建的入侵检测系统中关于具有信息增益的检测器做了较深入的研究。

神经网络

人工神经网络（ANN，Artificial Neural Network）是由人工神经元互连而成的网络，它从微观结构和功能上实现对人脑的抽象和简化。人工神经网络具有非线性逼近性，很好的鲁棒性以及容错性，快速的运算能力，较好的实时特性，良好的并行特性，良好的学习能力和自适应性等诸多优点。将人工神经网络技术应用于入侵检测系统，能够较好地解决目前一些不宜解决的问题，提高系统检测率，减少误报率。神经网络技术是最近几年研究的热点问题，如：多层前馈BP神经网络、蜜罐等等。

宋麟【9】等人研究了基于BP人工神经网络技术的入侵检测系统。对失真或不完全数据的处理能力，是基于BP神经网络的实时入侵检测系统的独特优点。李晨光【10】建立了基于BP神经网络的入侵检测系统，该系统具备了入侵检测技术的诸多优点，可以有效的检测出异常的网络攻击行为。蜜罐技术是一种主动的网络保护技术，其思想是构建一个严格的欺骗环境诱骗入侵者对其进行攻击，并在受到攻击后作出预警，从而实现保护实际运行的网络和系统。汪洁【11】等人设计并实现了一个基于人工神经网络的蜜罐入侵检测系统。该系统应用感知器学习方法构建FDM检测模型用于划分正常类和攻击类；构建SDM检测模型对一些具体的攻击类型进行识别。该系统对入侵行为具有较好的检测率和较低的误报率。

遗传算法

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的算法，是一种通过模拟自然进化过程搜索最优解的方法。将遗传算法应用到入侵检测中也有相关的研究。例如：朱红萍【12】等人构建了基于遗传算法的入侵检测系统，重点研究如何进行特征选择，来去除数据源中的不相关和冗余特征。

小结

从对人工智能算法入侵检测系统研究现状的情况看，人工智能算法目前还处于起步阶段，但是由于其算法先天的优势，正在被研究人员所关注，越来越多的研究工作正在展开。

人工神经 网络（ANN，Artificial Neural Network）是由人工神经元互连而成的网络，它从微观结构和功能上实现对人脑的抽象和简化。

通过对当前入侵检测算法的梳理，可分为误用检测算法、异常检测算法和人工智能算法三类。其中误用检测以模式匹配算法为主，关联规则、聚类、SVM等数据挖掘算法通常用于异常检测，免疫方法和神经网络是人工智能算法的代表。传统的数据挖掘算法仍是研究的重点和热点，以免疫算法和神经网络为代表的人工智能算法正引起人们的关注，其在入侵检测系统中的应用有着传统数据挖掘算法所不具备的优势和广泛的前景，应成为下一步研究的重点。

降低入侵检测系统的误报、漏报率和提升系统的运行效率仍然是算法研究的基本问题。另外，分布式架构和良好泛化性也是入侵检测系统所要亟待解决的问题。因此，研究算法来解决上述问题仍是当前科研人员主要工作。利用传统数据挖掘算法的特点和人工智能算法的优势，将其二者相结合或许能成为解决问题的一条路径。

（作者单位为南开大学信息化建设与管理办公室）

注释：

[1]黄侃．对Snort系统中BM模式匹配算法的研究与改进[J]．网络安全技术与应用，2014.7:39-40

[2]郝伟臣．Snort规则分组和映射算法的研究[D]．西安：西安电子科技大学，2014

[3]薛京花．K-means聚类算法在网络入侵检测中的应用研究[D]．长沙：中南林业科技大学，2012

[4]李汉彪，刘渊．一种SVM入侵检测的融合新策略[J]．计算机工程与应用，2012，48(4)：87-90

[5]杨聪明．基于蚁群聚类的SVM算法在入侵检测中的应用[D]．南京：南京理工大学，2012

[6]史珊姗．基于决策树C4.5算法的网络入侵检测研究[D]．苏州：苏州大学，2012

[7]姚云志，田玉玲．改进的基于人工免疫的入侵检测模型[J]．计算机应用与软件，2014，31(1)：308-310

[8]周志凯，张凤斌，马天宇．实值形态空间中基于信息增益的属性选择算法[J]．中国科技在线，2014，3(316)：1-9

[9]宋麟．人工神经网络技术在入侵检测系统中的应用[D]．成都：电子科技大学，2012

[10]李晨光．基于神经网络的入侵检测技术研究与应用[D]．长春：吉林大学，2013

[11]汪洁，杨柳．基于蜜罐的入侵检测系统的设计与实现[J]．计算机应用研究，2012，29(2)：667-671

[12]朱红萍，巩青歌，雷战波．基于遗传算法的入侵检测特征选择[J]．计算机应用研究，2013， 29(4)：1417-1419