Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

17.1 SEARCHING FOR MULTIPLE STRINGS IN P... > 17.1.1 Integrated String Matching Us... - Pg. 402

402 CHAPTER 17 Network Security b a b a b a r . . . (Packet payload) b a b b a e r babar barney y r n not b from most nodes b from most other nodes F I G U R E 17.2 The Aho­Corasick algorithm builds an alphabetical trie on the set of strings to be searched for. A search for the string "barney" can be found by following the "b" pointer at the root, the "a" pointer at the next node, etc. More interestingly, the trie is augmented with failure pointers that prevent restarting at the top of the trie when failure occurs and a new attempt is made to match, shifted one position to the right. Early versions of Snort do string search by matching each packet against each Snort rule in turn. For each rule that matches in the classifier part, Snort runs a Boyer­Moore search on the corresponding string, potentially doing several string searches per packet. Since each scan through a packet is expensive, a natural question is: Can one search for all possible strings in one pass through packet?