Publication Details
Automata with Bounded Repetition in RE2
RE2, regex, counting-set automata
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.
@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"
}