Information Technology Reference
In-Depth Information
(e.g., network topology, software versions, etc.) as well as attacker capabilities
(e.g., sniffed passwords, access to user or root-level shells, etc.). State transitions
represent actions that modify computer network configurations (e.g., changing
firewall rules) and attacker capabilities (e.g., exploits of vulnerabilities). The
initial state of the transition system represents the capabilities of a specific ad-
versary, e.g., an adversary with root access on a networked computer that is
external to the networked system under consideration. The goal states of the
transition system represent compromised states, e.g., states where the adversary
has root privileges on critical servers.
2.1 Model
Formally, a
state transition system
is a tuple
T
=(
S, τ, s
0
,S
G
)where
S
is a set
of states,
τ ⊆ S × S
is a state transition relation,
s
0
∈ S
is a start state, and
S
G
⊆ S
is a set of goal states. A system
T
=(
S
,τ
,s
0
,S
G
)isa
subsystem
of
system
T
=(
S, τ, s
0
,S
G
)if
S
⊆ S
,
τ
⊆ τ
,
s
0
=
s
0
,and
S
G
⊆ S
G
.Wewrite
T
≤ T
to denote that
T
is a subsystem of
T
.
A state
s
n
∈
S
is
reachable
from state
s
0
∈
S
if there exist states
s
1
,...,s
n−
1
1. A
vulnerable
state
is a state from which some goal state is reachable. A
successful attack path
is a sequence of state transitions that takes a transition system from its initial
state to a goal state. We are interested in attack graphs which represent all the
successful attack paths in a system.
∈
S
such that (
s
i
,s
i
+1
)
∈
τ
for 0
≤
i
≤
n −
and
T
=
S
,τ
,s
0
,S
G
Definition 1.
Let
T
=
be state transition
systems. Then,
T
is cal led an
attack graph of
T
if
T
≤ T
and if all states in
S
are both vulnerable and reachable from
s
0
in
T
.
Definition 2.
G
is cal led the
greatest attack graph
of a state transition system
T
=(
S, τ, s
0
,S
G
)
if
G
is an attack graph of
T
and if for all attack graphs
G
of
T
,
G
≤ G
.
S, τ, s
0
,S
G
Proposition 1.
Every state transition system has a greatest attack graph.
We define topological vulnerability analysis to be the construction and anal-
ysis of greatest attack graphs. In this paper, we focus on the construction of
the graphs and present ecient algorithms that map state transition systems to
their greatest attack graphs.
2.2 States
A state represents a computer network configuration and attacker capabilities.
A state is defined to be a set of ground predicates (called
attributes
). Let
K
be
a finite set of individual constants and
P
be a finite set of predicate symbols.
Each predicate has an assigned arity
≥
1. Then the (finite) set of all atoms,
G
,
is defined as follows: all constants in
K
are in
G
;further,if
p ∈P
has arity
n
and if
k
1
,...,k
n
∈K
then
p
(
k
1
,...,k
n
)
∈G
. Finally, the set of all attributes is
and the set of all states is
S
=2
A
.
A⊆G
