共查询到17条相似文献,搜索用时 62 毫秒
1.
2.
确定性有限自动机(DFA)是实现正则表达式匹配的一种有效手段,但DFA的状态跳转是串行的,导致匹配速度慢、难以满足高速骨干网环境深度包检测(DPI)的性能需求.提出了一种称为LBDFA(Loopback DFA)的细粒度并行化状态跳转方法,通过将在Loopback状态上的连续跳转并行化,提高了匹配速度.此外,利用Bloom filter消除该并行跳转中的临时偏离现象,进一步提高了并行潜力.在L7-filter以及Snort规则集上的测试结果表明,LBDFA能够满足10 Gbps以上的正则表达式匹配需求. 相似文献
3.
4.
随着规则数量的急剧增长,表示正则表达式的DFA(Deterministic Finite Automata,确定型有限自动机)容易引起状态空间爆炸,难以满足高速网络的实时处理需求。提出一种高效的正则表达式匹配算法,该算法通过将正则表达式分割为精确串、字符集合以及重复字符3个子集,分别对其进行分区优化及检测,然后再利用结点信息对匹配信号进行连接,即构建一种特殊的状态机DoLFA(Divide-optimize-Link Finite Automata)。理论分析和仿真结果表明,该算法可以大大节省存储空间,并获得较高的吞吐量,且具有较强的扩展性。 相似文献
5.
DFA (确定性有限自动机)对于实现深度包检测(deep packet inspection, DPI)技术具有重要作用。随着深度包检测规则的不断增多,DFA所需的存储空间急剧增大。为此,本文提出了一种基于字符替换的DFA压缩算法,利用状态转换表中每个状态通常只有少数几个不同跳转的特点,我们将状态转换表分解为剩余表和字符替换表,减少了存储空间。此外,通过使相似的状态可以共享相同的字符替换表以进一步压缩存储空间。最后,本文给出了复杂度为O(n2)的压缩算法,n为DFA的状态数。实验结果表明,该算法在L7-filter和Snort规则集上具有较稳定的压缩率,压缩率都在5%以下。 相似文献
6.
当前深度包检测算法通常需要将正则表达式转换为NFA或者DFA.但是随着网络带宽的不断增加.NFA和DFA状态占用的存储空间越来越大,极大地考验着系统的存储能力。为了应对这个问题.提出一种基于正则表达式相性的分组算法来对表达式进行分组,实验证明该算法能减少NFA和DFA状态的数量,提高匹配的效率。 相似文献
7.
8.
深度包检测中一种高效的正则表达式压缩算法 总被引:4,自引:2,他引:4
提出一种基于确定的有穷状态自动机(deterministic finite automaton,简称DFA)的正则表达式压缩算法.首先,定义了膨胀率DR(distending rate)来描述正则表达式的膨胀特性.然后基于DR提出一种分片的算法RECCADR (regular expressions cut and combine algorithm based on DR),有效地选择出导致DFA状态膨胀的片段并隔离,降低了单个正则表达式存储需求.同时,基于正则表达式的组合关系提出一种选择性分群算法REGADR(regular expressions group algorithm based on DR),在可以接受的存储需求总量下,通过选择性分群大幅度减少了状态机的个数,有效地降低了匹配算法的复杂性. 相似文献
9.
10.
11.
针对正则表达式匹配过程中吞吐率低及逻辑资源占用数多的问题,提出一种完全基于现场可编程门阵列(FPGA)逻辑电路的改进确定有限自动机(DFA)匹配算法。首先,该算法统计了DFA中每个状态的大多数转移边都会集中指向相同状态特征的结果,随后根据正则表达式的转移矩阵为DFA的每个状态设置一条默认的转移边,最后进行逻辑电路简化处理,并采用L7-filter规则集进行实测。实验结果表明,改进后的DFA方案与非确定有限自动机(NFA)方案相比,有10%~60%的规则获得了更高的吞吐率,62%~87%的规则占用了更少的逻辑资源。 相似文献
12.
13.
14.
基于正则表达式进行深度报文检测在IDS/IPS、应用层协议识别等网络应用中具有重要作用。然而,采用DFA实现正则表达式需要大量的存储空间,限制了它的实际应用。将DFA状态转换表拆分成3个表,使用run-length编码进行压缩,并对压缩方法进行了优化。采用l7-filter中几个常用应用程序的正则表达式进行测试,结果表明该方法压缩效果一般在90%以上。 相似文献
15.
深度包检测采用简单的字符串匹配技术将报文内容与一组固定字符串进行匹配,基于正则表达式匹配算法能提供更强的表达能力和灵活性,而复杂的正则表达式结构可能引起DFA的状态数膨胀,导致存储代价巨大;DFA拆分算法将DFA转换表拆分为三个表:间接索引表,转换输出表,直接转换表,实验结果表明DFA所占空间大大减小,实现了DFA的压缩存储。 相似文献
16.
提出了基于猜测-分组-检验的面向网络流正则表达式匹配算法。首先对出现概率高的部分特征子块进行搜索并把特征子块进行分组后DFA转换,然后对输出进行猜测匹配。若匹配成功,则使用NFA进行完整验证。实验表明,该方法能够在减少内存使用和资源占用率的同时,具有极高的匹配效率。 相似文献
17.
分析了构件化软件接口、事件、上下文及内容依赖关系在集成测试中的作用,以及提取该四要素的难度;针对构件化软件的自身特点提出了一种有限状态自动机模型,利用该模型实施对四要素的提取,并通过实例验证了该模型的有效性。 相似文献