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 <meyer...@redhat.com>
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 <meyer...@redhat.com>
+
+ 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 <br...@clisp.org>
Paul Eggert <egg...@cs.ucla.edu>
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
