Geri Dön

Fast, efficient and dynamically optimized data and hardware architectures for string matching

Dizi eşleme amaçlı verimli veri ve donanım mimarileri

PDF İndir

  1. Tez No: 383279
  2. Yazar: SALİH ZENGİN
  3. Danışmanlar: PROF. DR. HASAN CENGİZ GÜRAN, DOÇ. DR. ŞENAN ECE SCHMİDT
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Elektrik ve Elektronik Mühendisliği, Computer Engineering and Computer Science and Control, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Ağ güvenliği, Dizgi eşleme, Siber saldırı, Sonlu durum makineleri, Network security, String matching, Cyber attack, Finite state machinery
  7. Yıl: 2014
  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ı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Verilen bir dizi kümesini kendi girişinde arayan dizi eşleme modülleri (SMM), ağ sızıntı tespit sistemleri gibi bir çok hesaplama alanında kullanılır. Bir SMM, giriş verisini yüksek hızlarda tararken, doğru sonuçlar üretmesi beklenir. Ayrıca, aranan dizi kümeleri genelde büyüktür ve boyutları da sürekli artmaktadır. Bu tezde, hızlı, doğru ve verimli tasarım gerekliliği motivasyonu ile, büyük miktarda veriyi dizi kümeleri için sıkıştırarak temsil etmek maksadıyla Bloom Filter'leri kullanan bir kaç SMM yapısı önerilmektedir. Bu yapılar,Bloom filtrelerin olumlu eşleme sonuçlarının doğrulanması sebebiyle oluşan ve iyi bilinen yavaşlama problemini çözmeyi hedefler. Bu amaçla, tezin ilk katkısı olarak, doğrulama maksatlı olarak kullanılan ikinci bir filtre içeren Çift Bloom filtreli dizi eşleme modülü (DBF-SMM) oluşturulmuştur. DBF-SMM'in analiz, değerlendirme ve uygulamaları gösterilmiştir. Ayrıca, DBF-SMM'in istenen işlevi, SystemC ortamında ilgili yapı modellenip test edilerek doğrulanmıştır. Analiz ve uygulama sonuçlarımız, DBF-SMM'in Bloom filtre tabanlı diğer SMM tasarımlarından tepki süresinin yüksek dizi saklama verimliliği ve donanım ölçeklendirilebilirliliği ile korunması açısından daha üstün olduğunu gösterir. DBF-SMM sabit boyutlu diziler için tasarlanmıştır. Tezin ikinci katkısı ise, karakterler arası durum geçişleri ile değişken boyutlu dizileri saklayan sonlu makine tabanlı tasarımlardır. Bu maksatla, durum geçişleri sınıfları tanımlanmıştır. Daha sonra, iyi bilinen Aho-Corasick algoritması gerçeklenmesi, Bloom filtreleri ve CAM-RAM tablolarını kullanarak uygun geçiş sınıflarını etkili bir şekilde donanımda saklayacak ve sorgulayacak şekilde değiştirilmiştir. Bu yapıda Bloom filtre DBF-SMM olarak gerçeklenmiştir. Önerilen SMM yapısı, bütün diğer SMM tasarımlarından üstün hafıza verimliliğine, hızlı ve ölçeklenebilir donanım tasarımıyla sahiptir.

Özet (Çeviri)

Many fields of computing such as network intrusion detection employ string matching modules (SMM) that search for a given set of strings in their input. An SMM is expected to produce correct outcomes while scanning the input data at high rates. Furthermore, the string sets that are searched for are usually large and their sizes increase steadily. In this thesis, motivated by the requirement of designing fast, accurate and efficient SMMs; we propose a number of SMM architectures that employ Bloom Filters to compactly represent the large amounts of data for the string sets. The proposed architectures address the well-known slowdown problem of the Bloom Filters because of the verifications of the positive matches. To this end, the first contribution of the thesis is Double Bloom Filter SMM (DBF-SMM) which employs a second Bloom Filter which acts as a verification engine. We present an analysis, evaluation and implementation of the DBF-SMM. We further verify the required functionality of the DBF-SMM by modeling and testing the architecture in SystemC environment. Our analytical and implementation results demonstrate that DBF-SMM is superior to the existing Bloom Filter based SMM designs in terms of sustainability of the response time with high string storage efficiency and hardware scalability. DBF-SMM is designed for fixed size strings. The second contribution of the thesis is a finite automaton-based design that stores variable size strings as state transitions between characters. To this end, we first identify the classes of state transitions. We then modify the implementation of the well-known Aho-Corasick algorithm to effectively store and query the appropriate transition classes in a hardware architecture that features Bloom Filters and CAM-RAM look-up tables. The Bloom Filter in this architecture is realized as a DBF-SMM. The proposed SMM achieves a memory efficiency that is superior to all previous SMM designs together with fast and scalable hardware design.

Benzer Tezler

  1. Tez No

    397130

    Çoklu otonom insansız hava araçları için paralel programlama tabanlı yol planlaması

    Parallel programming based path planning for multi autonomous unmmaned vehicles

    ÖMER ÇETİN

    Doktora

    Türkçe

    Türkçe

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHava Harp Okulu Komutanlığı

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. GÜRAY YILMAZ

  2. Tez No

    996640

    Gömülü sistemler ile yarı-girişimsel yük izleme kullanarak ev aletlerinin enerji tüketiminin takibi ve enerji tasarrufu önerilerinin sunulması

    Monitoring household appliances' energy consumption using embedded systems with silm and providing energy-saving recommendations

    ALİ ŞAMİL AYTEKİN

    Yüksek Lisans

    Türkçe

    Türkçe

    2026

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ AYDIN TARIK ZENGİN

  3. Tez No

    356

    Akaryakıtla çalışan endüstriyel tav fırınlarında yanma, sıcaklık ve basıncın optimum kontrolu

    Optimum control of combustion temperature and pressure in industrial tempering furnaces working with fuel-oil

    MEHMET EROĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    1987

    Makine MühendisliğiGazi Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. YÜCEL ERCAN

  4. Tez No

    606

    Liorhyssus hyalinus (F.) (heteropterar haopalidae)'ta anten rejenerasyon kapasitesinin saptanması üzerinde araştırmalar

    Investigations on the Antennal regenerative capasity of Lrorhyssus hyalinus (F.) (heteroptera: rhappalidea)

    SACİDE BÜLBÜL

    Yüksek Lisans

    Türkçe

    Türkçe

    1985

    ZoolojiEge Üniversitesi

    Bitki Koruma Ana Bilim Dalı

  5. Tez No

    713

    Avrupa Topluluğu'nun bürokratik yapısı

    Başlık çevirisi yok

    GÜNİZ ODYAKMAZ

    Yüksek Lisans

    Türkçe

    Türkçe

    1989

    Uluslararası İlişkilerİstanbul Üniversitesi

    Uluslararası İlişkiler Ana Bilim Dalı

    PROF. DR. BENER KARAKARTAL

Geri Dön