S.Ya. Hilgurt
Èlektron. model. 2019, 41(3):59-80
ABSTRACT
Such information security means as Network Intrusion Detection Systems (NIDS) inspect theSuch information security means as Network Intrusion Detection Systems (NIDS) inspect thenetwork packet payload to search malicious content. This process, deep packet inspection, involvesdetection of predefined signature strings. A computationally intensive task of stringmatching becomes a bottleneck of network defense facilities. Since conventional software-basedstring matching tools have not kept pace with the increasing network speeds, hardware solutionsbases on Field Programmable Gate Arrays (FPGAs) have been introduced to solve this problem.There are several different methods for constructing hardware matching schemes on FPGAs. Oneof the most popular methods is based on Content-Addressable Memory (CAM) and underlyingdigital comparators. In this paper, a comprehensive analysis of this method is fulfilled. The keyfeatures of CAMs, their pros and cons, specifics of realization in hardware as well as encounteredproblems and ways to overcome them are investigated in details. The results obtained contributeto the effective constructing FPGA-based information security means.
KEYWORDS
NIDS, DPI, string matching, FPGA, CAM, digital comparator.
REFERENCES
1. Smyth, B. (2003), Computing Patterns in Strings, Pearson Addison Wesley.
2. Hilhurt, S.Ya. (2014), “Application of FPGA-based reconfigurable accelerators for network security tasks”, Simulation and informational technologies PIMEE NAS of Ukraine, Vol. 73, pp. 17-26.
3. Evdokimov, V.F., Davydenko, A.N. and Hilgurt, S.Ya. (2018), “Synthesis of reconfigurable information security hardware on HPC platforms”, Ukrainian information security research journal, Vol. 20, no. 4, pp. 247-258.
4. Hilhurt, S.Ya. (2018), “The use of reconfigurable accelerator for speed-up of signaturebased information security systems“, Simulation-2018, Ukraine, Kyiv, PMEE NAS of Ukraine, pp. 107-110.
5. Teuvo, K. (1987), Content-Addressable Memories, Berlin , Germany.
6. Robinson, I.N. (1992), “Pattern-addressable memory”, IEEE Micro, Vol. 12, no. 3, pp. 20-30.
https://doi.org/10.1109/40.141600
7. Pagiamtzis, K. and Sheikholeslami, A. (2006), “Content-addressable memory (CAM), circuits and architectures:Atutorial and survey”, IEEE Journal of Solid-State Circuits, Vol. 41, no. 3, pp. 712-727.
https://doi.org/10.1109/JSSC.2005.864128
8. Neale, R. (1999), “Is content addressable memory (CAM), the key to network success?”, Electronic Engineering, Vol. 71, no. 865, pp. 9-12.
9. NetLogic Microsystems, available at: https://web.archive.org/web/20120207195938/, http://www.netlogicmicro.com (accessed May 17, 2019).
10. MUSIC-IC, available at: https://www.music-ic.com (accessed May 17, 2019).
11. Guccione, S.A., Levi, D. and Downs, D. (2000), “A reconfigurable content addressable memory”, Parallel and Distributed Processing, Proceedings, Vol. 1800, pp. 882-889.
https://doi.org/10.1007/3-540-45591-4_122
12. Yu, F., Katz, R.H. and Lakshman, T.V. (2004), “Gigabit rate packet pattern-matching using TCAM”, Proceeding of 12th IEEE International Conference on Network Protocols, 2004, pp. 174-183.
13. Sung, J.S., Kang, S.M. and Lee, Y. (2005), “A multi-gigabit rate deep packet inspection algorithm using TCAM”, Proceeding of IEEE Global Telecommunications Conference (GLOBECOM 05), 2005, Vol. 1, pp. 453-457.
14. Bispo, J., Sourdis, L., Cardoso, J.M.P. and Vassiliadis, S. (2006), “Regular expression matching for reconfigurable packet inspectio”, Proceeding of 2006 IEEE International Conference on Field Programmable Technology, 2006, Bangkok, Thailand, pp. 119-126.
https://doi.org/10.1109/FPT.2006.270302
15. SNORT, available at: http://www.snort.org. (accessed May 17, 2019).
16. ClamAV, available at: http://www.clamav.net (accessed May 17, 2019).
17. Hilhurt, S.Ya. (2013), “Reconfigurable accelerators: Analytical review”, Elektronnoye modelirovaniye, Vol. 35, no. 4, pp. 49-72.
18. Iliopoulos, M. and Antonakopoulos, T. (2000), “Reconfigurable network processors based on field programmable system level integrated circuits C3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)”, Proceeding of 10th International Conference on Field-Programmable Logic and Applications, (FPL 2000), Vol. 1896, pp. 39-47.
https://doi.org/10.1007/3-540-44614-1_5
19. Bos, H. and Huang, K. (2004), A network instruction detection system on IXP1200 network processors with support for large rule sets.
20. Xinidis, K., Anagnostakis, K.G. and Markatos, E.P. (2005), “Design and implementation of a high-performance network intrusion prevention system C3 - IFIP Advances in Information and Communication Technology”, Proceeding of 20th International Information Security Conference, (IFIP/SEC2005), 2005, Chiba, pp. 359-374.
https://doi.org/10.1007/0-387-25660-1_24
21. Sourdis, I. and Pnevmatikatos, D. (2003), “Fast, large-scale string match for a 10Gbps FPGA-based network Intrusion Detection System”, Proceeding of Field-Programmable Logic and Applications, 2003, Vol. 2778, pp. 880-889.
https://doi.org/10.1007/978-3-540-45234-8_85
22. Cho, Y.H. and Mangione-Smith, W.H. (2004), “Deep packet filter with dedicated logic and read only memories”, Proceeding of 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2004, Napa, USA, pp. 125-134.
2. Hilhurt, S.Ya. (2014), “Application of FPGA-based reconfigurable accelerators for network security tasks”, Simulation and informational technologies PIMEE NAS of Ukraine, Vol. 73, pp. 17-26.
3. Evdokimov, V.F., Davydenko, A.N. and Hilgurt, S.Ya. (2018), “Synthesis of reconfigurable information security hardware on HPC platforms”, Ukrainian information security research journal, Vol. 20, no. 4, pp. 247-258.
4. Hilhurt, S.Ya. (2018), “The use of reconfigurable accelerator for speed-up of signaturebased information security systems“, Simulation-2018, Ukraine, Kyiv, PMEE NAS of Ukraine, pp. 107-110.
5. Teuvo, K. (1987), Content-Addressable Memories, Berlin , Germany.
6. Robinson, I.N. (1992), “Pattern-addressable memory”, IEEE Micro, Vol. 12, no. 3, pp. 20-30.
https://doi.org/10.1109/40.141600
7. Pagiamtzis, K. and Sheikholeslami, A. (2006), “Content-addressable memory (CAM), circuits and architectures:Atutorial and survey”, IEEE Journal of Solid-State Circuits, Vol. 41, no. 3, pp. 712-727.
https://doi.org/10.1109/JSSC.2005.864128
8. Neale, R. (1999), “Is content addressable memory (CAM), the key to network success?”, Electronic Engineering, Vol. 71, no. 865, pp. 9-12.
9. NetLogic Microsystems, available at: https://web.archive.org/web/20120207195938/, http://www.netlogicmicro.com (accessed May 17, 2019).
10. MUSIC-IC, available at: https://www.music-ic.com (accessed May 17, 2019).
11. Guccione, S.A., Levi, D. and Downs, D. (2000), “A reconfigurable content addressable memory”, Parallel and Distributed Processing, Proceedings, Vol. 1800, pp. 882-889.
https://doi.org/10.1007/3-540-45591-4_122
12. Yu, F., Katz, R.H. and Lakshman, T.V. (2004), “Gigabit rate packet pattern-matching using TCAM”, Proceeding of 12th IEEE International Conference on Network Protocols, 2004, pp. 174-183.
13. Sung, J.S., Kang, S.M. and Lee, Y. (2005), “A multi-gigabit rate deep packet inspection algorithm using TCAM”, Proceeding of IEEE Global Telecommunications Conference (GLOBECOM 05), 2005, Vol. 1, pp. 453-457.
14. Bispo, J., Sourdis, L., Cardoso, J.M.P. and Vassiliadis, S. (2006), “Regular expression matching for reconfigurable packet inspectio”, Proceeding of 2006 IEEE International Conference on Field Programmable Technology, 2006, Bangkok, Thailand, pp. 119-126.
https://doi.org/10.1109/FPT.2006.270302
15. SNORT, available at: http://www.snort.org. (accessed May 17, 2019).
16. ClamAV, available at: http://www.clamav.net (accessed May 17, 2019).
17. Hilhurt, S.Ya. (2013), “Reconfigurable accelerators: Analytical review”, Elektronnoye modelirovaniye, Vol. 35, no. 4, pp. 49-72.
18. Iliopoulos, M. and Antonakopoulos, T. (2000), “Reconfigurable network processors based on field programmable system level integrated circuits C3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)”, Proceeding of 10th International Conference on Field-Programmable Logic and Applications, (FPL 2000), Vol. 1896, pp. 39-47.
https://doi.org/10.1007/3-540-44614-1_5
19. Bos, H. and Huang, K. (2004), A network instruction detection system on IXP1200 network processors with support for large rule sets.
20. Xinidis, K., Anagnostakis, K.G. and Markatos, E.P. (2005), “Design and implementation of a high-performance network intrusion prevention system C3 - IFIP Advances in Information and Communication Technology”, Proceeding of 20th International Information Security Conference, (IFIP/SEC2005), 2005, Chiba, pp. 359-374.
https://doi.org/10.1007/0-387-25660-1_24
21. Sourdis, I. and Pnevmatikatos, D. (2003), “Fast, large-scale string match for a 10Gbps FPGA-based network Intrusion Detection System”, Proceeding of Field-Programmable Logic and Applications, 2003, Vol. 2778, pp. 880-889.
https://doi.org/10.1007/978-3-540-45234-8_85
22. Cho, Y.H. and Mangione-Smith, W.H. (2004), “Deep packet filter with dedicated logic and read only memories”, Proceeding of 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2004, Napa, USA, pp. 125-134.
https://doi.org/10.1109/FCCM.2004.25
23. Huang, J., Yang, Z.K., Du, X. and Liu, W. (2005), “FPGA based high speed and low area cost pattern matching”, Proceeding of IEEE Region 10 Conference (TENCON 2005), 2005, Nov 21-24, Melbourne, Australia, pp. 2693-2697.
https://doi.org/10.1109/TENCON.2005.300988
24. Sourdis, I. and Pnevmatikatos, D. (2004), “Pre-decoded CAMs for efficient and high-speed NIDS pattern matching”, Proceeding of 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2004, pp. 258-267.
https://doi.org/10.1109/FCCM.2004.46
25. Xilinx, “Virtex-II Platform FPGAs: Complete Data Sheet. Product Specification”, available at: https://www.xilinx.com/support/documentation/data_sheets/ds031.pdf (accessed May 17, 2019).
26. Clark, C.R. and Schimmel, D.E. (2003), “Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns”, Proceeding of Field-Programmable Logic and Applications, 2003, Vol. 2778, pp. 956-959.
https://doi.org/10.1007/978-3-540-45234-8_94
27. Clark, C.R. and Schimmel, D.E. (2004), “Scalable pattern matching for high speed networks”, Proceeding of 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2004, pp. 249-257.
https://doi.org/10.1109/FCCM.2004.50
28. Sourdis, I., Pnevmatikatos, D.N. and Vassiliadis, S. (2008), “Scalable multigigabit pattern matching for packet inspection”, IEEE Transactions on Very Large Scale Integration (VLSI), Systems, Vol. 16, no. 2, pp. 156-166.
https://doi.org/10.1109/TVLSI.2007.912036
29. Yusuf, S. and Luk, W. (2005), “Bitwise optimisedCAMfor network intrusion detection systems”, Proceedings of International Conference on Field Programmable Logic and Applications, 2005, Tampere, pp. 444-449.
https://doi.org/10.1109/FPL.2005.1515762
30. Knut, D.E. (2011), The Art of Computer Programmin, Vol. 4A, Combinatorial Algorithms, part 1, Vilyams, Moscow, Russia.
31. Hazelhurst, S., Fatti, A. and Henwood, A. (1998), Binary decision diagram representations of firewall and router access lists, Johannesburg , South Africa.
32. Guccione, S.A. and Levi, D. (1998), “XBI: A Java-based interface to FPGA hardware”, Proceedings of the Society of Photo-Optical Instrumentation Engineers (SPIE), 1998, Boston, Soc Optical Engineering, Vol. 3526, pp. 97-102.
https://doi.org/10.1117/12.327023
33. Hilgurt, S.Ya., Durnyak, B.V. and Korostil, Yu.M. (2014), “Intrusion detection systems defense against algorithmic complexity attacks”, Modelyuvannya ta informatsiyni tekhnolohiyi, Vol. 71, pp. 3-12.
23. Huang, J., Yang, Z.K., Du, X. and Liu, W. (2005), “FPGA based high speed and low area cost pattern matching”, Proceeding of IEEE Region 10 Conference (TENCON 2005), 2005, Nov 21-24, Melbourne, Australia, pp. 2693-2697.
https://doi.org/10.1109/TENCON.2005.300988
24. Sourdis, I. and Pnevmatikatos, D. (2004), “Pre-decoded CAMs for efficient and high-speed NIDS pattern matching”, Proceeding of 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2004, pp. 258-267.
https://doi.org/10.1109/FCCM.2004.46
25. Xilinx, “Virtex-II Platform FPGAs: Complete Data Sheet. Product Specification”, available at: https://www.xilinx.com/support/documentation/data_sheets/ds031.pdf (accessed May 17, 2019).
26. Clark, C.R. and Schimmel, D.E. (2003), “Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns”, Proceeding of Field-Programmable Logic and Applications, 2003, Vol. 2778, pp. 956-959.
https://doi.org/10.1007/978-3-540-45234-8_94
27. Clark, C.R. and Schimmel, D.E. (2004), “Scalable pattern matching for high speed networks”, Proceeding of 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2004, pp. 249-257.
https://doi.org/10.1109/FCCM.2004.50
28. Sourdis, I., Pnevmatikatos, D.N. and Vassiliadis, S. (2008), “Scalable multigigabit pattern matching for packet inspection”, IEEE Transactions on Very Large Scale Integration (VLSI), Systems, Vol. 16, no. 2, pp. 156-166.
https://doi.org/10.1109/TVLSI.2007.912036
29. Yusuf, S. and Luk, W. (2005), “Bitwise optimisedCAMfor network intrusion detection systems”, Proceedings of International Conference on Field Programmable Logic and Applications, 2005, Tampere, pp. 444-449.
https://doi.org/10.1109/FPL.2005.1515762
30. Knut, D.E. (2011), The Art of Computer Programmin, Vol. 4A, Combinatorial Algorithms, part 1, Vilyams, Moscow, Russia.
31. Hazelhurst, S., Fatti, A. and Henwood, A. (1998), Binary decision diagram representations of firewall and router access lists, Johannesburg , South Africa.
32. Guccione, S.A. and Levi, D. (1998), “XBI: A Java-based interface to FPGA hardware”, Proceedings of the Society of Photo-Optical Instrumentation Engineers (SPIE), 1998, Boston, Soc Optical Engineering, Vol. 3526, pp. 97-102.
https://doi.org/10.1117/12.327023
33. Hilgurt, S.Ya., Durnyak, B.V. and Korostil, Yu.M. (2014), “Intrusion detection systems defense against algorithmic complexity attacks”, Modelyuvannya ta informatsiyni tekhnolohiyi, Vol. 71, pp. 3-12.
Full text: PDF