Transcript ppt - University of Connecticut

A Signature Match Processor
Architecture for Network Intrusion
Detection
Janardhan Singaraju, Long Bu and John A. Chandy
Electrical and Computer Engineering Department,
University of Connecticut, Storrs, CT 06269-1157
Introduction

Network intrusion Detection :Process of identifying and analyzing
packets that may signify an impending threat to Organizations
Network.

Deployment- Passive : Uses secondary node to analyze data flow
Host Based System : Monitors a single system.

SNORT- Open Source intrusion detection Software.
EX: alert udp $EXTERNAL_NET any -> $HOME_NET 31335
(msg:"DDOSTrin00 Daemon to Master message detected"; content:"l44";
reference:arachnids,186;classtype:attempted-dos; sid:231; rev:3;)

String Matching: 30% of Computation Time.
Software vs. Hardware

Software Implementation

Hardware implementation

Relatively slow
More CPU computation
Flexible
Easy design and implementation

Very fast
CPU offload
Less flexible
Much longer design cycle







Hardware Techniques : Finite Automata based methods, CAM
Based methods
CAM Based NIDS





Content Addressable Memories: Used in
caches,IP address look-up tables.
CAM based NIDS stores a set of signatures
k bits matched against CAM for matches.
No need to reprogram.
Cannot handle regular Expressions.
Disadvantages



Fixed keyword size.
Cannot match overlapping signatures
e.g.: Signatures FOO and BAR
Data: AFOOBARCD, k=3 checks
AFO, OBA,RCD – no match?
Sliding window approach using single
character comparators with shift registers.
Our Model


CAM based Signature match processor
Uses array of Cellular automata to process Character
matches.

Compatible with further optimizations like processing
characters in parallel, prefix sharing, pattern
partitioning etc.

Multiple character matches per cycle of operation
Signature Match processor Architecture
CPU Control
CPU Control
Data in
Data in
From
network
Character Match
Array
Match Signal
PE Reset
Control
circuit
Signature Match Array
SM Reset
Signature Match buffer
Finish
Match Address output Logic
Matched Address Output
Character match array




Can be implemented with CAM
Array of Discrete Comparators
256, 8 bit Comparators to match all possible
ASCII Characters
P rows of Comparators, P denote the degree
of parallelism
Character Match Array
Byte 1
A
B
C
D
B
C
D
Byte 2
A
...
...
...
.........................................
Byte p
A
Match A[1:p]
B
C
D
Match D[1:p]
Character Match Array
Byte 1
C
A
B
0
C
0
...
D
1
0
Byte 1
D
A
B
0
C
0
...
D
0
1
Signature Match Array
N x 1 array of processing elements (PE)
N is number of characters in the signature set
to be matched.
 All inputs connected according to the
signature set to be matched.
 Each element performs a simple algorithm
based on the number of characters matched
at a time (p).

Signature Match Array
MQ[1:p]
MU[1:p]
MI[1:p]
MT[1:p]
Cin [1:p]
Cout [1:p]
Cin [1:p]
Cout [1:p]
Cin [1:p]
Sig_end
Cout [1:p]
Sig_beg
Signature match
Signature: QUIT
Signature Match Array
EX: p = 4
cout1 <= MA1 and (cin3 or sig_beg);
cout2 <= MA2 and (cin1 or sig_beg);
cout3 <= MA3 and (cin2 or sig_beg);
cout4_temp <= MA4 and (cin3 or sig_beg);
sig_match <= sig_end and (cout1 or cout2 or cout3 or cout4_temp);
if ( clk’event and clk=’1’) then
cout4 <= cout4_temp;
end if
Signature Match Array




Each PE generates carry signals that are
propagated to the next PE
These carry signals determine the carry
signals that are generated in the next PE.
Carry signals along with signature begin
signal determine the word match
Pth Carry out in each PE is latched for further
use.
Signature Match Processor
f
4
a
d
l
s
4
a
d
l
s
l
00
Sig_beg
Sig_end
0
1
l
00
00
01
Sig_beg
0
0
1
4
00
Sig_end
0
0
0
4
0
a
Signature match
0
Data in : fl44
0
0
0
d
0
0
0
s
0
0
l
Signature match
0
Signature Match Processor
4
4
a
d
l
s
4
a
d
l
s
4
11
Sig_beg
Sig_end
0
0
l
00
00
00
Sig_beg
1
0
1
4
00
Sig_end
0
1
0
4
0
a
Signature match
1
Data in : fl44
0
0
0
d
0
0
0
s
0
0
l
Signature match
0
Address Output Logic



Separates multiple matches for signatures
and decodes start address of each
Signature match
Signature match buffer stores end address of
all word matches
Match position (MP) is given as input to
binary structured address output logic
A1
MA out
MAA
LP in
LP1
MP1
LP0
MP0
A0
LP3
LP2
MP3
MP2
LP1
MP1
LP0
MP0
Address Output Logic
A0
LP3
LP2
MP3
MP2
LP1
MP1
LP0
MP0
Address Output Logic
A1
MAA
Address
1011
LP
1000
0011
0010
01
0001
0001
00
11
Control Circuit



Manages data flow throughout the signature
match processor
Presents p bytes of data to the signature
match processor
Resets the signature match buffers, enables
address output logic
Performance Analysis

time to process a b byte packet is b/p+M+1
cycles where M is the number of matches found in the
packet.

b/p corresponds to the time for the packet to stream
through the SMP signature matches and M + 1 is the time
to do the matched address output

per-packet cycle time is max ( b/p, M + 1)

If b/p > M + 1, which is the general case, the per-packet cycle
time is b/p, and the per-byte run-time is 1/p cycles.
NIDS with SMP Architecture
CPU or Network Processor
SDR AM
Packet
Buffer
Data in
from
Network
Packets In
MAC/ PHY
PKT _RDY
PKT _END
PKT _ACK
Keyword Match
Processor
FPGA implementation
Xilinx Virtex II Pro XC2VP30 FPGA
 Virtex II Pro has Rocket IO to implement
MAC
 XILINX ISE 7.1i Design environment
 Rule set ranging from 94 rules with 1021
char to 1237 rules with 16347 chars

Resource Utilization
Resource Utilization



Design using binary tree structured Address
output logic uses 1.5 registers and 1.5 LUTs
per CAM Character
LUTs correspond to CAM, PE logic ,MAO
logic.
Registers correspond to Word match buffers
and PE registers.
Comparison NIDS FPGA Designs
Comparison NIDS FPGA Designs



The performance metric is ratio between
throughput and logic cell/char to evaluate the
tradeoff between area and performance
Number of Logic cells/Char is small
Throughput will increase with increase in
parallelism.
Conclusions



Innovative CAM based Signature Match
Processor
Processing speed of over 5Gbps can be
achieved
Priority address encoder to generate
addresses in case of multiple matches
Future Directions




Plan to use embedded PowerPC in Virtex II Pro to
implement software part of NIDS such as SMP
Managements, Alerts, logging etc
Other applications such as directory lookup in
network storage systems, DNS lookup and LDAP
processing
Extending SMP to support wild card and
approximate word matching capabilities
Improving power characteristics of SMP