Publication detail
Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection
ČEŠKA, M. HAVLENA, V. HOLÍK, L. LENGÁL, O. VOJNAR, T.
Original Title
Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection
Type
conference paper
Language
English
Original Abstract
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.
Keywords
approximate reduction, probabilistic distance, finite automata, probabilistic automaton, network intrusion detection
Authors
ČEŠKA, M.; HAVLENA, V.; HOLÍK, L.; LENGÁL, O.; VOJNAR, T.
Released
23. 2. 2018
Publisher
Springer Verlag
Location
Thessaloniki
ISBN
0302-9743
Periodical
Lecture Notes in Computer Science
Year of study
10806
Number
2
State
Federal Republic of Germany
Pages from
155
Pages to
175
Pages count
18
URL
Full text in the Digital Library
BibTex
@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/"
}
Documents