共查询到17条相似文献,搜索用时 78 毫秒
1.
2.
针对特定条件下含有“.*”的正则表达式规则相互作用产生的状态爆炸问题,本文提出一种基于多维立方体的确定性有限自动机(Deterministic Finite Automaton,DFA)结构,将冗余状态按维度划分并压缩,并设计相应的多维立方体确定性有限自动机(Multi-Dimension-Cube-DFA,M-D-Cube-DFA)算法,通过构造动态交点的方法实现等价的状态转移.理论分析和仿真实验表明,与DFA算法相比,在维持时间复杂度不变的基础上对状态数目和存储空间进行了对数级别压缩. 相似文献
3.
多个正则表达式规则编译成一个DFA(deter minister finite automata)时,会产生状态爆炸、存储急剧增加的现象。针对最严重的状态爆炸问题,从信息论的角度给出了解释,并提出多维数学模型,将冗余状态分为0维状态和1维状态,通过前者按照维度压缩,后者动态构建的方法将空间复杂度降到理论下界,并在此基础上提出多维有限自动机(MFA, multi-dimensional finite automata)。实验表明,MFA构造时间比XFA略少,比DFA、STT冗余压缩算法和Hybrid-FA降低了2~3个数量级;存储空间比XFA略高,比DFA、STT冗余压缩算法、mDFA、Hybrid-FA降低了1~2个数量级;匹配时间比DFA、Hybrid-FA略多,但是比XFA略少,比STT冗余压缩算法和mDFA降低了1~2个数量级。 相似文献
4.
一种基于FPGA压缩DFA的高速正则表达式匹配算法 总被引:1,自引:0,他引:1
正则表达式匹配技术在网络应用中面临两方面的制约,一方面,复杂或大规模规则导致DFA存储空间急剧膨胀,现有的内存容量难以支撑;另一方面,传统计算机架构的DFA处理能力有限,很难满足高速网络流的线速处理需求。因此,提出一种基于FPGA使用改进游程编码压缩DFA的高速正则表达式匹配算法。实现了基于改进游程编码的DFA引擎架构、分组存储与多路并行比较器技术。该算法不仅具有游程编码的压缩效果,而且压缩后的DFA实现一次状态转移只需2个时钟周期。 相似文献
5.
6.
7.
8.
9.
利用转换矩阵对有限自动机进行化简。在各分组中,当两个不同的出发状态,具有同样的到达状态时,这两个出发状态就可以合并为一个状态。 相似文献
10.
阐述了智能打结机控制系统的功能和控制原理,结合有限自动机和规则库理论提出了打结机控制系统一种新的设计方法,即自动机-规则库设计方法.该方法实现了在系统状态图和控制系统规则库之间进行搜索匹配,从而很好地满足了打结机对动作实时性、准确性、匹配性的要求,大大提高了缝制效率. 相似文献
11.
12.
目前,面向网络流实时处理的正则表达式匹配技术面临两方面的挑战:一方面,复杂或大规模规则集会导致DFA存储空间爆炸的问题;另一方面,传统计算机的串行DFA匹配技术很难满足对高速主干网的线速深度包检测。本文提出了一个基于改进游程编码的DFA压缩算法,并在FPGA上高效实现了该压缩DFA的匹配引擎。测试结果表明规则集的单个DFA的吞吐率均大于800Mbps,在FPGA块内存最大利用率情况下的理论最大吞吐率达到49.5Gbps。 相似文献
13.
14.
为提升网络流识别性能,本文提出了一种TCP流识别算法.该算法基于传输控制协议(Transmission Control Protocol,TCP)下网络通信双方的交互过程构建双向流自动机,由该自动机根据TCP协议规则和网络流当前状态判断TCP流终止,同时以基于规则的过滤机制和超时策略为辅助措施,快速识别单包流和异常中断流.该算法内存开销、计算和内存总开销均低于经典算法固定超时策略(Fixed Timeout strategy,FT)和同类代表性算法两层自适应超时策略(Two-level Self-Adaptive Timeout,TSAT),同时该算法精度高于TSAT,且仅比默认精度标准略有下降.该算法基于协议规则识别TCP流,既保证了流的准确性,又节省了流的超时等待时间,而且算法尤其适合中流、小流和不规则TCP流比重较大的情况,使得识别系统在面临DDoS攻击、蠕虫爆发等网络异常时仍能正常运行. 相似文献
15.
16.
17.
高性能深度包检测系统使用确定型有穷自动机DFA(Deterministic Finite Automata)来执行数据包的检测过程.然而,DFA所带来的存储消耗问题使其难以适用于片内资源稀缺的FPGA.目前已存在多种算法着眼于解决DFA的空间爆炸问题,但是其在带来较好压缩率的同时,也在一定程度上影响到了系统的检测速度.本文提出了一种无匹配时间损耗的DFA压缩算法,并在此基础上,基于FPGA硬件平台,设计实现了单个DFA匹配引擎.实验测试结果表明,本文所设计的算法,在未影响整个系统匹配性能的前提下,可以实现10%~30%左右的压缩率. 相似文献