An ImprovedAlgorithm to■AccelerateREEvaluationYuankunQin
An Improved Algorithm to Accelerate RE Evaluation Yuankun Qin
ContentsREMatchingApproachesOptimizationofDFAGroup&ImprovedDDFA
Contents RE Matching Approaches Optimization of DFA Group & Improved DDFA
RE MatchingConvertREtoAutomataNFA:Expression-DrivenDFA:Text-Driven(TextOnePass
RE Matching ❖Convert RE to Automata ❖NFA : Expression-Driven ❖DFA : Text-Driven (Text One Pass)
Automata-basedApproachesDFA-basedNFA-based·AgroupofstatescanbeOnlyonestateisactivatedactiyated simultaneouslyRepeatedScancOne Pass Scan(SpaceProbiem)Can the input onty Higb percentage of wildeardsStartscanningfsomoneSidapproachesCanposition, if nomatch dtvidual pFast anletecoinie!soinetimeslessthanagainatthe axtstoropaebforean.GoodforparsersSomepatternsgenerafDvenE.PacketsmayonotntaiosirelargeDFAO(1)processinganypatternscomplexityforeachinputcomplexityforeachinputCortributioasanlearattigh.character. speed FaneWAElnandsAP)ESelectivelygrouppatternsintokgroups (e.g.,k=3)reducememoryusageAvoidexponentialmemorygrowthMakeDFA-based·Furtherspeed upmatchingapproachfeasible
Automata-based Approaches DFA-based NFA-based Start 3 A|D 4 2 E C A|B 1 Start 5 D 2 E C B 1 3 4 A C E Patterns (A|B)C and (A|D)E • A group of states can be activated simultaneously • Only one state is activated • High percentage of wildcards ➔NFA-based approaches can be slow, sometimes less than 1Mb/s Repeated Scan One Pass Scan • Start scanning from one position, if no match, start again at the next position • Good for parsers • Packets may not contain any patterns • No guarantee of high speed • Scan the input only once • Fast and deterministic throughput • Add .* before patterns • Some patterns generate very large DFA m Individual DFA for m patterns One composite DFA for m patterns • O(m) processing complexity for each input character • O(1) processing complexity for each input character • Rewrite techniques to reduce memory usage • Make DFA-based approach feasible Contributions • Selectively group patterns into k groups (e.g., k=3) • Avoid exponential memory growth • Further speed up matching process (Space Problem)
ImplementSommer&Paxson,2003*FPGA-Based- Sidhu & Prasanna, state->flip-flopSoftware-oriented- Versatility- Limited cost of implementation- Could be run at higher clock rateprocessors
Implement ❖Sommer & Paxson, 2003 ❖FPGA-Based ▪ Sidhu & Prasanna, state->flip-flop ❖Software-oriented ▪ Versatility ▪ Limited cost of implementation ▪ Could be run at higher clock rate processors