Come si verifica uno “stack overflow” e come lo si previene?

Question

Come si verifica un overflow dello stack e quali sono i modi migliori per assicurarsi che non si verifichi o i modi per prevenirne uno, in particolare sui server Web, ma anche altri esempi sarebbero interessanti?

Answer 1

Pila

Uno stack, in questo contesto, è l'ultimo buffer ad entrare, il primo ad uscire in cui inserisci i dati durante l'esecuzione del programma.Last in, first out (LIFO) significa che l'ultima cosa che inserisci è sempre la prima cosa che tiri fuori: se metti 2 elementi sullo stack, "A" e poi "B", allora la prima cosa che estrai dallo stack ci sarà "B" e la cosa successiva sarà "A".

Quando chiami una funzione nel codice, l'istruzione successiva alla chiamata alla funzione viene archiviata nello stack e l'eventuale spazio di archiviazione che potrebbe essere sovrascritto dalla chiamata alla funzione.La funzione che chiami potrebbe utilizzare più stack per le proprie variabili locali.Al termine, libera lo spazio dello stack delle variabili locali utilizzato, quindi ritorna alla funzione precedente.

Overflow dello stack

Un overflow dello stack si verifica quando hai utilizzato più memoria per lo stack di quella che il tuo programma avrebbe dovuto utilizzare.Nei sistemi embedded potresti avere solo 256 byte per lo stack, e se ciascuna funzione occupa 32 byte allora puoi avere solo chiamate di funzione 8 profonde - la funzione 1 chiama la funzione 2 chi chiama la funzione 3 chi chiama la funzione 4 ....chi chiama la funzione 8 chi chiama la funzione 9, ma la funzione 9 sovrascrive la memoria all'esterno dello stack.Ciò potrebbe sovrascrivere memoria, codice, ecc.

Molti programmatori commettono questo errore chiamando la funzione A che poi chiama la funzione B, che poi chiama la funzione C, che poi chiama la funzione A.Potrebbe funzionare la maggior parte delle volte, ma solo una volta l'input sbagliato lo farà rimanere in quel circolo per sempre finché il computer non riconosce che lo stack è eccessivo.

Anche le funzioni ricorsive sono una causa di questo, ma se stai scrivendo in modo ricorsivo (cioè, la tua funzione chiama se stessa) allora devi esserne consapevole e usare variabili statiche/globali per prevenire la ricorsione infinita.

In genere, il sistema operativo e il linguaggio di programmazione che stai utilizzando gestiscono lo stack ed è fuori dal tuo controllo.Dovresti guardare il tuo grafico delle chiamate (una struttura ad albero che mostra dal tuo main cosa chiama ciascuna funzione) per vedere quanto sono profonde le chiamate alla tua funzione e per rilevare cicli e ricorsioni che non sono previsti.I cicli intenzionali e la ricorsione devono essere controllati artificialmente per individuare errori se si chiamano a vicenda troppe volte.

Al di là delle buone pratiche di programmazione e dei test statici e dinamici, non c'è molto che puoi fare su questi sistemi di alto livello.

Sistemi integrati

Nel mondo embedded, in particolare nel codice ad alta affidabilità (automobilistico, aeronautico, spaziale), si eseguono revisioni e controlli approfonditi del codice, ma si eseguono anche le seguenti operazioni:

• Non consentire ricorsione e cicli: imposto da policy e test
• Mantieni il codice e lo stack distanti (codice nella flash, stack nella RAM e i due non si incontreranno mai)
• Posiziona le bande di guardia attorno allo stack: un'area vuota di memoria che riempi con un numero magico (di solito un'istruzione di interruzione del software, ma qui ci sono molte opzioni) e centinaia o migliaia di volte al secondo guardi le bande di guardia per assicurarti non sono stati sovrascritti.
• Utilizzare la protezione della memoria (ovvero, nessuna esecuzione sullo stack, nessuna lettura o scrittura appena fuori dallo stack)
• Gli interrupt non chiamano funzioni secondarie: impostano flag, copiano dati e lasciano che l'applicazione si occupi di elaborarli (altrimenti potresti arrivare a 8 in profondità nell'albero delle chiamate di funzione, avere un interrupt e quindi uscire con altre funzioni all'interno del interrompere, provocando lo scoppio).Hai diversi alberi delle chiamate: uno per i processi principali e uno per ogni interruzione.Se le vostre interruzioni possono interrompersi a vicenda...beh, ci sono i draghi...

Linguaggi e sistemi di alto livello

Ma nei linguaggi di alto livello vengono eseguiti sui sistemi operativi:

• Riduci l'archiviazione delle variabili locali (le variabili locali sono archiviate nello stack, anche se i compilatori sono piuttosto intelligenti a riguardo e talvolta inseriscono grandi locali nell'heap se l'albero delle chiamate è superficiale)
• Evitare o limitare rigorosamente la ricorsione
• Non suddividere troppo i tuoi programmi in funzioni sempre più piccole: anche senza contare le variabili locali, ogni chiamata di funzione consuma fino a 64 byte nello stack (processore a 32 bit, risparmiando metà dei registri della CPU, flag, ecc.)
• Mantieni l'albero delle chiamate poco profondo (simile all'affermazione precedente)

Server Web

Dipende dalla "sandbox" che hai se puoi controllare o addirittura vedere lo stack.È probabile che tu possa trattare i server web come faresti con qualsiasi altro linguaggio e sistema operativo di alto livello: è in gran parte fuori dal tuo controllo, ma controlla la lingua e lo stack di server che stai utilizzando.Esso È possibile far saltare lo stack sul tuo server SQL, ad esempio.

-Adamo

Answer 2

Un overflow dello stack nel codice reale si verifica molto raramente.La maggior parte delle situazioni in cui si verifica sono ricorsioni in cui la terminazione è stata dimenticata.Potrebbe tuttavia verificarsi raramente in strutture altamente annidate, ad es.documenti XML particolarmente grandi.L'unico vero aiuto qui è rifattorizzare il codice per utilizzare un oggetto stack esplicito invece dello stack di chiamate.

Answer 3

La maggior parte delle persone ti dirà che si verifica un overflow dello stack con la ricorsione senza un percorso di uscita - sebbene sia per lo più vero, se lavori con strutture dati sufficientemente grandi, anche un percorso di uscita ricorsivo adeguato non ti aiuterà.

Alcune opzioni in questo caso:

• Ricerca in ampiezza
• Ricorsione della coda, .Net fantastico post sul blog (scusate, .Net a 32 bit)

Answer 4

La ricorsione infinita è un modo comune per ottenere un errore di overflow dello stack.Per evitare: assicurati sempre che ci sia un percorso di uscita Volere essere colpito.:-)

Un altro modo per ottenere uno stack overflow (almeno in C/C++) è dichiarare qualche variabile enorme nello stack.

char hugeArray[100000000];

Basterà.

Answer 5

Si verifica uno stack overflow quando Jeff e Joel vogliono offrire al mondo un posto migliore in cui ottenere risposte a domande tecniche.È troppo tardi per impedire l'overflow dello stack.Quell'"altro sito" avrebbe potuto impedirlo non essendo scadente.;)

Answer 6

Di solito un overflow dello stack è il risultato di una chiamata ricorsiva infinita (data la normale quantità di memoria nei computer standard al giorno d'oggi).

Quando si effettua una chiamata ad un metodo, funzione o procedura il modo "standard" o l'effettuazione della chiamata consiste nel:

1. Inserimento della direzione di ritorno della chiamata nello stack (questa è la frase successiva dopo la chiamata)
2. Di solito lo spazio per il valore restituito viene riservato nello stack
3. Inserimento di ciascun parametro nello stack (l'ordine diverge e dipende da ciascun compilatore, inoltre alcuni di essi vengono talvolta memorizzati nei registri della CPU per miglioramenti delle prestazioni)
4. Effettuare la chiamata vera e propria.

Quindi, di solito, questo richiede alcuni byte a seconda del numero e del tipo di parametri, nonché dell'architettura della macchina.

Vedrai quindi che se inizi a effettuare chiamate ricorsive lo stack inizierà a crescere.Ora, lo stack è solitamente riservato in memoria in modo tale da crescere in direzione opposta all'heap quindi, dato un gran numero di chiamate senza "tornare indietro" lo stack inizia a riempirsi.

Ora, in passato, l'overflow dello stack potrebbe verificarsi semplicemente perché hai esaurito tutta la memoria disponibile, proprio così.Con il modello di memoria virtuale (fino a 4 GB su un sistema X86) che era fuori dall'ambito, quindi di solito, se ricevi un errore di overflow dello stack, cerca una chiamata ricorsiva infinita.

Answer 7

A parte la forma di stack overflow che si ottiene da una ricorsione diretta (ad es Fibonacci(1000000)), una forma più sottile che ho sperimentato molte volte è una ricorsione indiretta, in cui una funzione chiama un'altra funzione, che ne chiama un'altra, e poi una di quelle funzioni chiama di nuovo la prima.

Ciò può verificarsi comunemente in funzioni che vengono chiamate in risposta a eventi ma che a loro volta possono generare nuovi eventi, ad esempio:

void WindowSizeChanged(Size& newsize) {
  // override window size to constrain width
    newSize.width=200;
    ResizeWindow(newSize);
}

In questo caso la chiamata a ResizeWindow potrebbe causare il WindowSizeChanged() richiamata da attivare nuovamente, che chiama ResizeWindow di nuovo, finché non esaurisci lo stack.In situazioni come queste spesso è necessario posticipare la risposta all'evento fino al ritorno dello stack frame, ad esempio inviando un messaggio.

Answer 8

Che cosa?Nessuno ha amore per coloro che sono circondati da un ciclo infinito?

do
{
  JeffAtwood.WritesCode();
} while(StackOverflow.MakingMadBank.Equals(false));

Answer 9

Considerando che questo è stato contrassegnato con "hacking", sospetto che lo "stack overflow" a cui si riferisce sia un overflow dello stack di chiamate, piuttosto che un overflow dello stack di livello superiore come quelli a cui si fa riferimento nella maggior parte delle altre risposte qui.In realtà non si applica ad ambienti gestiti o interpretati come .NET, Java, Python, Perl, PHP, ecc., in cui sono generalmente scritte le app Web, quindi l'unico rischio è il server Web stesso, che probabilmente è scritto in C o C++.

Dai un'occhiata a questo thread:

https://stackoverflow.com/questions/7308/what-is-a-good-starting-point-for-learning-buffer-overflow