Re: Future of our regular expression code

On 02/19/2012 10:28 PM, Greg Stark wrote:
> One thing that concerns me more and more is that most sufficiently
> powerful regex implementations are susceptible to DOS attacks.

There's a list of "evil regexes" at http://en.wikipedia.org/wiki/ReDoS

The Perl community's reaction to Russ Cox's regex papers has some 
interesting comments along these lines too:  
http://www.perlmonks.org/?node_id=597262

That brings up the backreferences concerns Tom already mentioned.  
Someone also points out the Thompson NFA that Cox advocates in his first 
article can use an excessive amount of memory when processing Unicode:  
http://www.perlmonks.org/?node_id=597312

Aside--Cox's "Regular Expression Matching with a Trigram Index" is an 
interesting intro to trigram use for FTS purposes, and might have some 
inspirational ideas for further progress in that area:  
http://swtch.com/~rsc/regexp/regexp4.html

-- 
Greg Smith   2ndQuadrant US    greg@2ndQuadrant.com   Baltimore, MD
PostgreSQL Training, Services, and 24x7 Support www.2ndQuadrant.com