ACCELERATED PATTERN MATCHING USING PATTERN FUNCTIONS

• US 20180034779A1
• Filed: 07/29/2016
• Published: 02/01/2018
• Est. Priority Date: 07/29/2016
• Status: Active Grant

• Current Assignee: Fortinet Inc.
• Original Assignee: ShieldX Networks, Inc. (Fortinet Inc.)
• Inventors: Ahuja, Ratinder Paul Singh, Nedbal, Manuel, Gangashanaiah, Sumanth
• Granted Patent: US 10,212,133 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 63/0236 Filtering by address, protocol, port number or service, e.g. IP-address or URL
• 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

System, methods, and apparatuses enable a network security system to more efficiently perform pattern matching against data items. For example, the disclosed approaches may be used to improve the way in which a deep packet inspection (DPI) microservice performs pattern matching against data items (e.g., network traffic, files, email messages, etc.) in order to detect various types of network security threats (e.g., network intrusion attempts, viruses, spam, and other potential network security issues). A DPI microservice generally refers to an executable component of a network security system that monitors and performs actions relative to input data items for purposes related to computer network security.

Claims

1. A computer-implemented method, comprising:

generating one or more first pattern results, the first pattern results indicating that one or more first patterns of a first set of patterns were determined to exist in a data item based on regular expression matching the one or more first patterns against the data item;

generating one or more second pattern results, the one or more second pattern results indicating that one or more second patterns of a second set of patterns were determined to exist in the data item based on processing the data item by applying one or more pattern functions to the data item;

merging the first pattern results and the second pattern results to create third pattern results;

performing an action relative to the data item based at least in part on the third pattern results.

2. The method of claim 1, further comprising:

partitioning a set of input patterns into the first set of patterns and the second set of patterns;

wherein the first set of patterns includes patterns from the set of input patterns determined to not include a pattern element specifying a fixed offset.

3. The method of claim 1, further comprising:

partitioning a set of input patterns into the first set of patterns and the second set of patterns;

wherein the second set of patterns includes patterns from the set of input patterns determined to include a pattern element specifying fixed offset.

4. The method of claim 1, wherein each pattern function of the one or more pattern functions involves determining whether one or more particular patterns exist in data items without performing regular expression matching.

5. The method of claim 1, wherein at least one pattern function of the one or more pattern functions involves determining whether one or more particular patterns exist in data items based on a string comparison function.

6. The method of claim 1, wherein the generating the one or more first pattern results further comprises:

wherein one or more particular first patterns of the first patterns are specified in a first pattern table;

in response to determining that the one or more particular first patterns exist in a first portion of the data item, selecting a second pattern table from a plurality of pattern tables;

determining whether one or more second patterns of the second pattern table exist in a second portion of the data item, wherein the second portion of the data item is not compared against the one or more particular first patterns of the first pattern table;

wherein the first pattern results include the first particular patterns and the second patterns.

7. The method of claim 1, wherein the data item comprises character-based data.

8. The method of claim 1, wherein the data item comprises one or more of:

an application protocol message, a network protocol message, an email message, a file.

9. The method of claim 1, wherein the data item is received by a deep packet inspection (DPI) microservice.

10. The method of claim 1, wherein the data item is received by a deep packet inspection (DPI) microservice, and wherein the DPI microservice comprises a software container.

11. The method of claim 1, wherein the action comprises one or more:

dropping the data item, rejecting the data item, deleting the data item, quarantining the data item.

12. The method of claim 1, wherein the one or more first pattern results are generated concurrently with generating the one or more second pattern results.

13. One or more non-transitory computer-readable storage media storing instructions which, when executed by one or more hardware processors, cause performance of:

generating one or more first pattern results, the first pattern results indicating that one or more first patterns of a first set of patterns were determined to exist in a data item based on regular expression matching the one or more first patterns against the data item;

generating one or more second pattern results, the one or more second pattern results indicating that one or more second patterns of a second set of patterns were determined to exist in the data item based on processing the data item by applying one or more pattern functions to the data item;

merging the first pattern results and the second pattern results to create third pattern results;

performing an action relative to the data item based at least in part on the third pattern results

14. The one or more non-transitory storage media of claim 13, wherein the instructions which, when executed by the one or more computing devices, further cause:

partitioning a set of input patterns into the first set of patterns and the second set of patterns;

wherein the first set of patterns includes patterns from the set of input patterns determined to not include a pattern element specifying a fixed offset.

15. The one or more non-transitory storage media of claim 13, wherein the instructions which, when executed by the one or more computing devices, further cause:

partitioning a set of input patterns into the first set of patterns and the second set of patterns;

wherein the second set of patterns includes patterns from the set of input patterns determined to include a pattern element specifying fixed offset.

16. The one or more non-transitory storage media of claim 13, wherein each pattern function of the one or more pattern functions involves determining whether one or more particular patterns exist in data items without performing regular expression matching.

17. The one or more non-transitory storage media of claim 13, wherein at least one pattern function of the one or more pattern functions involves determining whether one or more particular patterns exist in data items based on a string comparison function.

18. The one or more non-transitory storage media of claim 13, wherein the generating the one or more first pattern results further comprises:

wherein one or more particular first patterns of the first patterns are specified in a first pattern table;

in response to determining that the one or more particular first patterns exist in a first portion of the data item, selecting a second pattern table from a plurality of pattern tables;

determining whether one or more second patterns of the second pattern table exist in a second portion of the data item, wherein the second portion of the data item is not compared against the one or more particular first patterns of the first pattern table;

wherein the first pattern results include the first particular patterns and the second patterns.

19. The one or more non-transitory storage media of claim 13, wherein the data item comprises character-based data.

20. The one or more non-transitory storage media of claim 13, wherein the data item comprises one or more of:

an application protocol message, a network protocol message, an email message, a file.

21. The one or more non-transitory storage media of claim 13, wherein the data item is received by a deep packet inspection (DPI) microservice.

22. The one or more non-transitory storage media of claim 13, wherein the data item is received by a deep packet inspection (DPI) microservice, and wherein the DPI microservice comprises a software container.

23. The one or more non-transitory storage media of claim 13, wherein the action comprises one or more:

dropping the data item, rejecting the data item, deleting the data item, quarantining the data item.

24. The one or more non-transitory storage media of claim 13, wherein the one or more first pattern results are generated concurrently with generating the one or more second pattern results.

25. An apparatus, comprising:

one or more hardware processors;

memory coupled to the one or more hardware processors, the memory storing instructions which, when executed by the one or more hardware processors, causes the apparatus to;

generate one or more first pattern results, the first pattern results indicating that one or more first patterns of a first set of patterns were determined to exist in a data item based on regular expression matching the one or more first patterns against the data item;

generate one or more second pattern results, the one or more second pattern results indicating that one or more second patterns of a second set of patterns were determined to exist in the data item based on processing the data item by applying one or more pattern functions to the data item;

merge the first pattern results and the second pattern results to create third pattern results;

perform an action relative to the data item based at least in part on the third pattern results.

26. The apparatus of claim 25, wherein the instructions which, when executed by the one or more hardware processors, further causes the apparatus to:

partition a set of input patterns into the first set of patterns and the second set of patterns;

wherein the first set of patterns includes patterns from the set of input patterns determined to not include a pattern element specifying a fixed offset.

27. The apparatus of claim 25, wherein the instructions which, when executed by the one or more hardware processors, further causes the apparatus to:

partition a set of input patterns into the first set of patterns and the second set of patterns;

wherein the second set of patterns includes patterns from the set of input patterns determined to include a pattern element specifying fixed offset.

28. The apparatus of claim 25, wherein each pattern function of the one or more pattern functions involves determining whether one or more particular patterns exist in data items without performing regular expression matching.

29. The apparatus of claim 25, wherein at least one pattern function of the one or more pattern functions involves determining whether one or more particular patterns exist in data items based on a string comparison function.

30. The apparatus of claim 25, wherein the instructions which, when executed by the one or more hardware processors, further causes the apparatus to:

wherein one or more particular first patterns of the first patterns are specified in a first pattern table;

in response to determining that the one or more particular first patterns exist in a first portion of the data item, select a second pattern table from a plurality of pattern tables;

determine whether one or more second patterns of the second pattern table exist in a second portion of the data item, wherein the second portion of the data item is not compared against the one or more particular first patterns of the first pattern table;

wherein the first pattern results include the first particular patterns and the second patterns.