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 case. 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. _______________________________________________ langsec-discuss mailing list [email protected] https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss
