[PATCH] dfa: don't overrun a malloc'd buffer for certain regexps

[Jim Meyering]

If you give your favorite grep program the wrong ERE,
it may clobber the heap:

    $ grep -E '(^| )*(a|b)*(c|d)*( |$)' < /dev/null
    [Exit 139 (SEGV)]

This bug affects gawk, too, since they use the same dfa.c:

    $gawk '{ /(^| )*(a|b)*(c|d)*( |$)/ }' < /dev/null
    [Exit 139 (SEGV)]



>From 0b91d6928e9d098d3746ce9f4bb4160a2e685f5c Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Fri, 17 Jun 2011 10:27:06 +0200
Subject: [PATCH] dfa: don't overrun a malloc'd buffer for certain regexps

* src/dfa.c (dfaanalyze): Allocate space for twice as many
positions as there are leaves.  Before this change, for some
regular expressions, DFA analysis would have inserted far more
"positions" than dfa->nleaves (up to double).
Reported by Raymond Russell in http://savannah.gnu.org/bugs/?33547
* tests/dfa-heap-overrun: Trigger the overrun.
* tests/Makefile.am (TESTS): Add it.
* NEWS (Bug fixes): Mention it.
---
 NEWS                   |    3 +++
 src/dfa.c              |    2 +-
 tests/Makefile.am      |    4 ++--
 tests/dfa-heap-overrun |   26 ++++++++++++++++++++++++++
 4 files changed, 32 insertions(+), 3 deletions(-)
 create mode 100755 tests/dfa-heap-overrun

diff --git a/NEWS b/NEWS
index d026448..3354d50 100644
--- a/NEWS
+++ b/NEWS
@@ -4,6 +4,9 @@ GNU grep NEWS                                    -*- outline -*-

 ** Bug fixes

+  grep no longer clobbers heap for an ERE like '(^| )*( |$)'
+  [bug introduced in grep-2.6]
+
   grep is faster on regular expressions that match multibyte characters
   in brackets (such as '[áéíóú]').

diff --git a/src/dfa.c b/src/dfa.c
index 873530f..c32d679 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -2134,7 +2134,7 @@ dfaanalyze (struct dfa *d, int searchflag)
   MALLOC(lastpos, position, d->nleaves);
   o_lastpos = lastpos, lastpos += d->nleaves;
   CALLOC(nalloc, int, d->tindex);
-  MALLOC(merged.elems, position, d->nleaves);
+  MALLOC(merged.elems, position, 2 * d->nleaves);

   CALLOC(d->follows, position_set, d->tindex);

diff --git a/tests/Makefile.am b/tests/Makefile.am
index 8d51727..1f0d2cf 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -46,6 +46,7 @@ TESTS =                                               \
   case-fold-char-range                         \
   case-fold-char-type                          \
   char-class-multibyte                         \
+  dfa-heap-overrun                             \
   dfaexec-multibyte                            \
   empty                                                \
   equiv-classes                                 \
@@ -103,7 +104,6 @@ MALLOC_PERTURB_ = 1
 TESTS_ENVIRONMENT =                            \
   tmp__=$$TMPDIR; test -d "$$tmp__" || tmp__=.;        \
   TMPDIR=$$tmp__; export TMPDIR;               \
-  exec 9>&2;                                   \
   shell_or_perl_() {                           \
     if grep '^\#!/usr/bin/perl' "$$1" > /dev/null; then                        
\
       if $(PERL) -e 'use warnings' > /dev/null 2>&1; then              \
@@ -141,6 +141,6 @@ TESTS_ENVIRONMENT =                         \
   PERL='$(PERL)'                               \
   SHELL='$(SHELL)'                             \
   PATH='$(abs_top_builddir)/src$(PATH_SEPARATOR)'"$$PATH" \
-  ; shell_or_perl_
+  ; shell_or_perl_ 9>&2

 VERBOSE = yes
diff --git a/tests/dfa-heap-overrun b/tests/dfa-heap-overrun
new file mode 100755
index 0000000..dda1c12
--- /dev/null
+++ b/tests/dfa-heap-overrun
@@ -0,0 +1,26 @@
+#!/bin/sh
+# Trigger a heap overrun in grep-2.6..grep-2.8.
+
+# Copyright (C) 2011 Free Software Foundation, Inc.
+
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+. "${srcdir=.}/init.sh"; path_prepend_ ../src
+
+fail=0
+
+grep -E '(^| )*(a|b)*(c|d)*( |$)' < /dev/null
+test $? = 1 || fail=1
+
+Exit $fail
--
1.7.6.rc0.293.g40857