First-Fit Allocation

Understanding glibc malloc first-fit strategy and exploitation implications

Overview

The first-fit algorithm is the core allocation strategy used by glibc malloc when selecting a free chunk to satisfy a memory request. When malloc needs to allocate memory, it searches through the appropriate bin and returns the first chunk that is large enough, rather than searching for the best-fitting chunk.

This seemingly simple design decision has significant implications for heap exploitation, particularly in use-after-free scenarios.

How First-Fit Works

When you call malloc(size), the allocator:

1. Calculates required size

   Converts the requested size to the actual chunk size needed (including metadata and alignment).

2. Searches for a free chunk

   Looks through the appropriate bin (tcache, fastbin, smallbin, etc.) for a free chunk.

3. Returns first match

   Returns the first chunk that is large enough, even if a better-fitting chunk exists later in the list.

4. Splits if necessary

   If the chunk is significantly larger than needed, it may be split, with the remainder returned to the free list.

First-fit prioritizes speed over optimal memory usage. It avoids traversing the entire free list to find the best match.

Demonstration Program

The following program demonstrates first-fit allocation behavior:

first_fit.c

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

int main()
{
	fprintf(stderr, "This file doesn't demonstrate an attack, but shows the nature of glibc's allocator.\n");
	fprintf(stderr, "glibc uses a first-fit algorithm to select a free chunk.\n");
	fprintf(stderr, "If a chunk is free and large enough, malloc will select this chunk.\n");
	fprintf(stderr, "This can be exploited in a use-after-free situation.\n");

	fprintf(stderr, "Allocating 2 buffers. They can be large, don't have to be fastbin.\n");
	char* a = malloc(0x512);
	char* b = malloc(0x256);
	char* c;

	fprintf(stderr, "1st malloc(0x512): %p\n", a);
	fprintf(stderr, "2nd malloc(0x256): %p\n", b);
	fprintf(stderr, "we could continue mallocing here...\n");
	fprintf(stderr, "now let's put a string at a that we can read later \"this is A!\"\n");
	strcpy(a, "this is A!");
	fprintf(stderr, "first allocation %p points to %s\n", a, a);

	fprintf(stderr, "Freeing the first one...\n");
	free(a);

	fprintf(stderr, "We don't need to free anything again. As long as we allocate smaller than 0x512, it will end up at %p\n", a);

	fprintf(stderr, "So, let's allocate 0x500 bytes\n");
	c = malloc(0x500);
	fprintf(stderr, "3rd malloc(0x500): %p\n", c);
	fprintf(stderr, "And put a different string here, \"this is C!\"\n");
	strcpy(c, "this is C!");
	fprintf(stderr, "3rd allocation %p points to %s\n", c, c);
	fprintf(stderr, "first allocation %p points to %s\n", a, a);
	fprintf(stderr, "If we reuse the first allocation, it now holds the data from the third allocation.\n");
}

Running the Program

Compile and run

gcc first_fit.c -o first_fit
./first_fit

Key Observations

Let’s break down what happens in this program:

1. Initial allocations

   char* a = malloc(0x512);  // Gets address 0x555555559260
   char* b = malloc(0x256);  // Gets address 0x555555559780
   strcpy(a, "this is A!");
   

   Two chunks are allocated. Pointer a contains “this is A!”.

2. Free first chunk

   free(a);  // Returns chunk to free list
   

   The 0x512-byte chunk is freed and added to the appropriate bin (likely unsorted bin or tcache).

3. Allocate smaller chunk

   c = malloc(0x500);  // Gets address 0x555555559260
   strcpy(c, "this is C!");
   

   Because 0x500 < 0x512, the freed chunk at a’s address is large enough. First-fit returns this chunk immediately.

4. Use-after-free

   fprintf(stderr, "first allocation %p points to %s\n", a, a);
   // Prints: first allocation 0x555555559260 points to this is C!
   

   Now a and c point to the same memory. Reading from a shows data written via c.

Critical Security Implication: The old pointer a still points to valid memory, but that memory now belongs to a new allocation c. This is a use-after-free vulnerability.

Exploitation Implications

First-fit allocation makes certain heap exploits more reliable:

Use-After-Free (UAF)

Example UAF scenario

struct User {
    char name[64];
    void (*print)(struct User*);
};

// Allocate and free a User object
struct User* user = malloc(sizeof(struct User));
user->print = print_user;
free(user);

// Attacker can allocate same-sized chunk
char* attacker_data = malloc(sizeof(struct User));
strcpy(attacker_data, "\x90\x90...\x41\x41\x41\x41...");

// Now user->print points to attacker-controlled data!
user->print(user);  // Can hijack control flow

Heap Spray

First-fit makes heap spraying more predictable:

1. Allocate many objects

   Fill the heap with objects containing exploit payloads.

2. Trigger vulnerability

   Cause a UAF or similar bug that allocates memory.

3. Exploit

   Because of first-fit, the vulnerability is likely to reuse one of your controlled chunks.

Heap Feng Shui

Exploiters can manipulate heap layout by:

1. Allocating chunks in specific order
2. Freeing strategic chunks to create controlled free list
3. Triggering vulnerability that allocates from manipulated free list
4. Achieving predictable memory reuse due to first-fit

First-fit makes the heap state more deterministic, which actually helps attackers create reliable exploits.

Why Not Best-Fit?

You might wonder why glibc doesn’t use a best-fit algorithm (find the smallest chunk that fits). The answer is performance:

First-Fit

• Fast: O(1) to O(n) with early exit
• Returns first match found
• Less memory traversal
• Good locality

Best-Fit

• Slow: O(n) always
• Must check all chunks
• More memory traversal
• Better memory efficiency

For most applications, the performance gain from first-fit outweighs the slight memory fragmentation cost.

Defense Considerations

To protect against first-fit-based exploits:

1. Avoid use-after-free

   Null out pointers after freeing them, and implement proper lifetime management.

2. Use memory safety tools

   AddressSanitizer can detect UAF bugs during development.

3. Consider safe languages

   Languages with automatic memory management eliminate entire classes of heap exploits.

4. Enable hardening features

   Use allocators with additional security checks (e.g., safe linking in modern glibc).

Practical Exercise

Try this experiment with the program:

1. Modify the allocation size

   Change malloc(0x500) to malloc(0x520) (larger than the freed chunk).

2. Observe the result

   The new allocation will get a different address because it doesn’t fit.

3. Try with tcache

   Allocate/free 7 same-sized chunks to fill tcache, then observe first-fit behavior.

Related Techniques

Tcache Poisoning

Exploit tcache’s LIFO structure with first-fit

Fastbin Dup

Double-free with first-fit allocation

House of Spirit

Create fake chunks that first-fit will allocate

Heap Basics

Review malloc fundamentals

Summary

First-fit allocation is:

• Fast: Returns the first suitable chunk without exhaustive search
• Predictable: Same allocation patterns produce consistent results
• Exploitable: Enables reliable use-after-free and heap grooming attacks
• Fundamental: Understanding this is essential for heap exploitation