PostgreSQL, TCL and others: A critical error in the RE engine. Possible vulnerability

I want to draw the attention of the habrasociety to a possible “vulnerability” in TCL, PostgreSQL, and theoretically in some other systems using rugular expression modules or NFA utilities, originally written by Henry Spencer himself. You can find a good hundred modified sources (from the same Sun Microsystems, UUNET, etc.). And although I do not think that the bug existed initially from the distant 90s, if only because I did not find the code where this error occurs in Henry, in his old sources, it's still worth checking your systems.

And so the error: this is busyloop at the stage of compiling a regular expression of the form (((((x)*)*)*)*)*. Moreover, it is not execution, but compilation, i.e. if there is a validation of the regularity and it is based on the same NFA code - we have the same endless cycle + 100% cpu usage.

The mistake was found by colleagues on the opensource TCL project, in all its current versions (including develop). Knowing that Postgres uses a similar API, it was not difficult to find out that feeding this Postgres regular expression completely freezes the thread (process) that processes the request.

An error occurs with such grouping only in the fifth or more nesting order - i.e. four nested groups compile and execute correctly.

Example for PostgreSQL:

postgres=# select 1 where 'x' ~ '((((x)*)*)*)*';
 ?column?
----------
        1
(1 row)
postgres=# select 1 where 'x' ~ '(((((x)*)*)*)*)*';

! busyloop!

Example for TCL:

% regexp -about {((((x)*)*)*)*}
4 REG_UEMPTYMATCH
% regexp -about {(((((x)*)*)*)*)*}

! busyloop!

Because this error leads to a freeze of the thread at 100% busy, and in view of the fact that there are already bug reports (which, by the way, are very actively studied by hackers and script kiddis), while the search is in progress and a bug fix is ​​issued, I recommend checking your projects ( products) and in case of a positive result, disable the ability to generate such regular expressions or foreign input regular in general.

Today, two times in this way I dropped a bug tracker of one of my friend, after which I listened first to swearing, then that nothing was visible in the logs (post arguments were disabled in the log), I heard thanks. For, warned - armed.

From the verified vulnerable:
TCL 8.4, 8.5, 8.6 - FAILED .
PostgreSQL 8.4, 9.1 -FAILED .

Not subject to error:
Python 2.5.2 and 2.7 - OK .
UPD: PostgreSQL 9.2.3 - OK . (according to the comment by uv. starius ).
UPD: PostgreSQL 9.2.1, 9.2.2-2 - OK . (thanks to catlion and sdevalex ).