Thread: Regex with > 32k different chars causes a backend crash

While playing with Alexander's pg_trgm regexp patch, I noticed that the 
regexp library trips an assertion (if enabled) or crashes, when passed 
an input string that contains more than 32k different characters:

select 'foo' ~ (select string_agg(chr(x),'') from generate_series(100, 
35000) x) as nastyregex;

This is because it uses 'short' as the datatype to identify colors. When 
it overflows, -32768 is used as index to the colordesc array, and you 
get a crash. AFAICS this can't reliably be used for anything more 
sinister than crashing the backend.

A regex with that many different colors is an extreme case, so I think 
it's enough to turn the assertion in newcolor() into a run-time check, 
and throw a "too many colors in regexp" error. Alternatively, we could 
expand 'color' from short to int, but that would double the memory usage 
of sane regexps with less different characters.

Thoughts?

- Heikki

Heikki Linnakangas <hlinnakangas@vmware.com> writes:
> A regex with that many different colors is an extreme case, so I think 
> it's enough to turn the assertion in newcolor() into a run-time check, 
> and throw a "too many colors in regexp" error. Alternatively, we could 
> expand 'color' from short to int, but that would double the memory usage 
> of sane regexps with less different characters.

Obviously Henry didn't think that far ahead.  I agree that throwing
an error is the best solution, and that widening "color" is probably
not what we want to do.  You want to fix that, or shall I?
        regards, tom lane

On 03.04.2013 18:21, Tom Lane wrote:
> Heikki Linnakangas<hlinnakangas@vmware.com>  writes:
>> A regex with that many different colors is an extreme case, so I think
>> it's enough to turn the assertion in newcolor() into a run-time check,
>> and throw a "too many colors in regexp" error. Alternatively, we could
>> expand 'color' from short to int, but that would double the memory usage
>> of sane regexps with less different characters.
>
> Obviously Henry didn't think that far ahead.  I agree that throwing
> an error is the best solution, and that widening "color" is probably
> not what we want to do.  You want to fix that, or shall I?

I can do it. I assume that Tcl has the same bug, so I'll submit a report 
there, too.

- Heikki

Heikki Linnakangas <hlinnakangas@vmware.com> writes:
> On 03.04.2013 18:21, Tom Lane wrote:
>> Obviously Henry didn't think that far ahead.  I agree that throwing
>> an error is the best solution, and that widening "color" is probably
>> not what we want to do.  You want to fix that, or shall I?

> I can do it. I assume that Tcl has the same bug, so I'll submit a report 
> there, too.

Yes, definitely.

It occurs to me that at some point it might be useful to convert "color"
to unsigned short, so that you could have 64K of them --- but we'd still
need the error check anyway, and there's no reason to tackle such a
change today.  (This possible change is, however, another reason to not
want pg_trgm looking directly at the internals of the data structure...)
        regards, tom lane

On 03.04.2013 18:41, Tom Lane wrote:
> Heikki Linnakangas<hlinnakangas@vmware.com>  writes:
>> On 03.04.2013 18:21, Tom Lane wrote:
>>> Obviously Henry didn't think that far ahead.  I agree that throwing
>>> an error is the best solution, and that widening "color" is probably
>>> not what we want to do.  You want to fix that, or shall I?
>
>> I can do it. I assume that Tcl has the same bug, so I'll submit a report
>> there, too.
>
> Yes, definitely.
>
> It occurs to me that at some point it might be useful to convert "color"
> to unsigned short, so that you could have 64K of them ...--- but we'd still
> need the error check anyway, and there's no reason to tackle such a
> change today.

I was just thinking the same. In practice, expanding it to 64k doesn't
get you much farther. There is this in newdfa():

   d->incarea = (struct arcp *) MALLOC(nss * cnfa->ncolors *
sizeof(struct arcp));

That's (number of states) * (number of colors) * (constant). The test
case I posted earlier would require about 40 GB of RAM for that
allocation alone, and fails with an "out of memory" error. Maybe it
would be possible to construct a regexp that has a lot of colors but few
states, but that's an even more marginal use case.


Attached is a patch to add the overflow check. I used the error message
"too many distinct characters in regex". That's not totally accurate,
because there isn't a limit on distinct characters per se, but on the
number of colors. Conceivably, you could have a regexp with more than
32k different characters, but where most of them are mapped to the same
color. In practice, it's not helpful to the user to say "too many
colors"; he will have no clue what a color is.

PS. I was mistaken when I said that this causes an assertion failure; it
segfaults even with assertions enabled.

- Heikki

Heikki Linnakangas <hlinnakangas@vmware.com> writes:
> Attached is a patch to add the overflow check. I used the error message 
> "too many distinct characters in regex". That's not totally accurate, 
> because there isn't a limit on distinct characters per se, but on the 
> number of colors. Conceivably, you could have a regexp with more than 
> 32k different characters, but where most of them are mapped to the same 
> color. In practice, it's not helpful to the user to say "too many 
> colors"; he will have no clue what a color is.

Patch looks good except perhaps for wordsmithing the message text.

One thought is that we don't need to identify this as a regex error
because the PG code will report it with "invalid regular expression: %s".

I think there's a good argument for saying "too many character colors"
and relying on the "invalid regular expression" context to clue in the
clueless.  After all, most of them don't know what an NFA is either, but
no one has complained about the REG_ETOOBIG message.  I think if you get
to the point where you're triggering this error, you probably know
something about regexes, or even if you don't the phrase "too many" will
give you a fair idea what's wrong.  There is much to be said for
specifically identifying the implementation limit that's been hit, even
if most users don't know what it is.  So I'd just as soon not fall back
on something imprecise.
        regards, tom lane

On Wed, Apr 03, 2013 at 08:09:15PM +0300, Heikki Linnakangas wrote:
> --- a/src/include/regex/regguts.h
> +++ b/src/include/regex/regguts.h
> @@ -148,6 +148,7 @@
>  typedef short color;            /* colors of characters */
>  typedef int pcolor;                /* what color promotes to */
>  
> +#define MAX_COLOR    32767        /* max value that fits in 'color' datatype */

This should use SHRT_MAX, no?  (Not that any supported platform differs here.)

-- 
Noah Misch
EnterpriseDB                                 http://www.enterprisedb.com

On 04.04.2013 03:32, Noah Misch wrote:
> On Wed, Apr 03, 2013 at 08:09:15PM +0300, Heikki Linnakangas wrote:
>> --- a/src/include/regex/regguts.h
>> +++ b/src/include/regex/regguts.h
>> @@ -148,6 +148,7 @@
>>   typedef short color;            /* colors of characters */
>>   typedef int pcolor;                /* what color promotes to */
>>
>> +#define MAX_COLOR    32767        /* max value that fits in 'color' datatype */
>
> This should use SHRT_MAX, no?  (Not that any supported platform differs here.)

I considered that, but I got all confused on whether limits.h needs to 
be included and where, if we use that. So I just used a constant 32767 
in the end. Committed that way.

I opened a ticket in TCL bug tracker for this: 
https://sourceforge.net/tracker/?func=detail&aid=3610026&group_id=10894&atid=110894. 


- Heikki