Transcript RAIDM-motorola - Computer Science Division

1
Towards Anomaly/Intrusion
Detection and Mitigation on
High-Speed Networks
Yan Gao, Zhichun Li, Manan Sanghi, Yan Chen, MingYang Kao
Northwestern Lab for Internet and Security
Technology (LIST)
Department of Computer Science
Northwestern University
http://list.cs.northwestern.edu
2
Outline
• Motivation
• Architecture of RAIDM
• Statistical Sketch-based Anomaly/Intrusion
Detection
– Design
– Evaluation Results
• Polymorphic Worm Signature Generation with
Provable Attack Resilience
– Design
– Preliminary Evaluation Results
• Conclusions
Desired Features of Intrusion Detection
Systems (IDS)
3
• Network-based and scalable to high-speed links
– Slammer worm infected 75,000 machines in <10 mins
– Flash worm can take less than 1 second to compromise 1M
vulnerable machines in the Internet [Staniford04]
– Host-based schemes inefficient and user dependent
» Have to install IDS on all user machines !
– Existing network IDS unscalable: In a 10Gbps link, each
40-byte packet only has 32ns for processing !
• Aggregated detection over multiple vantage points
– Multi-homing, load balancing, policy routing become
popular
asymmetric routing
– Even worse… Per-packet load balancing
– Cannot afford to move traffic around
Features of Demanded Intrusion Detection
Systems (IDS)
• Attack resiliency
– Human adversaries are difficult to handle. Attacks tend
to fool or DoS the IDS system.
– Many IDSs use exact per-flow states, which is
vulnerable to DoS attack.
• Attack root cause analysis for mitigation
– Detection is only the first step. We also need mitigation
and prevention.
– Overall traffic based approaches can scale to high
speed but cannot really help mitigation
– We need flow-level information for mitigation
– Signature generation for polymorphic worms
4
5
Outline
• Motivation
• Architecture of RAIDM
• Statistical Sketch-based Anomaly/Intrusion
Detection
– Design
– Evaluation Results
• Polymorphic Worm Signature Generation with
Provable Attack Resilience
– Design
– Preliminary Evaluation Results
• Conclusions
Router-based Anomaly/Intrusion Detection
and Mitigation System (RAIDM)
• Online traffic recording
– Design reversible sketch for data streaming computation
– Record millions of flows (GB traffic) in a few hundred KB
• Online flow-level anomaly/intrusion detection & mitigation
– As a first step, detect TCP SYN flooding, horizontal and vertical
scans even when mixed
» Existing schemes like TRW/AC, CPM will have high false positives
– Infer key characteristics of malicious flows for mitigation
• Dos attack resiliency
• Apply to distributed detection environment
RAIDM: First flow-level intrusion detection that can sustain
10s Gbps bandwidth even for worst case traffic of 40-byte
packet streams
6
Router-based Anomaly/Intrusion Detection
and Mitigation System (RAIDM)
• Attach to routers as a black box
RAIDM
system
LA
N
Internet
Switch
Switch
RAIDM
system
RAIDM
system
LA
N
scan
port
Internet
Internet
LA
N
Splitter
Switch
Router
Splitter
Router
Switch
Switch
Router
LA
N
(a)
Switch
scan
port
LA
N
HAIDM
system
(b)
LA
N
(c)
Attach HRAID black boxes to high-speed routers
(a) original configuration, (b) distributed configuration for which each port
is monitored separately, (c) aggregate configuration for which a splitter is
used to aggregate the traffic from all the ports of a router.
7
RAIDM Architecture
Remote
aggregated
sketch
records
Sent out for
aggregation
Normal flows
Reversible
k-ary sketch
monitoring
Streaming
packet
data
Filtering
Local
sketch
records
Sketch based
statistical anomaly
detection (SSAD)
Keys of suspicious flows
8
Part I
Sketchbased
monitoring
& detection
Keys of normal flows
Suspicious flows
Per-flow
monitoring
Signature
-based
detection
Polymorphic
worm detection
(Hamsa)
Network fault
diagnosis (DOD)
Intrusion or
anomaly alarms
Data path
Control path
Modules on
the critical
path
Modules on
the non-critical
path
Part II
Per-flow
monitoring
& detection
9
Outline
• Motivation
• Architecture of RAIDM
• Statistical Sketch-based Anomaly/Intrusion
Detection
– Design
– Evaluation Results
• Polymorphic Worm Signature Generation with
Provable Attack Resilience
– Design
– Preliminary Evaluation Results
• Conclusions
Statistical Sketch-based
Anomaly/Intrusion Detection (SSAD)
10
Aggregate
Two
dimensional
sketch
Sketches from
other routers
...
Real
traffic
stream
Sketch
recording
Current
reversible
sketch
Aggregate
reversible
sketch
Update
Recording process
Forecast
error
Statistical
detection
False
positive
reduction
Attack
mitigation
Forecast
sketch
Detection process
• Recording stage: record traffic of each router with
different sketches, then transfer and combine them to
current reversible sketch.
• Detection stage: use Time Series Analysis (Holt-Winter and
EWMA) to detect large forecast error as anomalies.
• False positive reduction & 2D sketch skipped (lack of time)
Statistical Sketch-based
Anomaly/Intrusion Detection (SSAD)
• Distributed Detection Environment
Router 2
Router 3
N2
SYN1
SY
`
`
SY
N/
AC
K2
Router 1
CK
A
/
N
SY
1
…...
`
Dept 1
Dept 2
Internal Network
Dept n
11
Background: Reversible k-ary Sketch
• Array of hash tables: Tj[K]
(j = 1, …, H)
– Similar to count sketch, counting bloom filter, multistage filter, …
• Update (k, u): Tj [ hj(k)] += u (for all j)
0 1
…
h1(k)
1
…
hj(k)
j
…
H
hH(k)
K-1
12
Background: Reversible k-ary Sketch
• Estimate v(S, k): sum of updates for key k
• Sketches are linear
– Can Combine Sketches
– Can aggregate data from different times, locations, and
sources
+
=
• Inference I(S, t): output the heavy keys whose
values are larger than threshold t
13
Detection Algorithm
• RS((DIP, Dport), SYN-SYN/ACK)
• RS((SIP, DIP), SYN-SYN/ACK)
• RS((SIP, Dport), SYN-SYN/ACK)
P
O
R
T
N
U
M
B
E
R
14
V
E
R
T
I
C
A
L
BLOCK
HORIZONTAL
SOURCE IP
Attack types
RS((DIP, Dport),
SYN-SYN/ACK)
RS((SIP, DIP),
RS((SIP, Dport),
SYN-SYN/ACK) SYN-SYN/ACK)
SYN flooding
Yes
Yes
Yes
Vertical scans
No
Yes
No
Horizontal scans
No
No
Yes
DoS Resiliency Analysis
• Possible DoS attack to existing approaches like
TRW and TRW/AC
– Source spoofed SYN flooding attack
– Source spoofed packets to random location
• Attack SSAD is difficult. Possible attack is
based on creating collisions in sketches. But…
– Reverse engineering of hash functions is difficult
– The possibility of finding collisions through exhaustive
search is very low
– Attacks are limited even with collisions: need the
cooperation with comprised internal hosts.
15
Evaluation
• Data Sets
– NU traces (239M flows, 1.8TB traffic/day)
– Lawrence Berkeley National Laboratory (LBL) Trace
(900M flows)
• Rest of results based on NU trace evaluation
• Scalability and memory usage
– Total 9.4MB used for recording hundreds of millions of
flows
» 3 reversible k-ary sketches, 2 two dimensional sketches and 1
original k-ary sketch
– Small # of memory access per packet
16
• Fast
Evaluation (cont’d)
– Recording speed for the worst case traffic, all 40B pkts
» 16 Gbps on a single FPGA board
» 526 Mbps on a Pentium-IV 2.4GHz PC
– Detection speed
» On site NU experiment covering 1430 minutes: 0.34 sec for one
minute on average. (std=0.64 sec)
• Accurate Anomaly Detection w/ Reversible Sketch
– Compared with detection using complete flow-level logs
– Provable probabilistic accuracy guarantees
– Even more accurate on real Internet traces
17
Evaluation (cont’d)
18
• 25 SYN flooding, 936 horizontal scans and 19 vertical scans
detected (after sketch-based false positive reduction)
• 18 out of 25 SYN flooding verified w/ backscatter
– Complete flow-level connection info used for backscatter
• Scans verified (all for vscan, top and bottom 10 for hscan)
– Unknown scans also found in DShield and other alert reports
Bottom 10 horizontal scans
Top 10 horizontal scans
Description
Dport
count
Description
SQLSnake
1433
5
Sasser or Korgo worm
445
3
W32.Rahack
4899
2
W32.Sasser.B.Worm
5554
1
unknown scan
6101
1
Nachi or MSBlast worm
135
3
Scan SSH
22
1
NetBIOS scan
139
3
MySQL Bot scans
10202
1
Dport count
19
Outline
• Motivation
• Architecture of RAIDM
• Statistical Sketch-based Anomaly/Intrusion
Detection
– Design
– Evaluation Results
• Polymorphic Worm Signature Generation with
Provable Attack Resilience
– Design
– Preliminary Evaluation Results
• Conclusions
Requirements for polymorphic
worm signature generation
• Network-based
20
– Worm spread at exponential speed, at early stage there
are limited worm samples.
– Keep up with the network speed !
• Noise tolerant
– Most network level flow classifier may suffer false
positives.
• Attack resilience
– Attackers always try to evade the signature generation
system
• Efficient signature matching
– Again, on high-speed networks!
• No existing work satisfies these requirements
Hamsa
• Content based v.s. behavior based signature
– Content based: treat a worm as a byte sequence
– Behavior based: the actual dynamics of the worm
execution
– Fast matching could be a problem for behavior based
• We propose Hamsa, a network-based signature
generation system to meet the aforementioned
requirements
– Content based system (token based)
– Accuracy comparable to the state-of-the art
technique [Polygraph] but much faster
– Propose an adversary model and has attack resilience
guarantee
21
22
Hamsa Design
Network
Tap
TCP
25
Known
Worm
Filter
•
•
•
•
•
Worm
Flow
Classifier
Protocol
Classifier
TCP
53
TCP
80
Normal
Traffic Pool
Suspicious
Traffic Pool
. . .
TCP
137
Hamsa
Signature
Generator
UDP
1434
Signatures
Sniff traffic from networks
Assembly the packets to flows
Classify traffic based protocol
Filter out known worms
Generate suspicious and normal pools.
23
Hamsa Design
Hamsa Signature Generator
Normal
Traffic Pool
Token
Identification
Suspicious
Traffic Pool
NO
Token
Extractor
Pool size
too small?
Signature
Core
Tokens
Filter
YES
Quit
•
•
•
•
Iterative signature generation
Extract the tokens form suspicious pool
Identify the same set of tokens in normal pool
Core part: greedy algorithm based on the token information
Model-based Polymorphic Worm Signature
Generation Problem & Algorithm
The problem
No noise: O(n)
The model
The algorithm
Noise: NP-Hard
24
Evaluation Methodology
• Data collection
– Normal pool:
» 300MB Web traffic for training
» 20GB Web traffic and Binary distribution of Linux for evaluation
– Suspicious pool:
» 10 ~ 500 samples (with noise and different worms)
» 5000 samples each worm as false negative testing data set
– Three pseudo worms: ATPhttpd, Apache-Knacker, Codered II
– Two polymorphic engines from Internet
• Simulation settings
– Single worm with noise
» Test pool size 100 and 200
» Noise ratio 0, 10%, 30%, 50%
– Multiple worms with noise
» 3 worms together: ATPhttpd, Apache-Knacker, Codered II
» Test pool size 100 and 200
» Noise ratio 0, 10% and 25%
25
Preliminary Evaluation Results
• Signature Quality
• Signature Generation Speed
– 64 ~ 361 times faster than Polygraph
– Only use several seconds to at most minutes to generate signatures
• Attack Resilience
– Provable attack resilience (details omitted)
– For token-fit attack, Polygraph fail but Hamsa succeed
26
27
Backup Slides
Intrusion Detection
and Mitigation
P
O
R
T
N
U
M
B
E
R
28
V
E
R
T
I
C
A
L
BLOCK
HORIZONTAL
SOURCE IP
Attacks detected
Mitigation
Denial of Service (DoS), SYN defender, SYN proxy, or SYN
e.g., TCP SYN flooding
cookie for victim
Port Scan and worms
Ingress filtering with attacker IP
Vertical port scan
Quarantine the victim machine
Horizontal port scan
Monitor traffic with the same port
# for compromised machine
Spywares
Warn the end users being spied
Reversible Sketch Based Anomaly
Detection
(k,u) …
Sketch
module
Sketches
Forecast
module(s)
Error
Sketch
29
Anomaly Alarms
detection
module
•
Input stream: (key, update) (e.g., SIP, SYN-SYN/ACK)
•
Summarize input stream using sketches
•
Build forecast models on top of sketches
•
•
Report flows with large forecast errors
Infer the (characteristics) key for mitigation
Reducing False Positives for SYN
Flooding Detection
• Reasons of false positives of SYN flooding
detection
– Network/server congestions/failtures
– Polluted or outdated DNS entries
• Filters to reduce false positives caused by bursty
network /server congestions/failures
# SYN  # SYN / ACK 1

# SYN
2
1.
2. Lifetime > Thresholdlife
• Filters to reduce the false positives caused by
misconfigurations or related problems
– No connection history
30
Intrusion Classification with Two
Dimensional Sketch
• We need to distinguish different types of attack
to take the most effective mitigation scheme
– However, one dimensional information is not enough
• Non-spoofed SYN flooding v.s. horizontal scan {SIP,DP}
– Bi-modal distribution.
• Two dimensional Sketch
Structure of 2D sketch
hy(DP)
hy(DP)
hy(DP)
hx(SIP,DIP)
hx(SIP,DIP)
hx(SIP,DIP)
H two-dimensional
hash matrix
hy(80)
Example UPDATE
+1
Packet {2.3.0.5, 9.7.2.3, 80,SYN}
hx(2.3.0.5,9.7.2.3)
31
Intrusion Classification with Two
Dimensional Sketch
• Two dimensional sketch is accurate
– Refer to the paper about accuracy proof
– Can archive 99.9956% detection rate by the parameter
mentioned in the paper
32
Automated worm signature
generation
• Manual signature generation is too slow for
fast propagated worms
• Automatic signature generation has been
proposed [Earlybird][Autograph]
• But it is not hard for hackers to apply
polymorphism to their worms.
• Polymorphic worm signature generation
becomes necessary.
33