一种实现网络入侵检测的高效算法及其实现架构

余 伟，田新志，陈 丹

(1.西安思源学院 基础部，西安 710038;2.西安思源学院 电子信息工程学院，西安 710038；3.西安空间无线电技术研究所，西安 710100)

0 引言

随着互联网发展成为一个巨大的全球开放网络，对互联网的攻击从未停止过，从黑客攻击、邪恶的探测攻击到网络诈骗，这些攻击甚至无需资金投入就能实现，而且可以在世界上任何地方发起；最常用的网络保护系统是防火墙和网络入侵检测系统(NIDS,network intrusion detection system)[1-2]。它们安装在网络的边界，以检查和监控流入和流出的网络流量。防火墙只执行网络的第3层或第4层过滤，基于数据包头部来处理数据包。而NIDS不仅提供第3层或第4层过滤，还提供了第7层过滤。NIDS搜索数据包头部和有效载荷以识别攻击模式(或签名)。因此，NIDS可以检测和阻止网络上传播的有害内容，识别出攻击的模式，然后采取行动终止连接或向系统管理员发出警报。

随着互联网的迅速发展和攻击数量的剧增，NIDS的设计也已成为一个巨大的挑战。现有的基于软件的解决方案无法实现内存高效利用和大的吞吐量，因此，必须采用硬件辅助。基于硬件的NIDS高速字符串匹配方案主要分为3大类：基于三态内容寻址存储器(TCAM,ternary content addressable memory)、基于动态/静态随机存取存储器(DRAM/SRAM,dynamic/static random access memory)，以及基于SRAM逻辑的方案。尽管基于TCAM的引擎可以在一个时钟周期内检索结果，但它们功耗太高，并且其吞吐量受到TCAM相对较低的速度限制；基于SRAM和SRAM逻辑的解决方案需要多个周期来执行一次搜索。因此，通常采用流水线技术来提高吞吐量。同时，基于SRAM的方法受到内存限制，导致低效的内存利用，从而限制了所支持的字典大小。此外，由于I/O管脚数量的制约，在这些架构中很难采用外部SRAM。由于这两个限制，即使最先进的基于SRAM的解决方案都不能很好地扩展以支持更大的字典。这种可扩展性一直是硬件中实现NIDS的主要问题。

一般来说，基于硬件的字符串匹配架构可以分为3类：TCAM、流水线非确定有限自动机(NFA, non-deterministic finite automaton)和流水线确定有限自动机(DFA,deterministic finite automaton)。

在文献[3]提出的基于TCAM的架构中，利用未使用的TCAM记录来提高搜索性能，选择性地生成TCAM表项来合并重叠的匹配条件，从而大大减少访问TCAM表项的数量。但整个字典都存储在TCAM中，它对任何输入都有确定的查找时间。这种架构的优点是内存效率高(接近1字节/字符)和更新机制简单，但实现的吞吐量低；在文献[4-6]提出的流水线NFA字符串匹配架构中，把所有给定的字符串模式组合起来构建一个NFA，把NFA实现为一个流水线网络，并行地匹配多个字符串模式。这些设计尽管能够实现8～10 Gbps的吞吐量，但主要缺点是缺乏灵活性和所支持的字典相对较小；文献[7]提出的字段合并(FM,field merge)NFA架构，将每个输入字符划分为k个位字段，并构造一个树结构的NFA。然后，把字典“垂直地”划分为正交的位字段，每个位字段用于构造一个树形结构的NFA，称为部分状态机(PSM,partial state machine)。此外，在PSM的构造过程中，维护一个逐级辅助表(ATB,auxiliary table)，以将每个完全匹配状态唯一地映射到同一级别上的一组部分匹配状态。这种设计的优势在于，通过采用相对较小的ATB，可以简化流水线遍历和PSM的输出合并。字段合并NFA完全基于内存，通过更新内存内容可以很容易地执行动态字典更新，但其内存效率依赖于字典，不同字典之间的差异很大；文献[8-9]提出的位分割(BS, bit split)DFA架构基于[10]的算法。它将N个模式的字典树转换为有O(N)个状态的DFA，对于每个字符需要O(1)计算，无论字典大小。然而，状态转换表中的有效(非零)状态通常非常稀少，这就导致了大量的内存浪费，使得内存带宽和延迟成为这种架构的瓶颈；为了提高内存效率，文献[11]提出了位分割算法，该算法将一个完整的DFA分割成几个分裂状态机。分裂状态机中的每个状态都维护一个部分匹配向量，以将状态映射到一组可能的匹配。尽管这种设计提高了内存效率，但对于具有数千个状态的大型字典来说，从DFA构建分裂状态机的成本非常高。尽管可以优化位分割方法的性能，但这样的优化需要为每个组规划资源，并使动态字典更新更加困难；可变步幅(VS, variable-stride)多模式匹配架构[12]也是一种基于DFA的方法，其主要思想是可以一步扫描可变数量的字符。尽管这是一个ASIC实现，但它实现了较高的内存效率，并且可以移植到FPGA平台。但这种设计的吞吐量较低，因为它高度依赖于字典。

上述研究的主要问题是低内存效率、低吞吐量和相对较小的支持字典。此外，这些设计或多或少依赖于字母表的大小，随着字母表大小的增加，内存效率会降低；另一方面，基于TCAM的方案虽然具有较高的内存效率和可扩展性，但吞吐量低和功耗高。随着模式数据库的增长，这些问题会变得更加严重。

为此，本文提出了一种预处理算法和一种可扩展、高吞吐量、内存高效的大规模字符串匹配架构。由于采用了线性流水线架构，所以具有灵活的扩展性，还能保证固定的延迟。

1 背景知识以及问题定义和记号

1.1 字符串模式匹配

字符串模式匹配(也称为精确字符串匹配或字符串匹配)是NIDS最重要的功能之一，它提供了内容搜索功能。字符串匹配算法是将给定字典(或数据库)中的所有字符串模式与流经设备的流量进行比较。

1.2 问题定义

字符串模式匹配问题可以表述为：给定一个长度为K的输入字符串、一个由全部ASCII字符构成的字母表∑(|∑|=256)和一个由N个字符串模式{S0,S1,…,SN-1}(其字符属于字母表∑)构成的字典，找到并返回给定输入字符串中每个模式的所有出现(如果存在的话)。

1.3 记号

图1所示为表1示例字典对应的前缀树[13-14]表示。给定一个字典和相应的前缀树表示，定义以下术语和记号：

图1 表1示例字典的前缀树

表1 事例模式数据库(字典)(最大模式长度为8)

1)字符串、模式或签名：标识任何恶意内容的独特特征；

2)*(星号)：包含一个空的任何字符串；

3){n}：重复前一项n次，其中n是一个正整数；

4)|S|：字符串S的长度(以位表示)，例如当每个ASCII字符占用8位时|abcd|=32；

5)S1是S2的前缀当且仅当S2=S1(，如S1=ab，S2=abcd，S1说成是S2的前缀孩子，S2是S1的前缀父亲。为简单起见，分别用孩子和父来表示前缀孩子和前缀父亲。在S1=S2时，S1是S2的前缀，反之亦然；

6)S1和S2是不同的当且仅当S1不是S2的前缀且S2不是S1的前缀，否则，认为它们是重叠的。所有模式对都是不相交的一组模式称为不相交模式集；

7)S1

8)字符串S的二进制表示记为BS，将S的所有字符转换成其相应的ASCII值即可得到；

9)字符串S的范围表示用L位(L>|S|)表示为RS=[RSL,RSH]，其中RSL=BS0{n}和RSH=BS1{n}，满足n=L-|S|。在L=|S|时，RS=[BS,BS]；

10)任何节点(从前缀树的根到该节点的路径表示字典中的模式)都称为模式节点。如果一个模式位于一个叶子节点上，则它就称为叶子模式节点，否则，就称为非叶子模式节点。

2 字符串匹配算法

2.1 前缀属性

字符串匹配可以构建为前缀匹配问题。考虑两个字符串SA和SB，在L位数空间(Ω=[0{L},1{L}]中，L≥max(|SA|,|SB|)，令nA=L-|SA|，nB=L-|SB|和nAB=abs(|SB|-|SA|)=abs(nB-nA)。下面給出用作为本文研究基础的属性。

属性1：给定两个不同的字符串SA和SB，如果|SA|=|SB|，则SA和SB不重叠。

属性2：给定两个不同的字符串SA和SB，如果它们重叠，则其中一个必须是另一个的前缀。

属性3：给定两个不同的字符串SA和SB，如果SA是SB的前缀，则SA

2.2 叶子-追加算法

对于字符串匹配引擎来说，树搜索算法是一个很好的选择，因为查找延迟不依赖于模式的长度，而是取决于字典中模式的数量。然而，为了采用树搜索算法，需要对给定的模式集进行处理，以消除模式之间的重叠。

对此，本文提出一种叶子-追加算法来分离模式。算法以前缀树作为输入，输出一组不相交的模式。所有孩子(或非叶子)模式都与它们的父亲(或叶子)模式合并。令L为模式的最大长度，每个父模式都有一个长度为L位的匹配向量(MV, matching vector)附属于它。匹配向量是一个二进制字符串，指示父模式中包含多少个子-父模式以及它们是什么。位置i的值为1意味着有一个长度为i字节的子-父模式，从父模式的开头开始。例如，如果父模式是andy，且它的匹配向量是0111，则包含3个子模式：an、and和andy，分别对应于位置2、3和4上的1。一个模式可以是多个父模式的子模式(前缀)。图2所示为两个父模式andy和between的示例合并。前缀树是从一组给定模式构建的。树的每个节点包括：1)一个叶子位；2)一个模式位；3)一个模式；4)一个匹配向量。叶子位和模式位分别确定节点是叶子节点还是模式节点。叶子-追加算法按顺序遍历前缀树，并将非叶子模式推到它们的叶子模式，图3所示为图1的前缀树在执行叶子-追加算法后的结果。一旦前缀树被附加叶子后，就收集叶子及其相关的匹配向量，以形成一个不相交的模式集。表2所示为表1示例字典在叶子-追加算法后的字典。

图2 示例合并

图3 叶子-追加树

表2 表1示例字典在叶子-追加算法后的模式

2.3 二叉搜索树字符串匹配算法

本节提出一种基于完全二叉搜索树(BST, binary search tree)[15]的高效内存数据结构。二叉搜索树算法是一种在排序列表中查找特定元素的技术。

给定字典经过叶子-追加，并提取叶子模式及其匹配向量，叶子模式用于构建BST，BST中的每个节点包含一个模式和一个匹配向量。构建了相应的BST之后，根据每个节点的比较结果，通过左遍历或右遍历来执行字符串匹配。如果输入字符串小于或等于该节点的值，则将其转发到该节点的左子树，否则转发到右子树。

为表2中的不相交模式集构建的完整BST示例如图4所示，示例中考虑的是最大长度为8个字符的模式。完整的BST映射如下：每一层的节点都存储在一个连续的内存块中。令x表示节点A的索引值。A有2个孩子节点，索引值为2x(左孩子)和2x+1(右孩子)。在以2为基的数字系统中，2x={x,0}和2x+1={x,1}，其中{}表示串接。采用这个内存映射，不需要将孩子指针存储在每个节点上，这些指针是通过简单地将当前节点的地址与比较结果位串接起来显式地实时计算的。

图4 表2中不相交模式集的示例完整BST

输入流用8个字符的窗口进行处理，每次前进1个字符。例如有一个8个字符的输入字符串anchorer到达，匹配状态向量(MSV,matching status vector)被重置(MSV=00000000)。在树的根(P12)，将输入与节点的模式car进行比较，得到不匹配和“less than”结果。输入字符串向左遍历。在节点P11，它与模式beat进行比较，再次得到相同的结果。然后输入字符串被转发到左边。在节点P3，输入字符串匹配节点的模式andy，得到一个匹配和一个“less than”结果。当输入字符串与孩子模式an匹配时，MSV的第二位被设置为MSV=01000000。输入字符串然后遍历到左边。在节点P5，输入字符串匹配节点的模式anchor且MSV=01000010，这就是最后结果。

注意，一个输入字符串的所有匹配模式必须是最长匹配模式的前缀。因此，叶子-追加步骤确保这些模式包含在最长模式的同一节点中。如果输入字符串SI到达该节点，则应该找到所有匹配模式，即输入字符串SI到达了包含最长匹配模式的节点。

2.4 BST字符串匹配算法的内存效率

本节分析采用提出的叶子-追加算法生成的不相交模式集(SDP,set of disjoint patterns)，分析中用到以下记号：

1)L：不相交模式的最大长度(以字节为单位)；

3)NDP：不相交模式的数目；

4)MDP：不相交模式集的大小(以字节为单位)；

5)MBST：采用BST数据结构存储SDP所需内存的大小(以字节为单位)；

每个不相交模式有一个长度为L位(或L/8字节)的匹配向量。MDP和MBST分别根据式(1)和(2)计算，式(3)为BST字符串匹配算法的内存效率：

(1)

MBST=NDP×(L+L/8)=9NDP/8×L

(2)

(3)

2.5 BST级联

图5 BST级联原理的框图

3 实现架构

3.1 总体架构

本文提出一种基于流水线的二叉搜索树来实现可扩展、高吞吐量、内存高效的字符串匹配架构，实现原理框图如图6所示。如上所述，匹配步骤包括(1)模式匹配和(2)标签匹配，分别由模式匹配模块(PMM,pattern matching module)和标签匹配模块(LMM,label matching module)完成。输入数据流一次输入到PMML个字节，输入窗口每个时钟周期前进1个字节。然后，PMM根据模式数据库匹配输入字符串，同时LMM匹配{前缀, 后缀, 匹配向量}组合，以验证长模式并输出匹配结果。临界点是输入窗口的大小L与LMM中的记录数之间的关系。窗口大小L应大于或等于LMM的匹配延迟。因此，L应根据字典的大小来选取。

图6 总体架构原理框图

3.2 PMM架构

流水线用于每个时钟周期生成一个查找操作，以提高吞吐量。流水线级的数量由搜索树的高度决定。树的每一层映射到一个流水线级，流水线级有自己的内存(或表)。级联BST用于提高内存效率。因此，PMM架构中使用了多个BST。

基本流水线和BST的单个级的框图如图7所示。为了利用架构提供的双端口特性，把该架构配置为双线性流水线。这种配置使得匹配速率加倍。在每一级，内存有2组读/写端口，以便每个时钟周期可以输入2个字符串。内存中每个记录的内容包括：(1)一个模式P，(2)一个匹配向量MV和(3)一个模式标签PL。在每个流水线级，有4个数据字段转发自前一级：(1)输入字符串SI，(2)匹配状态向量MSV，(3)内存访问地址Addr和(4)匹配标签ML。转发的内存地址用于检索模式及其存储在本地内存中的相关数据。将此信息与输入字符串进行比较，以确定匹配状态。在匹配的情况下，匹配标签ML和匹配状态向量MSV被更新。比较结果(如果输入字符串大于节点的模式，则为1，否则为0)添加到当前内存地址并转发到下一级。

图7 模式匹配模块及其基本流水线级的架构

在流水线的每一级有一个比较器。它将输入字符串与节点的模式进行比较，并用节点的匹配向量来生成匹配状态向量。输入包括：(1)一个输入字符串SI，(2)一个模式P，(3)一个匹配向量MV，(4)一个模式标签PL和(5)一个匹配标签。输入字符串SI和模式P进入到字节比较器，比较器执行两个输入的字节比较。结果(M7-M0)输入到匹配向量解码器。解码器的输出与节点的匹配向量进行与(AND)，然后结果与字符串比较器的输出进行与(AND)，比较器将模式标签和匹配标签进行比较，以生成一个8位匹配向量(MSV)。

3.3 LMM架构

LMM架构几乎与PMM架构相同。不同之处在于(1)只有一个BST，(2)每个记录没有匹配向量和(3)不再需要匹配标签字段。匹配操作实际上更简单，因为它不需要处理重叠问题。此外，每个节点中搜索键的大小实质上更短，使得比较更快。在设计中，用一个完整的BST来搜索标签匹配表。LMM架构及其基本的流水线级如图8所示。

图8 标签匹配模块及其基本流水线级的架构

令Nl表示LMM表中的记录数目。LMM的延迟时间为「log2(Nl+1)⎤。如前所述，输入窗口大小L必须大于或等于LMM的延迟，即L≥「log2(Nl+1)⎤。

3.4 字典更新

字典更新包括2个操作：1)模式删除和2)新模式插入。第一种更新需要删除现有的模式。每个模式可以包括(a)多个模式和(b)仅一个模式。在情形(a)，删除可以通过重置已处理模式的匹配向量的位i来完成，其中i是待删除模式的长度。例如，考虑有匹配向量0111的模式andy。要删除模式 and，第3位设置为0，匹配向量变为0101。在情形(b)，有2种可能方法：惰性删除和完全删除。惰性方法可以采用在情形(a)中描述的相同更新机制来执行。完全删除时，如果树的结构发生变化，则必须重新构建BST，并且必须重新加载每个流水线级的整个内存内容。

在第二种更新中，把新模式插入到现有的字典中。如果新模式有父模式，则只需要更新父匹配向量来包含新模式。如果新模式不是任何现有模式的孩子，则添加一个新节点。

3.5 模块可扩展性

本文设计的架构可以横向扩展，也可以纵向扩展，或二者同时扩展。在横向方向上，可以添加更多的流水线级来支持更大的字典。如果片上存储器的数量不够，则可以将流水线级扩展到外部SRAM；在纵向扩展中，可以多次复制架构。这时，全部流水线有相同的内存内容，并且可以同时匹配更多的数据流。由于每个流水线中的匹配是独立执行的，所以输入流可以在每个流水线中(流内)交叉地匹配不同字符；每个流水线还可以匹配独立的输入流(流间)，以增加总的吞吐量；除了这两种情形外，还可以在两个方向上扩展架构，以支持更大的字典，同时获得更高的吞吐量。

4 性能评价

4.1 实验设置

采用Snort[16]和Rogets[17]用于实验的安全字典。Snort是恶意互联网活动的签名列表，是一种普遍的开源和跨平台NIDS，它采用签名和包头来检测恶意Internet活动。作为一个开源系统，Snort规则由网络安全社区提出，以制定广泛接受和有效的规则集；Rogets是系统黑客通用密码破解者单词列表，该字典通常为系统黑客提供可行的密码和词表，相反，在网络安全社区中用于防止服务器/系统密码被黑。两个实验字典的统计数据如表3所示。

表3 Rogets和Snort字典的统计数据

4.2 内存效率

本节对所提出的字符串匹配算法的内存效率进行评价。两个实验字典的不同段长度值的标签匹配表中的记录数如表4所示。

表4 不同段长度值的标签匹配表中的记录数

如前所述，段长度L需要大于或等于LMM的匹配延迟，所以在设计中用一个完整的BST来实现LMM。因此，标签匹配表中的记录数不应超过2L-1，故分析中采用3个L值(16,20,24)。对于每个L值，采用不同LS∈{4,8,12,16}值的级联BST方法实现PMM。

表5所示为实验得到的结果，其中PMM的内存需求和LMM的内存需求分别表示为MPMM和MLMM(以比特为单位)，对于L和LS的每个组合的总体设计的内存效率表示为ME；可见，当L=24和LS=4时，Rogets和Snort的内存效率都达到了最佳，分别为0.56字节/字符和1.32字节/字符。最大的Rogets和Snort字典分别只需要100 kB和300 kB的片上内存，而先进的FPGA设备需要超过4 MB的片上内存。因此，所提出的架构足以满足NIDS的实际实现。还可看到，Rogets字典有更好的内存效率，因为Rogets的字母表较小为26，而Snort为256。

表5 不同段长度值的Rogets和Snort字典的内存效率

4.3 吞吐量

采用带Virtex-5 FX200T的Xilinx ISE 12.4为FPGA，在Verilog中实现所提出的模式匹配核。表6所示为对于不同模式段长度(以字节为单位)的实验结果。可见，在所有情形下，逻辑资源的数量都很低(不到总资源的15%)。对于24字节的段长度，实现了197 MHz的频率，实现了每个流水线1.6 Gbps的吞吐量，在双流水线架构下，吞吐量达到了3.2 Gbps。

表6 不同段长的实现结果

4.4 与目前先进设计的性能比较

在内存效率和吞吐量方面进行比较。尽管内存效率影响最大支持字典的大小，但吞吐量决定整个设计的处理速度。对于内存效率而言，较小的值表示更好的设计，而对于吞吐量，较大的值表示更好的设计。表7所示为本文设计和目前先进设计的比较结果。这些先进设计方法包括字段合并(FM,field merge)[7]、位分割(BS,bit split)[8]和可变步幅(VS,variable stride)[12]。为了公平比较，对段大小为8字节的整个Rogets和Snort字典计算内存效率，并采用相同的FPGA设备实现。

表7 本文设计、VS、BS和FM的性能比较

可以看到，对于同一字典，本文设计在内存效率和每流吞吐量方面都优于目前的先进设计方法。与最先进的设计FM[7]相比，本文设计实现了超过4倍的内存效率提高，只需要FM的1/4(对于Rogets和Snort来说)内存，同时获得1.4倍的每流吞吐量。与BS设计相比，本文设计只需要BS的1/51(对于Rogets)和1/26(对于Snort)的内存，同时实现1.8倍的每流吞吐量。此外，本文设计的内存效率和吞吐量不依赖于符号集(或字母表)的大小，而对于其他设计，当符号集增大时，它们的性能会显著下降。

5 结束语

本文针对大规模字符串的模式匹配提出了一种叶子-追加算法和二叉搜索树的字符串匹配算法，它可以在不增加模式数量的情况下拆分给定的模式集，还提出了实现该算法的总体架构；实验结果表明，与目前先进的设计相比，本文设计获得了更好的内存效率和吞吐量；在未来的研究中，我们打算改进本文的算法，以在每个时钟周期匹配多个字符，也进一步研究标签匹配模块的替代架构。