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)
approximate reduction, probabilistic distance, finite automata, probabilistic
automaton, network intrusion detection
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.
@inproceedings{BUT147192,
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",
booktitle="Proceedings of TACAS'18",
year="2018",
journal="Lecture Notes in Computer Science",
volume="10806",
number="2",
pages="155--175",
publisher="Springer Verlag",
address="Thessaloniki",
doi="10.1007/978-3-319-89963-3\{_}9",
issn="0302-9743",
url="https://www.fit.vut.cz/research/publication/11657/"
}