基于NFA的正则表达式硬件编译器设计

来源 :南京大学 | 被引量 : 0次 | 上传用户:mumu_lucky
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
正则表达式(regular expression),简称regex,被广泛的应用在计算机科学的各个领域。在许多应用模式匹配的场景里,匹配一定特征规则约束的文本或字符串信息时采用正则表达式作为匹配模本通常是一个高效快速的方法。正则表达式通过事先约定好的特定规则,通过一个简单的模本(pattern),实现对任意一个符合对应正则表达式规则的字符或字符串等数据信息的识别匹配。正则表达式有许多应用场景,常用的开源系统Unix/Linux中正是采用正则表达式作为文本识别匹配的主要工具。信息网络的建设随着当今信息时代的飞速发展全世界广泛的铺开,一个万物互联的全链接的社会正在形成。网络技术带给人类社会便利的同时,也附带了许多不安全信息,对社会和个人的生活带来了许多潜在的危险。面对数据量巨大的网络数据,为了防范网络上的危险信息,单纯通过标记指定具体特征的危险元素,识别效率低下,很难保证网络的安全。在网络完全入侵检测系统中采用正则表达式取代传统的固定匹配来识别一些危险负载是一种更为高效的方式。在时下主流的网络安全入侵检测系统,例如入侵检测系统(IDS)等中,都是采用正则表达式作为模本的匹配方案,通过软件实现正则匹配引擎,实现对已知危险特征的信息的识别过滤。然而随着网络数据的极速膨胀加上机器学习的兴起,如今网络上主流的基于CPU计算处理能力的软件正则匹配引擎越发不能满足现实应用的需求,尤其是在服务器端或数据中心等数据吞吐率高的应用场景中。如何对提高正则匹配的效率成为网络完全入侵检测系统迫切需要解决的问题。随着机器学习等基于海量数据的计算机科学的发展,许多学者提出了对现有的软件平台进行硬件化改造,通过硬件加速提高目标系统对输入数据处理的能力。在硬件加速技术领域,从GPU到FPGA甚至专用的集成电路(ASIC)等硬件加速引起了许多的广泛学者的研究。对于给定的正则集合,构造对应正则匹配硬件引擎意味着对规则集合中每一个正则表达式都需要构造一个有限自动机。如何快速的实现这个自动机构造过程,是实现该技术现实应用的关键。早在上个世纪,就有学者已经对正则表达式对应的硬件电路模型开展了前期的研究。在前人的研究基础上,常见的正则表达式匹配单元硬件电路模型已经建立起来。近些年,国外甚至已经有公司做出了专用的正则匹配硬件产品。目前为止,国内对正则表达式硬件匹配方案研究还处于相对初级阶段,部分研究者仅对正则匹配的基础算法进行过研究,在实际应用方面还没有突破。随着大数据时代的到来,越来越来的场景对专用正则表达式硬件电路的需求会逐步增加。本文基于上文所描述的现状,在前人对正则匹配算法研究的基础上,改进原有算法(MY算法)的标记方式,设计出基于非确定有穷自动机(NFA)方案的能够快速在FPGA上部署任意给定正则表达式集的自动编译器。并且本文所设计的编译器在很大程度上丰富了该编译器所支持的正则规则,实现对PCRE常见正则规则的覆盖。且本编译器模块规则处理函数功能划分清晰独立,能够方便后期根据用户指定的特殊规则丰富编译器的规则集合。本文中所设计的硬件编译器,可以自动将正则表达式集合中的正则表达式编译成Verilog形式的RTL代码,在末端采用最通用的正则引擎结构,因此只利用了 FPGA上的逻辑资源。在编译器的正则分析流程和模块构造流程中,本编译器采用了相互独立的两个模块,方便以后对编译器的升级,用更新的正则引擎架构来构造更高性能的匹配引擎来应对未来的现实需求。在主频为3.3GHz的inteli5-4590处理器,4G内存的个人计算机上进行实验,本编译器处理包含数千条正则表达式的大规模规则集合的时间开销不到15秒,并且能同时在最终结果中生成包含任一符合引擎匹配规则的测试字符串和对应的仿真测试文件。
其他文献
钢筋混凝土(RC)空心截面墩柱在高桥墩中得到广泛应用,其抗震性能已有较多研究,但尚未见到其抗爆性能研究的公开报道。鉴于桥梁结构遭受恐怖袭击的潜在风险和RC空心截面桥墩抗
在后基因组时代,蛋白质组学是一个非常重要的研究内容。蛋白质作为一种基础物质是直接参与了人类的生命活动,通常需要通过进行翻译后修饰(Post-translational modifications,
现代建筑工程不断向超高、重载、大跨和巨型方向发展,常规的建筑材料和结构形式已经不能完全适应这种发展的需要。本文充分利用“组合”这一概念,在型钢混凝土结构(Steel Rei
本次翻译实践的语料选自印度作家阿米塔夫·高希的科幻小说《加尔各答染色体》。小说围绕安塔尔和他的电脑,穆瑞根,罗斯爵士等角色展开,在时间上横跨过去、现在与未来。整个故事由安塔尔偶然发现的一张身份证说起,这张身份证驱使安塔尔探索穆瑞根失踪的秘密,一系列的谜题被揭开,其他谜题也相继出现。因此,本小说在内容上很吸引人,同时也具有很高的翻译价值。笔者以等值理论为指导开展此次翻译工作。等值理论应用于文学翻译实
众所周知,我国拥有丰富的海洋资源,除了能够满足人们对海产品的基本需求之外,还为工业、旅游业的发展提供了有力的支持与保障,同时又是构成我国物流运输体系的重要组成部分,
异形柱是指截面为L形、T形、十字形等形式的柱体,该种形式的柱子能够有效的避免室内出现明显的棱角、减轻结构的自重,并且使建筑内部布局更加美观。虽然异形柱有很多方面的优
随着工业化发展的快速推进,冷弯型钢的使用也日益广泛。人们对高强度钢材的使用,也使得冷弯型钢的板材趋向超薄化,对材料使用率方面也提出了很高的要求,这也带来了新的稳定问
手机“低头族”在步行时持续低头使用手机,忽视了身边各类潜在的安全隐患,这可能导致交通事故的发生。为解决手机“低头族”的步行安全问题,本文旨在设计一款基于智能手机平
随着土地资源日益匮乏,围堰造陆工程也与日俱增,面对大量的吹填场地软土地基,传统的静力排水固结法与动力排水固结法具有一定的局限和不足,针对吹填场地的不均匀性及软土地基
近年来,我国大力发展基础建设,随着西部大开发战略进一步深入,西部等欠发达地区的交通状况得到了明显改善,处于抗震设防烈度区的桥梁结构越来越多。桥梁结构作为交通运输的重