davisjam314

Thanks, folks!

Interestingly, the backtracking engines can also be viewed as using automata. The trouble is actually in how they simulate the automaton. They use backtracking -- like a depth-first search. Since they don't remember where they've been, this leads them to a lot of redundancy. Engines like RE2 use a lockstep approach instead -- like a breadth-first search. They work their way down the search tree level-by-level and so don't have to repeat themselves.

Practically speaking, the slow regex engines don't always build NFAs. Instead they may follow a grammar-directed approach. But the NFA is a valid model of that simulation.

(This is a repetition of my replies to your thread on Twitter).

My goal was not to prove that super-linear behavior is possible, but rather to understand questions like:

1. How common are such regexes in practice? (~10%)

2. Do developers know it? (<50%)

3. Do they use specialized regex engines like RE2 or HyperScan? (Not often)

These are not theoretical advances. But I believe that my work improved our understanding of practice, and that it will let us ground future decisions in large-scale data instead of opinion.

Are there other regex questions you think are worth a look? I'm all ears!

I apologize if my treatment of HyperScan was offensive to you. My understanding from surveys is that developers typically use the regex engine built into their programming languages. I therefore focused on those engines, not on standalones like RE2 and HyperScan.

Once RE2 and HyperScan reach widespread use (I hope my research moves folks in that direction!), understanding their weaknesses will be an interesting next step.

Thank you for the suggestion. I added notes about typical sizes depending on the complexity of the regex.

TLDR: ~30 chars is too long for exponential regexes. 1K-5K chars are too long for quadratic regexes. Higher polynomials blow up somewhere between 100 and 1000 characters.

> This seems like a quibble, but putting the emphasis on "using an appropriate engine" in parentheses at the end is burying the lede. Sticking to regular languages will not, in itself, help.

Yes. I attempted to make this point at the end of my article, while avoiding phrases like "regular languages".

> There are quite a number of backreferences out there that work this way

Yes, this appears to be a common usage of backreferences. In the regex corpus from the FSE'19 Lingua Franca paper, many backreference-using regexes are of this form.

I believe a loose bound on the worst-case time complexity for regexes with backreferences is n^{mX} where X is the number of backreferenced capture groups. The goal is to describe the number of distinct values the capture groups can take on. If a capture group can take on arbitrary sub-strings (e.g. .(.)\1) then m=2; if it is fixed but ambiguous (e.g. .*(')\1) then m=1; if it is unambiguous then m=0. Often still a polynomial though.

The exception proves the rule; I've seen regexes with 20 backreferences, many of them ambiguous, but the vast majority cover simple use cases and are quite sane.

The name for this in the security literature is "algorithmic complexity attacks". They were first proposed by Crosby & Wallach in 2003, with a running example of degraded hash tables.

----

Tangent: I am the author of the Lingua Franca paper. I hope you enjoyed it!

Yes, those terms are definitely imprecise.

My target audience for that blog post was "anyone vaguely technical, from programmers to managers". I therefore attempted to minimize the amount of technical detail and to focus on the core algorithmic concepts.

This is a "technical two-pager" of my doctoral research about regex denial of service.

Why you should measure the cost of your GraphQL queries, and how you should do it.

This is a summary of a research paper.

This post is intended as a “technical two-pager” to summarize a security vulnerability called Regex-based Denial of Service (AKA Regex DoS, ReDoS). There are a variety of write-ups about ReDoS, but I’m not aware of a good one-stop-shop with a higher-level treatment of all aspects of the subject. I have included links at the end to more detailed treatments.