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

I want to draw the attention of the habrasoobshchestvo to a possible “vulnerability” in TCL, PostgreSQL and theoretically in some other systems using modules of regular expressions or NFA utilities, originally written by Henry Spencer himself. Modified sources can be found a hundred (from the same Sun Microsystems, UUNET, etc.). And although I don’t think that the bug exists initially from the distant 90s, if only because Henry, in his old sources, did not find the code where this error occurs, it’s still worth checking your systems.

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

An error was found by colleagues on the opensource project TCL, in all its current versions (including develop). Knowing that Postgres uses a similar API, it was easy to find out that feeding this regular Postgres expression results in a complete hang of the thread (process) processing the request.
')
An error occurs when such a grouping is only in the fifth or more order of nesting - i.e. four nested groups are correctly compiled and executed.

PostgreSQL example:

 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!

Since This error causes the thread to hang up at 100% busy, and since there are already bug reports (which, by the way, are being actively studied by hackers and the Kiddys script), as long as a search is in progress and the bug fix will not be released, I recommend checking your projects ( products) and in the case of a positive result, turn off the possibility of generating similar regular expressions or foreign input regulars in general.

Today, I dropped a bug-tracker of one of my friends in such a way twice, after hearing the abuse first, then that nothing was visible in the logs (the post arguments were disabled in the log), I heard thanks. For, forewarned - armed.

From the proven 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 comments of uv. starius ).
UPD: PostgreSQL 9.2.1, 9.2.2-2 - OK . (thanks to catlion and sdevalex ).