检索结果-南通市图书馆

ɑFA:一种基于非信任字符比较的高性能正则表达式匹配算法

在线全文

学校读者我要写书评

暂无评论

电子技术应用 2024年第6期50卷 57-60页

作者：杨嘉佳关健于增明张雷姚旺君中国电子信息产业集团有限公司第六研究所北京100083

正则表达式匹配技术在数据治理、解析提取和深度包检测方面有着重大应用价值。然而,由于其在通用平台上的匹配性能较低,无法满足实际环境下数据实时处理的应用需求,限制了其在高性能数据处理领域的应用范围。针对当前正则表达式匹配性... 详细信息

正则表达式匹配技术在数据治理、解析提取和深度包检测方面有着重大应用价值。然而,由于其在通用平台上的匹配性能较低,无法满足实际环境下数据实时处理的应用需求,限制了其在高性能数据处理领域的应用范围。针对当前正则表达式匹配性能较低的问题,提出一种基于非信任字符比较的高性能正则表达式匹配算法,称之为ɑFA。该算法通过每次判断连续的若干个字符是否属于最常被访问状态的非信任字符集,获取无需通过DFA匹配可直接跳过的字符数,减少字符匹配过程中访问内存DFA状态转移表的次数,从而实现字符匹配的加速处理。实验结果表明,ɑFA算法可获得相比于原始DFA匹配算法约为1.05~7.58倍的性能加速比。

关键词：正则表达式匹配确定型有限自动机高性能数据处理

基于并行字符索引的多步长正则表达式匹配算法

在线全文

学校读者我要写书评

暂无评论

计算机研究与发展 2015年第3期52卷 681-690页

作者：丁麟轩黄昆张大方湖南大学信息科学与工程学院长沙410082 中国科学院计算技术研究所北京100190

深度包检测（deep packet inspection,DPI）是网络入侵检测与防御系统（network intrusion detection and prevention system,NIDPS）的核心.基于三态内容可寻址存储器（ternary content addressable memory,TCAM）的正则表达式匹配算法提高了数据包的处理速度,成为DPI技术的一个重要研究方向.TCAM具有查找速度快、存储空间小等特性,且能耗与存储空间成正比.由于DFA的存储空间开销比较大,且存储空间大小随着DFA步长数的增加而指数倍增,基于TCAM的DFA面临高能耗的问题,特别是多步长DFA.提出一种基于并行字符索引的多步长正则表达式匹配算法（multi-stride parallel character-indexed DFA,PCIDFA）,对确定型有限自动机（deterministic finite automaton,DFA）构造并行字符索引,通过比特位图取交集,减少匹配时激活的TCAM块数,显著降低TCAM能耗.实验结果表明：与多步长DFA相比,多步长PCIDFA在TCAM能耗上减少了99.8%以上,在TCAM存储空间开销上减少了48.5%-65.3%,在吞吐量上提高了1.9-2.6倍.

关键词：正则表达式匹配三态内容可寻址存储器并行字符索引分块存储低能耗

在线全文

学校读者我要写书评

暂无评论

支持多正则表达式匹配的硬件结构

清华大学学报（自然科学版） 2009年第10期49卷 1704-1707页

作者：张伟薛一波嵩天清华大学计算机科学与技术系北京100084 清华大学网络安全研究中心北京100084 北京理工大学计算机系北京100081

针对多正则表达式匹配已经成为制约网络安全系统性能瓶颈的问题,提出一种硬件四级流水线的多正则表达式匹配结构。该结构对多条正则表达式统一处理,将正则表达式切割成字符串和循环控制,采用字符串匹配结构处理字符串,并设计专用硬件电... 详细信息

针对多正则表达式匹配已经成为制约网络安全系统性能瓶颈的问题,提出一种硬件四级流水线的多正则表达式匹配结构。该结构对多条正则表达式统一处理,将正则表达式切割成字符串和循环控制,采用字符串匹配结构处理字符串,并设计专用硬件电路处理循环限制。实验表明,该硬件结构在Virtex2和Virtex4 FPGA上分别可以达到1.9和2.1Gb/s的匹配性能,与国外相关研究成果相比,消耗更少的存储空间,并支持更多的正则表达式。

关键词：网络安全系统结构特征匹配正则表达式匹配

同方期刊数据库

一种基于智能有限自动机的正则表达式匹配算法

在线全文

学校读者我要写书评

暂无评论

电子学报 2012年第8期40卷 1617-1623页

作者：张大方张洁坤黄昆湖南大学信息科学与工程学院湖南长沙410082 中国科学院计算技术研究所北京100190

本文提出了一种基于智能有限自动机(Smart Finite Automaton,SFA)的正则表达式匹配算法,在XFA的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,避免不必要的状态迁移操作.实验结果表明,SFA提高了正则表达式匹配的时空效率,与... 详细信息

本文提出了一种基于智能有限自动机(Smart Finite Automaton,SFA)的正则表达式匹配算法,在XFA的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,避免不必要的状态迁移操作.实验结果表明,SFA提高了正则表达式匹配的时空效率,与XFA相比,在存储空间开销上减少了44.1%,在存储器访问次数上减少了69.1%.

关键词：深度数据包检测正则表达式匹配确定型有限自动机扩展有限自动机智能有限自动机

在线全文

学校读者我要写书评

暂无评论

基于TCAM的低能耗正则表达式匹配算法

通信学报 2014年第8期35卷 162-168,178页

作者：丁麟轩黄昆张大方湖南大学信息科学与工程学院湖南长沙410082 中国科学院计算技术研究所北京100190

提出一种基于字符索引的正则表达式匹配算法,对确定型有限自动机(DFA,deterministic finite automaton)的字母表和状态进行分离存储,构建字符索引,减少匹配时激活的TCAM块数,显著降低TCAM能耗。实验结果表明:与DFA相比,基于字符索引的DF... 详细信息

提出一种基于字符索引的正则表达式匹配算法,对确定型有限自动机(DFA,deterministic finite automaton)的字母表和状态进行分离存储,构建字符索引,减少匹配时激活的TCAM块数,显著降低TCAM能耗。实验结果表明:与DFA相比,基于字符索引的DFA(CIDFA,character-indexed DFA)在能耗上平均减少了92.7%,在存储空间开销上平均减少了32.0%,在吞吐量上平均提高了57.9%。

关键词：正则表达式匹配字符索引分块存储低能耗

在线全文

学校读者我要写书评

暂无评论

正则表达式匹配存储优化技术研究

正则表达式匹配存储优化技术研究

作者：邵翔宇解放军信息工程大学

学位级别：硕士

网络安全问题成为关乎我国国计民生的大事,基于深度包检测(Deep Packet Inspection,DPI)技术的入侵检测系统(Intrusion Detection System, IDS)作为网络防护的重要手段,近年来得到广泛应用。正则表达式因其强大的功能和灵活表达手段成为... 详细信息

网络安全问题成为关乎我国国计民生的大事,基于深度包检测(Deep Packet Inspection,DPI)技术的入侵检测系统(Intrusion Detection System, IDS)作为网络防护的重要手段,近年来得到广泛应用。正则表达式因其强大的功能和灵活表达手段成为DPI的核心算法。随着网络安全攻防双方的发展,攻击模式的不断复杂化和网络业务及应用的日新月异,IDS中正则表达式匹配技术仍存在诸多问题,其中最重要的是高速低存储的正则表达式匹配算法的设计。基于确定型有限状态自动机(Deterministic Finite Automata, DFA)的正则表达式算法因其线性的匹配速度得到广泛应用,但存在部分类型的规则编译时会产生状态爆炸问题、存储空间急剧增长的情况。本文从DFA的构建过程出发,分析当前算法的改进思路和存在的不足,对DFA算法进行存储优化,设计高速低存储的正则表达式算法。本文主要工作如下：多维立方体自动机(Multi-dimensional Finite Automata, MFA)利用多维结构的对称性,仅保留坐标轴和当前所处位置信息,通过状态的实时更新,降低存储空间。针对MFA适用规则类型较少问题,结合入侵检测系统克林闭包规则的特点,设计了扩展多维有限自动机算法(eXtend Multi-dimensional Finite Automata, XMFA)。对不满足对称性的结构,进行结构调整,增加辅助变量,增加适用的规则类型;为了完成快速状态更新,设计简单完备的状态跳转指针。理论分析和仿真实验表明,XMFA与DFA数量级相当的匹配时间,同时占用存储空间比基于DFA算法大大减少。采用分组算法解决DFA状态爆炸问题,随着分组数目的增加,时间效率大大降低。基于正则表达式引擎输入驱动特性理论,提出了驱动特性有限自动机(Drive Character Finite Automata, DCFA)分组算法。DCFA分组算法将规则类型作为正则表达式分组的依据,根据规则类型确定各分组采用的改进算法,保证各个类型的规则集不出现状态爆炸问题。实验表明,在简单规则情况下,DCFA用更少的分组数目达到Multiple DFAs(mDFA)算法存储压缩效果,提高了匹配效率。与经典的改进算法相比,DCFA预处理时间和存储空间比Hybrid-FA、D2FA算法降低了2～3个数量级;匹配时间与DFA算法相当。分析当前入侵检测系统Perl兼容的正则表达式(Perl Compatible Regular Expressions, PCRE)规则特点,基于驱动特性的分组方案和扩展多维有限自动机结构,设计一种可以应用于当前入侵检测系统的模板有限自动机(Templates Based Finite Automata, TFA)匹配算法。TFA算法根据IDS规则类型特点,设计规则分组模板,然后根据规则模板将规则集划分为若干个规则子集,各个规则子集根据系统结构分别构建高速低存储的匹配引擎。实验表明,与经典的改进算法相比,TFA预处理时间和存储空间比Hybrid-FA、D2FA算法降低了几个数量级;匹配时间与DFA算法数量级相当。

关键词：入侵检测系统正则表达式匹配确定性有限自动机扩展多维有限自动机分组算法规则驱动特性驱动特性有限自动机模板有限自动机

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

正则表达式匹配算法并行化技术研究

正则表达式匹配算法并行化技术研究

作者：邵妍北京邮电大学

学位级别：硕士

正则表达式匹配是网络内容分析与过滤系统中的核心关键技术。随着互联网技术的快速发展,新型网络应用和协议不断涌现,待检测数据量急遽增长,检测规则数量庞大且语法日益复杂,这对正则表达式匹配技术在匹配速度和存储空间方面提出了双重... 详细信息

正则表达式匹配是网络内容分析与过滤系统中的核心关键技术。随着互联网技术的快速发展,新型网络应用和协议不断涌现,待检测数据量急遽增长,检测规则数量庞大且语法日益复杂,这对正则表达式匹配技术在匹配速度和存储空间方面提出了双重挑战。新型并行化硬件发展迅速,但由于传统的正则表达式匹配技术基于串行处理,无法直接利用并行硬件提升正则表达式匹配的性能。本文对正则表达式匹配算法的并行化技术展开研究,具体研究内容包括：DFA构建并行加速技术、DFA并行分解技术和DFA最小化并行加速技术。本文的主要研究成果总结如下： (1)DFA并行构建算法：本文在沿用k-Reduction算法对DFA的组织方法的基础上,研究经典的子集构造法的多线程并行加速技术。本文提出两种DFA并行构建算法：基于并行读写的DFA构建算法PRW通过对状态映射表的加锁和解锁操作,保证公共数据的多线程安全性,该算法的DFA构建速度最快达到k-Reduction算法的1.716倍;基于多线程和单线程循环交替的DFA构建算法SMA从状态映射表读取频率显著高于写入频率这一现象入手,拆分状态映射表的读写权限,该算法的DFA构建速度最快达到k-Reduction算法的2.714倍。 (2)DFA并行分解算法：本文从字符集分解的角度出发,提出DFA并行分解算法PDFA,该算法将大字符集上的DFA分解为多个小字符集上的DFA,用小字符集上的DFA模拟原DFA的状态转移。在多核并行加速情况下,PDFA算法的状态转移时间复杂度为O(1)。实验结果显示,PDFA算法能显著压缩绝大多数DFA的存储空间,空间压缩率优于相关DFA空间压缩算法。 (3)DFA并行最小化算法：本文针对经典的DFA最小化算法Hopcroft进行多线程并行加速研究,提出基于多线程并行的DFA最小化算法P-Hopcroft,该算法通过划分等价类的分割权限,实现对Hopcroft算法的并行加速。实验结果显示,最优情况下,P-Hopcroft算法的DFA最小化速度为原始Hopcroft算法的2.236倍。

关键词：正则表达式匹配 DFA构建 DFA压缩 DFA分解 DFA最小化

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

高性能正则表达式匹配算法评估

计算机工程 2010年第19期36卷 269-271页

作者：金军航张大方黄昆湖南大学软件学院长沙410082 湖南大学计算机与通信学院长沙410082

为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如DFA、D2FA、CD2FA、mDFA及XFA等最新算法,采用Snort规则集综合评估这些算法的存储空间和匹配时间。实验结果表明,在存储空间方面,与mDFA相比,XFA的存储空间减少84.9%89.... 详细信息

为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如DFA、D2FA、CD2FA、mDFA及XFA等最新算法,采用Snort规则集综合评估这些算法的存储空间和匹配时间。实验结果表明,在存储空间方面,与mDFA相比,XFA的存储空间减少84.9%89.9%;在匹配效率方面,与mDFA相比,XFA的匹配时间增加了38.9%174.6%;XFA在存储空间和匹配效率上具有良好的可伸缩性,即当规则数增加到8倍时,mDFA的存储空间增长了64倍,而XFA的存储空间仅增加了16倍,匹配时间仅增加了61.3%。

关键词：正则表达式匹配确定有限自动机扩展有限自动机性能评估

在线全文

学校读者我要写书评

暂无评论

基于变长切换的多数据流正则表达式匹配

计算机工程与设计 2013年第11期34卷 3856-3861页

作者：贺炜郭云飞莫涵扈红超国家数字交换系统工程技术研究中心河南郑州450002

为支持多条数据流的正则表达式匹配,提出一种基于FPGA的正则表达式匹配系统(VLS Memory-DFA)。通过具有记忆特性的DFA结构实现了匹配过程的灵活中断和恢复,通过变长切换机制保证了多条数据流处理的公平性和切换的快速性。通过部署于FPGA... 详细信息

为支持多条数据流的正则表达式匹配,提出一种基于FPGA的正则表达式匹配系统(VLS Memory-DFA)。通过具有记忆特性的DFA结构实现了匹配过程的灵活中断和恢复,通过变长切换机制保证了多条数据流处理的公平性和切换的快速性。通过部署于FPGA,该系统在3386条规则下,最大能够支持92条数据流的同时处理,能够达到236MHz的时钟频率以及7.55Gbps的吞吐率。处理结果表明,VLS Memory-DFA能够满足多数据流的处理需求,并达到较高的处理速率。

关键词：多数据流正则表达式匹配变长切换现场可编程门阵列高速