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

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

飞轮系统的符号动力学故障检测方法

为检测飞轮系统的微弱故障,提出一种基于符号动力学的故障检测方法.首先,利用符号动力学算法将飞轮的电流数据进行字符映射,实现信号降噪、数据压缩.其次,利用D阶马尔科夫过程定义电流字符序列的变异过程,且根据字符序列的熵值变化率确立算法的字符个数,并计算字符的概率状态转移矩阵.最后,根据概率状态转移矩阵求解字符概率特征向量,并利用特征向量之间的距离阈值检测飞轮的故障.仿真结果表明:该方法能够根据字符概率特征向量之间的距离区分不同严重程度的飞轮系统故障,实现微弱故障的检测;与扩展卡尔曼滤波算法相比,该方法不需复杂的动力学建模,且仅利用单变量即可实现飞轮的故障检测.此外,利用过程数据,该方法可以快速学习卫星其他部件的行为,并检测故障。

大规模复杂规则匹配技术研究

针对当前安全系统对复杂规则的需求和复杂规则匹配技术的状况,提出了一种新的规则表示方式——字符串表达式,并给出了对应的匹配方法——基于扩展的有限状态自动机(XFA)实现大规模复杂规则匹配的算法。字符串表达式可以描述多个精确字符串之间的逻辑关系与空间位置关系,从而满足安全系统对复杂特征的描述需求。匹配使用二维结构来完成,首先用经典串匹配算法进行字符串的存在性验证,然后将其结果作为输入,驱动以表达式中字符串为"字符"的XFA完成逻辑关系的验证。基于XFA的匹配方法的空间效率和时间效率都接近多模精确串匹配算法。实验结果表明,文中提出的方法既能满足安全系统对关联特征的描述需求,又能提供高效的匹配性能,较好地解决了大规模(万条)的复杂规则匹配问题。

基于预定义类的紧凑型正则表达式匹配算法

针对目前硬件正则表达式匹配算法在存储空间以及吞吐量等方面面临的挑战,结合扩展有限自动机(XFA)正则表达式匹配算法,提出了一种预定义类的压缩自动机匹配算法(Pre-Class CFA)。通过预定义类,算法既可以实现正则表达式中类字符匹配,又能够通过优先级的设定匹配特殊字符集,并在XFA消除确定性有限状态机(DFA)状态爆炸问题的基础上进一步压缩了迁移边数目;同时算法根据现场可编程门阵列(FPGA)和迁移边的特征,设计了一种基于并联只读存储器(ROM)结构的迁移边存取方法,可以实现同一状态多条迁移边的并行读取和匹配。在中低性能FPGA平台ALTERA DE2-70上对算法进行测试,实验中系统吞吐量为1.3 Gb/s,可实现千兆网络下的入侵检测和垃圾过滤。

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

为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如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%。