A Memory Efficient Regular Expression Matching by Compressing Deterministic Finite Automata
|
10.5120/21815-5143 |
Utkarsha P Pisolkar and Shivaji R Lahane. Article: A Memory Efficient Regular Expression Matching by Compressing Deterministic Finite Automata. International Journal of Computer Applications 122(20):14-17, July 2015. Full text available. BibTeX
@article{key:article,
author = {Utkarsha P. Pisolkar and Shivaji R. Lahane},
title = {Article: A Memory Efficient Regular Expression Matching by Compressing Deterministic Finite Automata},
journal = {International Journal of Computer Applications},
year = {2015},
volume = {122},
number = {20},
pages = {14-17},
month = {July},
note = {Full text available}
}
Abstract
Regular expressions are very meaningful and now-a-days broadly used to represent signatures of various attacks. The focal component of today's security systems like intrusion detection and prevention system is a signature based regular expression matching. Deterministic finite automaton is often used to represent regular expressions. In regular expression matching, storage space of Deterministic finite automata is very important concern. A massive amount of memory is essential to store transition function of Deterministic finite automata. The method described in this paper reduces size of Deterministic finite automata which is in regular expression format. The performance of the regular expression matching by compressing Deterministic finite automata is evaluated by using regular expression set.
References
- AnatBremler-Barr, D. Hay, Y. Koral, "CompactDFA:Scalable pattern matching Using Longest Prefix Match Solutions," in IEEE/ACM Transaction on networking,vol-22,No. 2,April 2014.
- A. V. Aho and M. J. Corasick. "Efficient String Matching: An Aid to Bibliographic Search. " Communications of the ACM, 18(6):333–340, 1975.
- S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner, "Algorithms to accelerate multiple regular expressions matching for deep packet inspection", in Proc. of ACM SIGCOMM , pages 339-350. ACM, 2006.
- S. Kumar, J. Turner, J. Williams, "Advanced algorithms for fast and scalable deep packet inspection", in Proc. ACM/IEEE Symp. Archit. Netw. Commun. Syst. (ANCS), pages 81-92. ACM, 2006.
- M. Becchi, P. Crowley, "A hybrid finite automaton for practical deep packet inspection", in Proc. Conf. Emerging Netw. Exp. Technol. (CoNEXT), pages 1-12, 2007.
- S. Kumar, B. Chandrasekaran, J. Turner, G. Varghese, "Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia", in Proc. ACM/IEEE Symp. Archit. Netw. Commun. Syst. (ANCS), pages 155-164. ACM, 2007.
- R. Smith, C. Estan, and S. Jha, "Xfa: Faster signature matching with extended automata", in IEEE Symposium on Security and Privacy, May 2008.
- D. Ficara, S. Giordano, G. Procissi, F. Vitucci, G. Antichi, A. D. Pietro, "An Improved DFA for Fast Regular Expression Matching" ACM SIGCOMM Computer Communication Review, Volume 38, Number 5, October 2008.
- S. Kong, R. Smith, and C. Estan, "Efficient signature matching with multiple alphabet compression tables," in Proc. Int. Conf. Security Privacy Commun. Netw. (Securecomm), 2008.
- S. Kumar, J. Turner, P. Crowley, and M. Mitzenmacher, "HEXA: Compact data structures for faster packet processing", in Proc. IEEE Conf. Comput. Commun. (INFOCOM), 2009.
- Ken Thompson, "Programming techniques: regular expression search algorithm", in Communications of the ACM, Pages 419-422 , Volume 11 Issue 6, June 1968
- John E. Hopcroft and Jeffrey D. Ullman, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley Publishing, Reading Massachusetts, 1979.
- "SNORT," 2010 [Online]. Available: http://www. snort. org