Variable-stride stream segmentation and multi-pattern matching
View Patent ↗A variable-stride multi-pattern matching apparatus segments patterns and input streams into variable-size blocks according to a modified winnowing algorithm. The variable-stride pattern segments are used to determine the block-symbol alphabet for a variable-stride discrete finite automaton (VS-DFA) that is used for detecting the patterns in the input streams. Applications include network-intrusion detection and protection systems, genome matching, and forensics. The modification of the winnowing algorithm includes using special hash values to determine the position of delimiters of the patterns and input streams. The delimiters mark the beginnings and ends of the segments. In various embodiments, the patterns are segmented into head, core, and tail blocks. The approach provides for memory, memory-bandwidth, and processor-cycle efficient, deterministic, high-speed, line-rate pattern matching.
1. A machine-implemented method for identifying multiple instances of a symbol pattern in a data packet being transmitted over a communication network, the method comprising:
(a) the machine segmenting the data packet into variable-size blocks of symbols using variable stride segmentation to yield a plurality of data-packet segments having two or more different lengths, wherein the data packet is delimited into the plurality of data-packet segments by (i) applying a hash function to different k-grams of symbols within the data packet to generate hash values associated with the different k-grams and (ii) delimiting each data-packet segment based on one or more of the hash values; and
(b) the machine comparing each of the plurality of data-packet segments with a pattern segment of the symbol pattern using deterministic finite automaton (DFA) processing to identify the multiple instances of the symbol pattern in the data packet with no false positives and no false negatives, wherein the pattern segment has fewer symbols than the symbol pattern.
2. The method of claim 1 , wherein step (a) comprises:
(a1) performing a hash function on the k-grams of symbols within the data packet to produce the hash values associated with the k-grams, where (k>0);
(a2) filtering the values to identify at least one special hash value associated with at least one k-gram; and
(a3) delimiting the data-packet stream into at least two data-packet segments based on location within the data packet of the at least one k-gram associated with the at least one special hash value.
3. The method of claim 2 , wherein:
step (a1) comprises generating a plurality of hash values corresponding to a plurality of k-grams within a window of size w, where (k<w); and
step (a2) comprises selecting the at least one special hash value associated with the at least one k-gram as the minimum hash value within the window.
4. The method of claim 1 , wherein step (a) further comprises segmenting said symbol pattern into at least a head block, a core block, and a tail block, wherein said pattern segment corresponds to one of the head block, the core block, and the tail block.
5. The method of claim 1 , wherein step (b) is performed using a single variable-stride discrete finite automaton (VS-DFA).
6. The method of claim 5 , wherein the VS-DFA is constructed using an alphabet comprising at least two core blocks.
7. The method of claim 5 , wherein the VS-DFA includes a quasi-state corresponding to one of at least two different possible pattern matches, wherein determining a pattern match among the at least two different possible pattern matches is a function of head and tail blocks.
8. The method of claim 5 , wherein:
said symbol pattern corresponds to a first symbol sequence; and
the VS-DFA is constructed using an alphabet that includes at least the pattern segment and a segment of a second symbol pattern corresponding to a second symbol sequence, the second symbol sequence being different from the first symbol sequence.
9. The method of claim 1 , further comprising:
(c) consolidating at least one sequence of p consecutive single-symbol data-packet segments into a single p-symbol data-packet segment, where (p>1).
10. The method of claim 1 , further comprising:
(c) consolidating at least one single-symbol data-packet segment into an adjacent multi-symbol data-packet segment.
11. Apparatus for identifying multiple instances of a symbol pattern in a data packet being transmitted over a communication network, apparatus configured to:
(a) segment the data packet into variable-size blocks of symbols using variable stride segmentation to yield a plurality of data-packet segments having two or more different lengths, wherein the data packet is delimited into the plurality of data-packet segments by (i) applying a hash function to different k-grams of symbols within the data packet to generate hash values associated with the different k-grams and (ii) delimiting each data-packet segment based on one or more of the hash values; and
(b) compare each of the plurality of data-packet segments with a pattern segment of the symbol pattern using deterministic finite automaton (DFA) processing to identify the multiple instances of the symbol pattern in the data packet with no false positives and no false negatives, wherein the pattern segment has fewer symbols than the symbol pattern.
12. The apparatus of claim 11 , wherein the apparatus is configured to segment the data packet by:
(a1) performing a hash function on the k-grams of symbols within the data packet to produce the hash values associated with the k-grams, where (k>0);
(a2) filtering the values to identify at least one special hash value associated with at least one k-gram; and
(a3) delimiting the data-packet stream into at least two data-packet segments based on location within the data packet of the at least one k-gram associated with the at least one special hash value.
13. The apparatus of claim 12 , wherein:
the apparatus is configured to perform the hash function by generating a plurality of hash values corresponding to a plurality of k-grams within a window of size w, where (k<w); and
the apparatus is configured to filter the hash values by selecting the at least one special hash value associated with the at least one k-gram as the minimum hash value within the window.
14. The apparatus of claim 11 , wherein the apparatus is further configured to segment said symbol pattern into at least a head block, a core block, and a tail block, wherein said pattern segment corresponds to one of the head block, the core block, and the tail block.
15. The apparatus of claim 11 , wherein the apparatus is configured to compare each of the plurality of data-packet segments with the pattern segment using a single variable-stride discrete finite automaton (VS-DFA).
16. The apparatus of claim 15 , wherein the VS-DFA is constructed using an alphabet comprising at least two core blocks.
17. The apparatus of claim 15 , wherein the VS-DFA includes a quasi-state corresponding to one of at least two different possible pattern matches, wherein determining a pattern match among the at least two different possible pattern matches is a function of head and tail blocks.
18. The apparatus of claim 15 , wherein:
said symbol pattern corresponds to a first symbol sequence; and
the VS-DFA is constructed using an alphabet that includes at least the pattern segment and a segment of a second symbol pattern corresponding to a second symbol sequence, the second symbol sequence being different from the first symbol sequence.
19. The apparatus of claim 11 , wherein the apparatus is further configured to:
(c) consolidate at least one sequence of p consecutive single-symbol data-packet segments into a single p-symbol data-packet segment, where (p>1); and
(d) consolidate at least one single-symbol data-packet segment into an adjacent multi-symbol data-packet segment.