基于 Snort入侵检测的后缀搜索算法的研究与改进 ◆胡朝举石倩 华北电力大学(保定)控制与计算机工程学院河北071000) 摘要: Snort是基于规则匹配的入侵检测系统,提高规则匹配的速度至关重要。本文通过对 Snort下基于后缀搜索的入侵检测算法BM 算法、WM算法的硏究,对wM算法进行了改进,将模式集合根据长度分为两部分,每个模式串建立子移动表。试验结果表明,改 进的算法提高了 Snort的入侵检测效率 关键词:入侵检测;模式匹配;WM算法 0引言 (3)好后缀在模式串中并不存在,则移动距离为m Snort入侵检测系统是目前使用最广的开源入侵检测系统之 BM算法的移动距离为好后缀机制和坏字符机制的最大值。 具有良好的跨平台性,并提供丰富的报警机制。 Snort的检3Wu- Manber(WM)算法及改进 测采用的是模式匹配策略。模式匹配过程是系统运行的主要过 WM算法继承了BM算法中的坏字符机制,但是WM算法 程,是系统主要的性能瓶颈。针对此问题已有很多学者做了大量依据长度为B的字符块进行跳跃 研究,文献[3]对BM算法做了改进,去除了传统的好后缀规则 3.1预处理过程 改进了坏字符规则。文献[4]提出一种基于随机指纹模型的多模式 预处理阶段建立三张表移动表( Shift table)、哈希表(Hash 匹配方法。文献[5]基于BM算法的优点改进AC算法,提出了多 Table)和前缀表( Prefix Table)来移动搜索窗口。 目标ACBM算法,大大降低重复搜索文本串的次数。文献[6] (1)建立移动表( Shift Table 把AC算法和BMH算法结合,只保留坏字符规则,最大移动距 记最小模式串长度m,只考虑每个模式串的前m个字符。 离为最短模式串长度。文献7]提出了一种改进的wM算法,减对m个字符中后B个字符创建一个移动表 少了重复比较次数。本文通过对后缀搜索算法的研究,对WM算 (2)建立哈希表( Hash Table) 法进行改进,提高了 Snort的入侵检测的效率 发生匹配时,为了确定匹配的字符串,避免和模式字符串全 1模式字符串匹配算法 部比较,使用哈希技术减少比较的次数。计算B个字符的哈希 已知字符集合E,大小记为P,模式串P-APPP315m,用作为哈希表的索引,哈希表的值就是该B个字符所在模式字符 文本串T=441-1∈21s≤n),m≤n,单模式字符串匹配即求解 串的索引。 O={l=P,1≤k≤m (3)建立前缀表( Prefix Table) 已知字符集合∑,大小记为||,Σ为正闭包,记文本串 有的有相同后缀的模式字符串在哈希表中有相同的入口 x1x}eE,模式串集合记为PP,v={mp}ex,值。当文本中这样一个后缀时,当发现shi值为0,不得不单独 模式集合长度总和为Pm字符串x、”、、",若y 检查所有带有这个后缀的模式字符串看它是否和T匹配,因此需 则x为y的前缀,a为的后缀,2为”的子串 要建立前缀表。匹配完所有模式串的B个字符和前缀表中的前B 多模式匹配问题可表示为求解集合 个字符,如果匹配成功,则让整个模式串去和文本进行逐字符匹 0=f1vj, 00文本指针向右滑刚位,转(1): 2.1坏字符机制 Shift]=0,转(3) 当P不包含c字符时 Bachar(c)= (3)计算文本当前位置前m位与前m-1位前缀的哈希值 mj,当P~目是最大整数(1≤j≤m) 记为 text prefix。 (1)导致不匹配的字符不在模式串P中,模式串向右取得 (4)对于每个p(面sp<ha地+),否则 最大移动距离m。 Prefix[p]= text prefix。如果相等,让真正的模式串去和文本进行 (2)导致不匹配的字符在模式串P中,则移动模式串最短 逐字符匹配 距离使可匹配字符与相应文本T字符对应 2.2好后缀机制 (1)好后缀在模式串中存在,那么好后缀和T中已匹配对 齐匹配 (2)好后缀的最大子串在模式串中存在,那么好后缀最大 区配a口b-口 子串和T对应子串对齐匹配 回四sr西
基于 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 模式字符串匹配算法 已知字符集合 Σ ，大小记为 | Σ |= σ ，模式串 1 2 3... ( ,1 ) P p p m r = p p p r m ， 文本串 1 2 3... ( ,1 ) T t t n s = t t t s n ， m n ，单模式字符串匹配即求解 集合： O i t p k m = = { | ,1 } i k k + 已知字符集合 Σ ，大小记为 | Σ |= σ ， * Σ 为正闭包，记文本串 * T ={T1T2T3 ...Tn}Σ ，模式串集合记为 { ... } P = P1P2P3 Pn ， * 1 2 3 = P p p p p i m { ... }Σ ， 模式集合长度总和为 1 | | | | r P p = i 。字符串 x、 y 、 z 、u ，若 y xzu = ， 则 x 为 y 的前缀， u 为 y 的后缀， z 为 y 的子串。 多模式匹配问题可表示为求解集合： O i j j r s t P k T i k = = + { | ,0 , . , 0 k<m} j 其中 后缀搜索是在搜索窗口内，模式匹配的是从右向左的搜索最 长公共后缀。基于后缀搜索的算法经典的有 BM 算法、WM 算法。 2 Boyer-Moore 算法 BM 算法中匹配失败时，用两种机制来确定模式串向右移动 的距离：坏字符机制和好后缀机制。 2.1 坏字符机制 j , P c ( ) m-j P =c j m BadChar c = 当 不包含 字符时 , 当 且 是最大整数(1 j m) （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 个字符 T m B T m [ 1]... [ ] − + ， 如图 1 所示。 （1）扫描文本的末 B 位 T m B T m [ 1]... [ ] − + 通过 hash 函数计算 哈希值 h。 （2 ） 查Shift Shift h Shift h 表，若 0，文本指针向右滑 位 ，转 （1）； Shift[h]=0，转（3）。 （3）计算文本当前位置前 m 位与前 m-1 位前缀的哈希值， 记为 text_prefix。 （ 4 ）对于每个 p （ Hash h p Hash h [ ] [ 1] + ）， 否 则 Prefix[p]=text_prefix。如果相等，让真正的模式串去和文本进行 逐字符匹配。 b a r b a r b a r i a n b a r Shift[ri]=2 Shift[rb]=3 Shift[rb]=3 Shift[an]=0 b a r b a r i a n m u s i c i a n 匹配
图1WM算法搜索示意图 分析WM算法发现,存在缺点:(1)如果最短模式串非常 短,那么m的值就会非常小,算法最多只能跳跃m,此时算法 表示在折线图中,如下图3所示 的效率就变得非常低。(2) Shift表为0时,需要进行精确匹配 而在WM算法中使用的精确匹配算法是效率较低的蛮力算法 3改进 对于这两个缺点,可以改进:(1)将特征集合分为长短两个 特征集合来处理。通过分析发现,找到合适的分割长度,从而 以取得较好的匹配性能。(2)为每个模式串建立一个sub-shit表, 图3各算法内存对比 其大小与模式串相同。相应的sub-shit表项中存放当与本模式串 匹配失败时,搜索窗口向右移动字符数。搜索过程中在精确匹配如下图4所示。 规则数目为2800,模式串最小长度不同下,算法的运行时间 全部完成时,我们根据各字符串 subshift表值的综合情况,找到如下图4所示 文本可以安全地向右跳跃的字符数 WM-NEW算法 4实验 4.1数据源 据源采用的是国际认可的麻省理工学院林肯实验室提供 盏45000 的 DARPA2000入侵检测数据集。该数据集包括DoS、R2L U2R、 Probe和Data5大类58种攻击方式 4.2实验环境 最式长度(字箐) 实验环境为win7操作系统、2G内存、 snort-2.9.1、C in Pcap 412, snortrules-snapshot-2.9.1.tar.gz. 4算法最短模式串长度下时间对比 yawn提供编译 Snort所需要的应用程序 bison、flex、sed。 通过实验结果可以看出,改进后的算法匹配效率能有了很大 WinPcap是数据包捕获器,为 Snort捕获数据包 提高,规则数目越多,优势越明显。且算法平稳增长时间性能受 4.3实验方法 影响较小。模式串长度增大时,新算法匹配效率提高较大。新算 以补丁的形式将算法加入到 Snort中,在配置文件中将匹配 法的内存占用量虽然比WM算法大,但仍小于AC算法,在可接 方法设置为WM算法 算法 WM-NEW及默认算法受范围,模式串越多约明显 AC- SPLIT算法。 Snort扫描入侵检测数据集,比较wM算法 5结束语 改进算法、 AC- SPLIT算法在规则数目不同时的时间,以及在规 本文研究了 Snort中两个经典后缀搜索算法,并对WM算法 则数目不同的占用内存。规则数目为2800,模式串最小长度不同进行了改进,并将其AC- SPLIT算法、WM算法进行了对比,结 下,算法的运行时间对比。规则数目是除去对数据集的解码规则果表明改进后的算法检测效率提高。同时,改进后的算法在内存 和预处理规则后的数目 占用方面仍有改进的空间,更加有效地为 Snort所使用 4实验结果 在规则数目不同情况下,各算法匹配时间,以1000ms为单 参考文献 表1算法匹配时间(×1000ms) 6001000140018002200 [1]刘积芬网络入侵检测关键技术研究[D]上海:东华大 AC-SPLIT422974379644949460(1505631 学,2013 WM416124327544564537047562|4842l [2]刘鑫网络入侵检测系统中模式匹配算法的应用研究 [D]大连海事大学,2013 WM-NEW412104285343810441854581047312 3]王友钊,黄冬一种提高系统搜索效率的BM改进算法 表示在折线图中,如下图2所 计算机工程,2014 [4张宏莉,徐东亮,梁敏,刘宇峰海量模式高效匹配方 法研究U电子学报,2014 [5]王正才,许道云,王晓峰基于自动机并操作的多目标 AC-BM算法[计算机科学,2013. [6]陆琳琳,田野基于确定有限状态自动机的改进多模式 匹配算法研究[计算机应用与软件,2013 刁蒋晓鸽,武小年,张昭基于后缀WM匹配算法的改进 图2各算法规则数目下时间对比 算法计算机与数字工程,2013. 规则数目不同情况下,各算法占用内存测试结果,以MB为 8]Laboratory Lincoln. MIT Lincoln Laboratory Int 单位。 ormation Systems Technolo gy[eb/ol].httP://www mit. edu/deval /data/2000d ata. html 规则数目200600100140180012001 AC-SPLIT
图 1 WM 算法搜索示意图 分析 WM 算法发现，存在缺点：（1）如果最短模式串非常 短，那么 m 的值就会非常小，算法最多只能跳跃 m，此时算法 的效率就变得非常低。（2）Shift 表为 0 时，需要进行精确匹配， 而在 WM 算法中使用的精确匹配算法是效率较低的蛮力算法。 3.3 改进 对于这两个缺点，可以改进：（1）将特征集合分为长短两个 特征集合来处理。通过分析发现，找到合适的分割长度，从而可 以取得较好的匹配性能。（2）为每个模式串建立一个 sub-shift 表， 其大小与模式串相同。相应的 sub-shift 表项中存放当与本模式串 匹配失败时，搜索窗口向右移动字符数。搜索过程中在精确匹配 全部完成时，我们根据各字符串 sub-shift 表值的综合情况，找到 文本可以安全地向右跳跃的字符数。 4 实验 4.1 数据源 数据源采用的是国际认可的麻省理工学院林肯实验室提供 的 DARPA2000[8]入侵检测数据集。该数据集包括 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） 规则数目 200 600 1000 1400 1800 2200 AC-SPLIT 42287 43796 44430 44690 49460 50563 WM 41612 43275 44956 45370 47562 48421 WM-NEW 41210 42853 43810 44185 45810 47312 表示在折线图中，如下图 2 所示。 40000 42000 44000 46000 48000 50000 52000 200 600 1000 1400 1800 2200 2600 运行时间（×1000ms） 规则数目 AC-SPLIT算法 WM算法 WM-NEW算法 图 2 各算法规则数目下时间对比 规则数目不同情况下，各算法占用内存测试结果，以 MB 为 单位。 表 2 算法占用内存（MB） 规则数目 200 600 1000 1400 1800 2200 AC-SPLIT 63 72 78 83 86 88 WM 58 69 72 76 79 82 WM-NEW 60 71 76 80 84 88 表示在折线图中，如下图 3 所示。 50 60 70 80 90 100 110 200 600 1000 1400 1800 2200 2600 占用内存（MB） 规则数目 AC-SPLIT算法 WM算法 WM-NEW算法 图 3 各算法内存对比 规则数目为 2800，模式串最小长度不同下，算法的运行时间 如下图 4 所示。 40000 45000 50000 55000 60000 运行时间 2 6 10 14 18 (×1000ms) 最短模式串长度（字符） WM算法 WM-NEW算法 图 4 算法最短模式串长度下时间对比 通过实验结果可以看出，改进后的算法匹配效率能有了很大 提高，规则数目越多，优势越明显。且算法平稳增长时间性能受 影响较小。模式串长度增大时，新算法匹配效率提高较大。新算 法的内存占用量虽然比 WM 算法大，但仍小于 AC 算法，在可接 受范围，模式串越多约明显。 5 结束语 本文研究了 Snort 中两个经典后缀搜索算法，并对 WM 算法 进行了改进，并将其 AC-SPLIT 算法、WM 算法进行了对比，结 果表明改进后的算法检测效率提高。同时，改进后的算法在内存 占用方面仍有改进的空间，更加有效地为 Snort 所使用。 参考文献： [1]刘积芬.网络入侵检测关键技术研究[D].上海：东华大 学，2013. [2]刘鑫.网络入侵检测系统中模式匹配算法的应用研究 [D].大连海事大学，2013. [3]王友钊，黄冬.一种提高系统搜索效率的 BM 改进算法 [J].计算机工程，2014． [4]张宏莉，徐东亮，梁敏，刘宇峰.海量模式高效匹配方 法研究[J].电子学报，2014. [5]王正才，许道云，王晓峰.基于自动机并操作的多目标 AC-BM 算法[J].计算机科学，2013. [6]陆琳琳，田野.基于确定有限状态自动机的改进多模式 匹配算法研究[J].计算机应用与软件，2013. [7]蒋晓鸽，武小年，张昭.基于后缀 WM 匹配算法的改进 算法[J].计算机与数字工程，2013. [8]Laboratory Lincoln.MIT Lincoln Laboratory Information Systems Technology[EB/OL].http：//www.ll. mit.edu/ideval/data/2000data.html
