Interactive Analysis of Attack Graphs Using Relational Queries

• US 20080046393A1
• Filed: 07/31/2007
• Published: 02/21/2008
• Est. Priority Date: 08/01/2006
• Status: Active Grant

• Current Assignee: National Institute of Standards and Technology (Government of the United States of America)
• Original Assignee: George Mason Research Foundation Inc.
• Inventors: Singhal, Anoop, Wang, Lingyu, Jajodia, Sushil
• Granted Patent: US 8,566,269 B2
• Time in Patent Office: Days
• US Class Current: 706/50
• CPC Class Codes: H04L 41/0853 by actively collecting configuration information or by backing up configuration information
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/149 for prediction of maintenance
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

Abstract

An attack graph analysis tool that includes a network configuration information input module, a domain knowledge input module, a network configuration information storage module, a domain knowledge storage module, and a result generation module. The network configuration information input module inputs network configuration information. The domain knowledge input module inputs domain knowledge for the network. The network configuration information storage module stores network configuration information in a network database table. The domain knowledge storage module stores the domain knowledge in an exploit database table. The result generation module generates a result using the network database table and exploit database table. The result may be generated in response to a query to a database management system that has access to the network database table and exploit database table. The network may be reconfigured to decrease the likelihood of future attacks using the attack information learned from the result.

Claims

1. ) A system for analyzing attack graphs, comprising modules residing on at least one tangible computer readable medium containing a set of computer readable instructions that are executable by one or more processors, the modules comprising:

a) a network configuration information input module configured to input network configuration information that describes the configuration of a network, al least part of the network configuration information describing at least part of the physical structure of the network, the network configuration information including at least one of the following;

i) host information;

ii) host configuration information;

iii) application information;

iv) network service information;

or

v) operating system information;

or

vi) a combination of the above;

b) a domain knowledge input module configured to input domain knowledge for the network, the domain knowledge including knowledge about at least one exploit;

c) a network configuration information storage module configured to store the network configuration information in at least one network database table;

d) a domain knowledge storage module configured to store the domain knowledge in at least one exploit database table, the domain knowledge including exploit information; and

e) a result generation module configured to generate a result using the network database table and exploit database table in response to a query to a database management system, the result including at least one of the following;

i) a metric;

ii) an attack path;

iii) part of an attack path;

iv) a collection of paths;

v) an exploit;

vi) a condition-exploit pair;

vii) an exploit-condition pair;

or

viii) a table that describes an attack graph;

or

ix) a combination of the above; and

wherein the network is reconfigured using attack information learned from the result.

2. ) A system for analyzing attack graphs, comprising:

a) a network configuration information input module configured to input network configuration information that describes the configuration of a network;

b) a domain knowledge input module configured to input domain knowledge for the network, the domain knowledge including knowledge about at least one exploit;

c) a network configuration information storage module configured to store the network configuration information in a network database table;

d) a domain knowledge storage module configured to store the domain knowledge in an exploit database table; and

e) a result generation module configured to generate a result describing at least part of a network attack using the network database table and exploit database table.

3. ) The system according to claim 2, wherein the network configuration information input module, the domain knowledge input module, the network configuration information storage module, the domain knowledge storage module, and the result generation module reside on at least one tangible computer readable medium containing a set of computer readable instructions that are executable by one or more processors.

4. ) The system according to claim 2, wherein the network configuration information includes host information and host configuration information.

5. ) The system according to claim 2, wherein at least part of the network configuration information describes at least part of the physical structure of the network.

6. ) The system according to claim 2, wherein the network configuration information includes application information.

7. ) The system according to claim 2, wherein the network configuration information includes network service information.

8. ) The system according to claim 2, wherein the network configuration information includes operating system information.

9. ) The system according to claim 2, wherein the domain knowledge includes exploit information.

10. ) The system according to claim 2, wherein the network database table includes more than one network database table.

11. ) The system according to claim 2, wherein the exploit table includes more than one exploit database table.

12. ) The system according to claim 2, wherein the result generation module is further configured to submit a query to a database management system.

13. ) The system according to claim 2, wherein the result is a metric.

14. ) The system according to claim 2, wherein the result is an attack path.

15. ) The system according to claim 2, wherein the result is part of an attack path.

16. ) The system according to claim 2, wherein the result is a collection of paths.

17. ) The system according to claim 2, wherein the result is an exploit.

18. ) The system according to claim 2, wherein the result is a condition-exploit pair.

19. ) The system according to claim 2, wherein the result is an exploit-condition pair.

20. ) The system according to claim 2, wherein the result is a table that describes an attack graph.

21. ) The system according to claim 2, wherein the network is reconfigured in response to the result.

22. ) The system according to claim 2, wherein at least part of the network database table and at least part of the exploit database table are stored in a common table.

23. ) A tangible computer readable medium containing a set of computer readable instructions that when executed by one or more processors, causes the one or more processors to perform a method for analyzing a network, the method comprising the steps of:

a) inputting network configuration information that describes the configuration of a network;

b) inputting domain knowledge for the network, the domain knowledge including knowledge about at least one exploit;

c) storing the network configuration information in a network database table;

d) storing the domain knowledge in an exploit database table,

e) generating a result describing at least part of a network attack using the network database table and exploit database table.