Methods, systems, and devices using reprogrammable hardware for high-speed processing of streaming data to find a redefinable pattern and respond thereto

• US 20030221013A1
• Filed: 05/21/2002
• Published: 11/27/2003
• Est. Priority Date: 05/21/2002
• Status: Active Grant

• Current Assignee: Washington University In St Louis
• Original Assignee: Washington University In St Louis
• Inventors: Pachos, Michael, Lockwood, John, Loui, Ronald, Moscola, James
• Granted Patent: US 7,093,023 B2
• Time in Patent Office: Days
• US Class Current: 709/231
• CPC Class Codes: H04L 41/08 Configuration management of networks or network elements address allocation H04L61/50
• CPC Class Codes: H04L 41/0803 Configuration setting

Abstract

A reprogrammable packet processing system for processing a stream of data is disclosed herein. A reprogrammable data processor is implemented with a programmable logic device (PLD), such as a field programmable gate array (FPGA), that is programmed to determine whether a stream of data applied thereto includes a string that matches a redefinable data pattern. If a matching string is found, the data processor performs a specified action in response thereto. The data processor is reprogrammable to search packets for the presence of different data patterns and/or perform different actions when a matching string is detected. A reconfiguration device receives input from a user specifying the data pattern and action, processes the input to generate the configuration information necessary to reprogram the PLD, and transmits the configuration information to the packet processor for reprogramming thereof

Claims

1. A reprogrammable system for processing a stream of data, said system comprising:

a reprogrammable data processor for receiving a stream of data and processing said received data stream through a programmable logic device (PLD) programmed to (1) determine whether said data stream includes a string that matches a redefinable data pattern, and (2) perform a redefinable action in the event said data stream is found to include a string that matches said data pattern; and

a reconfiguration device in communication with said data processor that is operable to reprogram said PLD with at least one of the group consisting of a redefined data pattern and a redefined action.

2. The system of claim 1 wherein said redefinable action is a data modification operation, and wherein said PLD is programmed to perform said data modification operation by modifying at least a portion of a data stream that is found to include a matching string.

3. The system of claim 2 wherein said data modification operation is a string replacement operation, said string replacement operation including a redefinable replacement string, and wherein said PLD is programmed to perform said string replacement operation by replacing a matching string in said data stream with said replacement string.

4. The system of claim 3 wherein said PLD is programmed to perform said string replacement operation by replacing a longest matching string in said data stream with said replacement string.

5. The system of claim 3 wherein said data processor is in communication with a computer network from which said data stream is received, said data stream comprising a stream of data packets transmitted over said computer network.

6. The system of claim 5 wherein each packet in said packet stream includes a payload portion, and wherein said PLD is programmed to determine whether the payload portion of any of said received packets includes a matching string.

7. The system of claim 6 wherein said reconfiguration device is in communication with said data processor via said computer network and is further operable to reprogram said PLD over said computer network.

8. The system of claim 6 wherein said reconfiguration device comprises:

a reconfiguration input operable to receive a data pattern and a replacement string;

a compiler operable to (1) generate a module from said received data pattern and said received replacement string that is operable upon being programmed into said PLD to determine whether the payload of a packet applied thereto includes a string that matches said received data pattern and, if a matching string is found therein, replace said matching string with said received replacement string, and (2) create configuration information from said generated module that is operable to program said PLD with said generated module; and

a transmitter operable to communicate said configuration information over said network to said data processor for programming said PLD with said module.

9. The system of claim 8 wherein said data processor further comprises a programming device in communication with said PLD and said computer network that is operable to receive said configuration information from said transmitter and program said PLD according to said received configuration information.

10. The system of claim 9 wherein said reconfiguration input is further configured to receive said data pattern in a regular expression format.

11. The system of claim 10 wherein said compiler is further configured to generate said module in part by processing said received data pattern through a lexical analyzer generator to thereby create a logical representation of a pattern matching state machine operable to determine whether data applied thereto includes a string that matches said received data pattern, said module including said pattern matching state machine representation.

12. The system of claim 11 wherein said lexical analyzer generator is JLex.

13. The system of claim 11 wherein said module includes a plurality of said pattern matching state machines representations for parallel processing of said packet stream.

14. The system of claim 11 wherein said compiler is further configured to generate said module in part by processing said received replacement string to thereby create a logical representation of a string replacement machine therefrom that is operable to replace a matching string found in data with said received replacement string, said module including said string replacement machine representation.

15. The system of claim 14 wherein said compiler is further configured generate said module in part by coordinating said pattern matching state machine representation and said string replacement machine representation with a logical representation of a controller, said controller representation being operable to (1) communicate with said pattern matching state machine representation to determine a start position and an end position of a matching string, and (2) process said determined start and end positions to control said string replacement machine representation, said module including said controller representation.

16. The system of claim 4 wherein said PLD is a field programmable gate array (FPGA).

17. The system of claim 4 wherein said data pattern encompasses at least a word in a first language, and wherein said replacement string comprises a translation of said at least one word in said first language into a second language.

18. The system of claim 4 wherein said data pattern encompasses at least in part a profanity, and wherein said replacement string comprises a data string not including said profanity.

19. The system of claim 4 wherein said data pattern encompasses an encrypted data string, and wherein said replacement string comprises a data string corresponding to a decryption of said encrypted data string.

20. The system of claim 4 wherein said data pattern encompasses a data string, and wherein said replacement string comprises an encryption of said data string.

21. The system of claim 4 wherein said data pattern encompasses at least a portion of a computer virus, and wherein said replacement string comprises a data string that is not a computer virus.

22. The system of claim 3 wherein said string replacement operation is a back substitution operation.

23. The system of claim 3 wherein said data processor is in communication with a computer network from which said data stream is received, said data stream comprising a stream of data packets transmitted over said computer network, wherein said redefinable action is a packet drop operation, and wherein said PLD is programmed to perform said packet drop operation by dropping a packet that is found to include a matching string.

24. The system of claim 1 wherein said redefinable action is a notification operation, wherein said PLD is programmed to perform said notification operation by sending a notification signal to an interested device, said notification signal being operative to identify the existence of a matching string in said data stream.

25. The system of claim 24 wherein said data processor is in communication with a computer network from which said data stream is received, said data stream comprising a stream of data packets transmitted over said computer network, wherein said notification signal is a notification packet addressed for transmission to an interested party, wherein said notification packet includes a copy of the packet that includes said matching string.

26. The system of claim 1 wherein said redefinable action is an awk operation, and wherein said PLD is programmed to perform said awk operation when a matching string is found in said data stream.

27. The system of claim 1 wherein said data pattern encompasses at least a portion of at least one of the group consisting of an image file, an audio file, a video file, an audio/video file, software, virus infected file, text file, and electronic publishing files.

28. The system of claim 1 wherein said data pattern encompasses at least a portion of a copyright-protected work.

29. The system of claim 1 wherein said data pattern encompasses at least a portion of a trade secret.

30. The system of claim 1 wherein said data pattern encompasses a data string indicative of a criminal conspiracy.

31. A method of processing a stream of data, said method comprising:

programming a programmable logic device (PLD) to (1) determine whether a stream of data applied thereto includes a string that matches a data pattern, and (2) perform a responsive action if said data stream is found to include a matching string;

processing a stream of data through said programmed PLD to (1) determine whether said data stream includes a string that matches said data pattern, and (2) perform said responsive action if said data stream is found to include a matching string; and

repeating said programming step with at least one of the group consisting of a different data pattern and a different action.

32. The method of claim 31 wherein said programming step includes:

receiving a data pattern;

receiving an action command, said action command specifying an action to be performed if said data stream is found to include a matching string;

generating configuration information from said received data pattern and said received action command that defines a module that is operable upon being programmed into said PLD to (1) determine whether a stream of data applied thereto includes a string that matches said received data pattern, and (2) perform said responsive action if said data stream is found to include a matching string; and

programming said PLD with said configuration information.

33. The method of claim 32 wherein said action command receiving step includes receiving an action command that specifies a data modification operation, said data modification operation identifying how a data stream is to be modified if that data stream is found to include a matching string.

34. The method of claim 33 wherein said action command receiving step includes receiving an action command that specifies a string replacement operation, said string replacement operation identifying a replacement string to be inserted into a data stream in place of a matching string.

35. The method of claim 32 wherein said action command receiving step includes receiving an action command wherein said action command specifies a notification operation, said notification operation specifying a notification signal to be transmitted when a matching string is found in said data stream.

36. The method of claim 32 wherein said data stream is a stream of packets transmitted over a computer network, each data packet including a payload portion, and wherein said processing step includes:

receiving a stream of data packets;

identifying the payload portion of each received data packet; and

processing the payload portion of each received data packet through said programmed PLD to (1) determine whether the payload portion of any received data packet includes a string that matches said data pattern, and (2) perform said responsive action if said a payload portion is found to include a matching string.

37. The method of claim 36 wherein said step of programming said PLD with said configuration information includes transmitting said configuration information over said computer network to said PLD.

38. A device for generating configuration information operable to program a programmable logic device (PLD) with a data processing module operable to receive and process a stream of data to determine whether said data stream includes a data pattern and, if so, perform a responsive action, said device comprising:

an input operable to receive a data pattern and an action command from a user, said action command specifying an action to be performed if said data stream is found to include a string that matches said data pattern;

a compiler operable to generate configuration information from said received data pattern and said received modification command, said configuration information defining a data processing module operable upon being programmed into said PLD to (1) determine whether a stream of data applied thereto includes a string that matches said received data pattern, and (2) perform said action if said data stream is found to include a matching string, said configuration information being operable to program said PLD with said data processing module.

39. The device of claim 38 wherein said action command is a modification command, said modification command specifying a modification operation to be performed upon said data stream if said data stream is found to include a matching string, and wherein said compiler is also operable to generate said configuration information from said modification command such that said module defined thereby is also operable upon being programmed into said PLD to perform said modification operation upon said data stream if said data stream is found to include a matching string.

40. The device of claim 39 wherein said compiler is also operable to process said received data pattern through a lexical analyzer generator to thereby generate a logical representation of a pattern matching state machine that is operable to determine whether a stream of data applied thereto includes a string that matches said received data pattern, said pattern matching state machine representation in part defining said module.

41. The device of claim 40 wherein said modification operation specified by said modification command is a string replacement operation, wherein said modification command includes a replacement string, and wherein said compiler is also operable to process said received modification command to thereby generate a logical representation of a string replacement machine that is operable to replace a matching string in said data stream with said replacement string, said string replacement machine representation in part defining said module.

42. The device of claim 41 wherein said compiler is also operable to process said received data pattern through said lexical analyzer generator such that said pattern matching state machine representation comprises at least one deterministic finite automaton (DFA).

43. The device of claim 42 wherein said data stream is a packet stream comprising a plurality of data packets transmitted over a computer network, said device further comprising a transmitter interfacing said compiler with said computer network, said transmitter being operable to receive said configuration information from said compiler and transmit said configuration information over said network to a programming device in communication with said PLD, said programming device being operable to program said PLD with said module defined thereby.

44. The device of claim 43 wherein each packet in said packet stream includes a payload portion, and wherein said compiler is further operable to generate said configuration information such that said module defined thereby is also operable upon being programmed into said PLD to determine whether any of said payloads of said packets comprising said packet stream include a matching string.

45. The device of claim 44 wherein said input is also operable to receive said data pattern in a regular expression format.

46. The device of claim 45 wherein said input is also operable to receive a plurality of data patterns and a plurality of said modification commands from a user, each modification command having a corresponding data pattern, and wherein said compiler is also operable to generate said configuration information such that said data processing module defined thereby is also operable to, for each data pattern and corresponding modification command, perform said match determination and said string replacement operation.

47. A method of programming a programmable logic device (PLD) to process a stream of data, said method comprising:

receiving a data pattern;

receiving a modification command corresponding to said data pattern, said action command specifying an action to be performed if said stream of data is found to include a string that matches said data pattern;

generating configuration information from said received data pattern and said received modification command that is operable to program said PLD with a data processing module that is operable upon being programmed into said PLD to (1) determine whether a data stream applied thereto includes a string that matches said data pattern, and (2) perform said action specified by said action command if said data stream is found to include a matching string; and

communicating said configuration information to a programming device in communication with said PLD, said programming device being operable to program said PLD with said configuration information.

48. The method of claim 47 wherein said action command is a modification command that specifies a modification operation to performed upon a data stream that includes a matching string, and wherein said generating step includes generating said configuration information such that said module defined thereby is also operable to perform said modification operation upon said data stream if said data stream is found to include a matching string.

49. The method of claim 48 wherein said modification operation is a string replacement operation, wherein said modification command includes a replacement string, and wherein said generating step includes generating said configuration information such that said module defined thereby is also operable to perform said string replacement operation by replacing a matching string in said data stream with said replacement string.

50. The method of claim 49 wherein said generating step includes processing said data pattern through a lexical analyzer generator to create a logical representation of a pattern matching state machine therefrom, said pattern matching state machine in part defining said module and being operable to determine whether a stream of data applied thereto includes a string that matches said data pattern.

51. The method of claim 50 wherein said generating step includes creating a logical representation of a string replacement machine from said received modification command, said string replacement machine in part defining said module and being operable to replace a matching string in said data stream with said replacement string.

52. The method of claim 51 wherein said data stream is a packet stream comprising a plurality of data packets transmitted over a computer network, and wherein said communicating step includes communicating said configuration information over said network to said programming device.

53. The method of claim 52 wherein each of said data packets includes a payload portion, and wherein said generating step includes generating said configuration information such that said module defined thereby is also operable upon being programmed into said PLD to determine whether any of said payload portions of said packets comprising said packet stream include a matching string.

54. The method of claim 53 wherein said data pattern receiving step includes receiving said data pattern in a regular expression format.

55. The method of claim 54 wherein said data pattern receiving step includes receiving a plurality of data patterns, wherein said modification command receiving step includes receiving a plurality of said modification commands, each modification command corresponding to a data pattern, and wherein said generating step includes generating said configuration information such that said module defined thereby is also operable to, for each data pattern and corresponding modification command, (1) perform said match determination, and (2) perform said string replacement operation

56. A device for processing a stream of data, said device comprising:

a programmable logic device (PLD) programmed to receive a stream of data and process said data stream through a plurality of redefinable logic structures in series, each logic structure being tuned with a corresponding redefinable data pattern and being operable to determine whether a string is present in said processed data stream that matches that logic structure'"'"'s corresponding data pattern.

57. The device of claim 56 wherein each logic structure is also tuned with a corresponding redefinable action and is further operable to perform that logic structure'"'"'s corresponding redefinable action if said processed data stream is found to include a string that matches that logic structure'"'"'s corresponding data pattern.

58. The device of claim 57 wherein each redefinable action is a string replacement operation, each string replacement operation including a replacement string, and wherein each logic structure is further operable to replace a string found in said processed data stream that matches that logic structure'"'"'s corresponding data pattern with that logic structure'"'"'s corresponding replacement string.

59. The device of claim 58 wherein said PLD is a field programmable gate array (FPGA) in communication with a computer network, said data stream comprising a stream of data packets transmitted over said computer network.

60. A device of processing a stream of data, said device comprising:

a programmable logic device (PLD) programmed to receive a stream of data and process said received data stream through a plurality of pattern matching state machines in parallel, each pattern matching state machine of said plurality of pattern matching state machines being tuned with a data pattern and being operable to determine whether said data stream includes a string that matches the data pattern with which it is tuned.

61. The device of claim 60 wherein each pattern matching state machine of said plurality of pattern matching state machines is tuned with the same data pattern.

62. The device of claim 61 wherein said data stream comprises a stream of data bytes, wherein said PLD is also programmed with a controller operable to provide said data stream to said plurality of parallel pattern matching state machines such that each pattern matching state machine receives said data stream starting at a different byte.

63. The device of claim 62 wherein said controller is also operable to communicate with said plurality of parallel pattern matching state machines to identify a longest string in said data stream that matches said data pattern.

64. The device of claim 60 each pattern matching state machine of said plurality of pattern matching state machines is tuned with a different data pattern.

65. A reprogrammable system for processing a stream of data, said system comprising:

a reprogrammable data processor for receiving a stream of data and processing said received data stream through a programmable logic device (PLD) programmed with at least one deterministic finite automaton (DFA) to determine whether said data stream includes a string that matches a redefinable data pattern; and

a reconfiguration device in communication with said data processor that is operable to reprogram said PLD with a different DFA to determine whether a data stream includes a string that matches a different data pattern.

66. A network processor for processing a stream of data packets transmitted over a computer network, said network processor comprising:

a protocol wrapper operative to receive data from said computer network and process said data to generate a stream of data packets therefrom, said packet stream comprising a stream of words, each word including a plurality of bytes;

a matching path operative to receive said packet stream from said protocol wrapper and detect whether any of said packets comprising said packet stream include a string that matches a data pattern;

a controller in communication with said matching path that is operative to determine a starting byte position and an ending byte position of each matching string detected by said matching path;

a data path in communication with said controller that is operative to receive said packet stream from said protocol wrapper and process each starting byte position and ending byte position for each matching string determined by said controller to (1) output each byte of said packet stream that does not correspond to a matching string, and (2) replace the bytes of said packet stream that correspond to a matching string with a replacement string;

wherein said matching path, said controller, and said data path are implemented on a programmable logic device (PLD).

67. The network processor of claim 66 wherein said protocol wrapper is also implemented on said PLD.