System and method for keyword searching using both static and dynamic dictionaries
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.
1. A method of analyzing communication traffic in a network to determine if keywords occur in the communication traffic, comprising:
during a recompilation of a static dictionary, wherein the static dictionary is represented by a data structure stored in computer memory:
receiving one or more keywords during the recompilation;
in response to beginning the recompilation of the static dictionary, transitioning a first dynamic dictionary to an active state from an inactive state and a second dynamic dictionary to a standby state from the active state, wherein each dynamic dictionary is represented by a respective data structure stored in the computer memory;
adding the one or more keywords to both the first dynamic dictionary and the second dynamic dictionary; and
searching input data using both the first dynamic dictionary and the static dictionary and not using the second dynamic dictionary while the first dynamic dictionary is in the active state and the second dynamic dictionary is in the standby state; and
following the recompilation:
in response to ending the recompilation of the static dictionary, transitioning the second dynamic dictionary to the active state from the standby state and the first dynamic dictionary to the inactive state from the active state; and
searching input data using both the second dynamic dictionary and the static dictionary and not using the first dynamic dictionary while the first dynamic dictionary is in the inactive state and the second dynamic dictionary is in the active state.
2. The method according to claim 1 , further comprising storing the respective data structures that represent the first and second dynamic dictionaries at least partly within a cache memory of a processor.
3. The method according to claim 2 , wherein storing the respective data structures at least partly within the cache memory of the processor comprises:
during the recompilation of the static dictionary, storing the first dynamic dictionary at least partly within the cache memory while storing the second dynamic dictionary in computer memory; and
following the recompilation, storing the second dynamic dictionary at least partly within the cache memory while storing the first dynamic dictionary in computer memory.
4. The method according to claim 1 , further comprising, following the recompilation, rebuilding the first dynamic dictionary, such that the first dynamic dictionary includes fewer keywords than that the first dynamic dictionary previously included.
5. The method according to claim 1 , wherein the recompilation is a first recompilation, and wherein the method further comprises, following the first recompilation, adding the keywords that were received during the first recompilation to the static dictionary, by performing a second recompilation of the static dictionary.
6. The method according to claim 5 , further comprising, during the second recompilation of the static dictionary:
adding any keywords that arrive during the second recompilation to both the first dynamic dictionary and the second dynamic dictionary; and
searching input data using both the second dynamic dictionary and the static dictionary.
7. The method according to claim 1 , further comprising adding the keywords to a keyword collection, wherein recompiling the static dictionary comprises recompiling the static dictionary such that the static dictionary includes all keywords contained in the keyword collection at a start of the recompilation.
8. The method according to claim 1 , further comprising adding to the second dynamic dictionary, but not to the first dynamic dictionary, any keywords that arrive following the recompilation and prior to a subsequent recompilation.
9. The method according to claim 1 , further comprising repeatedly adding at least one respective newly-arrived keyword to the static dictionary, by repeatedly recompiling the static dictionary.
10. Apparatus, comprising:
a network interface; and
one or more processors, configured to analyze communication traffic in a network to determine if keywords occur in the communication traffic and to:
during the recompilation of a static dictionary, wherein the static dictionary, which is represented by a data structure stored in computer memory:
receive one or more keywords during the recompilation;
in response to beginning the recompilation of the static dictionary, transition a first dynamic dictionary to an active state from an inactive state and a second dynamic dictionary to a standby state from the active state, wherein each dynamic dictionary is represented by a respective data structure stored in the computer memory;
add the one or more keywords to both the first dynamic dictionary and the second dynamic dictionary; and
search input data received via the network interface using both the first dynamic dictionary and the static dictionary and not using the second dynamic dictionary while the first dynamic dictionary is in the active state and the second dynamic dictionary is in the standby state; and
following the recompilation:
in response to ending the recompilation of the static dictionary, transition the second dynamic dictionary to the active state from the standby state and the first dynamic dictionary to the inactive state from the active state; and
search input data received via the network interface using both the second dynamic dictionary and the static dictionary and not using the first dynamic dictionary while the first dynamic dictionary is in the inactive state and the second dynamic dictionary is in the active state.
11. The apparatus according to claim 10 , wherein the processors are further configured to store the respective data structures that represent the first and second dynamic dictionaries at least partly within a cache memory of one of the processors.
12. The apparatus according to claim 11 , wherein the processors are configured to:
during the recompilation of the static dictionary, store the first dynamic dictionary at least partly within the cache memory while storing the second dynamic dictionary in computer memory; and
following the recompilation, store the second dynamic dictionary at least partly within the cache memory while storing the first dynamic dictionary in computer memory.
13. The apparatus according to claim 10 , wherein the processors are further configured to, following the recompilation, rebuild the first dynamic dictionary, such that the first dynamic dictionary includes fewer keywords than the first dynamic dictionary previously included.
14. The apparatus according to claim 10 , wherein the recompilation is a first recompilation, and wherein the processors are further configured to, following the first recompilation, add the keywords that arrived during the first recompilation to the static dictionary, by performing a second recompilation of the static dictionary.
15. The apparatus according to claim 14 , wherein the processors are further configured to, during the second recompilation of the static dictionary:
add any keywords that arrive during the second recompilation to the first dynamic dictionary and to the second dynamic dictionary; and
search input data received via the network interface using both the second dynamic dictionary and the static dictionary.
16. The apparatus according to claim 10 , wherein the processors are configured to add the keywords to a keyword collection, and to recompile the static dictionary such that the static dictionary includes all keywords contained in the keyword collection at a start of the recompilation.
17. The apparatus according to claim 10 , wherein the processors are further configured to add to the second dynamic dictionary, but not to the first dynamic dictionary, any keywords that arrive following the recompilation and prior to a subsequent recompilation.
18. The apparatus according to claim 10 , wherein the processors are configured to repeatedly add at least one respective newly-arrived keyword to the static dictionary, by repeatedly recompiling the static dictionary.
19. A computer software product comprising a tangible non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by one or more processors, cause the processors to analyze communication traffic in a network to determine if keywords occur in the communication traffic and to:
during a recompilation of a static dictionary which is represented by a data structure stored in computer memory:
receive one or more keywords during the recompilation;
in response to beginning the recompilation of the static dictionary, transition a first dynamic dictionary to an active state from an inactive state and a second dynamic dictionary to a standby state from the active state, wherein each dynamic dictionary is represented by a respective data structure stored in the computer memory;
add the one or more keywords to both the first dynamic dictionary and the second dynamic dictionary; and
search input data using both the first dynamic dictionary and the static dictionary and not using the second dynamic dictionary while the first dynamic dictionary is in the active state and the second dynamic dictionary is in the standby state; and
following the recompilation:
in response to ending the recompilation of the static dictionary, transition the second dynamic dictionary to the active state from the standby state and the first dynamic dictionary to the inactive state from the active state; and
search input data from the network using both the second dynamic dictionary and the static dictionary and not using the first dynamic dictionary while the first dynamic dictionary is in the inactive state and the second dynamic dictionary is in the active state.
20. The computer software product according to claim 19 , wherein the first dynamic dictionary comprises a management automaton and a runtime automaton.