Melany Wright
CSCI 485 – Topics in Network Security
Extented Abstract – Attack Graphs
Nov. 17, 2014

Attack graphs depict way in which an adversary exploits system vulnerabilities to achieve a desired state.  System administrators use attack graphs to determine how vulnerable their systems are and to determine what security measures to deploy to defend their systems.  Each path in an attack graph is a series of exploits that are called actions, which leads to an undesired state.  Attack graphs can serve as a useful tool in several areas of network security, including intrusion detection, defense, and forensic analysis.  They can be used for the following reasons:  to gather information (E.G. What attacks is the system vulnerable to? From an initial configuration, how many different ways can an attacker reach a final state to achieve this goal?), and to make decisions (E.G. Which set of actions should I prevent to ensure the attacker cannot achieve their goal? Which set of security measures should I deploy to ensure the attacker cannot achieve their goal?).  Attack trees are similar to attack graphs in that they are conceptual diagrams showing how an asset, or target, might be attacked.  However their construction is different.  There are several different modeling software available for attack tree generation, however, there is no automated tools for the development of attack graphs.  

An attack model is a general formalization suitable for modeling a variety of situations.  The system under attack can be virtually anything (computer network, electrical grid).  The attacker is an abstract representation of a group of agents who seek to move the system to a state that is inimical to the system’s interests.  The defender is an agent whose explicit purpose, in opposition to the attacker, is to prevent this occurrence.  The system itself is oblivious to the fact that it is under attack.  The system goes through its normal routine according to its purpose and goals regardless of the actions of the active agents.  Network attack graphs represent a collection of possible penetration scenarios in a computer network.

The actors in attack graphs are:
-	An Attack Model
        Is a finite automation M = (S, i, s0), where S is a set of states, t is a subset of SxS and is a transition relation, s0 is an element of S and is the initial state.  The state space S represents a set of three agents I = {E,D,T}.  Agent E is the attacker, agent D is the defender, and agent N is the system under attack.  Each agent in I has its own set of possible states, Si, so that S = X(for all elements in I)Si.
-	A Finite Execution of an attack model
        Is a finite sequence of states.  An infinite execution of an attack model M, is an infinite sequence of states.
-	Security Property
        Given an attack model M, a security property, P, is a subset of the set of L(M) of executions of M
-	Execution
        An execution (that is an element of L(M)) is correct with respect to a security property, P if and only if, the execution is an element of P.  An execution is failing with respect to P (violates P), if and only if it is not an element of P
-	Attack Graph
        Given an attack model M, and a security property P, an attack graph of M with respect to P is the set of L(M)\P of failing executions of M with respect to P.

The project will be restricted to finite executions and network attack graphs.

Deliverables:
As there has been no (or limited) automated construction of attack graphs, I will attempt to implement a network attack graph algorithm using a web based application.  I will also review some of the open source attack tree software and run it against several different networks for analysis.

The accompanying report for this project will outline the theory and algorithms for attack graphs and the theory and review of the software and analysis for attack trees.  Accompanying code will be for the implementation of attack graph software.

Sources:
http://www.cs.cmu.edu/~wing/publications/SheynerWing04.pdf 
http://www.acsac.org/2006/papers/70.pdf 
http://csrc.nist.gov/publications/nistir/ir7788/NISTIR-7788.pdf