NFA based regular expression matching on FPGA
FPGA üzerinde belirsiz sonlu durum makinası temelli düzenli ifade eşleştirme
- Tez No: 528787
- Danışmanlar: DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Elektrik Elektronik Mühendisliği Bilim Dalı
- Sayfa Sayısı: 100
Özet
Dizi eşleştirme, bir dizinin belirli bir metin içerisinde ki tüm mevcudiyetlerini bulmakla ilgili olan klasik ancak yine de popüler bir sorundur. Dizi eşleştirme algoritmaları, web ve güvenlik uygulamaları gibi çeşitli gerçek dünya alanlarında önemli rollere sahiptir. Bu çalışmada, özellikle Ağa Sızmayı Algılama Sistemleri (ASAS) alanını hedefleyen düzenli ifade eşleştirme ve dolayısıyla dizi eşleştirme problemini çözmekle ilgileniyoruz. Ağa sızmayı algılama sistemi ağ paketlerinin hem başlığını hem de içeriğini inceler dolayısıyla bir tür derinlemesine paket denetimi de gerçekleştirir. Bu inceleme, etkili dizi eşleştirme tekniklerinin kullanımını gerektirir, çünkü her ağ paketi belki de yüzlerce olası kötü niyetli saldırıya karşı hat hızında kontrol edilmeli ve karşılaştırılmalıdır. Bu tezde, ilk olarak düzenli ifade eşleştirme çalışmalarını açıklayan ve sınıflandıran ayrıntılı bir literatür analizi sunulmaktadır. Bu çalışmaların arasında, belirsiz sonlu durum makinesi (NFA) temelli mimarileri ve onların FPGA üzerine eşlemlenmesini sunan çalışmalar bulunmaktadır. Kendi çalışmamızda böylesi bir çalışmayı [1] seçtik ve daha önce önerilen NFA mimarisini daha da değiştirip geliştirdik. Referans çalışma değiştirilmiş McNaughton-Yamada algoritmasını kullanır ve elde edilen sonlu durum makinesini FPGA uygulaması için yapısal donanım tanımlama diline (HDL) çevirir. Değişikliğimiz, daha iyi bellek kullanımı sağlayan 2-karakterli bir eşleştirme yapısı kullanmayı önermektir. Bizim yaklaşımımızla sonlu durum makinesi gösterimi için olan devre, 2-karakterli düzenli ifade eşleştirme işlemini gerçekleştirmek için daha az sayıda duruma (dolayısıyla iki durumlu hafıza birimine) ve arabul çizelgesine ihtiyaç duyar. Bu tez kapsamında, Xilinx 7 serisi FPGA ları hedefleyen, tanınmış Snort ağa sızmayı algılama sistemi kural seti kullanılarak kapsamlı bir değerlendirme çalışması ve bazı sezgisel ve yapay olarak oluşturulmuş düzenli ifadeler kullanılarak en kötü durum değerlendirmesi çalışması yapılır. Değerlendirme sonuçları çeşitli performans ölçütleri kullanılarak elde edilir.
Özet (Çeviri)
String matching is about finding all occurrences of a string within a given text, which is a classical but still a popular problem. String matching algorithms have important roles in various real world areas, such as web and security applications. In this work, we are interested in solving regular expression and hence string matching problem targeting especially the network intrusion detection systems (NIDS) field. An NIDS engine inspects both the header and the content of the packet and hence performs a type of deep packet inspection also. This inspection requires effective string matching techniques because each network packet should be checked and compared against maybe hundreds of possible malicious attacks at line speed. In this thesis, a detailed literature analysis is presented first that explains and classifies regular expression matching studies. Among these, studies exist that presents nondeterministic finite automata (NFA) based architectures and their novel mappings onto FPGA. In our study we select one such study [1] and further modify vi and enhance the NFA architecture already proposed. The reference study uses the modified-McNaughton-Yamada-algorithm and maps the resulting NFA into structural HDL for FPGA implementation. Our modification proposes to use a 2-character based matching structure that yields better memory utilization. With our approach, the circuit for the NFA representation needs less number of states (hence flip-flops) and LUTs to perform the 2-character regular expression matching process. Within the scope of this thesis, an extensive evaluation study is performed using the well-known Snort IDS ruleset and the worst case evaluation is done using some intuitively and synthetically created regular expressions targeting Xilinx 7-series FPGAs. Evaluation results are obtained using various performance metrics.
Benzer Tezler
- Design, synthesis and characterizations of non-fullerene acceptors for organic photovoltaics
Organik fotovoltaikler için fulleren olmayan akseptörlerin tasarimi, sentezi ve karakterizasyonu
SEHER BALCI
Yüksek Lisans
İngilizce
2024
KimyaOrta Doğu Teknik ÜniversitesiFizikokimya Ana Bilim Dalı
PROF. DR. LEVENT KAMİL TOPPARE
- Türk tarımında kamu yapılanması ve kamu hizmetlerinin değerlendirilmesi
Evaluation of public structuring and services in Turkish agriculture
TUĞÇE KÖKSAL
Yüksek Lisans
Türkçe
2022
ZiraatÇukurova ÜniversitesiTarım Ekonomisi Ana Bilim Dalı
PROF. DR. MUSTAFA NECAT ÖREN
- Kant'ta inanç kavramı
Kant's concept of belief
CEMİL ULUDAĞ
Yüksek Lisans
Türkçe
2013
FelsefeKocaeli ÜniversitesiFelsefe Ana Bilim Dalı
PROF. DR. HÜRŞAD SİNAN ÖZBEK
- Miniemülsiyon polimerizasyonunda poli(etilen glikol) bazlı makromoleküllerin stabilizör olarak kullanımı
The Use of poli(ethylene glycol) based macromolecules as stabilizers in the miniemulsion polymerization
ENDER ÜNSAL
Yüksek Lisans
Türkçe
2000
Kimya MühendisliğiHacettepe ÜniversitesiKimya Mühendisliği Ana Bilim Dalı
PROF. DR. S. ALİ TUNCEL
- Nanobiyoteknolojide dendrimer esaslı hedeflendirilebilen salım sistemlerinin sentezi ve karakterizasyonu
Synthesis and characterization of targeted delivery systems based on dendrimer in nanobiotechnology
KEVSER BAL
Doktora
Türkçe
2024
Kimya Mühendisliğiİstanbul Üniversitesi-CerrahpaşaKimya Mühendisliği Ana Bilim Dalı
PROF. DR. SAADET KEVSER PABUCCUOĞLU