Accelerated pattern matching using pattern functions

• US 10,212,133 B2
• Filed: 07/29/2016
• Issued: 02/19/2019
• 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
• Primary Examiner(s): Armouche, Hadi S
• Assistant Examiner(s): Doan, Huan V
• Application Number:
  US15/224,401
• Publication Number:
  US 20180034779A1
• Time in Patent Office: 935 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 specified in a first pattern table were determined to exist in a first portion of the data item based on regular expression matching the one or more first patterns against the first portion of the data item, and further indicating that one or more second patterns of a second set of patterns specified in a second pattern table were determined to exist in a second portion of the data item based on regular expression matching the one or more second patterns against the second portion of the data item, the generation of the one or more first pattern results including;

in response to determining that a first pattern of the first set of patterns exists in the first portion of the data item, selecting the second pattern table from a plurality of pattern tables, and

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

generating one or more second pattern results, the one or more second pattern results indicating that one or more third patterns of a third 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; and

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 data item comprises character-based data.

7. 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.

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

9. 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.

10. 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.

11. 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.

12. 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 specified in a first pattern table were determined to exist in a first portion of the data item based on regular expression matching the one or more first patterns against the first portion of the data item, and further indicating that one or more second patterns of a second set of patterns specified in a second pattern table were determined to exist in a second portion of the data item based on regular expression matching the one or more second patterns against the second portion of the data item, the generation of the one or more first pattern results including;

in response to determining that a first pattern of the first set of patterns exists in a first portion of the data item, selecting the second pattern table from a plurality of pattern tables, and

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

generating one or more second pattern results, the one or more second pattern results indicating that one or more third patterns of a third 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; and

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

13. The one or more non-transitory storage media of claim 12, 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.

14. The one or more non-transitory storage media of claim 12, 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.

15. The one or more non-transitory storage media of claim 12, 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.

16. The one or more non-transitory storage media of claim 12, 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.

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

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

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

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

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

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

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

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

23. 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 specified in a first pattern table were determined to exist in a first portion of the data item based on regular expression matching the one or more first patterns against the first portion of the data item, and further indicating that one or more second patterns of a second set of patterns specified in a second pattern table were determined to exist in a second portion of the data item based on regular expression matching the one or more second patterns against the second portion of the data item, the generation of the one or more first pattern results including;

in response to determining that a first pattern of the first set of patterns exists in a first portion of the data item, selecting the second pattern table from a plurality of pattern tables, and

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

generate one or more second pattern results, the one or more second pattern results indicating that one or more third patterns of a third 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; and

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

24. The apparatus of claim 23, 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.

25. The apparatus of claim 23, 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.

26. The apparatus of claim 23, 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.

27. The apparatus of claim 23, 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.