memory corruption in regex.c

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  <aoliva@redhat.com>

	* 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   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: memory corruption in regex.c

[Chong Yidong]

Alexandre Oliva <aoliva@redhat.com> writes:

> 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.

This sounds correct.  Thanks very much for catching this bug.  I don't
see any problem with your patch, except:

> -    re_char *old_buffer = bufp->buffer;					\
> +    unsigned char *old_buffer = bufp->buffer;				\

What is the purpose of this?

Re: memory corruption in regex.c

[Alexandre Oliva]

On Mar 22, 2008, Chong Yidong <cyd@stupidchicken.com> wrote:

>> -    re_char *old_buffer = bufp->buffer;					\
>> +    unsigned char *old_buffer = bufp->buffer;				\

> What is the purpose of this?

Compiler warning avoidance.  b is unsigned char *, whereas re_char is
const unsigned char *.  I suppose it would be enough for new_buffer to
be non-const, but these buffers are not const anyway, and the
constness doesn't buy much at this point.

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

Re: memory corruption in regex.c

[Chong Yidong]

Alexandre Oliva <aoliva@redhat.com> writes:

> On Mar 22, 2008, Chong Yidong <cyd@stupidchicken.com> wrote:
>
>>> -    re_char *old_buffer = bufp->buffer;					\
>>> +    unsigned char *old_buffer = bufp->buffer;				\
>
>> What is the purpose of this?
>
> Compiler warning avoidance.  b is unsigned char *, whereas re_char is
> const unsigned char *.  I suppose it would be enough for new_buffer to
> be non-const, but these buffers are not const anyway, and the
> constness doesn't buy much at this point.

Thanks.

I've checked in your patch.