  We consider the problem of approximate reduction of non-deterministic
automata that appear in hardware-accelerated network intrusion detection
systems (NIDSes). We define an error distance of a reduced automaton from the
original one as the probability of packets being incorrectly classified by the
reduced automaton (wrt the probabilistic distribution of packets in the network
traffic). We use this notion to design an approximate reduction procedure that
achieves a great size reduction (much beyond the state-of-the-art
language-preserving techniques) with a controlled and small error. We have
implemented our approach and evaluated it on use cases from Snort, a popular
NIDS. Our results provide experimental evidence that the method can be highly
efficient in practice, allowing NIDSes to follow the rapid growth in the speed
of networks.
