基于Snort入侵检测的后缀搜索算法的研究与改进.doc

基于Snort入侵检测的后缀搜索算法的研究与改进胡朝举 石 倩（华北电力大学（保定）控制与计算机工程学院 河北 071000）摘要：Snort是基于规则匹配的入侵检测系统，提高规则匹配的速度至关重要。本文通过对Snort下基于后缀搜索的入侵检测算法BM算法、WM算法的研究，对WM算法进行了改进，将模式集合根据长度分为两部分，每个模式串建立子移动表。试验结果表明，改进的算法提高了Snort的入侵检测效率。关键词：入侵检测；模式匹配；WM算法0 引言Snort入侵检测系统是目前使用最广的开源入侵检测系统之一，具有良好的跨平台性，并提供丰富的报警机制。Snort 的检测采用的是模式匹配策略。模式匹配过程是系统运行的主要过程，是系统主要的性能瓶颈。针对此问题已有很多学者做了大量研究，文献3对BM算法做了改进，去除了传统的好后缀规则，改进了坏字符规则。文献4提出一种基于随机指纹模型的多模式匹配方法。文献5基于BM算法的优点改进AC算法，提出了多目标AC-BM算法，大大降低重复搜索文本串的次数。文献6把AC算法和BMH算法结合，只保留坏字符规则，最大移动距离为最短模式串长度。文献7提出了一种改进的WM算法，减少了重复比较次数。本文通过对后缀搜索算法的研究，对WM算法进行改进，提高了Snort的入侵检测的效率。1 模式字符串匹配算法已知字符集合，大小记为，模式串，文本串，单模式字符串匹配即求解集合： 已知字符集合，大小记为，为正闭包，记文本串，模式串集合记为，模式集合长度总和为。字符串、，若，则为的前缀，为的后缀，为的子串。多模式匹配问题可表示为求解集合：后缀搜索是在搜索窗口内，模式匹配的是从右向左的搜索最长公共后缀。基于后缀搜索的算法经典的有BM算法、WM算法。2 Boyer-Moore 算法BM 算法中匹配失败时，用两种机制来确定模式串向右移动的距离：坏字符机制和好后缀机制。2.1 坏字符机制 （1）导致不匹配的字符不在模式串P中，模式串向右取得最大移动距离m。（2）导致不匹配的字符在模式串P中，则移动模式串最短距离使可匹配字符与相应文本T字符对应。2.2 好后缀机制（1）好后缀在模式串中存在，那么好后缀和T中已匹配对齐匹配。（2）好后缀的最大子串在模式串中存在，那么好后缀最大子串和T对应子串对齐匹配。（3）好后缀在模式串中并不存在，则移动距离为m。BM算法的移动距离为好后缀机制和坏字符机制的最大值。3 Wu-Manber（WM）算法及改进WM算法继承了 BM 算法中的坏字符机制，但是WM算法依据长度为 B的字符块进行跳跃。3.1 预处理过程预处理阶段建立三张表移动表（Shift Table）、哈希表（Hash Table）和前缀表（Prefix Table）来移动搜索窗口。（1）建立移动表（Shift Table）记最小模式串长度m，只考虑每个模式串的前m个字符。对m个字符中后B个字符创建一个移动表。（2）建立哈希表（Hash Table）发生匹配时，为了确定匹配的字符串，避免和模式字符串全部比较，使用哈希技术减少比较的次数。计算B个字符的哈希值用作为哈希表的索引，哈希表的值就是该B个字符所在模式字符串的索引。（3）建立前缀表（Prefix Table）所有的有相同后缀的模式字符串在哈希表中有相同的入口值。当文本中这样一个后缀时，当发现Shift值为0，不得不单独检查所有带有这个后缀的模式字符串看它是否和T匹配，因此需要建立前缀表。匹配完所有模式串的B个字符和前缀表中的前B个字符，如果匹配成功，则让整个模式串去和文本进行逐字符匹配。3.2 搜索阶段扫描过程算法的主要包括以下步骤：每次扫描B个字符，如图1所示。（1）扫描文本的末B位通过hash函数计算哈希值h。（2），转（1）；Shifth=0，转（3）。（3）计算文本当前位置前m位与前m-1位前缀的哈希值，记为text_prefix。（4）对于每个p（），否则Prefixp=text_prefix。如果相等，让真正的模式串去和文本进行逐字符匹配。图1 WM算法搜索示意图分析WM算法发现，存在缺点：（1）如果最短模式串非常短，那么m的值就会非常小，算法最多只能跳跃m，此时算法的效率就变得非常低。（2）Shift表为0时，需要进行精确匹配，而在WM算法中使用的精确匹配算法是效率较低的蛮力算法。3.3 改进对于这两个缺点，可以改进：（1）将特征集合分为长短两个特征集合来处理。通过分析发现，找到合适的分割长度，从而可以取得较好的匹配性能。（2）为每个模式串建立一个sub-shift表，其大小与模式串相同。相应的sub-shift表项中存放当与本模式串匹配失败时，搜索窗口向右移动字符数。搜索过程中在精确匹配全部完成时，我们根据各字符串sub-shift表值的综合情况，找到文本可以安全地向右跳跃的字符数。4 实验4.1 数据源数据源采用的是国际认可的麻省理工学院林肯实验室提供的DARPA20008入侵检测数据集。该数据集包括DoS、R2L、U2R、Probe和Data5大类58种攻击方式。4.2 实验环境实验环境为win7操作系统、2G内存、snort-2.9.1、Cygwin、WinPcap_4_1_2、snortrules-snapshot-2.9.1.tar.gz。Cygwin提供编译Snort所需要的应用程序bison、flex、sed。WinPcap是数据包捕获器，为Snort捕获数据包。4.3 实验方法以补丁的形式将算法加入到Snort中，在配置文件中将匹配方法设置为WM算法、改进算法WM-NEW及默认算法AC-SPLIT算法。Snort扫描入侵检测数据集，比较WM算法、改进算法、AC-SPLIT算法在规则数目不同时的时间，以及在规则数目不同的占用内存。规则数目为2800，模式串最小长度不同下，算法的运行时间对比。规则数目是除去对数据集的解码规则和预处理规则后的数目。4.4 实验结果在规则数目不同情况下，各算法匹配时间，以1000ms为单位。表1 算法匹配时间（1000ms）规则数目2006001000140018002200AC-SPLIT422874379644430446904946050563WM416124327544956453704756248421WM-NEW412104285343810441854581047312表示在折线图中，如下图2所示。图2 各算法规则数目下时间对比规则数目不同情况下，各算法占用内存测试结果，以MB为单位。表2 算法占用内存（MB）规则数目2006001000140018002200AC-SPLIT637278838688WM586972767982WM-NEW607176808488表示在折线图中，如下图3所示。图3 各算法内存对比规则数目为2800，模式串最小长度不同下，算法的运行时间如下图4所示。图4 算法最短模式串长度下时间对比通过实验结果可以看出，改进后的算法匹配效率能有了很大提高，规则数目越多，优势越明显。且算法平稳增长时间性能受影响较小。模式串长度增大时，新算法匹配效率提高较大。新算法的内存占用量虽然比WM算法大，但仍小于AC算法，在可接受范围，模式串越多约明显。5 结束语本文研究了Snort中两个经典后缀搜索算法，并对WM算法进行了改进，并将其AC-SPLIT算法、WM算法进行了对比，结果表明改进后的算法检测效率提高。同时，改进后的算法在内存占用方面仍有改进的空间，更加有效地为Snort所使用。 参考文献：1刘积芬.网络入侵检测关键技术研究D.上海：东华大学，2013.2刘鑫.网络入侵检测系统中模式匹配算法的应用研究D.大连海事大学，2013.3王友钊，黄冬.一种提高系统搜索效率的BM改进算法J.计算机工程，20144张宏莉，徐东亮，梁敏，刘宇峰.海量模式高效匹配方法研究J.电子学报，2014.5王正才，许道云，王晓峰.基于自动机并操作的多目标AC-BM算法J.计算机科学，2013.6陆琳琳，田野.基于确定有限状态自动机的改进多模式匹配算法研究J.计算机应用与软件，2013.7蒋晓鸽，武小年，张昭.基于后缀WM匹配算法的改进算法J.计算机与数字工程，2013.8Laboratory Lincoln.MIT Lincoln Laboratory Inf-ormation Systems TechnologyEB/OL.http：/www.ll.mit.edu/ideval/data/2000data.html.