High-Performance Pattern Matching for Intrusion Detection IEEE Infocom 2006 +NEsN.4 H
High-Performance Pattern Matching for Intrusion Detection IEEE Infocom 2006
Contents Background: AC algorithm BFSM Optimizations to BFSm The implementation of BFSM Experimental Results +NeOn.4.4 H
Contents • Background: AC algorithm • BFSM • Optimizations to BFSM • The implementation of BFSM • Experimental Results
The AC algorithm P=he, she, his, hers) 0~④ 3) +NEsN.4 H
The AC Algorithm • P={he, she, his, hers}
The AC algorithm P=the, she, his, hers h e 0 4)(5 +NEsN.4 H
The AC Algorithm • P={he, she, his, hers}
The AC algorithm P=the, she, his, hers ④⑨ S ANNaN. H
The AC Algorithm • P={he, she, his, hers}
The Ac algorithm The Non-deterministic Finite automaton (NFA) h e 2}-8 Is 6 3 5 (a) Goto function 123456789 f()000120303 (b) Failure function ANNaN. H
The AC Algorithm • The Non-deterministic Finite Automaton (NFA)
The AC algorithm Convert NFA to DFA (deterministic FA) 0 2 9 {h,s} input symbol next state state 0: h 6)7 0 state 1: e (a) Goto functio 23456789 f()000120303 0 (b) Failure function H
The AC Algorithm • Convert NFA to DFA (deterministic FA)
The AC algorithm The standard Ac state Node Implementation struct ac node ° int *next state256]; rule x match rule list +NEsN.4 H
The AC Algorithm • The Standard AC State Node Implementation: • struct ac_node • { • int * next_state[256]; • rule * match_rule_list; • }
The BFSM Algorithm Concentrate on DFA Mainly a novel implementation of DFA The work is based on implementation on hardware. FPGA or ASIC +NEsN.4 H
The BFSM Algorithm • Concentrate on DFA • Mainly a novel implementation of DFA • The work is based on implementation on hardware, FPGA or ASIC
The BFSM Algorithm The transition rules The description of BFSM *Rule selection Policy State Clusters for scalability purpose +NEsN.4 H
The BFSM Algorithm • The transition rules • The description of BFSM • *Rule Selection Policy • *State Clusters for scalability purpose