# US 2008/0189784 A1 · Method and Apparatus for Deep Packet Inspection

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

- Number: US 2008/0189784 A1
- Document ID: US20080189784A1
- Status: Published application
- Kind: A1
- Application number: 11/574,878
- Filed: 2005-09-07
- Published: 2008-08-07
- Earliest claimed: 2004-09-10
- Assignees: The Regents of the University of California
- Inventors: William Mangione-Smith; Young H. Cho
- Web page: https://patentgrep.com/patent/US20080189784A1

## CPC

- H04L 63/0245: {Filtering by information in the payload}
- G06F 21/566: {Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities}
- H04L 63/145: {the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms}
- 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

A system and method is provided for detecting malicious data such as, for example, viruses in a computer network. More specifically, system and method utilizes filters to detect pre-identified patterns or threat signatures in a data stream. In one embodiment, a deep packet inspection system for detecting a plurality of malicious programs in a data packet received from a network, wherein each malicious program has a unique pattern comprising a plurality of segments, includes a plurality of pattern detection modules configured to receive one or more data packets in parallel, wherein each of the plurality of pattern detection modules has an output, and one or more long pattern state machines coupled to the outputs of the plurality of pattern detection modules. The deep packet inspection system is configured to detect a pattern of any length at any location within a data packet.

## Claims

### Claim 1

A method for detecting one or more malicious programs contained in a data packet received from a network, wherein each malicious program has a unique pattern comprising a plurality of segments, said method comprising the steps of:
storing the pattern of each malicious program in a memory module, wherein each pattern is addressed within the memory module by an index generated by hashing one or more of the segments within the pattern, further wherein the one or more segments to be hashed are hashed at any position within the pattern;
receiving a data packet having a plurality of segments from the network;
generating an index for the received data packet by hashing one or more segments within the received data packet;
searching the memory module for an index matching the index of the received data packet;
retrieving the pattern within the memory corresponding to the index matching the index of the received data packet;
comparing the retrieved pattern with the received data packet; and
outputting the index of the received data packet if the retrieved pattern matches data within the received packet.

### Claim 2 (depends on 1)

The method of claim 1, wherein the memory module further stores an offset for each pattern representing the position of the one or more segments hashed within the pattern, the method further comprising the step of delaying the outputting step by the value of the offset.

### Claim 3 (depends on 1)

The method of claim 1, further comprising dividing each pattern into a plurality of segments.

### Claim 4 (depends on 1)

The method of claim 1, further comprising dividing each pattern into a plurality of segments in accordance with a keyword tree.

### Claim 5

A deep packet inspection system for detecting one or more malicious programs in a data packet received from a network, wherein each malicious program has a unique pattern comprising a plurality of segments, said system comprising:
a plurality of pattern detection modules configured to receive one or more data packets in parallel, wherein each of the plurality of pattern detection modules has an output and an input; and
one or more multiplexers coupled to the outputs of the plurality of pattern detection modules, wherein each of the one or more multiplexers has an output.

### Claim 6 (depends on 5)

The deep packet inspection system of claim 5, further comprising one or more long pattern state machines coupled to the outputs of the one or more multiplexers, wherein the one or more pattern detection modules each include a memory having an entry length and wherein the long pattern state machine is configured to detect patterns that are longer than the width of the memory of a pattern detection module.

### Claim 7 (depends on 6)

The deep packet inspection system of claim 6, wherein the one or more long pattern state machines comprise parallel predictive long pattern state machines.

### Claim 8 (depends on 6)

The deep packet inspection system of claim 6, wherein the one or more long pattern state machines comprise retrospective long pattern state machines.

### Claim 9 (depends on 5)

The deep packet inspection system of claim 5, further comprising a switched pipeline coupled to the output of at least one of the plurality of pattern detection modules.

### Claim 10 (depends on 5)

The deep packet inspection system of claim 5, wherein a pattern detection module comprises:
a means for storing the pattern of each malicious program in a memory module, wherein each pattern is addressed within the memory module by an index generated by hashing one or more of the segments within the pattern, further wherein the one or more segments to be hashed are hashed at any position within the pattern;
a means for receiving a data packet having a plurality of segments from the network;
a means for generating an index for the received data packet by hashing one or more segments within the received data packet;
a means for searching the memory module for an index matching the index of the received data packet;
a means for retrieving the pattern within the memory corresponding to the index matching the index of the received data packet;
a means for comparing the retrieved pattern with the received data packet; and
a means for outputting the index of the received data packet if the retrieved pattern matches data within the received packet.

### Claim 11 (depends on 5)

The deep packet inspection system of claim 5, wherein a pattern detection module comprises:
a circuit for storing the pattern of each malicious program in a memory module, wherein each pattern is addressed within the memory module by an index generated by hashing one or more of the segments within the pattern, further wherein the one or more segments to be hashed are hashed at any position within the pattern;
a circuit for receiving a data packet having a plurality of segments from the network;
a circuit for generating an index for the received data packet by hashing one or more segments within the received data packet;
a circuit for searching the memory module for an index matching the index of the received data packet;
a circuit for retrieving the pattern within the memory corresponding to the index matching the index of the received data packet;
a circuit for comparing the retrieved pattern with the received data packet; and
a circuit for outputting the index of the received data packet if the retrieved pattern matches data within the received packet.

### Claim 12 (depends on 5)

The deep packet inspection system of claim 5, wherein the system is configured to divide each pattern into a plurality of segments in accordance with a keyword tree.

### Claim 13 (depends on 5)

The deep packet inspection system of claim 5, further comprising a pattern divider coupled to the inputs of the plurality of pattern detection modules.

### Claim 14

A deep packet inspection system for detecting one or more malicious programs in a data packet received from a network, wherein each malicious program has a unique pattern comprising a plurality of segments, said system comprising:
a reconfigurable deep packet filter; and
a dynamic deep packet filter coupled to the reconfigurable deep packet filter in parallel.

### Claim 15 (depends on 14)

The deep packet inspection system of claim 14, wherein the dynamic deep packet filter is implemented in a coprocessor.

### Claim 16 (depends on 14)

The deep packet inspection system of claim 14, wherein the system is implemented as a single field programmable gate array device.

### Claim 17 (depends on 14)

The deep packet inspection system of claim 14, wherein the dynamic deep packet filter comprises a plurality of pattern detection modules.

### Claim 18 (depends on 17)

The deep packet inspection system of claim 17, wherein the plurality of pattern detection modules each comprises:
a means for storing the pattern of each malicious program in a memory module, wherein each pattern is addressed within the memory module by an index;
a means for receiving a data packet having a plurality of segments from the network;
a means for generating an index for the received data packet;
a means for searching the memory module for an index matching the index of the received data packet;
a means for retrieving the pattern within the memory corresponding to the index matching the index of the received data packet;
a means for comparing the retrieved pattern with the received data packet; and
a means for outputting the index of the received data packet if the retrieved pattern matches data within the received packet.

### Claim 19 (depends on 18)

The deep packet inspection system of claim 18, wherein the index is generated by hashing one or more of the segments within the pattern.

### Claim 20 (depends on 19)

The deep packet inspection system of claim 19, wherein the one or more segments to be hashed are hashed at any position within the pattern.

### Claim 21 (depends on 18)

The deep packet inspection system of claim 18, wherein the index for the received data packet is generated by hashing one or more segments within the received data packet.

### Claim 22 (depends on 17)

The deep packet inspection system of claim 17, wherein a pattern detection module comprises:
a circuit for storing the pattern of each malicious program in a memory module, wherein each pattern is addressed within the memory module by an index generated by hashing one or more of the segments within the pattern, further wherein the one or more segments to be hashed are hashed at any position within the pattern;
a circuit for receiving a data packet having a plurality of segments from the network;
a circuit for generating an index for the received data packet by hashing one or more segments within the received data packet;
a circuit for searching the memory module for an index matching the index of the received data packet;
a circuit for retrieving the pattern within the memory corresponding to the index matching the index of the received data packet;
a circuit for comparing the retrieved pattern with the received data packet; and
a circuit for outputting the index of the received data packet if the retrieved pattern matches data within the received packet.

### Claim 23 (depends on 22)

The deep packet inspection system of claim 22, wherein the index is generated by hashing one or more of the segments within the pattern.

### Claim 24 (depends on 23)

The deep packet inspection system of claim 23, wherein the one or more segments to be hashed are hashed at any position within the pattern.

### Claim 25 (depends on 22)

The deep packet inspection system of claim 22, wherein the index for the received data packet is generated by hashing one or more segments within the received data packet.

### Claim 26 (depends on 14)

The deep packet inspection system of claim 14, wherein the dynamic deep packet filter comprises:
a plurality of pattern detection modules configured to receive one or more data packets in parallel, wherein each of the plurality of pattern detection modules has an output and an input; and
one or more multiplexers coupled to the outputs of the plurality of pattern detection modules, wherein each of the one or more multiplexers has an output.

### Claim 27 (depends on 26)

The deep packet inspection system of claim 26, wherein the dynamic deep packet filter further comprises one or more long pattern state machines coupled to the outputs of the one or more multiplexers, wherein the one or more pattern detection modules each include a memory having an entry length and wherein the long pattern state machine is configured to detect patterns that are longer than the width of the memory of a pattern detection module.

### Claim 28 (depends on 27)

The deep packet inspection system of claim 27, wherein the one or more long pattern state machines are parallel predictive long pattern state machines.

### Claim 29 (depends on 27)

The deep packet inspection system of claim 27, wherein the one or more long pattern state machines are retrospective long pattern state machines.

### Claim 30 (depends on 14)

The deep packet inspection system of claim 14, wherein the dynamic deep packet filter further comprises a switched pipeline coupled to the output of at least one of the plurality of pattern detection modules.

### Claim 31 (depends on 26)

The deep packet inspection system of claim 26, further comprising a pattern divider coupled to the inputs of the plurality of pattern detection modules.

### Claim 32 (depends on 14)

The deep packet inspection system of claim 14, wherein the system supports a Snort network intrusion detection system.

### Claim 33 (depends on 26)

The deep packet inspection system of claim 26, further comprising a priority multiplexer coupled to the outputs of the plurality of pattern detection modules.

### Claim 34 (depends on 14)

The deep packet inspection system of claim 14, wherein the dynamic deep packet filter comprises:
a plurality of pattern detection modules operating in parallel, each having an input and an output;
a switched pipeline coupled to the outputs of the plurality of pattern detection modules; and
a long pattern state machine coupled to the outputs of the plurality of pattern detection modules in parallel with the switched pipeline.

### Claim 35 (depends on 34)

The deep packet inspection system of claim 34, wherein the one or more long pattern state machines are parallel predictive long pattern state machines.

### Claim 36 (depends on 34)

The deep packet inspection system of claim 34, wherein the one or more long pattern state machines are retrospective long pattern state machines.

### Claim 37 (depends on 34)

The deep packet inspection system of claim 34, further comprising a pattern divider coupled to the inputs of the plurality of pattern detection modules.

### Claim 38 (depends on 37)

The deep packet inspection system of claim 37, wherein the pattern divider operates in accordance with a keyword tree.