Regular expressions cause out of memory or SIGSEGV

Binary package hint: libc6

It seems that even very simple regular expressions can be used to consume large amounts of memory and CPU resources in the re_compile_pattern function of libc. I know that this might be the side-effect of a feature needed for "normal" regex parsing operation, but perhaps the consequences could be handled somehow more gracefully.

All issues seem related to the OP_OPEN_DUP_NUM in parsing, which is triggered, according to my understanding of the libc source, by "{a,b}" "*" and "+" tokens in an extended regular expression, e.g.

grep -E -e '(){0,999}+'
grep -E -e 'x{0,32767}'

While running on platforms with more than 4GB of machine memory, such expressions will only cause high load and
"Memory exhausted" messages. On smaller systems, they might trigger the oom-killer, which caused the killing of other processes, e.g. the apache threads on the test system, perhaps due to the sorting in the process table. Due to the (broken?) out-of-memory handling in the pattern-compile, this can also be used to crash a program with SEGV when it calls the pattern-compile function with limited resources, e.g.

bash -c "ulimit -v 50000; grep -E -e '.++++++++++++++++++++++'"
bash: line 1: 4605 Segmentation fault grep -E -e '.++++++++++++++++++++++'
Mar 16 12:26:08 kernel: grep[4605]: segfault at 18 ip b7f13163 sp bffd8654 error 4 in libc-2.7.so[b7e63000+149000]

bash -c "ulimit -v 50000; grep -E -e '[+]++++++++++++++++++'"
bash: line 1: 4626 Segmentation fault grep -E -e '[+]++++++++++++++++++'
Mar 16 12:30:21 kernel: grep[4626]: segfault at b7a28004 ip b7e7d4ac sp bfe80eb8 error 4 in libc-2.7.so[b7e0e000+149000]

The crashes with ptr NULL+18 and xxxxx004 are both triggered in free:
0xb7e0a4ac <free+76>: mov 0x4(%eax),%eax

Without analysis of source it was not possible to gain full control over the pointer.

You might want to use
bash -c "ulimit -v 50000; gdb --args grep -E -e '[+]++++++++++++++++++'"
for debugging.