Enhancing Network Security Through Multi-Core Packet Scattering and Deep Packet Inspection
Multi-Core Packet Scattering to
Disentangle Performance Bottlenecks
Yotam Harchol
The Hebrew University
Joint work with Y. Afek, A. Bremler-Barr, D. Hay and Y. Koral.
This work was supported by European Research Council (ERC) Starting Grant
no. 259085, and appeared in HPSR'11 and ANCS’12.
Network Intrusion Detection Systems
Internet
•
Very popular middlebox
–
May be deployed in various places within the network
•
Reports or drops malicious packets
–
How to identify malicious packets?
Deep Packet Inspection (DPI)
•
Search for malicious
patterns
within packets’ payload
–
Exact string patterns/signatures
–
Patterns defined as regular expressions
–
Often combined with information from header fields
•
DPI is the heaviest processing component of NIDS
–
Why not use many machines/cores to speed it up?
1.
Pipeline multi-core, not efficient.
–
Imbalance of pipeline stations, DPI much heavier
2.
Parallel multi-core?
Multi-Core Deep Packet Inspection (DPI)
•
Option 1: Each core scans for a subset of the
pattern-set
Core 1
Core 2
Core 3
Core 4
Pattern Set 1
Pattern Set 2
Pattern Set 3
Pattern Set 4
Multi-Core Deep Packet Inspection (DPI)
•
Option 2: All cores are the same,
Load-balance between cores
Core 1
Core 2
Core 3
Core 4
DPI
DPI
DPI
DPI
Complexity DoS Attack Over NIDS
•
Regular operation
•
2 Steps attack:
Attacker
2. Launch original attack
(e.g., steal credit cards)
1. Kill IPS/FW
normal
malicious
heavy
Internet
•
Malicious packets
aim to hurt the application
NIDS should be able to deal with them with
no degradation in performance
•
Heavy packets
aim to hurt the NIDS
They will do nothing to the application
Attack on Security Elements
Attack on Snort
The most widely deployed IDS/IPS worldwide.
Heavy packets rate
OUR GOAL:
MCA
2
: M
ulti-
C
ore
A
rchitecture
for
M
itigating
C
omplexity
A
ttacks
Airline Desk Example
Airline Desk Example
Airline Desk Example
Airline Desk Example
Airline Desk Example
packets
packets
packets
packets
Some packets are much “heavier”
than others
The Snort-attack experiment
The Snort-attack experiment
Property 1 in Snort Attack
•
DPI mechanism is a main bottleneck in Snort
•
Allows single step for each input symbol
•
Holds transition for each alphabet symbol
Snort uses Aho-Corasick DFA
Crafting HEAVY packets
Snort patterns database
Heavy
packets factory
Chop last
2 bytes
Snort-Attack Experiment
Cache
Main
Memory
Normal Traffic
Attack Scenario
Does not require many packets!!!
Detecting heavy packets is feasible
Property
2
in Snort Attack
How Do We Detect?
•
Common states are detected through training traffic
set
threshold
non-common states
percentage
Tradeoff: Attack
effectiveness vs. false
positive/negative rates
How Do We Detect?
Common States
Non
Common States
Heavy packet :
# Not Common States
# Common States
≥
α
After at least
20 bytes
System Architecture
Processor Chip
Core #8
N
I
C
Core #1
Q
Core #2
Q
Q
Q
Q
Core #9
Core #10
Routine Mode:
Load balance between cores
System Architecture
Processor Chip
Core #8
D
e
d
i
c
a
t
e
d
C
o
r
e
#
9
N
I
C
Core #1
Q
Core #2
Q
Q
Q
B
D
e
d
i
c
a
t
e
d
C
o
r
e
#
1
0
B
Q
Alert Mode:
Dedicated cores for heavy packets
Others detect and move heavy to
Dedicated.
Inter-Thread Communication
•
Non-blocking IN-queues
–
Single reader,
single writer,
lock-free queues
•
Dedicated cores
in-queues are blocking
(using test&set locks)
–
Non-dedicated threads
“steal” packets from
the HoL when sending a
heavy packet
Processor Chip
Core #8
D
e
d
i
c
a
t
e
d
C
o
r
e
#
9
N
I
C
Core #1
Q
Core #2
Q
Q
Q
B
D
e
d
i
c
a
t
e
d
C
o
r
e
#
1
0
B
Q
Inter-Thread Communication
•
In queues
and
Heavy packets queues
are lock-free
– no locking mechanisms are used
•
Cyclic queue, conflicts are resolved by
marking two phases on the queue.
–
Changes after the entire queue is written to
•
Writer writes to the queue from right to left:
–
Check whether reader_phase=writer_phase or tail>head; otherwise queue is full
–
Right_phase
writer_phase
–
Write packet_pointer + offset
–
Left_phase
writer_phase
•
Reader reads in the opposite direction:
–
First reads left_phase bit, then packet, then right_phase bit.
–
If left_phase != right_phase: record is being written; retry.
–
If left_phase = right_phase != reader_phase: queue is empty
–
Otherwise, valid packet is read
Snort uses Aho-Corasick DFA
Huge memory footprint
Single memory access per input symbol
Small memory footprint
Multiple memory accesses per
input symbol
Full Matrix vs. Compressed
Heavy packets rate
In cache
Not in cache
Always in cache
Multiple
memory accesses
per symbol
One memory access per symbol
Experimental Results
System Throughput Over Time
Reaction time
can be smaller
Different Algorithms
Goodput
Bandwidth
Attack
Complexity
Attack
Additional Application for MCA
2
The Hybrid-FA-attack
The Hybrid-FA-attack
experiment
experiment
Hybrid-FA
•
Space-efficient data structure for
regular
expression matching
•
Faster than NFA
•
Structure:
–
Head DFA
–
Border states
–
Tail DFAs
•
More than one state can be active
at the same time!
.*
[^\n]*
Hybrid-FA Attack
Normal Traffic
Attack Scenario
Again: Does not require many packets!!!
.*
[^\n]*
s
0
s
7
s
8
s
9
s
10
s
11
s
12
s
2
s
5
s
13
Input:
C
D
B
B
C
A
B
Heavy Packet Detection
threshold
MCA
2
With Hybrid-FA
Concluding Remarks
•
A multi-core system architecture, which is
robust
against
complexity DoS attacks
•
This talk focused on specific NIDS and
complexity attack
–
But also shows other NIDS (e.g., Hybrid-FA)
–
More issues are dealt in the paper (e.g., dealing
with flows rather than single packets etc.)
•
We believe this approach can be generalized
(outside the scope of NIDS).
Thank You!!
Thank You!!
Extra Slides…
Extra Slides…
Detection Tradeoff
•
Attacker can use "lighter" heavy packets to
get below threshold
Detection Tradeoff
•
The effect of "lighter" packets on
throughput
-23%
-62%
-66%
-17%
-41%
-44%
affiliations
Explore the use of multi-core systems to tackle performance bottlenecks in network intrusion detection systems, specifically focusing on deep packet inspection. Techniques such as load balancing and pattern subset scanning are discussed to optimize DPI processes and improve overall network security against DoS attacks and malicious packet intrusions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Multi-Core Packet Scattering to Disentangle Performance Bottlenecks Yotam Harchol The Hebrew University Joint work with Y. Afek, A. Bremler-Barr, D. Hay and Y. Koral. This work was supported by European Research Council (ERC) Starting Grant no. 259085, and appeared in HPSR'11 and ANCS 12.
Network Intrusion Detection Systems Very popular middlebox May be deployed in various places within the network Reports or drops malicious packets How to identify malicious packets? Internet
Deep Packet Inspection (DPI) Search for malicious patterns within packets payload Exact string patterns/signatures Patterns defined as regular expressions Often combined with information from header fields DPI is the heaviest processing component of NIDS Why not use many machines/cores to speed it up? 1. Pipeline multi-core, not efficient. Imbalance of pipeline stations, DPI much heavier 1. Parallel multi-core?
Multi-Core Deep Packet Inspection (DPI) Option 1: Each core scans for a subset of the pattern-set Pattern Set 1 Core 1 Pattern Set 2 Pattern Set 3 Core 2 Core 3 Pattern Set 4 Core 4
Multi-Core Deep Packet Inspection (DPI) Option 2: All cores are the same, Load-balance between cores DPI Core 1 DPI DPI Core 2 Core 3 DPI Core 4
Complexity DoS Attack Over NIDS Regular operation 2 Steps attack: normal malicious heavy Attacker Malicious packets aim to hurt the application NIDS should be able to deal with them with no degradation in performance 1. Kill IPS/FW Heavy packets aim to hurt the NIDS Internet They will do nothing to the application 2. Launch original attack (e.g., steal credit cards)
Attack on Security Elements Combined Attack: DDoS on Security Element exposed the network theft of customers information
Attack on Snort The most widely deployed IDS/IPS worldwide. Heavy packets rate
OUR GOAL: MCA2: Multi-Core Architecture for Mitigating Complexity Attacks
Airline Desk Example Boarding pass, please
Airline Desk Example Overweight!!! An isle seat near window!! Can t find passport!! 20 min. Three carry on handbags !!! 1 min. Free first class upgrade!!
Airline Desk Example Special training Domain Properties packets 1. Heavy & Light customers. 4 min. 1 min. 2. Easy detection of heavy customers. packets packets 3. Moving customers between queues is cheap. packets 4. Heavy customers have special more efficient processing method.
Property 1 in Snort Attack Some packets are much heavier than others The Snort-attack experiment
Snort uses Aho-Corasick DFA DPI mechanism is a main bottleneck in Snort Allows single step for each input symbol Holds transition for each alphabet symbol Fast & Huge Cache Main Memory Best for normal traffic Exposed to cache-miss attack
Crafting HEAVY packets Heavy packets factory Snort patterns database Chop last 2 bytes
Snort-Attack Experiment Domain Properties Normal Traffic Attack Scenario Cache 1. Heavy & Light packets. Main Memory 2. Easy detection of heavy packets 3. Moving packets between queues is cheap. 4. Heavy packets have special more efficient processing method. Cache-miss!!! Does not require many packets!!!
Property 2in Snort Attack Detecting heavy packets is feasible
How Do We Detect? Common states are detected through training traffic set Tradeoff: Attack effectiveness vs. false positive/negative rates threshold non-common states percentage
How Do We Detect? Common States Non Common States Heavy packet : # Not Common States # Common States After at least 20 bytes
Domain Properties 1. Heavy & Light packets. 2. Easy detection of heavy packets 3. Moving packets between queues is cheap. 4. Heavy packets have special more efficient processing method.
System Architecture Detects heavy packets Core #1 NIC Q Q Core #2 Processor Chip Routine Mode: Q Core #8 Load balance between cores Core #9 Q Core #10 Q
System Architecture Detects heavy packets Core #1 NIC Q Q Core #2 Processor Chip Alert Mode: Dedicated cores for heavy packets Q Core #8 Others detect and move heavy to Dedicated. B B Dedicated Core #9 Q B Dedicated Core #10 Q B
Inter-Thread Communication Non-blocking IN-queues Single reader, single writer, lock-free queues Core #1 NIC Q Q Core #2 Processor Chip Dedicated cores in-queues are blocking (using test&set locks) Q Core #8 B B Dedicated Core #9 Q B Non-dedicated threads steal packets from the HoL when sending a heavy packet Dedicated Core #10 Q B
Inter-Thread Communication In queues and Heavy packets queues are lock-free no locking mechanisms are used Cyclic queue, conflicts are resolved by marking two phases on the queue. Changes after the entire queue is written to Writer writes to the queue from right to left: Check whether reader_phase=writer_phase or tail>head; otherwise queue is full Right_phase writer_phase Write packet_pointer + offset Left_phase writer_phase Reader reads in the opposite direction: First reads left_phase bit, then packet, then right_phase bit. If left_phase != right_phase: record is being written; retry. If left_phase = right_phase != reader_phase: queue is empty Otherwise, valid packet is read
Domain Properties 1. Heavy & Light packets. 2. Easy detection of heavy packets 3. Moving packets between queues is cheap. 4. Heavy packets have special more efficient processing method.
Snort uses Aho-Corasick DFA Huge memory footprint Single memory access per input symbol Small memory footprint Multiple memory accesses per input symbol
Full Matrix vs. Compressed In cache One memory access per symbol Always in cache Multiple memory accesses per symbol Not in cache Heavy packets rate
Domain Properties 1. Heavy & Light packets. 2. Easy detection of heavy packets 3. Moving packets between queues is cheap. 4. Heavy packets have special more efficient processing method.
System Throughput Over Time Reaction time can be smaller
Different Algorithms Goodput Complexity Attack Bandwidth Attack
Additional Application for MCA2 The Hybrid-FA-attack experiment
Hybrid-FA Space-efficient data structure for regular expression matching Faster than NFA Structure: Head DFA Border states Tail DFAs s0 B E C s1 s2 s7 D E D C s3 s4 s5 s8 [^\n]* D B A s9 .* s13 s6 A C s14 s10 More than one state can be active at the same time! A s11 B s12
Hybrid-FA Attack s0 s0 B s2 E C Normal Traffic Attack Scenario s1 s2 s7 s7 D E D C s3 s4 s5 s5 s8 s8 [^\n]* D B A s9 s9 s13 s13 s6 .* A C s14 s10 s10 A s11 B s11 s12 s12 Input: CDBBCAB Again: Does not require many packets!!!
Heavy Packet Detection threshold
Concluding Remarks A multi-core system architecture, which is robust against complexity DoS attacks This talk focused on specific NIDS and complexity attack But also shows other NIDS (e.g., Hybrid-FA) More issues are dealt in the paper (e.g., dealing with flows rather than single packets etc.) We believe this approach can be generalized (outside the scope of NIDS).
Detection Tradeoff Attacker can use "lighter" heavy packets to get below threshold 0.03% False Positive Rate 0.03% Different attack traffic With growing "heaviness" Medium Semi-Heavy "Regular" traffic 0.02% 0.02% Heavy Very Heavy 0.01% Percentage of packets 0.01% 0.00% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 0% Attack Intensity 30.00% False Negative Rate 25.00% 20.00% 15.00% 10.00% 5.00% 0.00% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 0% non-common states percentage Attack Instensity
Detection Tradeoff The effect of "lighter" packets on throughput 10000 9000 -17% 8000 7000 -23% Throughput [Mbps] -41% 6000 Very Light Light 5000 -44% Medium -62% Semi-Heavy 4000 Heavy 3000 -66% Very Heavy 2000 1000 0 0% 10% 20% 30% 40% Attack Intensity 50% 60% 70% 80% 90% 100%
