Scenario Graphs and
Attack Graphs Project
Webpage

Contents

Introduction

When evaluating the security of a system one needs to do more than detection of vulnerabilities. Systems usually contain multiple types of nodes along with complex connectivity matrices among them. In order to properly identify the threats the system faces one can construct a scenario graph. Scenario graphs represent the ways in which an adversary can exploit vulnerabilities to break into a system. Each path in an scenario graph is a series of an attacker’s steps called actions, which lead to an undesirable state. The edges in the graph are the actions, and the nodes of the graph are the system’s states. An example of an undesirable state is a state where the intruder has obtained administrative access to a critical node in the network. Scenario graphs used in the context of network security are called "attack graphs".

Construction by hand of scenario graphs is tedious, error-prone, and impractical for graphs larger than a hundred nodes. Our model-checking based toolkit automatically generates scenario graphs and enables different analyses that system administrators can perform on these graphs. These analyses can answer questions such as "Given a set of measures, what is a minimum subset needed to make this system safe?". We strive to extend this toolkit to a more general analysis tool that would be used in forensic analysis and intrusion detection.

People

We supply two versions of the toolkit.

Click here for installation instructions for both tools. Please contact Oren with any problem or question.

Contents

Introduction

When evaluating the security of a system one needs to do more than detection of vulnerabilities. Systems usually contain multiple types of nodes along with complex connectivity matrices among them. In order to properly identify the threats the system faces one can construct a scenario graph. Scenario graphs represent the ways in which an adversary can exploit vulnerabilities to break into a system. Each path in an scenario graph is a series of an attacker’s steps called actions, which lead to an undesirable state. The edges in the graph are the actions, and the nodes of the graph are the system’s states. An example of an undesirable state is a state where the intruder has obtained administrative access to a critical node in the network. Scenario graphs used in the context of network security are called "attack graphs".

Construction by hand of scenario graphs is tedious, error-prone, and impractical for graphs larger than a hundred nodes. Our model-checking based toolkit automatically generates scenario graphs and enables different analyses that system administrators can perform on these graphs. These analyses can answer questions such as "Given a set of measures, what is a minimum subset needed to make this system safe?". We strive to extend this toolkit to a more general analysis tool that would be used in forensic analysis and intrusion detection.

People

- Oren Dobzinski
- Yanjing Li
- Oleg Sheyner (alumnus)
- Jeannette M. Wing

- O. Sheyner “Scenario Graphs and Attack Graphs,” Carnegie Mellon University, April 2004. PhD Thesis.
- J.M.
Wing
“Scenario
Graphs Applied to Security,”
*Proceedings of Workshop on Verification of Infinite State Systems with Applications to Security*, Timisoara, Romania, March 2005. Summary paper. - O.
Sheyner
and J.M.
Wing, “Tools
for
Generating and Analyzing Attack Graphs,”
*Proceedings of Workshop on Formal Methods for Components and Objects*, 2004, pp. 344-371. - S. Jha,
O.
Sheyner, and
J.M. Wing, “Two
Formal Analyses
of Attack Graphs,”
*Proceedings of the 15th IEEE Computer Security Foundations Workshop*, Nova Scotia, Canada, June 2002, pp. 49-63. - O.
Sheyner,
J. Haines,
S. Jha, R. Lippmann,
and J.M. Wing, “Automated
Generation and
Analysis of Attack Graphs,”
*Proceedings of the IEEE Symposium on Security and Privacy*, Oakland, CA, May 2002.

We supply two versions of the toolkit.

- The attack graph toolkit, is the toolkit developed by Oleg Sheyner for his PhD thesis. It is specific for security applications.
- The scenario graph toolkit, is the generalized version developed by Oren Dobzinski.

Click here for installation instructions for both tools. Please contact Oren with any problem or question.