Augmentation of pattern matching with divergence histograms

• US 10,348,650 B2
• Filed: 04/17/2017
• Issued: 07/09/2019
• Est. Priority Date: 04/17/2017
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Zaifman, Arthur L., Mocenigo, John M., Zdroik, Glen
• Primary Examiner(s): Khirodhar, Maharishi V
• Application Number:
  US15/489,392
• Publication Number:
  US 20180302342A1
• Time in Patent Office: 813 Days
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 49/555 Error detection

Abstract

A processor may apply data blocks of a training data set to a pattern matching algorithm to identify whether the data blocks match a pattern, determine points of divergence between the data blocks and the pattern, count a number of times that each of a plurality of positions in the pattern is determined to be a point of divergence, and determine a position with a highest count of a number of times that the position is determined to be a point of divergence. The processor may further receive an incoming data block, compare a data value at the position in the pattern with the highest count to a data value at a corresponding position in the incoming data block, and determine a mismatch when the data value at the position in the pattern and the data value at the corresponding position in the incoming data block are different.

Claims

1. A device comprising:

a processor; and

a non-transitory computer-readable medium storing instructions which, when executed by the processor, cause the processor to perform operations, the operations comprising;

applying data blocks of a training data set to a pattern matching algorithm, wherein the pattern matching algorithm is a multi-pattern pattern matching algorithm that is associated with a plurality of patterns, wherein the pattern matching algorithm identifies whether the data blocks of the training data set match at least one pattern of the plurality of patterns of the pattern matching algorithm;

determining points of divergence between the data blocks of the training data set and each of the plurality of patterns;

counting a number of times that each of a plurality of positions in the each of the plurality of patterns is determined to be a point of divergence between the data blocks of the training data set and the each of the plurality of patterns;

determining a position in the each of the plurality of patterns with a highest count of a number of times that the position in the each of the plurality of patterns is determined to be the point of divergence between the data blocks of the training data set and the each of the plurality of patterns;

receiving an incoming data block;

comparing a data value at the position in the at least one pattern with the highest count to a data value at a corresponding position in the incoming data block; and

determining a mismatch between the incoming data block and the at least one pattern when the data value at the position in the at least one pattern and the data value at the corresponding position in the incoming data block are different.

2. The device of claim 1, wherein the operations further comprise:

applying the incoming data block to the pattern matching algorithm when the data value at the position in the at least one pattern and the data value at the corresponding position in the incoming data block are the same.

3. The device of claim 1, wherein the at least one pattern is maintained as a finite state machine, a trie, a directed acyclic graph, or a hash table for the pattern matching algorithm.

4. The device of claim 1, wherein the plurality of patterns is maintained as a finite state machine, a trie, a directed acyclic graph, or a hash table for the pattern matching algorithm.

5. The device of claim 1, wherein the comparing the data value and the determining the mismatch comprise:

comparing a data value at the position in the each of the plurality of patterns with the highest count to the data value at the corresponding position in the incoming data block; and

determining a mismatch between the incoming data block and the each of the plurality of patterns when the data value at the position in the each of the plurality of patterns and the data value at the corresponding position in the incoming data block are different.

6. The device of claim 5, wherein when the mismatch between the incoming data block and the each of the plurality of patterns is determined, an additional data block is processed without applying the incoming data block to the pattern matching algorithm.

7. The device of claim 1, wherein a number of the plurality of positions is selected to optimize a total execution time of determining whether each of a plurality of incoming data blocks is a match to the at least one pattern.

8. The device of claim 1, wherein the data blocks of the training data set are associated with a correlative input.

9. The device of claim 8, wherein the correlative input comprises:

a time of day;

a day of week;

a source of the data blocks of the training data set;

a sender identifier;

a recipient identifier;

a port number;

a device type;

a location;

or

a serving base station.

10. The device of claim 8, wherein the operations further comprise:

generating a first histogram containing the position in the at least one pattern with the highest count that is determined, wherein the first histogram is associated with the correlative input.

11. The device of claim 10, wherein at least one additional histogram associated with a different correlative input is created by applying additional data blocks of the training data set associated with a different correlative input to the pattern matching algorithm.

12. The device of claim 11, wherein the operations further comprise:

selecting the first histogram for the comparing the data value at the position in the at least one pattern with the highest count to the data value at the corresponding position in the incoming data block based upon an association of the incoming data block with the correlative input.

13. The device of claim 1, wherein the data blocks of the training data set and the incoming data block comprise:

packet header data;

packet payload data;

executable files;

scripts;

media files;

or

text data.

14. The device of claim 1, wherein the processor is deployed in a communication network, wherein the data blocks of the training data set and the incoming data block comprise network traffic data, wherein the operations further comprise:

processing the incoming data block in accordance with the determining the mismatch between the incoming data block and the at least one pattern.

15. The device of claim 14, wherein the processing comprises:

dropping the incoming data block;

admitting the incoming data block;

storing the incoming data block;

copying the incoming data block;

or

forwarding the incoming data block.

16. A method comprising:

applying, by a processor, data blocks of a training data set to a pattern matching algorithm, wherein the pattern matching algorithm is a multi-pattern pattern matching algorithm that is associated with a plurality of patterns, wherein the pattern matching algorithm identifies whether the data blocks of the training data set match at least one pattern of the plurality of patterns of the pattern matching algorithm;

determining, by the processor, points of divergence between the data blocks of the training data set and each of the plurality of patterns;

counting, by the processor, a number of times that each of a plurality of positions in the each of the plurality of patterns is determined to be a point of divergence between the data blocks of the training data set and the each of the plurality of patterns;

determining, by the processor, a position in the each of the plurality of patterns with a highest count of a number of times that the position in the each of the plurality of patterns is determined to be the point of divergence between the data blocks of the training data set and the each of the plurality of patterns;

receiving, by the processor, an incoming data block;

comparing, by the processor, a data value at the position in the at least one pattern with the highest count to a data value at a corresponding position in the incoming data block; and

determining, by the processor, a mismatch between the incoming data block and the at least one pattern when the data value at the position in the at least one pattern and the data value at the corresponding position in the incoming data block are different.

17. The method of claim 16, further comprising:

applying the incoming data block to the pattern matching algorithm when the data value at the position in the at least one pattern and the data value at the corresponding position in the incoming data block are the same.

18. The method of claim 16, wherein the at least one pattern is maintained as a finite state machine, a trie, a directed acyclic graph, or a hash table for the pattern matching algorithm.

19. The method of claim 16, wherein the plurality of patterns is maintained as a finite state machine, a trie, a directed acyclic graph, or a hash table for the pattern matching algorithm.

20. A non-transitory computer-readable storage medium storing instructions which, when executed by a processor, cause the processor to perform operations, the operations comprising:

applying data blocks of a training data set to a pattern matching algorithm, wherein the pattern matching algorithm is a multi-pattern pattern matching algorithm that is associated with a plurality of patterns, wherein the pattern matching algorithm identifies whether the data blocks of the training data set match at least one pattern of the plurality of patterns of the pattern matching algorithm;

determining points of divergence between the data blocks of the training data set and each of the plurality of patterns;

counting a number of times that each of a plurality of positions in the each of the plurality of patterns is determined to be a point of divergence between the data blocks of the training data set and the each of the plurality of patterns;

determining a position in the each of the plurality of patterns with a highest count of a number of times that the position in the each of the plurality of patterns is determined to be the point of divergence between the data blocks of the training data set and the each of the plurality of patterns;

receiving an incoming data block;

comparing a data value at the position in the at least one pattern with the highest count to a data value at a corresponding position in the incoming data block; and

determining a mismatch between the incoming data block and the at least one pattern when the data value at the position in the at least one pattern and the data value at the corresponding position in the incoming data block are different.