memory corruption in regex.c

[Alexandre Oliva]

https://bugzilla.redhat.com/show_bug.cgi?id=435767

emacs invokes undefined behavior in regex.c, computing the difference
between unrelated pointers.  In general, this wouldn't be too much of
a problem, as long as the type used to represent the difference was
wide enough to cover the entire possible range of pointer differences.

Such a type is not even guaranteed to exist, and it can be tricky to
get reasonable results on segmented architectures.  So, the correct
code needs to compute offsets between pointers in the old buffer, and
apply the same offset into the new buffer.  On most cases, the
compiler will just optimize the code to the same we got before on
i386, and to something very close, but using a 64-bit offset on
x86-64.

The problem I got, of semi-random "Regular expression too big" errors,
seems to have been caused at least in part by heap randomization, such
that regex buffers were *sometimes* (but somewhat rarely) moved to
locations that were too far away for the offset to be held correctly
in an int, and then Bad Things Happened.  I'm concerned that in this
case emacs core memory may be corrupted.

After the patch, I haven't seen the errors any more.  However, given
how difficult it was to trigger the bug in the first place, I can't be
sure it is gone for good.  But the fix is sound anyway.

This bug is present in emacs-22.1.50 and in current CVS.


for  src/ChangeLog
from  Alexandre Oliva  <address@hidden>

        * regex.c (MOVE_BUFFER_POINTER, EXTEND_BUFFER): Don't compute
        offsets between unrelated pointers.

--- emacs-22.1.50.orig/src/regex.c      2007-09-10 15:46:20.000000000 -0300
+++ emacs-22.1.50/src/regex.c   2008-03-22 08:07:06.000000000 -0300
@@ -3,7 +3,7 @@
    internationalization features.)
 
    Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001,
-                 2002, 2003, 2004, 2005, 2006, 2007
+                 2002, 2003, 2004, 2005, 2006, 2007, 2008
                  Free Software Foundation, Inc.
 
    This program is free software; you can redistribute it and/or modify
@@ -1832,8 +1832,10 @@
    being larger than MAX_BUF_SIZE, then flag memory exhausted.  */
 #if __BOUNDED_POINTERS__
 # define SET_HIGH_BOUND(P) (__ptrhigh (P) = __ptrlow (P) + bufp->allocated)
-# define MOVE_BUFFER_POINTER(P) \
-  (__ptrlow (P) += incr, SET_HIGH_BOUND (P), __ptrvalue (P) += incr)
+# define MOVE_BUFFER_POINTER(P)                                        \
+  (__ptrlow (P) = new_buffer + (__ptrlow (P) - old_buffer),    \
+   SET_HIGH_BOUND (P),                                         \
+   __ptrvalue (P) = new_buffer + (__ptrvalue (P) - old_buffer))
 # define ELSE_EXTEND_BUFFER_HIGH_BOUND         \
   else                                         \
     {                                          \
@@ -1847,12 +1849,12 @@
        SET_HIGH_BOUND (pending_exact);         \
     }
 #else
-# define MOVE_BUFFER_POINTER(P) (P) += incr
+# define MOVE_BUFFER_POINTER(P) ((P) = new_buffer + ((P) - old_buffer))
 # define ELSE_EXTEND_BUFFER_HIGH_BOUND
 #endif
 #define EXTEND_BUFFER()                                                        
\
   do {                                                                 \
-    re_char *old_buffer = bufp->buffer;                                        
\
+    unsigned char *old_buffer = bufp->buffer;                          \
     if (bufp->allocated == MAX_BUF_SIZE)                               \
       return REG_ESIZE;                                                        
\
     bufp->allocated <<= 1;                                             \
@@ -1864,7 +1866,7 @@
     /* If the buffer moved, move all the pointers into it.  */         \
     if (old_buffer != bufp->buffer)                                    \
       {                                                                        
\
-       int incr = bufp->buffer - old_buffer;                           \
+       unsigned char *new_buffer = bufp->buffer;                       \
        MOVE_BUFFER_POINTER (b);                                        \
        MOVE_BUFFER_POINTER (begalt);                                   \
        if (fixup_alt_jump)                                             \


-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   address@hidden, gcc.gnu.org}
Free Software Evangelist  address@hidden, gnu.org}