论文部分内容阅读
正则表达式(regular expression),简称regex,被广泛的应用在计算机科学的各个领域。在许多应用模式匹配的场景里,匹配一定特征规则约束的文本或字符串信息时采用正则表达式作为匹配模本通常是一个高效快速的方法。正则表达式通过事先约定好的特定规则,通过一个简单的模本(pattern),实现对任意一个符合对应正则表达式规则的字符或字符串等数据信息的识别匹配。正则表达式有许多应用场景,常用的开源系统Unix/Linux中正是采用正则表达式作为文本识别匹配的主要工具。信息网络的建设随着当今信息时代的飞速发展全世界广泛的铺开,一个万物互联的全链接的社会正在形成。网络技术带给人类社会便利的同时,也附带了许多不安全信息,对社会和个人的生活带来了许多潜在的危险。面对数据量巨大的网络数据,为了防范网络上的危险信息,单纯通过标记指定具体特征的危险元素,识别效率低下,很难保证网络的安全。在网络完全入侵检测系统中采用正则表达式取代传统的固定匹配来识别一些危险负载是一种更为高效的方式。在时下主流的网络安全入侵检测系统,例如入侵检测系统(IDS)等中,都是采用正则表达式作为模本的匹配方案,通过软件实现正则匹配引擎,实现对已知危险特征的信息的识别过滤。然而随着网络数据的极速膨胀加上机器学习的兴起,如今网络上主流的基于CPU计算处理能力的软件正则匹配引擎越发不能满足现实应用的需求,尤其是在服务器端或数据中心等数据吞吐率高的应用场景中。如何对提高正则匹配的效率成为网络完全入侵检测系统迫切需要解决的问题。随着机器学习等基于海量数据的计算机科学的发展,许多学者提出了对现有的软件平台进行硬件化改造,通过硬件加速提高目标系统对输入数据处理的能力。在硬件加速技术领域,从GPU到FPGA甚至专用的集成电路(ASIC)等硬件加速引起了许多的广泛学者的研究。对于给定的正则集合,构造对应正则匹配硬件引擎意味着对规则集合中每一个正则表达式都需要构造一个有限自动机。如何快速的实现这个自动机构造过程,是实现该技术现实应用的关键。早在上个世纪,就有学者已经对正则表达式对应的硬件电路模型开展了前期的研究。在前人的研究基础上,常见的正则表达式匹配单元硬件电路模型已经建立起来。近些年,国外甚至已经有公司做出了专用的正则匹配硬件产品。目前为止,国内对正则表达式硬件匹配方案研究还处于相对初级阶段,部分研究者仅对正则匹配的基础算法进行过研究,在实际应用方面还没有突破。随着大数据时代的到来,越来越来的场景对专用正则表达式硬件电路的需求会逐步增加。本文基于上文所描述的现状,在前人对正则匹配算法研究的基础上,改进原有算法(MY算法)的标记方式,设计出基于非确定有穷自动机(NFA)方案的能够快速在FPGA上部署任意给定正则表达式集的自动编译器。并且本文所设计的编译器在很大程度上丰富了该编译器所支持的正则规则,实现对PCRE常见正则规则的覆盖。且本编译器模块规则处理函数功能划分清晰独立,能够方便后期根据用户指定的特殊规则丰富编译器的规则集合。本文中所设计的硬件编译器,可以自动将正则表达式集合中的正则表达式编译成Verilog形式的RTL代码,在末端采用最通用的正则引擎结构,因此只利用了 FPGA上的逻辑资源。在编译器的正则分析流程和模块构造流程中,本编译器采用了相互独立的两个模块,方便以后对编译器的升级,用更新的正则引擎架构来构造更高性能的匹配引擎来应对未来的现实需求。在主频为3.3GHz的inteli5-4590处理器,4G内存的个人计算机上进行实验,本编译器处理包含数千条正则表达式的大规模规则集合的时间开销不到15秒,并且能同时在最终结果中生成包含任一符合引擎匹配规则的测试字符串和对应的仿真测试文件。