Information Technology Reference
In-Depth Information
Ψ
3
([
x
]
,
[
y
]) := (
ts
([
x
])
<ts
([
y
]))
∧
(
∃
P
∈
PAG
:
∃
v, w
:
(
v
∈
maps
i
(
x
)
∧
w
∈
maps
i
(
y
)
∧
in
(
v, P
)
∧
in
(
w, P
)))
(15)
The dependency graph
DG
is defined by the matched and aggregated alerts
A
m
as
vertices and the relations between these alerts as edges
E
m,k
. There are three possible
ways to define these relations using
Psi
k
.
Psi
1
defines two alerts as related, if they are
mapped to neighboring vertices in
AG
.
Psi
2
defines two alerts as related, if they are
mapped to two vertices in
AG
that are connected by the path
P
with the length of
n
.
Psi
3
defines two alerts as related, if they are mapped to two vertices in
AG
that are part
ofthesamepath
P
.
3.5
Searching
Each path in the alert dependency graph
DG
identifies a subset of alerts that might be
part of an attack scenario.
DG
is used in the last step to determine the most interesting
subsets of alerts, respectively the most interesting path in the alert dependency graph.
The last step of searching alert subsets is done by performing a Floyd Warshall algo-
rithm [24,25] to find all the shortest paths. Furthermore, the diameter
dia
(i.e. the value
of the longest instance of the shortest paths) is determined and each path
DP
i
that has
the length
ord
(
DP
)=
dia
is converted in subsets of alerts. All the subsets
S
x
are
defined as:
S
x
=
{
a
∈
A
|
in
(
a, DP
i
)
}
(16)
With a simple optimization, the algorithm allows to identify multiple different attack
scenarios of the same anatomy. By sorting the suspicious alert subsets according to the
smallest difference between alert
a
1
and
a
n
, the algorithm will identify the alerts that are
near each other on the time-line as related to one attack scenario. Let
as
1
=
{
a
1
, ..., a
n
}
and
as
2
=
{
b
1
, ..., b
n
}
be two alert sets where the only difference between
a
i
and
b
i
is
the times-tamp
ts
(
a
i
)
=
ts
(
b
i
)
. There are three different combinations how these alerts
can be located on a time-line:
1.
as
1
and
as
2
are not overlapping at all, i.e.,
ts
(
a
n
)
<ts
(
b
1
)
2.
as
1
=
{
a
1
,a
2
, ..., a
k
, ...a
n
}
and
as
2
=
{
b
1
, ..., b
n
}
are partially overlapping, i.e.,
∃
k
∈
∀
a
i∈{
1
,k}
|
ts
(
a
k
)
>ts
(
b
1
)
3.
as
2
is completely overlapped by
as
2
, i.e.,
(
ts
(
a
1
)
<ts
(
b
1
))
∧
(
ts
(
a
n
)
>
ts
(
b
n
))
The modified algorithm can identify both suspicious alert sets in case 1, which is im-
possible for the algorithm in [5]. Due to the memory limitation, this algorithm only
considers the last matching alert for each node in the AG.
Search WWH ::
Custom Search