Automata with Bounded Repetition in RE2

RE2, regex

Při vývoji softwaru má nezastupitelnou roli porovnávání regulárních výrazů (regex). Jedná se o výpočetně náročný proces, který se často aplikuje na rozsáhlé texty. Předvídatelnost jeho účinnosti má v praxi významný vliv na celkovou použitelnost softwarových aplikací. Problémem je, že standardní přístupy k regexovému porovnávání trpí vysokou složitostí v nejhorším případě. Nešťastná kombinace regexu a textu může prodloužit dobu porovnávání o řády. To může být vstupní branou pro tzv. útok odepření služby regulárním výrazem (Regular Expression Denial of Service, ReDoS), při kterém útočník způsobí odepření služby zadáním speciálně vytvořeného regexu nebo textu. Zaměříme se na jeden ze zdrojů těchto útoků, kterým jsou regexy s omezeným opakováním (např. "(ab)100"). Stručnou reprezentaci a rychlé porovnávání takových regexů lze archivovat pomocí nového automatu s počítací množinou. Představujeme implementaci párovacího algoritmu založeného na automatu počítající množiny v jazyce C++. Implementace je provedena v rámci programu RE2, což je rychlý regex matcher nejnovější generace. Provádíme experimenty na skutečných regexech. Experimenty ukazují, že implementace v rámci RE2 je rychlejší než původní implementace v jazyce C#.