String Matching System and Method Using Bloom Filters to Achieve Sub-Linear Computation Time

• US 20080111718A1
• Filed: 05/31/2007
• Published: 05/15/2008
• Est. Priority Date: 11/15/2006
• Status: Active Grant

• Current Assignee: National Chiao Tung University (Government of The Republic of China)
• Original Assignee: National Chiao Tung University (Government of The Republic of China)
• Inventors: Zheng, Yi-Jun, Lin, Ying-Dar, Lin, Po-Ching, Lai, Yuan-Cheng
• Granted Patent: US 7,482,955 B2
• Time in Patent Office: Days
• US Class Current: 341/51
• CPC Class Codes: G06F 21/564 by virus signature recognition

Abstract

A string matching system includes a text string, a plurality of patterns, an m-byte search window and a plurality of Bloom filters, wherein the m-byte search window stands for an m-byte sub-string in the text string under inspection. Every Bloom filter comprises sub-strings of a plurality of patterns. These Bloom filters are queried for membership of the rightmost block in the search window to determine the shift length. The acceleration efficiency of matching many bytes can be achieved simultaneously by shifting the search window for many bytes. Meanwhile, the patterns are stored into an embedded memory through a memory-efficient mechanism-the Bloom filter.

Claims

1. A string matching system, comprising:

a text string;

a plurality of patterns;

an m-byte search window standing for an m-byte sub-string in the text string under inspection; and

a plurality of Bloom filters, each of the Bloom filter comprising sub-strings of the plurality of patterns;

wherein the Bloom filters are required for membership of a rightmost block in the m-byte search window to determine a shift length.

2. The string matching system defined in claim 1, wherein the length of the m-byte search window is equal to the shortest length of the pattern.

3. The string matching system defined in claim 1, wherein if the shift length is N, the m-byte search window stands for a next m-byte sub-string in the text string under inspection by shifting forward N bytes.

4. The string matching system defined in claim 1, wherein every said pattern is divided into M−

Q+1 sub-strings based on length Q, and the sub-strings are grouped according to positions of the sub-strings in the pattern in order to be separately stored in the Bloom filter.

5. The string matching system defined in claim 4, wherein every said pattern is grouped into a plurality of sub-strings according to the prefix of preceding i words, wherein i=1, . . . , (Q−

1), and are stored separately in the Bloom filters.

6. The string matching system defined in claim 1, further comprising a priority setting module, wherein when the Bloom filter generates two or more shift lengths, the priority setting module is used to determine the shift length and output the shorter shift length on a priority.

7. A string matching method, comprising:

(a) providing a plurality of patterns;

(b) providing a text string;

(c) standing for an m-byte sub-string from the text string under inspection through an m-byte search window;

(d) requiring a plurality of Bloom filters for membership of the rightmost block in the m-byte search window to determine a shift length, wherein every Bloom filter comprises sub-strings of the plurality of patterns; and

(e) if the shift length is 0, the Bloom filters are queried for comparison of the blocks from the rightmost one backward in the m-byte search window;

if the shift length is not greater than 0, verification is implemented after finishing comparison, and a byte for the m-byte search window is shifted, and if the shift length is not 0, or greater than 0, the m-byte search window is shifted according to the shift length; and

(f) repeating Step (c) to Step (e) until the text string is matched completely.

8. The method defined in claim 7, wherein the length of the m-byte search window is equal to the shortest length of the pattern.

9. The method defined in claim 7, wherein if the shift length is N, the m-byte search window stands for a next m-byte sub-string in the text string under inspection by shifting forward N bytes.

10. The method defined in claim 7, wherein every said pattern is divided into M−

Q+1 sub-strings based on length Q, and the sub-strings are grouped according to positions of the sub-strings in the pattern in order to be respectively stored in the Bloom filter.

11. The method defined in claim 10, wherein every said pattern is grouped into a plurality of sub-strings according to the prefix of preceding i words, wherein i=1, . . . , (Q−

1), and are stored separately in the Bloom filter.

12. The method defined in claim 7, further comprising a step of providing a priority setting module, wherein when the Bloom filter generates two or more shift lengths, the priority setting module is used to determine the shift length and output the shorter shift length on a priority.