Publication Details
Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection
Havlena Vojtěch, Ing., Ph.D. (DITS)
Holík Lukáš, doc. Mgr., Ph.D. (DITS)
Lengál Ondřej, Ing., Ph.D. (DITS)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS)
reduction, nondeterministic finite automata, deep packet inspection, high-speed
network monitoring
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.
@article{BUT161576,
author="Milan {Češka} and Vojtěch {Havlena} and Lukáš {Holík} and Ondřej {Lengál} and Tomáš {Vojnar}",
title="Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection",
journal="International Journal on Software Tools for Technology Transfer",
year="2020",
volume="22",
number="5",
pages="523--539",
doi="10.1007/s10009-019-00520-8",
issn="1433-2779",
url="https://link.springer.com/article/10.1007/s10009-019-00520-8"
}