filtering out "bad" regular expressions from user input

[Andrew Dalke]

Skip:
>    Andrew> The time slowdown occurs for backtracking, especially if there
are
>    Andrew> multiple levels of backtracking.
>
>As usual, I specified the problem incompletely.  The problem isn't so much
>regular expressions that perform poorly when matched against particular
>strings.  It is that some very simple regular expressions (like ".*") can
>match all (or almost all) records in a database of 20,000 or so rows.

And I also read something different than what you posted.  :)

I had been thinking about the problem of how to protect a server from
what I guess I'll call "pathological regexp attacks", where the regexp
takes exponential time to match and so acts as a denial of service
attack.  You post had enough similarities to what I had been worried about
that I thought that that's what you were talking about.

                    Andrew
                    dalke at acm.org