基于FPGA的正则表达式匹配引擎设计

时间:2022-08-17 10:11:28

基于FPGA的正则表达式匹配引擎设计

【摘要】为了提高硬件正则表达式匹配引擎的吞吐率和状态信息存储效率,设计了一种可以多字节并行处理的正则表达式匹配结构,引入了“失效状态”的概念,并且结合Bloom Filter的思想,对状态机进行了过滤和分类匹配。最后在FPGA上进行了验证和测试,结果表明,该匹配引擎有效节约了状态信息存储所需的空间,提高了正则表达式的匹配速率。

【关键词】正则表达式;并行处理;Bloom Filter;FPGA

1.引言

基于模式匹配的入侵检测系统是将入侵的行为和手段表达为一种模式和特征,然后检测网络上的数据是否与既定的模式相匹配。正则表达式匹配是模式匹配的一种,因其丰富和灵活的表达能力在模式匹配中得到广泛应用。最初的正则表达式匹配引擎大多是基于软件的,但是通用处理器的发展远远跟不上网络数据流量的增长。基于软件的正则表达匹配引擎的吞吐率越来越跟不上日益增长的网络数据流量,所以基于硬件的正则表达匹配引擎逐渐成为国内外学者研究的热点。

自1982年Floyd和Ullman[1]首次在硬件上实现一个分层的NFA模型起,正则表达式的硬件匹配技术已得到了长足地发展。Sidhu和Prasanna[2]设计了针对正则表达式中“或”、“循环”、“连接”3个基本操作的专用电路,并基于基本操作提出了一个NFA专用匹配电路结构。Christopher L.Hayes等人提出了一种能够减少存储空间且能够有很高匹配速率的正则表达式匹配结构。国内的学者也研究出了不少高性能的正则表达式匹配引擎。清华大学的张伟[5]等人提出了一种硬件四级流水线的多正则表达式匹配结构;张树壮[6]等人提出了一种基于猜测―验证的正则表达式匹配结构。

目前,正则表达式匹配的硬件实现方法主要有两种:基于纯硬件专用匹配电路和基于存储器查询。前者的特点是占用资源比较少,不需要大容量存储器,匹配速度快,但缺点同样明显,即重构性差,只能针对特定的正则表达式,有局限性。基于存储器查询的方法可以解决前者的不可重构性和局限性的问题,但是它需要大容量存储器的支持。并且,存储器访问频率的限制和大量状态信息的存储已成为基于存储器查询的正则表达式匹配引擎性能提高的瓶颈。本文在前人研究的基础上,利用硬件的可并行特点,设计了一种可以多字符同时处理的正则表达匹配结构。并且结合Bloom filter的思想,对状态机进行了过滤和分类匹配,引入了“失效状态”的概念,在一定程度上解决了以上的两个瓶颈问题。

2.设计原理

2.1 多字符的并行处理

假设,待检测的字符串为“FiniteAu-tomata”,模式串为“.*Auto”。那么模式串“.*Auto”的DFA如图1所示。

一般情况下,必须把字符串进行逐个匹配,设一次状态转移需要消耗的时钟周期为M,那么共需消耗M*N(N为字符串长度,这里N=14)个时钟周期。现在把字符串平均分成两段,L1=FiniteA和L2=utomata,如表1所示。

然后进行如下处理,第一步,让L1和L2从0状态开始进行并行匹配,并且记录L2达到过的状态;第二步,以L1的末状态为首状态,继续对L2进行匹配,并且每到达一个状态与第一步中L2在该字符到达的状态比较。如果两个状态相同,那么就可以跳过后面的字符,直接开始下一个字符串的匹配。

这种方法是正确的。①当模式串只包含在L1或L2中时,第一步就可以把模式串匹配出来。②当模式串被拆散在L1和L2中的情况下,因为第二步继续匹配的起始状态为L1的末状态,所以同样能匹配出来。③假设,第二步中找到的相同状态为Si,因为对于同一DFA,在同一状态下,输入同一个字符,能到达的下一个状态是确定的[7],所以在Si以后的状态在第一步的L2中都已到达过,可以直接跳过。

从表1可以看到,用此方法来处理字符串“FiniteAutomata”时,消耗的时钟周期为11*M,比直接逐个处理的方法节省了22%的时间。当用正则表达式状态机来匹配网络数据流时,匹配的概率是很低的,所有的正则表达式开始于一个单一的初始状态,大量状态转换会回到初始状态或与初始状态相邻的状,且许多状态接受同样的字符会转移到相同的目的状态[7]。因此,当进行第二步处理时,有很高的概率可以较早得到达相同状态。最好情况下,把待处理的字符串分成两段,速度就可以提高一倍;分成四段,速度就可以提高三倍。

2.2 “失效状态”的概念

当正则表达式编译成DFA状态机时,会引起状态爆炸,状态信息的存储面临着巨大地挑战。本文对状态信息的存储进行了优化,引入了“失效状态”的概念,有效地节省了状态信息存储占用的空间。先举一个简单的例子,如表2所示为“AB.*CD”的状态转移表。状态2就是由“.*”引入的状态,也是当多条表达式编译时引起状态爆炸的地方。如果我们对每个状态的每条转移都进行存储,状态2就需要有256条有效转移,如表2所示。

现在我们引入“失效状态”的概念,即把每个状态有效转移条数最多的那个下一状态定为此状态的“失效状态”。这样只需存储“失效状态”,不存储大量的转移信息。对于表2所示的例子,状态2的“失效状态”就是状态2,简化后的状态转移表就如表3所示,空格的地方就不需要再存储,明显地减少了状态信息存储所需的空间。

单独编译一条正则表达式时不存在状态爆炸的问题,但当多条正则表达式一起编译成一个DFA时,有些元字符就会引起状态爆炸:“.*”会导致DFA状态数的线性增加,“.{}”和“[]{}”会导致DFA状态数的指数级增加,而每个状态又会包含大量的转移信息。snort规则库中14%的规则包含“.*”,1%的规则包含“.{}”和“[]{}”[7],“失效状态”的引入可以很大程度地节省状态信息的存储空间。

2.3 Bloom Filter和分类匹配

Snort规则库中的正则表达式的DFA需要占用庞大的存储资源,FPGA内部的存储资源有限,而过多地访问外部存储器成为硬件匹配结构提高吞吐率的瓶颈之一。正则表达式匹配应用于网络入侵检测系统时,具有以下特点:①在大量的网络数据流中,存在入侵行为的概率是很低的;②当正则表达式规则库编译成一个DFA进行匹配时,所有的正则表达式开始于一个单一的初始状态,大量状态转换徘徊在初始状态或与初始状态相邻的状态,以及一些特殊的状态,这些状态只是DFA少量的一部分,需要的存储空间也比较小,而大量的远离初始状态的状态被访问到的概率很小,且需要大量的存储资源。

Bloom Filter是一种基于多个哈希函数映射,复杂度很小的随机数据结构[10]。用Bloom filter结构可以大大减少系统访问外部存储器的次数,并且高效利用片上资源。但是Bloom filter的使用必须要控制假阳性误判率和匹配概率,误判率的公式为:

其中k为哈希函数的个数,m为存储空间的位数,n为存入的元素个数。

基于以上考虑,本文设计了一种内部匹配与Bloom Filter并行的匹配结构,如图2所示。

我们对snort规则库中的正则表达式的DFA进行了统计和分类,把适量浅层次和被访问概率比较大的状态信息存在片上ram,大量深层次的被访问到概率小的状态信息存在外部RAM。状态转移表内存储的信息如图3(a)所示,Bloom Filter内存储的信息如图3(b)所示。Bloom Filter与内配匹配模块并行运行,当内部匹配模块和Bloom Filter都不匹配时就可以直接跳转到失效状态,当内部匹配模块匹配时就可以直接查询到下一状态,当内部匹配模块不匹配,但Bloom Filter出现匹配是就需查询外部RAM。这样可以大大减少系统访问外部RAM的次数,同时充分利用了片上资源。

3.总体结构设计

系统的总体方案设计如图4所示。在数据输入模块用以太网接口接受数据,用两个RAM组对输入数据缓存,进行乒乓操作,实现内部数据的无缝连接。内部状态转移表和Bloom Filter信息的存储都用运了hash映射,使信息存储更加紧凑,采用的hash函数为H3哈希函数组。理论上在多字符并行处理时需要多个状态转移表与之对应,但是基于实际考虑,本文设计的匹配结构需要访问片外状态转移表的频率很低,所以本文在FPGA内部设计了一个多路的虚拟状态转移表,而只使用一个片外RAM,在不怎么影响系统性能的前提下,节省系统所需的资源。

4.性能测试

在现有实验条件下,我们在FPGA上对系统的综合性能进行了模拟验证和测试,并且与现有的方法进行了对比。使用的FPGA是Altera Cyclone II EP2C35F484C8,片外RAM是Micron的SDRAM,系统时钟为50MHZ。测试结果如表4所示。

p_seed表示输入字符对状态机中深层结点的访问概率;L表示并行处理的字符数,即输入字符串的分段数。Hybrid-FA是参考文献[6]中作者提出的一种比较先进的正则表达式匹配方法。从图中可以明显看出,在系统频率为50MHZ时,一般情况下(p_seed=3%),本文设计的匹配引擎的吞吐率明显高于文献[6]提出的匹配方法;在比较极端的情况下(p_seed=50%),本文设计的匹配引擎也能较好地保持匹配速度。当系统频率达到250MHZ,L=4时,该匹配引擎的最高吞吐率就能到达1.63Gb/s。另外,经测试与对比,本文设计的正则表达引擎的存储效率也有一定的提高。

5.结束语

本文针对当前正则表达式匹配的硬件实现所遇到的两个瓶颈问题,设计了一种时空高效的正则表达式匹配结构。该匹配系统的匹配速度快,可重构,配置灵活。只要更新存储器里的状态信息就可以匹配新的正则表达式。在正常情况下,只要提高L的值,增加内部匹配模块的信息量就能提高系统的吞吐率。本系统的局限性在于当受到恶意攻击的时候,系统性能将会有所下降,这也是需要进一步考虑的地方。另外,本文虽然提出了一种提高状态信息存储效率的方法,但只做了理论分析和简单的定性测试,未给出定量的测试结果,这也是本文进一步要开展的工作。

参考文献

[1]Floyd R W,Ullman J D.The Compilation of Regular Expressions into Integrated Circuits[J].Journal of theACM,1982,29(3):603-622.

[2]Sidhu,R,Prasanna,V.K.Fast Regular Expression Matching using FPGAs:the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines,2001[C].USA:Rohnert Park,California,2001:227-238.

[3]Joao B,Ioannis S,Cardoso J M,etal.Regular expression matching for reconfigurable packet inspection:Proceedings of IEEE International Conference on Field-Programmable Technology(FPT),2006[C].Thailand:Bangkok,2006:119-126.

[4]Tsern-Huei Lee.Hardware Architecture for High-Performance Regular Expression Matching[J].IEEE TRANSACTIONS ON COMPUTERS,2009,58(7):984-993.

[5]张伟.支持多正则表达式匹配的硬件结构[J].清华大学学报(自然科学版)2009,49(10):1704-1707.

[6]张树壮.一种面向网络安全检测的高性能正则表达式匹配算法[J].计算机学报,2010,33(10):1976-1986.

[7]YAO YUAN.Survey on storage-oriented regular expressions matching algorithms[J].Journal of Computer Applications,2009,29(12):3171-3173.

[8]Harmapurikai D,Lockwood S.Fast and scalable Pattern Matching for Network instrusion Detection Systems[J].IEEE,2006,24(10):1781-1792.

[9]Michela Becchi.A Hybrid Finite Automaton for Practical Deep Packet Inspection:CONEXT 2007[C].New York,NY,U.S.A.2007.10-13.

[10]程澜绵,周峰.基于Bloom Filter和概率分发队列的P2P网络快速查找算法[J].计算机科学,2012,39(5):57-61.

上一篇:对现代信息技术辅助高中数学课堂教学的几点思... 下一篇:浅谈如何提高化学课堂教学的实效性