Information Technology Reference
In-Depth Information
that require the absence of some attributes and that cause the absence of other
attributes.
In order to see why monotonic rules are inadequate for some real-world situ-
ations, consider that a buffer overflow attack typically results in the termination
of the attacked service. Further, it may also cause the victim host to crash or
halt. An attacker may use this to disable a host while he hijacks a connection it
had with another host. However, in doing this, the attacker may lose access to
the host and may no longer benefit from trust relationships (e.g., as represented
in .rhosts files) that the host has with other hosts. Thus, in this example, the
attacker must execute actions in a specific order so as to achieve his goal. In a
more complex situation, the constraints may be such that an attacker cannot
succeed since exploits invalidate each other.
Such situations may be represented directly using nonmonotonic rules. Some
researchers have suggested that such situations may also be captured by the
careful design of monotonic rules. One approach is to ignore some constraints
while modeling or analyzing the system. The monotonic approximation that we
present in Section 4.1 is an example of this approach. However, as we will show,
this approach yields attack paths that are not available in practice due to order-
ing constraints on individual exploits. Another approach is to carefully design
attributes and rules so that all constraints are captured by monotonic rules.
However, this is as hard as doing the nonmonotonic analysis since the system
modeler must determine the consequences of all nonmonotonic constraints while
modeling the system. In fact, this is quite undesirable both since it is unnatural
and since it shifts the burden from the computational analysis to the human
modeler.
While nonmonotonic rulesets capture real-world constraints directly, they
also introduce two problems. First, rules must be invoked in a specific order
and hence searching for a path may involve backtracking. Second, a successful
attack path may take the system through all (or a large number of states) before
reaching a goal state. Hence, the length of attack paths is bounded by the number
of states
2
A
|
|
(as opposed to the number of attributes
|A|
for monotonic rulesets).
4.1 Monotonic Approximation
Let
∆
be a set of transition rules. Let
∆
be a set of monotonic transition rules
such that
δ
(
A, ∅,C,∅
∈ ∆
if and only if
δ
(
A, B, C, D
)
.
We call
∆
the
monotonic approximation
of
∆
, and we call rule-system
T
=
(
)
∈ ∆
for some
B, D ⊆A
A,∆
,s
0
,S
G
)the
monotonic approximation
of rule-system
T
=(
A,∆,s
0
,S
G
).
A key observation is that an adversary can reach a goal state in a rule-
system
T
only if he can reach a goal state in the monotonic approximation of
T
.
That is, a system is vulnerable to attacks only if its monotonic approximation
is vulnerable.
Proposition 5.
Let
T
=(
A,∆,s
0
,S
G
)
be a state transition rule-system and let
T
=(
A,∆
,s
0
,S
G
)
be the monotonic approximation of
T
. For each goal state
that is reachable from
s
0
in
T
, there exists a goal state
s
g
∈ S
G
s
g
∈ S
G
such
that
s
g
⊆ s
g
and
s
g
is reachable from
s
0
in
T
.
