First Fit

This technique describes the 'first-fit' behavior of glibc's allocator. Whenever any chunk (not a fast chunk) is freed, it ends up in the unsorted bin. Insertion happens at the HEAD of the list. On requesting new chunks (again, non fast chunks), initially unsorted bins will be looked up as small bins will be empty. This lookup is from the TAIL end of the list. If a single chunk is present in the unsorted bin, an exact check is not made and if the chunk's size >= the one requested, it is split into two and returned. This ensures first in first out behavior.
Consider the sample code:
1
char *a = malloc(300);    // 0x***010
2
char *b = malloc(250);    // 0x***150
3
​
4
free(a);
5
​
6
a = malloc(250);          // 0x***010
Copied!
The state of unsorted bin progresses as:
1.'a' freed.
head -> a -> tail
2.'malloc' request.
head -> a2 -> tail [ 'a1' is returned ]
'a' chunk is split into two chunks 'a1' and 'a2' as the requested size (250 bytes) is smaller than the size of the chunk 'a' (300 bytes). This corresponds to [6. iii.] in _int_malloc.
This is also true in the case of fast chunks. Instead of 'freeing' into unsorted bin, fast chunks end up in fastbins. As mentioned earlier, fastbins maintain a singly linked list and chunks are inserted and deleted from the HEAD end. This 'reverses' the order of chunks obtained.
Consider the sample code:
1
char *a = malloc(20);     // 0xe4b010
2
char *b = malloc(20);     // 0xe4b030
3
char *c = malloc(20);     // 0xe4b050
4
char *d = malloc(20);     // 0xe4b070
5
​
6
free(a);
7
free(b);
8
free(c);
9
free(d);
10
​
11
a = malloc(20);           // 0xe4b070
12
b = malloc(20);           // 0xe4b050
13
c = malloc(20);           // 0xe4b030
14
d = malloc(20);           // 0xe4b010
Copied!
The state of the particular fastbin progresses as:
1.'a' freed.
head -> a -> tail
2.'b' freed.
head -> b -> a -> tail
3.'c' freed.
head -> c -> b -> a -> tail
4.'d' freed.
head -> d -> c -> b -> a -> tail
5.'malloc' request.
head -> c -> b -> a -> tail [ 'd' is returned ]
6.'malloc' request.
head -> b -> a -> tail [ 'c' is returned ]
7.'malloc' request.
head -> a -> tail [ 'b' is returned ]
8.'malloc' request.
head -> tail [ 'a' is returned ]
The smaller size here (20 bytes) ensured that on freeing, chunks went into fastbins instead of the unsorted bin.
Use after Free Vulnerability
In the above examples, we see that, malloc might return chunks that were earlier used and freed. This makes using freed memory chunks vulnerable. Once a chunk has been freed, it should be assumed that the attacker can now control the data inside the chunk. That particular chunk should never be used again. Instead, always allocate a new chunk.
See sample piece of vulnerable code:
1
char *ch = malloc(20);
2
​
3
// Some operations
4
//  ..
5
//  ..
6
​
7
free(ch);
8
​
9
// Some operations
10
//  ..
11
//  ..
12
​
13
// Attacker can control 'ch'
14
// This is vulnerable code
15
// Freed variables should not be used again
16
if (*ch=='a') {
17
  // do this
18
}
Copied!

Heap Exploitation

Double Free

Last modified 1yr ago

Copy link

Contents

Use after Free Vulnerability