Název: Hledání slabých stránek Hyperscanu
Překlad názvu: Finding Weaknesses of Hyperscan
Autoři: Hrabovský, Jiří ; Vojnar, Tomáš (oponent) ; Síč, Juraj (vedoucí práce)
Typ dokumentu: Bakalářské práce
Rok: 2024
Jazyk: eng
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [eng] [cze]
Cilem této bakalářské práce je vysvětlit, jak funguje open source vyhledávač regulárních výrazů Hyperscan, a poskytnutí přehledu algoritmů, které interně používá. Druhým cílem je pomocí experimentů zjistit, jak moc lze ovlivnit výkon Hyperscanu skenovaným textem. Na základě zdrojového kódu a článků od autorů Hyperscanu je v kapitole 3 vysvětleno, jak Hyperscan vyhledává regulární výrazy v textu a v kapitole 4 jsou vysvětleny implementace konečných automatů používaných Hyperscanem. Různé způsoby zpomalení vyhledávačů regulárních výrazů jsou zhodnoceny a je zvolena metoda, která je založena na fungování jedné z implementací konečných automatů používaných v Hyperscanu. Na základě zvolené metody je implementován generátor, který pro vybraný výraz vygeneruje text, jehož skenování by mělo Hyperscanu zabrat výrazně déle než u normálního textu. Provedené benchmarky ukázaly, že pro některé regulární výrazy způsobil generovaný text v porovnání vůči náhodnému textu výrazné prodloužení vyhledávání Hyperscanem. U nejvíce ovlivněného regulárního výrazu trvalo skenování generovaného textu více než 8000krát déle než skenování náhodného textu. This Bachelor's thesis aims to explain how the open sourced regular expression matcher Hyperscan works, and provide overview of algorithms it uses internally. The second objective is conducting experiments to determine how much can the performance of the matcher be affected by the scanned text. Based on the source code and articles by the authors of Hyperscan the overview of how Hyperscan scans the text for patterns is provided in chapter 3 and the implementations of NFA (Nondeterministic Finite Automata) used by the Hyperscaned are explained in chapter 4. How could the matcher be slowed down by input text is discussed and approach focusing on specific implementation of NFA used by Hyperscan is proposed. Generator using the proposed approach that is able to generate text for some expressions, that when scanned using Hyperscan with the given expression takes significantly longer that normal text. Conducted benchmark showed that for some expressions the generated text caused the Hyperscan to scan significantly longer. The most affected regular expression took more than 8000 times longer when scanning the generated text than the random text.
Klíčová slova: finite state automata; Hyperscan; regex matching; regular expressions; Hyperscan; konečné automaty; regulární výrazy; vyhledávání regulárních výrazů

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: https://hdl.handle.net/11012/246924

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-619338


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Bakalářské práce