Detail publikace

Automata with Bounded Repetition in RE2

HOLÍKOVÁ, L.; HORKÝ, M.; SÍČ, J. Automata with Bounded Repetition in RE2. In Computer Aided Systems Theory - EUROCAST 2022. Lecture Notes in Computer Science. Heidelberg: Springer Verlag, 2023. p. 232-239. ISSN: 0302-9743.
Název česky
Automaty s omezeným opakováním v RE2
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Holíková Lenka, Ing., Ph.D. (VZ VERIFIT)
Horký Michal, Ing.
Síč Juraj, Mgr. (UITS)
Klíčová slova

RE2, regex

Abstrakt

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#.

Rok
2023
Strany
232–239
Časopis
Lecture Notes in Computer Science, č. 13789, ISSN 0302-9743
Sborník
Computer Aided Systems Theory - EUROCAST 2022
Konference
Eurocast 2022 -- 18th International Conference on Computer Aided Systems Theory, Las Palmas de Gran Canaria, Canary Islands, ES
Vydavatel
Springer Verlag
Místo
Heidelberg
DOI
10.1007/978-3-031-25312-6_27
EID Scopus
2-s2.0-85151120069
BibTeX 
@inproceedings{BUT185168,
  author="Lenka {Holíková} and Michal {Horký} and Juraj {Síč}",
  title="Automata with Bounded Repetition in RE2",
  booktitle="Computer Aided Systems Theory - EUROCAST 2022",
  year="2023",
  journal="Lecture Notes in Computer Science",
  number="13789",
  pages="232--239",
  publisher="Springer Verlag",
  address="Heidelberg",
  doi="10.1007/978-3-031-25312-6\{_}27",
  issn="0302-9743"
}
Nahoru