Method and apparatus for generating highly predictive blacklists

• US 9,083,712 B2
• Filed: 04/04/2008
• Issued: 07/14/2015
• Est. Priority Date: 04/04/2007
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Porras, Phillip Andrew, Zhang, Jian
• Primary Examiner(s): Eskandarnia, Arvin
• Assistant Examiner(s): DESAI, MARGISHI V
• Application Number:
  US12/098,345
• Publication Number:
  US 20090064332A1
• Time in Patent Office: 2,657 Days
• Field of Search: 726/25, 726/22, 726/23, 709/225
• US Class Current: 1/1
• CPC Class Codes: H04L 2463/146 Tracing the source of attacks
• CPC Class Codes: H04L 63/0236 Filtering by address, protocol, port number or service, e.g. IP-address or URL
• CPC Class Codes: H04L 63/101 Access control lists [ACL]
• CPC Class Codes: H04L 63/105 Multiple levels of security
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04W 12/10 Integrity

Abstract

In one embodiment, the present invention is a method and apparatus for generating highly predictive blacklists. One embodiment of a method for generating a blacklist of network addresses for a user of a network includes collecting security log data from users of the network, the security log data identifying observed attacks by attack sources, assigning the attack sources to the blacklist based on a combination of the relevance each attack source to the user and the maliciousness of the attack source, and outputting the blacklist.

Claims

1. A method for generating a blacklist of network addresses, the method comprising:

analyzing attack history data of a plurality of nodes of a computer network;

computing a relevance ranking for a current attack source with respect to a first node of the computer network, the relevance ranking indicative of an attack history of the current attack source with respect to the first network node;

propagating the relevance ranking to a second node of the computer network by applying a weight to the relevance ranking computed for the first network node, the weight indicative of a strength of an attack correlation relationship between the first network node and the second network node, the strength of the attack correlation relationship based on whether the attack history data includes data indicative of a previous attack on the first network node and the second network node, respectively, by a common attack source different than the current attack source;

based at least partly on the propagated relevance ranking, adjusting a score of the current attack source on a list of attack sources; and

generating a blacklist for the second network node by selecting one or more attack sources from the list of attack sources based on respective scores of the one or more selected attack sources.

2. The method of claim 1, further comprising:

pre-processing the attack history data to remove noise and erroneous data.

3. The method of claim 2, wherein the erroneous data comprises one or more of:

data produced from an attack source from invalid Internet Protocol address space, data produced from an attack source from unassigned Internet Protocol address space, data produced from a network address from an Internet measurement service, data produced from a web crawler, data produced from a software update source, and data produced from a timed-out network service.

4. The method of claim 1, comprising:

for each of a plurality of attack sources;

computing a severity score indicative of a maliciousness of the attack source;

combining the relevance ranking and the severity score to produce a final score for the attack sources; and

including an attack source in the blacklist when the attack source is among a predefined number of attack sources who are most highly ranked, based on the final score.

5. The method of claim 1, wherein computing the relevance ranking comprises:

constructing a correlation graph that models an attack correlation relationship between the nodes of the network; and

distributing a relevance of each of the attack sources in accordance with the correlation graph.

6. The method of claim 5, wherein the correlation graph comprises an edge between each pair of nodes, the edge being weighted in accordance with a correlation between the nodes in the pair of nodes.

7. The method of claim 6, wherein the correlation is based on a number of the attack sources that has attacked both of the nodes.

8. The method of claim 6, comprising, for a given attack source:

assigning an initial relevance value at each node, the initial relevance value being based on an attack history of the given attack source relative to a node; and

assigning a propagated relevance value for the given attack source at each neighbor of each node to which an initial relevance value has been assigned, the propagated relevance value comprising an initial relevance value multiplied by a weight of an edge connecting a node to which the initial relevance value is assigned to a neighbor to which a propagated relevance value is assigned.

9. The method of claim 8, wherein the assigning the propagated relevance value continues outward from a node to which the initial relevance value is assigned until relevance values for the given attack source at all nodes in the correlation graph have reached stable states.

10. The method of claim 4, wherein computing the severity score comprises, for a given attack source:

calculating a malware port score for the given attack source, the malware port score indicative of a malware behavior pattern of the given attack source;

calculating a set of unique target Internet Protocol addresses connected to the given attack source; and

defining the severity score for the given attack source as the sum of the malware port score plus a logarithm of the set of unique target internet Protocol addresses connected to the given attack source.

11. The method of claim 10, further comprising:

calculating a ratio of national Internet Protocol addresses to international Internet Protocol addresses targeted by the given attack source; and

increasing the severity score by a logarithm of the ratio.

12. The method of claim 11, further comprising:

dampening the logarithm by a factor having a value between zero and one.

13. The method of claim 4, wherein combining the relevance ranking and the severity score comprises:

compiling a list of candidate attack sources;

ranking the candidate attack sources in accordance with respective relevance rankings for the candidate attack sources; and

adjusting the ranking of the candidate attack sources by respective severity scores for the candidate attack sources to generate the final score.

14. The method of claim 13, comprising:

sorting final scores of the candidate attack sources; and

selecting a predefined number of the candidate attack sources having lowest final scores.

34. The method of claim 1, wherein the relevance ranking is higher when an attack source has attacked another one of the nodes with whom the node shares at least one common attack source than when the attack source has not attacked another one of the nodes with whom the node shares at least one common attack source.

15. A blacklist generation module embodied in one or more non-transitory computer readable storage media and configured to cause a computing device to:

analyze first attack history data of a first network node and second attack history data of a second network node;

identify, in the first attack history data, data indicative of an attack by a current attack source; and

in response to determining that the second attack history data does not comprise data indicative of an attack by the current attack source;

(i) determine a relevance ranking for the current attack source with respect to the first network node, the relevance ranking indicative of an attack history of the current attack source with respect to the first network node;

(ii) propagate the relevance ranking to the second network node by applying a weight to the relevance ranking, the weight indicative of a strength of an attack correlation relationship between the first network node and the second network node, the strength of the attack correlation relationship based on whether the attack history data includes data indicative of a previous attack on the first network node and the second network node, respectively, by a common attack source different than the current attack source;

(iii) based at least partly on the relevance ranking, adjust a score of the current attack source on a list of attack sources; and

(iv) generate a blacklist for the second network node by selecting one or more attack sources from the list of attack sources based on respective scores of the selected one or more attack sources on the list of attack sources.

16. The blacklist generation module of claim 15, further comprising:

pre-processing the attack history data to remove noise and erroneous data.

17. The blacklist generation module of claim 16, wherein the erroneous data comprises one or more of:

data produced from an attack source from invalid Internet Protocol address space, data produced from an attack source from unassigned Internet Protocol address space, data produced from a network address from an Internet measurement service, data produced from a web crawler, data produced from a software update source, and data produced from a timed-out network service.

18. The blacklist generation module of claim 15, wherein the assigning comprises, for each of the attack sources:

computing a severity score for the attack source, the severity score indicating the maliciousness of the attack source;

combining the relevance ranking and the severity score to produce a final score for the attack source; and

including the attack source in the blacklist when the attack source is among a predefined number of attack sources who are most highly ranked, based on the final score.

19. The blacklist generation module of claim 15, wherein computing the relevance ranking comprises:

constructing a correlation graph that models an attack correlation relationship between the nodes of the network; and

distributing a relevance of each of the attack sources in accordance with the correlation graph.

20. The blacklist generation module of claim 19, wherein the correlation graph comprises a node for each of the nodes and an edge between each pair of nodes, the edge being weighted in accordance with a correlation between nodes in the pair of nodes.

21. The blacklist generation module of claim 20, wherein the correlation is based on a number of the attack sources that has attacked both of the nodes.

22. The blacklist generation module of claim 20, wherein the distributing comprises, for a given attack source:

assigning an initial relevance value at each node, the initial relevance value being based on an attack history of the given attack source relative to each node; and

assigning a propagated relevance value for the given attack source at each neighbor of each node to which an initial relevance value has been assigned, the propagated relevance value comprising an initial relevance value multiplied by a weight of an edge connecting a node to which the initial relevance value is assigned to a neighbor to which a propagated relevance value is assigned.

23. The blacklist generation module of claim 22, wherein the assigning the propagated relevance value continues outward from a node to which the initial relevance value is assigned until relevance values for the given attack source at all nodes in the correlation graph have reached stable states.

24. The blacklist generation module of claim 18, wherein computing the severity score comprises, for a given attack source:

calculating a malware port score for the given attack source, the malware port score indicative of a malware behavior pattern of the given attack source;

calculating a set of unique target Internet Protocol addresses connected to the given attack source; and

defining the severity score for the given attack source as the sum of the malware port score plus a logarithm of the set of unique target Internet Protocol addresses connected to the given attack source.

25. The blacklist generation module of claim 24, further comprising:

calculating a ratio of national Internet Protocol addresses to international Internet Protocol addresses targeted by the given attack source;

increasing the severity score by a logarithm of the ratio.

26. The blacklist generation module of claim 25, further comprising:

dampening the logarithm by a factor having a value between zero and one.

27. The blacklist generation module of claim 18, wherein combining the relevance ranking and the severity score comprises:

compiling a list of candidate attack sources;

ranking the candidate attack sources in accordance with respective relevance rankings for the candidate attack sources; and

adjusting the ranking of the candidate attack sources by respective severity scores for the candidate attack sources to generate the final score.

28. The blacklist generation module of claim 27, wherein the including comprises:

sorting final scores of the candidate attack sources; and

selecting a predefined number of the candidate attack sources having lowest final scores.

29. A system for generating a blacklist of network addresses, the system comprising a computing device configured to:

analyze first attack history data of a first network node and second attack history data of a second network node;

identify, in the first attack history data, data indicative of an attack by a current attack source; and

in response to determining that the second attack history data does not comprise data indicative of an attack by the current attack source;

(i) determine a relevance ranking for the current attack source with respect to the first network node, the relevance ranking indicative of an attack history of the current attack source with respect to the first network node;

(ii) propagate the relevance ranking to the second network node by applying a weight to the relevance ranking, the weight indicative of a strength of an attack correlation relationship between the first network node and the second network node, the strength of the attack correlation relationship based on whether the attack history data includes data indicative of a previous attack on the first network node and the second network node, respectively, by a common attack source different than the current attack source;

(iii) based at least partly on the relevance ranking, adjust a score of the current attack source on a list of attack sources; and

(iv) generate a blacklist for the second network node by selecting one or more attack sources from the list of attack sources based on respective scores of the one or more selected attack sources on the list of attack sources.

30. The system of claim 29, comprising a plurality of sensors distributed throughout the network.

31. The system of claim 29, wherein the computing device comprises:

a severity assessment module to compute a severity score for each of the attack sources, the severity score indicating the maliciousness of the attack sources; and

a blacklist generation module to combine the relevance ranking and the severity score to produce a final score for each of the attack sources.

32. The system of claim 31, wherein the blacklist generation module is further configured to include an attack source in the blacklist when the attack source is among a predefined number of attack sources who are most highly ranked, based on the final score.

33. The system of claim 31, wherein the computing device is configured to pre-process the attack history data to remove noise and erroneous data.