Derin paket incelemesi için önerilen yeni bir örüntü eşleştirme algoritması
A new pattern matching algorithm for deep packet inspection
Yazar: MERVE ÇELEBİ
Danışman: DR. ÖĞR. ÜYESİ URAZ YAVANOĞLU
Gazi Üniversitesi / Bilişim Enstitüsü / Adli Bilişim Ana Bilim Dalı
Derece: Doktora, 2023
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Derin Paket İnceleme (Deep Packet Inspection / DPI), ağ trafiğinin derinlemesine analiz edilmesini ve inceleme sonuçlarına göre bazı kararlar alınmasını sağlar. DPI sayesinde kötü amaçlı yazılım imzaları ile saldırı sırası, saldırganın izlediği yol ve saldırganın kullandığı tekniklerin birleşimi olarak tanımlanan saldırı örüntüsü tespit edilebilir. İnceleme yalnızca paket başlıklarını değil, aynı zamanda paket yüklerini de kapsadığı için yöntem, derin inceleme olarak adlandırılır. Paket yüklerini de kapsayan bu inceleme sayesinde, iki uç istasyon arasındaki iletişim üzerinde tam kontrol sağlanır. Bu tez çalışmasında, örüntü eşleştirme süresinin ve örüntü eşleştirme sürecinde ihtiyaç duyulan bellek alanının azaltılması amacıyla tek seferde birden fazla sayıda paket yükü karakteri işleyen bir çoklu örüntü eşleştirme algoritması önerilmiştir. Ayrıca, önerilen algoritmaya P3FSM yaklaşımı uygulanarak ikinci bir bellek azaltma işlemi gerçekleştirilmiştir. Önerilen algoritmanın performansını değerlendirmek amacıyla oluşturulan DPI sistemindeki örüntü eşleştirme işlemi, paralel hesaplama kabiliyeti ile ağ paketlerinin işlenmesini hızlandıran GPU donanımı üzerinde gerçekleştirilir. AC (Aho-corasick) algoritması, WM (Wu-Manber) algoritması ve bu tez çalışmasında önerilen algoritma, farklı sayıda örüntü içeren veri kümelerine özel oluşturulan tablolar kullanılarak gerçekleştirilen örüntü eşleştirme testleri için gereken bellek alanı ve bu testlerden elde edilen verim açısından karşılaştırılmıştır. 500 örüntü içeren bir veri kümesini kullanarak oluşturulan algoritma tabloları, AC ve WM'ye göre sırasıyla 425 ve 688 kat daha az bellek alanı gerektirir. Bu tablolar kullanılarak gerçekleştirilen örüntü eşleştirme işleminde, AC ve WM'ye kıyasla sırasıyla 3.5 ve 1.5 kat daha fazla verim elde edilmiştir.

Abstract:
Deep Packet Inspection (DPI) provides an in-depth analysis of network traffic and takes some decisions based on the inspection results. With the help of DPI, well-known malware signatures and the attack pattern, which is defined as the combination of the attack order, the path followed by the attacker, and the techniques used by the attacker can be detected. Since the inspection also covers packet payloads as well as packet headers, the method is called as deep inspection. As this inspection includes packet payloads, it provides full control over the communication between two end stations. In this thesis, it is proposed that a multi-pattern matching algorithm that processes more than one payload character at once in order to reduce both pattern matching time and the memory space required in the pattern matching process. In addition, a second memory reduction operation is performed by applying the P3FSM approach to the proposed algorithm. The pattern-matching process in DPI system, which is created to evaluate the performance of the proposed algorithm, is carried out on the GPU hardware, which accelerates the processing of network packets with its parallel computing capability. AC (Aho-corasick) algorithm, WM (Wu-Manber) algorithm and the algorithm proposed by this thesis are compared in terms of the memory space required for the pattern matching tests performed using tables specially created for datasets containing different numbers of patterns and the throughput obtained from these tests. Algorithm tables created using a dataset containing 500 patterns require 425 times less memory space than AC and 688 times less than WM. In the pattern matching process using these tables, throughput 3.5 times more than AC and 1.5 times more than WM is obtained.