If I remember correctly there are other tools that also try to find ReDoS. Do these tools also fail/take very long on this specific regex?
Basically, I'm just curious whether this is an inherent problem to ReDoS detection; if I were to guess, I'd assume that this problem is np complete (as most interesting problems are 😢 )?

If I remember correctly there are other tools that also try to find ReDoS. Do these tools also fail/take very long on this specific regex?

It is a problem with the implementation strategy I've taken in implementing this.
Which is a natural way of implementing it in CodeQL.

E.g. the Java implementation from the author of the research I've based my implementation on does not experience the same issue.

The bottom-up evaluation nature of CodeQL hurts here.

LGTM if you want to merge like this.

But if you want to try and fix it in a more principled way I think this would work: (possibly for a future PR)

• Include pivot in the StateTuple. It then represents a state tuple (q1, q2, q3) that is known to be reachable from (pivot, _, _).
• Sharpen isFeasibleTuple to require that q1 can reach the associated pivot (rather than just any pivot)
• Compute a variant of isReachableFromStartTuple that does not have trace and dist (the exponential number of traces is what caused this to blow up).
• Compute dist using the shortestPath HOP over the subset of StateTuples that are reachable.
  • Here it's beneficial that pivot is part of the StateTuple, since we get an independent distance measure for each pivot.
• Materialize traces based on the distance measure. In the recursive case, only extend a trace to the successor with the smallest distance from the pivot, breaking ties by picking the successor with the smallest InputSymbol.