双向AC算法及其在入侵检测系统中

经过众多伟大科学家不断地研究，我国在算法领域有了进一步的发展，当前相关的科学家已经在经典的多模式字符串匹配算法-AC算法的基础上提出了双向AC算法。这种双向算法的提出能够在预处理阶段建立正向和反向两种状态的自动机，这种自动机在扫描的过程中使用正向有限自动机从中间向右进行，而反向有限自动机从中间向左进行。这种算法与之前相比具有更高的效率，因此得到了更广泛的使用。

【关键词】AC算法 串匹配算法 入侵检测系统

一般情况下，网络入侵检测系统的模式匹配算法的主要功能就是判断攻击模式串是否在截获的网络数据包有效负载中出现。一般情况下，我们将模式匹配算法分为两种，一种是单模式匹配，还有一种是多模式匹配。单模式算法中最经典的是跳跃式配算法，其在匹配的过程中能够自动的跳过不许匹配的字符。而多模式算法中最经典的是AC算法，这种算法在执行过程中不会受到模式长度以及文本特征的影响，因此使用的比较广泛。

1 双向AC算法的工作流程

双向AC算法在运行的过程中，首先进行的工作就是对模式串进行预处理，并且在处理的过程中生成正向、反向两种树状有限状态自动机，其在匹配的过程中由正向、反向自动机分别从中间向左右两侧扫描，从而将所有的模式串匹配出来。

1.1 模式串集合的预处理过程

进行模式串集合的预处理工作时，相关工作人员的主要工作就是将模式串集合转换成正向和反向有限自动机。在这个阶段，工作人员需要注意的是将正向有限自动机与AC算法结合，从左向右进行扫描。另外，在预处理的过程中，首先进行的就是对Goto函数，与此同时注意生成一部分Output函数，工作的时候从0开始，对字符的顺序及重复性进行考虑，同时增加一些新的状态及路径，直到将所有的模式串都处理完。另外，在处理模式串的过程中，还应该将其状态进行记录，使整个算法能够有条不紊的进行。

1.2 AC算法的文本匹配过程

AC算法在进行的过程中，文本串及模式串集合一般情况下是已经给定的，因此工作人员在匹配的过程中就应该将文本串的中心点作为基础，而匹配过程中的重复区域使用最长模式串充当，并且将正向和反向匹配的起点确定下来，将正向处理过程与反向处理过程进行对比，使AC算法的文本匹配过程能够顺利的进行。

1.3 双向AC算法在Snort系统中的使用

双向AC算法在當今的社会中使用的十分广泛，其在Snort系统中的应用十分的普遍。将其应用在Snort系统中能够精确的完成实时流量分析以及网络的测试，除此之外还能够完成协议分析、内容查找以及匹配等工作。还有一点最重要的是双向AC算法在Snort系统中的使用能够完成最后的模式匹配，提前发现数据包中可能含有的入侵信息，避免系统受到不良的侵害。

2 系统的测试与分析

AC算法在使用的过程中，为了保证其安全性，相关的工作人员还应该对其进行测试。一般情况下，工作人员对其进行测试的时候通常是与BM算法、WM算法以及原始的AC算法进行比较。在本文中，我们主要将一台PC作为模拟攻击主机作为例子进行说明。一般情况下，发送攻击封包的时候主要由仿真攻击软件Tcpreplay进行，在检测DEFCON录制的封包数据的时候使用Snort V2.6规则集中的6718条规则，并且在测试的时候要分别以同的规则数和算法去测试，同时还应该对不同算法下的系统入侵检测侵效率进行统计。一般情况下，工作人员对其进行检测的时候通常是在Snort主机为CPU Intel CORE 2DUO 3.0GHz、内存2G DDRIII，操作环境为Windows2000server的环境下进行，之所以选择在这种环境下测试，最主要的原因就是因为在这种环境下AC算法运行比较稳定，因此检测的结果更加的稳定，得到的数据具有更高的信服力。

另外，在检测的过程中相关工作人员还需要注意，如果在检测过程中使用的TCPreplay，那么第一次在攻击端使用DEFCON数据包的大小为24.5MByte，其内部含有20笔攻击特征。在这20笔攻击特征中，封包传输协议TCP占了百分之八十二，UPD占百分之十五，而ICMP只占了百分之三，并且在进行的过程中其是以8000个每秒的速度发送到Snort主机上的，Snort则以14000个每秒的速度进行封包统计。除此之外，为了避免进程调度对检测带来干扰，每一次检测的数据都是取十次检测的平均值，这就能够有效的避免数据的不准确性以及随机性，使实验数据更加的具有说服力。

相关的工作人员通过进行一系列的实验能够看出，随着规则数的不断增加，每一次实验中使用到的算法都具有效率比较低的情况，但是通过使用多种算法进行对比能够得出AC算法的稳定性要远远的高于其他的算法，使用发现攻击即停止匹配方式进行检测的时候，双向AC算法处理的数据量往往是一般算法的1.5倍。通过分析，AC算法之所以具有更高的效率，最主要的原因就是其将文本串分为两个部分，双向对文本进行处理。但是需要注意的一点是，在使用的过程中由于其需要同时建立正向和反向状态机，所以占用的空间相对其他的算法来说就比较大，在这种情况下，这种算法就不能使用到内存资源比较小的嵌入式入侵检测系统当中。

3 结束语

从上面文章的描述中国我们就能够知道，双向AC算法在最近的几年取得了突破性的进步，并且通过一系列的测试能够知道，AC算法的性能要远远优于其他的算法，AC算法的使用不仅能够与多模式匹配算法进行结合，还能够优化时空开销。因此相关的工作人员必须对其进行足够的重视，并且投入更大的精力对其进行研究，只有这样才能够使其获得进一步的发展，让其成为世界范围的领导者。

（通讯作者：潘华伟）

参考文献

[1]张庆平.一种基于Snort的入侵检测系统的实现和应用[J].计算机应用与软件，2016（08）：134-137.

[2]高平丽，任金吕.基于Snort的入侵检测系统的分析与实现[J].计算机应用与软件，2016（03）：108-111.

[3]杨超.双向AC算法及其在入侵检测系统中应用[J].计算机系统应用，2015（03）：222-225.

[4]宫正.入侵检测系统中模式匹配算法的改进及应用[J].计算机系统应用，2013（12）：96-99.

[5]王奇敏.基于入侵检测系统的正则表达式匹配引擎设计[D].杭州：杭州电子科技大学，2014（08）：13-17.

[6]刘鑫.网络入侵检测系统中模式匹配算法的应用研究[D].大连：大连海事大学，2013（06）：88-91.

作者简介

潘华伟（1990-），男，安徽省人。湖北工业大学计算机学院硕士研究生。研究方向为网络防火墙中多模式匹配算法的应用研究。

作者单位

1.湖北工业大学计算机学院 湖北省武汉市 430068

2. 武汉软件工程职业学院计算机学院 湖北省武汉市 430205