Re: regex DoS in postgresql?

Stuart McGraw <smcg4191(at)mtneva(dot)com> writes:
> I would like to deploy a web application with a Postgresql backend
> that allows a user to both add a record containing arbitrary text,
> and to search that text column with an arbitrary regular expression.

> My question is, is the app subject to a regex denial of service attack?

Possibly. We've run into such problems before (eg [1][2][3]), and
generally been able to find mitigations, but I wouldn't promise that
somebody who was intent on making a query run a long time couldn't do so.
However, I don't really think that this is a showstopper reason not to
allow users to give regexp patterns --- just make sure you use a statement
timeout to limit the runtime.

> I would have presumed so but I have been unable produce any problems
> when testing using the "evil" regexs described in the Wikipedia
> article on the subject: https://en.wikipedia.org/wiki/ReDoS
> Is there something in the way Postgresql implements its RE engine
> that makes it immune to this attack?

PG's RE engine is based on Henry Spencer's third regex library (also used
by Tcl), which is quite different from most others out there such as
Perl's. That wikipedia entry doesn't seem to go into much detail, but
I suspect the examples it gives are intended to cause problems for Perl's
engine. Perl's engine does a lot more backtracking than ours does, and
consequently it's easier to send it down the rabbit hole.

regards, tom lane

[1] https://git.postgresql.org/gitweb/?p=postgresql.git&a=commit&h=3bb3f42f3749d40b8d4de65871e8d828b18d4a45
[2] https://git.postgresql.org/gitweb/?p=postgresql.git&a=commit&h=48789c5d23a7f382e3cb721547d5e0af7aaa4585
[3] https://git.postgresql.org/gitweb/?p=postgresql.git&a=commit&h=98f27aaef34291246c09ce5d0e0fba4f4477467a