Thread: Death by regexp_replace

On Fri, Jan 15, 2016 at 10:12 AM, Benedikt Grundmann
<bgrundmann@janestreet.com> wrote:
> Today we discovered that we had a backend whose client had gone away, the
> automatic query watching process had send both pg_cancel and
> pg_terminate_backend but nevertheless the process was sitting there
> consuming resources and had been for over 1 day...
>
> gdb revealed that we were sitting in pg_regexec  (we forced it to return 16
> aka invalid regex to return our system into a good state).
>
> Here is the regular expression and the text to run on:
>
> WARNING DO NOT DO THIS ON A PRODUCTION BOX
>
> select regexp_replace('VODI GR,VOD LN,VOD LN,VODN MM,VODPF US,VOD US,VZC
> LN', '([^,]+)(,*\1)+', '\1');
>
> This was in postgres 9.2

9.2.what?  Tom just fixed a whole bunch of bugs in this area, so if
you're running less than 9.2.14, please test whether this can be
reproduced with that version.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 2016-01-15 10:25 AM, Robert Haas wrote:
> On Fri, Jan 15, 2016 at 10:12 AM, Benedikt Grundmann
> <bgrundmann@janestreet.com> wrote:
>> Today we discovered that we had a backend whose client had gone away, the
>> automatic query watching process had send both pg_cancel and
>> pg_terminate_backend but nevertheless the process was sitting there
>> consuming resources and had been for over 1 day...
>>
>> gdb revealed that we were sitting in pg_regexec  (we forced it to return 16
>> aka invalid regex to return our system into a good state).
>>
>> Here is the regular expression and the text to run on:
>>
>> WARNING DO NOT DO THIS ON A PRODUCTION BOX
>>
>> select regexp_replace('VODI GR,VOD LN,VOD LN,VODN MM,VODPF US,VOD US,VZC
>> LN', '([^,]+)(,*\1)+', '\1');
>>
>> This was in postgres 9.2
> 9.2.what?  Tom just fixed a whole bunch of bugs in this area, so if
> you're running less than 9.2.14, please test whether this can be
> reproduced with that version.
>

I just tried this on 9.4.5 (stock Ubuntu 15.10 release), waited a minute 
and killed the backend.

Benedikt Grundmann <bgrundmann@janestreet.com> wrote:
> Today we discovered that we had a backend whose client had gone away, the
> automatic query watching process had send both pg_cancel and
> pg_terminate_backend but nevertheless the process was sitting there
> consuming resources and had been for over 1 day...
> gdb revealed that we were sitting in pg_regexec  (we forced it to return 16
> aka invalid regex to return our system into a good state).
> Here is the regular expression and the text to run on:
> *WARNING DO NOT DO THIS ON A PRODUCTION BOX*
> select regexp_replace('VODI GR,VOD LN,VOD LN,VODN MM,VODPF US,VOD US,VZC
> LN', '([^,]+)(,*\1)+', '\1');

> This was in postgres 9.2

9.2 what?  This responds to cancel just fine for me.  See 9.2.14
release notes.

(FWIW, I think you probably wanted ,+ not ,* in the regex, else there's
practically no constraint there, leading to having to consider O(N^2)
or more possibilities.)
        regards, tom lane

On Fri, Jan 15, 2016 at 9:33 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

>> *WARNING DO NOT DO THIS ON A PRODUCTION BOX*
>> select regexp_replace('VODI GR,VOD LN,VOD LN,VODN MM,VODPF US,VOD US,VZC
>> LN', '([^,]+)(,*\1)+', '\1');

> This responds to cancel just fine for me.

> (FWIW, I think you probably wanted ,+ not ,* in the regex, else there's
> practically no constraint there, leading to having to consider O(N^2)
> or more possibilities.)

On master (commit cf7dfbf2) it responds to pg_cancel_backend(),
but it seems to be in an endless loop until you do that.

-- 
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

<div dir="ltr">9.2.6</div><div class="gmail_extra"><br /><div class="gmail_quote">On Fri, Jan 15, 2016 at 3:48 PM,
KevinGrittner <span dir="ltr"><<a href="mailto:kgrittn@gmail.com" target="_blank">kgrittn@gmail.com</a>></span>
wrote:<br/><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span
class="">OnFri, Jan 15, 2016 at 9:33 AM, Tom Lane <<a href="mailto:tgl@sss.pgh.pa.us">tgl@sss.pgh.pa.us</a>>
wrote:<br/><br /> >> *WARNING DO NOT DO THIS ON A PRODUCTION BOX*<br /> >> select regexp_replace('VODI
GR,VODLN,VOD LN,VODN MM,VODPF US,VOD US,VZC<br /> >> LN', '([^,]+)(,*\1)+', '\1');<br /><br /></span><span
class="">>This responds to cancel just fine for me.<br /><br /></span><span class="">> (FWIW, I think you
probablywanted ,+ not ,* in the regex, else there's<br /> > practically no constraint there, leading to having to
considerO(N^2)<br /> > or more possibilities.)<br /><br /></span>On master (commit cf7dfbf2) it responds to
pg_cancel_backend(),<br/> but it seems to be in an endless loop until you do that.<br /><span class="HOEnZb"><font
color="#888888"><br/> --<br /> Kevin Grittner<br /> EDB: <a href="http://www.enterprisedb.com" rel="noreferrer"
target="_blank">http://www.enterprisedb.com</a><br/> The Enterprise PostgreSQL Company<br
/></font></span></blockquote></div><br/></div> 

Kevin Grittner <kgrittn@gmail.com> writes:
> On Fri, Jan 15, 2016 at 9:33 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> (FWIW, I think you probably wanted ,+ not ,* in the regex, else there's
>> practically no constraint there, leading to having to consider O(N^2)
>> or more possibilities.)

> On master (commit cf7dfbf2) it responds to pg_cancel_backend(),
> but it seems to be in an endless loop until you do that.

A bit of further experimentation suggests the runtime growth is actually
more like O(2^N).  It will terminate in a reasonable amount of time if the
input string is about half as long as the given example.

The problem is that so far as the DFA engine is concerned, the pattern
substring '(,*\1)+' can match almost anything at all, because it's
equivalent to '(,*[^,]+)+' which is easily seen to match any string
whatever that's got at least one non-comma.  So, for each possible match
to the substring '([^,]+)', of which there are lots, it has to consider
every possible way of breaking up all the rest of the string into one or
more substrings.  The vast majority of those ways will fail when the
backref match is checked, but there's no way to realize it before that.
        regards, tom lane

> Hmm I just wanted to get the rpm for the latest 9.2 release for centos6 but
> it looks like you haven't released at least the link on this page for 9.2
>
> http://yum.postgresql.org/repopackages.php
>
> says 7 in the filename which is certainly not 14 ;-)
>
> http://yum.postgresql.org/9.2/redhat/rhel-6-x86_64/pgdg-centos92-9.2-7.noarch.rpm
>
> Is that expected?

Adding Devrim, who I believe maintains that stuff.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Hi,<br /><br /> That is the version of *repo* RPM, not PostgreSQL itself.Once you install it, you can grab the latest
versionwith <br /><br /> yum install postgresql92-server<br /><br /> Regards, Devrim<br /><br /><div
class="gmail_quote">OnJanuary 15, 2016 7:48:53 PM GMT+02:00, Robert Haas <robertmhaas@gmail.com>
wrote:<blockquoteclass="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204);
padding-left:1ex;"><pre class="k9mail"><blockquote class="gmail_quote" style="margin: 0pt 0pt 1ex 0.8ex; border-left:
1pxsolid #729fcf; padding-left: 1ex;"> Hmm I just wanted to get the rpm for the latest 9.2 release for centos6 but<br
/>it looks like you haven't released at least the link on this page for 9.2<br /><br /> <a
href="http://yum.postgresql.org/repopackages.php">http://yum.postgresql.org/repopackages.php</a><br/><br /> says 7 in
thefilename which is certainly not 14 ;-)<br /><br /> <a
href="http://yum.postgresql.org/9.2/redhat/rhel-6-x86_64/pgdg-centos92-9.2-7.noarch.rpm">http://yum.postgresql.org/9.2/redhat/rhel-6-x86_64/pgdg-centos92-9.2-7.noarch.rpm</a><br
/><br/> Is that expected?<br /></blockquote><br />Adding Devrim, who I believe maintains that stuff.<br
/></pre></blockquote></div><br/> -- <br /> Sent from my Android device with K-9 Mail. Please excuse my brevity.