龙源期刊网httpwwwqika
comc

基于FPGA的正则表达式匹配引擎设计
作者：王奇敏李训根赵海斌来源：《电子世界》2013年第01期
【摘要】为了提高硬件正则表达式匹配引擎的吞吐率和状态信息存储效率，设计了一种可以多字节并行处理的正则表达式匹配结构，引入了“失效状态”的概念，并且结合BloomFilter的思想，对状态机进行了过滤和分类匹配。最后在FPGA上进行了验证和测试，结果表明，该匹配引擎有效节约了状态信息存储所需的空间，提高了正则表达式的匹配速率。【关键词】正则表达式；并行处理；BloomFilter；FPGA1引言基于模式匹配的入侵检测系统是将入侵的行为和手段表达为一种模式和特征，然后检测网络上的数据是否与既定的模式相匹配。正则表达式匹配是模式匹配的一种，因其丰富和灵活的表达能力在模式匹配中得到广泛应用。最初的正则表达式匹配引擎大多是基于软件的，但是通用处理器的发展远远跟不上网络数据流量的增长。基于软件的正则表达匹配引擎的吞吐率越来越跟不上日益增长的网络数据流量，所以基于硬件的正则表达匹配引擎逐渐成为国内外学者研究的热点。自1982年Floyd和Ullma
1首次在硬件上实现一个分层的NFA模型起，正则表达式的硬件匹配技术已得到了长足地发展。Sidhu和Prasa
a2设计了针对正则表达式中“或”、“循环”、“连接”3个基本操作的专用电路，并基于基本操作提出了一个NFA专用匹配电路结构。ChristopherLHayes等人提出了一种能够减少存储空间且能够有很高匹配速率的正则表达式匹配结构。国内的学者也研究出了不少高性能的正则表达式匹配引擎。清华大学的张伟5等人提出了一种硬件四级流水线的多正则表达式匹配结构；张树壮6等人提出了一种基于猜测验证的正则表达式匹配结构。目前，正则表达式匹配的硬件实现方法主要有两种：基于纯硬件专用匹配电路和基于存储器查询。前者的特点是占用资源比较少，不需要大容量存储器，匹配速度快，但缺点同样明显，即重构性差，只能针对特定的正则表达式，有局限性。基于存储器查询的方法可以解决前者的不可重构性和局限性的问题，但是它需要大容量存储器的支持。并且，存储器访问频率的限制和大量状态信息的存储已成为基于存储器查询的正则表达式匹配引擎性能提高的瓶颈。本文在前人研究的基础上，利用硬件的可并行特点，设计了一种可以多字符同时处理的正则表达匹配结构。并且结合Bloomfilter的思想，对状态机进行了过滤和分类匹配，引入了“失效状态”的概念，在一定程度上解决r