Slide 2
This talk has the following organization:
1) The motivation for the work
2) The Kolmogorov Complexity Method (KCM) we have proposed
3) Our novel K-step Capability Accumulation (KCA) metric 
and lastly we apply the Kolmogorov Complexity Method to our KCA metric.

Slide 3
Few would disagree with the assertion that a secure system is a system that is difficult to cause a security policy violation in.  From this perspective, we can view the security of a system in terms of how difficult it is to cause a security breach.   Exploitability is a term used to characterize the ease an attacker experiences in exploiting a vulnerability. 

Slide 4
Each of these reputable organizations have included exploitability into their assessments of a system’s security.  The inclusion of exploitability across these organizations suggest the importance of exploitability.  Moreover, understanding the exploitation process is critical.  One tool we have for analyzing attack paths is the attack graph.  And we assert that the analysis of the attack paths of the attack graphs could yield useful information to the security engineer. 

Slide 5
The following is an attack graph. For simplicity, allow the nodes to correspond to hosts, and the edges to correspond to CVE vulnerabilities that the attacker can exploit.  The attacker’s goal is to reach the Victim host because there is some valuable information stored at this host.  Through sanning the network and capturing the connectivity of the network, an attack graph can be generated that reveals all the ways an attacker can reach the Victim from his initial state given the KNOWN vulnerabilities. 

Slide 6
If you inspect the literature, one of the first things you will realize is that there is no consistency in how attack graph path length is represented.  These issues create the problems stated on this slide. If security will be taken seriously, there must be a way for us to communicate something as important as attack path difficulty in a consistent and sound way. 

Slide 7
The following is a wish list for a consistent way of measuring attack paths.  We believe KCM achieves this aim. 

Slide 8
Kolmogorov Complexity has been shown that a lower bound K for any given string can never be known.  This an important factor to bear in mind.  We apply Kolmogorov Complexity to attack paths.  And the aforementioned result means that we can never know the “true” effort an effort an attacker exerts to violate security policy.  This seems to agree with our own logic.  More importantly, we only need an approximation of how difficult exploitation is.   Our approach requires the use of a language in order to represent attack paths, and that is what follows. 

Slide 12
There are more qualitative representations, but we show only a few here. As you can see the modeler has the ability to very different ways based on his or her own assumptions.  The quantitative representation makes the assumption that each vulnerability requires equal effort.  The first qualitative representation says that exploiting v1 once makes the effort of exploiting v1 again trivial.  The second qualitative representation says that while most of the v1 vulnerabilities are trivial to exploit after one is exploited, the last vulnerability to reach the target host is different (e.g., requires a different set of credentials).  The last qualitative representation says something similar. 

Slide 13
One limitation in other approaches, is that there was no ability to capture the path length of a path with a cycle in it.  Using KCM we can model cycles in attack graphs.  For the sake of time, we will move on to the KCA metric 

Slide 15
Broadly speaking, there are two types of security metrics: capability metrics, and complexity metrics. The number of paths metric says security is commserate with the number attack paths in the attack graph.  The weakest adversary metric claims that the security of a network is equivalent the capability of the weakest attacker that can violate a security policy in your network. Network compromise percentage is the percentage of hosts in your network that can be compromised by an attacker. 

The shortest path metric says that the security of your network is equivalent to the path of least resistance. The mean of path lengths metric claims that average difficulty experienced by attacker when attacker a network is the security of the network. Each of the approaches have drawbacks because they measure a dimension of security, and security is inherently multidimensional. 

Slide 17
Suppose that a network administrator is choosing from two different configurations for his network.  These configurations can be referred to as network_1 and network_2.  
Now further suppose that once he analyzed both configurations, he found that he obtained two different attack graphs for these networks, G1 and G2 respectively.  

The KCA metric can help the network administrator determine which of two networks he should deploy.  
Cap_h corresponds to the capabilities the attacker can attain at level h in the attack graph (where the attacker’s level in the attack graph is at height zero).

KCA_k then is the union of Cap_h for i equal to 0 up to k

As can be seen, depending on what level of the attack you are intersted in, you may obtain different values. 

Slide 19
The second bullet says that when s_j^0...i is expanded it is equivalent to some quantitatve representation such that any vulnerabilities appear within q0 and qm appear in between s0 and si -- in other words, s corresponds to a qualitative representation where vulnerabilities that are same, after the first one of its kind is exploited, no longer adds to the difficulty of an attack path.