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"
}