View Issue Details

IDProjectCategoryView StatusLast Update
0000532LDMud 3.3Efunspublic2018-01-29 22:57
Reporterchaos Assigned Tozesstra  
PrioritynormalSeveritycrashReproducibilityalways
Status resolvedResolutionfixed 
Product Version3.3.716 
Fixed in Version3.3.717 
Summary0000532: restore_value() segfaults on large inputs on 64-bit Debian; alloca() related
DescriptionProduct version is actually 3.3.716 (Mantis only knows about 3.3.715).

On my amd64 Debian system, restore_value() will segfault if fed a sufficiently large input; attached file (uncompress first) will trigger the behavior. Error is:

0x00000000004a7dbf in f_restore_value (sp=0x67ef20) at object.c:9058
9058 memcpy(buff, get_txt(sp->u.str), len);
(gdb) print buff
$1 = 0x7fffd0904d40 <Address 0x7fffd0904d40 out of bounds>

This appears to be a failure of alloca() on this architecture; as a workaround I modified f_restore_value() to manage 'buff' using xalloc() and xfree() instead of alloca(), and this alleviated the problem.
Additional InformationSeems likely that other uses of alloca() may fail on large sizes.
TagsNo tags attached.

Relationships

related to 0000553 resolvedGnomi LDMud 3.2 Backports of 3.3 fixes for 3.2.16 
child of 0000545 new LDMud 3.3 Usages of alloca() have to be checked for possible stack overflow 

Activities

chaos

2008-02-19 08:28

reporter   ~0000596

Please disregard in favor of next ticket; the file upload attempted with this one failed.

zesstra

2008-02-19 12:26

administrator   ~0000597

You may just attach your file to this ticket, no need to open a new one.

Yes, alloca() allocates memory on the stack and that is often limited to 8 MB by default, so its relatively "easy" to hit that limit.

Note that the check after the alloca() doesn't work on my machine as well. alloca() seems to happily allocate memory exceeding the stack limit for the process (without returning NULL) and upon accessing it or calling a function (which implicitly accesses the out-of-bounds stack now) the driver crashes.
According to the manpage its behaviour is machine and compiler dependent. (You can try the behaviour on your system with the very simple test program I will attach.)

One problems is: It is not very straight-forward to determine the already used stack size as there is no libc function for it, otherwise you could check beforehand if there is enough space on the stack + a safety margin. Therefore it is probably indeed a good idea to replace other alloca() as well or introduce a (rather low) limit for all alloca() (which may impair legitimate uses) and will not work if you heavily recursed and use already quite a lot of the available stack space.

Note: For MG we use a stack size limit of 128MB at the moment, because of such potential problems and the PCRE crash reported in 0000524, but that doesn't solve the basic problem.

2008-02-19 12:35

 

alloca_test.c (320 bytes)   
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>

#define KB 1024

int main() {
  long count = 0;
  uintptr_t *ptr;

  while(1) {
    ptr = alloca((size_t)KB);
    if (!ptr) break;
    
    printf("Allocated %ld KB on the stack, got address %p\n",
	++count,(void*)ptr); 
  }
  return 0;
}

alloca_test.c (320 bytes)   

zesstra

2008-02-19 12:47

administrator   ~0000598

Hmpf, I forgot: My system here is 32 bit based, it is definitely not a 64 bit issue. A quick search suggests that it is quite common for alloca() implementations not to return NULL upon out-of-stack-memory. From a BSD man page: "if the allocated block is beyond the current stack limit, the resulting behavior is undefined." I assume that on most systems this crash s reproducible.
(BTW: the man page on MacOS is just wrong. :-( )

chaos

2008-02-19 14:11

reporter   ~0000599

Additional data: I had suspected a 64-bit issue because the same data being processed by 3.2.15 restore_value() (also uses alloca()) on intel32 FreeBSD 5.4 works fine.

So, yeah, glibc's fault.

zesstra

2008-02-19 14:25

administrator   ~0000600

How large was that string and stack size limit you used there? alloca() on FreeBSD 5.4 may well behave the same behaviour, maybe the stack size limit was just bigger and you didn't hit the limit. At least FreeBSD 6.2 has the same behaviour according to its manpage. It says:
"The allocation made may exceed the bounds of the stack, or even go further into other objects in memory, and alloca() cannot determine such an error."

So I would check if either the stack limit was higher on your FreeBSD or if the process just didn't get killed and potentially overwrote stuff after/below the stack (on Linux that would be system/shared lib code, but I don't know how FreeBSD organizes the process' address space.
(The latter behaviour would be especially interesting as it may allow to inject code into the drivers process.)

zesstra

2008-02-19 18:11

administrator   ~0000601

I thought a little bit about my last note and tested the alloca() on 2 systems (MacOS 10.5 and Debian etch). Basically on both systems alloca() gave me any address in the virtual address space of the process I wanted to have. So you can write arbitrary data to arbitrary memory addresses in the driver's address space.
Of course, in practice you are limited by the possible size of the string to restore_value() (AFAIK LPC strings are only limited by the amount of memory available).
If you know the process image layout and where the systems shared libs are mapped and which memory areas are not write-protected, you may really be able to inject code remotely if you know what you do (I don't, that said.).
(simplified and quick example: in a small test program I expanded the stack into an address range allocated by the heap. That area is not write-protected so you can overwrite the data there or continue program execution (calling functions is possible because the system simply expands the stack happily further into the heap). Although simply overwriting the heap should be detected by the driver's memory allocator later, resulting in calling fatal().)

BTW, there are 69 calls to alloca(), some of them in efuns, probably one has to have a closer look at them, if they may be a problem. They contain checks for NULL pointers, but... *sigh*

chaos

2008-02-20 14:09

reporter   ~0000604

Re: your question about my FreeBSD environment, I don't know how to find out what stack size gcc sets up (I'm thinking that's the relevant stack size, rather than the LPC interpreter's stack). Google shows me articles which speak of the stack size being "unlimited" unless changed with ulimit, but we seem to be seeing that alloca() interacts with it in a way that doesn't cause it to expand when needed.

http://www.irccrew.org/~cras/security/howto/dynamic.html has commentary on alloca() that pretty much says that it's completely unsafe to use on any arbitrary or user-provided data, and portability-negative too.

zesstra

2008-02-20 15:43

administrator   ~0000605

I would say, the people on irccrew.org are right with that opinion.

And yes, I did not mean the LPC stack. ;-) It is, how much memory space your system wants to permit the process to use (obviously it does only weakly enforce it). You can find that out by executing 'ulimit -a' in your shell, there should be an entry "stack size", that is the maximum amount of memory the process started in that shell should use for the stack. (You can also change it with ulimit.)

Example:
On my system the memory of the process looks like this (system-dependent!):
-----<stack><stackguard>--------<syslibs>---------<heap><executable>
(all --- may be used for the heap, it grows from right to left here)
The <stackguard> is read and write protected, so any access there gets the process killed, if you extend the stack into to the <stackguard> area. If you manage to "jump" over it at get from alloca() an address where you can write, your process doesn't get killed.
Linux AFAIK even doesn't have this stackguard area, there stack and heap are next to each other, if that neighbouring heap area is allocated by your process, you may not even notice it for some time, if the stack grows into the heap.

chaos

2008-02-20 15:51

reporter   ~0000606

Okay. ulimit -a shows a stack size of 8192K on the Debian system and 65536K on the FreeBSD system, so that's consistent with observed behavior.

zesstra

2008-05-06 14:22

administrator   ~0000611

Yesterday Gnomi and me had a discussion about the use of alloca() in the driver.
Basically there seem to be 3 possibilities:
1) use alloca() only for small allocations (<200 byte) and only if it is guaranteed to be not more. Consequently change all other alloca() to xalloc().
2) There is a alloc.c in the driver source, using mempools to allocate memory and it reclaims storage allocated deeper in the stack. We might use this palloca() instead of alloca(). But I am not sure if it is finished yet.
3) continue to use alloca() but always check before if there is enough stack space left. This can be determined by using the initial stack pointer upon start-up, the current stack pointer, the direction in which the stack grows and RLIMIT_STACK from getrlimit().

2) and 3) have the advantage of not having to free the memory manually.
With 3) a function may still use a lot of stack space and potentially crash upon calling other functions.
1) may increase fragmentation of the heap and we have to keep in mind all return paths out of the function for freeing the memory.

Any favorites?

chaos

2008-07-02 10:17

reporter   ~0000661

Last edited: 2008-07-02 10:17

3) doesn't seem like a good idea; what will it do when there isn't enough memory on the stack, error out? Then lib code will error at random based on stack conditions, and a new unanticipated failure condition has been introduced into all the functions using alloca; seems very unfriendly. The only alternative I see to erroring out is switching to using xalloc, and then really you may as well have just used xalloc in the first place.

I can't really evaluate 2); if it's not clear that the function is finished, it sounds like it's going to be flaky.

So 1), the painful one, kinda sounds the best.

zesstra

2008-07-02 19:11

administrator   ~0000665

I still think, palloca() has some potential, but to have a fix ready for this one I just changed f_restore_value() to use xalloc/xfree for the buffer. I noticed 6 return paths in the function, if somebody reads the diff, please double-check that I did not miss one. ;-)

Gnomi

2008-07-03 03:46

manager   ~0000666

restore_svalue might throw errors that abort through a longjmp. Mostly out of memory errors, but also on illegal array sizes (e.g. restore_value("0000001:0\n({" + "0,"*100000 + "})\n")). So I would recommend using the already existing error handler (restore_value_cleanup) to catch these.

2008-07-03 05:27

 

restore_value-2.diff (2,639 bytes)   
diff --git a/src/object.c b/src/object.c
index 41750ac..384baf7 100644
--- a/src/object.c
+++ b/src/object.c
@@ -8996,13 +8996,20 @@ static int nesting = 0;  /* Used to detect recursive calls */
 
 /*-------------------------------------------------------------------------*/
 static void
-restore_value_cleanup ( svalue_t * arg UNUSED)
+restore_value_cleanup ( svalue_t * arg )
 
 /* The error handler during restore value cleanup: free all resources.
  */
 
 {
+    restore_cleanup_t * data = (restore_cleanup_t *) arg;
+
+    if (data->buff)
+        xfree(data->buff);
+
     free_shared_restored_values();
+
+    xfree(arg);
 } /* restore_value_cleanup() */
 
 svalue_t *
@@ -9021,7 +9028,7 @@ f_restore_value (svalue_t *sp)
     int        restored_version; /* Formatversion of the saved data */
     char      *buff;  /* The string to parse */
     char      *p;
-    svalue_t   rcp; /* T_ERROR_HANDLER value */
+    restore_cleanup_t *rcp; /* Cleanup structure */
 
     /* The restore routines will put \0s into the string, so we
      * need to make a copy of all but malloced strings.
@@ -9030,10 +9037,10 @@ f_restore_value (svalue_t *sp)
         size_t len;
 
         len = mstrsize(sp->u.str);
-        buff = alloca(len+1);
+        buff = xalloc(len+1);
         if (!buff)
         {
-            errorf("(restore) Out of stack (%lu bytes).\n"
+            errorf("(restore) Out of memory (%lu bytes).\n"
                  , (unsigned long) len+1);
             /* NOTREACHED */
             return sp;
@@ -9056,6 +9063,7 @@ f_restore_value (svalue_t *sp)
         p = strchr(buff, '\n');
         if (!p)
         {
+            xfree(buff);
             errorf("No data given.\n");
             return sp-1;
         }
@@ -9075,6 +9083,7 @@ f_restore_value (svalue_t *sp)
     shared_restored_values = xalloc(sizeof(svalue_t)*max_shared_restored);
     if (!shared_restored_values)
     {
+        xfree(buff);
         errorf("(restore) Out of memory (%lu bytes) for shared values.\n"
              , max_shared_restored * sizeof(svalue_t));
         return sp; /* flow control hint */
@@ -9087,7 +9096,18 @@ f_restore_value (svalue_t *sp)
     *sp = const0;
 
     /* Setup the error cleanup */
-    push_error_handler(restore_value_cleanup, &rcp);
+    rcp = xalloc(sizeof(*rcp));
+    if (!rcp)
+    {
+        xfree(buff);
+        errorf("(restore) Out of memory (%lu bytes).\n"
+              , (unsigned long) sizeof(*rcp));
+        /* NOTREACHED */
+        return sp;
+    }
+    rcp->buff = buff;
+
+    push_error_handler(restore_value_cleanup, &(rcp->head));
 
     /* Now parse the value in buff[] */
 
restore_value-2.diff (2,639 bytes)   

fufu

2008-07-03 05:30

manager   ~0000667

How about this?

We could cheat and use a global variable, but I'd rather eliminate those than introduce new ones.

Gnomi

2008-07-03 05:40

manager   ~0000668

A global variable is not an option, because restore_value/object calls can be quite recursive (e.g. "#e:efun" can raise a privilege violation and the master can then call restore_value/object again).

zesstra

2008-07-03 05:54

administrator   ~0000669

Ok, had the same in mind after Gnomis comment, but had no time during the day.
I think using the restore_cleanup_t for transfering the address of buff is just fine.
There is IMHO one problem left, which I also missed in my first patch: buff is changed in line 9070: buff = p+1; We have to account for this and use the original address of the allocated memory for xfree and the cleanup structure.

2008-07-03 06:08

 

restore_value-2a.diff (1,447 bytes)   
diff --git a/src/object.c b/src/object.c
index 384baf7..86ab239 100644
--- a/src/object.c
+++ b/src/object.c
@@ -9052,24 +9052,6 @@ f_restore_value (svalue_t *sp)
     restored_version = -1;
     restored_host = -1;
 
-    /* Check if there is a version line */
-    if (buff[0] == '#')
-    {
-        int i;
-
-        i = sscanf(buff+1, "%d:%d", &restored_version, &restored_host);
-
-        /* Advance to the next line */
-        p = strchr(buff, '\n');
-        if (!p)
-        {
-            xfree(buff);
-            errorf("No data given.\n");
-            return sp-1;
-        }
-        buff = p+1;
-    }
-
     /* Initialise the shared value table */
 
     max_shared_restored = 64;
@@ -9109,9 +9091,28 @@ f_restore_value (svalue_t *sp)
 
     push_error_handler(restore_value_cleanup, &(rcp->head));
 
+    /* Check if there is a version line */
+    if (buff[0] == '#')
+    {
+        int i;
+
+        i = sscanf(buff+1, "%d:%d", &restored_version, &restored_host);
+
+        /* Advance to the next line */
+        p = strchr(buff, '\n');
+        if (!p)
+        {
+            errorf("No data given.\n");
+            return sp-1;
+        }
+        p++;
+    }
+    else
+        p = buff; /* parse from beginning of buffer */
+
+
     /* Now parse the value in buff[] */
 
-    p = buff;
     if ( (restored_version < 0 && p[0] == '\"')
          ? !old_restore_string(sp, p)
          : !restore_svalue(sp, &p, '\n')
restore_value-2a.diff (1,447 bytes)   

fufu

2008-07-03 06:09

manager   ~0000670

good point. I think the easiest solution is to check whether a version is there after setting up the error handler, see latest patch. (restore_value-2a.diff applies on top of restore_value-2.diff)

zesstra

2008-07-03 07:04

administrator   ~0000671

Looks good for me.
I wrote a small test yesterday, once the testsuite is available in SVN I could commit the test (although it heavily depends on the available stack memory, so it just feeds some 50MB of zeroes into restore_value()...).

Gnomi

2008-07-04 07:47

manager   ~0000672

Last edited: 2008-07-04 07:47

Looks good for me too.

zesstra

2008-07-08 16:53

administrator   ~0000684

Fuchur, do you want to apply your patches yourself?

fufu

2008-07-09 09:19

manager   ~0000701

(Zesstra) Fuchur, do you want to apply your patches yourself?
Done now, see SVN revision 2377.

Issue History

Date Modified Username Field Change
2008-02-19 08:24 chaos New Issue
2008-02-19 08:28 chaos Note Added: 0000596
2008-02-19 12:26 zesstra Note Added: 0000597
2008-02-19 12:35 zesstra File Added: alloca_test.c
2008-02-19 12:47 zesstra Note Added: 0000598
2008-02-19 14:11 chaos Note Added: 0000599
2008-02-19 14:25 zesstra Note Added: 0000600
2008-02-19 18:11 zesstra Note Added: 0000601
2008-02-20 14:09 chaos Note Added: 0000604
2008-02-20 15:43 zesstra Note Added: 0000605
2008-02-20 15:51 chaos Note Added: 0000606
2008-05-06 14:22 zesstra Note Added: 0000611
2008-07-02 04:47 zesstra Assigned To => zesstra
2008-07-02 04:47 zesstra Status new => acknowledged
2008-07-02 04:47 zesstra Product Version 3.3.715 => 3.3.716
2008-07-02 05:49 zesstra Relationship added child of 0000545
2008-07-02 10:01 zesstra Status acknowledged => assigned
2008-07-02 10:17 chaos Note Added: 0000661
2008-07-02 10:17 chaos Note Edited: 0000661
2008-07-02 19:05 zesstra File Added: restore_value.diff
2008-07-02 19:11 zesstra Note Added: 0000665
2008-07-03 03:46 Gnomi Note Added: 0000666
2008-07-03 05:27 fufu File Added: restore_value-2.diff
2008-07-03 05:30 fufu Note Added: 0000667
2008-07-03 05:39 zesstra File Deleted: restore_value.diff
2008-07-03 05:40 Gnomi Note Added: 0000668
2008-07-03 05:54 zesstra Note Added: 0000669
2008-07-03 06:08 fufu File Added: restore_value-2a.diff
2008-07-03 06:09 fufu Note Added: 0000670
2008-07-03 07:04 zesstra Note Added: 0000671
2008-07-04 07:47 Gnomi Note Added: 0000672
2008-07-04 07:47 Gnomi Note Edited: 0000672
2008-07-08 16:53 zesstra Note Added: 0000684
2008-07-09 09:19 fufu Status assigned => resolved
2008-07-09 09:19 fufu Resolution open => fixed
2008-07-09 09:19 fufu Note Added: 0000701
2008-07-09 10:01 zesstra Fixed in Version => 3.3.717
2008-07-10 09:36 Gnomi Relationship added related to 0000553
2010-11-16 10:42 user43 Source_changeset_attached => ldmud.git master b7721727
2010-11-16 10:42 zesstra Source_changeset_attached => ldmud.git master 39b4f837
2018-01-29 19:59 Source_changeset_attached => ldmud.git master b7721727
2018-01-29 19:59 zesstra Source_changeset_attached => ldmud.git master 39b4f837
2018-01-29 22:57 Source_changeset_attached => ldmud.git master b7721727
2018-01-29 22:57 zesstra Source_changeset_attached => ldmud.git master 39b4f837