¿Cómo se produce un "desbordamiento de pila" y cómo se puede prevenir?

Question

¿Cómo se produce un desbordamiento de pila y cuáles son las mejores formas de asegurarse de que no suceda, o formas de evitarlo, especialmente en servidores web, pero también serían interesantes otros ejemplos?

Answer 1

Pila

Una pila, en este contexto, es el último búfer en entrar y primero en salir en el que coloca los datos mientras se ejecuta el programa.El último en entrar, el primero en salir (LIFO) significa que lo último que pones es siempre lo primero que sacas: si empujas 2 elementos en la pila, 'A' y luego 'B', entonces lo primero que sacas fuera de la pila será 'B', y lo siguiente será 'A'.

Cuando llamas a una función en tu código, la siguiente instrucción después de la llamada a la función se almacena en la pila y cualquier espacio de almacenamiento que pueda ser sobrescrito por la llamada a la función.La función que llame podría utilizar más pila para sus propias variables locales.Cuando termina, libera el espacio de pila de variables locales que usó y luego regresa a la función anterior.

Desbordamiento de pila

Un desbordamiento de pila ocurre cuando usted ha usado más memoria para la pila de la que se suponía que debía usar su programa.En los sistemas integrados, es posible que solo tenga 256 bytes para la pila, y si cada función ocupa 32 bytes, entonces solo puede tener llamadas a funciones de 8 profundidades: la función 1 llama a la función 2, quien llama a la función 3, quien llama a la función 4...quién llama a la función 8 quién llama a la función 9, pero la función 9 sobrescribe la memoria fuera de la pila.Esto podría sobrescribir la memoria, el código, etc.

Muchos programadores cometen este error al llamar a la función A que luego llama a la función B, que luego llama a la función C, que luego llama a la función A.Puede que funcione la mayor parte del tiempo, pero una sola vez, la entrada incorrecta hará que gire en ese círculo para siempre hasta que la computadora reconozca que la pila está sobrecargada.

Las funciones recursivas también son una causa de esto, pero si escribe de forma recursiva (es decir, su función se llama a sí misma), debe tener esto en cuenta y utilizar variables estáticas/globales para evitar la recursividad infinita.

Generalmente, el sistema operativo y el lenguaje de programación que estás usando administran la pila y está fuera de tu control.Deberías mirar tu gráfico de llamadas (una estructura de árbol que muestra desde tu principal lo que llama cada función) para ver qué tan profundas son tus llamadas a funciones y para detectar ciclos y recursividad que no son los previstos.Los ciclos intencionales y la recursividad deben comprobarse artificialmente para detectar errores si se llaman entre sí demasiadas veces.

Más allá de las buenas prácticas de programación y las pruebas estáticas y dinámicas, no hay mucho que pueda hacer en estos sistemas de alto nivel.

Sistemas embebidos

En el mundo integrado, especialmente en el código de alta confiabilidad (automotor, avión, espacio), se realizan revisiones y comprobaciones exhaustivas del código, pero también se hace lo siguiente:

• No permitir la recursividad y los ciclos: aplicados por políticas y pruebas
• Mantenga el código y la pila separados (código en flash, pila en RAM y nunca los dos se encontrarán)
• Coloque bandas de protección alrededor de la pila: área vacía de memoria que llena con un número mágico (generalmente una instrucción de interrupción de software, pero aquí hay muchas opciones), y cientos o miles de veces por segundo mira las bandas de protección para asegurarse. no han sido sobrescritos.
• Utilice protección de memoria (es decir, no ejecute en la pila, no lea ni escriba fuera de la pila)
• Las interrupciones no llaman a funciones secundarias: establecen indicadores, copian datos y dejan que la aplicación se encargue de procesarlos (de lo contrario, podría llegar a 8 de profundidad en su árbol de llamadas de funciones, tener una interrupción y luego salir de otras funciones dentro del interrumpir, provocando la explosión).Tiene varios árboles de llamadas: uno para los procesos principales y otro para cada interrupción.Si tus interrupciones pueden interrumpirse entre sí...bueno, habrá dragones...

Lenguajes y sistemas de alto nivel.

Pero en lenguajes de alto nivel se ejecutan en sistemas operativos:

• Reduzca su almacenamiento de variables locales (las variables locales se almacenan en la pila, aunque los compiladores son bastante inteligentes al respecto y, a veces, colocarán variables locales grandes en el montón si su árbol de llamadas es poco profundo)
• Evite o limite estrictamente la recursividad
• No divida demasiado sus programas en funciones cada vez más pequeñas; incluso sin contar las variables locales, cada llamada a función consume hasta 64 bytes en la pila (procesador de 32 bits, lo que ahorra la mitad de los registros de la CPU, indicadores, etc.)
• Mantenga su árbol de llamadas poco profundo (similar a la declaración anterior)

servidores web

Depende del 'sandbox' que tengas si puedes controlar o incluso ver la pila.Es muy probable que pueda tratar los servidores web como lo haría con cualquier otro lenguaje y sistema operativo de alto nivel; en gran medida está fuera de su alcance, pero verifique el idioma y la pila de servidores que está utilizando.Él es Es posible volar la pila en su servidor SQL, por ejemplo.

-Adán

Answer 2

Un desbordamiento de pila en código real ocurre muy raramente.La mayoría de las situaciones en las que ocurre son recurrencias en las que se ha olvidado la terminación.Sin embargo, esto puede ocurrir raramente en estructuras muy anidadas, p.documentos XML particularmente grandes.La única ayuda real aquí es refactorizar el código para usar un objeto de pila explícito en lugar de la pila de llamadas.

Answer 3

La mayoría de la gente le dirá que se produce un desbordamiento de pila con recursividad sin una ruta de salida; aunque en su mayoría es cierto, si trabaja con estructuras de datos lo suficientemente grandes, ni siquiera una ruta de salida de recursividad adecuada le ayudará.

Algunas opciones en este caso:

• Búsqueda en amplitud
• recursividad de cola, .Net específico genial entrada en el blog (lo siento, .Net de 32 bits)

Answer 4

La recursividad infinita es una forma común de obtener un error de desbordamiento de pila.Para evitarlo, asegúrese siempre de que haya una ruta de salida que voluntad ser golpeado.:-)

Otra forma de conseguir un desbordamiento de pila (al menos en C/C++) es declarar alguna variable enorme en la pila.

char hugeArray[100000000];

Eso bastará.

Answer 5

Se produce un desbordamiento de pila cuando Jeff y Joel quieren brindarle al mundo un lugar mejor para obtener respuestas a preguntas técnicas.Es demasiado tarde para evitar que este desbordamiento de pila.Ese "otro sitio" podría haberlo evitado al no ser de mala calidad.;)

Answer 6

Por lo general, un desbordamiento de pila es el resultado de una llamada recursiva infinita (dada la cantidad habitual de memoria en las computadoras estándar hoy en día).

Cuando se realiza una llamada a un método, función o procedimiento la forma "estándar" o realizar la llamada consiste en:

1. Empujar la dirección de retorno de la llamada a la pila (esa es la siguiente oración después de la llamada)
2. Por lo general, el espacio para el valor de retorno se reserva en la pila.
3. Insertar cada parámetro en la pila (el orden diverge y depende de cada compilador; además, algunos de ellos a veces se almacenan en los registros de la CPU para mejorar el rendimiento)
4. Hacer la llamada real.

Por lo tanto, normalmente esto requiere unos pocos bytes dependiendo del número y tipo de parámetros, así como de la arquitectura de la máquina.

Verás entonces que si empiezas a hacer llamadas recursivas la pila empezará a crecer.Ahora, la pila generalmente se reserva en la memoria de tal manera que crece en dirección opuesta al montón, por lo que, dada una gran cantidad de llamadas sin "regresar", la pila comienza a llenarse.

Ahora, en tiempos más antiguos, el desbordamiento de la pila podía ocurrir simplemente porque agotaba toda la memoria disponible, así como así.Con el modelo de memoria virtual (hasta 4 GB en un sistema X86) que normalmente estaba fuera del alcance, si obtiene un error de desbordamiento de pila, busque una llamada recursiva infinita.

Answer 7

Aparte de la forma de desbordamiento de pila que se obtiene de una recursividad directa (por ejemplo, Fibonacci(1000000)), una forma más sutil que he experimentado muchas veces es una recursividad indirecta, donde una función llama a otra función, que llama a otra, y luego una de esas funciones vuelve a llamar a la primera.

Esto puede ocurrir comúnmente en funciones que se llaman en respuesta a eventos pero que a su vez pueden generar nuevos eventos, por ejemplo:

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

En este caso la llamada a ResizeWindow puede causar el WindowSizeChanged() la devolución de llamada se activará nuevamente, lo que llama ResizeWindow nuevamente, hasta que te quedes sin pila.En situaciones como estas, a menudo es necesario posponer la respuesta al evento hasta que el marco de la pila haya regresado, por ejemplo, publicando un mensaje.

Answer 8

¿Qué?¿Nadie ama a aquellos que están atrapados en un bucle infinito?

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

Answer 9

Teniendo en cuenta que esto fue etiquetado con "piratería", sospecho que el "desbordamiento de pila" al que se refiere es un desbordamiento de pila de llamadas, en lugar de un desbordamiento de pila de nivel superior, como los que se mencionan en la mayoría de las otras respuestas aquí.Realmente no se aplica a ningún entorno administrado o interpretado como .NET, Java, Python, Perl, PHP, etc., en el que normalmente se escriben las aplicaciones web, por lo que su único riesgo es el propio servidor web, que probablemente esté escrito en C o C++.

Mira este hilo:

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