Efficient signature packing for an intrusion detection system

• US 7,624,446 B1
• Filed: 01/25/2005
• Issued: 11/24/2009
• Est. Priority Date: 01/25/2005
• Status: Expired due to Fees

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Wilhelm, Jeffrey
• Primary Examiner(s): Vu; Kimyen
• Assistant Examiner(s): BLAIR, APRIL YING SHAN
• Application Number:
  US11/043,649
• Time in Patent Office: 1,764 Days
• Field of Search: 726 22- 25, 713187-188
• US Class Current: 726/23
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

Abstract

A flow assignment module identifies different network flows'"'"' characteristics and the characteristics of the signatures for the different network flows. Based on the identified characteristics, the flow assignment module assigns a network flow to a hash table among a small set of hash tables for storing signatures for that network flow. The flow assignment module assigns the network flow in such a way to minimize the likelihood that a signature for the network flow is hashed to a table entry that frequently occurs in a different network flow assigned to the same hash table. The flow assignment module identifies a hash table for the network flow where there is the least overlap between a signature for that network flow and a frequent byte in another network flow.

Claims

1. A computer-implemented method of packing a signature that detects a malicious data stream for an intrusion detection system, the method comprising:

using a computer processor configured to execute method steps comprising;

identifying a network flow;

identifying a plurality of signatures associated with the network flow, the signatures for detecting a malicious data stream within the network flow;

comparing the signatures of the network flow to byte frequency distributions of a plurality of other network flows, each of the other network flows assigned to one of a plurality of hash tables;

assigning, based on the comparison, the network flow to a particular hash table selected from the plurality of hash tables, the particular hash table selected to minimize a likelihood that a hash function maps a signature for the network flow to a same table address in the hash table as is mapped a frequently occurring byte within one of the other network flows also assigned to the hash table, wherein each network flow using a critical communications protocol is assigned to a separate hash table, and wherein each network flow using a non-critical communications protocol is assigned to one of the separate hash tables selected to minimize the overlap between a byte frequency distribution of a data stream within the critical communications protocol network flow assigned to the hash table and a byte frequency distribution of a signature for the non-critical communications protocol network flow; and

storing the plurality of signatures that detect the malicious data stream within the network flow in the assigned hash table.

2. The method of claim 1, wherein storing the signature in the assigned hash table comprises:

hashing one or more bytes of each of the signatures to identify an entry in the hash table for storing each of the signatures.

3. The method of claim 1, further comprising identifying a byte frequency distribution of a signature for the network flow, wherein the comparing step further comprises comparing the byte frequency distribution of the signature for the network flow with the byte frequency distributions of the other network flows.

4. The method of claim 1, wherein assigning the network flow to the hash table comprises:

assigning a weight to each of a plurality of network flows based on the byte frequency distribution of each network flow;

assigning a fixed capacity to each of the plurality of hash tables;

sorting the plurality of network flows in decreasing order of their weights; and

iterating through the sorted plurality of network flows to assign each of the sorted plurality of network flows to a first hash table of the plurality of hash tables that has enough capacity for the network flow'"'"'s assigned weight.

5. The method of claim 1, further comprising:

scanning a data stream using a sliding window to identify one or more bytes of the data stream within the sliding window;

hashing the one or more bytes of the data stream within the sliding window to identify an entry in the hash table;

determining if the identified entry in the hash table stores a signature; and

examining the stored signature to determine if the data stream matches the stored signature.

6. The method of claim 1, wherein the network flow is represented as a tuple comprising information regarding an origination port that originates the network flow, a destination port that receives the network flow, and a communications protocol used by the network flow to transmit data.

7. A computer system for packing a signature that detects a malicious data stream for an intrusion detection system, the computer system comprising:

a processor;

a computer-readable storage medium storing executable software modules that cause the processor to perform steps, comprising;

identifying a network flow;

identifying a plurality of signatures associated with the network flow, the signatures for detecting a malicious data stream within the network flow;

comparing the signatures of the network flow to byte frequency distributions of a plurality of other network flows, each of the other network flows assigned to one of a plurality of hash tables;

assigning, based on the comparison, the network flow to a particular hash table selected from the plurality of hash tables, the particular hash table selected to minimize a likelihood that a hash function maps a signature for the network flow to a same table address in the hash table as is mapped a frequently occurring byte within one of the other network flows also assigned to the hash table, wherein each network flow using a critical communications protocol is assigned to a separate hash table, and wherein each network flow using a non-critical communications protocol is assigned to one of the separate hash tables selected to minimize the overlap between a byte frequency distribution of a data stream within the critical communications protocol network flow assigned to the hash table and a byte frequency distribution of a signature for the non-critical communications protocol network flow; and

storing the plurality of signatures that detect the malicious data stream within the network flow in the assigned hash table.

8. The system of claim 7, wherein the flow assignment module hashes one or more bytes of each of the signatures to identify an entry in the hash table for storing each of the signatures.

9. The system of claim 7, further comprising:

a traffic analysis module for providing the byte frequency distribution of the network flow to the flow assignment module.

10. The system of claim 7, wherein the flow assignment module is adapted to:

assign weight to each of a plurality of network flows based on the byte frequency distribution of each network flow;

assign a fixed capacity to each of the plurality of hash tables;

sort the plurality of network flows in decreasing order of their weights; and

iterate through the sorted plurality of network flows to assign each of the sorted plurality of network flows to a first hash table of the plurality of hash tables that has enough capacity for the network flow'"'"'s assigned weight.

11. The system of claim 7, further comprising:

a scanning module for scanning the data stream using a sliding window to identify one or more bytes of the data stream within the sliding window; and

a hash table lookup module for;

hashing the one or more bytes of the data stream within the sliding window to identify an entry in the hash table,

determining if the identified entry in the hash table stores a signature, and

examining the stored signature to determine if the data stream matches the stored signature.

12. The system of claim 7, wherein the network flow is represented as a tuple comprising information regarding an origination port that originates the network flow, a destination port that receives the network flow, and a communications protocol used by the network flow to transmit data.

13. A computer program product having a computer-readable storage medium having embodied thereon program code for packing a signature that detects a malicious data stream for an intrusion detection system, the program code comprising:

a flow assignment module for;

identifying a network flow;

identifying a plurality of signatures associated with the network flow, the signatures for detecting a malicious data stream within the network flow;

comparing the signatures of the network flow to byte frequency distributions of a plurality of other network flows, each of the other network flows assigned to one of a plurality of hash tables;

assigning, based on the comparison, the network flow to a particular hash table selected from the plurality of hash tables, the particular hash table selected to minimize a likelihood that a hash function maps a signature for the network flow to a same table address in the hash table as is mapped a frequently occurring byte within one of the other network flows also assigned to the hash table, wherein each network flow using a critical communications protocol is assigned to a separate hash table, and wherein each network flow using a non-critical communications protocol is assigned to one of the separate hash tables selected to minimize the overlap between a byte frequency distribution of a data stream within the critical communications protocol network flow assigned to the hash table and a byte frequency distribution of a signature for the non-critical communications protocol network flow; and

storing the plurality of signatures that detect the malicious data stream within the network flow in the assigned hash table.

14. The computer program product of claim 13, wherein the flow assignment module hashes one or more bytes of each of the signatures to identify an entry in the hash table for storing each of the signatures.

15. The computer program product of claim 13, wherein the program code further comprises:

a traffic analysis module for providing the byte frequency distribution of the network flow to the flow assignment module.

16. The computer program product of claim 13, wherein the flow assignment module is adapted to:

assign a weight to each of a plurality of network flows based on the byte frequency distribution of each network flow;

assign a fixed capacity to each of the plurality of hash tables;

sort the plurality of network flows in decreasing order of their weights; and

iterate through the sorted plurality of network flows to assign each of the sorted plurality of network flows to a first hash table of the plurality of hash tables that has enough capacity for the network flow'"'"'s assigned weight.

17. The computer program product of claim 13, wherein the program code further comprises:

a scanning module for scanning the data stream using a sliding window to identify one or more bytes of the data stream within the sliding window; and

a hash table lookup module for;

hashing the one or more bytes of the data stream within the sliding window to identify an entry in the hash table,

determining if the identified entry in the hash table stores a signature, and

examining the stored signature to determine if the data stream matches the stored signature.