Original title: Hledání slabých stránek Hyperscanu
Translated title: Finding Weaknesses of Hyperscan
Authors: Hrabovský, Jiří ; Vojnar, Tomáš (referee) ; Síč, Juraj (advisor)
Document type: Bachelor's theses
Year: 2024
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [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.
Keywords: Hyperscan; konečné automaty; regulární výrazy; vyhledávání regulárních výrazů; finite state automata; Hyperscan; regex matching; regular expressions

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: https://hdl.handle.net/11012/246924

Permalink: http://www.nusl.cz/ntk/nusl-619338


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses