Automata with Bounded Repetition in RE2

Automata with Bounded Repetition in RE2

Paper in proceedings (conference paper)

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.

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.

RE2, regex, counting-set automata

RE2, regex, counting-set automata

HOLÍKOVÁ, L.; HORKÝ, M.; SÍČ, J.

2025

10.02.2023

Springer Verlag

Heidelberg

Computer Aided Systems Theory - EUROCAST 2022

0302-9743

Lecture Notes in Computer Science

13789

Federal Republic of Germany

232

239

8