# US 2009/0158427 A1 · Signature string storage memory optimizing method, signature string pattern matching method, and signature string matching engine

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2009/0158427 A1
- Document ID: US20090158427A1
- Status: Published application
- Kind: A1
- Application number: 12/331,613
- Filed: 2008-12-10
- Published: 2009-06-18
- Earliest claimed: 2007-12-17
- Assignees: Electronics and Telecommunications Research Institute
- Inventors: Byoung Koo Kim; Jin Tae Oh; Jong Soo Jang; Sung Won Sohn
- Web page: https://patentgrep.com/patent/US20090158427A1

## CPC

- H04L 63/0263: {Rule management}
- G06F 16/90344: {by using string matching techniques}
- H04L 63/1408: {by monitoring network traffic (monitoring network traffic per se H04L43/00)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Enclosed are a signature string storage memory optimizing method, a signature string pattern matching method, and a signature matching engine. Signature is tokenized in units of substrings and the tokenized substrings are stored in an internal memory block and an external memory block to optimize a memory storage pattern. Therefore, matching of introduction data to signature patterns is effectively performed.

## Claims

### Claim 1

A method of optimizing a signature string storage memory, comprising:
tokenizing signature string patterns to be used as searching patterns of a harmful packet to substrings;
determining whether a substring to be stored in the substrings is the same as a substring of another previously stored signature string pattern to share a corresponding memory table when it is determined that the substring to be stored is the same as the substring of the other previously stored signature string pattern and to analyze whether the substring to be stored is a first substring when it is determined that the substring to be stored is not the same as the substring of the other previously stored signature string pattern;
storing the substring in an internal memory block when it is determined that the substring to be stored is the first substring and analyzing whether a memory table in which a substring previous to the substring to be stored is stored is linked to a memory table in which another substring corresponding to a position of the substring to be stored is stored when it is determined that the substring to be stored is not the first substring; and
storing the substring in an external memory block when it is determined that the memory table in which the substring previous to the substring to be stored is stored is not linked to the memory table in which another substring corresponding to the position of the substring to be stored is stored and storing the substring in the internal memory block when it is determined that the memory table in which the substring previous to the substring to be stored is stored is linked to the memory table in which another substring corresponding to the position of the substring to be stored is stored.

### Claim 2 (depends on 1)

The method of claim 1, wherein the memory table of the internal memory block comprises an address field of a memory table in which a previous substring is stored, an address field of a memory table in which a next substring is stored, a character column field of a substring to be stored, a field for displaying whether the next substring exists, a field for displaying whether the substring to be stored is a first substring, and a field for displaying whether a memory is assigned to the internal memory block.

### Claim 3 (depends on 1)

The method of claim 1, wherein the memory table of the external memory block comprises an address field of a memory table in which a next substring is stored, a character column field of a substring to be stored, a field for displaying information on the size of the character column of the substring to be stored, a field for displaying whether the next substring exists, a field for displaying whether the substring to be stored is the last substring, and a field for displaying whether a memory is assigned to the external memory block.

### Claim 4 (depends on 1)

The method of claim 1, further comprising calculating a hash value of a substring,
wherein the memory table of the substring is stored in an address of an internal memory block matched to the calculated hash value.

### Claim 5 (depends on 4)

The method of claim 4, wherein a character column of a predetermined size is stored in the substrings to be stored in the memory table of the internal memory block.

### Claim 6 (depends on 1)

The method of claim 1, wherein the substrings are sequentially arranged in a memory table from an arbitrary external memory block address when the substrings are stored in the external memory block.

### Claim 7

A method of matching signature string patterns, comprising:
dividing a payload of introduction traffic to be the same as a size of a signature substring character column stored in a signature matching engine;
calling a memory table of an internal memory block address corresponding to the hash value of the character column to be searched when a character column previous to a character column to be searched in the character columns of the divided introduction traffic was not matched to the stored signature substring;
stopping a matching process when the signature substring stored in the called memory table is not matched to the character column to be searched and analyzing whether the matched signature substring is the last substring in the signature substrings when the signature substring stored in the called memory table is matched to the character column to be searched; and
analyzing whether the character column to be searched is matched to the substring stored in the called external memory block address when an external memory block address is called from the called memory table when the matched signature substring is not the last substring and generating an alarm when the matched signature substring is the last substring.

### Claim 8 (depends on 7)

The method of claim 7, wherein, when the character column to be searched is not the last substring and the external memory block address is not called from the called memory table, further comprising analyzing whether the substring stored in the memory table of the internal memory block address corresponding to the hash value of the next character column to be searched is matched to the next character column.

### Claim 9 (depends on 7)

The method of claim 7, wherein, when the character column previous to the character column to be searched was matched to the stored signature substring, further comprising:
analyzing whether the external memory block address was called from the memory table in which the matched signature substring is stored; and
analyzing whether the substring stored in the called address is matched to the character column to be searched when the external memory block address is called from the memory table and analyzing whether the substring stored in the internal memory block address corresponding to the character column hash value to be searched is matched to the character column to be searched when the external memory block address was not called from the memory table.

### Claim 10 (depends on 9)

The method of claim 9, wherein, a matching process is stopped when the substring stored in the internal or external memory block is not matched to the character column to be searched in analyzing whether the substring stored in the internal or external memory block is matched to the character column to be searched and a process is returned to a process of analyzing whether the matched signature substring is the last substring in the corresponding signature substring when the substring stored in the internal or external memory block is matched to the character column to be searched.

### Claim 11

A signature matching engine stored in units of substrings to which signature strings for distinguishing harmful packets included in introduction traffic are tokenized, comprising:
an internal memory block in which a memory table including the substring to be stored is included is provided when the memory table including the first substring that constitutes the signature in the substrings is linked to the memory table in which another substring corresponding to the substring to be stored in the memory table in which the previous substring is stored; and
an external memory block in which a memory table including the substring to be stored is provided when the memory table in which the previous substring is stored is linked to the memory table in which the other substring corresponding to the substring to be stored is stored.

### Claim 12 (depends on 11)

The signature matching engine of claim 11, wherein the memory table of the internal memory block comprises an address field of a memory table in which a previous substring is stored, an address field of a memory table in which a next substring is stored, a character column field of a substring to be stored, a field for displaying whether the next substring exists, a field for displaying whether the substring to be stored is a first substring, and a field for displaying whether a memory is assigned to the internal memory block.

### Claim 13 (depends on 11)

The signature matching engine of claim 11, wherein the memory table of the external memory block comprises an address field of a memory table in which a next substring is stored, a character column field of a substring to be stored, a field for displaying information on the size of the character column of the substring to be stored, a field for displaying whether the next substring exists, a field for displaying whether the substring to be stored is the last substring, and a field for displaying whether a memory is assigned to the external memory block.

### Claim 14 (depends on 1)

The signature matching engine of claim 1, wherein, when the memory table including the substrings is stored in the internal memory block, the memory table is provided in the address of the internal memory block matched to the hash value of the substring.

### Claim 15 (depends on 14)

The signature matching engine of claim 14, wherein a character column of a predetermined size is stored in the substrings to be stored in the internal memory block memory table.

### Claim 16 (depends on 11)

The signature matching engine of claim 11, wherein, when the memory table including the substrings is stored in the external memory block, the substrings are sequentially arranged from an arbitrary external memory block address.

### Claim 17 (depends on 11)

The signature matching engine of claim 11, comprising:
dividing a payload of introduction traffic to be the same as a size of a signature substring character column stored in an internal or external memory block memory table;
calling a memory table of an internal memory block address corresponding to the hash value of the character column to be searched when a character column previous to a character column to be searched in the character columns of the divided introduction traffic was not matched to the stored signature substring;
stopping a matching process when the signature substring stored in the called memory table is not matched to the character column to be searched and analyzing whether the matched signature substring is the last substring in the signature substrings when the signature substring stored in the called memory table is matched to the character column to be searched; and
analyzing whether the character column to be searched is matched to the substring stored in the called external memory block address when an external memory block address is called from the called memory table when the matched signature substring is not the last substring and generating an alarm when the matched signature substring is the last substring.

### Claim 18 (depends on 17)

The signature matching engine of claim 17, wherein, when the character column to be searched is not the last substring and the external memory block address is not called from the called memory table, further comprising analyzing whether the substring stored in the memory table of the internal memory block address corresponding to the hash value of the next character column to be searched is matched to the next character column.

### Claim 19 (depends on 17)

The signature matching engine of claim 17, wherein, when the character column previous to the character column to be searched was matched to the stored signature substring, further comprising:
analyzing whether the external memory block address was called from the memory table in which the matched signature substring is stored; and
analyzing whether the substring stored in the called address is matched to the character column to be searched when the external memory block address is called from the memory table and analyzing whether the substring stored in the internal memory block address corresponding to the character column hash value to be searched is matched to the character column to be searched when the external memory block address was not called from the memory table.

### Claim 20 (depends on 19)

The signature matching engine of claim 19, wherein, a matching process is stopped when the substring stored in the internal or external memory block is not matched to the character column to be searched in analyzing whether the substring stored in the internal or external memory block is matched to the character column to be searched and a process is returned to a process of analyzing whether the matched signature substring is the last substring in the corresponding signature substring when the substring stored in the internal or external memory block is matched to the character column to be searched.
