%0 Conference Paper %1 Becchi:2007:HFA:1364654.1364656 %A Becchi, Michela %A Crowley, Patrick %B Proceedings of the 2007 ACM CoNEXT Conference %C New York, NY, USA %D 2007 %I ACM %K automaton deep finite hybrid practical %P 1:1--1:12 %R 10.1145/1364654.1364656 %T A Hybrid Finite Automaton for Practical Deep Packet Inspection %U http://doi.acm.org/10.1145/1364654.1364656 %X Deterministic finite automata (DFAs) are widely used to perform regular expression matching in linear time. Several techniques have been proposed to compress DFAs in order to reduce memory requirements. Unfortunately, many real-world IDS regular expressions include complex terms that result in an exponential increase in number of DFA states. Since all recent proposals use an initial DFA as a starting-point, they cannot be used as comprehensive regular expression representations in an IDS. In this work we propose a hybrid automaton which addresses this issue by combining the benefits of deterministic and non-deterministic finite automata. We test our proposal on Snort rule-sets and we validate it on real traffic traces. Finally, we address and analyze the worst case behavior of our scheme and compare it to traditional ones. %@ 978-1-59593-770-4

@inproceedings{Becchi:2007:HFA:1364654.1364656, abstract = {Deterministic finite automata (DFAs) are widely used to perform regular expression matching in linear time. Several techniques have been proposed to compress DFAs in order to reduce memory requirements. Unfortunately, many real-world IDS regular expressions include complex terms that result in an exponential increase in number of DFA states. Since all recent proposals use an initial DFA as a starting-point, they cannot be used as comprehensive regular expression representations in an IDS. In this work we propose a hybrid automaton which addresses this issue by combining the benefits of deterministic and non-deterministic finite automata. We test our proposal on Snort rule-sets and we validate it on real traffic traces. Finally, we address and analyze the worst case behavior of our scheme and compare it to traditional ones.}, acmid = {1364656}, added-at = {2013-12-19T14:19:12.000+0100}, address = {New York, NY, USA}, articleno = {1}, author = {Becchi, Michela and Crowley, Patrick}, biburl = {https://www.bibsonomy.org/bibtex/2e3380bf01620c995212983b1f9ebe326/ckleemann}, booktitle = {Proceedings of the 2007 ACM CoNEXT Conference}, description = {A hybrid finite automaton for practical deep packet inspection}, doi = {10.1145/1364654.1364656}, interhash = {bad06ffd0b691e14014e18efa8eb62c6}, intrahash = {e3380bf01620c995212983b1f9ebe326}, isbn = {978-1-59593-770-4}, keywords = {automaton deep finite hybrid practical}, location = {New York, New York}, numpages = {12}, pages = {1:1--1:12}, publisher = {ACM}, series = {CoNEXT '07}, timestamp = {2013-12-19T14:19:12.000+0100}, title = {A Hybrid Finite Automaton for Practical Deep Packet Inspection}, url = {http://doi.acm.org/10.1145/1364654.1364656}, year = 2007 }