A Signature Match Processor Architecture for Network Intrusion DetectionIntroductionSoftware vs. HardwareCAM Based NIDSDisadvantagesOur ModelSignature Match processor ArchitectureCharacter match arrayCharacter Match ArraySlide 10Signature Match ArraySlide 12Slide 13Slide 14Signature Match ProcessorSlide 16Address Output LogicSlide 18Slide 19Control CircuitPerformance AnalysisNIDS with SMP ArchitectureFPGA implementationResource UtilizationSlide 25Comparison NIDS FPGA DesignsSlide 27ConclusionsFuture DirectionsA Signature Match Processor Architecture for Network Intrusion DetectionJanardhan Singaraju, Long Bu and John A. ChandyElectrical and Computer Engineering Department, University of Connecticut, Storrs, CT 06269-1157IntroductionNetwork 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. HardwareSoftware ImplementationRelatively slowMore CPU computationFlexibleEasy design and implementationHardware implementationVery fastCPU offloadLess flexibleMuch longer design cycleHardware Techniques : Finite Automata based methods, CAM Based methodsCAM Based NIDSContent Addressable Memories: Used in caches,IP address look-up tables.CAM based NIDS stores a set of signaturesk bits matched against CAM for matches.No need to reprogram. Cannot handle regular Expressions.DisadvantagesFixed 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 ModelCAM based Signature match processorUses 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 operationSignature Match processor ArchitectureMatched Address OutputControl circuitData in From networkCPU ControlCharacter Match ArraySignature Match ArraySignature Match bufferMatch SignalData inPE ResetSM ResetFinishMatch Address output LogicCPU ControlCharacter match arrayCan be implemented with CAMArray of Discrete Comparators256, 8 bit Comparators to match all possible ASCII CharactersP rows of Comparators, P denote the degree of parallelismCharacter Match ArrayA B C DByte 1. . .A B C DByte 2. . .A B C DByte p. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Match A[1:p] Match D[1:p]Character Match ArrayA B C DByte 1. . .D0 0 1 0 A B C DByte 1. . .C0 0 0 1Signature Match ArrayN 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 ArrayCout [1:p]Cout [1:p]Cin [1:p]Cout [1:p]Cin [1:p]Cin [1:p] Signature: QUITMQ[1:p] MU[1:p] MI[1:p] MT[1:p]Sig_beg Sig_endSignature matchSignature Match ArrayEX: p = 4cout1 <= 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 ifSignature Match ArrayEach PE generates carry signals that are propagated to the next PEThese carry signals determine the carry signals that are generated in the next PE.Carry signals along with signature begin signal determine the word matchPth Carry out in each PE is latched for further use.Signature Match Processor4 a d l s4 a d l sfl00 00 00 01 001 0 0 0 0 0 00lSig_beg4 4 a d s lSig_begSig_endSig_end10000000000Signature match Signature matchData in : fl44Signature Match Processor4 a d l s4 a d l s4411 00 00 00 000 0 1 0 0 0 01lSig_beg4 4 a d s lSig_begSig_endSig_end10010000000Signature match Signature matchData in : fl44Address Output LogicSeparates multiple matches for signatures and decodes start address of each Signature matchSignature match buffer stores end address of all word matchesMatch position (MP) is given as input to binary structured address output logicAddress Output LogicMP0MP1MP2MP3LP0LP1LP2LP3MAAA1A0MA outLP inMP0LP0MP1LP1Address Output LogicMP1MP2MP3LP0LP1LP2LP3A1A01011LP1000 11 AddressMAAMP00010 0100110001 000001Control Circuit Manages data flow throughout the signature match processorPresents p bytes of data to the signature match processorResets the signature match buffers, enables address output logicPerformance Analysistime 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 outputper-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 ArchitecturePKT_RDYPKT _ACKPKT_ENDPackets InSDRAM Packet BufferData infrom NetworkKeyword MatchProcessorCPU or Network ProcessorMAC/ PHYFPGA implementationXilinx Virtex II Pro XC2VP30 FPGAVirtex II Pro has Rocket IO to implement MAC XILINX ISE 7.1i Design environmentRule set ranging from 94 rules with 1021 char to 1237 rules with 16347 charsResource UtilizationResource UtilizationDesign using binary tree structured Address output logic uses 1.5 registers and 1.5 LUTs per CAM CharacterLUTs correspond to CAM, PE logic ,MAO logic.Registers correspond to Word match buffers and PE registers.Comparison NIDS FPGA DesignsComparison NIDS FPGA DesignsThe performance metric is ratio between throughput and logic cell/char to evaluate the tradeoff between area and performanceNumber of Logic cells/Char is smallThroughput will
View Full Document