Information Technology Reference
In-Depth Information
an algorithm (
TVA()
) that returns a successful attack path if one exists.
TVA
takes a partial reverse attack path
σ
as an argument, together with
∆
and
∆
.It
also takes a fourth argument
as
which is the set of attributes that were deleted
by the last rule that was applied thus far.
TVA
first applies
findMaximal
to
extend the attack path since noninterfering rules can be applied in any order
as shown earlier. If the path is successful, it returns the path. Otherwise it
tries to recover the attributes in
as
. We have not included the pseudo-code for
recoverAttributes
. However, when an attribute is first acquired, we mark the
attribute with the attack path that causes it to be acquired. Then, to recover an
attribute,
recoverAttributes
reapplies the rules in the stored attack path. Having
done this,
TVA
then tries completing the attack path. If it fails, it backtracks
andthentrieseachrulein
∆ − ∆
in turn; after applying each rule, it recurses
to repeat the above process.
We observe that in practice, most attributes that are lost due to some exploit
(e.g., as in the buffer overflow examples) can be immediately recovered without
impacting the attacker's ability to reach a goal state. In this case, the algorithm
does not backtrack and remains ecient. Thus, the algorithm backtracks only
in the unusual event that the lost attributes must be recovered in a delayed
manner. Figure 6 shows a graphical representation of
TVA()
algorithm.
4.3 Example 3
The BIND and SSHd buffer overflow exploits described in Example 1 exhibit the
property of privilege loss: they provide an attacker with a root shell on the target
machine but terminate the BIND or SSHd service. Since the attacker has root
level privilege in the shell, the attacker is able to restart the previously crashed
BIND or SSHd service.
We can represent the transition rules for restarting the BIND and SSHd
daemons on host
V
for an attacker
A
as follows. Let
δ
6
be the transition rule for
restarting the SSHd daemon. Then,
a
1
δ
6
c
1
where:
a
1
=
sh(A, root, V)
and
c
1
=
service(SSHd, 22,
l
1
,V)
. Similarly, we can
write the transition rule for restarting the BIND daemon.
5 Related Work
Dacier et al. [4,5] and Ortalo et al. [8] represent the vulnerabilities in a system
by means of a privilege graph where nodes are sets of privileges owned by users
and edges represent vulnerabilities. Our attack graph representation is motivated
by their work. However, while they focus on security metrics that are based on
privilege graphs, we focus on the ecient construction of greatest attack graphs.
Templeton and Levitt [18] proposed a “requires/provides” model that models
attacks in terms of their preconditions and postconditions (expressed as pred-
icates over capabilities). The models presented in [1,7,14,13,15,6] all model at-
