Augmentation of pattern matching with divergence histograms

• US 10,645,030 B2
• Filed: 07/08/2019
• Issued: 05/05/2020
• 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:
  US16/505,548
• Publication Number:
  US 20190334839A1
• Time in Patent Office: 302 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;

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 identifies whether the data blocks of the training data set match a pattern of the pattern matching algorithm;

determining points of divergence between the data blocks of the training data set and the pattern;

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

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

receiving an incoming data block;

comparing 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;

determining a mismatch between the incoming data block and the pattern 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; and

processing an additional incoming data block without applying the incoming data block to the pattern matching algorithm when the mismatch is determined.

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

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

3. The device of claim 1, wherein the 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 pattern matching algorithm is a multi-pattern pattern matching algorithm that is associated with a plurality of patterns, wherein the plurality of patterns includes the pattern.

5. The device of claim 4, 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.

6. The device of claim 1,

wherein the determining the position in the pattern comprises determining a plurality of positions in the pattern with highest counts of a number of times that each of the plurality of positions in the pattern is determined to be a point of divergence between the data blocks of the training data set and the pattern;

wherein the comparing comprises comparing data values at the plurality of positions in the pattern with the highest counts to data values at corresponding positions in the incoming data block; and

wherein the determining the mismatch comprises determining the mismatch between the incoming data block and the pattern when a data value of at least one of the plurality of positions in the pattern and a data value of at least one a plurality of corresponding positions in the incoming data block are different.

7. The device of claim 6, 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 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;

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 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 the 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 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 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 identifies whether the data blocks of the training data set match a pattern of the pattern matching algorithm;

determining, by the processor, points of divergence between the data blocks of the training data set and the pattern;

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

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

receiving, by the processor, an incoming data block;

comparing, by the processor, 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;

determining, by the processor, a mismatch between the incoming data block and the pattern 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; and

processing, by the processor, an additional incoming data block without applying the incoming data block to the pattern matching algorithm when the mismatch is determined.

17. The method of claim 16, further comprising:

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

18. The method of claim 16, wherein the 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 pattern matching algorithm is a multi-pattern pattern matching algorithm that is associated with a plurality of patterns, wherein the plurality of patterns includes the pattern.

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 identifies whether the data blocks of the training data set match a pattern of the pattern matching algorithm;

determining points of divergence between the data blocks of the training data set and the pattern;

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

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

receiving an incoming data block;

comparing 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;

determining a mismatch between the incoming data block and the pattern 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; and

processing an additional incoming data block without applying the incoming data block to the pattern matching algorithm when the mismatch is determined.