Heap Corruption

,-----------------------------------------------------------------.

| Heap Corruption / A Short Description and Step-by-Step Tutorial |
|         Costantino Pistagna - pistagna@dmi.unict.it             |

'-----------------------------------------------------------------'

Abstract



Cosa e` lo Heap?
La memoria allocata dal processo in fase di runtime -esecuzione-, fa' parte
della struttura che comunemente va' sotto il nome di Heap. Con il termine Heap,
quindi, si intende qualunque forma e porzione di memoria che viene creata
dinamicamente durante l'esecuzione del nostro processo. Un array di caratteri,
allocato dinamicamente attraverso una chiamata malloc/calloc fara' parte dello
heap. In generale qualunque assegnazione dinamica di memoria contigua fara'
parte dello heap. Viceversa, quando la porzione di memoria non e' piu' utile,
viene chiamata una funzione antitetica alla malloc: free().



In qualunque circostanza, comunque, la gestione dello Heap e' un compito
altamente complesso. L'obiettivo di allocazione ottimale ed efficente della
memoria, infatti, e' un problema NP-Completo; questo significa, che qualunque
approccio utilizzato, non ha soluzione polinomiale adeguata. Ci limiteremo,
quindi, a lavorare con algoritmi che fanno il loro lavoro "ragionevol
mente" bene ed in un "ragionevole" intervallo di tempo. Si puo' vedere
il problema come la ricerca del giusto compromesso: se si ottimizza la gestione
della memoria senza sprechi, si paga un pegno in termini di tempo e risorse
della CPU; viceversa se non si ottimizza adeguatamente la memoria, si avranno
delle chiamate di funzione - malloc,free, etc. - molto piu' veloci, ma una
gestione della memoria disponibile molto frammentata.

.         .                      .         .
.         .                      .         .
.---------.                      .---------.
|allocated|                      | free    |
+---------+                      +---------+
|allocated|                      |allocated|
+---------+                      +---------+
|allocated+                      | free    |
+---------+                      +---------+
|allocated+                      | free    |
+---------+                      +---------+
|allocated+                      |allocated|
+---------+                      +---------+
.         .                      |allocated|
.         .                      +---------+
.         .                      .         .
.         .                      .         .

Quando una porzione di memoria viene allocata, non puo' essere ri/mossa sino a
quando l'utente non la libera. Se viene liberata della memoria ad indirizzi
inferiori o superiori, si crea quello che si chiama un "buco" nella memoria
allocata. Il blocco di memoria libero cosi' creato viene, tipicamente, aggiunto
in una lista doppiamente linkata per successive riallocazioni. Come gia'
accennato, una buona gestione dello heap dovrebbe allocare la memoria in
maniera contigua senza lasciare spazi inutilizzati; questo implica delle
politiche di gestione dello spazio non indifferenti, che comunque portano via
del tempo. Gli heap manager piu' efficenti riescono ad effettuare allocazioni
di spazio in tempi non superiori a O(lgn), il che non e' male. Un buon rapporto
prezzo/prestazioni, insomma, e' l'unica soluzione verosimilmente attuabile.


Lo spazio di indirizzamento dei processi
Lo spazio di indirizzamento di un processo consiste di tutti gli indirizzi
logici che puo' utilizzare. Ogni processo ha un suo spazio di indirizzamento
privato ma puo' condividerlo, attraverso tecniche di memory sharing, con altri
processi. Un processo puo' acquisire nuova memoria dinamica per il suo heap
attraverso chiamate di sistema dedicate: malloc, calloc, brk. I campi start_brk
e brk indicano, rispettivamente, il punto di inizio ed il punto di fine
dell'attuale zona di heap. Attraverso le funzioni sopra citate e' possibile,
tuttavia, modificare a proprio piacimento le dimensione dello heap. brk(2) e'
la radice di tutte le altre funzioni e si occupa della crescita dinamica del
data segment o heap.


Gli Overflow di Heap: Heap Corruption Attack
Gli overflow di heap possono essere divisi in due classi:
Una classe comprende gli attacchi dove l'overflow di un buffer allocato sullo
heap altera direttamente il contenuto di una zona di memoria adiacente.
L'altra classe comprende exploits che alterano le informazioni di gestione
utilizzate dal memory manager (malloc, free, etc.). La maggior parte delle
implementazioni di *alloc condividono il comportamento nel conservare le
informazioni di gestione all'interno dello stesso heap. Questo comportamento
diventa un possibile punto d'attacco per un attaccante che intende modificare
o corrompere le informazioni presenti sullo heap.

L'idea centrale dell'attacco e' quella di modificare le informazioni di
gestione, in un modo che permettera' sovrascritture arbitrarie successive.
Cosi' facendo gli indirizzi di ritorno, tabelle di link o data level possono
essere alterati in maniera casuale dall'attaccante. Quale esempio chiaritore,
si immagini un contesto in cui le zone di memoria heap vengono conservate
attraverso delle strutture dati liste doppiamente linkate. Se un attaccante e'
in grado di modificare le zone di heap adiacenti a quella in cui gli e'
permesso scrivere -attacco del primo tipo-, con un po' piu' di esperienza sara'
in grado di modificare i puntatori del proprio spazio di memoria in maniera da
puntare a zone diverse da quelle originali. In questo modo e' possibile
modificare i puntatori interpellati in fase di liberamento e nuova allocazione
della memoria, creando una corruzione dello heap. Si vedano a tal proposito gli
esempi forniti.

Al di la' di tecniche esoteriche, comunque, il problema della malformazione
dello heap puo' dare vita a fenomeni e situazioni inaspettate: -bugs-. A titolo
di esempio, si immagini un elementare programma che conservi in memoria
strutture dati complesse, contenenti informazioni circa utenti e loro credito
bancario:


typedef struct cliente {
char nome[20];
char cognome[20];
int credito;
int debito;
struct cliente *next, *prev;
}


L'utente che ha accesso in scrittura alle zone di memoria dinamica contenenti
le strutture di cui sopra,puo' sferrare attacchi multipli di tipo HC al sistema
Se non viene fatto nessun controllo sulla stringa nome e cognome, sara' facile
scavalcarle per poter avere accesso libero alle note di credito e debito. Il
seguente codice, anche se concettualmente giusto, apre una breccia di sicurezza all'interno del nostro sistema:

int main(int argc, char **argv) {
cliente *ptr;
ptr = (cliente *)calloc(1,sizeof(cliente));

strcpy(ptr->cognome, argv[2]);
ptr->credito=atoi(argv[3]);
ptr->debito=atoi(argv[4]);
strcpy(ptr->nome, argv[1]);

printf("Vs. Credito: %d\nVs. Debito: %d\n", ptr->credito, ptr->debito);
return 0;
}

cagliostro$./heap4 Marco Moretti 0 4
Vs. Credito: 0
Vs. Debito: 4
cagliostro$



Cosa succede se forziamo il buffer NOME ?

cagliostro$./heap4 MarcoPINOPENASENZAPANEMENTREPINAPANEPONENEL Moretti 0 4
Vs. Credito: 1313164288
Vs. Debito: 4
cagliostro$



Eccoci servito un credito a nostro favore di: 1.313.164.288Euro!

Ma il nostro attaccante puo' anche giocare piu' astutamente e modificare allo
stesso modo i puntatori *next e *prev, fornendo locazioni con utenze di comodo
che si e' precedentemente creato senza corrompere direttamente i campi. Visto
che la memoria in un sistema viene mantenuta attraverso liste linkate (in
verita' non e' proprio cosi, ma l'astrazione rende per il target del nostro
trattato)un attaccante potra' alterare i puntatori a zone di memoria in maniera
da ottenere un effetto di invalida e corruzione dello heap da sfruttare a
proprio favore.


Forziamo le regole - Alcuni Esempi Pratici
Se un utente malizioso e' in grado di mettere in overflow un blocco di memoria
allocato dinamicamente,potra' sovrascrivere la prossima intestazione di memoria
contigua.Quando il chunk messo in overflow viene disallocato, ad esempio in una
lista doppiamente linkata, l'attaccante puo' controllare i valori next e prev
di questo chunk.

Un file eseguibile come ELF, ha alcune sezioni al suo interno:

- PLT (Procedure Linking Table)
- GOT (Global Offset Table)
- init (instructions executed on init)
- fini (instructions executed upon termination)
- ctors (global constructors)
- dtors (global destructors)

La memoria allocata al processo e' conosciuta, ovviamente, come HEAP.La sezione
BSS contiene dati non inizializzati, e viene allocata a run-time. Finche' non
viene scritto su di essa, rimane a zero. Quando parliamo di heap-based overflow
ci riferiamo contemporaneamente a overflows di buffers basati su heap/data/bss.


valvoline$ cat heap1.c

#include
#include
#include
#include

#define BUFSIZE 16
#define OVERSIZE 8 /* overflow buf2 by OVERSIZE bytes */

int main() {
u_long diff;
char *buf1 = (char *)malloc(BUFSIZE), *buf2 = (char *)malloc(BUFSIZE);

diff = (u_long)buf2 - (u_long)buf1;
printf("buf1 = %p, buf2 = %p, diff = 0x%x bytes\n", buf1, buf2, diff);
memset(buf2, 'A', BUFSIZE-1);
buf2[BUFSIZE-1] = '\0';
printf("before overflow: buf2 = %s\n", buf2);
memset(buf1, 'B', (u_int)(diff + OVERSIZE));
printf("after overflow: buf2 = %s\n", buf2);
return 0;
}

valvoline$ ./heap1
buf1 = 0x300140, buf2 = 0x300150, diff = 0x10 bytes
before overflow: buf2 = AAAAAAAAAAAAAAA
after overflow: buf2 = BBBBBBBBAAAAAAA
valvoline$

Il codice funziona perche buf1 va' oltre i suoi limiti e sconfina nello spazio
di heap di buf2. Semplice! Poiche' lo spazio di heap di buf2 e' ancora valido
(qualcuno ha allocato dello spazio in memoria ed e' possibile scrivere/leggere)
il programma continuera' a funzionare senza segnalarci errori o crash.


valvoline$ cat heap2.c

#include
#include
#include
#include
#include

#define BUFSIZE 16
#define ADDRLEN 4 /* # of bytes in an address */

int main() {
u_long diff;
static char buf[BUFSIZE], *bufptr;

bufptr = buf, diff = (u_long)&bufptr - (u_long)buf;
printf("bufptr (%p) = %p, buf = %p, diff = 0x%x (%d) bytes\n",
&bufptr, bufptr, buf, diff, diff);
memset(buf, 'A', (u_int)(diff + ADDRLEN));
printf("bufptr (%p) = %p, buf = %p, diff = 0x%x (%d) bytes\n",
&bufptr, bufptr, buf, diff, diff);
return 0;
}

valvoline$ ./heap2
bufptr (0x3090) = 0x3080, buf = 0x3080, diff = 0x10 (16) bytes
bufptr (0x3090) = 0x41414141, buf = 0x3080, diff = 0x10 (16) bytes

valvoline$


Il nuovo codice si appoggia ad un attacco di tipo bss/heap-based overflow.
In questo caso sovrascriviamo il puntatore ptrbuf, alterando teoricamente il
flusso originale del codice.