Approximate Fingerprinting to Accelerate Pattern Matching

Pattern matching and analysis over network data streams is increasingly becoming an essential primitive of network monitoring systems. It is a fundamental part of most intrusion detection systems, worm detecting algorithms and many other anomaly detection mechanisms. It is a processing intensive task, usually requiring to search for a large number of patterns simultaneously. We propose the technique of "approximate fingerprinting" to reduce the memory demands and significantly accelerate the pattern matching process. The method computes fingerprints of prefixes of the patterns and matches them against the input stream. It acts as a generic preprocessor to a standard pattern matching engine by "clearing" a large fraction of the input that would not match any of the patterns. The main contribution is the "approximate" characteristic of the fingerprint, which allows to slide the fingerprinting window through the packet at a faster rate, while maintaining a small memory footprint and low number of false positives. An improvement over a Bloom filter solution, a fingerprint can indicate which patterns are the candidate matches. We validate our technique by presenting the performance gain for the popular Snort intrusion detection system with the preprocessor in place.

This is joint work with Ramaswamy Ramaswamy (Univ. of Massachusetts, Amherst) and Gianluca Iannaccone (Intel Research Cambridge).