Variable-stride stream segmentation and multi-pattern matching
US8250016B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 17, 2009 |
| Grant date | Aug 21, 2012 |
| Priority date | — |
| Expiry date | Jan 22, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F18/20
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.