[PATCH] regex: don't infloop on persistent failing calloc

[Jim Meyering]

FYI,

I found that grep would infloop in a restricted-memory environment,
and that this regex bug was at the root of the problem.
I discovered this with a grep binary built to use glibc's regex code.
Attempting the same exploit using a grep binary built --with-included-regex,
the problem did not arise immediately, probably because a fixed memory
limit does not apply equally to the two implementations.

To provoke the infloop, I did this on an x86_64 F14 system:

    $ (ulimit -v 9000; ./grep --color -f <(seq 500) <(seq 99); echo $?)

It prints only 39 lines, and then hangs.
Attach to that its PID using gdb:

    (gdb) w
    #0  0x00000030230dc69a in brk () from /lib64/libc.so.6
    #1  0x00000030230dc745 in sbrk () from /lib64/libc.so.6
    #2  0x000000302307f389 in mabort () from /lib64/libc.so.6
    #3  0x000000302307aa9c in _int_malloc () from /lib64/libc.so.6
    #4  0x000000302307aed8 in malloc_check () from /lib64/libc.so.6
    #5  0x000000302307e24e in calloc () from /lib64/libc.so.6
    #6  0x00000030230be682 in build_trtable () from /lib64/libc.so.6
    #7  0x00000030230c4781 in re_search_internal () from /lib64/libc.so.6
    #8  0x00000030230c90ae in re_search_stub () from /lib64/libc.so.6
    #9  0x00000030230c99f8 in re_match_2 () from /lib64/libc.so.6

While poking around, I provoked a different problem:

  $ (ulimit -v 15000; grep -f <(seq 4000) k; echo $?)
  *** glibc detected *** grep: free(): invalid pointer: 0x3c3c3c3c3c3c3c3c ***
  134

That one is in grep's dfa.c, but I haven't tracked it down yet:

  #0  0x00007f1f7c5b5085 in raise () from /lib64/libc-2.12.90.so
  #1  0x00007f1f7c5b6a36 in abort () from /lib64/libc-2.12.90.so
  #2  0x00007f1f7c5f256b in __libc_message () from /lib64/libc-2.12.90.so
  #3  0x00007f1f7c5fa6e4 in free_check () from /lib64/libc-2.12.90.so
  #4  0x0000000000407fd5 in freelist (cpp=<value optimized out>) at dfa.c:3628
  #5  0x000000000040dfa5 in dfamust (s=<value optimized out>, len=<value
  optimized out>, d=<value optimized out>, searchflag=<value optimized
  out>) at dfa.c:4008
  #6  dfacomp (s=<value optimized out>, len=<value optimized out>,
  d=<value optimized out>, searchflag=<value optimized out>) at dfa.c:3446
  #7  0x0000000000402a36 in GEAcompile (pattern=0x1711260
  
"1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11\n12\n13\n14\n15\n16\n17\n18\n19\n20\n21\n22\n23\n24\n25\n26\n27\n28\n29\n30\n31\n32\n33\n34\n35\n36\n37\n38\n39\n40\n41\n42\n43\n44\n45\n46\n47\n48\n49\n50\n51\n52\n53\n54\n55\n56\n57\n58\n59\n60\n61\n62\n63\n64\n65\n66\n67\n68\n69\n70"...,
  size=23892, syntax_bits=68358) at dfasearch.c:210
  #8  0x0000000000405e03 in main (argc=5, argv=0x7fffe82bc568) at main.c:2151

Here's the patch I've pushed:

>From 028e437c6da50340f95b83978a25748e427012ae Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Tue, 28 Dec 2010 15:12:47 +0100
Subject: [PATCH] regex: don't infloop on persistent failing calloc

* lib/regexec.c (build_trtable): Return failure indication upon
calloc failure.  Otherwise, re_search_internal could infloop on OOM.
In glibc, this was fixed for version 2.13:
http://sourceware.org/bugzilla/show_bug.cgi?id=12348
---
 ChangeLog     |    8 ++++++++
 lib/regexec.c |    2 ++
 2 files changed, 10 insertions(+), 0 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 0d175a2..0a17782 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2010-12-28  Jim Meyering  <address@hidden>
+
+       regex: don't infloop on persistent failing calloc
+       * lib/regexec.c (build_trtable): Return failure indication upon
+       calloc failure.  Otherwise, re_search_internal could infloop on OOM.
+       In glibc, this was fixed for version 2.13:
+       http://sourceware.org/bugzilla/show_bug.cgi?id=12348
+
 2010-12-28  Bruno Haible  <address@hidden>
             Paul Eggert <address@hidden>

diff --git a/lib/regexec.c b/lib/regexec.c
index 9388ac1..ee702bc 100644
--- a/lib/regexec.c
+++ b/lib/regexec.c
@@ -3402,6 +3402,8 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
        {
          state->trtable = (re_dfastate_t **)
            calloc (sizeof (re_dfastate_t *), SBC_MAX);
+          if (BE (state->trtable == NULL, 0))
+            return false;
          return true;
        }
       return false;
--
1.7.3.4