Transcript Detection and Identification of Network Anomalies Using

Detection and
Identification of Network
Anomalies Using Sketch
Subspaces
Xin Li, Fang Bian, Mark Crovella,
Christophe Diot, Ramesh
Govindan, Gianluca Iannaccone,
and Anukool Lakhina
Speaker: Chang Huan Wu
2009/5/1
ACM Internet Measurement Conference
2006
Outline
 Introduction
 Previous Approach
 Defeat
 Evaluation
 Conclusions
2
Introduction (1/3)
 Unusual
traffic patterns arise from
network abuse as well as from
legitimate activity
 These traffic anomalies are often
difficult to detect at a single link
and require scrutiny of the entire
network
3
Introduction (2/3)
 Characterizing
“normal” traffic
using IP flows representation is
intractable
–
High dimension
 Reduce
dimension and identify
anomalies
4
Introduction (2/3)


5
Previous work aggregate
netflow into origindestination (OD) flows
Modify this approach and
increases the detection
rate while reducing false
alarms and identify the IPflows responsible for the
anomaly
Points of Presence, PoP
Link
Previous Approach

6
Reference: Anukool Lakhina, Mark
Crovella, Christophe Diot, "Mining
Anomalies Using Traffic Feature
Distributions," In ACM SIGCOMM 2005
Volume vs.
Traffic Feature Distribution

Volume based detection schemes have been
successful in isolating large traffic changes
–

Using traffic feature distribution
–
–
7
But a large of anomalies do NOT cause
detectable disruptions in traffic volume
Augments volume-based anomaly detection
Traffic distributions can reveal valuable
information about the structure of anomalies
Port scan anomalies viewed in terms of
traffic volume and in terms of entropy
Port scan dwarfed
in volume metrics…
But stands out in
feature entropy
8
Traffic Feature Distributions

Anomalies can be detected and
distinguished by inspecting traffic features:
–
9
4-tuple: SrcIP, SrcPort, DstIP, DstPort
Entropy based scheme



In volume based scheme, # of packets or bytes per
time slot was the variable.
In entropy based scheme, in every time slot, the
entropy of every traffic feature is the variable.
This gives us a three way data
matrix H.
–

H(t, p, k) denotes at time t, the
entropy of OD flow p, of the traffic
feature k.
To apply subspace method,
we need to unfold it into a
single-way representation.
Subspace Decomposition



11
Normal subspace, : first k principal
components
Anomalous subspace, : remaining
principal components
Then, decompose traffic on all links by
projecting onto
and
to obtain:
Traffic vector at a
particular
point in time
Normal traffic
vector
Residual traffic
vector
11
Geometric illustration
Traffic on link 2
In general,
anomalous traffic
results in a large
value of
y
Use
to identify
if it is anomalous
Traffic on link 1
12
12
Multiway Subspace Method:
H(dstPort)
H(dstIP)
H(srcPort)
H(srcIP)
# timebins
(Multi-way to single-way)
pe
ty
s
H(SrcIP)
H(SrcPort)
H(DstIP) H(DstPort)
# od-pairs


Decompose into a single-way matrix
Now apply the usual subspace decomposition
(PCA)
–
Every row of the matrix will be decomposed into
Defeat (1/2)
R1, SrcIP
h1
s buckets
R2, SrcIP
h1
h3
h3
h4
h4
h5
h5


14
…
R2 h1 s buckets
t2 Entropy of h1
…
h2
R1 h1 s buckets
…
h2
s buckets
t1 Entropy of h
1
tn Entropy of h1
Entropy of h1
Use random aggregations of IP flows
(sketches)
Put an IP flow into different hash functions
(h1, h2…)
Defeat (2/2)
SrcIP
SrcPort
DstIP
DstPort
t1 Entropy of h Entropy of h Entropy of h Entropy of h
1
1
1
1
t2 Entropy of h1Entropy of h1Entropy of h1Entropy of h1
…
…
…
…
tn Entropy of h1Entropy of h1Entropy of h1Entropy of h1


Apply multiway subspace method to each
hash function
In all m hash functions, see how many ones
are identified as anomalous
–
15
Voting approach
Identify Anomalies
t1 Entropy of h
1
s buckets


16
Entropy of h2
Entropy of h3
Entropy of h4
s buckets
s buckets
s buckets
Find the element in hash functions that is
identified as anomalous
The intersection of the key sets over all hash
functions which has raised the alarms,
identifies the keys of the IP flows that caused
the anomaly (with high likelihood)
Evaluation (1/2)
17
Evaluation (2/2)


18
5 or 6 hash functions is enough
If m is the number of hash functions, m−2 or more votes may
be enough
Conclusion
 Uses
multiple random traffic
projections to robustly detect
anomalies
 Higher detection rate and fewer
false alarms
 Able to automatically infer the IP
flows responsible for an anomaly
19
Comments
 Only
can handle offline data
 Can other fields in packet header
be used for anomaly detection?
20