论文部分内容阅读
网络入侵检测与防御(Network Intrusion Detection/Prevention,NIDP)是信息安全领域一个重要的技术手段。NIDP的基本原理是预先制定一定的安全策略,并将安全策略与其检测到的内容进行匹配,如果检测到安全策略不允许的内容,则拦截或作其他处理。而深度包检测(Deep Packet Inspection,DPI)是实现NIDP的重要技术。由于正则表达式灵活、高效的特点,其常用于网络安全的DPI。传统的正则表达式匹配算法实现方式主要基于非确定有限自动机(NFA,Nondeterministic Finite Automaton)和确定有限自动机(DFA,Deterministic Finite Automaton)。上述两种实现方式在匹配效率和存储空间优化上很难兼得。NFA所需存储空间很小但是匹配速度很慢;DFA由于匹配速度很快使得DFA方法成为了实现正则表达式匹配的普遍选择,但DFA的高匹配速度是以可呈指数膨胀的状态空间为代价的。最近研究者们提出了扩展有限自动机(Extended Finite Automata,XFA),XFA的主要思想是在某些状态后附加一些额外的指令,对DFA实现压缩。附加的指令有寄存器置位复位、计数器累加复位等操作。针对一些包含通配符“.*”的数据具有很大的优化作用。本文在分析传统正则表达式匹配算法NFA和DFA无法满足高性能需求的原因的基础上,试图进一步优化XFA。根据对于实际正则表达式数据集的研究,通过其生成的XFA当中会包含很多相似的结构。本文尝试利用子图同构的原理,提出将XFA进行分块处理后,对其进行合理的编码,从而进一步存储压缩存储空间,提升吞吐量。文中以星形结构为例,使用通过开源正则表达式工具regex转换得到的数据,进行了三态内容可寻址存储器(Ternary Content Addressable Memory,TCAM)的仿真实验。实验结果表明,本方法对于一些数据集可以将存储空间压缩至26.8%,而相同存储量的吞吐量则提高到2.6倍。