High-speed pattern storing and matching method

• US 20050125551A1
• Filed: 12/31/2003
• Published: 06/09/2005
• Est. Priority Date: 12/05/2003
• Status: Abandoned Application

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Oh, Jin-Tae, Heo, Young-Joon, Jang, Jong-Soo
• Application Number:
  US10/749,262
• Publication Number:
  US 20050125551A1
• Time in Patent Office: Days
• US Class Current: 709/230
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

The high-speed pattern storing and matching method includes dividing pattern data having a defined rule into parts having a defined length, tabulating and storing input position sequence information of the divided parts of the pattern data and information about the pattern data subsequent to the corresponding divided part of the pattern data, dividing input pattern data into parts having a defined length, independently searching the divided parts of the input pattern data, and determining whether the pattern data input according to each input position sequence are matched to the pattern data having the defined rules, thereby enabling high-speed pattern matching in real time and storing repeating words in one address of memories to enhance the memory efficiency.

Claims

1. A high-speed pattern storing method, which is to tabulate and store pattern data constituting rules, the method comprising:

(a) dividing the pattern data into parts having a defined length or less;

(b) extracting input position sequence information of each divided part of the pattern data; and

(c) assigning a characteristic packet ID to each divided part of the pattern data, and tabulating and storing the divided parts of the pattern data and the input position sequence information of the corresponding parts of the pattern data.

2. The high-speed pattern storing method as claimed in claim 1, wherein the table information includes pattern ID information peculiar to the pattern data having an input position next to the pattern data stored in the corresponding table information.

3. The high-speed pattern storing method as claimed in claim 1, wherein space information of the corresponding pattern data is included to process meta characters.

4. The high-speed pattern storing method as claimed in claim 1, wherein the step (c) includes determining information of a packet head as the characteristic packet ID when the pattern data is the first in the input position sequence among the divided parts of the pattern data.

5. The high-speed pattern storing method as claimed in claim 1, wherein the step (c) includes storing, in a separate table, and multiplexing the pattern data stored in the corresponding table, the input position sequence of the corresponding pattern data, or the pattern data subsequent to and different from the corresponding pattern data.

6. The high-speed pattern storing method as claimed in claim 1, wherein pattern data having the same divided part of the last sequence are stored to make the divided part of the pattern data of the last sequence have the same position information.

7. The high-speed pattern storing method as claimed in claim 1, wherein in the step (c), information representing that the corresponding pattern data is the pattern data of the last sequence is included in the input position sequence information when the divided part of the pattern data is at the last position.

8. The high-speed pattern storing method as claimed in claim 1, wherein the pattern data are stored in a hash table, and a hash value of each divided part of the pattern data, sequence information of the corresponding divided part of the pattern data and word connection information are stored.

9. A high-speed pattern matching method, which is to determine whether input data pattern are matched to pattern data tabulated and stored according to a defined rule, the method comprising:

(a) dividing the input pattern data into parts having a defined length or less;

(b) searching table information storing the same pattern data as the divided data pattern;

(c) extracting table input position sequence information of the corresponding data included in the table information storing the same pattern as the divided parts of the data pattern searched, and table information having the same input position sequence information of the divided data pattern; and

(d) determining from the extracted table information whether the pattern data being constructed is the same as the input data pattern.

10. The high-speed pattern matching method as claimed in claim 9, wherein the stored pattern data includes:

a packet ID representing an input position sequence of the corresponding pattern data; and

packet ID information of pattern data subsequent to the input position of the corresponding pattern data.

11. The high-speed pattern matching method as claimed in claim 9, wherein the step (b) includes stopping a search for pattern data connected to the corresponding pattern data when the input position information of the divided parts of the pattern data is different from the input position information of pattern data being the same as the corresponding data pattern.