Ubuntu 16.04 - malloc implementation. Where is the pointer to the next chunk?

Question

I am trying to understand how the malloc implementation in glibc is working. According to the source code of malloc (malloc.c in glibc 2.23) free memory chunks have the following structure.

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk                            |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                         |P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Forward pointer to next chunk in list             |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |                 Back pointer to previous chunk in list        |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Unused space (may be 0 bytes long)                .
            .                                                               .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Normally we should be able to see this structure in the gnu debugger (gdb) as well. So I wrote the following program. The program allocates 6 memory chunks with the size of 64 Byte. Each chunk is filled with memset, so we can easy see the according chunk in gdb later. Because chunks 1,3 and 6 are freed they should have the above mentioned structure. Since there are allocated chunks in between, the freed chunks can not consolidated and as a result they are organized in a doubled linked list trough the pointers in each chunk.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void to_jump();

int main(int argc, char **argv){
    char *b1, *b2, *b3, *b4, *b5, *b6;

    //allocate 6 chunks of memory
    b1 = malloc(64);
    b2 = malloc(64);
    b3 = malloc(64);
    b4 = malloc(64);
    b5 = malloc(64);
    b6 = malloc(64);

    memset(b1, 'B', 64);
    memset(b2, 'C', 64);
    memset(b3, 'D', 64);
    memset(b5, 'E', 64);
    memset(b6, 'F', 64);
    //free chunks 1,3 and 6
    free(b1);
    free(b3);
    free(b6);

    strcpy(b4, argv[1]);   // <-- set breakpoint here
    //exploit this line
    free(b4);
    free(b5);
    free(b2);
}

void to_jump(){
    printf("Exploited");
}

When I start the program within gdb and set a breakpoint in line strcpy(b4, argv[1]); we should be able to see that the freed chunks are organized in a double linked list. However the gdb output is as follows:

gdb-peda$ p b1
$11 = 0x602010 ""
gdb-peda$ x/62xg 0x602000
0x602000:   0x0000000000000000  0x0000000000000051  
0x602010:   0x0000000000000000  0x4242424242424242   |
0x602020:   0x4242424242424242  0x4242424242424242   | b1 (freed)
0x602030:   0x4242424242424242  0x4242424242424242   |
0x602040:   0x4242424242424242  0x4242424242424242   |
0x602050:   0x0000000000000000  0x0000000000000051
0x602060:   0x4343434343434343  0x4343434343434343   |
0x602070:   0x4343434343434343  0x4343434343434343   | b2 (allocated)
0x602080:   0x4343434343434343  0x4343434343434343   |
0x602090:   0x4343434343434343  0x4343434343434343   |
0x6020a0:   0x0000000000000000  0x0000000000000051
0x6020b0:   0x0000000000602000  0x4444444444444444   | 0x602000 is pointing to b1 (previous freed block)
0x6020c0:   0x4444444444444444  0x4444444444444444   | b3 (freed)
0x6020d0:   0x4444444444444444  0x4444444444444444   | 
0x6020e0:   0x4444444444444444  0x4444444444444444   |
0x6020f0:   0x0000000000000000  0x0000000000000051
0x602100:   0x0000000000000000  0x0000000000000000   |
0x602110:   0x0000000000000000  0x0000000000000000   | b4 (will be filled trough strcpy(b4, argv[1]);
0x602120:   0x0000000000000000  0x0000000000000000   |
0x602130:   0x0000000000000000  0x0000000000000000   |
0x602140:   0x0000000000000000  0x0000000000000051
0x602150:   0x4545454545454545  0x4545454545454545   |
0x602160:   0x4545454545454545  0x4545454545454545   | b5 (allocated)
0x602170:   0x4545454545454545  0x4545454545454545   |
0x602180:   0x4545454545454545  0x4545454545454545   |
0x602190:   0x0000000000000000  0x0000000000000051
0x6021a0:   0x00000000006020a0  0x4646464646464646   | 0x6020a0 is pointing to b3 (previous freed block)
0x6021b0:   0x4646464646464646  0x4646464646464646   | b6 (freed)
0x6021c0:   0x4646464646464646  0x4646464646464646   |
0x6021d0:   0x4646464646464646  0x4646464646464646   |
0x6021e0:   0x0000000000000000  0x0000000000020e21

In this output we can see the freed chunks and the back pointer to the previous freed chunk (See the comments on the right side from the output). But where are the forward pointers and the size of previous chunk?

Answer 1

Cross-posted from security.stackexchange

Depending upon the size of the chunk to be freed, chunks are held in different types of bins (linked lists):

• Unsorted bins
• Small bins
• Large bins

You are suggested to look up the source code if you are interested in knowing how these bins are maintained. But something common among all these bins is that the lists are doubly-linked. So you were correct in your assumption that you should have found both a forward and a backward pointer in the freed chunks (and also perhaps the previous size field)

However, there is another type of special bin known as a fastbin. Chunks of a very small size (usually between 16 and 80 bytes, but it may slightly vary across versions) are kept in these fastbins. Unlike your regular bins, these are singly-linked. They are kept in an appropriate fastbin based on their size (each bin containing chunks of the same size). Instead of having to traverse the list, chunks can be added and removed in a LIFO order, speeding up the performance. Also unlike regular chunks, adjacent fastbin-chunks are not consolidated (which of course results into fragmentation, but makes free faster). This also means that you don't need the size of the previous chunk either.

The chunks in your program are also probably a part of one of these fastbins. Therefore to see what you are expecting, try allocating and freeing memory of a larger size.