Skip to main content
SpringerLink
Log in

A Technical Survey on Intelligent Optimization Grouping Algorithms for Finite State Automata in Deep Packet Inspection

  • Original Paper
  • Published:
Archives of Computational Methods in Engineering Aims and scope Submit manuscript

Abstract

Construction and deployment of finite state automata from the regular expressions might results in huge overhead and results in the state explosion problem which is in need of large memory space, high bandwidth and additional computational time. To overcome this problem, a new framework is proposed, and several intelligent optimization algorithms are reviewed and compared in this framework. The proposed approach is called intelligent optimization grouping algorithms (IOGA), which intends to group regular expression intelligently. IOGAs are used to allocate the regular expression sets into various groups and to build independent deterministic finite automata (DFA) for each group. Grouping the regular expression efficiently solves the state explosion problem by achieving large-scale best tradeoff among memory utilization and computational time. This study reviews and compares the various alternatives of IOGA including genetic algorithm, ant colony optimization, particle swarm optimization, bacterial foraging optimization, artificial bee colony algorithm, biogeography based optimization, cuckoo search, firefly algorithm, bat algorithm and flower pollination algorithm for solving the problem of DFA state explosion and also for improving the overall efficiency of deep packet inspection (DPI). The discussions state that by effectively using these grouping algorithms along with DFA based DPI, the number of states can be reduced, providing a balance between the memory consumption, time complexity, throughput, inspection speed, convergence speed and grouping time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Paxson V (1998) Bro: a system for detecting network intruders in real time. Comput Netw Int J Comput Telecommun Netw 31:2435–2463

    Google Scholar 

  2. Nitin T, Singh SR, Singh PG (2012) Intrusion detection and prevention system (IDPS) technology—network behavior analysis system (NBAS). ISCA J Eng Sci 1:151–156

    Google Scholar 

  3. Hopcroft JE, Motwani R, Ullman JD (2001) Introduction to automata theory, languages, and computation, 2nd edn. Addison-Wesley Series in Computer Science. Addison-Wesley, Longman, pp 1–521. ISBN 978-0-201-44124-6

    MATH  Google Scholar 

  4. Yu F, Chen Z, Diao Y, Lakshman TV, Katz RH (2006) Fast and memory-efficient regular expression matching for deep packet inspection. University of California at Berkeley, Technical Report No.UCB/EECS-2006-76. http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-76.html

  5. Rohrer J, Atasu J, Van Lunteren J, Hagleitner C (2009) Memory-efficient distribution of regular expressions for fast deep packet inspection. In: Proceedings of the 7th IEEE/ACM international conference on hardware/software codesign and system synthesis. pp 147–154. https://doi.org/10.1145/1629435.1629456

  6. Liu T, Liu AX, Shi J, Sun Y, Guo Li (2014) Towards fast and optimal grouping of regular expressions via DFA size estimation. IEEE J Sel Areas Commun 32:10

    Google Scholar 

  7. Konar A (2005) Computational intelligence: principles, techniques and applications. Springer, Berlin Heidelberg New York

    MATH  Google Scholar 

  8. Sumathi S, Ashok Kumar L, Surekha P (2015) Computational intelligence paradigms for optimization problems using Matlab/Simulink. CRC Press, Boca Raton

    Google Scholar 

  9. Koza JR (1992) Genetic programming on the programming of computers by means of natural selection. MIT Press, Cambridge

    MATH  Google Scholar 

  10. Dorigo M, Maniezzo V, Colorni A (1991) Positive feedback as a search strategy. Politecnico di Milano, Italy, Technical Report, Report No. 91-016

  11. Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks. vol IV, pp 1942–1948

  12. Passino KM (2001) Biomimicry of bacterial foraging for distributed optimization and control. IEEE Control Syst 22(3):52–67

    Google Scholar 

  13. Tereshko V, Loengarov A (2005) Collective decision making in honey-bee foraging dynamics. Comput Inf Syst 9:3

    Google Scholar 

  14. Simon D (2008) Biogeography-based optimization. IEEE Trans Evol Comput 12(6):702–713

    Google Scholar 

  15. Yang X-S, Deb S (2009) Cuckoo search via levy flights. In: Proceedings of world congress on nature and biologically inspired computing (NaBIC). IEEE Publications, USA

  16. Yang X-S (2008) Nature-inspired metaheuristic algorithms, 2nd edn. University of Cambridge, Luniver Press, Cambridge

    Google Scholar 

  17. Yang XS (2010) A new metaheuristic bat-inspired algorithm. nature inspired cooperative strategies for optimization (NISCO 2010). Stud Comput Intell 284:65–74

    Google Scholar 

  18. Yang XS (2012) Flower pollination algorithm for global optimization. Unconventional computation and natural computation, lecture notes in computer science. vol 7445, pp 240–249

  19. Gandomi AH, Alavi AH (2012) Krill herd: a new bio-inspired optimization algorithm. Commun Nonlinear Sci Numer Simul 17(12):4831–4845. https://doi.org/10.1016/j.cnsns.2012.05.010

    Article  MathSciNet  MATH  Google Scholar 

  20. Mirjalili S, Gandomi AH, Mirjalili SZ, Saremi S, Faris H, Mirjalili SM (2017) Salp swarm algorithm: a bio-inspired optimizer for engineering design problems. Adv Eng Softw 114:163–191. https://doi.org/10.1016/j.advengsoft.2017.07.002

    Article  Google Scholar 

  21. Kleene SC (1951) Representation of events in nerve nets and finite automata. RAND Research Memorandum RM-704, RAND Corporation

  22. Harrison MA (1978) Introduction to formal language theory. Addison-Wesley Longman Publishing Co., Inc, Boston

    MATH  Google Scholar 

  23. Roesch M (1999) Snort: light weight intrusion detection for networks. In: Proceedings of the 13th USENIX conference on system administration. pp 229–238

  24. Levandoski J, Sommer E, Strait M, Application layer packet classifier for Linux. http://l7-filter.sourceforge.net/. Accessed 6 May 2018

  25. Koza JR (1994) Genetic programming II, automatic discovery of reusable programs. MIT Press, Cambridge

    MATH  Google Scholar 

  26. Hopcroft JE (1971) An nlogn algorithm for minimizing states in a finite automaton. The Theory of Machines and Computations. Academic, New York, pp 189–196

    Google Scholar 

  27. Sidhu R, Prasanna VK (2001) Fast regular expression matching using FPGAs. In: Proceedings of the 9th annual IEEE symposium on field-programmable custom computing machines. pp 227–238

  28. Prithi S, Sumathi S (2016) A review on deterministic finite automata compression strategies for deep packet inspection. Int J Innov Adv Comput Sci 5:6

    Google Scholar 

  29. Laptev N, Mousavi H, Shkapsky A, Zaniolo C (2012) Optimizing regular expression clustering for massive pattern search. UCLA Technical Report # 120005

  30. Aho AV, Corasick MJ (1975) Efficient string matching: an aid to bibliographic search. Commun ACM 18:6333–6340

    MathSciNet  MATH  Google Scholar 

  31. Wu S, Manber U (1994) A fast algorithm for multi pattern searching. Technical Report TR-94-17, University of Arizona

  32. Commentz-Walter B (1979) A string matching algorithm fast on the average. In: Proceedings of ICALP. pp 118–132

  33. Fu Z, Li J (2014) Spectral clustering based regular expression grouping. ANCS’14

  34. Fu Z, Wang K, Cai L, Li J (2014) Intelligent grouping algorithms for regular expressions in deep inspection. IEEE/ACM Trans Netw 22:2

    Google Scholar 

  35. Becchi M, Cadambi S (2007) Memory—efficient regular expression search using state merging. In: Proceedings of IEEE INFOCOM

  36. Yu X, Lin B, Becchi M (2014) revisiting state blow up: automatically building augmented-FA while preserving functional equivalence. IEEE J Sel Areas Commun 32:10

    Google Scholar 

  37. Becchi M, Crowley P (2013) A-DFA: a time-and space-efficient DFA compression algorithm for fast regular expression evaluation. ACM Trans Archit Code Optim 10:1. https://doi.org/10.1145/2445572.2445576

    Article  Google Scholar 

  38. Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor

    Google Scholar 

  39. Darwin C (1859) On the origin of species, 6th edn. http://www.gutenberg.org/etext/1228. Accessed 05 Aug 2007

  40. Sumathi S, Surekha P (2010) Computational intelligence paradigms theory and applications using MATLAB. CRC Press, Boca Raton

    Google Scholar 

  41. Mabu S, Hirasawa K, Hu J (2007) A graph-based evolutionary algorithm: genetic network programming (GNP) and its extension using reinforcement learning. Evol Comput 15(3):369–398

    Google Scholar 

  42. Yang XS, Cui ZH, Xiao RB, Gandomi AH, Karamanoglu M (2013) Swarm intelligence and bio-inspired computation: theory and applications. Elsevier, London

    Google Scholar 

  43. Fabera V, Janes V, Janesova M (2006) Automata construct with genetic algorithm. In: Proceedings of 9th Euromicro conference on digital system design. pp 460–463

  44. Niparnan N, Chongstitvatana P (2002) An improved genetic algorithm for the inference of finite state machine. IEEE Int. Conf Syst Man Cybern 7:5. https://doi.org/10.1109/icsmc.2002.1175719

    Article  Google Scholar 

  45. Goldberg DE, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms. Urbana 51:61801–62996

    Google Scholar 

  46. Chivilikhin D, Ulyantsev V (2012) Learning finite state machines with ant colony optimization. In: Proceedings of 8th international conference on swarm intelligence. vol 7461, pp 268–275

  47. Chivilikhin D, Ulyantsev V, Tsarev F (2012) Test-based extended finite-state machines induction with evolutionary algorithms and ant colony optimization. In: GECCO (Companion). pp 603–606

  48. Janakiriman S, Vasudevan V (2009) ACO based distributed intrusion detection system. Int J Digit Content Technol Appl 3(1):66–72

    Google Scholar 

  49. Wang J, Hong X, Ren R, Li T (2009) A real-time intrusion detection system based on PSO-SVM. In: Proceedings of international workshop on information security and application. IWISA, Qingdao, China

  50. Gandomi AH, Yang X-S, Talatahari S, Alavi AH (2013) Metaheuristic Algorithms in modeling and optimization. In: Metaheuristic applications in structures and infrastructures. pp 1–24. https://doi.org/10.1016/B978-0-12-398364-0.00001-2

  51. Robinson J, Rahmat-Samii Y (2004) Particle swarm optimization in electromagnetics. IEEE Trans Antennas Propag 52:2

    MathSciNet  MATH  Google Scholar 

  52. Djemame S, Batouche M (2012) Combining cellular automata and particle swarm optimization for edge detection. Int J Comput Appl 57:14

    Google Scholar 

  53. Bai Q (2010) Analysis of particle swarm optimization algorithm. Comput Inf Sci 3:1

    Google Scholar 

  54. Ghalia MB (2008) Particle swarm optimization with an improved exploration-exploitation balance. In: 51st Midwest symposium on circuits and systems. https://doi.org/10.1109/MWSCAS.2008.4616910

  55. Passino KM (2010) Bacterial foraging optimization. Int J Swarm Intell Res 1:1

    Google Scholar 

  56. Kim DH, Abraham A, Cho JH (2007) A hybrid genetic algorithm and bacterial foraging approach for global optimization. Inf Sci 177(18):3918–3937

    Google Scholar 

  57. Karaboga D, Akay B (2009) A comparative study of artificial bee colony algorithm. Appl Math Comput 214:108–132

    MathSciNet  MATH  Google Scholar 

  58. Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Technical Report TR06, Computer Engineering Department, Engineering Faculty, Erciyes University

  59. Basturk B, Karaboga D (2006) An artificial bee colony (ABC) algorithm for numeric function optimization. In: IEEE swarm intelligence symposium 2006, Indianapolis, Indiana, USA

  60. Chan FTS, Tiwari MK (2007) Swarm intelligence: focus on ant and particle swarm optimization. Itech Education and Publishing, Vienna, p 532. ISBN 978-3-902613-09-7

    Google Scholar 

  61. Akay B, Karaboga D (2012) Artificial bee colony algorithm for large-scale problems and engineering design optimization. J Intell Manuf 23:41001–41014

    Google Scholar 

  62. Civicioglu P, Besdok E (2011) A conceptual comparison of cuckoo-search, particle search optimisation, differential evolution and artificial bee colony algorithms. Springer, Berlin. https://doi.org/10.1007/s10462-011-9276-0

    Book  Google Scholar 

  63. Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Glob Optim 39(3):459–471

    MathSciNet  MATH  Google Scholar 

  64. Gao W, Liu S (2011) Improved artificial bee colony algorithm for global optimization. Inf Process Lett 111(17):871–882

    MathSciNet  MATH  Google Scholar 

  65. Zhu G, Kwong S (2010) Gbest-guided artificial bee colony algorithm for numerical function optimization. Appl Math Comput 217(7):3166–3173

    MathSciNet  MATH  Google Scholar 

  66. Simon D, Ergezer M, Du D, Rarick R (2011) Markov models for biogeography-based optimization. IEEE Trans Syst Man Cybern Part B Cybern 41:1

    MATH  Google Scholar 

  67. Simon D, Ergezer M, Dawei D, Rarick RA (2011) Markov models for biogeography-based optimization. IEEE Trans Syst Man Cybern 41(1):299–306

    MATH  Google Scholar 

  68. Pavlyukevich I (2007) Levy flights, non-local search and simulated annealing. J Comput Phys 226:1830–1844

    MathSciNet  MATH  Google Scholar 

  69. Viswanathan GM, Buldyrev SV, Havlin S, Da Luz MGE, Rapso EP, Stanley HE (1999) Optimizing the success of random searches. Nature 401:911–914

    Google Scholar 

  70. Soneji HR, Sanghvi RC (2014) Towards the improvement of cuckoo search algorithm. Int J Comput Inf Syst Ind Manag Appl 6:77–88

    Google Scholar 

  71. Rajabioun R (2011) Cuckoo optimization algorithm. Appl Soft Comput J 11:85508–85518

    Google Scholar 

  72. Gandomi AH, Yang XS, Alavi AH (2013) Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems. Eng Comput 29:17. https://doi.org/10.1007/s00366-011-0241-y

    Article  Google Scholar 

  73. Yang X-S (2009) Firefly algorithm for multimodal optimization. In: Proceedings of the stochastic algorithms, foundations and applications (SAGA 109), Lecture notes in computer sciences. Springer, p 5792

  74. Farahani SM, Abshouri AA, Nasiri B, Meybodi MR (2011) A gaussian firefly algorithm. Int J Mach Learn Comput 1(5):448–453

    Google Scholar 

  75. Sipper M, Goeke M, Mange D, Stauffer A, Sanchez E, Tomassini M (1997) The firefly machine: online evolware. In: Proceedings of 1997 IEEE international conference on evolutionary computation (ICEC ‘97)

  76. Gandomi AH, Yang X-S, Alavi AH (2011) Mixed variable structural optimization using firefly algorithm. Comput Struct 89(23–24):2325–2336. https://doi.org/10.1016/j.compstruc.2011.08.002

    Article  Google Scholar 

  77. Hassanzadeh T, Meybodi M (2012) A new hybrid algorithm based on firefly algorithm and cellular learning automata. In: 20th Iranian conference on electrical engineering (ICEE2012)

  78. Mohapatra DP (2015) Generating prioritised test sequences using firefly optimization technique. In: Jain LC et al (eds) Computational intelligence in data mining. Springer, vol 2

  79. Yilmaz S, Kucuksille EU (2013) Improved bat algorithm (IBA) on continuous optimization problems. Lecture Notes on Software Engineering 1:3

    Google Scholar 

  80. Tudge C (2000) The variety of life. Oxford University Press, Oxford. ISBN 0-19-850311-3

    Google Scholar 

  81. Yang X-S (2013) Bat algorithm: literature review and applications. Int J Bio-Inspir Comput 5:3141–3149

    Google Scholar 

  82. Huang G-Q, Zhao W-J, Lu Q-Q (2013) Bat algorithm with global convergence for solving large-scale optimization problem. Appl Res Comput 30:10–31

    Google Scholar 

  83. Yang X, Gandomi AH (2012) Bat algorithm: a novel approach for global engineering optimization. Eng Comput 29(5):464–483. https://doi.org/10.1108/02644401211235834

    Article  Google Scholar 

  84. Progias P, Amanatiadis AA, Spataro W, Trunfio GA, Sirakoulis GC (2016) A cellular automata based FPGA realization of a new metaheuristic bat-inspired algorithm. numerical computations: theory and algorithms (NUMTA–2016). In: AIP conference proceedings. https://doi.org/10.1063/1.4965359

  85. Xin-She Y, Mehmet K, Xingshi H (2013) Multi-objective flower algorithm for optimization. In: International conference on computational science, ICCS 2013

  86. Wang R, Zhou Y (2014) Flower pollination algorithm with dimension by dimension improvement. Math Probl Eng. https://doi.org/10.1155/2014/481791

    Article  Google Scholar 

  87. Mantegna RN (1994) Fast accurate algorithm for numerical simulation of levy stable stochastic process. Phys Rev E 49:4677–4683

    Google Scholar 

  88. Back T (1996) Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming and genetic algorithms. Oxford University Press, Oxford

    MATH  Google Scholar 

Download references

Funding

The authors confirm that there is no source of funding for this study.

Author information

Authors and Affiliations

  1. Department of CSE, Rajalakshmi Engineering College, Chennai, Tamil Nadu, India

    Prithi Samuel

  2. Department of EEE, PSG College of Technology, Coimbatore, Tamil Nadu, India

    Sumathi Subbaiyan

  3. School of Computer Science and Engineering, Galgotias University, Greater Noida, India

    Balamurugan Balusamy

  4. School of Computer Science, Vellore Institute of Technology, Amaravati, Andhra Pradesh, India

    Sumathi Doraikannan

  5. Faculty of Engineering & Information Technology, University of Technology Sydney, Ultimo, NSW, Australia

    Amir H. Gandomi

Authors
  1. Prithi Samuel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sumathi Subbaiyan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Balamurugan Balusamy
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sumathi Doraikannan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Amir H. Gandomi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Amir H. Gandomi.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Human Participants and/or Animals

None.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Samuel, P., Subbaiyan, S., Balusamy, B. et al. A Technical Survey on Intelligent Optimization Grouping Algorithms for Finite State Automata in Deep Packet Inspection. Arch Computat Methods Eng 28, 1371–1396 (2021). https://doi.org/10.1007/s11831-020-09419-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11831-020-09419-z

Search

Navigation