Technische Universität Braunschweig
  • Studium & Lehre
    • Vor dem Studium
      • Informationen für Studieninteressierte
      • Studiengänge von A-Z
      • Bewerbung
      • Fit4TU - Self-Assessment
      • Beratungsangebote für Studieninteressierte
      • Warum Braunschweig?
    • Im Studium
      • Erstsemester-Hub
      • Semestertermine
      • Lehrveranstaltungen
      • Studien-ABC
      • Studienorganisation
      • Beratungsnavi
      • Zusatzqualifikationen
      • Finanzierung und Kosten
      • Besondere Studienbedingungen
      • Hinweise zum Coronavirus
      • Gesundheit & Wohlbefinden
      • Campusleben
    • Nach dem Studium
      • Exmatrikulation und Vorlegalisation
      • Nach dem Abschluss
      • Alumni
    • Strategien und Qualitätsmanagement
      • Strategiepapiere für Studium und Lehre
      • Studienqualitätsmittel
      • Studiengangsentwicklung
      • Qualitätsmanagement
      • Rechtliche Grundlagen
    • Für Lehrende
      • Informationen für Lehrende
      • Lernmanagementsystem Stud.IP
      • Lehre und Medienbildung
    • Kontakt
      • Studienservice-Center
      • Sag's uns - in Studium und Lehre
      • Zentrale Studienberatung
      • Immatrikulationsamt
      • Abteilung 16 - Studium und Lehre
      • Career Service
      • Projekthaus
  • Forschung
    • Forschungsprofil
      • Forschungsschwerpunkte
      • Exzellenzcluster
      • Forschungsprojekte
      • Forschungszentren
      • Forschungsprofile der Professuren
    • Wissenschaftlicher Nachwuchs
      • Förderung des wissenschaftlichen Nachwuchs
      • Promotion
      • Postdocs
      • Nachwuchsgruppenleitung
      • Junior Professur und Tenure-Track
      • Habilitation
      • Service-Angebote für Wissenschaftler*innen
    • Forschungsdaten & Transparenz
      • Transparenz in der Forschung
      • Forschungsdaten
      • Open Access Strategie
      • Digitale Forschungsanzeige
    • Forschungsförderung
      • Netzwerk Forschungsförderung
      • Datenbanken und Stiftungen
    • Kontakt
      • Forschungsservice
      • Graduiertenakademie
  • International
    • Internationale Studierende
      • Warum Braunschweig?
      • Studium mit Abschluss
      • Austauschstudium
      • TU Braunschweig Summer School
      • Geflüchtete
      • International Student Support
    • Wege ins Ausland
      • Studium im Ausland
      • Praktikum im Ausland
      • Lehren und Forschen im Ausland
      • Arbeiten im Ausland
    • Internationale Wissenschaftler*innen
      • Internationale Postdocs und Professor*innen
      • Internationale Promovierende
      • Service für gastgebende Einrichtungen
    • Sprachen und interkulturelle Kompetenzvermittlung
      • Deutsch lernen
      • Fremdsprachen lernen
      • Interkulturelle Kompetenzvermittlung
    • Internationales Profil
      • Internationalisierung
      • Internationale Kooperation
    • International House
      • Wir über uns
      • Kontakt & Sprechstunden
      • Aktuelles und Termine
      • Newsletter, Podcast & Videos
      • Stellenausschreibungen
  • Die TU Braunschweig
    • Unser Profil
      • Ziele & Werte
      • Ordnungen und Leitlinien
      • Allianzen & Partner
      • Hochschulentwicklung 2030
      • Internationale Strategie
      • Fakten & Zahlen
      • Unsere Geschichte
    • Karriere
      • Arbeiten an der TU
      • Stellenmarkt
      • Berufsausbildung an der TU
    • Wirtschaft & Unternehmen
      • Unternehmensgründung
      • Freunde & Förderer
    • Öffentlichkeit
      • Veranstaltungskalender
      • Check-in für Schüler*innen
      • Hochschulinformationstag (HIT)
      • Kinder-Uni
      • Gasthörer*innen & Senior*innenstudium
      • Nutzung der Universitätsbibliothek
    • Presse & Kommunikation
      • Stabsstelle Presse und Kommunikation
      • Medienservice
      • Ansprechpartner*innen
      • Tipps für Wissenschaftler*innen
      • Themen und Stories
    • Kontakt
      • Allgemeiner Kontakt
      • Anreise
      • Für Hinweisgeber
  • Struktur
    • Leitung & Verwaltung
      • Das Präsidium
      • Stabsstellen
      • Verwaltung
      • Organe, Statusgruppen und Kommissionen
    • Fakultäten
      • Carl-Friedrich-Gauß-Fakultät
      • Fakultät für Lebenswissenschaften
      • Fakultät Architektur, Bauingenieurwesen und Umweltwissenschaften
      • Fakultät für Maschinenbau
      • Fakultät für Elektrotechnik, Informationstechnik, Physik
      • Fakultät für Geistes- und Erziehungswissenschaften
    • Institute
      • Institute von A-Z
    • Einrichtungen
      • Universitätsbibliothek
      • Gauß-IT-Zentrum
      • Zentrale Personalentwicklung
      • International House
      • Projekthaus
      • Transfer- und Kooperationshaus
      • Hochschulsportzentrum
      • Einrichtungen von A-Z
    • Studierendenschaft
      • Studierendenparlament
      • Fachschaften
      • Studentische Wahlen
    • Lehrer*innenbildung
      • Lehrer*innenfortbildung
      • Forschung
    • Chancengleichheit
      • Gleichstellung
      • Familie
      • Diversität
    • Kontakt
      • Personensuche
  • Suche
  • Schnellzugriff
    • Personensuche
    • Webmail
    • cloud.TU Braunschweig
    • Messenger
    • Mensa
    • TUconnect (Studierendenportal)
    • Lehrveranstaltungen
    • Im Notfall
    • Stud.IP
    • UB Katalog
    • Status GITZ-Dienste
    • Störungsmeldung GB3
    • IT Dienste
    • Informationsportal (Beschäftigte)
    • Beratungsnavi
    • Linksammlung
    • DE
    • EN
Menü
  • Technische Universität Braunschweig
  • Struktur
  • Fakultäten
  • Carl-Friedrich-Gauß-Fakultät
  • Institute
  • Institut für Systemsicherheit
  • Teaching
  • Summer 2019
  • Seminar SESAM
Logo Institut für Systemsicherheit der TU Braunschweig
  • Summer 2019
    • Lecture MLSEC
    • Lecture CRYPRO1
    • Seminar MOSES
    • Seminar SESAM
    • Lab Seclab
    • Lab SEP1
    • Lab SEP2

Seminar SESAM

String and Stream Algorithms

String and Stream Algorithms

Overview

Semester
Sommer 2019 🌞
Course type
Block Seminar
Lecturer
Prof. Dr. Konrad Rieck
Audience
Master, Bachelor
Credits
5 ECTS
Hours
2
Language
English or German
Capacity
max. 8 Students
Room
BRICS 107/108
Kalender
https://calendar.sec.tu-bs.de/teaching/strings (CalDAV)

Description

The efficient processing of strings is key to many security applications, with signature matching as used by "traditional" virus scanners leading the way. Large amounts of data needs to be efficiently searched for a set (sub)strings—ideally in linear time. Also, more evolved detection mechanisms, for instance, using machine learning build upon the efficient processing of strings to handle large amounts of data.

Schedule

Date
Step
Tue, 9. April, 14:00–15:30h
Primer on academic writing, assignment of topics
Tue, 26. April
Arrange appointment with assistant
Mo, 29. April - Fr, 03. May
Individual meetings with assistant
Thu, 06. June
Submit final paper
Thu, 20. June
Submit review of two fellow students
Thu, 04. July
Submit camera-ready version of your paper
Fr, 12. July
Presentation

Requirements

The seminar is organized like a real academic conference. You need to prepare a written paper (English or German language) about the selected topic with 8-10 pages in ACM double-column style.

After submitting your paper at our conference system, you will write reviews about two of the papers submitted by your fellow students. This way, you can give them feedback about how to improve their paper. Then, you will have time to improve your own final paper based on the reviews you received.

Finally, you will give a 20–25 minutes talk about your topic/paper at our small string- and stream algorithm conference.

Topics

▸ Multi-String Matching

Matching multiple strings at once is a core component of virus scanner for the last decades. Doing so efficiently, however, requires careful algorithmic engineering. You will study different algorithms such as Aho-Corasick automata, the Rabin-Karp algorithm, etc.

▸ Efficient Regular Expression Matching

Due to efficiency reasons, malware signatures often do not allow for search patterns with complex relations. However, regular expressions are incredibly powerful in describing patterns and given the right data structures, as for instance nondeterministic finite automata (NFA), they can also be efficiently processed. Here you will study different approaches and assess their performance in practice.

▸ Suffix Trees and Suffix Arrays

These two data structures form the backbone of many efficient string processing algorithms. Suffix Trees not only store all input strings as is, but all its suffixes (as the name suggests :P). In doing so, it can be used to efficiently search for substrings, and collect various statistics in linear or quasilinear time, that are useful to attack detection. Suffix Arrays are the condensed counterpart to Suffix Trees. You will study both from construction to application.

▸ Probabilistic Data Structures

Another class of algorithms for efficient string processing are powered by probabilistic data structures such as Bloom Filter, Count-Min Sketches, Skip Lists, etc. Rather than storing data explicitly, data is stored with respect to a certain probability of error. Here you will study different data structures of this kind as well as their applications.

▸ Less Hashing, Same Performance

Hashing is an integral component in computer security. For string and stream algorithms one-way functions are important too, but usually here they do not require to be cryptographically secure. You will study applications of (universal) hash functions and how these can be efficiently computed, for instance, for their application in Bloom Filters or sketches.

▸ Exact Pattern Matching with Probabilistic Data Structures

As probabilistic data structures operate based on a certain probability of error, they cannot by directly used for exact pattern matching. However, they are very well suitable for pre-filtering data to significantly speed up the overall process. Here you will study this exiting intersection of two areas of efficient string processing.

▸ Stream Clustering using Sketches

Clustering is the processes of grouping similar data, such that items within a cluster are more similar to each other than to the rest in the data set. Unfortunately, this often requires quadratic time and space :( Here you will study algorithms based on Sketches that enable clustering in linear time.

▸ De Bruijn Graphs and their Application to Security

These graphs allow to generate continuous sequences (De Bruijn sequences) that contain all possible substrings of length n over a certain alphabet A as compactly as possible. The compactness and complexity of construction is based the clever overlap of contained substrings. The effort for generating these sequences however allows for improving security applications such as testing port knocking daemons.

▸ Ron was Wrong, Whit is Right

In 2012 researchers have shown that it is possible to efficiently factorize public keys if two communication parties use the same program for generating their keys. While feasible, factorizing keys still is a computational intensive. In this special case it has however been possible to process 6.2 million keys in 7.5 hours or thousand keys in 4.5 seconds. Strictly speaking not a string algorithm, but certainly a prime example for efficient algorithms for offensive security.

Bildnachweise dieser Seite

Für alle

Stellen der TU Braunschweig
Jobbörse des Career Service
Merchandising
Sponsoring- & Spendenleistungen
Drittmittelgeförderte Forschungsprojekte
Vertrauenspersonen für Hinweisgeber

Für Studierende

Semestertermine
Lehrveranstaltungen
Studiengänge von A-Z
Informationen für Erstsemester
TUCard

Interne Tools

Status GITZ-Dienste
Handbuch für TYPO3 (Intern)
Corporate Design-Toolbox (Intern)
Glossar (DE-EN)
Meine Daten ändern
Hochschulöffentliche Bekanntmachungen

Kontakt

Technische Universität Braunschweig
Universitätsplatz 2
38106 Braunschweig
Postfach: 38092 Braunschweig
Telefon: +49 (0) 531 391-0

Anreise

© Technische Universität Braunschweig
Impressum Datenschutz Barrierefreiheit

Zur anonymisierten Reichweitenmessung nutzt die TU Braunschweig die Software Matomo. Die Daten dienen dazu, das Webangebot zu optimieren.
Weitere Informationen finden Sie in unserer Datenschutzerklärung.