Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection .

We consider the problem of approximate reduction of non-deterministicautomata that appear in hardware-accelerated network intrusion detectionsystems (NIDSes). We define an error distance of a reduced automaton from theoriginal one as the probability of packets being incorrectly classified by thereduced automaton (wrt the probabilistic distribution of packets in the networktraffic). We use this notion to design an approximate reduction procedure thatachieves a great size reduction (much beyond the state-of-the-artlanguage-preserving techniques) with a controlled and small error. We haveimplemented our approach and evaluated it on use cases from Snort, a popularNIDS. Our results provide experimental evidence that the method can be highlyefficient in practice, allowing NIDSes to follow the rapid growth in the speedof networks.