Jason, this is actually incorrect. The IS_MMAPPED value is defined as 0x2. This means that 0x4, 0x5, and 0x8 all do not have the IS_MMAPPED flag set. (Neither would 0x9). 0x4 would have the NON_MAIN_ARENA flag set 0x5 would have the NON_MAIN_ARENA and PREV_INUSE flags set 0x8 would have no flags set. -- malloc.c -- /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */ #define PREV_INUSE 0x1 ... /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */ #define IS_MMAPPED 0x2 ... /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained from a non-main arena. This is only set immediately before handing the chunk to the user, if necessary. */ #define NON_MAIN_ARENA 0x4 -- Aaron Adams On Tue, 20 May 2003, Jason_Royes wrote: > This may be totally incorrect, but here's my armchair analysis. > On glibc systems: 0x4, 0x5 and 0x8 all have the IS_MMAPPED bit turned on > (0x9 does not), meaning the chunk is allocated with mmap. Which means > they're free'd by munmap_chunk (when free(buf2) is called), which in > turn calls munmap on an invalid memory address. The invalid memory > address is equal to p - p->prev_size, where prev_size is the last 4 > bytes of buf1 (i.e. some big number). This results in a segfault. > > -- snip:malloc.c -- > static void > internal_function > #if __STD_C > munmap_chunk(mchunkptr p) > #else > munmap_chunk(p) mchunkptr p; > #endif > { > /* JR: size = 0x10{4,5,8} */ > INTERNAL_SIZE_T size = chunksize(p); > int ret; > > assert (chunk_is_mmapped(p)); > assert(! ((char*)p >= sbrk_base && (char*)p < sbrk_base + > sbrked_mem)); > assert((n_mmaps > 0)); > /* > * JR: ensure length is multiple of pagesize > * prev_size = < last 4 bytes of buf1 > > */ > assert(((p->prev_size + size) & (malloc_getpagesize-1)) == 0); > > n_mmaps--; > mmapped_mem -= (size + p->prev_size); > > /* unmap */ > /* JR: Memory Access Violation p->prev_size is huge */ > ret = munmap((char *)p - p->prev_size, size + p->prev_size); > > /* munmap returns non-zero on failure */ > assert(ret == 0); > } > > -- > > EOF > > > On Tue, 2003-05-20 at 19:19, Aaron Adams wrote: > > For each challenge program that we release we will do our best to post a > > summary that includes our intentions for releasing the particular program. > > We will also explain and summarize some of the findings by people who took > > part in the discussion. > > > > VulnDev2.c is currently in the works and will hopefully be released May > > 21st. > > > > VulnDev1.c Summary > > ------------------ > > > > -- Summary -- > > > > The VulnDev1.c challenge program was written to encourage people to look > > into the internal workings of heap allocation on various systems. It was > > designed in hopes that readers would research into why an off-by-one in > > the heap is exploitable under some circumstances. > > > > It was specifically written to be exploited on a system implementing the > > Doug Lea Malloc implementation [1]. This includes the Linux and GNU/HURD > > operating systems, and possibly others. As a result, this issue had > > varying results depending on the type of system under which it was > > invoked. Some participants noted a segmentation fault would not occur on > > AIX and Windows systems. This is due to differing allocation algorithms > > and memory management features. *BSD systems are also unaffected by this > > issue as the algorithm used (PHK) does not implement inline memory > > management. Meaning that information used for keeping track and managing > > the status of the heap is not corruptable by overrunning a buffer in the > > heap. > > > > I assume that the reader of this summary is familiar with the internals of > > the Doug Lea algorithm as well has heap-based exploitation methods [2, 3]. > > I will not be delving into the internals of these as they have all been > > well documented. > > > > -- Details -- > > > > VulnDev1.c contained a simple flaw within the for() loop. > > > > for (i = 0; i <= SIZE && i != '\0'; i++) > > buf1[i] = p[i]; > > > > This flaw allowed a user invoking the program to overwrite 1 byte of heap > > memory adjacent to memory allocated for buf1. Due to the Doug Lea > > implementation, this 1 byte of memory corruption can be leveraged to > > execute our own instructions. Two contributors to the discussion > > demonstrated this successfully. > > > > The one key attribute of VulnDev1.c which made exploitation possible was > > the following declaration: > > > > #define SIZE 252 > > > > As some posts indicated, simple modifications of this value would prevent > > a segmentation fault from occurring when SIZE is overrun. This is due to > > the behavior of the malloc() function when allocating buffers of various > > sizes. > > > > As described in Once Upon A free(), each chunk size passed to > > malloc() has a minimum of 4 bytes additional overhead. This is to > > accommodate for the [SIZE] field of the adjacent chunk header. Also, due > > to the 3 least significant bits of each [SIZE] value being used as flags, > > the [SIZE] value of each chunk is padded to the next 8 byte boundary. > > > > The following examples depict this behavior: > > > > malloc(256) [SIZE = 264] > > malloc(15) [SIZE = 24 ] > > malloc(0) [SIZE = 8 ] > > > > And most importantly: > > > > malloc(252) [SIZE = 256] > > > > As shown above, depending on the [SIZE] padding and the subsequent layout > > of the chunk within memory, the last byte of a user-controllable buffer > > may be directly adjacent to the first byte of the next headers [SIZE] > > value. This condition will only occur when the size of an allocated buffer > > + 4 falls on an 8 byte boundary, such as 252, 12, 1020, etc. In > > situations where this does not occur, overwriting 1 byte of memory will > > result in the corruption of a padding byte. However, in situations similar > > to the memory layout caused by VulnDev1.c, overwriting 1 byte of memory > > will allow for the corruption of the LSB of the adjacent [SIZE] field on > > little endian machines. A variety of posts touched on this issue when > > slightly modifying the SIZE variable used by malloc(). > > > > Now that we know that this bug can be used to overwrite a sensitive value > > in memory, the question is whether or not this can be leveraged to execute > > our own instructions. As was shown, this is indeed possible and I will > > explain why. Just as a note, due to the layout of the program, at first > > glance it may appear that exploitation could occur during free(buf2). In > > actuality, exploitation could occur during free(buf1). There are also some > > anomalies with exploitation which I will do my best to address later on. > > > > When buf2 is allocated (buf2 = malloc(SIZE) ) the additonal 4 bytes are > > added to SIZE, resulting in a [SIZE] value of 0x0100 (256). Because buf1 > > has also been allocated, and thus is in use, the PREV_INUSE flag will also > > be set, causing the [SIZE] to be 0x0101. > > > > When the 1 byte of memory corruption occurs the LSB of buf2's [SIZE] will > > be overwritten. For example's sake we will use the value 0xC. This will > > result in buf2's [SIZE] value being 0x010C. This corrupted value is first > > referenced during the call to free(buf1) and this is where exploitation > > takes place. > > > > At some point during execution the free(buf1) call checks whether the > > adjacent forward or backward chunks are free. If so, the chunks will be > > coalesced to avoid contiguous free chunks. The [SIZE] value of buf1's > > header is first checked for the PREV_INUSE flag to see if buf1 and the > > previous chunk should be coalesced. This is followed by a check to see if > > the forward chunk, in our case buf2, is free. To make the check the > > PREV_INUSE flag AFTER buf2 must be tested. This is accomplished by > > referencing the address at *buf1 + ([SIZE] field of buf1) + ([SIZE] field > > of buf2). This third chunk's [SIZE] value is then referenced via this > > location. Under normal circumstances this would place the test at the > > first bytes of data in the chunk following buf2. In the context of > > exploitation of VulnDev1.c however the buf2[SIZE] value has been > > corrupted. This will result in the check for PREV_INUSE flag occuring > > further in the heap, beyond the chunk following buf2. In our case, if > > buf2[SIZE] is 0x010C, then the check will occur at the offset *buf1 + 524. > > In our situation this offset will place us in unused heap memory which has > > been initialized to zero. > > > > This will result in the PREV_INUSE flag appearing unset, making free() > > believe that buf2 is in fact free. Forward consolidation will then occur > > and the unlink() function will be called on buf2. This inturn can be used > > to our advantage by populating the first 8 bytes of buf2 with fake [FD] > > and [BK] pointers, which when referenced by unlink() will be corrupted. > > > > As shown by the two exploits released, this can lead to exploitation by > > overwriting the free GOT entry. Other values which could be overwritten > > include .dtors or a function pointer within free() itself. It should be > > noted that if the second free() is allowed to be called and the corrupted > > [SIZE] is again referenced, varying functionality may occur. > > > > That's all. Overwriting the free GOT entry to point to our own > > instructions somewhere in memory will allow us to execute our own code, > > theoretically with elevated privileges of course. Off-by-one bugs in the > > heap have been found in the wild and I hope the list's discussion and > > summary will help people understand how exploitation works. > > > > -- Additional Discussion -- > > > > When I first wrote the program I considered a scenario, dependent on bytes > > chosen for the 1 byte overwrite, that would result in the program > > exiting cleanly. I also believed that in some situations exploitation > > could occur during the second free(), however I was unable to reproduce > > the situation and have since determined that exploitation during the > > second free() is likely not possible. > > > > Although I was unable to reproduce my hypothesis, Matrix and Marco Ivaldi > > described a situation that was similar to the scenario I had anticipated. > > No discussion really followed their findings so I will do my best to shed > > a little light on the issues. It should be noted that there is some > > behavior that I have not been able to figure out. Any corrections or > > additional information regarding these observations is much appreciated > > and anticipated. > > > > Matrix: > > > > > It's true that the exploit will work on the first free() for any value > > > of the overflow char > 0x9, however I noticed some different things > > > happen for values < 0x9. If the overflow char is 0x1, 0x2, 0x6, 0x7, or > > > 0x9 the program will exit cleanly without a segfault. If the overflow > > > char is 0x4 or 0x5, the first free() will execute find, and the program > > > will segfault on the second free(). I don't know if these cases are > > > exploitable or not. And finally, if the overflow char is 0x8 the program > > > segfaults in the first free() (like when the char is > 0x9) > > > > If the corrupted size value is small enough (0x1, 0x2, 0x6, 0x7) the > > value will be ignored during forward consolidation. This is again due to > > the first 3 bits of the value being used as flags. All 4 of these values > > will consume only the 3 least significant bits of the [SIZE] field. As a > > result, the correct [SIZE] (256) will be used for the forward > > consolidation check. As buf2 will correctly be shown as INUSE, unlink() > > will not be called. When the call to free(buf1) is completed, the > > PREV_INUSE flag of buf2 will appropriately be removed and the [PREV_SIZE] > > will be updated accordingly. As a result, exploitation during these cases > > is not possible. > > > > I have not been able to figure out why 0x4 and 0x5 will trigger a segfault > > during the second free() as I would expect their behavior to mimic those > > values above. Especially since they also only consume the 3 least > > significant bits of buf2 [SIZE]. Any takers? > > > > The first free() segfaults with a value of 0x8 because it affects the 4th > > bit of buf2 [SIZE] thus affecting the forward consolidation check. This > > should put it ahead in heap memory and result in an unset PREV_INUSE flag. > > > > As for 0x9, again I would expect the behavior to mimic that of 0x8. I'm > > not sure why 0x9 does not behave the same way. > > > > Any questions or corrections to the summary, please feel free to post to > > the list as it will benefit everyone. If necessary, I will participate in > > the list discussion. > > > > -- References -- > > > > [1] Doug Lea Malloc Implementation > > http://gee.cs.oswego.edu/dl/html/malloc.html > > > > [2] Once Upon A free() > > http://www.phrack.org/phrack/57/p57-0x09 > > > > [3] Vudo - An object superstitiously believed to embody magical powers > > http://www.phrack.org/phrack/57/p57-0x08 > > > > EOF > > > > Aaron Adams > -- > Jason Royes > Data Access Experts > >
This archive was generated by hypermail 2b30 : Wed May 21 2003 - 10:34:23 PDT