Approximate Fingerprinting to Accelerate Pattern Matching
Lukas Kencl
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).
|