Detail práce
Automata with Counting in Regular Expression Matching
Vyhledávání podle regulárních výrazů (regexové vyhledávání) je široce využívaný prostředek např. pro vyhledávání informací, ověřování dat, vyhledávání a nahrazování, získávání dat nebo zvýrazňování syntaxe v mnoha programovacích jazycích. Jedná se o výpočetně náročný proces, který se často aplikuje na rozsáhlé texty. Jeho předvídatelnost a stabilita má v praxi významný dopad na celkovou použitelnost softwarových aplikací. Problémem je, že standardní přístupy pro regexové vyhledávání mají vysokou složitost a nešťastná kombinace regexu a textu může dobu vyhledávání řádově prodloužit. To může být vstupní branou pro tzv. ReDoS útoky, což je závažný bezpečnostní problém, kdy útočník způsobí odepření služby pomocí speciálně vytvořeného regexu nebo textu.Automatové regexové vyhledávače jsou v současné době nejefektivnějšími nástroji pro regexové vyhledávání používanými v praxi, zejména v průmyslových výkonnostně kritických aplikacích. Dlouholeté empirické studie ukazují, že tyto přístupy mají mnohem stabilnější výkonnost, než jakou mají existující nástroje pro regexové vyhledávání založené na zpětném prohledávání. Nicméně i automatové regexové vyhledávače se mohou dostat do potíží. Omezená opakování, např. [ab]{100}, představují hlavní zdroj problémů i pro nejrychlejší nástroje pro regexové vyhledávání. Tato práce se touto problematikou zabývá systematicky.V této práci jsme nejprve představili rozsáhlou studii zranitelnosti nástrojů pro regexové vyhledávání založených na konečných automatech. Za tímto účelem jsme navrhli nový ReDoS generátor. Jedná se o první generátor schopný využívat omezené opakování ke generování útoků pro automatové regexové vyhledávače. Byli jsme schopni experimentálně prokázat, že omezená opakování skutečně představují vážnou bezpečnostní hrozbu, jak pro automatové regexové vyhledávače, tak pro ty založené na zpětném prohledávání.Dále jsme navrhli řešení problému efektivního regexové vyhledávání s omezeným opakováním. Obecný přístup je založen na kompilaci regexů do nedeterministických čítačových automatů a jejich následné determinizaci. Hlavním problémem je najít stručnou deterministickou reprezentaci, která dokáže provádět rychlé regexové vyhledávání (naivní determinizace vytváří deterministické konečné automaty exponenciálně velké k velikosti regexu a k maximům mezí opakování, které se v nich nachází). Nejprve jsme navrhli determinizační algoritmus vycházející z klasické podmnožinové konstrukce, který generuje deterministické čítačové automaty. Tyto automaty jsou exponenciálně stručnější než odpovídající deterministické konečné automaty. Hlavní přínos této práce jsme pak získali, když jsme determinizaci rozpracovali pomocí myšlenky čítacích množin. Navrhli jsme stručnou transformaci čítačového automatu na deterministický automat se speciálním typem registrů, které mohou obsahovat množinu celočíselných hodnot. Představili jsme také novou kompilaci regexů na čítačové automaty, která zobecňuje Antimirovu derivatovou konstrukci. Vytvořili jsme aplikační rámec založený na simulaci automatů s čítačovými registry a Antimirově derivatové konstrukci. Porovnali jsme rychlost vyhledávání jednotlivých nástrojů na rozsáhlé sadě reálných regexů s omezeným opakováním. Zjistili jsme, že náš algoritmus je mnohem robustnější, překonává nejmodernější nástroje pro regexové vyhledávání na regexech s omezeným opakováním a není závislý na velikosti mezí opakování. Snadno řeší většinu případů, ve kterých mají stávající nástroje pro regexové vyhledávání problém s omezeným opakováním.
Vyhledávání podle regulárních výrazů, omezené opakování, ReDoS, determinizace, Antimirovy derivativy, čítačové automaty.
@phdthesis{FITPT1416,
author = "Lenka Hol\'{i}kov\'{a}",
type = "Diserta\v{c}n\'{i} pr\'{a}ce",
title = "Automata with Counting in Regular Expression Matching",
school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
year = 2022,
location = "Brno, CZ",
language = "english",
url = "https://www.fit.vut.cz/study/phd-thesis/1416/"
}