Parallel combining different approaches to multi pattern matching for FPGA-based security systems
| dc.citation.epage | 15 | |
| dc.citation.issue | Volume 5, № 1 | |
| dc.citation.journalTitle | Advances in Cyber-Physical Systems | |
| dc.citation.spage | 7 | |
| dc.contributor.affiliation | Pukhov Institute for Modelling in Energy Engineering | |
| dc.contributor.author | Hilgurt, Sergii | |
| dc.date.accessioned | 2022-11-28T09:35:46Z | |
| dc.date.available | 2022-11-28T09:35:46Z | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2022 | |
| dc.description.abstract | The multi-pattern matching is a fundamental technique found in applications like a network intrusion detection system, anti-virus, anti-worms and other signature based information security tools. Due to rising traffic rates, increasing number and sophistication of attacks and the collapse of Moore's law, traditional software solutions can no longer keep up. Therefore, hardware approaches are frequently being used by developers to accelerate pattern matching. Reconfigurable FPGA-based devices, providing the flexibility of software and the near-ASIC performance, have become increasingly popular for this purpose. Hence, increasing the efficiency of reconfigurable information security tools is a scientific issue now. Many different approaches to constructing hardware matching circuits on FPGAs are known. The most widely used of them are based on discrete comparators, hash functions and finite automata. Each approach possesses its own pros and cons. None of them still became the leading one. In this paper, a method to combine several different approaches to enforce their advantages has been developed. An analytical technique to quickly advance estimate the resource costs of each matching scheme without need to compile FPGA project has been proposed. It allows to apply optimization procedures to near-optimally split the set of pattern between different approaches in acceptable time. | |
| dc.format.pages | 7-15 | |
| dc.identifier.citation | Hilgurt S. Parallel combining different approaches to multi pattern matching for FPGA-based security systems / Sergii Hilgurt // Advances in Cyber-Physical Systems. – Lviv : Lviv Politechnic Publishing House, 2020. – Volume 5, № 1. – P. 7–15 . – Bibliography: 34 titles. | |
| dc.identifier.uri | https://ena.lpnu.ua/handle/ntb/57224 | |
| dc.language.iso | en | |
| dc.publisher | Lviv Politechnic Publishing House | |
| dc.relation.ispartof | Advances in Cyber-Physical Systems | |
| dc.relation.references | [1] ChenH., ChenY. , and Summerville D. H., “A Survey on the Application of FPGAs for Network Infrastructure Security”, IEEE Communications Surveys and Tutorials, Article vol. 13, no. 4, pp. 541–561, 2011, doi: 10.1109/surv.2011.072210. 00075. [2] Hilhurt S. Y., “Application of FPGA-based reconfigurable accelerators for network security tasks”, Modeling andinformation technologies. Collection of scientific works of PIMEE NAS of Ukraine, no. 73, pp. 17–26, 2014. [3] Paxson V. et al., “Rethinking hardware support for network analysis and intrusion prevention”, presented at the USENIX First Workshop on Hot Topics in Security (HotSec), Vancouver, July 31, 2006. [4] Smyth B., Computing Patterns in Strings. Essex: Pearson Addison Wesley, 2003. [5] Lewis H. R. and Papadimitriou C. H., Elements of the Theory of the Computations, 2nd ed. Prentice-Hall, 1998. [6] Kazmirchuk S., Korchenko A., and Paraschuk T., “Analysis of intrusion detection systems”, Ukrainian Information Security Research Journal, vol. 20, no. 4, pp. 259–276, 2018, (in Ukrainian), doi: 10.18372/2410-7840.20.13425. [7] Korostil J. M. and Hilgurt S. Y., “Principles of building FPGA-based network intrusion detection systems”, Modeling and information technologies. Collection of scientific works of PIMEE NAS of Ukraine, no. 57, pp. 87–94, 2010, (in Russian). [8] Katashita T., Yamaguchi Y., Maeda A. and Toda K., “FPGA-based intrusion detection system for 10 Gigabit Ethernet”, IEICE Transactions on Information and Systems, Article vol. E90D, no. 12, pp. 1923–1931, Dec 2007, doi: 10.1093/ietisy/e90-d.12.1923. [9] Hilgurt S., “Constructing optimal reconfigurable pattern matching tools for information security”, Ukrainian Scientific Journal of Information Security, vol. 25, no. 2, pp. 74–81, 2019, (in Ukrainian), doi: 10.18372/2225- 5036.25.13824. [10] Guccione S. A., Levi D., and Downs D., “A reconfi gurable content addressable memory”, Parallel and Distributed Processing, Proceedings, Article; Proceedings Paper vol. 1800, pp. 882–889, 2000. [11] Cho Y. H., Navab S., and Mangione-Smith W. H., “Spe cialized hardware for deep network packet filtering”, Field-Programmable Logic and Applications, Procee dings: Reconfigurable Computing Is Going Mainstream, Article; Proceedings Paper vol. 2438, pp. 452–461, 2002. [12] Sourdis I. and Pnevmatikatos D., “Fast, large-scale string match for a 10Gbps FPGA-based network Intrusion Detection System”, Field-Programmable Logic and Applica tions, Proceedings, Article; Proceedings Paper vol. 2778, pp. 880–889, 2003. [13] Y. H. Cho and W. H. Mangione-Smith, “Deep packet filter with dedicated logic and read only memories”, 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Proceedings, Proceedings Paper pp. 125–134, 2004, doi: 10.1109/fccm.2004.25. [14] Sourdis I. and Pnevmatikatos D., “Pre-decoded CAMs for efficient and high-speed NIDS pattern matching”, 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Proceedings, Proceedings Paper pp. 258–267, 2004, doi: 10.1109/fccm.2004.46. [15] Sourdis I., Pnevmatikatos D. N. and Vassiliadis S., “Scalable multigigabit pattern matching for packet inspection”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Article vol. 16, no. 2, pp. 156–166, Feb 2008, doi: 10.1109/tvls1.2007.912036. [16] Bloom B. H., “Space/Time Trade-offs in Hash Coding with Allowable Errors”, Communications of the ACM, Article vol. 13, no. 7, pp. 422–426, 1970, doi: 10.1145/362686.362692. [17] Fan L., Cao P., Almeida J., and Broder A. Z., “Summary cache: A scalable wide-area Web cache sharing protocol”, IEEE - ACM Transactions on Networking, Article vol. 8, no. 3, pp. 281–293, Jun 2000, doi: 10.1109/90.851975. [18] Dharmapurikar S., Krishnamurthy P., Sproull T. S. and Lockwood J. W., “Deep packet inspection using parallel bloom filters”, IEEE Micro, Article; Proceedings Paper vol. 24, no. 1, pp. 52–61, Jan-Feb 2004, doi: 10.1109/mm.2004.1268997. [19] Dharmapurikar S., Attig M. and Lockwood J., “Design and Implementation of a String Matching System for Network Intrusion Detection using FPGA-based Bloom Filters”, in All Computer Science and Engineering Research, Washington University in St. Louis, WUCSE-2004-12, 2004-03-25 2004. [20] J. Harwayne-Gidansky, D. Stefan, and I. Dalal, “FPGA based SoC for Real-Time Network Intrusion Detection using Counting Bloom Filters”, presented at the Proceedings of the IEEE SoutheastCon 2009, Technical Proceedings, 2009, Proceedings Paper. [21] Geravand S. and Ahmadi M., “Bloom filter applications in network security: A state-of-the-art survey”, Computer Networks, Article vol. 57, no. 18, pp. 4047–4064, Dec 2013, doi: 10.1016/j.comnet.2013.09.003. [22] Aho A. V. and Corasick M. J., “Efficient String Matching: An Aid to Bibliographic Search”, Communications of the ACM, vol. 18, no. 6, pp. 333–340, 1975, doi: 10.1145/360825.360855. [23] Lunteren J., “High-performance pattern-matching for intrusion detection”, 25th IEEE International Conference on Computer Communications, Vols 1-7, Proceedings IEEE Infocom 2006, Proceedings Paper pp. 1409-1421, 2006. [24] Lin C., Y. Tai, and Chang S., “Optimization of pattern matching algorithm for memory based architecture”, presented at the Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, Orlando, Florida, USA, 2007. [25] Pao D., Lin W. and Liu B., “Pipelined architecture for multi-string matching”, IEEE Computer Architecture Letters, vol. 7, no. 2, pp. 33–36, 2008, doi: 10.1109/ L-CA.2008.5. [26] Jiang W., Yang Y. H. E. and Prasanna V. K., “Scalable multi-pipeline architecture for high performance multi-pattern string matching”, in 24th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2010, Atlanta, GA, 2010, doi: 10.1109/IPDPS.2010.5470374. [27] Lin C. H. and Chang S. C., “Efficient Pattern Matching Algorithm for Memory Architecture”, IEEE Transac tions on Very Large Scale Integration (VLSI) Systems, Article vol. 19, no. 1, pp. 33–41, Jan 2011, doi: 10.1109/tvlsi.2009. 2028346. [28] Hilgurt S. Y., “Constructing CAM on discrete comparators by reconfigurable means for solving information security tasks”, Electronic Modeling, vol. 41, no. 3, pp. 59–80, 2019, (in Ukrainian), doi: 10.15407/emodel.41.03.059. [29] Hilgurt S., “Constructing Bloom filters by reconfigurable means for solving information security tasks”, Ukrainian Scientific Journal of Information Security, vol. 35, no. 1, pp. 53–58, 2019, (in Ukrainian), doi: 10.18372/2225- 5036.25.13594. [30] Hilgurt S., “Constructing deterministic finite automata by reconfigurable means forsolving information security Tasks”, Ukrainian Information Security Research Journal, vol. 21, no. 2, pp. 111–120, 2019, (in Ukrainian), doi: 10.18372/2410-7840.21.13768. [31] Evdokimov V. F., Davydenko A. M. and Hilgurt S. Y., “Or ganization of centralized generation of bitstreamsfor hardware accelerators for information security tasks”, Modeling and information technologies. Collection of scientific works of PIMEE NAS of Ukraine, no. 81, pp. 3–11, 2017, (inRussian) . [32] Huang J., Yang Z. K., Du X., and Liu W., “FPGA based high speed and low area cost pattern matching”, in IEEE Region 10 Conference (TENCON 2005), Melbourne, AUSTRALIA, Nov 21-24 2005, NEW YORK: IEEE, 2006, pp. 2693–2697. [33] Hilgurt S. Y., Kislov O. G., Popova V. M. and Liakh I. M., “Accelerated calculation of characteristics of reconfigurable matching schemes based on CAM and digital comparators”, Modeling and information technologies. Collection of scientific works of PIMEE NAS of Ukraine, no. 89, pp. 3–16, 2019, (in Ukrainian). [34] Evdokimov V. F., Davydenko A. M., Hilgurt S. Y. and Yarema O. R., “Hardware platform for reconfigurable information security tools”, Modeling and information technologies. Collection of scientific works of PIMEE NAS of Ukraine, no. 86, pp. 3–11, 2019, (in Ukrainian), doi: 10.5281/zenodo.610626. | |
| dc.subject | mbining approaches, DPI, FPGA, infor mation security, multi-pattern matching, signature | |
| dc.title | Parallel combining different approaches to multi pattern matching for FPGA-based security systems | |
| dc.type | Article |
Files
Original bundle
1 - 1 of 1