十年潜心研究,RegEx40协处理卡横空出世

发布时间:2017-05-09

正则表达式是由数学家Stephen Kleene于1956年提出的,主要通过字符的格式匹配进行词法分析,早期主要应用于文本搜索、程序语言编译器等领域。

常用的匹配正则表达式模式的方式是使用FSM(Finite State Machine,有限自动机)来识别的,FSM是一个五元组(Q,∑,q0,δ,F),其中,Q为有穷状态集,∑为有穷输入集,q0为初始状态,转移函数δ:q×∑→Q ,F为接受状态集。FSM从初始状态q0开始,逐一读入由∑中字符构成的输入串的每个字节,根据当前状态、输入字节和转移函数δ决定自动机的下一个状态。若自动机处于接受状态集合F中的某一个状态,则表示自动机接受该输入串;若直到输入串结束,FSM始终未处于接受状态,则自动机不接受该输入串。FSM分为确定性有限自动机(Deterministic Finite Automaton,DFA)与非确定性有限自动机(Nondeterministic Finite Automaton,NFA)。DFA对每个输入只产生一个状态转移,而NFA对每个输入可能产生多个状态转移,并且有空边ε。

DFA包含一组来自∑的输入符号、一组有限的状态和一个转移函数δ。在网络应用中,∑包含28个输入符号(扩展的ASCII码)。在所有的状态中,存在一个初始状态q0和一组接受状态。转换函数δ以当前状态和输入符号为参数,得到下一个状态。DFA在任何时候只有一个状态处于活跃状态。NFA的工作机制与DFA相似,但是NFA中的δ函数可以将一个状态和一个输入符号转换成一组新的状态,因此,在NFA中可能同时存在多个活跃状态。理论研究表明,长度为n的正则表达式,NFA可以用O(n)个状态标识,当将NFA转换成DFA时,最差可能产生O(∑n)个状态,DFA处理每个字符的复杂性为O(1),而NFA处理每个字符的最差复杂性为O(n2)。因此,研究如何在DFA和NFA之间折中,使用合适的技术兼顾DFA的性能和NFA的存储空间,是需要解决的关键问题。

正则表达式匹配加速问题一直困扰学术界和产业界多年,戎腾核心团队成员及合作高校的学者在近十余年来,一直潜心于正则表达式加速匹配的研究,发表了一系列高水平学术论文,2017年5月,在国家自然科学基金的支持下,采用SPBV(用于FPGA实现高性能规则匹配),LoR(多维空间规则复合)、HyperMem(用于正则表达式匹配性能的加速)等核心算法,强力推出RegEx40,作为正则表达式匹配加速的协处理器,该卡兼具压缩解压缩、加密解密、多元组规则匹配等加速功能,必将在大数据分析预处理、入侵检测、云中心检测、内容审计、防火墙、基因匹配、内容搜索等领域得到广泛应用。