CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

A Memory Efficient Regular Expression Matching by Compressing Deterministic Finite Automata

by Utkarsha P. Pisolkar, Shivaji R. Lahane
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 122 - Number 20
Year of Publication: 2015
Authors: Utkarsha P. Pisolkar, Shivaji R. Lahane
10.5120/21815-5143

Utkarsha P. Pisolkar, Shivaji R. Lahane . A Memory Efficient Regular Expression Matching by Compressing Deterministic Finite Automata. International Journal of Computer Applications. 122, 20 ( July 2015), 14-17. DOI=10.5120/21815-5143

@article{ 10.5120/21815-5143,
author = { Utkarsha P. Pisolkar, Shivaji R. Lahane },
title = { A Memory Efficient Regular Expression Matching by Compressing Deterministic Finite Automata },
journal = { International Journal of Computer Applications },
issue_date = { July 2015 },
volume = { 122 },
number = { 20 },
month = { July },
year = { 2015 },
issn = { 0975-8887 },
pages = { 14-17 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume122/number20/21815-5143/ },
doi = { 10.5120/21815-5143 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:11:02.817547+05:30
%A Utkarsha P. Pisolkar
%A Shivaji R. Lahane
%T A Memory Efficient Regular Expression Matching by Compressing Deterministic Finite Automata
%J International Journal of Computer Applications
%@ 0975-8887
%V 122
%N 20
%P 14-17
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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.
  2. A. V. Aho and M. J. Corasick. "Efficient String Matching: An Aid to Bibliographic Search. " Communications of the ACM, 18(6):333–340, 1975.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. R. Smith, C. Estan, and S. Jha, "Xfa: Faster signature matching with extended automata", in IEEE Symposium on Security and Privacy, May 2008.
  8. 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.
  9. 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.
  10. 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.
  11. Ken Thompson, "Programming techniques: regular expression search algorithm", in Communications of the ACM, Pages 419-422 , Volume 11 Issue 6, June 1968
  12. John E. Hopcroft and Jeffrey D. Ullman, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley Publishing, Reading Massachusetts, 1979.
  13. "SNORT," 2010 [Online]. Available: http://www. snort. org
Index Terms

Computer Science
Information Sciences

Keywords

Regular expressions security attacks deterministic finite automata intrusion detection and prevention.

Powered by PhDFocusTM