SYSTEMS AND METHODS FOR KEYWORD SPOTTING USING ALTERNATING SEARCH ALGORITHMS

• US 20180075133A1
• Filed: 09/25/2017
• Published: 03/15/2018
• Est. Priority Date: 01/30/2014
• Status: Active Grant

• Current Assignee: Cognyte Technologies Israel Ltd. (Cognyte Software Ltd.)
• Original Assignee: Verint Systems Limited (Verint Systems Incorporated)
• Inventors: Yishay, Yitshak
• Granted Patent: US 10,719,540 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

Systems and methods for spotting keywords in data packets are provided. In particular, input data is received to be searched for occurrences of a set of patterns, the input data being divided into multiple segments. Then the input data and the patterns are assigned to first and second pattern matching algorithms, the first pattern matching algorithm is configured to search only within each of the segments, and the second pattern matching algorithm is configured to search across boundaries between adjacent segments. Then the input data is searched using the first and second pattern matching algorithms.

Claims

1. A method, comprising:

receiving, by a network interface card of a system, a sequence of packets exchanged in a communication network;

storing the received sequence of packets in a memory of the system; and

searching, by a processor of the system, the received sequence of packets for occurrences of a set of patterns, wherein the processor searches with a first pattern matching algorithm only within packet boundaries of each of the packets in the sequence of packets, and wherein the processor searches with a second pattern matching algorithm across boundaries between adjacent packets in the received sequence of packets.

2. The method according to claim 1, wherein the first and second pattern matching algorithms comprise respective first and second searching states, wherein the first searching state is larger than the second searching state.

3. The method according to claim 2, wherein searching the received sequence of packets comprises initializing the first searching state when starting to search in a given packet for a pattern in the set of patterns, and clearing the first searching state when concluding searching of the given packet.

4. The method according to claim 3, wherein clearing the first searching state comprises freeing, by the processor, memory space allocated for the first searching state in the memory.

5. The method according to claim 2, wherein searching the received sequence of packets comprises:

storing, by the processor, the second searching state in the memory when concluding searching a given packet, wherein the second pattern matching algorithm searches a last predetermined number of characters in the given packet, and

recovering, by the processor, the stored second searching state from the memory when starting a search of a following packet, wherein the second pattern matching algorithm searches an initial predetermined number of characters in the following packet.

6. The method according to claim 5, wherein searching the received sequence of packets further comprises:

clearing, by the processor, the second searching state by de-allocating memory space allocated for the second searching state in the memory when concluding searching of the initial predetermined number of characters in the following packet.

7. The method according to claim 5, wherein a size of the last predetermined number of characters in the given packet and the initial predetermined number of characters in the following packet is based on a number of characters in a longest pattern among the set of patterns.

8. The method according to claim 1, wherein one or more of the patterns comprise at least one wildcard character, and wherein each of the first and second pattern matching algorithms skips matching the wildcard character by suspending the respective first or second searching state until matching a non-wildcard character.

9. The method according to claim 8, wherein searching the received sequence of packets comprises dividing a pattern containing the wildcard character into multiple sub-patterns that do not contain any wildcard character, searching the received sequence of packets for the sub-patterns to obtain sub-pattern results, and combining the sub-pattern results.

10. The method according to claim 1, wherein searching the received sequence of packets comprises assigning a first set of patterns to the first and second pattern matching algorithms, and, upon receiving an instruction to switch to a second set of patterns, which is different from the first set, assigning the second set of patterns to the second pattern matching algorithm while analyzing a given packet using the first pattern matching algorithm, prior to restarting the second pattern matching algorithm.

14. The apparatus according to claim 3, wherein the processor is configured to clear the first searching state by freeing memory space allocated for the first searching state in the memory.

11. An apparatus, comprising:

a network interface card configured to receive a sequence of packets exchanged in a communication network;

a memory configured to store the received sequence in packets; and

a processor which is configured to search the received sequence of packets for occurrences of a set of patterns with first and second pattern matching algorithms, wherein the first pattern matching algorithm is configured to search only within packet boundaries of each of the packets in the sequence of packets, and the second pattern matching algorithm is configured to search across boundaries between adjacent packets.

12. The apparatus according to claim 11, wherein the first and second pattern matching algorithms comprise respective first and second searching states, wherein the first searching state is larger than the second searching state.

13. The apparatus according to claim 12, wherein the processor is configured to initialize the first searching state when starting a search in a given packet for a pattern in the set of patterns, and to clear the first searching state when concluding the search of the given packet.

15. The apparatus according to claim 12, wherein the processor is configured to store the second searching state in the memory when concluding analyzing a given packet, wherein the second pattern matching algorithm searches a last predetermined number of characters in the given packet,

wherein the processor is configured to recover the stored second searching state from the memory when starting a search of a following packet, wherein the second pattern matching algorithm searches an initial predetermined number of characters in the following packet.

16. The apparatus according to claim 15, wherein the processor is configured to clear the second searching state by de-allocating memory space allocated for the second searching state in the memory when a search of the initial predetermined number of characters in the following packet is concluded.

17. The apparatus according to claim 15, wherein a size of the last predetermined number of characters in the given packet and the initial predetermined number of characters in the following packet is based on a number of characters in a longest pattern among the set of patterns.

18. The apparatus according to claim 11, wherein one or more of the patterns comprise at least one wildcard character, and wherein the processor is configured to skip matching the wildcard character by suspending the respective first or second searching state until matching a non-wildcard character.

19. The apparatus according to claim 18, wherein the processor is configured to search the received sequence of packets by dividing a pattern containing the wildcard character into multiple sub-patterns that do not contain any wildcard character, searching the input data for the sub-patterns to obtain sub-pattern results, and combining the sub-pattern results.

20. The apparatus according to claim 11, wherein the processor is configured to assign a first set of patterns to the first and second pattern matching algorithms, and, upon receiving an instruction to switch to a second set of patterns, which is different from the first set, to assign the second set of patterns to the second pattern matching algorithm while analyzing a given packet using the first pattern matching algorithm, prior to restarting the second pattern matching algorithm.