网络入侵检测中多模式匹配的状态编码方法

State encoding for multi-pattern matching for network intrusion detection

为了减少网络入侵检测系统的硬件实现方案中自动机占用的存储容量,提出了一种自动机状态的编码方法。该方法通过对自动机状态重新进行编号,使得多个状态能够用一个通配编号来表示,这样自动机中具有相同输入和下一状态的多条变迁就能被聚合为一条,大大减小了需要存储的变迁数目。可以证明状态编码方法能够将变迁数目减小到理论上最小值同时保证自动机恒定的处理速率。实验表明,对于常见特征串集,该方法可以将变迁数目减小98.9%以上。

A state encoding scheme was developed to reduce the storage for the Deterministic Finite Automaton （DFA） in hardware-based Network Intrusion Detection System （NIDS）. The scheme greatly reduces the number of transitions by re-encoding the DFA states so that multiple states can be represented by one number and transitions with the same input to the next state can be combined into one transfer. Theoretical analyses prove that this state encoding scheme minimizes the number of transitions while maintaining the best worst case DFA performance. Experiments on a mainstream NIDS rule set show that the state encoding scheme reduces the transitions by more than 98.9%.