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

[Jim Meyering]

Paul Eggert wrote:
> On 06/17/11 01:46, Jim Meyering wrote:
>> +  MALLOC(merged.elems, position, 2 * d->nleaves);
>
> Hmm, aren't other buffer overruns possible in that
> area, via integer overflows?
>
> How about the additional patch given at the end of this
> message?  I haven't tested it because savannah grep doesn't
> build out of the box for me: ./bootstrap ends with 
>
> ./bootstrap: aclocal --force -I m4  ...
> configure.ac:88: warning: gt_LC_MESSAGES is m4_require'd but not m4_defun'd
> m4/localename.m4:7: gl_LOCALENAME is expanded from...
> m4/gnulib-comp.m4:278: gl_INIT is expanded from...
>
> and a few more lines like that (I suppose I should file
> another bug report, but I'm supposed to be finishing my
> grading now....).  Anyway, here's the untested patch:
>
> diff --git a/src/dfa.c b/src/dfa.c
> index c32d679..38f0566 100644
> --- a/src/dfa.c
> +++ b/src/dfa.c
> @@ -396,19 +396,20 @@ struct dfa
>  static void dfamust (struct dfa *dfa);
>  static void regexp (void);
>  
> -#define CALLOC(p, t, n) ((p) = xcalloc((size_t)(n), sizeof (t)))
> -#define MALLOC(p, t, n) ((p) = xmalloc((n) * sizeof (t)))
> -#define REALLOC(p, t, n) ((p) = xrealloc((p), (n) * sizeof (t)))
> +#define CALLOC(p, t, n) ((p) = XCALLOC (n, t))
> +#define MALLOC(p, t, n) ((p) = XNMALLOC (n, t))
> +#define REALLOC(p, t, n) ((p) = xnrealloc (p, n, sizeof (t)))
>  
>  /* Reallocate an array of type t if nalloc is too small for index. */
> -#define REALLOC_IF_NECESSARY(p, t, nalloc, index) \
> -  if ((index) >= (nalloc))                     \
> -    {                                                  \
> -      do                                       \
> -        (nalloc) *= 2;                                 \
> -      while ((index) >= (nalloc));             \
> -      REALLOC(p, t, nalloc);                   \
> -    }
> +#define REALLOC_IF_NECESSARY(p, t, nalloc, index)       \
> +  do                                                    \
> +    if ((nalloc) <= (index))                            \
> +      {                                                 \
> +        size_t new_nalloc = (index) + ! (p);            \
> +        (p) = x2nrealloc (p, &new_nalloc, sizeof (t));  \
> +        (nalloc) = new_nalloc;                          \
> +      }                                                 \
> +  while (false)

Thanks.

I've added the fixes in dfasearch.c and pcresearch.c and put your name on it.
Let me know if you'd like to change anything before I push it.

>From f97bf2652b87a094b1e6cf6dcd2f4f7526c35cc2 Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Sun, 19 Jun 2011 22:49:07 +0200
Subject: [PATCH] dfa: avoid possibility of overflow

* src/dfa.c (REALLOC_IF_NECESSARY, CALLOC, MALLOC, REALLOC):
Use functions from xalloc.h to avoid overflow.
* src/dfasearch.c (GEAcompile): Use xnrealloc rather than realloc.
* src/pcresearch.c (Pcompile): Use xnmalloc, not xmalloc.
---
 src/dfa.c        |   23 ++++++++++++-----------
 src/dfasearch.c  |    4 +---
 src/pcresearch.c |    2 +-
 3 files changed, 14 insertions(+), 15 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 0fcb2f0..0fc6c55 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -396,19 +396,20 @@ struct dfa
 static void dfamust (struct dfa *dfa);
 static void regexp (void);

-#define CALLOC(p, t, n) ((p) = xcalloc((size_t)(n), sizeof (t)))
-#define MALLOC(p, t, n) ((p) = xmalloc((n) * sizeof (t)))
-#define REALLOC(p, t, n) ((p) = xrealloc((p), (n) * sizeof (t)))
+#define CALLOC(p, t, n) ((p) = XCALLOC (n, t))
+#define MALLOC(p, t, n) ((p) = XNMALLOC (n, t))
+#define REALLOC(p, t, n) ((p) = xnrealloc (p, n, sizeof (t)))

 /* Reallocate an array of type t if nalloc is too small for index. */
-#define REALLOC_IF_NECESSARY(p, t, nalloc, index) \
-  if ((index) >= (nalloc))                       \
-    {                                            \
-      do                                         \
-        (nalloc) *= 2;                           \
-      while ((index) >= (nalloc));               \
-      REALLOC(p, t, nalloc);                     \
-    }
+#define REALLOC_IF_NECESSARY(p, t, nalloc, index)       \
+  do                                                    \
+    if ((nalloc) <= (index))                            \
+      {                                                 \
+        size_t new_nalloc = (index) + ! (p);            \
+        (p) = x2nrealloc (p, &new_nalloc, sizeof (t));  \
+        (nalloc) = new_nalloc;                          \
+      }                                                 \
+  while (false)


 #ifdef DEBUG
diff --git a/src/dfasearch.c b/src/dfasearch.c
index 8b40bca..3471308 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -162,9 +162,7 @@ GEAcompile (char const *pattern, size_t size, reg_syntax_t 
syntax_bits)
           total = 0;
         }

-      patterns = realloc (patterns, (pcount + 1) * sizeof (*patterns));
-      if (patterns == NULL)
-        error (EXIT_TROUBLE, errno, _("memory exhausted"));
+      patterns = xnrealloc (patterns, pcount + 1, sizeof *patterns);
       patterns[pcount] = patterns0;

       if ((err = re_compile_pattern (p, len,
diff --git a/src/pcresearch.c b/src/pcresearch.c
index 52db987..e8c7f4b 100644
--- a/src/pcresearch.c
+++ b/src/pcresearch.c
@@ -44,7 +44,7 @@ Pcompile (char const *pattern, size_t size)
 #else
   int e;
   char const *ep;
-  char *re = xmalloc (4 * size + 7);
+  char *re = xnmalloc (4, size + 7);
   int flags = PCRE_MULTILINE | (match_icase ? PCRE_CASELESS : 0);
   char const *patlim = pattern + size;
   char *n = re;
-- 
1.7.6.rc2.4.g36bfb.dirty