Geri Dön

NFA based regular expression matching on FPGA

FPGA üzerinde belirsiz sonlu durum makinası temelli düzenli ifade eşleştirme

  1. Tez No: 528787
  2. Yazar: KAMİL SERT
  3. Danışmanlar: DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2018
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Elektrik Elektronik Mühendisliği Bilim Dalı
  13. 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

  1. 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

    İngilizce

    2024

    KimyaOrta Doğu Teknik Üniversitesi

    Fizikokimya Ana Bilim Dalı

    PROF. DR. LEVENT KAMİL TOPPARE

  2. 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

    Türkçe

    2022

    ZiraatÇukurova Üniversitesi

    Tarım Ekonomisi Ana Bilim Dalı

    PROF. DR. MUSTAFA NECAT ÖREN

  3. Kant'ta inanç kavramı

    Kant's concept of belief

    CEMİL ULUDAĞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2013

    FelsefeKocaeli Üniversitesi

    Felsefe Ana Bilim Dalı

    PROF. DR. HÜRŞAD SİNAN ÖZBEK

  4. 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

    Türkçe

    2000

    Kimya MühendisliğiHacettepe Üniversitesi

    Kimya Mühendisliği Ana Bilim Dalı

    PROF. DR. S. ALİ TUNCEL

  5. 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

    Türkçe

    2024

    Kimya Mühendisliğiİstanbul Üniversitesi-Cerrahpaşa

    Kimya Mühendisliği Ana Bilim Dalı

    PROF. DR. SAADET KEVSER PABUCCUOĞLU