| Multiple-pattern matching algorithms are the heart of many network intrusion detection systems' signature matching engines. They allow these engines to quickly search for many patterns simultaneously in input passing through such systems, but often consume most of the processing time. Thus, they should be as fast as possible to ensure system scalability into networks of ever-increasing speeds. Concurrently they must enforce security so that they are not susceptible to algorithmic complexity attacks.;We provide a comprehensive overview of significant pattern matching algorithms and discuss their suitability for these kinds of systems. Using the Snort network intrusion detection system as a platform, we implement and compare several apposite algorithms. Multiple Backward Oracle Matching has not been used in intrusion detection to our knowledge, and we introduce it in options we add to Snort: MBOM and AUTO. Our AUTO option is a new approach to pattern matching in Snort using multiple algorithms. |
