Publication Details

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

ČEŠKA Milan, HAVLENA Vojtěch, HOLÍK Lukáš, LENGÁL Ondřej and VOJNAR Tomáš. Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection. In: Proceedings of TACAS'18. Thessaloniki: Springer Verlag, 2018, pp. 155-175. ISSN 0302-9743.
Czech title
Přibližná redukce konečných automatů pro detekci útoků ve vysokorychlostních sítích
Type
conference paper
Language
english
Authors
Keywords


approximate reduction, probabilistic distance, finite automata, probabilistic automaton, network intrusion detection

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.

Published
2018
Pages
155-175
Journal
Lecture Notes in Computer Science, vol. 10806, no. 2, ISSN 0302-9743
Proceedings
Proceedings of TACAS'18
Conference
European Joint Conferences on Theory and Practice of Software, Thessaloniki, GR
Publisher
Springer Verlag
Place
Thessaloniki, GR
DOI
UT WoS
000445822600009
EID Scopus
BibTeX
@INPROCEEDINGS{FITPUB11657,
   author = "Milan \v{C}e\v{s}ka and Vojt\v{e}ch Havlena and Luk\'{a}\v{s} Hol\'{i}k and Ond\v{r}ej Leng\'{a}l and Tom\'{a}\v{s} Vojnar",
   title = "Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection",
   pages = "155--175",
   booktitle = "Proceedings of TACAS'18",
   journal = "Lecture Notes in Computer Science",
   volume = 10806,
   number = 2,
   year = 2018,
   location = "Thessaloniki, GR",
   publisher = "Springer Verlag",
   ISSN = "0302-9743",
   doi = "10.1007/978-3-319-89963-3\_9",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11657"
}
Back to top