Mitigating network attacks using automatic signature generation

• US 20060107321A1
• Filed: 11/18/2004
• Published: 05/18/2006
• Est. Priority Date: 11/18/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Tzadikario, Rephael
• Granted Patent: US 7,540,025 B2
• Time in Patent Office: Days
• US Class Current: 726/22
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

A computer-implemented method for mitigating attacks of malicious traffic in a computer network includes receiving a set of attack sequences, including first traffic sequences suspected of containing the malicious traffic, analyzing the attack sequences so as to automatically extract a regular expression that matches at least a portion of the attack sequences in the set, and comparing second traffic sequences to the regular expression in order to identify the second traffic sequences that contain the malicious traffic.

Claims

1. A computer-implemented method for mitigating attacks of malicious traffic in a computer network, comprising:

receiving a set of attack sequences, comprising first traffic sequences suspected of containing the malicious traffic;

analyzing the attack sequences so as to automatically extract a regular expression that matches at least a portion of the attack sequences in the set; and

comparing second traffic sequences to the regular expression in order to identify the second traffic sequences that contain the malicious traffic.

2. The method according to claim 1, wherein receiving the set of attack sequences comprises:

analyzing communications traffic in the computer network to establishing a baseline behavior pattern;

detecting a deviation from the baseline behavior pattern that is indicative of an attack; and

collecting the attack sequences in response to the deviation.

3. The method according to claim 2, wherein detecting the deviation comprises identifying a source address of the malicious traffic, and wherein collecting the attack sequences comprises recording the malicious traffic received from the source address.

4. The method according to claim 3, wherein recording the malicious traffic comprises establishing a connection with the source address, thus soliciting the source address to generate additional malicious traffic, and collecting the additional malicious traffic while blocking further transmission of the malicious traffic through the network.

5. The method according to claim 1, wherein receiving the set of attack sequences comprises establishing a connection with a source computer that is transmitting the set of attack sequences, thus soliciting the source computer to generate additional malicious traffic, and collecting the additional malicious traffic while blocking further transmission of the malicious traffic through the network.

6. The method according to claim 1, and comprising receiving a set of innocent sequences, having a high likelihood of not containing any malicious traffic, wherein analyzing the attack sequences comprises determining the regular expression so that the regular expression does not match any of the innocent sequences.

7. The method according to claim 1, wherein receiving the set of attack sequences comprises receiving data packets transmitted over the network, and wherein analyzing the attack sequences comprises extracting and processing message payloads from the data packets.

8. The method according to claim 1, wherein analyzing the attack sequences comprises:

finding a representative sequence in the set of attack sequences; and

comparing the attack sequences to the representative sequence in order to generate the regular expression.

9. The method according to claim 8, wherein finding the representative sequence comprises:

choosing a subset of the set of attack sequences;

determining a cumulative alignment score for each attack sequence in the subset by aligning each attack sequence in the subset relative to other attack sequences in the subset; and

selecting the attack sequence in the subset having a maximal cumulative alignment score.

10. The method according to claim 8, wherein comparing the attack sequences to the representative sequence comprises aligning and finding a respective alignment score of each attack sequence relative to the representative sequence.

11. The method according to claim 10, wherein comparing the attack sequences comprises determining a true positive similarity threshold, and discarding the attack sequences having respective alignment scores below the true positive similarity threshold.

12. The method according to claim 11, wherein determining the true positive similarity threshold comprises:

defining an expected fraction of false positive traffic sequences in the set of attack sequences;

ranking the attack sequences in order of the respective alignment scores;

selecting a position in the order responsively to the expected fraction; and

picking the alignment score of the attack sequence that is ranked in the selected position in the order to be the true positive similarity threshold.

13. The method according to claim 8, wherein comparing the attack sequences to the representative sequence comprises generating the regular expression by extending the representative sequence to match the attack sequences.

14. The method according to claim 13, and comprising receiving a set of innocent sequences, having a high likelihood of not containing any malicious traffic, wherein generating the regular expression comprises extending the representative sequence so as to match a maximal number of the attack sequence while not matching the innocent sequences.

15. The method according to claim 1, wherein analyzing the attack sequences comprises:

generating a first regular expression that matches a number of the attack sequences;

removing from the set of attack sequences all the attack sequences that match the first regular expression, thereby generating a reduced set of the attack sequences; and

generating at least a second regular expression using the reduced set.

16. The method according to claim 1, and comprising:

receiving an additional set of attack sequences; and

refining the regular expression using the additional set of attack sequences.

17. The method according to claim 16, wherein refining the regular expression comprises extending the regular expression to match at least a portion of the additional set of attack sequences.

18. The method according to claim 1, and comprising preventing further transmission through the network of the second traffic sequences that are identified, using the regular expression, as containing the malicious traffic.

19. The method according to claim 18, wherein preventing the further transmission comprises identifying a source address of the malicious traffic and blocking further traffic originating from the source address.

20. The method according to claim 1, wherein receiving the attack sequences comprises receiving an indication that an attack has begun, and collecting the attack sequences responsively to the indication, and wherein analyzing the attack sequences comprises generating the regular expression within one minute of receiving the indication.

21. The method according to claim 20, wherein generating the regular expression comprises generating the regular expression within five seconds of receiving the indication.

65. Apparatus according to claim 1, wherein the means for receiving the set of attack sequences comprise:

means for analyzing communications traffic in the computer network to establishing a baseline behavior pattern;

means for detecting a deviation from the baseline behavior pattern that is indicative of an attack; and

means for collecting the attack sequences in response to the deviation.

66. Apparatus according to claim 65, wherein the means for detecting the deviation comprise means for identifying a source address of the malicious traffic, and wherein the means for collecting the attack sequences comprise means for recording the malicious traffic received from the source address.

67. Apparatus according to claim 66, wherein the means for recording the malicious traffic comprise means for establishing a connection with the source address, thus soliciting the source address to generate additional malicious traffic, and means for collecting the additional malicious traffic while blocking further transmission of the malicious traffic through the network.

22. Apparatus for mitigating attacks of malicious traffic in a computer network, comprising:

a guard device, wherein the guard device is adapted to receive a set of attack sequences, comprising first traffic sequences suspected of containing the malicious traffic, to analyze the attack sequences so as to automatically extract a regular expression that matches at least a portion of the attack sequences in the set, and to compare second traffic sequences to the regular expression in order to identify the second traffic sequences that contain the malicious traffic.

23. Apparatus according to claim 22, wherein the guard device comprises an anomaly detector, which is adapted to analyze communications traffic in the computer network, to establish a baseline behavior pattern, to detect a deviation from the baseline behavior pattern that is indicative of an attack, and to collect the attack sequences in response to the deviation.

24. Apparatus according to claim 23, wherein the anomaly detector is arranged to identify a source address of the malicious traffic, and to record the malicious traffic received from the source address.

25. Apparatus according to claim 24, wherein the guard device is adapted to establish a connection with the source address, thus soliciting the source address to generate additional malicious traffic, and to collect the additional malicious traffic while blocking further transmission of the malicious traffic through the network.

26. Apparatus according to claim 22, wherein the guard device is adapted to establish a connection with a source computer that is transmitting the set of attack sequences, thus soliciting the source computer to generate additional malicious traffic, and to collect the additional malicious traffic while blocking further transmission of the malicious traffic through the network.

27. Apparatus according to claim 22, wherein the guard device is adapted to receive a set of innocent sequences, having a high likelihood of not containing any malicious traffic, and comprising a signature generator, which is adapted to determine the regular expression so that the regular expression does not match any of the innocent sequences.

28. Apparatus according to claim 22, wherein the guard device is adapted to receive data packets transmitted over the network, to extract and to process message payloads from the data packets.

29. Apparatus according to claim 22, wherein the guard device comprises a signature generator, which is adapted to find a representative sequence in the set of attack sequences and to compare the attack sequences to the representative sequence in order to generate the regular expression.

30. Apparatus according to claim 29, wherein the signature generator is adapted to find the representative sequence by choosing a subset of the set of attack sequences, determining a cumulative alignment score for each attack sequence in the subset by aligning each attack sequence in the subset relative to other attack sequences in the subset, and selecting the attack sequence in the subset having a maximal cumulative alignment score.

31. Apparatus according to claim 29, wherein the signature generator is adapted to compare the attack sequences to the representative sequence by aligning and finding a respective alignment score of each attack sequence, relative to the representative sequence.

32. Apparatus according to claim 31, wherein the signature generator is arranged to determine a true positive similarity threshold, and to discard the attack sequences having respective alignment scores below the true positive similarity threshold.

33. Apparatus according to claim 32, wherein the signature generator is adapted to receive a definition of an expected fraction of false positive traffic sequences in the set of attack sequences, and to rank the attack sequences in order of the respective alignment scores, select a position in the order responsively to the expected fraction and pick the alignment score of the attack sequence that is ranked in the selected position in the order to be the true positive similarity threshold.

34. Apparatus according to claim 29, wherein the signature generator is adapted to generate the regular expression by extending the representative sequence to match the attack sequences.

35. Apparatus according to claim 34, wherein the signature generator is adapted to receive a set of innocent sequences, having a high likelihood of not containing any malicious traffic, and to extend the representative sequence so as to match a maximal number of the attack sequence while not matching the innocent sequences.

36. Apparatus according to claim 22, wherein the guard device comprises a signature generator, which is adapted to generate a first regular expression that matches a number of the attack sequences, removes from the set of attack sequences all the attack sequences that match the first regular expression, thereby generating a reduced set of the attack sequences, and generates at least a second regular expression using the reduced set.

37. Apparatus according to claim 22, wherein the guard device is adapted to receive an additional set of attack sequences and to refine the regular expression using the additional set of attack sequences.

38. Apparatus according to claim 37, wherein the guard device is adapted to extend the regular expression to match at least a portion of the additional set of attack sequences.

39. Apparatus according to claim 22, wherein the guard device comprises an intrusion prevention system, which is adapted to prevent further transmission through the network of the second traffic sequences that are identified, using the regular expression, as containing the malicious traffic.

40. Apparatus according to claim 39, wherein the guard device is adapted to identify a source address of the malicious traffic, and wherein the intrusion prevention system is adapted to block the further traffic originating from the source address.

41. Apparatus according to claim 22, wherein the guard device is adapted to receive an indication that an attack has begun, to collect the attack sequences responsively to the indication, and to generate the regular expression within one minute of receiving the indication.

42. Apparatus according to claim 41, wherein the guard device is adapted to generate the regular expression within five seconds of receiving the indication.

43. A computer software product for mitigating attacks of malicious traffic in computer networks, the product comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to receive a set of attack sequences, comprising first traffic sequences suspected of containing the malicious traffic, to analyze the attack sequences so as to automatically extract a regular expression that matches at least a portion of the attack sequences in the set, and to compare second traffic sequences to the regular expression in order to identify the second traffic sequences that contain the malicious traffic.

44. The product according to claim 43, wherein the instructions cause the computer to establish a baseline behavior pattern, to detect a deviation from the baseline behavior pattern that is indicative of an attack, and to collect the attack sequences in response to the deviation.

45. The product according to claim 44, wherein the instructions cause the computer to identify a source address of the malicious traffic, and to record the malicious traffic received from the source address.

46. The product according to claim 45, wherein the instructions cause the computer to establish a connection with the source address, thus soliciting the source address to generate additional malicious traffic, and to collect the additional malicious traffic while blocking further transmission of the malicious traffic through the network.

47. The product according to claim 43, wherein the instructions cause the computer to establish a connection with a source computer that is transmitting the set of attack sequences, thus soliciting the source computer to generate additional malicious traffic, and to collect the additional malicious traffic while blocking further transmission of the malicious traffic through the network.

48. The product according to claim 43, wherein the instructions cause the computer to receive a set of innocent sequences, having a high likelihood of not containing any malicious traffic, and to determine the regular expression so that the regular expression does not match any of the innocent sequences.

49. The product according to claim 43, wherein the instructions cause the computer to receive data packets transmitted over the network, to extract and to process message payloads from the data packets.

50. The product according to claim 43, wherein the instructions cause the computer to find a representative sequence in the set of attack sequences and to compare the attack sequences to the representative sequence in order to generate the regular expression.

51. The product according to claim 50, wherein the instructions cause the computer to find a representative sequence by choosing a subset of the set of attack sequences, determining a cumulative alignment score for each attack sequence in the subset by aligning each attack sequence in the subset relative to other attack sequences in the subset, and selecting the attack sequence in the subset having a maximal cumulative alignment score.

52. The product according to claim 50, wherein the instructions cause the computer to compare the attack sequences to the representative sequence by aligning and finding a respective alignment score of each attack sequence, relative to the representative sequence.

53. The product according to claim 52, wherein the instructions cause the computer to determine a true positive similarity threshold, and to discard the attack sequences having respective alignment scores below the true positive similarity threshold.

54. The product according to claim 53, wherein the instructions cause the computer to define an expected fraction of false positive traffic sequences in the set of attack sequences, to rank the attack sequences in order of the respective alignment scores, to select a position in the order responsively to the expected fraction, and to pick the alignment score of the attack sequence that is ranked in the selected position in the order to be the true positive similarity threshold.

55. The product according to claim 50, wherein the instructions cause the computer to generate the regular expression by extending the representative sequence to match the attack sequences.

56. The product according to claim 55, wherein the instructions cause the computer to receive a set of innocent sequences, having a high likelihood of not containing any malicious traffic, and to extend the representative sequence so as to match a maximal number of the attack sequence while not matching the innocent sequences.

57. The product according to claim 43, wherein the instructions cause the computer to generate a first regular expression that matches a number of the attack sequences, to remove from the set of attack sequences all the attack sequences that match the first regular expression, thereby generating a reduced set of the attack sequences, and to generate at least a second regular expression using the reduced set.

58. The product according to claim 43, wherein the instructions cause the computer to receive an additional set of attack sequences and to refine the regular expression using the additional set of attack sequences.

59. The product according to claim 58, wherein the instructions cause the computer to extend the regular expression to match at least a portion of the additional set of attack sequences.

60. The product according to claim 43, wherein the instructions cause the computer to prevent further transmission through the network of the second traffic sequences that are identified, using the regular expression, as containing the malicious traffic.

61. The product according to claim 60, wherein the instructions cause the computer to identify a source address of the malicious traffic and to block the further traffic originating from the source address.

62. The product according to claim 43, wherein the instructions cause the computer to receive an indication that an attack has begun, to collect the attack sequences responsively to the indication, and to generate the regular expression within one minute of receiving the indication.

63. The product according to claim 62, wherein the instructions cause the computer to generate the regular expression within five seconds of receiving the indication.

64. Apparatus for mitigating attacks of malicious traffic in a computer network, comprising:

means for receiving a set of attack sequences, comprising first traffic sequences suspected of containing the malicious traffic;

means for analyzing the attack sequences so as to automatically extract a regular expression that matches at least a portion of the attack sequences in the set; and

means for comparing second traffic sequences to the regular expression in order to identify the second traffic sequences that contain the malicious traffic.

68. Apparatus according to claim 64, wherein the means for receiving the set of attack sequences comprise means for establishing a connection with a source computer that is transmitting the set of attack sequences, thus soliciting the source computer to generate additional malicious traffic, and means for collecting the additional malicious traffic while blocking further transmission of the malicious traffic through the network.

69. Apparatus according to claim 64, and comprising means for receiving a set of innocent sequences, having a high likelihood of not containing any malicious traffic, wherein the means for analyzing the attack sequences comprise means for determining the regular expression so that the regular expression does not match any of the innocent sequences.

70. Apparatus according to claim 64, wherein the means for receiving the set of attack sequences comprise means for receiving data packets transmitted over the network, and wherein the means for analyzing the attack sequences comprise means for extracting and processing message payloads from the data packets.

71. Apparatus according to claim 64, wherein the means for analyzing the attack sequences comprise:

means for finding a representative sequence in the set of attack sequences; and

means for comparing the attack sequences to the representative sequence in order to generate the regular expression.

72. Apparatus according to claim 71, wherein means for finding the representative sequence comprise:

means for choosing a subset of the set of attack sequences;

means for determining a cumulative alignment score for each attack sequence in the subset by aligning each attack sequence in the subset relative to other attack sequences in the subset; and

means for selecting the attack sequence in the subset having a maximal cumulative alignment score.

73. Apparatus according to claim 71, wherein the means for comparing the attack sequences to the representative sequence comprise means for aligning and finding a respective alignment score of each attack sequence relative to the representative sequence.

74. Apparatus according to claim 73, wherein the means for comparing the attack sequences comprise means for determining a true positive similarity threshold, and discarding the attack sequences having respective alignment scores below the true positive similarity threshold.

75. Apparatus according to claim 74, wherein the means for determining the true positive similarity threshold comprise:

means for defining an expected fraction of false positive traffic sequences in the set of attack sequences;

means for ranking the attack sequences in order of the respective alignment scores;

means for selecting a position in the order responsively to the expected fraction; and

means for picking the alignment score of the attack sequence that is ranked in the selected position in the order to be the true positive similarity threshold.

76. Apparatus according to claim 71, wherein the means for comparing the attack sequences to the representative sequence comprise means for generating the regular expression by extending the representative sequence to match the attack sequences.

77. Apparatus according to claim 76, and comprising means for receiving a set of innocent sequences, having a high likelihood of not containing any malicious traffic, wherein the means for generating the regular expression comprise means for extending the representative sequence so as to match a maximal number of the attack sequence while not matching the innocent sequences.

78. Apparatus according to claim 64, wherein the means for analyzing the attack sequences comprise:

means for generating a first regular expression that matches a number of the attack sequences;

means for removing from the set of attack sequences all the attack sequences that match the first regular expression, thereby generating a reduced set of the attack sequences; and

means for generating at least a second regular expression using the reduced set.

79. Apparatus according to claim 64, and comprising:

means for receiving an additional set of attack sequences; and

means for refining the regular expression using the additional set of attack sequences.

80. Apparatus according to claim 79, wherein the means for refining the regular expression comprise means for extending the regular expression to match at least a portion of the additional set of attack sequences.

81. Apparatus according to claim 64, and comprising means for preventing further transmission through the network of the second traffic sequences that are identified, using the regular expression, as containing the malicious traffic.

82. Apparatus according to claim 81, wherein the means for preventing the further transmission comprise means for identifying a source address of the malicious traffic and means for blocking further traffic originating from the source address.

83. Apparatus according to claim 64, wherein the means for receiving the attack sequences comprise means for receiving an indication that an attack has begun, and means for collecting the attack sequences responsively to the indication, and wherein the means for analyzing the attack sequences comprise means for generating the regular expression within one minute of receiving the indication.

84. Apparatus according to claim 83, wherein the means for generating the regular expression comprise means for generating the regular expression within five seconds of receiving the indication.