1. ACPS
  2. All Volumes and Issues
  3. Volume 5, Number 1, 2020
  4. Parallel Combining Different Approaches to Multi-pattern Matching for Fpga-based Security Systems

Parallel Combining Different Approaches to Multi-pattern Matching for Fpga-based Security Systems

ACPS.
2020;
Volume 5, Number 1
: pp. 8 - 15
https://doi.org/10.23939/acps2020.01.008
Authors:
  1. Sergii Hilgurt
1
Pukhov Institute for Modelling in Energy Engineering, Ukraine

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.

combining approaches
DPI
FPGA
information security
multi-pattern matching
signature
  1. H. Chen, Y. Chen, and D. H. Summerville, "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. https://doi.org/10.1109/SURV.2011.072210.00075
  2. S. Y. Hilhurt, "Application of FPGA-based reconfigurable accelerators for network security tasks," Modeling and information technologies. Collection of scientific works of PIMEE NAS of Ukraine, no. 73, pp. 17-26, 2014.
  3. V. Paxson 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. B.  Smyth, Computing Patterns in Strings. Essex:  Pearson Addison Wesley, 2003.
  5. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of the Computations, 2nd ed. Prentice-Hall, 1998.
  6. S. Kazmirchuk, A. Korchenko, and T. Paraschuk, "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. https://doi.org/10.18372/2410-7840.20.13425
  7. J. M. Korostil and S. Y. Hilgurt, "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. T. Katashita, Y. Yamaguchi, A. Maeda, and K. Toda, "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. https://doi.org/10.1093/ietisy/e90-d.12.1923
  9. S. Hilgurt, "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. https://doi.org/10.18372/2225-5036.25.13824
  10. S. A. Guccione, D. Levi, and D. Downs, "A reconfigurable content addressable memory," Parallel and Distributed Processing, Proceedings, Article; Proceedings Paper vol. 1800, pp. 882-889, 2000. https://doi.org/10.1007/3-540-45591-4_122
  11. Y. H. Cho, S. Navab, and W. H. Mangione-Smith, "Specialized hardware for deep network packet filtering," Field- Programmable Logic and Applications, Proceedings: Reconfigurable Computing Is Going Mainstream, Article; Proceedings Paper vol. 2438, pp. 452-461, 2002. https://doi.org/10.1007/3-540-46117-5_48
  12. I. Sourdis and D. Pnevmatikatos, "Fast, large-scale string match for a 10Gbps FPGA-based network Intrusion Detection System," Field-Programmable Logic and Applications, Proceedings, Article; Proceedings Paper vol. 2778, pp. 880- 889, 2003. https://doi.org/10.1007/978-3-540-45234-8_85
  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. https://doi.org/10.1109/FCCM.2004.25
  14. I. Sourdis and D. Pnevmatikatos, "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. https://doi.org/10.1109/FCCM.2004.46
  15. I. Sourdis, D. N. Pnevmatikatos, and S. Vassiliadis, "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. https://doi.org/10.1109/TVLSI.2007.912036
  16. B. H. Bloom, "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. https://doi.org/10.1145/362686.362692
  17. L. Fan, P. Cao, J. Almeida, and A. Z. Broder, "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. https://doi.org/10.1109/90.851975
  18. S. Dharmapurikar, P. Krishnamurthy, T. S. Sproull, and J. W. Lockwood, "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. S. Dharmapurikar, M. Attig, and J. Lockwood, "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. S. Geravand and M. Ahmadi, "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. A. V. Aho and M. J. Corasick, "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. J. Lunteren, "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. C. Lin, Y. Tai, and S. Chang, "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. D. Pao, W. Lin, and B. Liu, "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. W. Jiang, Y. H. E. Yang, and V. K. Prasanna, "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. C. H. Lin and S. C. Chang, "Efficient Pattern Matching Algorithm for Memory Architecture," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Article vol. 19,  no.  1,  pp.  33-41,  Jan  2011,  doi:  10.1109/tvlsi.2009.2028346.
  28. S. Y. Hilgurt, "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. S. Hilgurt, "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. S. Hilgurt, "Constructing deterministic finite automata by reconfigurable means for solving 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. V. F. Evdokimov, A. M. Davydenko, and S. Y. Hilgurt, "Organization of centralized generation of bitstreams for 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, (in Russian).
  32. J. Huang, Z. K. Yang, X. Du, and W. Liu, "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. S. Y. Hilgurt, O. G. Kislov, V. M. Popova, and I. M. Liakh "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. V.  F.  Evdokimov,  A.  M.  Davydenko,  S.  Y.  Hilgurt,  and O. R. Yarema, "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.