Multi-pattern matching algorithm and processing apparatus using the same

Patent metadata

Field	Value
Publication number	US-2016239748-A1
Application number	US-201615008966-A
Country	US
Kind code	A1
Filing date	Jan 28, 2016
Priority date	Feb 15, 2015
Publication date	Aug 18, 2016
Grant date	—

Abstract

A multi-pattern matching algorithm may be provided that includes: a moving step of moving a moving window from the start of a string one byte by one byte; a DF 1 checking step of converting the string on a current position of the moving window into an integer value, and of checking whether or not a bit of a related position in a first direct filter DF 1 for patterns having lengths larger than 2 bytes is set to 1; a DF moving step of checking one or more direct filters DF when the bit is set to 1 according to the DF 1 checking step; a re-moving step of moving the moving window by one byte again when the bit of a related position in the direct filter DF, which has been checked lastly, is 0; and a terminating step of checking whether the moving window is located at the end of the string or not, and of terminating the algorithm when the moving window is positioned at the end of the string.

First claim

1 . A multi-pattern matching algorithm comprising:
a moving step of moving a moving window from the start of a string one byte by one byte; a DF 1 checking step of converting the string on a current position of the moving window into an integer value, and of checking whether or not a bit of a related position in a first direct filter DF 1 for patterns having lengths larger than 2 bytes is set to 1; a DF moving step of checking one or more direct filters DF when the bit is set to 1 according to the DF 1 checking step; a re-moving step of moving the moving window by one byte again when the bit of a related position in the direct filter DF, which has been checked lastly, is 0; and a terminating step of checking whether the moving window is located at the end of the string or not, and of terminating the algorithm when the moving window is positioned at the end of the string.

2 . The multi-pattern matching algorithm of claim 1 , further comprising, after the DF moving step, a DF 4 checking step of checking whether or not a bit of a related position in a fourth direct filter DF 4 for patterns having lengths larger than 2 bytes and less than 4 bytes is set to 1.

3 . The multi-pattern matching algorithm of claim 2 , further comprising, after the DF 4 checking step, a PID recording step of when the bit of a related position in the fourth direct filter DF 4 is set to 1, recording a pattern ID (PID) corresponding to the string in which the moving window is located, with reference to a first compact table CT 1 storing PIDs of the patterns having lengths larger than 2 bytes and less than 4 bytes.

4 . The multi-pattern matching algorithm of claim 1 , further comprising, after the DF moving step, a DF 2 checking step of moving the moving window by two bytes from the current position, of converting the string of a length as much as 2 bytes on the moved position into an integer value, and of checking whether or not a bit of a related position in a second direct filter DF 2 for patterns having lengths larger than 4 bytes is set to 1.

5 . The multi-pattern matching algorithm of claim 4 , further comprising, after the DF 2 checking step, a DF 5 checking step of, when the bit of a related position in the second direct filter DF 2 is 1, checking whether or not a bit of a related position in a fifth direct filter DF 5 for patterns having lengths larger than 4 bytes and less than 8 bytes is set to 1.

6 . The multi-pattern matching algorithm of claim 5 , further comprising, after the DF 5 checking step, a PID recording step of when the bit of a related position in the fifth direct filter DF 5 is 1, checking whether or not a pattern ID (PID) corresponding to the string in which the moving window is located, with reference to a second compact table CT 2 storing PIDs of the patterns having lengths larger than 4 bytes and less than 8 bytes, and of when the PID corresponding to the string exists, recording the PID.

7 . The multi-pattern matching algorithm of claim 1 , further comprising, after the DF moving step, a DF 3 checking step of moving the moving window by six bytes from the current position, of converting the string of a length as much as 2 bytes on the moved position into an integer value, and of checking whether or not a bit of a related position in a third direct filter DF 3 for patterns having lengths larger than 8 bytes is set to 1.

8 . The multi-pattern matching algorithm of claim 7 , further comprising, after the DF 3 checking step, a PID recording step of, the bit of a related position in the third direct filter DF 3 is set to 1, recording a pattern ID (PID) corresponding to the string in which the moving window is located, with reference to a third compact table CT 3 storing PIDs of the patterns having lengths larger than 8 bytes.

9 . The multi-pattern matching algorithm of claim 1 , wherein the algorithm is used in a network intrusion detection system (NIDS).

10 . A program which is stored in a medium and performs:
a moving step of moving a moving window from the start of a string one byte by one byte; a DF 1 checking step of converting the string on a current position of the moving window into an integer value, and of checking whether or not a bit of a related position in a first direct filter DF 1 for patterns having lengths larger than 2 bytes is set to 1; a DF moving step of moving the moving window to one or more direct filters DF when the bit is set to 1 according to the DF 1 checking step; a re-moving step of moving the moving window by one byte again when the bit of a related position in the direct filter DF, which has been checked lastly, is 0; and a terminating step of checking whether the moving window is located at the end of the string or not, and of terminating the algorithm when the moving window is positioned at the end of the string.

11 . A multi-pattern matching processing device comprising:
a direct filter DF which is a bit array having a plurality of bits, each of which indicates whether one or more consecutive ASCII codes corresponding to its index belongs to a portion of a particular pattern or not, and is composed of one or more direct filters, each of which has information on 2 n (n=0, 1, 2, 3, . . . )-th two bytes of the pattern according to a length of the pattern; and at least one compact table CT which is a structure for recording pattern IDs of the patterns existing in a string and for finding out what pattern exists in the string, and stores the pattern ID according to pattern groups formed based on the length of the pattern.

12 . The multi-pattern matching processing device of claim 11 , wherein the direct filter DF comprises a first direct filter DF 1 comprising information on the two headmost bytes of all of the patterns, a second direct filter DF 2 comprising information on the second two bytes of the patterns having lengths larger than 4 bytes, a third direct filter DF 3 comprising information on the fourth two bytes of the patterns having lengths larger than 8 bytes, and a fourth direct filter DF 4 comprising information on the two headmost bytes of the patterns having lengths larger than 2 bytes and less than 4 bytes.

13 . The multi-pattern matching processing device of claim 12 , wherein the direct filter DF further comprises a fifth direct filter DF 5 comprising information on the second two bytes of the patterns having lengths larger than 4 bytes and less than 8 bytes.

14 . The multi-pattern matching processing device of claim 11 , wherein the compact table CT comprises a first compact table CT 1 comprising the pattern IDs of the patterns having lengths larger than 2 bytes and less than 4 bytes, a second compact table CT 2 comprising the pattern IDs of the patterns having lengths larger than 4 bytes and less than 8 bytes, and a third compact table CT 3 comprising the pattern IDs of the patterns having lengths larger than 8 bytes.

Assignees

• Korea Advanced Inst Sci & Tech

Inventors

• Han Dong-Su
• Choi Byung-Kwon
• NAM Jae-Hyun
• Jamshed Muhammad
• Park Kyoung-Soo
• CHAE Jong-Wook

Classifications

• H04L63/1416 Primary

  Event detection, e.g. attack signature detection · CPC title

• G06N5/04

  Inference or reasoning models · CPC title

• G06N5/047 Primary

  Pattern matching networks; Rete networks · CPC title

• G06V30/1983 Primary

  Syntactic or structural pattern recognition, e.g. symbolic string recognition · CPC title