模式匹配算法在入侵检测中的应用

预处理阶段，模式树的各个节点作为状态，根节点作为初态，标签为模式的节点作为终态，利用转向函数g和失效函数f作为转移函数，将模式树扩展成一个树型有限自动机。
由模式树扩展所得的AC自动机M是1个6元组：

M=(Q,∑，g，f，q0，F)
其中：
(1)Q是有限状态集(模式树上的节点)；
(2)∑是有穷的输入字符表(数据包中可能出现的所有字符)；
(3)g是转移函数，该函数定义如下：g(s，a)：从当前状态s开始，沿着边上标签为a的路径所到的状态。假如(u，v)边上的标签为a，那么g(u，a)=v；如果根节点上出来的边上的标签没有a，则g(0，a)=O，即如果没有匹配的字符出现，自动机停留在初态；
(4)f(不匹配时自动机的状态转移)也是转移函数，该函数定义如下：
f(s)：当w是L(s)最长真后缀并且w是某个模式的前缀，那么f(s)就是以w为标签的那个节点；
(5)q0∈Q是初态(根节点，标识符为0)；
(6)XXXXX是终态集(以模式为标签的节点集)。
这样，在目标串中查找模式的过程转化成在模式树中的查找过程。查找一个串T时从模式树的根节点开始，沿着以T中字符为标签的路径往下走：若自动机能够抵达终态v，则说明T中存在模式L(v)；否则不存在模式。
AC算法模式匹配的时间复杂度是0(n)，并且与模式集中模式串的个数和每个模式串的长度无关。无论模式串P是否出现在目标串T中，T中的每个字符都必须输入状态机中，所以无论是最好情况还是最坏情况，AC算法模式匹配的时间复杂度都是O(n)，包括预处理时间在内，AC算法总时间复杂度是O(M+n)，其中M为所有模式串的长度总和。
2．3 AC―BM算法
对多模式串的匹配而言，虽然AC算法比BM算法高效得多，但AC算法必须逐一查看目标串的每个字符，即必须按顺序输入，不能实现跳跃，而BM算法则能够利用“右滑”跳过目标串中的大段字符，从而提高搜索速度。如果将BM算法的这种启发式搜索技术应用到AC算法中，则可大大提高多模式匹配算法的效率。许多人据此给出了各种改进的算法。Commentz―Walter最先将BM算法和AC算法结合在一起给出了Com―mentz―Walter算法；Baeza―Yates结合BMP算法和AC算法也给出了多模式匹配改进算法。
AC―BM算法是Jang―Jong在1993年结合Ac算法的有限自动机和BM算法的连续跳跃思想提出来的新算法，利用劣势移动表和优势跳转表来实现跳跃式地并行搜索，算法的时间复杂度为0(mn)。该算法的思想是：首先把要查找的多个模式构成一个关键字树，把相同的前缀作为树的根节点。模式树从目标串的右端向左移动，一旦模式树确定在适当的位置，字符比较从左向右开始进行。模式树移动时同时使用坏字符移动和好前缀移动。坏字符移动的策略为：如果出现不匹配的情况，移动模式树，使得树中其他模式的能与当前目标串正在比较的字符相匹配的那个字符移动到与当前目标串正在比较的字符的相同位置上，如果在当前的深度上，目标字符没有出现在任何模式中，则模式树的偏移量为树中最短模式的长度。好前缀移动的移动策略为：将模式树移动到一个已被发现是另一个模式子串完全前缀的下一个位置，或者移动到作为树中另一个模式后缀能够正确匹配目标串的某个前缀的下一个位置。在模式树的移动过程中，必须确保模式树的偏移量不能大于树中最短的模式长度。
2．4 AC，AC―BM算法改进情况简介
文献中卢汪节等人针对AC算法在构造状态机时空间冗余较大的情况，对状态机各结点进行压缩存储，使空间性能和时间性能都有提高；文献中万国根等人对AC―BM算法的改进借鉴了BMH算法的思想，取消了原算法的好前缀跳转，优化了坏字符跳转，并修改了skip的计算方法，对大字符集的情况在平均情况下具有更优的性能；文献对AC―BM的改进则是通过预处理思想实现的，在进行AC―BM匹配之前首先扫描首和(或)尾字符，确定其位置，再到相应位置进行匹配，相当于把目标串按模式串首、尾字符分成数段，每段进行比较，段间不含首字符的就直接跳过，不用比较，从而提高效率。

3 算法的实际执行效率
上述这些算法究竟哪种算法具有最好的执行效率呢?能不能仅通过时间复杂度来进行衡量呢?时间复杂度仅是一个度量的范围，表示受几个参数的影响，并不代表一个具体的值，还需要在具体的环境中进行测试。
文献测试了包括上述算法在内的多种单模式和多模式匹配算法的性能。测试平台为：硬件：CPUIntel Xeon 3．46 GHz X 2，内存2 GB DDR，硬盘200GB SCSI；软件：windows 2003 Server，Intel IXASDK4．1。单模式匹配测试的规则集，使用随机生成的8，16，32，48，128位具有代表意义的规则，可以对应端口、IP地址，MAC地址、IPv6地址等，对多模式匹配测试采用Snort系统2．4．3规则集。
单模式匹配算法主要测试模式长度与匹配时间、占用空间及预处理时间的变化关系。测试结果表明：各算法的测试指标在规则长度增长的情况下均呈递增趋势，但BM算法的增长速度最为缓慢，在不太在意存储空间的情况下，BM可以作为优先考虑的算法，同时对IPV6地址也更为合适。
多模式匹配算法的测试项目为规则数与单位匹配时间、占用储存单元、单位预处理时间的变化关系。测试结果表明AC―BM算法在上述3项测试中取得了很好的性能平衡。这也是新版的Snort系统中选用AC―BM算法的重要原因。