Facilitating storage and querying of payload attribution information

• US 20060072582A1
• Filed: 09/27/2005
• Published: 04/06/2006
• Est. Priority Date: 09/27/2004
• Status: Active Grant

• Current Assignee: Polytechnic Institute Of New York University (New York University)
• Original Assignee: Polytechnic Institute Of New York University (New York University)
• Inventors: Memon, Nasir, Bronnimann, Herve, Shanmugasundaram, Kulesh
• Granted Patent: US 7,933,208 B2
• Time in Patent Office: Days
• US Class Current: 370/395.320
• CPC Class Codes: H04L 12/2854 Wide area networks, e.g. public data networks
• CPC Class Codes: H04L 2463/146 Tracing the source of attacks
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

A hierarchical data structure of digested payload information (e.g., information within a payload, or information spanning two or more payloads) allows a payload excerpt to be attributed to earlier network flow information. These compact data structures permit data storage reduction, while permitting efficient query processing with a low level of false positives. One example of such a compact data structure is a hierarchical Bloom filter. Different layers of the hierarchy may correspond to different block sizes.

Claims

1. A method comprising:

a) accepting network flows;

b) for each flow, storing a summary of payload content of the flow using a summarizing function, wherein each summary stored is associated with flow attributes;

c) accepting a query including a query parameter which includes at least an excerpt of payload content;

d) determining a summary of the query parameter using the summarizing function;

e) finding one or more summaries of payload content of the flows that match the summary of the query parameter, by searching the stored summaries of the payload content of the flows; and

f) obtaining flow attributes associated with the found one or more summaries of content of the flows.

2. The method of claim 1 wherein the summarizing function is a hash function.

3. The method of claim 1 wherein the flow attributes include at least one of a source Internet protocol address and a destination Internet protocol address.

4. The method of claim 1 wherein the flow attributes include at least one of a source port and a destination port.

5. The method of claim 1 wherein the act of storing, for each flow, a summary of payload content of the flow using a summary function, includes

segmenting the payload content into blocks of various lengths, and

storing summaries of the blocks in a hierarchical Bloom filter.

6. The method of claim 1 wherein the act of storing, for each flow, a summary of payload content of the flow using a summary function, includes

segmenting the payload content into blocks of various lengths,

adding block offset information to each of the blocks to generate a plurality of blocks with offset information, and

storing summaries of the plurality of blocks with offset information in a hierarchical Bloom filter.

7. The method of claim 1 wherein the act of storing, for each flow, a summary of payload content of the flow using a summary function, includes

segmenting the payload content into blocks of various lengths,

adding the flow attribute information to each of the blocks to generate a plurality of blocks with attribute information, and

storing summaries of the plurality of blocks with attribute information in a hierarchical Bloom filter.

8. A method comprising:

a) accepting a payload content and attribute information of a flow;

b) segmenting the payload content into blocks of various lengths;

c) for each of the blocks, determining a summary of the block using a summarizing function, to generate summarized blocks; and

d) storing the summarized blocks in a hierarchical data structure, wherein the hierarchy corresponds to block length, and wherein the summarized blocks are associated with the attribute information.

9. The method of claim 8 wherein the summarizing function is a hash function, and wherein the hierarchical data structure is a hierarchical Bloom filter.

10. The method of claim 8 further comprising:

e) for each of the blocks,

i) adding block offset information to the block to generate a block with offset information, and

ii) determining a summary of the block with offset information using a summarizing function, to generate a summarized block with offset information; and

f) storing the summarized blocks with offset information in a hierarchical data structure, wherein the hierarchy corresponds to block length, and wherein the summarized blocks with offset information are associated with the attribute information.

11. The method of claim 8 further comprising:

e) for each of the blocks,

i) adding the attribute information to the block to generate a block with attribute information, and

ii) determining a summary of the block with attribute information using a summarizing function, to generate a summarized block with attribute information; and

f) storing the summarized blocks with attribute information in a hierarchical data structure, wherein the hierarchy corresponds to block length.

12. A method comprising:

a) accepting a query including a query parameter which includes at least an excerpt of payload content;

b) determining a summary of the query parameter using a summarizing function;

c) finding one or more summaries of payload content that match the summary of the query parameter, by searching, in a hierarchical manner, a hierarchical data structure in which summaries of the payloads of packets are stored; and

d) obtaining attribute information associated with the found one or more summaries.

13. Apparatus comprising:

a) means for accepting network flows;

b) means, for each flow, for storing a summary of payload content of the flow using a summarizing function, wherein each summary stored is associated with flow attributes;

c) means for accepting a query including a query parameter which includes at least an excerpt of payload content;

d) means for determining a summary of the query parameter using the summarizing function;

e) means for finding one or more summaries of payload content of the flows that match the summary of the query parameter, by searching the stored summaries of the payload content of the flows; and

f) means for obtaining flow attributes associated with the found one or more summaries of content of the flows.

14. A computer-readable medium having stored thereon a computer-readable data structure comprising:

a) a summary of blocks, the blocks corresponding to segments, of various lengths, of payload content of a network flow; and

b) a hierarchical data structure arranging the summary of blocks,

wherein the hierarchy corresponds to block length, and

wherein the summarized blocks are associated with attribute information of the network flow.

15. The computer-readable medium of claim 14 wherein the summary of blocks are a hash of information including block information, and wherein the hierarchical data structure is a hierarchical Bloom filter.