METHOD AND APPARATUS FOR GENERATING HIGHLY PREDICTIVE BLACKLISTS

• US 20090064332A1
• Filed: 04/04/2008
• Published: 03/05/2009
• Est. Priority Date: 04/04/2007
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Zhang, Jian, Porras, Phillip Andrew
• Granted Patent: US 9,083,712 B2
• Time in Patent Office: Days
• US Class Current: 726/23
• 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 for a user of a network, the method comprising the steps of:

collecting security log data from one or more users of the network, the security log data identifying one or more observed attacks on the one or more users by one or more attack sources;

assigning at least one of the one or more attack sources to the blacklist based on a combination of a relevance of the at least one of the one or more attack sources to the user and a maliciousness of the at least one of the one or more attack sources; and

outputting the blacklist.

2. The method of claim 1, further comprising:

pre-processing the security log 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, wherein the assigning comprises, for each of the one or more attack sources:

computing a relevance ranking for a given attack source, the relevance ranking indicating the relevance of the given attack source to the user;

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

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

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

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

constructing a correlation graph that models an attack correlation relationship between the one or more users of the network; and

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

6. The method of claim 5, wherein the correlation graph comprises a node for each of the one or more users and an edge between each pair of nodes, the edge being weighted in accordance with a correlation between users corresponding to the pair of nodes.

7. The method of claim 6, wherein the correlation is based on a number of the one or more attack sources that has attacked both of the users corresponding to the pair of nodes.

8. The method of claim 6, wherein the distributing comprises, for each attack source:

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 user of 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.

9. The method of claim 8, wherein the assigning of propagated relevance values continues outward from the 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 each attack source:

calculating a malware port score for a 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 to international addresses targeted by the given attack source;

increasing the severity score by a logarithm of the ratio of national to international addresses targeted by the given attack source.

12. The method of claim 11, further comprising:

dampening the logarithm of the ratio of national to international addresses targeted by the given attack source 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 from the one or more attack sources;

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

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

14. The method of claim 13, 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.

15. A computer readable storage medium containing an executable program for generating a blacklist of network addresses for a user of a network, where the program performs the steps of:

collecting security log data from one or more users of the network, the security log data identifying one or more observed attacks on the one or more users by one or more attack sources;

assigning at least one of the one or more attack sources to the blacklist based on a combination of a relevance of the at least one of the one or more attack sources to the user and a maliciousness of the at least one of the one or more attack sources; and

outputting the blacklist.

16. The computer readable storage medium of claim 15, further comprising:

pre-processing the security log data to remove noise and erroneous data.

17. The computer readable storage medium 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 computer readable storage medium of claim 15, wherein the assigning comprises, for each of the one or more attack sources:

computing a relevance ranking for a given attack source, the relevance ranking indicating the relevance of the given attack source to the user;

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

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

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

19. The computer readable storage medium of claim 18, wherein computing the relevance ranking comprises:

constructing a correlation graph that models an attack correlation relationship between the one or more users of the network; and

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

20. The computer readable storage medium of claim 19, wherein the correlation graph comprises a node for each of the one or more users and an edge between each pair of nodes, the edge being weighted in accordance with a correlation between users corresponding to the pair of nodes.

21. The computer readable storage medium of claim 20, wherein the correlation is based on a number of the one or more attack sources that has attacked both of the users corresponding to the pair of nodes.

22. The computer readable storage medium of claim 20, wherein the distributing comprises, for each attack source:

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 user of 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 computer readable storage medium of claim 22, wherein the assigning of propagated relevance values continues outward from the 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 computer readable storage medium of claim 18, wherein computing the severity score comprises, for each attack source:

calculating a malware port score for a 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 computer readable storage medium of claim 24, further comprising:

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

increasing the severity score by a logarithm of the ratio of national to international addresses targeted by the given attack source.

26. The computer readable storage medium of claim 25, further comprising:

dampening the logarithm of the ratio of national to international addresses targeted by the given attack source by a factor having a value between zero and one.

27. The computer readable storage medium of claim 18, wherein combining the relevance ranking and the severity score comprises:

compiling a list of candidate attack sources from the one or more attack sources;

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

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

28. The computer readable storage medium 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 for a user of a network, the system comprising:

means for collecting security log data from one or more users of the network, the security log data identifying one or more observed attacks on the one or more users by one or more attack sources;

means for assigning at least one of the one or more attack sources to the blacklist based on a combination of a relevance of the at least one of the one or more attack sources to the user and a maliciousness of the at least one of the one or more attack sources; and

means for outputting the blacklist.

30. The system of claim 29, wherein the means for collecting comprises a plurality of sensors distributed throughout the network.

31. The system of claim 29, wherein the means for assigning comprises:

a relevance ranking module for computing a relevance ranking for a given attack source, the relevance ranking indicating the relevance of the given attack source to the user;

a severity assessment module for computing a severity score for the given attack source, the severity score indicating the maliciousness of the given attack source; and

a blacklist generation module for combining the relevance ranking and the severity score to produce a final score for the given attack source.

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

33. The system of claim 31, further comprising:

means for pre-processing the security log data to remove noise and erroneous data.