First Fit

First Fit

Quando você libera memória em um programa usando glibc, diferentes "bins" são usados para gerenciar os blocos de memória. Aqui está uma explicação simplificada de dois cenários comuns: bins não ordenados e fastbins.

Bins Não Ordenados

Quando você libera um bloco de memória que não é um bloco rápido, ele vai para o bin não ordenado. Este bin atua como uma lista onde novos blocos liberados são adicionados à frente (a "cabeça"). Quando você solicita um novo bloco de memória, o alocador olha para o bin não ordenado de trás para frente (a "cauda") para encontrar um bloco que seja grande o suficiente. Se um bloco do bin não ordenado for maior do que o que você precisa, ele é dividido, com a parte da frente sendo retornada e a parte restante permanecendo no bin.

Exemplo:

• Você aloca 300 bytes (a), depois 250 bytes (b), então libera a e solicita novamente 250 bytes (c).
• Quando você libera a, ele vai para o bin não ordenado.
• Se você então solicitar 250 bytes novamente, o alocador encontra a na cauda e o divide, retornando a parte que atende ao seu pedido e mantendo o restante no bin.
• c apontará para o anterior a e será preenchido com o conteúdo de a.

char *a = malloc(300);
char *b = malloc(250);
free(a);
char *c = malloc(250);

Fastbins

Fastbins são usados para pequenos pedaços de memória. Ao contrário dos bins não ordenados, fastbins adicionam novos pedaços ao início, criando um comportamento de último a entrar, primeiro a sair (LIFO). Se você solicitar um pequeno pedaço de memória, o alocador irá retirar do início do fastbin.

Exemplo:

char *a = malloc(20);
char *b = malloc(20);
char *c = malloc(20);
char *d = malloc(20);
free(a);
free(b);
free(c);
free(d);
a = malloc(20);   // d
b = malloc(20);   // c
c = malloc(20);   // b
d = malloc(20);   // a

🔥 Considerações modernas do glibc (tcache ≥ 2.26)

Desde o glibc 2.26, cada thread mantém seu próprio tcache que é consultado antes do bin não ordenado. Portanto, um cenário de first-fit só será alcançado se:

1. O tamanho solicitado é maior que tcache_max (0x420 em 64 bits por padrão), ou
2. O bin correspondente do tcache está já cheio ou esvaziado manualmente (alocando 7 elementos e mantendo-os em uso).

Em exploits reais, você geralmente adicionará uma rotina auxiliar como:

// Drain the tcache for a given size
for(int i = 0; i < 7; i++) pool[i] = malloc(0x100);
for(int i = 0; i < 7; i++) free(pool[i]);

Uma vez que o tcache está esgotado, liberações subsequentes vão para o bin não ordenado e o comportamento clássico de first-fit (busca na cauda, inserção na cabeça) pode ser acionado novamente.

🚩 Criando um UAF de chunk sobreposto com first-fit

O fragmento abaixo (testado no glibc 2.38) mostra como o divisor no bin não ordenado pode ser abusado para criar 2 ponteiros sobrepostos – um primitivo poderoso que converte uma única liberação em uma escrita após a liberação.

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

int main(){
setbuf(stdout, NULL);

/* 1. prepare 2 adjacent chunks and free the first one */
char *A = malloc(0x420);   // big enough to bypass tcache
char *B = malloc(0x420);
strcpy(A, "AAAA\n");
free(A);                   // A → unsorted

/* 2. request a *smaller* size to force a split of A */
char *C = malloc(0x400);   // returns lower half of former A

/* 3. The remainder of A is still in the unsorted bin.
Another 0x400-byte malloc will now return the *same*
region pointed to by B – creating a UAF/overlap. */
char *C2 = malloc(0x400);

printf("B  = %p\nC2 = %p (overlaps B)\n", B, C2);

// Arbitrary write in B is immediately visible via C2
memset(B, 'X', 0x10);
fwrite(C2, 1, 0x10, stdout);  // prints Xs
}

Receita de exploração (comum em CTFs recentes):

1. Drenar o tcache para o tamanho alvo.
2. Liberar um chunk para que ele caia no bin não ordenado.
3. Alocar um tamanho ligeiramente menor – o alocador divide o chunk não ordenado.
4. Alocar novamente – a parte restante se sobrepõe a um chunk existente em uso → UAF.
5. Sobrescrever campos sensíveis (ponteiros de função, vtable de FILE, etc.)

Uma aplicação prática pode ser encontrada no desafio Setjmp das Quals HITCON 2024, onde este exato primitivo é usado para pivotar de um UAF para controle total de __free_hook.{{#ref}} ../../../../references/2024_setjmp_firstfit.md {{#endref}}

🛡️ Mitigações & Fortalecimento

• Safe-linking (glibc ≥ 2.32) protege apenas as listas tcache/fastbin ligadas singularmente. Os bins não ordenados/pequenos/grandes ainda armazenam ponteiros brutos, então sobreposições baseadas em first-fit permanecem viáveis se você conseguir obter um leak de heap.
• Criptografia de ponteiro de heap & MTE (ARM64) ainda não afetam glibc x86-64, mas flags de endurecimento de distribuições como GLIBC_TUNABLES=glibc.malloc.check=3 abortarão em metadados inconsistentes e podem quebrar PoCs ingênuas.
• Preenchendo tcache ao liberar (proposto em 2024 para glibc 2.41) reduziria ainda mais o uso não ordenado; monitore lançamentos futuros ao desenvolver exploits genéricos.

Outras Referências & Exemplos

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Use after free: Gere um objeto de usuário, libere-o, gere um objeto que obtenha o chunk liberado e permita escrever nele, sobrescrevendo a posição de user->password do anterior. Reutilize o usuário para burlar a verificação de senha
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• O programa permite criar notas. Uma nota terá as informações da nota em um malloc(8) (com um ponteiro para uma função que pode ser chamada) e um ponteiro para outro malloc() com o conteúdo da nota.
• O ataque seria criar 2 notas (note0 e note1) com conteúdos malloc maiores do que o tamanho das informações da nota e, em seguida, liberá-las para que entrem no fast bin (ou tcache).
• Em seguida, crie outra nota (note2) com tamanho de conteúdo 8. O conteúdo vai estar na note1, pois o chunk será reutilizado, onde poderíamos modificar o ponteiro de função para apontar para a função win e então Use-After-Free a note1 para chamar o novo ponteiro de função.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• É possível alocar alguma memória, escrever o valor desejado, liberá-la, realocá-la e, como os dados anteriores ainda estão lá, serão tratados de acordo com a nova estrutura esperada no chunk, tornando possível definir o valor para obter a flag.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• Neste caso, é necessário escrever 4 dentro de um chunk específico que é o primeiro a ser alocado (mesmo após forçar a liberação de todos eles). Em cada novo chunk alocado, seu número no índice do array é armazenado. Então, aloque 4 chunks (+ o inicialmente alocado), o último terá 4 dentro dele, libere-os e force a realocação do primeiro, que usará o último chunk liberado, que é o que tem 4 dentro dele.
• 2024 HITCON Quals Setjmp write-up (Quarkslab) – ataque prático de sobreposição first-fit / unsorted-split: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify write-up – abusando da divisão de bin não ordenado para vazar libc e ganhar sobreposição: https://hackmd.io/@aneii11/H1S2snV40