Derin Paket İncelemesi için Önerilen Yeni Bir Örüntü Eşleştirme Algoritması

Derin Paket İnceleme (Deep Packet Inspection-DPI), hem paket başlığı hem de paket yükü üzerinde ayrıntılı analizler gerçekleştirerek ağ trafiğinin tam görünürlüğünü sağlayan teknolojidir. DPI ile iyi bilinen kötü amaçlı yazılım imzaları ve saldırı sırası, saldırganın izlediği yol ve kullandığı tekniklerin birleşimi olarak tanımlanan saldırı deseninin tespiti yapılabilmektedir. Bu doğrultuda, ağ güvenliği veya devlet gözetimi gibi uygulamalarda kullanılabilmesi yönüyle DPI, kritik bir öneme sahiptir. Bu çalışmada, tek seferde taranan bayt sayısını artırarak DPI sürecini hızlandırmayı amaçlayan blok tabanlı bir örüntü eşleştirme algoritması önerilmiştir. Farklı sayıda örüntü içeren veri kümeleri kullanılarak Aho-Corasick (AC), Rabin-Karp (RK), Wu-Manber (WM) ve bu çalışmada önerilen algoritma üzerinde örüntü eşleştirme testleri gerçekleştirilmiş ve bu algoritmaların performansları karşılaştırılmıştır. AC, WU ve RK algoritmalarına kıyasla bu çalışmada önerilen algoritma, daha yüksek bir performans göstermiştir.

Anahtar Kelimeler:

Derin paket inceleme, Örüntü eşleştirme, Ağ güvenliği, Ağ trafiği analizi

A New Pattern Matching Algorithm for Deep Packet Inspection

Deep Packet Inspection (DPI) is a technology that provides full visibility into network traffic by performing detailed analysis on both packet header and packet payload. DPI technique is used to detect well-known malware signatures. Additionally, the attack pattern which includes the attack order, the path followed by the attacker and the techniques used by the attacker can be detected. Accordingly, DPI has a critical importance as it can be used in applications i.e network security or government surveillance. In this study, a block-based pattern matching algorithm is proposed, which aims to speed up the DPI process by increasing the number of bytes scanned at once. Pattern matching tests are performed on Aho-Corasick (AC), Wu-Manber (WM), Rabin-Karp (RK) algorithms and the algorithm in this study by using datasets containing different numbers of patterns, and the performances of these algorithms are compared. Compared to the AC, RK and WM algorithms, the proposed algorithm in this study has a higher performance.

Keywords:

Deep packet inspection, Pattern matching, Network security, Network traffic analysis,

PDF

___

[1] M. Abbasi, A. Shahraki, and A. Taherkordi, "Deep learning for network traffic monitoring and analysis (NTMA): A survey," Computer Communications, vol. 170, pp. 19-41, 2021.
[2] G. A. Pimenta Rodrigues, R. de Oliveira Albuquerque, F. E. Gomes de Deus, R. T. de Sousa Jr, G. A. de Oliveira Júnior, L. J. Garcia Villalba, and T. H. Kim, “Cybersecurity and network forensics: Analysis of malicious traffic towards a honeynet with deep packet inspection,” Applied Sciences, vol. 7, no. 10, pp. 1082, 2017.
[3] C. Xu, S. Chen, J. Su, S. M. Yiu, and L. C. Hui, “A survey on regular expression matching for deep packet inspection: Applications, algorithms, and hardware platforms,” IEEE Communications Surveys & Tutorials, vol. 18, no. 4, pp. 2991-3029, 2016.
[4] H. Tahaei, F. Afifi, A. Asemi, F. Zaki, and N. B. Anuar, “The rise of traffic classification in IoT networks: A survey,” Journal of Network and Computer Applications, vol. 154, 102538, 2020.
[5] C. Parsons, Deep Packet Inspection in Perspective: Tracing its lineage and surveillance potentials, Kingston, Canada: Surveillance Studies Centre, Queen's University, 2008.
[6] X. de Carné de Carnavalet, and P. C. van Oorschot, “A survey and analysis of TLS interception mechanisms and motivations,” arXiv e-prints, 2020.
[7] S. Canard, A. Diop, N. Kheir, M. Paindavoine, and M. Sabt, “BlindIDS: Market-compliant and privacy-friendly intrusion detection system over encrypted traffic,” In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pp. 561-574, 2017.
[8] A. D’Alconzo, I. Drago, A. Morichetta, M. Mellia, and P. Casas, (2019). “A survey on big data for network traffic monitoring and analysis,” IEEE Transactions on Network and Service Management, vol. 16, no. 3, pp. 800-813, 2019.
[9] R. Topolski, F. Press, and P. Knowledge, NebuAd and partner ISPs: Wiretapping, forgery and browser hijacking, Washington DC: FreePress, 2008.
[10] M. R. Shahid, G. Blanc, Z. Zhang, and H. Debar, “IoT devices recognition through network traffic analysis,” presented at 2018 IEEE international conference on big data, pp. 5187-5192, IEEE, 2018.
[11] M. Finsterbusch, C. Richter, E. Rocha, J. A. Muller, and K. Hanssgen, “A survey of payload-based traffic classification approaches,” IEEE Communications Surveys & Tutorials, vol. 16, no. 2, pp. 1135-1156, 2013.
[12] L. Deri, M. Martinelli, T. Bujlow, and A. Cardigliano, “ndpi: Open-source high-speed deep packet inspection,” presented at 2014 International Wireless Communications and Mobile Computing Conference (IWCMC), pp. 617-622, IEEE, 2014.
[13] T. T. Nguyen, and G. Armitage, “A survey of techniques for internet traffic classification using machine learning,” IEEE communications surveys & tutorials, vol. 10, no. 4, pp. 56-76, 2008.
[14] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors” Communications of the ACM, vol. 13, no. 7, pp. 422-426, 1970.
[15] D. E. Knuth, The art of computer programming, sorting and searching, vol. 3, Addison Wesley Longman Publishing Co. Inc., Redwood City, CA, USA, 1998.
[16] B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher, “Cuckoo filter: Practically better than bloom,” presented at Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies, pp. 75-88, 2014.
[17] M. Al‐hisnawi, M. Ahmadi, “QCF for deep packet inspection,” IET Networks, vol. 7, no. 5, pp. 346-352, 2018.
[18] B. Choi, J. Chae, M. Jamshed, K. Park, and D. Han, “{DFC}: Accelerating string pattern matching for network applications,” presented at 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), pp. 551-565, 2016.
[19] R. M. Karp, and M. O. Rabin, “Efficient randomized pattern-matching algorithms,” IBM journal of research and development, 31(2), 249-260, 1987.
[20] R. S. Boyer, and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, vol. 20, no. 10, pp. 762-772, 1977.
[21] S. Wu, and U. Manber, U. A fast algorithm for multi-pattern searching Tucson, AZ: University of Arizona, Department of Computer Science, 1994, pp. 1-11.
[22] D. Luchaup, L. De Carli, S. Jha, and E. Bach, “Deep packet inspection with DFA-trees and parametrized language overapproximation,” presented at IEEE INFOCOM 2014-IEEE Conference on Computer Communications, pp. 531-539, IEEE, 2014.
[23] M. Češka, V. Havlena, L. Holík, O. Lengál, and T. Vojnar, “Approximate reduction of finite automata for high-speed network intrusion detection,” presented at International Journal on Software Tools for Technology Transfer, vol. 22, no. 5, pp. 523-539, 2020.
[24] M. Ceška, V. Havlena, L. Holík, J. Korenek, O. Lengál, D. Matoušek, j. Matoušek, J. Semric, and T. Vojnar, “Deep packet inspection in FPGAs via approximate nondeterministic automata,” presented at 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), pp. 109-117, IEEE, 2019.
[25] M. Roesch, “Snort: Lightweight intrusion detection for networks,” In Lisa, vol. 99, no. 1, pp. 229-238, 1991.
[26] R. Sommer, “Bro: An open source network intrusion detection system,” Security, E-learning, E-Services, 17. DFN-Arbeitstagung über Kommunikationsnetze, 2003.
[27] Cisco. (2022, june 6). Cisco IOS Intrusion Prevention System (IPS) [Online]. Available: https://www.cisco.com/c/en/us/products/security/ios intrusion-prevention-system-ips/index.html
[28] C. Yin, H. Wang, X. Yin, R. Sun, J. Wang, “Improved deep packet inspection in data stream detection,” The Journal of Supercomputing, vol. 75, no. 8, pp. 4295-4308, 2019.
[29] R. Sun, L. Shi, C. Yin, J. Wang, “An improved method in deep packet inspection based on regular expression,” The Journal of Supercomputing, vol. 75, no. 6, 3317-3333, 2019.
[30] S. Nagaraju, B. Shanmugham, and K. Baskaran, High throughput token driven FSM based regex pattern matching for network intrusion detection system, Materials Today: Proceedings, vol. 47, pp. 139-143, 2021.
[31] X. Yu, W. C. Feng, D. Yao, and M. Becchi, “O 3 FA: A scalable finite automata-based pattern-matching engine for out-of-order deep packet inspection,” presented at 2016 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), pp. 1-11, IEEE.
[32] A. V. Aho, and M. J. Corasick, “Efficient string matching: an aid to bibliographic search,” Communications of the ACM, vol. 18, no. 6, 333-340, 1975.
[33] M. Norton, “Optimizing pattern matching for intrusion detection,” Sourcefire, Inc., Columbia, MD, 2004.
[34] N. Tuck, T. Sherwood, B. Calder, and G. Varghese, “Deterministic memory-efficient string matching algorithms for intrusion detection,” In IEEE INFOCOM 2004, vol. 4, pp. 2628-2639, IEEE.
[35] L. Tan, T. Sherwood, “A high throughput string matching architecture for intrusion detection and prevention,” presented at 32nd International Symposium on Computer Architecture (ISCA'05), pp. 112-122, IEEE, 2005.
[36] T. H. Lee, and N. L. Huang, “A pattern-matching scheme with high throughput performance and low memory requirement,” IEEE/ACM Transactions on Networking, vol. 21, no. 4, 1104-1116, 2012.
[37] H. Kim, “A scalable architecture for reducing power consumption in pipelined deep packet inspection system”, Microelectronics Journal, vol. 46, no. 10, 950-955, 2015.
[38] R. Padmashani, S. Sathyadevan, and D. Dath, “BSnort IPS better snort intrusion detection/prevention system,” presented at 2012 12th International Conference on Intelligent Systems Design and Applications (ISDA), pp. 46-51, IEEE, 2012.
[39] S. Gupta, “Efficient malicious domain detection using word segmentation and BM pattern matching,” presented at 2016 International Conference on Recent Advances and Innovations in Engineering (ICRAIE), pp. 1-6, IEEE, 2016.
[40] T. F. A. Rahman, A. G. Buja, K. Abd, and F. M. Ali, “SQL Injection Attack Scanner Using Boyer-Moore String Matching Algorithm,” J. Comput., vol. 12, no. 2, 183-189, 2017.
[41] Y. Otoum, and A. Nayak, “As-ids: Anomaly and signature based ids for the internet of things,” Journal of Network and Systems Management, vol. 29, no. 3, pp. 1-26, 2021.
[42] Y. Wang, and H. Kobayashi, “An improved technology for content matching intrusion detection system,” presented at 2006 International Conference on Software in Telecommunications and Computer Networks, pp. 238-241, IEEE, 2006.
[43] A. A. Hasan, and N. A. A. Rashid, “Hash-Boyer-Moore-Horspool string matching algorithm for intrusion detection system,” presented at In International Conference on Computer Networks and Communication Systems, vol. 35, pp. 12-16, 2012.
[44] S. Sharma, and M. Dixit, “Single Digit Hash Boyer Moore Horspool Pattern Matching Algorithm for Intrusion Detection System,” presented at International Journal of Future Generation Communication and Networking, vol. 9, no. 9, 169-180, 2016.
[45] Q. Zheng, “An improved multiple patterns matching algorithm for intrusion detection,” presented at 2010 IEEE International Conference on Intelligent Computing and Intelligent Systems, vol. 2, pp. 124-127, IEEE, 2010.
[46] C. Ke-Qin, D. Lin, and W. Hui, “An improved multi-pattern matching algorithms in intrusion detection,” presented at 2013 Fifth International Conference on Measuring Technology and Mechatronics Automation, pp. 203-205, IEEE, 2013.
[47] M. Aldwairi, K. Al-Khamaiseh, F. Alharbi, and B. Shah, “Bloom filters optimized Wu-Manber for intrusion detection,” Journal of Digital Forensics, Security and Law, vol. 11, no. 4, 2016.
[48] B. Zhang, X. Chen, Pan, and Z. Wu, “High concurrence Wu-Manber multiple patterns matching algorithm,” presented at the 2009 International Symposium on Information Processing (ISIP 2009), pp. 404, 2009.
[49] Cisco. (2022, june 6). SNORT [Online]. Available: https://snort.org/