Efficient access to sparse packets in large repositories of stored network traffic

• US 9,537,972 B1
• Filed: 02/05/2015
• Issued: 01/03/2017
• Est. Priority Date: 02/20/2014
• Status: Active Grant

• Current Assignee: Fireeye Security Holdings US LLC
• Original Assignee: FireEye, Inc.
• Inventors: Edwards, Dennis Lee, Fauerbach, Christopher Hayes
• Primary Examiner(s): Thompson, Jr., Otis L
• Application Number:
  US14/614,985
• Time in Patent Office: 698 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC

Abstract

A secondary indexing technique cooperates with primary indices of an indexing arrangement to enable efficient storage and access of metadata used to retrieve packets persistently stored in data files of a data repository. Efficient storage and access of the metadata used to retrieve the persistently stored packets may be based on a target value of the packets over a search time window. The metadata is illustratively organized as a metadata repository of primary index files that store the primary indices containing hash values of network flows of the packets, as well as offsets and paths to those packets stored in the data files. The technique includes one or more secondary indices having a plurality of present bits arranged in a binary format (i.e., a bit array) to indicate the presence of the target value in one or more packets stored in the data files over the search time window. Notably, the present bits may be used to reduce (i.e., “prune”) a relatively large search space of the stored packets (e.g., defined by the hash values) to a pruned search space of only those data files in which packets having the target value are stored.

Claims

1. A method comprising:

capturing a first packet from a network;

annotating the first packet with a time stamp specifying an arrival time of the first packet;

s storing the first packet in a first data file of a set of data files organized at predetermined intervals, the first data file dedicated to a first predetermined interval based on the time stamp;

creating a first primary index for the first packet, the first primary index containing a path and an offset to the first packet stored in the first data file;

storing the first primary index for the first packet in a first primary index file associated with the first data file dedicated to the first predetermined interval; and

creating a secondary index for the first packet, the secondary index having an ordered sequence of present bits, wherein a first present bit corresponds to the first primary index and the first data file dedicated to the first predetermined interval, and wherein an asserted value of the first present bit indicates presence of a target value in the first packet stored in the first data file over a search time window.

4. The method of claim 1 further comprising storing the secondary index in a secondary index file associated with the search time window.

5. The method of claim 4 wherein storing the secondary index in the secondary index file comprises organizing the secondary index file as a data structure that stores the secondary index over the search time window.

6. The method of claim 5 wherein the data structure is a n-way trie and wherein the n-way trie is organized based on the target value.

7. The method of claim 6 further comprising organizing the n-way trie as a plurality of internal nodes and leaf nodes, wherein each internal node is composed of an array of elements accessible by keys formed from subsets of the target value.

8. The method of claim 7 wherein each element of each internal node contains a key of a child of the internal node and wherein one of the leaf nodes contains the secondary index.

9. The method of claim 8 further comprising storing the n-way trie of the secondary index file on disk by only storing the leaf node having an asserted value of the first present bit of the secondary index.

10. The method of claim 9 further comprising storing a header file associated with the n-way trie of the secondary index file on disk, the header file containing one of the time stamp of an earliest second within the search time window associated with the secondary index file, a number of internal nodes allocated in the n-way trie, and the number of leaf nodes allocated in the n-way trie.

11. The method of claim 9 further comprising, in response to a request to retrieve packets having the target value, utilizing the keys to traverse the internal nodes of the n-way trie until reaching the leaf node containing the secondary index.

12. The method of claim 1 wherein each of the predetermined intervals is one second, and wherein the time stamp of the first packet comprises the first predetermined interval between a beginning of a second and the beginning of a next second dedicated to the first data file.

13. The method of claim 12 wherein each data file of the set of data files contains packets captured from the network and annotated with time stamps at the predetermined intervals of seconds.

14. The method of claim 13 wherein the ordered sequence comprises 3600 present bits and wherein the search time window is an hour.

15. The method of claim 14 wherein asserted binary values of the 3600 present bits within the ordered sequence identify the data files of the set of data files that contain at least one packet having the target value within the search time window of the hour.

2. The method of 1 wherein the target value is an element of a network flow.

3. The method of 2 wherein the element is one of an internet protocol address and a port number.

16. A system comprising:

one or more processors coupled to a network;

a plurality of storage repositories coupled to the one or more processors, the storage repositories including a data repository having data files configured to store packets captured from the network and a metadata repository having primary and secondary index files configured to store primary and secondary indices, the primary indices having hash values along with paths and offsets to the captured packets stored in the data files, the hash values calculated from a hash function applied to network flows of the captured packets, the secondary indices having a plurality of present bits arranged to indicate presence of a target value in one or more of the captured packets stored in the data files over a search time window; and

a memory coupled to the one or more processors and configured to store one or more processes of an operating system, the one or more processes executable by the one or more processors to use the present bits of the secondary indices to prune a search space of the captured packets as defined by the hash values to a pruned search space of only the data files of the data repository storing captured packets having the target value, the one or more processes further executable to use the paths and the offsets of the primary indices having the hash values defined by the pruned search space to retrieve the captured packets having the target value from the data repository.

17. The system of claim 16 wherein the target value is an element of a network flow.

18. The system of claim 16 wherein the secondary index file is organized as a data structure that stores the secondary indices over the search time window.

19. The system of claim 18 wherein the data structure is a n-way trie having a plurality of internal nodes and leaf nodes, wherein each internal node is composed of an array of elements accessible by keys formed from subsets of the target value.

20. A non-transitory computer readable medium including program instructions for execution on one or more processors, the program instructions when executed operable to:

capture a packet from a network;

annotate the packet with a time stamp specifying an arrival time of the packet;

store the packet in a data file of a set of data files organized at predetermined intervals, the data file dedicated to a predetermined interval based on the time stamp;

create a primary index for the packet, the primary index containing a path and an offset to the packet stored in the data file;

store the primary index for the packet in a primary index file associated with the data file dedicated to the predetermined interval; and

create secondary index for the packet, the secondary index having an ordered sequence of present bits, wherein a present bit corresponds to the primary index and the data file dedicated to the predetermined interval, and wherein an asserted value of the present bit indicates presence of a target value in the packet stored in the data file over a search time window.