Journal of Information Security, 2011, 2, 8-27
doi:10.4236/jis.2011.21002 Published Online January 2011 (http://www.SciRP.org/journal/jis)
A Novel Attack Graph Posterior Inference Model Based on
Bayesian Network
Shaojun Zhang1, Shanshan Song2
1School of Information Security Engineering, Shanghai Jiao Tong University, Shanghai, China
2Information Technology Department, Guotai Junan Futures Co., Ltd, Shanghai, China
Received January 5, 2011; revised January 17, 2011; accepted January 18, 2011
Abstract
Network attack graphs are originally used to evaluate what the worst security state is when a concerned net-
work is under attack. Combined with intrusion evidence such like IDS alerts, attack graphs can be further
used to perform security state posterior inference (i.e. inference based on observation experience). In this
area, Bayesian network is an ideal mathematic tool, however it can not be directly applied for the following
three reasons: 1) in a network attack graph, there may exist directed cycles which are never permitted in a
Bayesian network, 2) there may exist temporal partial ordering relations among intrusion evidence that can-
not be easily modeled in a Bayesian network, and 3) just one Bayesian network cannot be used to infer both
the current and the future security state of a network. In this work, we improve an approximate Bayesian
posterior inference algorithm–the likelihood-weighting algorithm to resolve the above obstacles. We give out
all the pseudocodes of the algorithm and use several examples to demonstrate its benefit. Based on this, we
further propose a network security assessment and enhancement method along with a small network scenario
to exemplify its usage.
Keywords: Network Security, Attack Graph, Posterior Inference, Bayesian Network, Likelihood-Weighting
1. Introduction
Network attack graphs [1-5] are widely used as a good
tool to analyze network security state in comprehensive
consideration of exploits, vulnerabilities, privileges, net-
work connectivity, etc. Originally, they are built to tell
what the worst scenarios are when a network is under
attack. But later, it is found that security alerts can be
mapped to them [6-8] and along with these observed
intrusion evidence, attack graphs can also be used to as-
sess the security state of a concerned network dynami-
cally.
In this area, probabilistic approaches have been pro-
posed to perform such analysis. In [9], a method which
reasons about complementary intrusion evidence is pre-
sented. According to the method, security alerts gener-
ated by intrusion detection systems (IDSs) as well as
reports generated by system monitoring tools can be in-
tegrated into Bayesian networks. And prior conditional
probability values which denote the success rate of the
corresponding attacks can be assigned to each of the evi-
dence nodes. By doing this, uncertain or unknown intru-
sion evidence can be reasoned about based on verified
evidence. Although quite useful in reasoning observed
intrusion evidence, this method cannot tell people what
attack will be executed next and with what probability.
In [10], HCPN (Hidden Colored Petri-Net) is used to
depict the relationship among different steps carried out
by an intruder and model intrusion actions and intrusion
evidence together. The initial state of HCPN attack graph
is determined by an initial probability distribution. And
empirical formulas are defined to reevaluate its state af-
ter receiving each alert from the sensors (most com-
monly are IDSs). This method runs quite well in predict-
ing what the next intrusion actions are. However, at re-
evaluating the probabilities of the graph nodes according
to the alerts, the method only updates probabilities of the
successor nodes of an assumed action node, which obvi-
ously contravenes our intuition that in most inference
algorithms there must be backward belief propagation
(i.e. probabilities of the predecessor nodes should also be
updated).
To overcome these flaws, we firstly thought about ex-
tending the Bayesian network into a general attack graph

S. J. ZHANG ET AL.
9
definition to integrally model intrusion resources, actions
and evidence. By exploiting Bayesian network’s embed-
ded posterior inference capability, it can not be plainer to
perform attack graph-based posterior inference [11].
However, soon we found that things were not so easy.
There are at least three main differences between an at-
tack graph and a Bayesian network which obstruct this
way:
 In a Bayesian network, no directed cycles are al-
lowed. However, in a network attack graph, this re-
striction is not appropriate since people always
want to depict potential intrusion paths succinctly.
 In a Bayesian network, there can not be any partial
ordering relations among evidence nodes. However,
we can often observe temporal partial ordering re-
lations among intrusion evidence (e.g. when an ips-
weep is observed before a portscan), which may in-
dicate that some exploits happen before some oth-
ers.
 At performing attack graph-based posterior infer-
ence, two questions are most often raised: 1) what
is the current state of a network, and 2) what is the
future state of it. Essentially this means one set of
observed intrusion evidence should be used to infer
two temporally different states. In Bayesian infer-
ence, this demands two prior conditional probabi-
listic distribution, one for current state inference
and one for future state inference. Although we
think it feasible to define the later one (For exam-
ple we say an exploit will happen in probability 0.8
if an attacker was given enough time), it is really a
disaster to define the former one (how to assess the
exploit probability when the attacker has got two
hours).
These obstacles almost made us give up Bayesian po-
sterior inference. But fortunately we find a good way to
overcome them—we manage to improve the likelihood-
weighting algorithm (an approximate Bayesian inference
algorithm) into a novel attack graph-based posterior in-
ference algorithm. And based on this, we find a method
to quantitively assess the overall security level of a con-
cerned network and identify the most cost-effective se-
curity measures to enhance it.
The rest of this paper is organized as follows. Section
2 depicts the aforementioned posterior inference prob-
lems in details. Section 3 introduces the underlying for-
malized attack graph definition. Section 4 describes our
improved likelihood-weighting algorithm and Section 5
gives out several examples for benefit testification. Sec-
tion 6 presents our security assessment and enhancement
method and Section 7 gives out an example to exemplify
it. The last section concludes the paper.
2. The Primal Motives
2.1. Directed Cycles
Various models and methods have been proposed to re-
present multi-step network attacks and generate network
attack graphs automatically. These models and methods
can be roughly divided into two categories: security state
enumeration and vulnerability/exploit dependency. Com-
paratively, the later one is more popular since it exhaus-
tively and succinctly depicts the interdependency of se-
curity elements such as privilege, trust, vulnerability, ex-
ploit, network connectivity, etc. Representatives of this
category include the approaches proposed in [2-5]. In this
category, although some approaches promise that they
only generate attack graphs without directed cycles, we
cannot assume that all of them are generating DAG (Di-
rected Acyclic Graph).
Here is an example to demonstrate that directed cycles
sometime are useful since we want to depict the intrusion
paths succinctly. Assume there are three hosts on a small
network which is illustrated in Figure 1. Host Master has
a certain vulnerability that can be exploited by the other
two hosts to gain its USER privilege. On the other hand,
the USER accounts on Master are mapped to a ROOT
account on the other two hosts.
We can imagine that a succinct network attack graph
for this network is like the one shown in Figure 2.
In Figure 2 we adopt a graph notation widely used in
Petri-Net. Circle s1, s2 and s3 respectively denote that
the attacker has got ROOT privilege on Slave1, ROOT
privilege on Slave2 and USER privilege on Master. Line
a1 and a2 denote the attacker exploits the vulnerability of
Master respectively from Slave1 and Slave2. Obviously,
in this attack graph, there exist directed cycles.
2.2. Evidence Partial Ordering Relations
In a Bayesian network, there cannot be any partial or-
dering relations among observed evidence. However, at
performing security posterior inference, temporal partial
ordering relations among evidence nodes often provide
us important cues. Figure 3 illustrates an example which
demonstrates the benefit of analyzing temporal partial
ordering relations among intrusion evidence.
In Figure 3, we assume that the attacker initially oc-
cupies resource s1 and her goal is to occupy s6. The at-
tacker can use exploit a1~a6 to perform intrusion. How-
ever, exploit a1 and a4 will trigger alert o1, exploit a2 and
a3 will trigger alert o2 and a5 and a6 will trigger alert o3.
Finally, during the intrusion, an evidence sequence o2→
o1→o3 is observed.
Analysis: To achieve her goal, the attacker can choose

S. J. ZHANG ET AL.
10
Figure 1. A small network environment.
a
2
a
1
s
1
s
3
s
2
Figure 2. Attack graph for the network.
s
4
s
1
s
2
s
3
a
1
o
1
o
2
s
5
a
2
a
3
a
4
s
6
a
5
a
6
o
3
Figure 3. A simple network attack graph.
two intrusion paths:
α. s1→a1→s2→a3→s4→a5→s6
β. s1→a2→s3→a4→s5→a6→s6
If we neglect all temporal partial ordering relations, then
the three evidence nodes are set to True. And since the
attack graph is symmetrical (notice there is no ordering
relations between evidence nodes), using Bayesian pos-
terior inference we can find that both intrusion paths can
be chosen by the attacker. However, if we do consider
temporal partial ordering relations, we can infer that only
intrusion path β is chosen by the attacker, since execut-
ing intrusion path α will violate the temporal partial or-
dering relation o2→o1.
2.3. Posterior Inference for Multi-State
As we mentioned before, two questions are most often
raised at performing attack graph-based posterior infer-
ence: 1) what is the current state of a network, and 2)
what is the future state of it. In Bayesian inference, this
means two different prior conditional probabilistic dis-
tribution should be assigned—one for current state in-
ference and one for future state inference. If we say the
assignment for the later one is tough but still practical,
then it is almost infeasible to define the former one.
People may argue that Hidden Markov Model [12] or
Generalized Hidden Semi-Markov Models [13] can be
used to resolve this problem. But in HMM or GHSMMs,
a key concept is the time instants associated with state
changes. This concept is quite natural in technique areas
such as speech signal processing. However in security
analysis we cannot just fix a time slot for an attacker to
perform actions. And even we do constrainedly figure
out this slot, we still face the problem of how to define
the probability of an action when the attacker is given
one time slot.
Under this understanding, we decide to stick to Baye-
sian inference and seek if we can use one prior condi-
tional probabilistic distribution with one set of observed
intrusion evidence to infer two temporally different secu-
rity states. Eventually we successfully resolve this chal-
lenge by inventing a sample reprocessing method called
transientization which will be introduced in Section 4.
3. The Underlying Model
In this section, we propose a formalized network attack
graph definition as the basis for attack graph-based secu-
rity posterior inference.
In the early days of Internet, network attacks are often
performed to demonstrate the personal skills of the at-
tacker. They were limited to a small number of known
methods such as cracking the password and exploiting
the operating system vulnerabilities. But lately attacks
have evolved into complex procedures which may com-
prise several interrelated intrusion actions. Execution of
these actions incrementally changes the security state of
the network, making the attacker take over more and
more resources (and most commonly during the intrusion
procedure the attacker will not give up resources she has
already got [3]) and eventually achieve her goal. Fortu-
nately, security devices such as IDSs will send alerts if
there is an attack. Then administrators can use them to
assess the real state of the network and take proper
measures to compensate.
A network attack graph depicts the above three com-
ponents (network resource, intrusion action and intrusion
evidence) and their causal relationship. In most cases, it
can exhaustively and succinctly comprises all of the po-
tential intrusion paths. Based on the above analysis, an
attack graph can formally be defined as:
Definition 1. An attack graph is a 10-tuple directed
graph


0
,,,,,,,,,AGSSGA OE

 , where:



1, ,
is
Ssi N is a finite set of resource
state nodes. The value of each node variable i
s
can be either True or False, denoting if a resource
has been taken over by the attacker;
 0 SS is a subset of S representing resources the
attacker may initially occupy. Graphically it is the
root nodes of AG;

S. J. ZHANG ET AL.
11
 GS is a subset of S representing attack goals;


1, ,
ia
A
ai N is a finite set of intrusion ac-
tion nodes. The value of each node variable i a
can be either True or False, denoting whether an
intrusion action has been conducted by the at-
tacker;


1, ,
io
Ooi N is a finite set of intrusion
evidence nodes. The value of each node variable
i
o can be either True or False, denoting whether
the evidence has been observed. Considering that
in most occasions intrusion evidence will be pre-
processed (e.g. fused) by the low-layer sensors so
that their observation numbers are often distorted,
here we only consider whether a kind of evidence
has been observed, discarding its concrete observa-
tion number;


123
EEEE is a finite set of edges which
link nodes together. 1
ESA is a set of edges
which denote actions can only be conducted given
that all the prerequisite resources are taken over by
the attacker; 2 EAS is a set of edges which
denote actions may consequently let the attacker
take over some other resources and 3
EAO is
a set of edges which denote actions may trigger cer-
tain intrusion evidence. Generally we use


nPre
and

nCon to respectively denote the prerequi-
site nodes and consequent nodes of node n;






:,0,1
ii
aa   Pre is the prior condi-
tional probability distribution that an action will be
conducted if its prerequisite is satisfied. In this pa-
per, we assume that all elements of


i
aPre are
in a conjunctive normal form. In other words, an
action can be conducted only if all its prerequisite
resources are occupied by the attacker;






:, 0,1
ii
aa   Con is the probability
distribution that an action will succeed if it is con-
ducted. Since an action changes its consequent re-
source state only when it succeeds,  is also the
probability that an action set its consequent node
variables to True. Here we assume that for any re-
source node i
s
if there are more than one suc-
cessful actions in

i
s
Pre , then each of them can
set i
s
to True independently;




:, 0,1
ij
ao   is the probability distri-
bution that a type of intrusion evidence will be ob-
served if one of its prerequisite actions is con-
ducted. Here we also assume that for any evidence
node
j
o if there are more than one successful ac-
tions in

j
oPre , each of them can set
j
o to
True independently;




:0,1SAO    is the node belief
distribution of AG. Here

i
s
 denotes the prob-
ability that the attacker has taken over resource i
s
;


i
a  denotes the probability that action i a has
been conducted by the attacker and


i
o  de-
notes the probability that evidence i o has been
observed. Specially, 0  is the initial node belief
distribution of AG, denoting what resources are
occupied by the attacker at the very beginning. So,
we can expect:



00
00
0,
0,
ii
ii
nnS
nnS




.
Graphically, a network attack graph follows Definition
1 is like the one illustrated in Figure 4.
In Figure 4, the attacker initially occupies resource s1,
s2 and s3 (with probabilities defined in 0 ). Then intru-
sion actions a1, a2 and a3 will be conducted (with prob-
abilities defined in

), and further make the attacker
take over resource s4~s7 (with probabilities defined in

). As actions being conducted, intrusion evidence
o1~o4 will be triggered and observed (with probabilities
defined in

).
As mentioned before, in this paper, we are only inter-
ested in whether a type of evidence has been observed,
discarding its concrete observation number. However,
we can still utilize the temporal partial ordering relations
among attack evidence to assist posterior inference.
Definition 2. There are two categories of evidence
temporal partial ordering relations. We say:
 There is a type I temporal partial ordering relation
om↗on if om is observed before on is observed. In
other words, the first observation timepoint of om is
earlier than the first observation timepoint of on.
 There is a type II temporal partial ordering relation
om↘on if om is never observed after on is firstly
observed. In other words, all the observation time-
points of om are earlier than any of the ones of on.
With the above definition, the problem of network at-
tack graph-based posterior inference can be defined as:
Given an attack graph AG, when an evidence sequence
12ii ik
oo o


 which conforms to a partial
s
1
o
1
s
2
s
3
s
4
s
5
s
7
a
1
a
2
a
3
o
2
o
3
o
4
s
6
Figure 4. A typical network attack graph.

S. J. ZHANG ET AL.
12
ordering relation set Ω = {om↗on}{om↘on} is ob-
served, how to compute the corresponding graph node
belief distribution sequence 01 k


 ?
4. The Posterior Inference Algorithm
In this section, we propose an algorithm for resolving the
above posterior inference problem. Our algorithm is mai-
nly based on the approximate Bayesian inference algo-
rithm—the likelihood-weighting algorithm.
A Bayesian network (or a belief network, a causal net-
work) is a probabilistic graphical model that represents a
set of variables and their probabilistic independencies.
Essentially, a network attack graph following Definition
1 is a mimetic Bayesian network. However, since a Baye-
sian network cannot contain any directed cycle or partial
ordering relation of evidence nodes, traditional Bayesian
inference should not be used to perform this attack
graph-based posterior inference.
To support these additional features, we manage to im-
prove one of the approximate Bayesian network inference
algorithms–the likelihood weighting algorithm [14,15] to
a novel one. Likelihood weighting enhances logic sam-
pling algorithm in that it never discards samples. It is the
most commonly used simulation method for Bayesian
network inference. Pseudocode of our improved algo-
rithm is as follow:
The 2nd line of the pseudocode is an outside loop con-
trol statement which drives the algorithm to generate n
effective samples in one run. In the loop, effective sam-
ples are generated and added into a sample set Ξ which
will eventually be returned.
Pseudocode 3~35 is to generate an effective sample,
which could be regarded as one potential attack scenario.
This procedure can be further divided into five stages:
1) Initialization (3~6). In this stage, firstly two vari-
ables wi and C are initialized. Here wi will be used to
hold the weight of the sample and C will be used to hold
the node pairs that temporally cannot be updated for their
causation relationship. Then each node X in the attack
graph is set to False and two assistant set variable FX and
BX are initialized to empty. FX will be used to hold the
nodes whose value are set to True by X. BX will be used
to hold the nodes who set X to True. From another point
of view, FX and BX respectively hold the forward and
backward causation pointers of X.
2) Nodes sampling (7~23). In this stage, all the nodes
in AG (except those nodes in OD) will be sampled. Firstly,
in line 7~10, root nodes are sampled according to the
initial node belief distribution Π0. Then, in line 11~23,
AG is circularly updated until no more changes occur. In
each cycle, every True value node X is checked out and
a subfunction UpdateAttackGraph (for space limitation,
pseudocodes of all the subfunctions are given out in An-
ImprovedLikelihoodWeighting (AG, n, OD, OF, Ω, m)
Input: AG — a network attack graph;
n — effective sample number to generate;
O
D — a set of observed evidence nodes;
O
F — a set of not observed evidence nodes;
Ω — a temporal partial ordering relation set on
OD∪OF;
m —inference mode, 0 for future state, 1 for current
state.
Output: Ξ — a set of effective samples.
Algorithm: 01: Ξ←Ø; i←0;
02: while (i<n)
03: wi←1; C←Ø;
04: for (each node variable X in AG)
05: X←False; FX←Ø; BX←Ø;
06: end for (04)
07: for (each node variable X∈S0)
08: X←the sampling result according to Π0;
09: Mark X as sampled;
10: end for (07)
11: converged←False;
12: while (!converged)
13: converged←True;
14: for (each node variable X=True in AG)
15: for (each node variable Y∈Con(X))
16: if (edge X→Y is not sampled) then
17: if (UpdateAttackGraph(AG,X,Y)) then
18: converged←False;
19: end if (17)
20: end if (16)
21: end for (15)
22: end for (14)
23: end while (12)
24: for (each node variable X∈OD)
25: X←True;
26: wX←SelectEvidenceCausation(AG,X);
27: wi←wi*wX;
28: end for (24)
29: if (m=1) then
30: b←Transientize(AG,OD,OF);
31: end if (29)
32: if (b∧PartialRelationSatisfied(AG,OD∪OF,Ω))
then
33: ξi.AG←AG; ξi.w←wi;
34: Ξ←Ξ∪{ξi}; i←i+1;
35: end if (32);
36: end while (02)
37: return Ξ;

S. J. ZHANG ET AL.
13
nex A of this paper) is called on each pair of X and its
descendant node Y iff the edge X→Y is not sampled.
3) Observed evidence causation selection (24~28). In
this stage, for each observed evidence node X in OD, a
subfunction SelectEvidenceCausation is called on X to
randomly select a causation set from Pre(X) to denote
what set X to True. At the same time, the occurrence
probability of this chosen causation set will affect the
weight of the sample.
4) Transientization (29~31). If what we need to infer is
the current state of the network, then the sample should
be reshaped to represent a budding (not fully developed)
attack scenario. The processing transientization is based
on the idea that although some evidence nodes in OF may
equal to True in the sample, they actually represent evi-
dence that will be observed only in the future (currently
only the ones in OD are observed). So, correspondingly,
the actions that trigger the evidence also have not oc-
curred yet. This means, in order to reshape the sample to
represent current state, all these nodes should be set to
False. In our algorithm, this processing will be perfor-
med through a subfunction Transientize.
5) Sample effectiveness verification (32~35). In this
stage, a subfunction PartialRelationSatisfied is called to
check whether the temporal partial ordering relations
among the evidence nodes conform to the causation rela-
tions among the action nodes.
By running the algorithm, we can get a set of samples
which not only have node values generated under the gi-
ven probability distribution, but also definitely conform
to the temporal partial ordering relations among evidence.
Then, to use this sample set, a node belief computation
function is defined as follow:
By running this function, a set M will be returned
which contains all the node belief values for later queries.
By inputting different intrusion evidence sequences
which correspond to different observation timepoints, we
can get an attack graph node belief distribution sequence
01 k


  to represent security state evolvement.
5. Node Belief Computation Examples
In order to exemplify the improved likelihood-weighting
algorithm, we design and implement a Java program to
perform following experiments:
5.1. Comparison with Bayesian Inference
Firstly, we use the variable elimination algorithm (a tra-
ditional Bayesian inference algorithm) to compute the
posterior node belief values of the attack graph illustra-
ted in Figure 3. The result is listed in Table 1.
In Table 1, different number i denotes different infer-
ence layer. In this example, i = 0 denotes the inference is
performed before any evidence is observed, i = 1 denotes
the inference is performed after o2 is observed, i = 2 de-
notes the inference is performed after sequence o2→o1 is
observed and i = 3 denotes the inference is performed
after o2→o1→o3 is observed.
Then we use our improved likelihood weighting algo-
rithm to perform the same inference. The result is listed
in Table 2 (10000 effective samples without transienti-
zation) and Table 3 (10000 samples with transientiza-
tion).
Since traditional Bayesian network inference methods
does not support intrusion evidence ordering, we are not
surprised to see that in Table 1, when i > 1, the node
belief values of intrusion path α and β are mirror sym-
metrical. This makes it difficult for us to judge which
path has been chosen by the attacker. However, by using
improved likelihood weighting algorithm, we can ob-
serve no matter in Table 2 or Table 3, the node belief
values of path β are all higher than path α, indicating it is
more likely to have been chosen by the attacker.
NodeBeliefComputing(AG,n,OD,OF,Ω,m)
Input: AG — a network attack graph;
n — effective sample number to generate;
O
D — a set of observed evidence nodes;
O
F — a set of not yet observed evidence nodes;
Ω — a temporal partial ordering relation set on
OD∪OF;
m —inference mode, 0 for future state, 1 for current
state.
Output: M — a node belief metric set
Algorithm: 01: M←Ø; W←0;
02: Ξ←ImprovedLikelihoodWeighting(AG,n,
OD,OF,Ω,m);
03: for (each node variable X in AG)
04: NX←0;
05: end for (03)
06: for (each sample ξ in Ξ)
07: for (each node variable X in ξ.AG)
08: if (X=1) then
09: NX←NX+ξ.w;
10: end if (08)
11: end for (07)
12: W←W+ξ.w;
13: end for (06)
14: for (each node variable X in AG)
15: M←M∪{PX=NX/W};
16: end for (14)
17: return M;

S. J. ZHANG ET AL.
14
Table 1. Node belief values (use traditional inference).
i πi(s1) πi(s2) πi(s3) πi(s4) πi(s5) πi(s6)
0 1.000 0.250 0.250 0.063 0.063 0.031
1 1.000 0.333 0.444 0.111 0.111 0.055
2 1.000 0.500 0.500 0.167 0.167 0.083
3 1.000 0.619 0.619 0.524 0.524 0.504
i πi(a1) πi(a2) πi(a3)πi(a4) πi(a5) πi(a6)
0 0.500 0.500 0.125 0.125 0.031 0.031
1 0.556 0.889 0.222 0.222 0.056 0.056
2 0.833 0.833 0.333 0.333 0.083 0.083
3 0.746 0.746 0.556 0.556 0.508 0.508
Table 2. Node belief values (without transientization).
i πi(s1) πi(s2) πi(s3) πi(s4) πi(s5) πi(s6)
0 1.000 0.247 0.259 0.060 0.063 0.028
1 1.000 0.250 0.499 0.060 0.121 0.042
2 1.000 0.392 0.606 0.092 0.202 0.071
3 1.000 0.494 0.831 0.366 0.701 0.504
i πi(a1) πi(a2) πi(a3)πi(a4) πi(a5) πi(a6)
0 0.498 0.503 0.122 0.132 0.031 0.029
1 0.504 1.000 0.127 0.246 0.028 0.058
2 0.792 1.000 0.190 0.405 0.044 0.101
3 0.663 1.000 0.409 0.744 0.342 0.680
Table 3. Node belief values (with transientization).
i πi(s1) πi(s2) πi(s3) πi(s4) πi(s5) πi(s6)
0 1.000 0.000 0.000 0.000 0.000 0.000
1 1.000 0.000 0.504 0.000 0.000 0.000
2 1.000 0.246 0.630 0.000 0.220 0.000
3 1.000 0.147 1.000 0.000 1.000 0.505
i πi(a1) πi(a2) πi(a3)πi(a4) πi(a5) πi(a6)
0 0.000 0.000 0.000 0.000 0.000 0.000
1 0.000 1.000 0.000 0.000 0.000 0.000
2 0.747 1.000 0.000 0.442 0.000 0.000
3 0.430 1.000 0.000 1.000 0.000 1.000
Then, to testify that our improved likelihood weight-
ing algorithm can process attack graphs that contain di-
rected cycles, we run the program to compute node belief
values for Figure 2. Assuming in initial state the attacker
occupies s1 and that every other used probability is 0.5,
the inference result is listed in Table 4 (10000 effective
samples, and since the graph has no evidence nodes, the
result is same no matter the samples are transientized or
not).
5.2. Comparison with HCPN-Based Inference
As aforementioned, in HCPN-based inference, empirical
formulas are defined to reevaluate the security state of
the network after intrusion evidence is observed. Compa-
ratively, our algorithm is not dependent on any empirical
formula, which makes the inference results more rational.
To prove that, we modify the Figure 3 example to the
one illustrated in Figure 5.
Comparing with Figure 3, in Figure 5 three additional
nodes a7, s7, o4 with the corresponding edges are added.
Meanwhile, some of the action-evidence relations are
modified and all the probabilities are explicitly labeled
on the edges.
Similar to Figure 3, under the initial state the attacker
whose final attack goal is also g1 is assumed to occupy
resource s1 with probability 1.0. But during the attack, an
evidence sequence o1→o2→o3→o4 is observed.
Using the HCPN-based inference method, we can get
node belief values listed in Table 5 (since HCPN only
defines the belief value of resource nodes, nodes of other
types are not listed).
Then we run our improved likelihood weighting in-
ference program to perform the same computation. The
result is listed in Table 6 (10000 effective samples
without transientization) and Table 7 (10000 effective
samples with transientization).
s
4
s
1
s
2
s
3
a
1
o
1
o
2
s
5
a
2
a
4
s
6
a
5
a
6
o
3
g
1
s
7
o
4
0.8
0.5
1.0
1.0
0.81.0
a
3
0.8
1.0
0.5 1.0 0.5
0.5
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
a
7
Figure 5. A network attack graph.
Table 4. Our inference result.
i πi(s1) πi(s2) πi(s3) πi(a1) πi(a2)
0 1.000 0.129 0.248 0.502 0.065

S. J. ZHANG ET AL.
15
Table 5. HCPN-based inference result.
i assumed
action πi(s1) πi(s2) πi(s3)πi(s4) πi(s5) πi(s6)πi(s7)
0 - 1.0 0.0 0.0 0.0 0.0 0.0 0.0
a1 1.0 0.615 0.00.0 0.0 0.00.0
1
a2 1.0 0.0 0.3850.0 0.0 0.0 0.0
a3 1.0 0.615 0.0 0.275 0.0 0.00.0
2
a4 1.0 0.0 0.385 0.0 0.193 0.00.0
a5 1.0 0.615 0.0 0.275 0.0 0.109 0.0
3
a6 1.0 0.0 0.385 0.0 0.193 0.057 0.0
4 a7 1.0 0.0 0.385 0.0 0.193 0.0570.057
Table 6. Our inference result (without transientization).
i πi(s1) πi(s2) πi(s3) πi(s4) πi(s5) πi(s6)πi(s7)
0 1.000 0.800 0.507 0.641 0.250 0.581 0.124
1 1.000 0.888 0.558 0.714 0.278 0.641 0.137
2 1.000 0.931 0.569 0.877 0.349 0.787 0.174
3 1.000 0.955 0.563 0.918 0.339 1.000 0.171
4 1.000 0.865 1.000 0.757 1.000 1.000 1.000
i πi(a1) πi(a2) πi(a3) πi(a4) πi(a5) πi(a6)πi(a7)
0 0.800 0.507 0.641 0.250 0.518 0.125 0.124
1 0.888 0.558 0.714 0.278 0.574 0.141 0.137
2 0.931 0.569 0.877 0.349 0.703 0.174 0.174
3 0.955 0.563 0.918 0.339 0.890 0.227 0.171
4 0.865 1.000 0.757 1.000 0.678 0.660 1.000
We can observe that in Table 5, from layer 1 to 3,
different actions denoting different attack paths are as-
sumed to be conducted by the attacker. In these layers,
inferred node belief values of intrusion path α are all
higher than the values of path β. That is mainly due to
the different probability values assigned to the two paths.
In layer 4, the predominant attack path α is excluded
from further consideration as o4 can only be triggered by
a7 which is on attack path β. That judgment is quite rea-
sonable. However, we find that most node belief values
on attack path β are still not increased. It is due to the
empirical formulas defined in HCPN-based inference
method only update the belief values of the successor
nodes of a7 (obviously inconsistent with our intuition and
what we usually see in most inference models that there
should be a backward belief propagation procedure).
Table 7. Our inference result (with transientization).
i πi(s1)πi(s2)πi(s3)πi(s4) πi(s5) πi(s6)πi(s7)
0 1.000 0.000 0.000 0.000 0.000 0.000 0.000
1 1.000 0.896 0.551 0.000 0.000 0.000 0.000
2 1.000 0.930 0.557 0.878 0.339 0.000 0.000
3 1.000 0.957 0.555 0.921 0.327 1.000 0.000
4 1.000 0.863 1.000 0.758 1.000 1.000 1.000
i πi(a1)πi(a2)πi(a3)πi(a4) πi(a5) πi(a6)πi(a7)
0 0.000 0.000 0.000 0.000 0.000 0.000 0.000
1 0.896 0.551 0.000 0.000 0.000 0.000 0.000
2 0.930 0.557 0.878 0.339 0.000 0.000 0.000
3 0.957 0.555 0.921 0.327 0.894 0.218 0.000
4 0.863 1.000 0.758 1.000 0.674 0.668 1.000
In comparison, in Table 6 and Table 7, no action is
needed to be assumed to perform the inference. From
layer 1 to 3, inferred node belief values of path α are all
higher than the values of path β. And in layer 4, path β is
confirmed by the observation of o4, with all the belief
values of that path set to 1.0 (this is the backward belief
propagation we are expecting).
5.3. Algorithm Performance Evaluation
We adjust the specified number of effective samples (i.e.
m), then record the CPU time that is used to generate the
sample set. Figure 6 illustrates three performance curves
which respectively correspond to the above three exam-
ples. The hardware and software environment of the pro-
gram is: Intel Core2 Duo CPU 2.00GHz, 2GB DDR2
Memory, Windows XP Professional (with Service Pack
2), Sun JDK 1.6.0_10-rc.
Figure 6 shows that for a certain attack graph, the
CPU time to generate a sample set is basically propor-
tional to the number of the samples. Through a detailed
analysis it can be found that the sampling time consump-
tion is mainly determined by two facts: 1) the node num-
ber N of the attack graph and 2) the evidence temporal
partial ordering relation set Ω. According to Definition 1,
in any attack graph the prerequisite node number of a
single node is always below N, so we may define a con-
stant Tmax and use Tmax*N to denote the upper bound of
the time used to process a node. And the time to generate
a full sample will be less than N*(Tmax*N). On the other
hand, checking against the partial ordering relation set Ω
may force us to discard some generated samples. To con-

S. J. ZHANG ET AL.
16
Figure 6. CPU time curves of sampling.
trol this fact, we may specify a maximal try number M.
Once M samples have been generated (no matter how
many effective samples are there), the program will
cease sampling. In conclusion, for any attack graph, the
sampling procedure can always finish in Tmax*M*N2. In
other words, the algorithm has quadratic computational
complexity.
6. Security Assessment & Enhancement
In this section, based on the above node belief computa-
tion algorithm, we propose a model for assessing net-
work security level and performing security enhance-
ment.
6.1. Security Assessment
Generally, the overall security level of a concerned net-
work is mainly determined by three factors: 1) threat of
the network, 2) vulnerability of the network and 3) in-
fluence of the potential attacks. In the previously pro-
posed model, the former two factors have been dealt with
(by IDS alerts indicating threats and network attack
graph itself indicating vulnerabilities). However, we still
have a problem with how to model the influence of po-
tential attacks. In this section, we introduce a concept of
asset value breakage rate to quantify it.
Asset value breakage rate is the ratio of the lost asset
value to the overall asset value, illustrated in Figure 7.
Since we often use asset CIA (confidentiality, integrity
and availability) value to achieve more particular quanti-
fication, we introduce asset CIA breakage nodes into
Figure 7. Components of asset value.
network attack graph and extend Definition 1 into Defi-
nition 3.
Definition 3. An extended attack graph is a 12-tuple
directed graph


0
,,,,,,,,,,,AGSSAGOE


where 0 ,,,,,,,,SS AGO

 are the same elements
as defined in Definition 1 and:



CIA

   is a set of asset breakage
nodes where C

is a set of asset confidentiality
breakage nodes,
I

is a set of asset integrity
breakage nodes and A

is a set of asset availabil-
ity breakage nodes. Values of each node variable
Xi

(X = C, I, A; i = 1, , N. where N is the total
asset number) all lie in [0, 1], denoting the breakage
percentage of every asset in particular aspect. Apart
from that, we define a function


:0,+   to
map each asset to its overall value in confidential-
ity, integrity and availability. So we can use


ii

  to denote the absolute loss value of an
asset in CIA.



12345
EEEEEE is a finite set of
edges which link graph nodes together. Here E1, E2
and E3 share the same definition as in Definition 1,
while 4 ES denotes that if the attacker
gains certain resources, she will do damage to cer-
tain assets, and 5
EA denotes that if the at-
tacker executes certain actions, she will do damage
to certain assets.








12
:, 0,1,:, 0,1
ij ij
sa    is
the asset breakage conductivity rate distribution
where 1

denotes when the attacker gains a re-
source, how much damage will she do to an asset
and 2

denotes when the attacker executes an ac-
tion, how much damage will she do to an asset.
Just like the other prior conditional probability dis-
tributions, values of

also lies in [0, 1] where a
larger value denotes a greater potential damage.
Based on Definition 3, we can use a function




to quantify the network security level:











 
  
111 1
CCI IAA
CCII AA
CCI IAA
CI A



  


 

 



 
 



S. J. ZHANG ET AL.
17
In the above equation,




is the function to com-
pute the normalized asset residual value. The right ex-
pression uses asset residual value as the numerator and
asset overall value as the denominator.
Just like other network attack graph node variables, all
the belief values of asset breakage nodes also can be
computed by the inference algorithm in Section 4. So, by
inputting different evidence sequences corresponding to
different observation timepoints, eventually we can get a
sequence 01k

  indicating the security evolvement.
6.2. Security Enhanceme nt
Broadly speaking, as long as a measure can help en-
hacing network security, it is referred to as a network
security enhancement measure. In most cases, the im-
plementation of a security enhancement measure may
affect a network attack graph in two ways:
1) it changes the structure of the attack graph, or
2) it changes the conditional probability distributions
of the attack graph including 0 ,,,, .
However, since commonly the implementation of a
security enhancement measure will cut off certain intru-
sion paths, the resulting (enhanced) attack graph is often
the sub-graph of the original attack graph. Based on this,
we can always convert the above situation 1 into situa-
tion 2 by adjusting certain conditional probability.
For example, in the previous example illustrated in
Figure 2, if the vulnerability on Master is patched, we
need not generate a new attack graph, but set the con-
ducting probability of a1 and a2 to 0.0.
On this basis, we introduce a security enhancement
measure tuple

,,M

 :


1,,
K
M
mm is a candidate measure set.
 :22
M


 is a function which maps a combina-
tion of measures to a rectified attack graph prob-
ability distribution


0
,,,,  .
 :2
MR


 is a function which maps a combina-
tion of measures to its implementation cost.
With the above security measure tuple, we can per-
form the following analysis:
1) Static Security Enhancement. This analysis is to
find the best combination of security measures to be im-
plemented before any potential intrusion happens. A ty-
pical usage of this analysis is to enhance a network sys-
tem before it is placed online. To achieve this, all candi-
date measure combinations need to be iterated. For each
measure combination 2
M
C
M, we set the probability
distribution to

C
M 

 and recompute the network
normalized asset residual value 0

. Then the net profit
of C
M
is:



00CC
uMOverallAsset ValueM  
  ,
where 0

is the normalized asset residual value when
no security measure is implemented (C M). Finally,
by sorting these measure combinations according to their
net profits, we can easily choose the greatest one as the
optimal enhancement solution.
2) Dynamic Security Enhancement. This analysis is
to find the best measure combination when intrusion is
happening (or has happened). To achieve this, we firstly
need to use the previous inference algorithm to generate
a set ΞT of transientized attack samples. Then we iterate
all of the candidate measure combinations. For each
combination 2
M
C
M, we rectify the graph probability
distribution to


C
M 

 . After doing this, we re-
sample (a process same to line 11~23 of the Improved
LikelihoodWeighting algorithm) ΞT according to the
new distribution and get a new set ΞS which will be actu-
ally used to compute the network normalized asset re-
sidual value S


. Then the net profit of C
M
is:






CSS C
uMOverallAsset ValueM  

 ,
where S

is a normalized asset residual value when no
measure is implemented (C M). Finally, by sorting
these measure combinations according to their net profits,
we can easily choose the greatest one as the optimal en-
hancement solution.
7. Assessment & Enhancement Examples
To exemplify the above security assessment and enhan-
cement method, in one experiment we generated an at-
tack graph for a two tier network system. Based on it, we
performed corresponding security assessment and used
our enhancement method to find out optimal security en-
hancement measure combinations for static and dynamic
security enhancement respectively.
7.1. Basic Posterior Inference
Figure 8 illustrates the topology of the two tier network.
In this network, four intranet servers were connected to a
switch which was further connected to the Internet by a
router. A firewall was placed between the two devices to
perform package filtering, besides an IDS was connected
to a mirror port of the switch to monitor the outflow and
inflow of the servers.
We assumed a scenario that an attacker on the Internet
intends to use her personal computer to attack this net-
work. The final goal of the attacker was to get the ROOT
privilege on server3 and steal its business data.
For further analysis, we firstly need to generate a net-
work attack graph to find out all the potential intrusion
paths. So we scanned the online devices and servers and
found out six vulnerabilities (listed in Table 8). Addi-

S. J. ZHANG ET AL.
18
Figure 8. A two tier network system.
Table 8. Host vulnerabilities.
device OS application vulnerabilities
server1 windows nt 4.0 serv-u ftp 3.0 cve-2004-0330
cve-2004-1992
server2 windows 2000 - cve-2003-0533
server3 redhat linux 7.3 oracle 9i
cvs 1.11
cve-2004-0417
cve-2004-0415
server4 redhat linux 7.3 apache 1.3.23 cve-2002-0392
tionally, we found that the firewall is configured to per-
mit and only permit the Internet user to access intranet
servers through HTTP protocol.
By importing these information into a network attack
graph building system developed by us (design concept
of this system mainly follows the framework proposed in
[16]), we get a network attack graph shown in Figure 9.
In Figure 9, resource state nodes are represented in
circles while action nodes are represented in rectangles.
The top row in the figure (11 resource state nodes) inclu-
des the 6 vulnerabilities on the servers and the 5 low lev-
el privileges which can be used by anyone to access the
servers. However, owes to the firewall, initially the atta-
cker can only access server4’s HTTP service and exploit
the apache vulnerability (this exploitation is represented
in the figure with the action node right below the top re-
source state node row). After that, the attacker may get
the USER privilege of server4 and use this server as a
stepping stone to perform further intrusion (mainly by
exploiting the rest vulnerabilities listed in Table 8). Ac-
cording to Figure 9, to the maximum extent, the attacker
can get the USER privilege of server1, server3 and serv-
er4 as well as the ROOT privilege of server2 and server3
(represented by the other 5 circles in the figure exclude
the top row).
Then we should assigned conditional probability dis-
tributions to the generated graph. In this stage, we mainly
used data sources such as CVSS [17] and OSVBD [18]
complemented with expertise knowledge. For example,
in CVSS, a score metric named Exploitability are defined
to indicate the difficulty for an attacker to exploit vul-
nerability. So we decide to use this metric to evaluate the
success rate of an action by the following transformation:

 of
1.0
E
xploitability a
ae 


With all prior conditional probability distributions as-
signed, we were able to perform posterior inference ac-
cording to observed intrusion evidence. As an example
for exemplification, we assumed that an IDS alert se-
quence is observed as in Table 9:
By running the improved likelihood weighting algo-
rithm, we computed node belief values for each inference
layer. Due to space limitation, detailed result is not given
out here. But in Annex B this security evolvement proce-
dure is illustrated graphically. In each figure of the annex,
a darker node is used to represent a greater node belief
value. We see that with more evidence observed, belief
values of some graph nodes increase rapidly, indicating
intrution paths that are most probably chosen.
7.2. Security Assessment
Since our aim is to assess security level of the network
and find out an optimal enhancement solution, we sele-
cted 5 important service assets from the network system
whose CIA values are listed in Table 10 (in thousands
$US). Correspondingly, we introduced into the attack
graph 15 corresponding asset breakage nodes.
Meanwhile, we quantified the asset breakage conduc-
tivity rate between these 15 nodes and the aforemen-
tioned 5 resource state nodes which represent the esca-
lated privileges that may be gained by the attacker. The
conductivity rates between them are listed in Table 11.
Table 9. Observed alerts.
id exploited vulnerability source target
1 cve-2002-0392 pc server4
2 cve-2003-0533 server4 server2
3 cve-2004-0417 server3 server3
Table 10. Important assets and their CIA values.
id asset host λ(ρC) λ(ρI) λ(ρA)
1 ftp server1 1 1 1
2 file server2 50 50 50
3 database server3 100 100 50
4 cvs server4 10 10 10
5 apache server4 0 10 10

S. J. ZHANG ET AL.
19
Figure 9. Attack graph of the network.
Table 11. Asset breakage conductivity r a te .
ρC1 ρC2 ρC3 ρC4 ρC5
ρI1 ρI2 ρI3 ρI4 ρI5 escalated privilege
ρA1 ρA2 ρA3 ρA4 ρA5
0.00 0.00 0.00 0.00 1.00
0.00 0.00 0.00 0.00 0.80 USER on server4
0.00 0.00 0.00 0.00 0.50
0.00 0.90 0.00 0.00 0.00
0.00 0.90 0.00 0.00 0.00 ROOT on server2
0.00 0.50 0.00 0.00 0.00
1.00 0.00 0.00 0.00 0.00
0.80 0.00 0.00 0.00 0.00
USER on server1
0.50 0.00 0.00 0.00 0.00
0.00 0.00 0.00 1.00 0.00
0.00 0.00 0.00 0.80 0.00
USER on server3
0.00 0.00 0.00 0.50 0.00
0.00 0.00 1.00 1.00 0.00
0.00 0.00 0.80 0.80 0.00 ROOT on server3
0.00 0.00 0.50 0.50 0.00
After doing this, we recomputed the node belief values
for each inference layer and get 2 normalized asset re-
sidual value sequences 0123

 listed in Table 12 and
Table 13 (without and with transientization respectively).
These sequences are graphically illustrated in Figure 10
to reveal the evolvement of network security. In the fig-
ure we can observe that the asset residual values gener-
ated with transientization are always greater than the
ones without transientization. This is reasonable since
with all condition unchanged, the current security level
of a network is always higher than its futu re security
level, because from current timepoint to the future the
attacker gets additional time to perform more intrusion.
7.3. Security Enhanceme nt
Then, for enhancement, we analyzed the network system
and listed 11 plainest security measures as candidates in
Table 14. These measures include patching the vulner-
abilities on the servers and disabling low level privilege
accounts on them. Additionally, we identified a measure
of configuring the firewall to deny all incoming access
including HTTP. Costs of these security measures were
also analyzed and listed in the table (in thousands $US).
By using the security enhancement methods proposed
in Section 6, we eventually got all the net profit of the
security measure combinations. In Table 15 we list the

S. J. ZHANG ET AL.
20
Figure 10. Evolvement of network security.
Table 12. Assessment result (without transientization).
i 0 1 2 3
Σλ(ρ) 453.000 453.000 453.000 453.000
Σρλ(ρ) 66.472 92.342 161.153 192.790
Σ(1 – ρ)λ(ρ) 386.528 360.658 291.847 260.210
τi 85.33% 79.62% 64.43% 57.44%
Table 13. Assessment result (with transientization).
i 0 1 2 3
Σλ(ρ) 453.000 453.000 453.000 453.000
Σρλ(ρ) 0.909 13.548 91.443 173.655
Σ(1 – ρ)λ(ρ) 452.091 439.452 361.557 279.345
τi 99.80% 97.01% 79.81% 61.67%
top 5 best security enhancement measure combinations
for static security enhancement (SSE) and in Table 16
we list the top 3 best combinations (of each inference
layer) for dynamic security enhancement (DSE).
8. Conclusions
As network attack graphs are more and more widely
used in real-time network security analysis, the problem
of how to use observed intrusion evidence to compute
attack graph node belief becomes a concerned issue. Al-
though Bayesian network is an ideal mathematic tool for
posterior inference, it can not be directly used in attack
graph-based inference for the following limitations: 1)
There may exist directed cycles in an attack graph, but in
a Bayesian network this is not permitted. 2) There are
Table 14. Candidate security measures.
id security measure cost
1 patch CVE-2004-0330 on server1 0.1
2 patch CVE-2004-1992 on server1 0.1
3 patch CVE-2003-0533 on server2 5.0
4 patch CVE-2004-0417 on server3 5.0
5 patch CVE-2004-0415 on server3 1.0
6 patch CVE-2002-0392 on server4 1.0
7 disable GUEST account on server1 1.0
8 disable GUEST account on server2 50.0
9 disable GUEST account on server3 60.0
10 disable GUEST account on server4 10.0
11 add HTTP filtering rule on firewall 10.0
Table 15. Top 5 best combinations for SSE.
id combination cost net gain
1 {6} 1.0 65.14
2 {1, 6} 1.1 65.04
3 {2, 6} 1.1 65.04
4 {1, 2, 6} 1.2 64.94
5 {5, 6} 2.0 64.14
Table 16. Top 3 best combinations for DSE.
layer id combination cost net gain
1 {1, 2, 6, 7} 2.2 40.87
2 {1, 2, 6} 1.2 40.77 0
3 {1, 2, 5, 6} 2.2 40.67
1 {1, 2, 3, 4} 10.2 55.20
2 {2, 3, 4} 10.1 54.86 1
3 {3, 5, 7} 7.0 54.70
1 {1, 2, 4, 6} 6.2 51.23
2 {1, 2, 4} 5.2 51.23 2
3 {1, 2, 4, 5} 6.2 50.73
1 {1, 2, 5} 1.2 11.41
2 {1, 2, 5, 6} 2.2 11.01 3
3 {1, 2, 4} 5.2 10.21

S. J. ZHANG ET AL.
21
temporal partial ordering relations among intrusion evi-
dence, but we can not use a Bayesian network to model
this information. 3) A Bayesian network cannot be direc-
tly used to infer both the current and the future security
state of a network. In this work, we resolve these critical
problems by developing an approximate Bayesian infer-
ence algorithm—the likelihood weighting algorithm. We
give out all the pseudocodes of the algorithm and use se-
veral examples to show its advantage. Essentially, we be-
lieve this algorithm is not only limited in attack graph-
based analysis, but also can be applied in other techni-
ques employing traditional Bayesian posterior inference.
Based on the algorithm and its underlying model, we
further propose a novel network security assessment and
enhancement method. In this paper, we use a small net-
work system to exemplify how to use this method to
quantify the overall network security level and make de-
cisions about what security measures are most cost- ef-
fective for network security enhancement.
9. Acknowledgements
This work was supported in part by the National Natural
Science Foundation of China under Grant Nos.60605019;
the National High-Tech Research and Development Plan
under Grant Nos.2007AA01Z473; the National Research
Foundation for the Doctoral Program of Higher Educa-
tion of China under Grant No.20070248002.
The authors would also like to thank all the members
of Shanghai Key Laboratory for Information Security
Integrated Management Technology Research.
If anyone is interested in the algorithms of this article,
please feel free to contact leony7888@hotmail to get the
java source codes.
10. References
[1] O. Sheyner, J. Haines, S. Jha, et al., “Automated Genera-
tion and Analysis of Attack Graphs,” Proceedings of the
2002 IEEE Symposium on Security and Privacy, Oakland,
12-15 May 2002, pp. 273-284. doi:10.1109/SECPRI.2002.
1004377
[2] S. Jajodia, S. Noel and B. O’Berry, “Topological Analy-
sis of Network Attack Vulnerability,” Managing Cyber
Threats: Issues, Approaches and Challenges, Kluwer
Academic Publisher, 2004.
[3] P. Ammann, D. Wijesekera and S. Kaushik, “Scalable,
Graph-Based Network Vulnerability Analysis,” Procee-
dings of the 9th ACM Conference on Computer & Com-
munications Security, Washington DC, 2002, pp. 217-224.
[4] X. Ou, S. Govindavajhala and A. Appel, “MulVAL: A
Logic-Based Network Security Analyzer,” Proceedings
of the 14th conference on USENIX Security Symposium,
Baltimore, 31 July-5 August 2005, pp. 8-23.
[5] R. Lippmann, K. Ingols, C. Scott, et al., “Validating and
Restoring Defense in Depth Using Attack Graphs,” Pro-
ceedings of the 2007 IEEE Military Communications
Conference, Washington DC, 2006.
[6] P. Ning and D. Xu, “Learning Attack Strategies from
Intrusion Alerts,” Proceedings of the 10th ACM Confer-
ence on Computer and Communications Security, Wash-
ington DC, October 2003.
[7] S. Noel, E. Robertson and S. Jajodia, “Correlating Intru-
sion Events and Building Attack Scenarios through At-
tack Graph Distances,” Proceedings of the 20th Annual
Computer Security Applications Conference, Tucson,
December 2004, pp. 350-359. doi:10.1109/SECPRI.2002.
1004377
[8] L. Wang, A. Liu and S. Jajodia, “Using Attack Graphs for
Correlating, Hypothesizing, and Predicting Intrusion
Alerts,” Computer Communications, Vol. 29, No. 15,
2006, pp. 2917-2933. doi:10.1016/j.comcom.2006.04.001
[9] Y. Zhai, P. Ning, P. Iyer, et al., “Reasoning about Com-
plementary Intrusion Evidence,” Proceedings of the 20th
Annual Computer Security Applications Conference,
Tucson, 6-10 December 2004, pp. 39-48. doi:10.1109/
CSAC.2004.29
[10] D. Yu and D. Frincke, “Improving the Quality of Alerts
and Predicting Intruder’s Next Goal with Hidden Colored
Petri-Net,” Computer Networks, Vol. 51, No. 3, 2007, p.
632. doi:10.1016/j.comnet.2006.05.008
[11] S. Zhang, L. Li, J. Li, et al., “Using Attack Graphs and
Intrusion Evidences to Extrapolate Network Security
State,” Proceedings of the 4th International Conference
on Communications and Networking in China, Guang
Zhou, 2009. doi:10.1109/CHINACOM.2009.5339841
[12] Z. Bhahramani, “An Introduction to Hidden Markov
Models and Bayesian Networks,” International Journal
of Pattern Recognition and Artificial Intelligence, Vol. 15,
No. 1, 2001, pp. 9-42. doi:10.1142/S0218001401000836
[13] F. Salfner, “Modeling Event-driven Time Series with
Generalized Hidden Semi-Markov Models,” Technical
Report 208, Department of Computer Science, Humboldt
University, Berlin, Germany, 2006.
[14] F. Jensen, “Bayesian Networks and Decision Graphs,”
Statistics for Engineering and Information Science,
Springer, 2001.
[15] K. Korb and A. Nicholson, “Bayesian Artificial Intelli-
gence,” CRC Press, 2003. doi:10.1201/9780203491294
[16] S. Zhang, J. Li and X. Chen, “Building Network Attack
Graph for Aalert Causal Correlation,” Computers & Se-
curity, Vol. 27, No. 5-6, 2008, pp. 188-196. doi:10.1016/
j.cose.2008.05.005
[17] “National Institute of Standards and Technology,” 2010.
Common Vulnerability Scoring System.
http://nvd.nist.gov/cvss.cfm
[18] “Open Security Foundation,” 2010. OSVDB: The Open
Source Vulnerability Database. http://osvdb.org/

S. J. ZHANG ET AL.
22
Annex A: Pseudocode of Subfunctions
SF1. UpdateAttackGraph—called in ImprovedLike-
lihood Weighting
SF2. IsCriticalCausation—called in UpdateAttack-
Graph and later SFs
SF3. SelectEvidenceCausation—called in Improved-
LikelihoodWeighting
UpdateAttackGraph(AG,X,Y)
Input: AG—an attack sample
X—an ancestor node Y—a descendant node
Output: a boolean variable indicating if AG is updated
Alg: 01: updated←False;
02: if (Y cand not sampled) then
03: if (for each node X’ in Pre(Y) variable X’=True) then
04: if (for each node X’ in Pre(Y)
IsCriticalCausation(AG,Y,X’,Ø)=False) then
05: Y←the sampling result according to 1()Y

;
07: if (Y=True) then
08: for (each node X’ in Pre(Y))
09: FX←FX∪{Y};
10: BY←BY∪{X};
11: end for (08)
12: updated←True;
13: for (each node Z in Con(Y))
14: if (edge Y→Z is not sampled) then
15: UpdateAttackGraph (AG,Y,Z);
16: end if (14)
17: end for (13)
18: end if (07)
19: mark Y as sampled;
20: for (each node X’ in Pre(Y))
21: mark edge X’→Y as sampled;
22: end for (20)
23: end if (04)
24: end if (03)
25: end if (02)
26: if (Y is other type node) then
27: if (!IsCriticalCausation(AG,Y,X,Ø)) then
28: Yold←Y;
29: y←sampling result by (,)
X
Y

or (,)
X
Y

;
30: if (y=True) then
31: Y←True;
32: FX←FX∪{Y};
33: BY←BY∪{X};
34: updated←True;
35: if (Yold=False) then
36: for (each node Z in Con(Y))
37: if (edge Y→Z is not sampled) then
38: UpdateAttackGraph(AG,Y,Z);
39: end if (37)
40: end for (36)
41: end if (35)
42: end if (30)
43: mark edge X→Y as sampled;
44: end if (27)
45: end if (26)
46: return updated;
IsCriticalCausation(AG,X,Y,H)
Input: AG—an attack sample
X—a candidate causation node
Y—a candidate affection node
H—a set to hold historically processed nodes
Output: a boolean variable indicating if X is a critical causation of Y
Alg: 01: if (Y is an action node) then
02: if (Y∈H ∨BY=Ø) then
03: r←False;
04: end if (02)
05: if (X∈BY (∨for each node Z in BY,
IsCriticalCausation(AG,X,Z, H∪{Y})=True)) then
06: r←True;
07: else (05)
08: r←False;
09: end if (05)
10: end if (01)
11: if (Y is other type node) then
12: if (Y∈H或BY=Ø) then
13: r←False;
14: end if (12)
15: if ({X}=BY (∨for each node Z in BY,
IsCriticalCausation(AG,X,Z, H∪{Y})=True)) then
16: r←True;
17: else (15)
18: r←False;
19: end if (15)
20: end if (11)
21: return r;
SelectEvidenceCausation(AG,X)
Input: AG — a network attack graph
X — an observed evidence node (whose value is True)
Output: the occurrence probability of the chosen causation set
Alg: 01: pΣ←0;
02: Φ←Ø; Ψ←{Y|Y∈Pre(X)∧Y=True};
03: for (each non-emtpy subset ψ of Ψ)
04: pψ←∏Y∈ψθ(Y,X) * ∏Y(∈Ψ-ψ)(1-θ(Y,X));
05: Φ←Φ{(∪ψ, pψ)};

S. J. ZHANG ET AL.
23
SF4. Transientize—called in ImprovedLikelihood-
Weighting
SF5. PartialRelationSatisfied—called in Improved-
LikelihoodWeighting
06: pΣ←pΣ+pψ;
07: end for (03)
08: for (each pair (ψ, pψ) in Φ)
09: pψ←pψ / pΣ;
10: end for (08)
11: (ψr, pψr)←chose a pair in Φ according to pψ of the pair;
12: for (each node Z in ψ)
13: FZ←FZ∪{X};
14: BX←BX∪{Z};
15: end for (12)
16: return pψr*pΣ;
Transientize(AG,OD,OF)
Input: AG—an attack sample OD—a set of observed evidence nodes
OF—a set of not yet observed evidence nodes
Output: a boolean indicating AG’s effectiveness after transientization
Alg: 01: for (each node X in OF)
02: for (each action node Y in BX)
03: Y←False;
04: mark edge Y→X as not sampled;
05: BX←BX -{Y}; FY←FY -{X};
06: if (Y is an action node) then
07: mark Y as not sampled;
08: end if (06)
09: for (each node Z in BY)
10: mark edge Z→Y as not sampled;
11: BY←BY -{Z}; FZ←FZ -{Y};
12: end for (09)
13: end for (02)
14: end for (01)
15: converged←False;
16: while (!converged)
17: converged←True;
18: for (each non-root node in AG)
19: if (X is an action node) then
20: if (X is sampled(some node in ∧BX is False∨
X is the critical causation of some node in BX)) the n
21: X←False;
22: mark X as not sampled;
23: for (each node Y in BX)
24: mark edge Y→X as not sampled;
25: BX←BX -{Y}; FY←FY -{X};
26: end for (23)
27: converged←False;
28: end if (20)
29: else (19)
30: for (each node Y in BX)
31: if (Y=False∨IsCriticalCausa tion(AG,X,Y,Ø)) then
32: mark edge Y→X as not sampled;
33: BX←BX -{Y}; FY←FY -{X};
PartialRelationSatisfied (AG,O,Ω)
Input: AG—an attack sample
O—the evidence set of AG
Ω—a temporal partial ordering relation set on O
Output: a boolean indicating if AG conforms to Ω (and is effective)
Alg: 01: typeI_satisfied←True; typeII_satisfied←True;
02: for (each type I partial ordering relation Om↗On in Ω)
03: pairSatisfied←False;
04: for (each node Ai in BOm)
05: existJCoversI←False;
06: for (each node Aj in BOn)
07: if (IsCriticalCausation(AG,Aj,Ai,Ø)) then
08: existJCoversI←True;
09: end if (07)
10: end for (06)
11: if (!existJCoversI) then
12: pairSatisfied←True;
13: end if (11)
14: end for (04)
15: if (!pairSatisfied) then
16: typeI_satisfied←False;
17: end if (15)
18: end for (02)
19: for (each type II partial ordering relation Om↘On in Ω)
20: for (each node Ai in BOm)
21: for (each node Aj in BOn)
22: if (IsCriticalCausation(AG,Aj,Ai,Ø))
23: typeII_satisfied←False;
24: end if (22)
25: end for (21)
26: end for (20)
27: end for (19)
28: return typeI_satisfied ∧ typeII_satisfied;
34: end if (31)
35: end for (30)
36: if (BX = Ø) then
37: if (X∈OD) then
38: return False;
39: else (37)
40: X←False;
41: converged←False;
42: end if (37)
43: end if (36)
44: end if (19)
45: end for (18)
46: end while (16)
47: return True;

S. J. ZHANG ET AL.
24
Annex B: Graph Node Belief Evolvement
Without Sample Transientization
Figure 1. Layer 0-no alert is observed.
Figure 2. Layer 1–one alert is observed.

S. J. ZHANG ET AL.
25
Figure 3. Layer 2–two alerts is observed.
Figure 4. Layer 3-three alerts is observed.

S. J. ZHANG ET AL.
26
With Sample Transientization
Figure 1. Layer 0-no alert is observed.
Figure 2. Layer 1–one alert is observed.

S. J. ZHANG ET AL.
27
Figure 3. Layer 2–two alerts is observed.
Figure 4. Layer 3–three alerts is observed.