PostgreSQL, TCL и другие: Критическая ошибка в RE engine. Возможная уязвимость

Хочу обратить внимание хабрасообщества на возможную «уязвимость» в TCL, PostgreSQL и теоретически в некоторых других системах использующих RE engine, или NFA утилиты, изначально написаные самим Генри Спенсором (Henry Spencer). Измененных исходников можно найти добрую сотню (у того же Sun Microsystems, UUNET и т.д.). И хотя я не думаю что баг существует изначально с далеких 1998-х, хотя бы потому, что кода где возникает эта ошибка я у Генри, в старых его источниках, не нашел, проверить ваши системы все-таки стоит.

И так ошибка: это busyloop на стадии компиляции регулярного выражения вида (((((x)*)*)*)*)*. Причем именно не исполнения, а компиляции, т.е. если есть проверка валидности регулярки и она базируется на том же коде NFA — имеем тот же безконечный цикл + 100% cpu usage.

Ошибку нашли коллеги по opensource проекту TCL, во всех его актуальных версиях (включая develop). Зная, что Postgres использует похожее API, нетрудно было выяснить, что скармливание этого регулярного выражения Postgres приводит к такой же ошибке.

Ошибка возникает при таком группировании только в пятом и более порядке вложенности — т.е. четыре вложеных группы корректно компилируются и исполняются.

Пример для PostgreSQL:

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

!busyloop!

Пример для TCL:

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

!busyloop!

Т.к. эта ошибка приводит к подвисанию потока при 100% busy, и ввиду того, что уже имеются bug reports (которые, кстати, очень активно штудируются хакерами и скрипт-киддис), пока идет поиск и не будет выпущен bug fix, рекомендую проверить свои проекты (продукты) и в случае положительного результата, поотключать возможность генерации подобных регулярных выражений или foreign input регулярок вообще.

Сегодня целых два раза уронил таким способом баг-трекер одного своего друга, после чего выслушав сперва ругань, затем что в логах ничего не было видно (аргументы post у него отключены в логе), затем — спасибо. Ибо, предупрежден — вооружен.

Из проверенного уязвимы:
TCL 8.4, 8.5, 8.6 — FAILED.
PostgreSQL 8.4, 9.1, 9.2 — FAILED.

Не подвержены ошибке:
Python 2.5.2 и 2.7 — OK.