APP下载

基于规则模板的正则表达式分组算法

2016-05-30邵翔宇刘勤让谭力波

电子学报 2016年1期

邵翔宇,刘勤让,谭力波

(国家数字交换系统工程技术研究中心,河南郑州450002)



基于规则模板的正则表达式分组算法

邵翔宇,刘勤让,谭力波

(国家数字交换系统工程技术研究中心,河南郑州450002)

摘要:采用规则分组的方法解决确定型有限自动机(Deterministic Finite Automata,DFA)状态爆炸问题,随着分组数目的增加,匹配效率大大降低.本文提出正则表达式的输入驱动特性理论,并基于此提出了基于规则模板的分组算法——模板有限自动机.模板有限自动机算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎.理论分析和实验表明,与典型的DFA改进算法相比,预处理时间和存储空间有2~3个数量级别的缩减,且匹配效率没有明显降低.

关键词:正则表达式;确定型有限自动机;分组自动机;扩展有限自动机;多维有限自动机;规则模板

1 引言

在网络信息安全领域,入侵检测系统(Intrusion Detection Systems,IDS)扮演着重要的角色,它采用深度包检测(Deep Packet Inspection,DPI)方法进行病毒检测、入侵识别等.随着攻击模式的多样化,最早的基于精确字符串匹配方式已经无法满足要求,正则表达式以其强大的、灵活的表达能力而得到广泛应用.但随着网络带宽逐年增加、规则数目的快速增长以及正则表达式表达功能的强大,DPI应用中的正则表达式匹配(Regular Expression Matching,REM)面临严峻挑战,其中最为急迫的是如何满足高速网络数据包处理的要求.有限自动机分为非确定性有限自动机(Non-deterministic Finite Automata,NFA)和确定性有限自动机(Deterministic Finite Automata,DFA)两种,其中DFA与NFA相比在任意时刻只有一……

登录APP查看全文