[Bug 343894] Re: Regular expressions cause out of memory or SIGSEGV

[Jodie Cunningham]

Just confirmed that this still affects Ubuntu 14.04


Specifically, this is the command I tested, which segfaulted:

bash -c "ulimit -v 50000; grep -E -e '.++++++++++++++++++++++'"

-- 
You received this bug notification because you are a member of Ubuntu
Foundations Bugs, which is subscribed to glibc in Ubuntu.
https://bugs.launchpad.net/bugs/343894

Title:
  Regular expressions cause out of memory or SIGSEGV

Status in glibc package in Ubuntu:
  Confirmed

Bug description:
  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.

To manage notifications about this bug go to:
https://bugs.launchpad.net/ubuntu/+source/glibc/+bug/343894/+subscriptions