Fast Packet Classification Using Condition Factorization
Rule-based packet classification plays a central role in network intrusion detection systems such as Snort. To enhance performance, these rules are typically compiled into a matching automaton that can quickly identify the subset of rules that are applicable to a given network packet. The principal metrics in the design of such an automaton are its size and the time taken to match packets at runtime. Previous techniques for this problem either suffered from high space overheads (i.e., Automata could be exponential in the number of rules), or matching time that increased quickly with the number of rules.