Re: regex DoS in postgresql? - Mailing list pgsql-general

From Tom Lane
Subject Re: regex DoS in postgresql?
Date
Msg-id 8823.1551589517@sss.pgh.pa.us
Whole thread Raw
In response to regex DoS in postgresql?  (Stuart McGraw <smcg4191@mtneva.com>)
List pgsql-general
Stuart McGraw <smcg4191@mtneva.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


pgsql-general by date:

Previous
From: Stuart McGraw
Date:
Subject: regex DoS in postgresql?
Next
From: Laurenz Albe
Date:
Subject: Re: Future Non-server Windows support???