System and method for maintaining a dynamic dictionary

• US 10,546,008 B2
• Filed: 10/21/2016
• Issued: 01/28/2020
• Est. Priority Date: 10/22/2015
• Status: Active Grant

• Current Assignee: Cognyte Technologies Israel Ltd. (Cognyte Software Ltd.)
• Original Assignee: Verint Systems Limited (Verint Systems Incorporated)
• Inventors: Yishay, Yitshak
• Primary Examiner(s): Cheema, Azam M
• Application Number:
  US15/299,729
• Publication Number:
  US 20170116331A1
• Time in Patent Office: 1,194 Days
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

An apparatus and techniques for constructing and utilizing a “dynamic dictionary” that is not a compiled dictionary, and therefore does not need to be recompiled in order to be updated. The dynamic dictionary includes respective data structures that represent (i) a management automaton that includes a plurality of management nodes, and (ii) a runtime automaton that is derived from the management automaton and includes a plurality of runtime nodes. The runtime automaton may be used to search input data, such as communication traffic over a network, for keywords of interest, while the management automaton manages the addition of keywords to the dynamic dictionary. Typically, at least two (e.g., exactly two) such dynamic dictionaries are used in combination with a static dictionary.

Claims

1. A method, comprising:

storing, in computer memory, data structures that collectively represent at least one dynamic dictionary of keywords that does not need to be recompiled in order to be updated, the data structures including (i) a management automaton that includes a plurality of management nodes, and (ii) a runtime automaton that is derived from the management automaton and includes a plurality of runtime nodes;

searching input data, using the runtime automaton; and

upon receiving a new keyword that is not included in the at least one dynamic dictionary;

updating the management automaton to include the new keyword, wherein updating the management automaton to include the new keyword comprises adding one or more new management nodes to the management automaton, each of the new management nodes corresponding to at least a portion of the new keyword,

for at least one of the new management nodes;

ascertaining that the portion of the new keyword corresponded to by the new management node differs by an appendage of exactly one symbol from a sequence of symbols corresponded to by another one of the management nodes;

in response thereto, identifying the another one of the management nodes as a parent node of the new management node; and

in response thereto, storing, in the parent node, a child pointer to the new management node, the child pointer corresponding to the appended symbol, and

based on the update to the management automaton, updating the runtime automaton to include the new keyword.

2. The method according to claim 1, wherein storing the data structures comprises storing data structures that collectively represent at least two dynamic dictionaries, each of the dynamic dictionaries including a management automaton and a runtime automaton.

3. The method according to claim 1, wherein the management automaton uses an alphabet of nibbles, such that each of the management nodes corresponds to a sequence of nibbles that is a portion of at least one of the keywords.

4. The method according to claim 3, wherein at least one of the management nodes corresponds to a sequence of nibbles consisting of an odd number of nibbles.

5. The method according to claim 1, further comprising:

identifying another one of the management nodes as a fallback node of a management node selected from the new management nodes, in that the other one of the management nodes corresponds to a sequence of symbols that is a largest suffix of the portion of the new keyword corresponded to by the selected management node; and

in response thereto, storing, in the selected management node, a fallback pointer to the fallback node.

6. The method according to claim 5, further comprising:

identifying another one of the management nodes as a fallback node of the parent node, in that the other one of the management nodes corresponds to a sequence of symbols that is a largest suffix of the sequence of symbols corresponded to by the parent node; and

ascertaining that the fallback node of the parent node stores a child pointer, corresponding to the appended symbol, that points to a child node of the fallback node of the parent node,

wherein identifying the fallback node of the selected management node comprises identifying the fallback node of the selected management node by following the child pointer stored in the fallback node of the parent node.

7. The method according to claim 5, further comprising:

ascertaining that the fallback node stores a child pointer to a child node of the fallback node, indicating that a sequence of symbols corresponded to by the child node of the fallback node differs by an appendage of exactly one symbol from the sequence of symbols corresponded to by the fallback node; and

in response thereto, storing, in the selected management node, a shortcut pointer to the child node of the fallback node.

8. The method according to claim 1, further comprising storing, in one or more other management nodes, respective fallback pointers that point to a management node selected from the new management nodes, indicating that the selected management node corresponds to a largest suffix of respective sequences of symbols corresponded to by the other management nodes.

9. The method according to claim 8, wherein storing the respective fallback pointers in the other management nodes comprises:

identifying one or more friend nodes of the parent node pointed to by respective friend pointers stored in the parent node, the friend pointers indicating the parent node corresponds to a largest suffix of respective sequences of symbols corresponded to by the friend nodes of the parent node;

ascertaining that one or more of the friend nodes store respective child pointers corresponding to the appended symbol;

identifying the other management nodes, by following the respective child pointers from the one or more of the friend nodes; and

storing, in the other management nodes, the respective fallback pointers to the selected management node.

10. The method according to claim 1, further comprising storing, in one or more other management nodes, respective shortcut pointers that point to the new management node, indicating that the parent node corresponds to a largest suffix of respective sequences corresponded to by the other management nodes.

11. The method according to claim 10, wherein storing the respective shortcut pointers in the other management nodes comprises:

identifying one or more friend nodes of the parent node pointed to by respective friend pointers stored in the parent node, the friend pointers indicating that the parent node corresponds to a largest suffix of respective sequences of symbols corresponded to by the friend nodes of the parent node; and

storing, in each of one or more of the friend nodes, a shortcut pointer, corresponding to the appended symbol, that points to the new management node.

12. The method according to claim 1, wherein updating the runtime automaton to include the new keyword comprises updating the runtime automaton to include the new keyword while using the runtime automaton to search the input data.

13. The method according to claim 1, wherein updating the runtime automaton to include the new keyword comprises adding one or more new runtime nodes to the runtime automaton, each of the new runtime nodes corresponding to at least a portion of the new keyword.

14. The method according to claim 13, wherein adding the one or more new runtime nodes to the runtime automaton comprises:

adding a regular runtime node, corresponding to the keyword, to the runtime automaton; and

adding a reporting runtime node, corresponding to the keyword, to the runtime automaton, the reporting runtime node storing a plurality of pointers that point to the regular runtime node.

15. The method according to claim 14, wherein the reporting runtime node further stores an index for the new keyword.

16. A method, comprising:

storing, in computer memory, data structures that collectively represent at least one dynamic dictionary of keywords that does not need to be recompiled in order to be updated, the data structures including (i) a management automaton that includes a plurality of management nodes, and (ii) a runtime automaton that is derived from the management automaton and includes a plurality of runtime nodes;

searching input data, using the runtime automaton;

upon receiving a new keyword that is not included in the at least one dynamic dictionary;

updating the management automaton to include the new keyword, and

based on the update to the management automaton, updating the runtime automaton to include the new keyword, wherein updating the runtime automaton to include the new keyword comprises adding one or more new runtime nodes to the runtime automaton, each of the new runtime nodes corresponding to at least a portion of

the new keyword, wherein the runtime automaton uses an alphabet of symbols; and

for each of the new runtime nodes;

storing, in the new runtime node, a plurality of pointers to one or more of the new runtime nodes, the pointers including a respective pointer corresponding to each one of the symbols in the alphabet; and

subsequently, storing, in one or more of the new runtime nodes, respective pointers to the new runtime node.

17. A method, comprising:

storing, in computer memory, data structures that collectively represent at least one dynamic dictionary of keywords that does not need to be recompiled in order to be updated, the data structures including (i) a management automaton that includes a plurality of management nodes, and (ii) a runtime automaton that is derived from the management automaton and includes a plurality of runtime nodes;

searching input data, using the runtime automaton; and

upon receiving a new keyword that is not included in the at least one dynamic dictionary;

updating the management automaton to include the new keyword, and

based on the update to the management automaton, updating the runtime automaton to include the new keyword, wherein updating the runtime automaton to include the new keyword comprises adding one or more new runtime nodes to the runtime automaton, each of the new runtime nodes corresponding to at least a portion of the new keyword, wherein adding the one or more new runtime nodes to the runtime automaton comprises;

adding a regular runtime node, corresponding to the keyword, to the runtime automaton; and

adding a reporting runtime node, corresponding to the keyword, to the runtime automaton, the reporting runtime node storing a plurality of pointers that point to the regular runtime node,

wherein searching the input data comprises;

traversing the runtime automaton, until the reporting runtime node is reached; and

upon reaching the reporting runtime node, ascertaining that the new keyword is present in the input data, by ascertaining that at least two of the pointers stored in the reporting runtime node are equivalent to one another and do not point to a root node of the runtime automaton.