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.