Prevedere il Buffer Overrun
usando Programmazione Lineare
e Analisi Statica
Buffer Overrun Detection
using Linear Programming
and Static Analysis
Analisi e Verifica di Programmi
Alberto De Lazzari - Fabio Pustetto
Introduzione

Scrivere oltre i limiti di un buffer in memoria
– C permette la manipolazione diretta dei puntatori senza alcun tipo di
controllo sui limiti
– Dati validi possono essere sovrascritti
– Hacker sfruttano per eseguire codice malvagio



Caricato in memoria come valido
acquisizione dei privilegi di root
Gli approcci per rilevare il buffer overrun possono essere di tipo
– Statico

esamina il codice sorgente per eliminare questo tipo di bug prima che il codice sia
distribuito
– Dinamico




previene gli “attacchi” basati sul bug
perciò non sono eliminati come nell’analisi statica
generalmente causano il crash dell’applicazione quando è rilevato un attacco
Controlli ridondanti portano ad overhead
Linee Guida:
La definizione e l’implementazione del tool che permette
l’analisi statica del codice, si divide nei seguenti punti:




Uso di analisi statica per modellare stringhe di codice C sorgente
come programma lineare
Definizione e implementazione di risolutori veloci e scalabili basati su
tecniche innovative della programmazione lineare. La soluzione al
programma lineare determina i limiti del buffer
Tecniche per rendere l’analisi del programma sensibile al contesto
Efficacia di altre tecniche di analisi come il partizionamento statico
per eliminare bug dal codice sorgente
-> tool deve essere scalabile
Tecniche dinamiche:
approfondimento

Proteggere l’indirizzo di ritorno sullo stack
– controllo d’integrità sui record evitando la modifica dell’indirizzo di
ritorno
– si può rilevare e prevenire un attacco di tipo stack smashing

Corrompere lo stack scrivendo oltre la sua fine, permettendo di cambiare
l’indirizzo di ritorno di una funzione
– Altre tecniche generalizzano il concetto precedente estendendolo a puntatori,
variabili locali e argomenti di funzioni

Proteggere tutti gli accessi ai puntatori
–
–
–
–
cifrandoli quando sono memorizzati
decifrandoli quando sono caricati nei registri della CPU
non evita la possibilità di distruggere il puntatore
impedisce di ottenere un valore di puntatore prevedibile in memoria

non si conosce la chiave di decifratura
Tecniche statiche:
approfondimento

suddivise in tre classi
1. tool guidati da annotazioni

utilizza annotazioni date dall’utente
– Es: pre/post-condizioni di una funzione
2. tool che usano l’analisi simbolica
3. tool che estraggono un modello dal
codice sorgente e lo utilizzano per
rilevare la presenza di bug
1. tool guidati da
annotazioni



CSSV converte un programma in C in un
programma intero, con asserzioni di correttezza
incluse e usa un algoritmo di analisi statica
conservativa per trovare manipolazioni erronee sugli
interi che direttamente si traducono in bug sul
codice C.
L’analisi è fatta sulla base di annotazioni (chiamate
contract) che sono usate per rendere l’analisi
interprocedurale
Split è simile a CSSV anche se usa un’analisi flowsensitive e pre/post-condizioni fornite dall’utente.
2. tool che usano l’analisi
simbolica

Alcuni tool (Archer, ARray CHeckER) eseguono il codice
in maniera
– Simbolica

permette di analizzare il codice senza conoscere l’esatto valore delle
variabili che si stanno manipolando
– Interprocedurale

permette di trattare una stessa variabile che si trova in metodi
diversi
– mantenendo l’informazione riguardo alle variabili in un database
man mano che l’esecuzione procede


l’esecuzione di statement può portare alla modifica dello stato del
programma
quando in uno statement si accede ad un buffer, Archer controlla,
attraverso il database, se l’accesso avviene nel rispetto dei limiti del
buffer
3. tool che estraggono un modello
dal codice sorgente e lo utilizzano
per rilevare la presenza di bug



Si estrae un modello dal codice sorgente
Si modellano le stringhe come tipi di dato
astratto e si trasforma il rilevamento del
buffer overrun in un problema di analisi sul
range di valori interi
Il tool presentato in questo paper rientra in
questa classe di tecniche introducendo
un’analisi dei puntatori più precisa
Architettura complessiva

plug-in per CodeSurfer
– tool utilizzato per la comprensione del codice
– costruisce una rappresentazione totale del programma
attraverso





grafo delle dipendenze di sistema composto dai grafi di
dipendenza di ciascuna procedura
grafo del controllo del flusso interprocedurale
alberi di sintassi astratta per le espressioni del programma
informazioni sui puntatori
Slicing
– partizionamento di un programma
– Tecnica per visualizzare le dipendenze
– restringe l’attenzione alle componenti di un programma
rilevanti per la valutazione di espressioni
– backward slicing / forward slicing
Generazione dei vincoli …

buf: puntatore a buffer modellato da 4 variabili di vincolo:
– buf!alloc!max
– buf!alloc!min

numero massimo e minimo di byte allocati per il buffer buf

numero massimo e minimo di byte usati da buf
– buf!used!max
– buf!used!min

i: variabile intera, modellata da 2 variabili di vincolo
– i!max

indica il massimo valore di i

denota il minimo valore di i
– i!min

I vincoli modellano il programma in maniera
– non sensibile al flusso

ignora l’ordine degli statement
– non sensibile al contesto

non fa differenze per molteplici punti di chiamata, alla stessa funzione
…

4 statement generano
vincoli
–
–
–
–

dichiarazioni di buffer
assegnamenti
chiamate a funzione
statement di ritorno
Es: alla riga 17 del codice
– strcpy(copy,buffer)



Risultano i vincoli (associati
ai puntatori dei buffer):
copy!used!max ≥
buffer!used!max
copy!used!min ≤
buffer!used!min
… alcuni chiarimenti


Poiché è ignorata l’analisi di flusso, i predicati come counter < 10
sono ignorati
Se generiamo un vincolo del tipo counter!max ≥ counter!max + 1
(generato da counter++), questo non può essere interpretato da un
risolutore di programmi lineari
– dunque questo statement è modellato trattandolo come due statement:
counter’ = counter + 1 e counter = counter’. I due vincoli catturano il
fatto che il puntatore è incrementato di uno e sono accettabili dal
risolutore, anche se il programma lineare risultante sarà non
ammissibile

Una variabile di programma che ottiene il suo valore dall’ambiente o
dall’input dell’utente in un modo non controllato, è considerata
insicura
– Se consideriamo, ad esempio, lo statement getenv(“PATH”), che ritorna
il percorso di ricerca, può ritornare una stringa arbitrariamente lunga.
Per riflettere il fatto che la stringa può essere arbitrariamente lunga,
sono generati dei vincoli del tipo getenv$return!used!max ≥ +∞ e
getenv$return!used!min ≤ 0. Allo stesso modo, una variabile intera i
inserita dall’utente genera i vincoli: i!max ≥ +∞ e i!min ≤ -∞
Analisi di alterazione

Vincoli generati, passati al modulo di analisi di alterazione
– Scopo: ottenere dei vincoli che siano successivamente utilizzabili
dal risolutore
– Solo valori finiti

2 passi
– Identificare e rimuovere variabili che danno valore infinito
– Identifica e rimuove variabili di vincolo non inizializzata

il sistema di vincoli è esaminato per vedere se
– vincoli di tipo max hanno un estremo inferiore finito
– vincoli di tipo min hanno un estremo superiore finito

Requisito non soddisfatto se
– non sono state inizializzate nel codice sorgente
– gli statement che influiscono sulle variabili di programma non sono state
catturate dal generatore di vincoli
 => non esiste modello per funzioni di librerie
Risoluzione dei vincoli…

si utilizza la programmazione lineare
– modella e manipola nuovi tipi di vincoli
– garantisce correttezza dei risultati

Un programma lineare e' un problema di
ottimizzazione:
minimizza cTx
riferito a Ax ≥ b
– A matrice m x n di costanti
– b e c vettori di costanti
– x è vettore di variabili

sistema di m disequazioni in n variabili, necessarie per
trovare i valori delle variabili che soddisfano i vincoli e
minimizzano la funzione obiettivo cTx, nel campo dei numeri
reali finiti.
…

Insieme di vincoli ottenuti dopo l'analisi è insieme di
vincoli lineari
– si può allora formulare come problema di programmazione
lineare
– Obiettivo: ottenere i valori




buf!alloc!max
buf!alloc!min
buf!used!max
buf!used!min
– che rendono la differenza tra byte allocati e byte usati dal puntatore al
buffer buf più piccola possibile, rispettando i vincoli
– se tutte le variabili max hanno minimo finito e tutte le
variabili min hanno massimo finito, vale che:

min Σbuf (buf!alloc!max - buf!alloc!min + buf!used!max - buf!used!min)
…

Trovare soluzioni intere è Programmazione
Lineare Intera: problema NP-completo ben
conosciuto
– NP = è noto un algoritmo che termina in tempo polinomiale rispetto alla
dimensione dei dati
– NP-hard = un algoritmo per risolvere uno di questi problemi può essere
convertito in un algoritmo per risolvere un qualunque problema NP
– NP-completi = sia NP che NP-hard

programma lineare ammissibile
– si trovano valori finiti per tutte le variabili (rispettando
i vincoli)

soluzione ammissibile è ottima
– se massimizza (o minimizza) il valore della funzione

programma lineare inammissibile
– se non ha soluzioni ammissibili
…


soluzione ottima per determinare i limiti del buffer
nessun programma può essere illimitato
– vincoli esaminati dall'analizzatore di alterazione




tutte le variabili max della funzione obiettivo hanno limite inferiore finito
Minimizzando le variabili max otterremo ancora valori finiti
Similmente per min
se programma lineare non ha soluzioni ammissibili
– non si può assegnare arbitrariamente dei valori finiti alle variabili per
ottenere soluzioni ammissibili
– Es: settare tutte le variabili di max a +∞ e quelle di min a -∞ => ci
sarebbero troppi falsi allarmi!

approccio in cui si rimuovere un piccolo insieme di vincoli per rendere
il sistema ammissibile
– noto come Irreducibly Inconsistent Set (IIS)

insieme minimale di vincoli: l'intero insieme dei vincoli di un IIS è
inammissibile ma ogni sottoinsieme è ammissibile
Elastic Filtering algorithm


1.
Dato un insieme di vincoli determina un IIS (se esiste) e garantisce
che nel caso ce ne siano più di uno almeno uno venga rilevato
si può iterare l'algoritmo più volte sul risultato dell'iterazione
precedente per creare il più piccolo programma lineare ammissibile
da uno non ammissibile
esamina l'insieme dei vincoli C per
determinare ammissibilità
Se è ammissibile STOP
Altrimenti -> 2
2.
3.
4.
allora esiste almeno un C’  C che
è IIS
genera dopo un certo numero di
iterazioni, C-C’ ammissibile
settare i valori delle variabili max e
min in C' rispettivamente a ∞ e -∞
5.
ci sono variabili a ∞
rimuovere i vincoli alterati da
queste variabili: C’’  C-C‘
D=C-C’-C”
Risolvere i vincoli
gerarchicamente

Elastic Filtering algorithm veloce ma
anche un’approssimazione
– può rimuovere più vincoli di quelli necessari
per avere una soluzione ammissibile
risolutore gerarchico

scomporre l’insieme dei vincoli in insiemi più
piccoli e risolverli separatamente
– grafo diretto aciclico (DAG)
 ogni insieme di vincoli è associato a un vertice del
DAG e gli archi rappresentano le dipendenze tra
essi
 modifica a ∞ un numero inferiore di variabili, risulta
più preciso e determina dei valori precisi
Individuare overrun

basata sui valori restituiti dal risolutore e dai valori
dell’analisi di alterazione
– buffer puntato da header ha 2048 byte allocati e la sua
lunghezza può variare tra 1 e 2048 byte => non si può
verificare un buffer overrun => header è segnato
come “sicuro”. La stessa cosa vale per buf.
– buffer puntato da ptr ha un numero di byte allocati
[1024..2048] mentre la lunghezza può variare
[1..2048]. ptr fa parte di due statement. Alla riga (6)
ptr punta ad un buffer lungo 2048 byte mentre alla
riga (9) punta ad un buffer lungo 1024 byte. La non
sensibilità al contesto dell’analisi significa che non
possiamo fare differenze tra i due punti del programma
e dunque possiamo derivare che al massimo ptr è di
2048 byte. In questo tipo di situazione in cui si verifica
che


ptr!alloc!min < ptr!used!max ≤ ptr!alloc!max
possiamo avere un overrun. Questo però è un falso
positivo dovuto alla non sensibilità del contesto dell’analisi
– variabile copy: copy!alloc!max < copy!used!max e c’è
un’esecuzione del programma in cui saranno scritti più
byte di quelli che possono essere ottenuti

Concludiamo dunque che in questa situazione si verifica
un overrun
Aggiungere la sensibilità
al contesto

generazione dei vincoli
– non è sensibile al contesto
– si considera ogni punto di chiamata come un
assegnamento delle variabili in input reali alle
variabili in input formali e il ritorno dalla funzione
come un assegnamento delle variabili in output
formali alle variabili in output reali

si fondono le informazioni attraverso i punti di
chiamata, ottenendo un’analisi imprecisa
2 tecniche


constraint inlining
summary information
constraint inlining…

Inlining nelle funzioni
– rimpiazza una chiamata di
funzione con un’istanza del corpo
della funzione
– gli argomenti reali sono sostituiti a
quelli formali
– eseguita a tempo di compilazione
– crea una nuova istanza dei vincoli
della funzione chiamata ad ogni
punto di chiamata

Se non sensibile al contesto
– si trattano differenti punti di
chiamata ad una funzione, in
modo identico
Ad ogni punto di chiamata di una
funzione, produciamo i vincoli per la
funzione con le variabili locali e i
parametri formali, rinominati
unicamente per quel punto di
chiamata
…


La sensibilità al contesto si può ottenere modellando ciascun punto
di chiamata alla funzione come un insieme di assegnamenti di
istanze rinominate delle variabili formali
un assegnamento per ciascun parametro in input formale rinominato
della funzione
– allevia il problema di unire le informazioni attraverso differenti chiamate
alla stessa funzione
– per il puntatore cc1 otteniamo il range [0…2047] per cc1!alloc e
[1…2048] per cc1!used
– per il puntatore cc2 otteniamo il range [0…1023] per cc2!alloc e
[1…1024] per cc2!used

miglioramento rispetto a non sensibile al contesto, ma…
– Se numero esponenziale di contesti di chiamata



il sistema di vincoli avrà un numero molto grande di variabili
ci sarà anche un grande numero di vincoli
non può funzionare con le chiamate di funzioni ricorsive
summary information…


supera i difetti del constraint inlining
si ottiene un “riassunto” per ciascuna funzione f
per “simulare” l’effetto della chiamata
– Vincoli riassuntivi



riassumono l’effetto della funzione in termini di variabili di
vincolo rappresentanti variabili globali e parametri formali
della funzione stessa
Es: i vincoli generati dalla funzione copy_buffer
Rimpiazzare parametri formali dei vincoli riassuntivi con quelli
reali corrispondenti a ciascun punto di chiamata
…

Questo approccio non causa un accrescimento del
numero di variabili di vincolo
– è più efficiente ma meno preciso del constraint inlining
– può manipolare anche le funzioni ricorsive

Es:
– i valori per cc1!used, cc1!alloc, cc2!used e cc2!alloc sono gli
stessi che si ottengono usando il constraint inlining
– i valori di copy!alloc e copy!used sono [0…2047] e [1...2048]
rispettivamente

Questo perché i valori di queste variabili ottenute dalla chiamata alla
riga (7) e alla riga (10) sono “unite”
– Il constraint inlining ritorna i valori [0...2047] e [1…2048] per
copy!alloc e copy!used, rispettivamente per la chiamata alla riga
(7)
– ritorna [0…1023] e [1…1024] per la chiamata alla riga (10)
Sperimentazione su casi
reali

Testato su
–
–
–
–
–
–


wu-ftpd (2.5.0 e 2.6.2) e sendmail (8.7.6 e 8.11.6)
Pentium 4 Xeon 3GHz, 4 GB RAM
sistema operativo Debian Linux 3.0
CodeSurfer 1.8 e compilatore gcc-3.2.1
risolutore gerarchico
Context insensitive
CodeSurfer per filtrare i warning
Testato per provare se riusciva a scoprire bug
già conosciuti e se riusciva a scoprirne altri non
conosciuti
Testing wu-ftpd 2.6.2


18mila righe di codice
tool ha segnalato 178 warning
– 14 overrun mai segnalati. Eccone uno:


•
•
•
•
potenziale overrun su buffer puntato
da accesspath in read_servers_line nel
file rdservers.c:
8192 byte possono essere copiati in un
buffer in cui sono allocati al massimo
4095 byte
La funzione fgets può copiare fino a 8192 (dimensione di BUFSIZ) byte in buffer
hcp e acp, puntano all’interno di buffer => qualcuno può far puntare hcp o acp ad un buffer lungo
fino a 8192 byte => overflow sul buffer puntato sia da accesspath sia da hostname
La procedura read_server_line è chiamata, ad es, nel main di ftprestart.c con due buffer locali,
hostaddress e configdir, per i quali sono allocati 32 byte e 4095 byte, rispettivamente
La chiamata legge il contenuto del file _PATH_FTPSERVERS, che tipicamente ha accesso
privilegiato
•
•
In alcune configurazioni questo file può essere scritto da un utente locale
Scegliendo dunque delle stringhe di input in maniera attenta, si può sfruttare l’overflow per ottenere accessi
privilegiati
Testing wu-ftpd 2.5.0


16mila righe di codice
tool ha segnalato 139 warning
– overflow su una variabile globale, mapped_path, che punta ad un
buffer nella procedura do_elem nel file ftpd.c

Uso improprio di strcat(mapped_path,dir)
– dir può derivata (indirettamente) dall’input dell’utente
– range per mapped_path!used è [0…+∞] mentre per mapped_path!alloc
è [4095…4095]

La chiamata a strcat è modellata
secondo quattro vincoli lineari
– I primi due vincoli rendono il
programma lineare non ammissibile
– risultato in dst!used!max settato a +∞
– mapped_path!used!max settato +∞
Testing sendmail

8.7.6
– 38mila righe di codice
– tool ha segnalato 295 warning


alcuni overflow di tipo off-by-one
8.11.6
– si potrebbe verificare la scrittura di n+1 byte in un buffer che ha n byte
allocati
– 68mila righe di codice
– Tool ha segnalato 453 warning

Uno coinvolge la funzione crackaddr nel file headers.c, che fa il
parsing della stringa di un indirizzo e-mail
– memorizza la stringa dell’indirizzo in un buffer statico locale, buf lungo
MAXNAME + 1 byte.
– molti controlli di limite per evitare l’overflow ma la condizione di <>
nella stringa From è imprecisa e porta all’overflow
– eseguite molte operazioni matematiche sui puntatori => bp!alloc!max
= +∞ e bp!used!max = +∞ (bp puntatore a buf)
– warning esiste anche se le condizioni di controllo sui limiti sono corrette
Performance

tempi di esecuzione impiegati per il controllo del codice
– CODESURFER: tempo impiegato dall’applicazione per l’analisi del
codice
– GENERATOR: tempo per la generazione dei vincoli
– TAINT: analisi di alterazione
– LPSOLVE: tempi per il metodo IIS
– HIERSOLVE: tempi per il metodo gerarchico
– PRE-TAINT: vincoli generati prima dell’analisi di alterazione
– POST-TAINT: vincoli generati dopo l’analisi di alterazione
sensibilità al contesto su
casi reali





Testata su wuftpd-2.6.2 usando sia l’approccio con constraint inlining sia
l’approccio summary constraint
Aggiungere la sensibilità al contesto non trova nuovi overrun ma fornisce
migliori valori dati dal risolutore dei vincoli
Test: controllo delle variabili “affinate”
senza sensibilità al contesto: valori per 7310 variabili
summary constraint: raffinamento di 72 variabili
– Il numero di variabili di vincolo è lo stesso dell’analisi senza sensibilità al contesto
– il numero di vincoli può cambiare e cresce dell’ 1%


l’approccio introduce alcuni vincoli (i “riassunti”) e rimuove altri vincoli (i vincoli degli
assegnamenti dei vecchi punti di chiamata)
Constraint inlining
– specializza l’insieme di vincoli per ciascun punto di chiamata


aumento di 5,8 volte nel numero di vincoli
aumento di 8,7 volte nel numero di variabili di vincolo
– 7310 variabili dell’analisi senza sensibilità al contesto sono specializzate in 63704
variabili basate sul contesto di chiamata
– Su 63704 variabili specializzate, 7497 variabili sono molto più precise
– Su 7310 variabili non specializzate, 406 sono più precise in almeno un contesto di
chiamata
Effetto dell’analisi dei
puntatori

ridurre i falsi negativi con l’uso dell’analisi dei
puntatori
– tool ha la capacità di gestire, in maniera arbitraria, i
livelli di dereferenziamento

confronto risultati restituiti utilizzando i puntatori
e i risultati ottenuti senza analisi dei puntatori:
– su sendmail sono generati 251 warning a differenza
dei 295 generati con l’analisi dei puntatori

tool fallisce nel generare i vincoli per alcuni
statement
Imperfezioni

flow insensitivity produce molti falsi allarmi
– Con partizionamento è possibile affrontare questo tipo di
problema




operazione manuale e dispendiosa
benefici della context sensitivity sono limitati dalla flow
insensitivity dell’analisi
modellando i vincoli in termini di puntatori ai buffer
piuttosto che buffer stessi, possiamo perdere gli
overrun, portando a falsi negativi.
algoritmi di analisi dei puntatori sono flow insensitive e
context insensitive
– generare vincoli in termini di buffer avrebbe portato come
risultato ad un maggiore numero di vincoli e
conseguentemente ad un maggiore numero di falsi allarmi
Bibliografia











http://en.wikipedia.org/wiki/Buffer_overrun
Analysis and verification: Buffer overrun detection using linear programming and
static analysis Vinod Ganapathy, Somesh Jha, David Chandler, David Melski, David
Vitek, 10th ACM conference on Computer and communications security, 2003
The twenty most critical internet security vulnerabilities www.sans.org/top20
L. O. Andersen. Program Analysis and Specialization for the C Programming
Language. PhD thesis, DIKU, Univ. Of Copenhagen, 1994
C. Cowan, S. Beattie, J. Johansen, and P.Wagle PointGuardTM: Protecting pointers
from buffer overflow vulnerabilities. In 12th USENIX Sec. Symp., 2003
V. Ganapathy, S. Jha, D. Chandler, D. Melski, and D. Vitek.
Buffer overrun detection using linear programming and static analysis. 2003. UWMadison Comp. Sci. Tech. Report 1488 ftp://ftp.cs.wisc.edu/pub/techreports/reports/2003/tr1488.ps.Z
CPLEX Optimizer. www.cplex.com
D. Wagner, J. S. Foster, E. A. Brewer, and A. Aiken. A first step towards automated
detection of buffer overrun vulnerabilities. In Network and Distributed System
Security (NDSS), 2000.
Y. Xie, A. Chou, and D. Engler. ARCHER: Using symbolic, path-sensitive analysis to
detect memory access errors. In 9° European Soft. Engg. Conf. and 11th ACM Symp.
on Foundation of Soft. Engg. (ESEC/FSE), 2003.
CodeSurfer http://www.grammatech.com/products/codesurfer