Comment se produit un « débordement de pile » et comment l'éviter ?

Question

Comment se produit un débordement de pile et quels sont les meilleurs moyens de s'assurer que cela ne se produise pas, ou de l'empêcher, en particulier sur les serveurs Web, mais d'autres exemples seraient également intéressants ?

Answer 1

Empiler

Une pile, dans ce contexte, est le dernier tampon entré, premier sorti dans lequel vous placez les données pendant l'exécution de votre programme.Dernier entré, premier sorti (LIFO) signifie que la dernière chose que vous mettez est toujours la première chose que vous ressortez - si vous poussez 2 éléments sur la pile, « A » puis « B », alors la première chose que vous faites apparaître. de la pile sera « B », et la chose suivante est « A ».

Lorsque vous appelez une fonction dans votre code, l'instruction suivante après l'appel de fonction est stockée sur la pile, ainsi que tout espace de stockage susceptible d'être écrasé par l'appel de fonction.La fonction que vous appelez peut utiliser plus de pile pour ses propres variables locales.Une fois terminé, il libère l'espace de pile de variables locales utilisé, puis revient à la fonction précédente.

Débordement de pile

Un débordement de pile se produit lorsque vous avez utilisé plus de mémoire pour la pile que ce que votre programme était censé utiliser.Dans les systèmes embarqués, vous ne pouvez avoir que 256 octets pour la pile, et si chaque fonction occupe 32 octets, vous ne pouvez avoir que 8 appels de fonction en profondeur - la fonction 1 appelle la fonction 2 qui appelle la fonction 3 qui appelle la fonction 4 ....qui appelle la fonction 8 qui appelle la fonction 9, mais la fonction 9 écrase la mémoire en dehors de la pile.Cela pourrait écraser la mémoire, le code, etc.

De nombreux programmeurs font cette erreur en appelant la fonction A qui appelle ensuite la fonction B, qui appelle ensuite la fonction C, qui appelle ensuite la fonction A.Cela peut fonctionner la plupart du temps, mais une seule fois, une mauvaise entrée le fera rester dans ce cercle pour toujours jusqu'à ce que l'ordinateur reconnaisse que la pile est exagérée.

Les fonctions récursives en sont également une cause, mais si vous écrivez de manière récursive (c'est-à-dire que votre fonction s'appelle elle-même), vous devez en être conscient et utiliser des variables statiques/globales pour empêcher une récursion infinie.

Généralement, le système d’exploitation et le langage de programmation que vous utilisez gèrent la pile, et cela n’est pas entre vos mains.Vous devriez regarder votre graphique d'appels (une structure arborescente qui montre à partir de votre principal ce que chaque fonction appelle) pour voir jusqu'où vont vos appels de fonction et pour détecter les cycles et la récursion qui ne sont pas prévus.Les cycles intentionnels et la récursion doivent être vérifiés artificiellement pour éviter les erreurs s'ils s'appellent trop souvent.

Au-delà des bonnes pratiques de programmation et des tests statiques et dynamiques, vous ne pouvez pas faire grand-chose sur ces systèmes de haut niveau.

Systèmes embarqués

Dans le monde embarqué, en particulier dans le code à haute fiabilité (automobile, avion, espace), vous effectuez des révisions et des vérifications approfondies du code, mais vous effectuez également les tâches suivantes :

• Interdire la récursivité et les cycles - appliqués par la politique et les tests
• Gardez le code et la pile éloignés l'un de l'autre (code en flash, pile en RAM et jamais les deux ne se rencontreront)
• Placez des bandes de garde autour de la pile - une zone vide de mémoire que vous remplissez avec un nombre magique (généralement une instruction d'interruption logicielle, mais il existe de nombreuses options ici), et des centaines ou des milliers de fois par seconde, vous regardez les bandes de garde pour vous assurer ils n'ont pas été écrasés.
• Utiliser la protection de la mémoire (c'est-à-dire pas d'exécution sur la pile, pas de lecture ou d'écriture juste en dehors de la pile)
• Les interruptions n'appellent pas de fonctions secondaires - elles définissent des indicateurs, copient les données et laissent l'application s'occuper de leur traitement (sinon vous pourriez avoir 8 profondeurs dans votre arborescence d'appels de fonction, avoir une interruption, puis exécuter quelques autres fonctions à l'intérieur du interruption, provoquant l'éruption).Vous disposez de plusieurs arborescences d'appels : une pour les processus principaux et une pour chaque interruption.Si vos interruptions peuvent s'interrompre...eh bien, il y a des dragons...

Langages et systèmes de haut niveau

Mais dans les langages de haut niveau exécutés sur les systèmes d'exploitation :

• Réduisez le stockage de vos variables locales (les variables locales sont stockées sur la pile - bien que les compilateurs soient assez intelligents à ce sujet et mettent parfois de gros éléments locaux sur le tas si votre arbre d'appels est peu profond)
• Éviter ou limiter strictement la récursivité
• Ne divisez pas trop vos programmes en fonctions de plus en plus petites - même sans compter les variables locales, chaque appel de fonction consomme jusqu'à 64 octets sur la pile (processeur 32 bits, économisant la moitié des registres du processeur, des indicateurs, etc.)
• Gardez votre arbre d'appels superficiel (similaire à la déclaration ci-dessus)

Serveurs Web

Cela dépend du « bac à sable » dont vous disposez, si vous pouvez contrôler ou même voir la pile.Il y a de fortes chances que vous puissiez traiter les serveurs Web comme vous le feriez avec n'importe quel autre langage et système d'exploitation de haut niveau - cela est en grande partie hors de votre contrôle, mais vérifiez le langage et la pile de serveurs que vous utilisez.Il est possible de faire exploser la pile sur votre serveur SQL, par exemple.

-Adam

Answer 2

Un débordement de pile dans le code réel se produit très rarement.La plupart des situations dans lesquelles cela se produit sont des récursions où la terminaison a été oubliée.Cela peut cependant rarement se produire dans des structures fortement imbriquées, par ex.documents XML particulièrement volumineux.La seule véritable aide ici est de refactoriser le code pour utiliser un objet de pile explicite au lieu de la pile d'appels.

Answer 3

La plupart des gens vous diront qu'un débordement de pile se produit avec une récursion sans chemin de sortie - bien que cela soit généralement vrai, si vous travaillez avec des structures de données suffisamment volumineuses, même un chemin de sortie de récursion approprié ne vous aidera pas.

Quelques options dans ce cas :

• Recherche en largeur
• Récursivité de la queue, Génial spécifique à .Net article de blog (désolé, .Net 32 ​​bits)

Answer 4

La récursion infinie est un moyen courant d'obtenir une erreur de débordement de pile.Pour éviter - assurez-vous toujours qu'il existe un chemin de sortie qui volonté être touché.:-)

Une autre façon d'obtenir un débordement de pile (au moins en C/C++) consiste à déclarer une énorme variable sur la pile.

char hugeArray[100000000];

Cela le fera.

Answer 5

Un débordement de pile se produit lorsque Jeff et Joel souhaitent offrir au monde un meilleur endroit pour obtenir des réponses aux questions techniques.Il est trop tard pour empêcher ce débordement de pile.Cet "autre site" aurait pu l'empêcher en n'étant pas dégueulasse.;)

Answer 6

Habituellement, un débordement de pile est le résultat d'un appel récursif infini (étant donné la quantité habituelle de mémoire dans les ordinateurs standards de nos jours).

Lorsque vous appelez une méthode, une fonction ou une procédure, la manière "standard" d'effectuer l'appel consiste à :

1. Pousser la direction de retour de l'appel dans la pile (c'est la phrase suivante après l'appel)
2. Habituellement, l'espace pour la valeur de retour est réservé dans la pile
3. Pousser chaque paramètre dans la pile (l'ordre diverge et dépend de chaque compilateur, certains d'entre eux sont également parfois stockés dans les registres du CPU pour améliorer les performances)
4. Passer l'appel proprement dit.

Ainsi, cela prend généralement quelques octets en fonction du nombre et du type de paramètres ainsi que de l'architecture de la machine.

Vous verrez alors que si vous commencez à faire des appels récursifs, la pile commencera à croître.Désormais, la pile est généralement réservée en mémoire de telle manière qu'elle grandit dans la direction opposée au tas. Ainsi, étant donné un grand nombre d'appels sans "revenir", la pile commence à se remplir.

Désormais, dans les temps anciens, un débordement de pile pouvait se produire simplement parce que vous aviez épuisé toute la mémoire disponible, juste comme ça.Avec le modèle de mémoire virtuelle (jusqu'à 4 Go sur un système X86) qui était généralement hors de portée, si vous obtenez une erreur de dépassement de pile, recherchez un appel récursif infini.

Answer 7

Mis à part la forme de débordement de pile que vous obtenez d'une récursivité directe (par exemple Fibonacci(1000000)), une forme plus subtile que j'ai expérimentée à plusieurs reprises est une récursion indirecte, où une fonction appelle une autre fonction, qui en appelle une autre, puis l'une de ces fonctions appelle à nouveau la première.

Cela peut généralement se produire dans des fonctions appelées en réponse à des événements mais qui peuvent elles-mêmes générer de nouveaux événements, par exemple :

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

Dans ce cas, l'appel à ResizeWindow peut causer le WindowSizeChanged() rappel à déclencher à nouveau, qui appelle ResizeWindow encore une fois, jusqu'à ce que vous manquiez de pile.Dans de telles situations, vous devez souvent différer la réponse à l'événement jusqu'au retour du cadre de pile, par exemple en publiant un message.

Answer 8

Quoi?Personne n’aime ceux qui sont enfermés dans une boucle infinie ?

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

Answer 9

Considérant que cela a été étiqueté avec "piratage", je soupçonne que le "débordement de pile" auquel il fait référence est un débordement de pile d'appels, plutôt qu'un débordement de pile de niveau supérieur tel que ceux référencés dans la plupart des autres réponses ici.Cela ne s'applique pas vraiment aux environnements gérés ou interprétés tels que .NET, Java, Python, Perl, PHP, etc., dans lesquels les applications Web sont généralement écrites. Votre seul risque est donc le serveur Web lui-même, qui est probablement écrit en C ou C++.

Consultez ce fil :

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