En programación informática , un desbordamiento de enteros ocurre cuando una operación aritmética con números enteros intenta crear un valor numérico que está fuera del rango que puede representarse con una cantidad determinada de dígitos, ya sea mayor que el valor máximo o menor que el valor mínimo representable.
El resultado más común de un desbordamiento es que se almacenan los dígitos menos significativos representables del resultado; se dice que el resultado se ajusta alrededor del máximo (es decir, módulo una potencia del radix , generalmente dos en las computadoras modernas, pero a veces diez u otro número). En algunos procesadores como las unidades de procesamiento gráfico (GPU) y los procesadores de señal digital (DSP) que admiten aritmética de saturación , los resultados desbordados se restringirían , es decir, se establecerían en el valor mínimo en el rango representable si el resultado está por debajo del mínimo y se establecerían en el valor máximo en el rango representable si el resultado está por encima del máximo, en lugar de ajustarse.
Una condición de desbordamiento puede generar resultados que conduzcan a un comportamiento no deseado. En particular, si no se ha previsto la posibilidad, el desbordamiento puede comprometer la confiabilidad y la seguridad de un programa .
Para algunas aplicaciones, como temporizadores y relojes, el ajuste en caso de desbordamiento puede ser conveniente. El estándar C11 establece que para los números enteros sin signo, el ajuste de módulo es el comportamiento definido y el término desbordamiento nunca se aplica: "un cálculo que involucra operandos sin signo nunca puede desbordarse". [1]
El ancho de registro de un procesador determina el rango de valores que se pueden representar en sus registros. Aunque la gran mayoría de las computadoras pueden realizar operaciones aritméticas de precisión múltiple en operandos en memoria, lo que permite que los números sean arbitrariamente largos y evitar el desbordamiento, el ancho de registro limita los tamaños de los números con los que se puede operar (por ejemplo, sumar o restar) utilizando una sola instrucción por operación. Los anchos de registro binarios típicos para números enteros sin signo incluyen:
Cuando una operación aritmética sin signo produce un resultado mayor que el máximo anterior para un entero de N bits, un desbordamiento reduce el resultado al módulo N-ésima potencia de 2, reteniendo solo los bits menos significativos del resultado y causando efectivamente un enrollamiento .
En particular, multiplicar o sumar dos números enteros puede dar como resultado un valor inesperadamente pequeño, y restar de un número entero pequeño puede causar un salto a un valor positivo grande (por ejemplo, la suma de un número entero de 8 bits 255 + 2 da como resultado 1, que es 257 mod 2 8 , y de manera similar, la resta 0 − 1 da como resultado 255, una representación de complemento a dos de −1).
Este tipo de envoltura puede causar perjuicios de seguridad: si se utiliza un valor desbordado como la cantidad de bytes a asignar a un búfer, el búfer se asignará inesperadamente pequeño, lo que puede provocar un desbordamiento del búfer que, dependiendo del uso del búfer, podría a su vez causar la ejecución de código arbitrario.
Si la variable tiene un tipo entero con signo , un programa puede suponer que una variable siempre contiene un valor positivo. Un desbordamiento de entero puede provocar que el valor se reinicie y se vuelva negativo, lo que viola la suposición del programa y puede provocar un comportamiento inesperado (por ejemplo, la suma de enteros de 8 bits de 127 + 1 da como resultado −128, un complemento a dos de 128). (Una solución para este problema en particular es utilizar tipos enteros sin signo para valores que un programa espera y supone que nunca serán negativos).
La mayoría de las computadoras tienen dos indicadores de procesador dedicados para verificar condiciones de desbordamiento.
El indicador de acarreo se activa cuando el resultado de una suma o resta, considerando los operandos y el resultado como números sin signo, no cabe en el número de bits indicado. Esto indica un desbordamiento con un acarreo o un préstamo del bit más significativo . Una operación de suma con acarreo o resta con préstamo inmediatamente posterior utilizaría el contenido de este indicador para modificar un registro o una ubicación de memoria que contenga la parte superior de un valor de varias palabras.
El indicador de desbordamiento se activa cuando el resultado de una operación con números con signo no tiene el signo que se podría predecir a partir de los signos de los operandos, por ejemplo, un resultado negativo al sumar dos números positivos. Esto indica que se ha producido un desbordamiento y que el resultado con signo representado en forma de complemento a dos no cabría en la cantidad de bits dada.
En el caso de un tipo sin signo, cuando el resultado ideal de una operación está fuera del rango representable del tipo y el resultado devuelto se obtiene mediante un encapsulamiento, este evento se define comúnmente como un desbordamiento. Por el contrario, el estándar C11 define que este evento no es un desbordamiento y establece que "un cálculo que involucra operandos sin signo nunca puede desbordarse". [1]
Cuando el resultado ideal de una operación entera está fuera del rango representable del tipo y el resultado devuelto se obtiene mediante una restricción, este evento se define comúnmente como una saturación. El uso varía en función de si una saturación es o no un desbordamiento. Para eliminar la ambigüedad, se pueden utilizar los términos desbordamiento envolvente [2] y desbordamiento saturante [3] .
Se pueden encontrar muchas referencias al desbordamiento por defecto de enteros. [4] [5] [6] [7] [8] Cuando se utiliza el término desbordamiento por defecto de enteros, significa que el resultado ideal estaba más cerca del infinito negativo que el valor representable del tipo de salida más cercano al infinito negativo. Según el contexto, la definición de desbordamiento puede incluir todos los tipos, incluidos los desbordamientos por defecto, o puede incluir solo los casos en los que el resultado ideal estaba más cerca del infinito positivo que el valor representable del tipo de salida más cercano al infinito positivo.
Cuando el resultado ideal de una operación no es un entero exacto, el significado de desbordamiento puede ser ambiguo en casos extremos. Considere el caso donde el resultado ideal tiene un valor de 127.25 y el valor máximo representable del tipo de salida es 127. Si el desbordamiento se define como el valor ideal que está fuera del rango representable del tipo de salida, entonces este caso se clasificaría como un desbordamiento. Para las operaciones que tienen un comportamiento de redondeo bien definido, la clasificación de desbordamiento puede necesitar posponerse hasta después de que se aplique el redondeo. El estándar C11 [1] define que las conversiones de punto flotante a entero deben redondearse hacia cero. Si se utiliza C para convertir el valor de punto flotante 127.25 a entero, entonces se debe aplicar primero el redondeo para dar una salida entera ideal de 127. Dado que el entero redondeado está en el rango de salidas, el estándar C no clasificaría esta conversión como un desbordamiento.
El comportamiento en caso de desbordamiento puede no ser consistente en todas las circunstancias. Por ejemplo, en el lenguaje Rust , si bien se proporciona funcionalidad para dar a los usuarios opciones y control, el comportamiento para el uso básico de operadores matemáticos es naturalmente fijo; sin embargo, este comportamiento fijo difiere entre un programa creado en modo "depuración" y uno creado en modo "liberación". [9] En C, el desbordamiento de enteros sin signo está definido para que se ajuste a la situación, mientras que el desbordamiento de enteros con signo causa un comportamiento indefinido .
La implementación de detección de desbordamiento en tiempo de ejecución UBSan( sanitizador de comportamiento indefinido ) está disponible para los compiladores de C.
En Java 8, hay métodos sobrecargados , por ejemplo Math.addExact(int, int), que lanzarán un error ArithmeticExceptionen caso de desbordamiento.
El equipo de respuesta a emergencias informáticas (CERT) desarrolló el modelo entero As-if Infinitely Ranged (AIR), un mecanismo en gran medida automatizado para eliminar el desbordamiento y truncamiento de enteros en C/C++ mediante el manejo de errores en tiempo de ejecución. [13]
Al asignar variables con tipos de datos que sean lo suficientemente grandes como para contener todos los valores que posiblemente se puedan calcular y almacenar en ellas, siempre es posible evitar el desbordamiento. Incluso cuando el espacio disponible o los tipos de datos fijos proporcionados por un lenguaje o entorno de programación son demasiado limitados para permitir que las variables se asignen defensivamente con tamaños generosos, al ordenar cuidadosamente las operaciones y verificar los operandos por adelantado, a menudo es posible garantizar a priori que el resultado nunca será mayor que lo que se puede almacenar. Se pueden utilizar herramientas de análisis estático , verificación formal y técnicas de diseño por contrato para garantizar con mayor confianza y solidez que no se pueda producir un desbordamiento accidental.
Si se prevé que puede producirse un desbordamiento, se pueden insertar pruebas en el programa para detectar cuándo sucede o está a punto de suceder y realizar otros procesos para mitigarlo. Por ejemplo, si un resultado importante calculado a partir de la entrada del usuario se desborda, el programa puede detenerse, rechazar la entrada y tal vez solicitar al usuario una entrada diferente, en lugar de que el programa proceda con la entrada desbordada no válida y probablemente funcione mal como consecuencia.
Las CPU generalmente tienen una forma de detectar esto para permitir la suma de números mayores que el tamaño de su registro, generalmente usando un bit de estado. La técnica se llama aritmética de precisión múltiple. Por lo tanto, es posible realizar una suma de bytes en operandos más anchos que un byte: primero sume los bytes bajos, almacene el resultado y verifique si hay desbordamiento; luego sume los bytes altos y, si es necesario, sume el acarreo de los bytes bajos y luego almacene el resultado.
El manejo de un posible desbordamiento de un cálculo puede presentar a veces la opción de realizar una comprobación antes de un cálculo (para determinar si se producirá o no un desbordamiento) o después de él (para considerar si es probable que se produzca o no en función del valor resultante). Dado que algunas implementaciones pueden generar una condición de trampa en caso de desbordamiento de enteros, los programas más portables realizan pruebas antes de realizar la operación que podría desbordarse.
Los lenguajes de programación implementan varios métodos de mitigación contra un desbordamiento accidental: Ada , Seed7 y ciertas variantes de lenguajes funcionales activan una condición de excepción en caso de desbordamiento, mientras que Python (desde 2.4) convierte sin problemas la representación interna del número para que coincida con su crecimiento, representándolo eventualmente como long– cuya capacidad solo está limitada por la memoria disponible. [14]
En lenguajes con soporte nativo para aritmética de precisión arbitraria y seguridad de tipos (como Python , Smalltalk o Common Lisp ), los números se promueven a un tamaño mayor automáticamente cuando ocurren desbordamientos o se lanzan excepciones (condiciones señaladas) cuando existe una restricción de rango. El uso de dichos lenguajes puede ser útil para mitigar este problema. Sin embargo, en algunos de estos lenguajes, aún son posibles situaciones en las que puede ocurrir un desbordamiento de enteros. Un ejemplo es la optimización explícita de una ruta de código que el generador de perfiles considera un cuello de botella. En el caso de Common Lisp , esto es posible mediante el uso de una declaración explícita para anotar el tipo de una variable en una palabra del tamaño de una máquina (fixnum) [15] y reducir el nivel de seguridad de tipos a cero [16] para un bloque de código en particular. [17] [18] [19] [20]
En marcado contraste con lenguajes más antiguos como C, algunos lenguajes más nuevos como Rust proporcionan funciones integradas que permiten una fácil detección y elección del usuario sobre cómo se debe manejar el desbordamiento caso por caso. En Rust, si bien el uso de operadores matemáticos básicos naturalmente carece de tal flexibilidad, los usuarios pueden realizar cálculos de manera alternativa a través de un conjunto de métodos proporcionados por cada uno de los tipos primitivos de números enteros. Estos métodos brindan a los usuarios varias opciones entre realizar una operación verificada (o de desbordamiento ) (que indica si se produjo o no un desbordamiento a través del tipo de retorno); una operación "sin verificar"; una operación que realiza un ajuste o una operación que realiza una saturación en los límites numéricos.
En gráficos de computadora o procesamiento de señales , es típico trabajar con datos que van de 0 a 1 o de −1 a 1. Por ejemplo, tome una imagen en escala de grises donde 0 representa negro, 1 representa blanco y los valores intermedios representan tonos de gris. Una operación que uno puede querer soportar es iluminar la imagen multiplicando cada píxel por una constante. La aritmética saturada permite simplemente multiplicar ciegamente cada píxel por esa constante sin preocuparse por el desbordamiento simplemente apegándose a un resultado razonable de que todos estos píxeles más grandes que 1 (es decir, "más brillantes que el blanco" ) simplemente se vuelvan blancos y todos los valores "más oscuros que el negro" simplemente se vuelvan negros.
El desbordamiento aritmético imprevisto es una causa bastante común de errores de programación . Estos errores de desbordamiento pueden ser difíciles de descubrir y diagnosticar porque pueden manifestarse solo para conjuntos de datos de entrada muy grandes, que tienen menos probabilidades de usarse en pruebas de validación.
Tomar la media aritmética de dos números sumándolos y dividiéndolos por dos, como se hace en muchos algoritmos de búsqueda , causa un error si la suma (aunque no la media resultante) es demasiado grande para ser representada y, por lo tanto, se desborda. [21]
Entre 1985 y 1987, el desbordamiento aritmético de las máquinas de radioterapia Therac-25 , junto con la falta de controles de seguridad del hardware, provocó la muerte de al menos seis personas por sobredosis de radiación. [22]
Un desbordamiento aritmético no controlado en el software de dirección del motor fue la causa principal del accidente del vuelo inaugural de 1996 del cohete Ariane 5. [23] El software se había considerado libre de errores ya que se había utilizado en muchos vuelos anteriores, pero en ellos se utilizaron cohetes más pequeños que generaban una aceleración menor que la del Ariane 5. Frustrantemente, la parte del software en la que se produjo el error de desbordamiento ni siquiera era necesario que estuviera en ejecución para el Ariane 5 en el momento en que causó la falla del cohete: era un proceso de régimen de lanzamiento para un predecesor más pequeño del Ariane 5 que había permanecido en el software cuando se adaptó para el nuevo cohete. Además, la verdadera causa del fallo fue una falla en la especificación de ingeniería de cómo el software manejaba el desbordamiento cuando se detectaba: hizo un volcado de diagnóstico a su bus, que se habría conectado al equipo de prueba durante las pruebas de software durante el desarrollo, pero estaba conectado a los motores de dirección del cohete durante el vuelo; La descarga de datos empujó la tobera del motor con fuerza hacia un lado, lo que dejó al cohete fuera de control aerodinámico y precipitó su rápida ruptura en el aire. [24]
El 30 de abril de 2015, la Administración Federal de Aviación de los EE. UU. anunció que ordenaría a los operadores del Boeing 787 que reiniciaran su sistema eléctrico periódicamente, para evitar un desbordamiento de enteros que podría provocar la pérdida de energía eléctrica y el despliegue de la turbina de aire de impacto , y Boeing implementó una actualización de software en el cuarto trimestre. [25] La Agencia Europea de Seguridad Aérea siguió el 4 de mayo de 2015. [26] El error ocurre después de 2 31 centésimas de segundo (aproximadamente 249 días), lo que indica un entero con signo de 32 bits .
Los errores de desbordamiento son evidentes en algunos juegos de computadora. En Super Mario Bros. para NES , el número de vidas almacenado es un byte con signo (que va de −128 a 127), lo que significa que el jugador puede tener 127 vidas de manera segura, pero cuando el jugador llega a su vida número 128, el contador pasa a cero vidas (aunque el contador de números falla antes de que esto suceda) y deja de llevar la cuenta. Como tal, si el jugador muere, el juego termina de inmediato. Esto se debe al desbordamiento de datos del juego, que fue un error de programación, ya que es posible que los desarrolladores no hayan pensado que dicha cantidad de vidas se ganaría razonablemente en una partida completa.
En el juego arcade Donkey Kong , es imposible avanzar más allá del nivel 22 debido a un desbordamiento de enteros en su tiempo/bonificación. El juego calcula el tiempo/bonificación tomando el número de nivel en el que se encuentra un usuario, multiplicándolo por 10 y sumando 40. Cuando alcanzan el nivel 22, el número de tiempo/bonificación es 260, que es demasiado grande para su registro de valor 256 de 8 bits, por lo que se desborda a un valor de 4, demasiado corto para terminar el nivel. En Donkey Kong Jr. Math , al intentar calcular un número superior a 10 000, solo muestra los primeros 4 dígitos. El desbordamiento es la causa del famoso nivel de "pantalla dividida" en Pac-Man . [27] Este error también causó Far Lands en Minecraft Java Edition, que existió desde el período de desarrollo de Infdev hasta Beta 1.7.3; luego se solucionó en Beta 1.8. El mismo error también existía en Minecraft Bedrock Edition, pero desde entonces se ha solucionado. [28]
En el juego Lamborghini American Challenge de Super Nintendo Entertainment System (SNES) , el jugador puede hacer que su cantidad de dinero caiga por debajo de $0 durante una carrera al ser multado por sobre el límite de dinero restante después de pagar la tarifa de una carrera, lo que hace fallar el número entero y le otorga al jugador $65,535,000 más de lo que hubiera tenido después de volverse negativo. [29]
IBM– Microsoft Macro Assembler (MASM) versión 1.00, y probablemente todos los demás programas creados con el mismo compilador Pascal , tenían un error de desbordamiento de entero y de signo en el código de configuración de la pila, lo que impedía que se ejecutaran en máquinas DOS más nuevas o emuladores bajo algunas configuraciones comunes con más de 512 KB de memoria. El programa se bloquea o muestra un mensaje de error y sale al DOS. [30]
En agosto de 2016, una máquina de casino en Resorts World Casino imprimió un boleto de premio de $42,949,672.76 como resultado de un error de desbordamiento. El casino se negó a pagar esta cantidad, calificándolo de mal funcionamiento, y utilizó en su defensa el argumento de que la máquina indicaba claramente que el pago máximo era de $10,000, por lo que cualquier premio que excediera esa cantidad tenía que ser el resultado de un error de programación. La Comisión de Juegos del Estado de Nueva York falló a favor del casino. [31]