[langsec-discuss] langsec implications on Re-DOS Attacks

Harald Lampesberger h.lampesberger at cdcc.faw.jku.at
Mon Oct 28 11:36:32 UTC 2013

On 28.10.2013 03:53, Sashank Dara wrote:
> I suspect there are other forms of regex's too other than backlashes
> that can cause problem .
> For example , the context sensitive grammar example given in the link
> here .
> <http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html>
> does not have back lashes !
> Since the acceptance of CSG is UnDecidable this could cause  attacks too
> according to langsec principles .
> Is my understanding correct ?

Backtracking is the biggest problem because it can take exponential time
for some input (ReDoS). Backreferences and recursive subpatterns for
grammar-style regex, like in the link, need backtracking. So if there is
no way to write your PCRE regex without backreferences or recursion then
it is definitely beyond linear time/constant space matching in the worst

If your PCRE regex is regular, you can still run into backtracking
problems because of iteration (*) and nondeterminism in expressions. But
here you have alternatives; you can switch to a non-backtracking
implementation like google's RE2. Of course, these implementations
support only a fragment of PCRE features.

More information about the langsec-discuss mailing list