基于SBOM算法的网络入侵检测系统的实现

时间:2023-12-21 点赞:49887 浏览:101423 作者原创标记本站原创

此文是一篇数据结构论文范文,数据结构有关论文范文集,与基于SBOM算法的网络入侵检测系统的实现相关毕业论文开题报告。适合不知如何写数据结构及算法及计算机网络信息安全方面的参考文献专业大学硕士和本科毕业论文以及数据结构类开题报告范文和职称论文的作为写作参考文献资料下载。

摘 要: 入侵检测系统的核心部分就是检测引擎,检测引擎采用的算法的优劣直接关系到入侵检测系统的性能.在分析SBOM算法的数据结构和模式匹配过程的基础上,将SBOM算法引入Snort网络入侵检测系统中,得到了实现Snort检测引擎的一种新的方法.实验结果表明,SBOM算法在模式集较大的情况下性能比较具有优势,并且随着最小模式长度以及模式集的增长算法具有更好的性能.

关 键 词 : 入侵检测系统; Snort; 模式匹配; SBOM

中图分类号: TP309 文献标识码: A 文章编号:2095-2163(2013)03-0090-03

The Implementation of Network Intrusion Detection System based on SBOM Algorithm

ZHOU Lihua

(Computer Network Center, Guizhou Minzu University, Guiyang 550025, China)

Abstract: The detection engine is the core module of the intrusion detection system. The efficiency of pattern matching algorithm used in detection engine decides the performance of this type of intrusion detection system. This paper implements the SBOM algorithm in Snort and obtains a new method of Snort detection engine. The result of experiment indicates that algorithm being paratively excellent for large keyword sets, and progressively better for large alphabets as the minimum keyword length increases and as the keyword set size increases.

Key words: Intrusion Detection System; Snort; Pattern Matching; SBOM

0 引 言

随着计算机网络的蓬勃发展和快速普及,计算机网络信息安全已成为当今社会的一个焦点问题.传统的计算机网络信息安全防御技术,如防火墙、数字签名等,已经难于适应当前计算机网络攻击的多样性.在此背景之下,入侵检测系统即成为研究的探索方向.入侵检测系统是一种积极主动防御的技术,其工作原理是动态的,可以在入侵过程中对防护系统进行实时监控,无论是发生内部攻击或是外部攻击,入侵检测系统均能对其提供实时的保护.入侵检测系统的核心部分就是检测引擎,检测引擎的算法优劣将直接关系入侵检测系统的性能[1].

1.SBOM算法数据结构

本文将近年来较新提出的基于Factor Oracle自动机的SBOM(Set Backward Oracle Matching)算法运用到Snort中.多模式的SBOM算法是BOM(Backward Oracle Matching)算法的扩展.BOM算法通过模式串建立一种类似于Trie的数据结构Oracle因子[2],Oracle由一系列节点因子连接而成,能接收模式串中所有的节点因子.事实上,Oracle的数据结构就是一种结构紧凑的确定型自动机,能够识别其所建立的关键字的所有因子,构建Oracle因子的算法可参考文献[3],此处不再赘述.图1是BOM的Oracle数据结构.

多模式的SBOM(Set Backward Oracle Matching)算法继承了BOM算法的Oracle数据结构和Aho-Corasick算法的Trie数据结构.在进行预处理过程中将根据所有模式串构造模式匹配的Oracle结构,以识别匹配窗口的最长字串.由于各个模式串的长度可能互不相同,为了不致遗漏正确的匹配,SBOM算法对模式串进行了如下处理[4]:

图1 BOM算法的Oracle数据结构

Fig.1 Oracle data structure of the BOM algorithm

(1)求模式串中最小串的长度,记为Imin.

(2)根据模式串集合P'等于{prefix(p,Imin)| p∈P}进行构造Oracle,即使用每个模式串的长度为Imin的前缀来完成构造.

多个模式串的Oracle结构为实现构造使用了BOM算法中的一个函数——supply function S,S函数的作用是对于某个状态p,能识别另外的一个状态k作为其替代状态.SBOM算法的Oracle数据结构的构建方法如下:

(1)根据所有模式串反相构造Trie连接结构.

(2)指定Trie的根节点I的supply function为空,即S[I]等于Φ.

(3)按宽度优先法则遍历Trie中的所有节点q,对于所有的q∈oracle(q≠I):

(a)初始化变量k←S[parent(q)];

(b) 初始化变量σ(σ表示从parent(q)到q结点的迁移值);

(c)如k等于Φ,则S(q) ←I;

(d)如k≠Φ并且没有从k到q值为σ的迁移,那么建立一个从k到q值为σ的迁移,置k←S(k),重复步骤(c); (e)如k≠Φ并且有从k状态开始值为σ的指向状态s的迁移,那么S(q)←s,完成状态q的建立.第3期 周丽华:基于SBOM算法的网络入侵检测系统的实现 智能计算机与应用 第3卷

现举一例,如模式串barbarian和bomb的Oracle结构,如图2所示.

图2 SBOM算法的Oracle数据结构

Fig.2 Oracle data structure of the SBOM algorithm

2.SBOM算法匹配过程

SBOM算法的匹配过程采用一个长度为Imin的滑动窗口来扫描输入文本,在这个窗口中可从右到左读取最长的从初始状态开始标示的后缀.SBOM算法的最坏时间复杂度是O(n*M),但在平均意义下则能亚线性地执行达到n[2].SBOM算法的匹配过程写成伪代码,如下所示:

(1)预处理过程,构建模式的Oracle结构;

(2)得到模式串中最小串的长度Imin,I←oracle root(根节点);

(3)i←0(文本当前的匹配位置),匹配过程开始;

验证y[i]...y[i+Imin -1]是否与q指向的模式串匹配

以下将通过实例来说明SBOM算法匹配过程.

由图2可得,数据串如3所示.

容易知道,匹配窗口移动2位,如图4所示.

图3 数据串

Fig.3 Data string

图4 SBOM算法匹配过程

Fig.4 The matching procedure of the

SBOM algorithm3 实验验证

为了评价加入SBOM算法后的NIDS的功能,本文将SBOM算法加入到Snort中并重新编译后得到Snort2.8.0.1版本,采用的编译环境是VC++6.0.硬件的配置如下:处理器为Pentium(R)4,内存为512M,操作系统为windows 2003 server.在检测基于SBOM算法的网络入侵监测系统的性能的同时,还选择了几个Snort自带模式匹配算法选项如AC-Full、acs、ac-banded、ac-bnfa、low-mem来比较彼此之间的性能[5].实验比较不同算法选项所对应的检测引擎的处理时间、系统消耗的内存随规则、模式、数据包的数量增减的变化情况.实验过程中,Snort以4 990条规则作为基数,每次减少约1 000条,对于每次选取的规则数的运行时间和内存消耗进行了3次记录,结果取其平均值.为了更准确地检测算法的性能,一组测试数据采用的是Shmoo工作组[6]所使用数据集,另外一组则采用与前者差距较大的美国麻省理工大学林肯实验室提供的1999 DARPA intrusion Detection Evaluation Data Sets,也就是著名的林肯数据集[7].其中,林肯数据集在评估入侵检测系统性能方面具有公认的权威性,目前国际上的商用系统及处于实验室阶段的科学研究原型系统均采用这个数据集进行测试,这个数据集记录了七个星期的主机系统记录日志和所有的网络流量记录,其数据是采用tcpdump和B审计数据的格式来进行记录的.本实验采用的则是其中一天的攻击数据.经处理后,这两个数据集大小分别为42.3MB和365.1MB,内含的数据包分别为406 815个和1 406 063个,实验结果分别如图5、图6所示.


图5 各算法运行时间

Fig.5 The running time of the algorithms

图6 各算法消耗内存

Fig.6 The memory usage of the algorithms 由图5和图6可以得出以下结论:

算法运行时间和数据包的大小有关,数据包越大,算法运行时间越长并且各算法之间的时间差距越大.在各个算法中,运行时间最优的是AC-Full和acs,其次是lowmem算法. 算法的内存消耗和数据包大小无关而与规则的数量有关,规则越多,消耗的内存越大.在各个算法中,消耗内存最多的是AC-Full算法,内存消耗最少的是ac-bnfa和lowmem.消耗内存最多的是AC-Full和SBOM算法,这两者的内存消耗基本上一致,多数时候SBOM略大于AC-Full,则是因为SBOM算法的Trie结构是用AC算法实现的,这一部分消耗的内存和AC-Full算法消耗的内存一致,多出来的部分用于构建Oracle数据结构,这一部分的构建是基于反向的最短关键字,可以看到构建Oracle数据结构消耗的内存比构建Trie结构要少得多.

SBOM算法的平均运行时间能达到亚线性,从图5和图6可以看到在模式较多、也就是规则较多的情况下,SBOM算法在性能上较有优势,但是如果规则较少,优势则并不十分明显.

4.结束语

在AC算法的各种变体中,AC-Full完全是以空间换时间,在性能上相较其他几种算法并没有极大的优势;ac-bnfa在内存消耗上比较低但是同时又有比较高的性能,虽然lowmem也同样消耗内存较少,但其性能并不是很高.由此得出结论,没有一种算法能适用于所有的情况,在实际的应用中,可以根据系统的具体情况以选择相应的算法.

相关论文

混合数据聚类的网络入侵检测算法

本文是一篇图书馆论文范文,关于图书馆硕士论文开题报告,关于混合数据聚类的网络入侵检测算法相关专升本毕业论文范文。适合图书馆及计算机及。

网络入侵检测方法

本文是一篇概率统计论文范文,关于概率统计相关毕业论文模板,关于网络入侵检测方法相关专科毕业论文范文。适合概率统计及计算机网络及计算机。

WSN多级分类代理入侵检测系统

本文是一篇算法论文范文,关于算法毕业论文题目,关于WSN多级分类代理入侵检测系统相关大学毕业论文范文。适合算法及向量及计算机系方面的的。

基于代理的分布式入侵检测系统设计

本文是一篇信息安全论文范文,信息安全有关硕士学位论文,关于基于代理的分布式入侵检测系统设计相关大学毕业论文范文。适合信息安全及网络及。

基于免疫原理的网络入侵检测

本文是一篇计算机安全论文范文,关于计算机安全相关毕业论文开题报告范文,关于基于免疫原理的网络入侵检测相关毕业论文提纲范文。适合计算机。