Automata with Bounded Repetition in RE2

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F23%3APU149395" target="_blank" >RIV/00216305:26230/23:PU149395 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-031-25312-6_27" target="_blank" >http://dx.doi.org/10.1007/978-3-031-25312-6_27</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-25312-6_27" target="_blank" >10.1007/978-3-031-25312-6_27</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Automata with Bounded Repetition in RE2

Popis výsledku v původním jazyce

Regular expression (regex) matching has an irreplaceable role in software development. It is a computationally intensive process often applied on large texts. Predictability of its efficiency has a significant impact on the overall usability of software applications in practice. A problem is that standard approaches for regex matching suffer from high worst case complexity. An unlucky combination of a regex and text may increase the matching time by orders of magnitude. This can be a doorway for the so-called Regular Expression Denial of Service (ReDoS) attack in which the attacker causes a denial of service by providing a specially crafted regex or text. We focus on one of the sources of these attacks, which are regex with bounded repetition (e.g., '(ab)100'). Succinct representation and fast matching of such regexes can be archived by using a novel counting-set automaton. We present a C++ implementation of a matching algorithm based on the counting-set automaton. The implementation is done within RE2, which is a fast state-of-the-art regex matcher. We perform experiments on real-life regexes. The experiments show that implementation within the RE2 is faster than the original C# implementation.

Název v anglickém jazyce

Automata with Bounded Repetition in RE2

Popis výsledku anglicky

Regular expression (regex) matching has an irreplaceable role in software development. It is a computationally intensive process often applied on large texts. Predictability of its efficiency has a significant impact on the overall usability of software applications in practice. A problem is that standard approaches for regex matching suffer from high worst case complexity. An unlucky combination of a regex and text may increase the matching time by orders of magnitude. This can be a doorway for the so-called Regular Expression Denial of Service (ReDoS) attack in which the attacker causes a denial of service by providing a specially crafted regex or text. We focus on one of the sources of these attacks, which are regex with bounded repetition (e.g., '(ab)100'). Succinct representation and fast matching of such regexes can be archived by using a novel counting-set automaton. We present a C++ implementation of a matching algorithm based on the counting-set automaton. The implementation is done within RE2, which is a fast state-of-the-art regex matcher. We perform experiments on real-life regexes. The experiments show that implementation within the RE2 is faster than the original C# implementation.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-24397S" target="_blank" >GA19-24397S: Automaty v rozhodovacích procedurách a verifikaci</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Computer Aided Systems Theory - EUROCAST 2022

ISBN

—

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

8

Strana od-do

232-239

Název nakladatele

Springer Verlag

Místo vydání

Heidelberg

Místo konání akce

Las Palmas de Gran Canaria, Canary Islands

Datum konání akce

20. 2. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—