N. R. Pokhrel, C. P. Tsokos
94
graph when a number of nodes and complexity of the network increase. As the
scalability and complexity of the network increase exponentially, the computa-
tion cost to create the attack graph increases. As a result, it is difficult to interp-
ret the attack graph precisely. On the other hand, most of the attack graphs are
designed for a single target, and cannot be used to evaluate the overall security of
the networks with several targets. To address these striking problems Anming
Xie, Zhuhua Cai, Cong Tang, Jianbin Hu, and Zhong Chen [11] developed a
novel approach to generate and describe the attack graph. They developed a two
layer attack graph, where the upper layer is a host access graph and the lower
layer is composed of some host pair attack graphs. The lower level describes all
the detailed attack scenarios between each host pair, and the upper level shows
the direct network access relationship between each host pair by ignoring de-
tailed information. In this study our stochastic model is based on upper layer at-
tack graphs; that is, host access graphs have been utilized.
2.3. Common Vulnerability Scoring System (CVSS)
CVSS [12] is the open framework that provides the quantitative scores repre-
senting the overall severity and risk of the known vulnerabilities. It is maintained
by the
Forum of Incident Response Team (FIRST) [13]. A CVSS score is on
the scale of 0 to 10 and consists of three major metrics group: base, temporal and
environmental as mentioned in
Figure 1. Vulnerabilities with the base score range
from 0 - 3.9 is considered
Low vulnerability, 4.0 - 6.9 as Medium, and 7.0 - 10 as
High. The base score is computed using two sub-scores; Exploitability sub-score
and
Impact sub-score using standard expression mentioned in Figure 1. These
two sub-scores are the fundamental quantitative value for our analysis.
2.4. Markov Chain
A Markov chain is regarded as one of the best modeling techniques that has been
used effectively in various fields such as reliability analysis [14], performance
analysis, dependability analysis [15] [16], and cybersecurity analysis [17], among
others. We will model the host access attack graph described in the previous
subsection using a Markov chain with the real behavior of the attacker in con-
junction with the Markovian properties.
Mathematically, a Markov chain can be defined as a discrete stochastic
process [18]. More specifically let
S
be a set of states (in the present study
S
is fi-
nite, we can think of it as nodes in host access graph). A Markov chain is a se-
quence of random variables
that satisfies the “Marko-
vian property”, that is,
1 0 01 1 1
, ,,
n nn n nn
P X yX x X x X x P X yX x
++
= = = = = = =
The Markovian properties reveal the fact that the transitions between states
are memoryless; transitioning to the next step depends only on the current state
and not on any of the other previous states. We can correlate this property with
the attacker’s behavior in a sense that an attacker needs to exploit several nodes
before reaching the goal node. When the attacker starts attacking an immediate