Systems and methods for accelerated pattern matching

• US 10,212,132 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): Wade, Shaqueal D
• Application Number:
  US15/224,396
• Publication Number:
  US 20180034778A1
• Time in Patent Office: 935 Days
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• 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 performed by a security service comprising a plurality of microservices, the method comprising:

searching, by a deep packet inspection (DPI) microservice of the plurality of microservices, a data item using a first pattern matching table;

determining that one or more first patterns of the first pattern matching table exist in a first portion of the data item;

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

searching a second portion of the data item for patterns using the second pattern matching table, wherein the second portion of the data item does not include the first portion of the data item;

determining that one or more second patterns of the second pattern matching table exist in the second portion of the data item; and

performing an action relative to the data item based at least in part on the determination that the one or more first patterns exist in the first portion of the data item and the one or more second patterns exist in the second portion of the data item.

2. The method of claim 1, wherein the first pattern matching is a regular expression table, and wherein determining that the one or more first patterns of the first pattern matching table exist in the first portion of the data item includes regular expression matching.

3. The method of claim 1, wherein the second portion of the data item is not compared against the one or more first patterns of the first pattern matching table.

4. The method of claim 1, wherein the second pattern matching table is selected by a callback function associated with the first pattern matching table.

5. The method of claim 1, wherein the first pattern matching table comprises a plurality of entries, each entry of the plurality of entries specifying a current state value, an input value, a next state value, a match indicator, and a callback function identifier;

wherein the second pattern matching table is selected by a callback function identified by a callback function identifier in the first pattern matching table.

6. The method of claim 1, wherein determining that the one or more first patterns of the first pattern matching table exist in the data item comprises:

wherein the first pattern matching table comprises a plurality of entries, each entry of the plurality of entries specifying a current state value, an input value, a next state value, a match indicator, and a callback function identifier;

receiving a next input value from the data item;

based on a current state value and the next input value, identifying an entry in the first pattern matching table, the entry including a particular callback function identifier; and

wherein the second pattern matching table is selected by a callback function corresponding to the particular callback function identifier.

7. The method of claim 1, wherein the second pattern matching table contains less than all of the patterns contained in the first pattern matching table.

8. The method of claim 1, wherein each of the one or more first patterns is different from each of the one or more second patterns.

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

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

11. The method of claim 1, wherein the data item is received by the DPI microservice.

12. The method of claim 1, wherein the data item is received by the DPI microservice, and wherein the DPI microservice comprises a software container.

13. The method of claim 1, wherein at least one pattern of the one or more first patterns is expressed using a regular expression.

14. The method of claim 1, wherein at least one pattern of the one or more first patterns is expressed using a regular expression;

and

wherein the first pattern matching table comprises one or more entries, each entry of the one or more entries representing a state of processing at least one regular expression.

15. The method of claim 1, wherein the first pattern matching table is a master pattern matching table comprising entries corresponding states for all input patterns.

16. The method of claim 1, further comprising:

generating, based on a plurality of input patterns, a master pattern matching table comprising states for the plurality of input patterns;

generating, based on the plurality of input patterns, an alternative pattern matching table comprising states for a selected subset of the plurality of input patterns; and

wherein the first pattern matching table is the alternative pattern matching table.

17. The method of claim 1, further comprising:

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

determining that one or more third patterns of the third pattern matching table exist in a third portion of the data item, wherein the third portion of the data item is not compared against either the one or more first patterns or the one or more second patterns.

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

19. One or more non-transitory computer-readable storage media storing instructions which, when executed by one or more hardware processors implementing a security service comprising a plurality of microservices, cause performance of:

searching, by a deep packet inspection (DPI) microservice of the plurality of microservices, a data item using a first pattern matching table;

determining that one or more first patterns of the first pattern matching table exist in a first portion of the data item;

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

searching a second portion of the data item for patterns using the second pattern matching table, wherein the second portion of the data item does not include the first portion of the data item;

determining that one or more second patterns of the second pattern matching table exist in the second portion of the data item; and

performing an action relative to the data item based at least in part on the determination that the one or more first patterns exist in the first portion of the data item and the one or more second patterns exist in the second portion of the data item.

20. The one or more non-transitory storage media of claim 19, wherein the first pattern matching is a regular expression table, and wherein determining that the one or more first patterns of the first pattern matching table exist in the first portion of the data item includes regular expression matching.

21. The one or more non-transitory storage media of claim 19, wherein the second portion of the data item is not compared against the one or more first patterns of the first pattern matching table.

22. The one or more non-transitory storage media of claim 19, wherein the second pattern matching table is selected by a callback function associated with the first pattern matching table.

23. The one or more non-transitory storage media of claim 19, wherein the first pattern matching table comprises a plurality of entries, each entry of the plurality of entries specifying a current state value, an input value, a next state value, a match indicator, and a callback function identifier;

wherein the second pattern matching table is selected by a callback function identified by a callback function identifier in the first pattern matching table.

24. The one or more non-transitory storage media of claim 19, wherein determining that the one or more first patterns of the first pattern matching table exist in the data item comprises:

wherein the first pattern matching table comprises a plurality of entries, each entry of the plurality of entries specifying a current state value, an input value, a next state value, a match indicator, and a callback function identifier;

receiving a next input value from the data item;

based on a current state value and the next input value, identifying an entry in the first pattern matching table, the entry including a particular callback function identifier; and

wherein the second pattern matching table is selected by a callback function corresponding to the particular callback function identifier.

25. An apparatus, comprising:

one or more hardware processors implementing a security service comprising a plurality of microservices;

memory coupled to the one or more hardware processors, the memory storing instructions which, when executed by the one or more hardware processors, causes a deep packet inspection (DPI) microservice of the plurality of microservices to;

search a data item using a first pattern matching table;

determine that one or more first patterns of the first pattern matching table exist in a first portion of the data item;

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

search a second portion of the data item for patterns using the second pattern matching table, wherein the second portion of the data item does not include the first portion of the data item

determine that one or more second patterns of the second pattern matching table exist in the second portion of the data item; and

perform an action relative to the data item based at least in part on the determination that the one or more first patterns exist in the first portion of the data item and the one or more second patterns exist in the second portion of the data item.

26. The apparatus of claim 25, wherein the first pattern matching is a regular expression table, and wherein determining that the one or more first patterns of the first pattern matching table exist in the first portion of the data item includes regular expression matching.

27. The apparatus of claim 25, wherein the second portion of the data item is not compared against the one or more first patterns of the first pattern matching table.

28. The apparatus of claim 25, wherein the second pattern matching table is selected by a callback function associated with the first pattern matching table.

29. The apparatus of claim 25, wherein the first pattern matching table comprises a plurality of entries, each entry of the plurality of entries specifying a current state value, an input value, a next state value, a match indicator, and a callback function identifier;

wherein the second pattern matching table is selected by a callback function identified by a callback function identifier in the first pattern matching table.

30. The apparatus of claim 25, wherein determining that the one or more first patterns of the first pattern matching table exist in the data item comprises:

wherein the first pattern matching table comprises a plurality of entries, each entry of the plurality of entries specifying a current state value, an input value, a next state value, a match indicator, and a callback function identifier;

receiving a next input value from the data item;

based on a current state value and the next input value, identifying an entry in the first pattern matching table, the entry including a particular callback function identifier; and

wherein the second pattern matching table is selected by a callback function corresponding to the particular callback function identifier.