一种正则表达式集合快速搜索算法

正则表达式由于其强描述能力和灵活性,在信息检索,程序设计,数据挖掘,深度分组检测,生物信息处理等领域得到了广泛而深入的应用,然而正则表达式,尤其是正则表达式集合,由于搜索速度慢往往成为系统的性能瓶颈。现有的正则表达式搜索算法性能较好的是多模式过滤类型的算法,此类算法严重依赖于两个因素,从NFA的初始状态到终止状态的最短路径Lmin和正则表达式所表达的语言的前缀集合Pref（RE）的大小,Lmin越长,搜索速度越快,Pref（RE）越大,搜索速度越慢。针对上述问题提出了一种基于Bloom filter的正则表达式集合搜索算法,此方法利用Bloom filter的集合查询时间集合大小无关的特点,使得正则表达式搜索速度不受Pref（RE）大小的影响,如果采用多个Bloom filter并行,还可以间接增大Lmin的长度。分析与测试结果表明,本算法较大的加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,可以实现大规模正则表达式集合的快速搜索。     

一种基于Bloom Filter的正则表达式集合快速搜索算法

正则表达式搜索算法的性能与从非确定性有限状态自动机(NFA)的初始状态到终止状态的最短路径Lmin成正比,与正则表达式所表达的语言的前缀集合Pref(RE)成反比,而一般情况下Pref(RE)较大,确定Pref(RE)中的元素在目标文本中的出现位置比较困难.文中提出了一种基于Bloom Filter的正则表达式集合搜索算法,此算法利用Bloom Filter集合查询时间与集合大小无关的特点,可以快速准备定位Pref(RE)的出现位置,使得搜索速度不受Pref(RE)的影响,如果采用多个Bloom Filter并行,还可以间接增大Lmin.分析与测试结果表明,该算法较大地加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,在Lmin较长、Pref(RE)较大时,搜索速度可以提高数倍至数十倍,适合大规模的多正则表达式的快速搜索.     

基于规则分组的DFA正则表达式匹配算法

模式匹配因误报率低和漏报率低被入侵检测所采用.在使用正则表达式构造DFA时,因状态爆炸导致匹配算法需要较多的存储空间和运行时间,算法效率低下,采用规则分组后,可以在一定程度上抑制状态爆炸问题.根据缓存中的历史记录对正则表达式进行分组,既能利用规则分组减少状态总数,抑制状态爆炸,又能减少因每次重新构建DFA所带来的开销,...     

确定有限自动机到正则表达式转换的并行处理

有限自动机和正则表达式都是描述语言重要方法,二者的转换具有重要意义.针对确定有限自动机模型做了深入的分析,在并行环境,提出了一种确定有限自动机到正则表达式的并行转换算法,并以实例详细描述了算法并行处理过程并验证了其算法的可行性.     

面向网络流的自适应正则表达式分组匹配算法

针对当前的多正则表达式匹配算法占用较大的系统资源,且吞吐量较低的问题,在分析典型的正则表达式匹配算法的基础上,提出了一种自适应的多正则表达式分组匹配算法.该算法通过对正则表达式进行高效分组,将相互之间存在交叠且容易引起状态数指数增长的表达式相互隔离;将每个分组构造为一个确定性有限自动机(DFA),按匹配概率大小建立伸展树进行调度.仿真结果表明,该算法不仅大大节省了存储空间,而且吞吐量提高了大约3倍.     

一种基于多线程的混合深度包检测方法

为了提高网络入侵检测速度和稳定性,提出了一种基于多线程的混合深度包检测方法.该方法首先采用正则表达式的线性系数来对规则集中的正则表达式进行分组,然后对不同正则表达式组采用不同压缩技术进行状态位压缩,生成不同FA(Finite Automata),最后采用多线程技术对生成的不同FA进行检测.通过实验验证,得出该方法具有较高的压缩和处理性能,同时能有效提高检测的速度和稳定性.     

正则表达式的实现

正则表达式提供了功能强大、灵活而又高效的方法来处理文本。论述了如何用C＋＋语言实现基于正则表达式的查找和替换。     

一种基于CPU-GPU协同的特征码匹配机制

在网络安全系统中,提出了一种基于CPU-GPU协同的特征码匹配机制。先用每个特征码表达式的n前缀,构建一个小的DFA（有限自动机）;再在GPU上进行不完全匹配,剔除大量正常数据包,检测出可疑的数据包;然后再在CPU上对可疑数据包进行精确匹配。测试结果表明,该机制的匹配吞吐量能达到了19Gbits/s。     

有限自动机正则化方法研究

有限自动机正则化是编译中的重要技术,文章针对现有有限自动机正则化方法的不足,分析了有限自动机正则化的本质,提出了一个新的有限自动机正则化方法。这个新的方法具有通用的特点。     

一种快速的多模式字符串匹配算法

以基于有限自动机的多模式匹配算法（DFSA）为基础，结合Boyer-Moore(BM）和Quick Search（QS)快速单模式匹配算法的优点，提出了一种快速的多模式字符串匹配算法，在一般情况下，该算法不需要匹配目标文本中的每个字符，能充分利用匹配过程中本次匹配不成功的信息和已经匹配成功的信息，跳过尽可能多的字符。实验表明，模式串较短时，本算法所需时间为DFSA算法的1／2－1／3；模式串较长时，本算法所需时间为DFSA算法的1／2－1／3；模式串较长时，其所需时间为DFSA算法的1／3－1／5。     

一种非确定型有穷自动机的极小化方法

自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言．确定型有穷状态自动机（DFA）极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机．而非确定型有穷状态自动机（NFA）极小化问题尚未找到有效算法．尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加．从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机．     

一种基于XML和正则表达式的简单验证框架

在Web开发中,繁琐的表单验证会花费大量的时间与精力,本文简要介绍了一种综合利用正则表达式和XML技术的通用验证框架,可以基本满足高效、简便的表单验证工作。     

一种构造格蕴涵代数的方法

格蕴涵代数是一种重要的逻辑代数,可以分别刻画真值的可比较性和不可比较性,从而形象地描述人类的思维活动。因此,构造新的格蕴涵代数对人工智能的研究具有重要意义。提出了格蕴涵同态像的概念,证明了格蕴涵同态像是格蕴涵代数;并通过已有的格蕴涵同态映射,得到构造格蕴涵代数的新方法。     

基于多GPU的正则表达式匹配技术

针对传统正则匹配性能低下的问题,设计了基于多GPU的正则表达式匹配引擎,并采用折半分组优化算法解决了有限状态自动机在大规模正则集合情况下由于空间爆炸无法使用的问题,并做了相关的优化,提升了数据匹配速度.实验结果表明:基于多GPU的正则表达式匹配性能较CPU提升了61倍,其数据吞吐率远优于其他加速方式.     

高速网络环境下的新型木马快速检测方法研究

为了适应高速网络环境下的木马检测,通过分析传统的IDS,针对其在高速网络环境下对木马检测能力的不足,提出了单引擎大特征集的木马检测方法;通过分析木马的网络数据特征,对有限自动机转换过程进行优化,缩短了编译的时间,避免了重复匹配的问题,大幅度提高了基于正则表达式的木马检测方法的效率.     

基于JS和正则表达式的客户端数据验证方法研究

介绍了数据验证的含义和重要性,通过对传统服务器端数据验证方式及其弊端的分析,以及对客户端数据验证可行性分析,给出了基于JS和正则表达式的客户端数据验证方法及其组成,同时说明了客户端数据验证方式的局限性并提出客户端验证和服务器端验证相结合的解决方法.     

一种改进的多模式匹配算法

在基于有限状态自动机的多模式匹配算法(DFSA算法)基础上,结合Tuned BM算法的优点,提出一种快速的多模式字符串匹配算法,实现了多模式匹配过程中不匹配字符的连续跳跃.在一般情况下,算法不需要匹配目标串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配.在模式串较长和较短的情况下,算法都有很好的性能.分析指出算法实际比较的字符数随着模式串长度的增加而下降,并随模式集的增大有所增多.实验表明,在模式串较短时,算法需要的匹配时间仅为AC算法的50%到33.3%,AQR算法的90%左右;在模式串较长时,所需时间为AC算法的25%至12.5%,AQR算法的75%左右.     

一种新型动态可重构的正则表达式匹配引擎设计

针对大规模数据处理和动态更新规则的网络计算需求,本文提出了一种新型动态可重构的正则表达式匹配(DRR)算法.算法采用参数化一致性表达方法,提高了正则表达式的动态匹配能力;采用专用电路与可重构电路的混合计算框架,设计了正则表达式匹配的并行计算加速引擎.在软硬件协同工作模式下,新型动态可重构的匹配加速引擎不仅可以最大化利用FPGA电路的可编程特性实现表达式匹配规则的动态更新,提高匹配的预处理速度,设计的专用ASIC并行匹配电路更大幅提高了正则表达式的匹配计算速度.本文采用TSMC 28nm CMOS工艺完成芯片的设计和流片,实验结果表明:本文设计实现的动态可重构的匹配加速引擎可以有效地适用于大多数应用场景下的正则表达式匹配,匹配计算的吞吐率达到280Gb/s,相比于同类型基于FPGA的匹配计算引擎实现了5倍以上的匹配速度提升.     

基于二元关系闭包运算构造商集的一种方法

本文通过对二元关系闭包运算的研究,给出与二元关系R结构相近的一个等价关系的划分,从而构造相应的商集,该方法简便、实用、高效,易于操作。     

基于二元关系闭包运算构造商集的一种方法

本文通过对二元关系闭包运算的研究,给出与二元关系R结构相近的一个等价关系的划分,从而构造相应的商集,该方法简便、实用、高效,易于操作。