System and method for maintaining a dynamic dictionary

Patent metadata

Field	Value
Publication number	US-2017116331-A1
Application number	US-201615299729-A
Country	US
Kind code	A1
Filing date	Oct 21, 2016
Priority date	Oct 22, 2015
Publication date	Apr 27, 2017
Grant date	—

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.

First claim

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; and searching input data, using the runtime automaton.

2 . (canceled)

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

4 . (canceled)

5 . (canceled)

6 . (canceled)

7 . (canceled)

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

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

10 . The method according to claim 1 , further comprising, upon receiving a new keyword that is not included in the 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.

11 . The method according to claim 10 , 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.

12 . The method according to claim 11 , further comprising, 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 other 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.

13 . (canceled)

14 . (canceled)

15 . The method according to claim 12 , 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.

16 . The method according to claim 15 , 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.

17 . (canceled)

18 . (canceled)

19 . (canceled)

20 . The method according to claim 15 , 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.

21 . The method according to claim 12 , 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.

22 . The method according to claim 21 , 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.

23 . The method according to claim 12 , 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.

24 . The method according to claim 23 , 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.

25 . The method according to claim 10 , 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.

26 . The method according to claim 10 , 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.

27 . (canceled)

28 . The method according to claim 26 , wherein the runtime automaton uses an alphabet of symbols, and wherein the method further comprises, for each of the new runtime nodes:
storing, in the new runtime node, a plurality of pointers to one or more of the 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 runtime nodes, respective pointers to the new runtime node.

29 . The method according to claim 26 , wherein adding the one or more new runtime nodes to the runtime automato

Assignees

• Verint Systems Ltd

Inventors

• Yishay Yitshak

Classifications

• H04L63/0263

  Rule management · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06F16/353 Primary

  into predefined classes · CPC title

• G06F16/36

  Creation of semantic tools, e.g. ontology or thesauri · CPC title

• H04L63/1416

  Event detection, e.g. attack signature detection · CPC title