Bulletin of TUIT: Management and Communication Technologies


Nowadays the Internet is very massive and the need for a system to protect the networks from being attacked becomes very important. One of the main goals of studying pattern matching techniques is their significant role in real-world applications, such as the intrusion detection systems branch. The purpose of the network attack detection systems NIDS is to protect the infocommunication network from unauthorized access. This article provides an analysis of the exact match and fuzzy matching methods, and discusses a new implementation of the classic Aho-Corasick pattern matching algorithm at the hardware level. The proposed approach to the implementation of the Aho-Corasick algorithm can make it possible to ensure the efficient use of resources, such as memory and energy.




[1] Current Cyber Threats: Results of 2019 - https://www.ptsecurity.com/ru-ru/research/analytics/cybersecurity-threatscape-2019/

[2] Boyer R.S. and Moore, J.S. (1977). A Fast String Searching Algorithm. Communications of ACM, 20(10), pp.762-772.

[3] Knuth, D.E., Morris, J. and Pratt, V.R. (1977). Fast Pattern Matching in Strings. SIAM Journal on Computing. 6(2), pp.323-350

[4] Horspool, R.N. (1980). Practical fast searching in strings. Software: Practice and Experience. 10(6), pp.501-506.

[5] Baeza-Yates, R. and Gonnet, G.H. (1992). A new approach to text searching. Communications of the ACM , 35(10), pp.74-82.

[6] Dharmapurikar, S., Krishnamurthy, P., Sproull, T. and Lockwood, J.W. (2003). Deep Packet Inspection Using Parallel Bloom Filters. Proceedings 11th Symposium on High Performance Interconnects (HotInterconnects). pp.44-51.

[7] Bloom, B.H. (1970). Space/time trade-offs in hash coding with allowable errors. Commun. ACM. 13(7), pp.422-426.

[8] Song, H. and Lockwood, J.W. (2005b). Multi-pattern Signature Matching for Hardware Network Intrusion Detection Systems. IEEE Global Telecommunications Conference GLOBECOM’05. vol.3, 5 pages.

[9] Zhou, Y. and Wang, X. 2010. Efficient Pattern Matching with Counting Bloom Filter. CIICT2010.

[10] Markatos, E., Antonatos, S., Polychronakis, M. and Anagnostakis, K. (2002). Exclusion-based Signature Matching for Intrusion Detection. In Proceedings of IASTED International Conference on Communications and Computer Networks (CCN 2002);

[11] Tharaka PMK, Wijerathne DMD, Perera N, Vishwajith D, Pasqual A. Runtime rule-reconfigurable high throughput NIPS on FPGA. In: International Conference on Field Programmable Technology (ICFPT); 2017. p. 251–4.

[12] Lei S, Wang C, Fang H, Li X, Zhou X. SCADIS: a scalable accelerator for data-intensive string set matching on FPGAs. In: IEEE Trustcom/BigDataSE/ISPA; 2017. p. 1190–7.

[13] Domínguez A, Carballo PP, Nunez A. Programmable SoC platform for deep packet inspection using enhanced boyer-moore algorithm. In: 12th international symposium on reconfigurable communication-centric systems-on-chip (ReCoSoC); 2017. p. 1–8.

[14] Sarbishei I, Vakili S, Langlois JMP, Savaria Y. Scalable memory-less architecture for string matching with FPGAs. In: IEEE International Symposium on Circuits and Systems (ISCAS); 2017. p. 1–4.

[15] Lin CH, Chang SC. Efficient pattern matching algorithm for memory architecture. In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 19; 2011. p. 33–40.

[16] Pontarelli S, Bianchi G, Teofili S. Traffic-aware design of a high-speed FPGA network intrusion detection system. In: IEEE transactions on computers. 62; 2013. p. 2322–33.

[17] Bande JM, Palancar JH, Cumplido R. Multi-character cost-effective and high throughput architecture for content scanning. Microprocess Microsyst 2013;37: 1200–7.

[18] Pao D, Wang X. Multi-stride string searching for high-speed content inspection. Comput J 2012;55:1216–31.

[19] Madhavan A, Sherwood T, Strukov DB. High-throughput pattern matching with CMOL FPGA circuits: case for logic-in-memory computing. In: IEEE transactions on very large scale integration (VLSI) systems. 26; 2018. p. 2759–72.

[20] PAO D, LIN W, LIU B. A memory-efficient pipelined implementation of the Aho-Corasick string-matching algorithm. ACM Trans Architect Code Optimiz 2010;7: 1–27.

[21] Kim H, Choi K, Choi S. A memory-efficient deterministic finite automaton-based bit-split string matching scheme using pattern uniqueness in deep packet inspection. PLoSONE 2015;10:1–24.

[22] Kim HJ, Kim HS, Kang S. A memory-efficient bit-split parallel string matching using pattern dividing for intrusion detection systems. In: IEEE transactions on parallel and distributed systems. 22; 2011. p. 1904–11.

[23] Wang X, Pao D. Memory-based architecture for multicharacter Aho–Corasick string matching. In: IEEE transactions on very large scale integration (VLSI) systems. 26; 2017. p. 143–54.

[24] Kim H. A failureless pipelined Aho-Corasick algorithm for FPGA-based parallel string matching engine. Lect Notes Electric Eng (LNCS) 2015;339:157–64.

[25] Chen CC, Wang S. An efficient multi-character transition string-matching engine based on the Aho-Corasick algorithm. ACM Trans Architect Code Optimiz 2013; 10:1–22.

[26] Chen CC, Wang S. A hybrid multiple-character transition finite-automaton for string matching engine. Microprocess Microsyst 2015;39:1–13.

[27] Serrano JMB, Palancar JH. String alignment pre-detection using unique subsequences for FPGA-based network intrusion detection. Comput Commun 2012;35: 720–8.

[28] Kim H, Choi KI. A pipelined non-deterministic finite automaton-based string matching scheme using merged state transitions in an FPGA. PLoSONE 2016;11: 1–24.

[29] Kaneta Y, Yoshizawa S, Minato SI, Arimura H, Miyanaga Y. Dynamic reconfigurable bit-parallel architecture for large-scale regular expression matching. In: International Conference on Field-Programmable Technology; 2010. p. 21–8.

[30] Roy I, Srivastava A, Nourian M, Becchi M, Aluru S. High performance pattern matching using the automata processor. In: IEEE International Parallel and Distributed Processing Symposium (IPDPS); 2016. p. 1123–32.

[31] Arun M, Krishnan A. Functional verification of signature detection architectures for high speed network applications. Int J Autom Comput 2012;9:395–402.

[32] Xue CJ, Liu M, Zhuge Q, Sha EHM. Variable length pattern matching for hardware network intrusion detection system. J Signal Process Syst 2010;59:85–93.

[33] Thinh TN, Kittitornkun S. Massively parallel cuckoo pattern matching applied for NIDS/NIPS. In: 5th IEEE International Symposium on Electronic Design, Test & Applications, Ho Chi Minh; 2010. p. 217–21.

[34] Erdem G, Carus A. Multi-pipelined and memory-efficient packet classification engines on FPGAs. Comput Commun 2015;67:75–91.

[35] Erdem O. Tree-based string pattern matching on FPGAs. Comput Electric Eng 2016;49:117–33.

[36] Hajiabadi MH, Saidi H, Behdadfar M. Scalable high-throughput and modular hardware based string matching algorithm. In: 11th International ISC Conference on Information Security and Cryptology; 2014. p. 192–8.

[37] Le H, Prasanna VK. A memory-efficient and modular approach for large-scale string pattern matching. IEEE Trans Comput 2013;62:844–57

[38] Aho, A. and M. Corasick (1975). Fast pattern matching: an aid to bibliographic search. In: Communications of the ACM. Vol. 18. pp. 333–340.

[39] Commentz-Walter, B. (1979). A String Matching Algorithm Fast on the Average. Lecture Notes in Computer Science. 71, pp.118-132.

[40] Charras, C. and T. Lecroq (2004). Exact String Matching Algorithms. King’s College London Publications. London, UK.

[41] Navarro, G. and Raffinot, M. (2002). Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences. Cambridge University Press, New York, NY, USA.

[42] Wu, S. and Manber, U. (1994). A fast algorithm for multi-pattern searching. Technical Report TR94-17, Department of Computer Science, University of Arizona, 1994.

[43] Norton, M. (2004). Optimizing Pattern Matching for Intrusion Detection, Sourcefire Inc.;

[44] Tuck, N., Sherwood, T., Calder, B. and Varghese, G. (2004). Deterministic memoryefficient string matching algorithms for intrusion detection. INFOCOM 2004. 4, pp.2628-2639. March 2004.

[45] Tan, L. and Sherwood, T. (2005). A High Throughput String Matching Architecture for Intrusion Detection and Prevention. In Proceedings of the 32nd annual international symposium on Computer Architecture (ISCA '05). pp.112-122.

[46] Sidhu, R. and Prasanna, V.K. (2001). Fast Regular Expression Matching Using FPGAs. In Proceedings of the the 9th Annual IEEE Symposium on FieldProgrammable Custom Computing Machines (FCCM '01). pp.227-238.

[47] Yu, F. and Katz, R.H. (2004). Efficient Multi-Match Packet Classification with TCAM. Proceedings 12th IEEE Symposium on Hot Interconnects (HOTI’04). pp.28-34.

[48] Sung, J., Kang, S., Y. Lee, T. Kwon, and B. Kim (2005). A Multi-gigabit Rate Deep Packet Inspection Algorithm using TCAM. IEEE Global Telecommunications Conference GLOBECOM’05. vol.1, 5 pages.

[49] Bakhodir, Y., Nurbek, N., Odiljon, Z. Methods for applying of scheme of packet filtering rules. International Journal of Innovative Technology and Exploring Engineering. Volume 8, Issue 11, September 2019, Pages 1014-1019

[50] Ganiev, S.K., Irgasheva, D.Y. About of One Methods Synthesis the Structural Protected Computer Network. International Conference on Information Science and Communications Technologies, ICISCT 2019; Tashkent; Uzbekistan; November 2019 6; CFP19H74-ART; 158120;

[51] Rajaboevich, G.S., Saidaminovna, X.C., Irkinovna, G.T., Tagirovna, D.S. Analysis of methods for measuring available bandwidth and classification of network traffic. International Journal of Emerging Trends in Engineering Research. Volume 8, Issue 6, June 2020, Pages 2753-2759;

[52] Karimovich, G.S., Turakulovich, K.Z., Ubaydullayevna, H.I. Computer's source based (Pseudo) random number generation. International Conference on Information Science and Communications Technologies, ICISCT 2017; Tashkent University of Information Technologies (TUIT)Tashkent; Uzbekistan; November 2017; CFP17H74-ART;133832;

[53] Sherzod, G., Dilmurod, A., Nodira, M., Husniya, A. Construction of schemes, models and algorithm for detection network attacks in computer networks. International Journal of Innovative Technology and Exploring Engineering. Volume 8, Issue 12, October 2019, Pages 2234-2241;

[54] Karimov, M., Tashev, K., Yoriqulov, M. Problems of increasing efficiency of NIDS by using implementing methods packet classifications on FPGA. International Conference on Information Science and Communications Technologies, ICISCT 2019; Tashkent; Uzbekistan; November; CFP19H74-ART; 158120;

[55] Akhmatovich, T.K., Turakulovich, K.Z., Tileubayevna, A.J. Improvement of a security enhanced one-time mutual authentication and key agreement scheme. International Journal of Innovative Technology and Exploring Engineering. Volume 8, Issue 12, October 2019, Pages 5031-5036;

[56] Jakub Botwicz ∗ Piotr Buciak ∗ Tadeusz Łuba ∗ Henry Selvaraj ∗∗ Piotr Sapiecha ∗. Aho-Corasick algorithm implementation in hardware for network intrusion detection. IFAC Proceedings Volumes. Volume 37, Issue 20, November 2004, Pages 203-207.

[57] Karimov Madjid, Gulomov Sherzod, Yusupov Bokhodir. Method of constructing packet filtering rules. International conference on information science and communications technologies applications, trends and opportunities (ICISCT). 4-6 November, 2019, Tashkent Uzbekistan.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.