En programación de computadoras , un desbordamiento de enteros ocurre cuando una operación aritmética intenta crear un valor numérico que está fuera del rango que se puede representar con un número determinado de dígitos, ya sea mayor que el 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 representables menos significativos del resultado; se dice que el resultado ronda el máximo (es decir, módulo una potencia de la base , generalmente dos en las computadoras modernas, pero a veces diez u otra base).
Una condición de desbordamiento puede dar resultados que conduzcan a un comportamiento no deseado. En particular, si no se ha previsto la posibilidad, el desbordamiento puede comprometer la confiabilidad y seguridad de un programa .
Para algunas aplicaciones, como temporizadores y relojes, puede ser conveniente ajustar el desbordamiento. El estándar C11 establece que para 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]
En algunos procesadores, como las unidades de procesamiento de gráficos (GPU) y los procesadores de señales digitales (DSP), que admiten aritmética de saturación , los resultados desbordados se "fijarían", es decir, se establecerían en el valor mínimo o máximo en el rango representable, en lugar de ajustarse.
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 aritmética de precisión múltiple con operandos en la memoria, lo que permite que los números sean arbitrariamente largos y se evite el desbordamiento, el ancho del registro limita los tamaños de los números con los que se puede operar (por ejemplo, sumar o restar) usando una sola instrucción por operación. Los anchos de registros binarios típicos para 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 ajuste .
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 ajuste a un valor positivo grande (por ejemplo, la suma de enteros de 8 bits 255 + 2 da como resultado 1, lo que es 257 mod 2 8 y, de manera similar, la resta 0 − 1 da como resultado 255, una representación en complemento a dos de −1).
Tal envoltura puede causar perjuicios a la seguridad: si se utiliza un valor desbordado como el número de bytes a asignar para un búfer, el búfer se asignará inesperadamente pequeño, lo que podría provocar un desbordamiento del búfer que, dependiendo del uso del búfer, podría en a su vez provocar 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 enteros puede hacer que el valor se ajuste 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 particular es utilizar tipos enteros sin signo para los 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.
La bandera 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 dado. Esto indica un desbordamiento con un acarreo o préstamo del bit más significativo . Una operación inmediatamente posterior de suma con acarreo o resta con préstamo usaría el contenido de este indicador para modificar un registro o una ubicación de memoria que contiene 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 uno 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 complemento a dos no cabe en el número de bits dado.
Para 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 ajustando, entonces 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 sujeción, entonces este evento se define comúnmente como saturación. El uso varía en cuanto a 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 de números enteros. [4] [5] [6] [7] [8] Cuando se utiliza el término subdesbordamiento de entero, 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. Dependiendo del contexto, la definición de desbordamiento puede incluir todos los tipos, incluidos los desbordamientos insuficientes, o puede incluir solo casos en los que el resultado ideal estuvo 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 número entero exacto, el significado de desbordamiento puede ser ambiguo en casos extremos. Considere el caso en el que 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 que el valor ideal está fuera del rango representable del tipo de salida, entonces este caso se clasificaría como desbordamiento. Para operaciones que tienen un comportamiento de redondeo bien definido, es posible que sea necesario posponer la clasificación de desbordamiento hasta 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 coma flotante 127,25 a un número entero, primero se debe aplicar el redondeo para obtener 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 cuando se produce un desbordamiento puede no ser coherente en todas las circunstancias. Por ejemplo, en el lenguaje Rust , si bien se proporciona funcionalidad para brindar a los usuarios elección 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 "lanzamiento". [9] En C, el desbordamiento de enteros sin signo se define para ajustarse, mientras que el desbordamiento de enteros con signo provoca un comportamiento indefinido .
La implementación de detección de desbordamiento en tiempo de ejecución UBSan( desinfectante de comportamiento indefinido ) está disponible para los compiladores de C.
En Java 8, hay métodos sobrecargados , por ejemplo Math.addExact(int, int), que generará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 el 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 puedan calcularse y almacenarse 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 de manera defensiva con tamaños generosos, ordenando cuidadosamente las operaciones y verificando los operandos por adelantado, a menudo es posible asegurar a priori que el resultado nunca será mayor de 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 produzca un desbordamiento accidentalmente.
Si se prevé que pueda ocurrir un desbordamiento, entonces se pueden insertar pruebas en el programa para detectar cuándo sucede o está a punto de suceder, y realizar otros procesamientos 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 quizás solicitar al usuario una entrada diferente, en lugar de que el programa continúe con la entrada no válida desbordada y probablemente funcione mal como consecuencia.
Las CPU generalmente tienen una forma de detectar esto para admitir 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 de más de un byte: primero agregue los bytes bajos, almacene el resultado y verifique si hay desbordamiento; luego agregue los bytes altos y, si es necesario, agregue el acarreo de los bytes bajos, luego almacene el resultado.
El manejo de un posible desbordamiento de un cálculo a veces puede presentar la opción de realizar una verificación antes de un cálculo (para determinar si se producirá o no un desbordamiento) o después (para considerar si es probable que haya ocurrido o no según el valor resultante). Dado que algunas implementaciones pueden generar una condición de captura en caso de desbordamiento de enteros, la mayoría de los programas portátiles prueban antes de realizar la operación que podría desbordarse.
Si un valor es demasiado grande para almacenarlo, se le puede asignar un valor especial que indique que se ha producido un desbordamiento y luego hacer que todas las operaciones sucesivas devuelvan este valor de indicador. Estos valores a veces se denominan NaN , que significa "no es un número". Esto es útil para que el problema pueda comprobarse una vez al final de un cálculo largo en lugar de después de cada paso. Esto suele ser compatible con hardware de punto flotante llamado FPU .
Los lenguajes de programación implementan varios métodos de mitigación contra un desbordamiento accidental: Ada , Seed7 y ciertas variantes de lenguajes funcionales desencadenan 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, y eventualmente lo representa como long– cuya capacidad sólo 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 se producen desbordamientos o se lanzan excepciones (condiciones señaladas) cuando existe una restricción de rango. Por lo tanto, el uso de dichos lenguajes puede resultar útil para mitigar este problema. Sin embargo, en algunos de estos lenguajes todavía son posibles situaciones en las que puede producirse 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 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 esa flexibilidad, los usuarios pueden realizar cálculos alternativamente a través de un conjunto de métodos proporcionados por cada uno de los tipos primitivos de enteros. Estos métodos brindan a los usuarios varias opciones entre realizar una operación marcada (o desbordada ) (que indica si se produjo o no un desbordamiento mediante el tipo de devolución); una operación "no controlada"; una operación que realiza envoltura o una operación que realiza saturación en los límites numéricos.
En gráficos por computadora o procesamiento de señales , es típico trabajar con datos que varían de 0 a 1 o de −1 a 1. Por ejemplo, tome una imagen en escala de grises donde 0 representa el negro, 1 representa el blanco y los valores intermedios representan sombras. de gris. Una operación que quizás desee admitir es iluminar la imagen multiplicando cada píxel por una constante. La aritmética saturada permite 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 mayores que 1 (es decir, "más brillantes que el blanco" ) simplemente se vuelven blancos y todos los valores "más oscuros que el negro". "Simplemente vuélvete negro.
El desbordamiento aritmético inesperado es una causa bastante común de errores en el programa . Estos errores de desbordamiento pueden ser difíciles de descubrir y diagnosticar porque pueden manifestarse sólo para conjuntos de datos de entrada muy grandes, que es menos probable que se utilicen 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 , provoca 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 en las máquinas de radioterapia Therac-25 , junto con la falta de controles de seguridad del hardware, causaron 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 primer vuelo del cohete Ariane 5 en 1996 . [23] El software se había considerado libre de errores ya que se había utilizado en muchos vuelos anteriores, pero utilizaban cohetes más pequeños que generaban una aceleración menor que el Ariane 5. Es frustrante que la parte del software en la que se produjo el error de desbordamiento ni siquiera estuviera disponible. Se requería que estuviera funcionando para el Ariane 5 en el momento en que provocó que el cohete fallara: 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 de la falla fue una falla en la especificación de ingeniería de cómo el software manejó el desbordamiento cuando fue detectado: hizo un volcado de diagnóstico en su bus, que habría sido 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; el volcado 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 EE. UU . anunció que ordenará a los operadores del Boeing 787 que reinicien su sistema eléctrico periódicamente, para evitar un desbordamiento de enteros que podría provocar una pérdida de energía eléctrica y el despliegue de turbinas de aire , y Boeing implementó una actualización de software en el cuarto trimestre. [25] La Agencia Europea de Seguridad Aérea hizo lo mismo 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 de 32 bits con signo .
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 firmado (que va de −128 a 127), lo que significa que el jugador puede tener 127 vidas de forma segura, pero cuando el jugador alcanza la vida número 128, el contador llega a cero. vive (aunque el contador de números falla antes de que esto suceda) y deja de contar. Como tal, si el jugador muere, el juego termina inmediatamente. 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 se podría ganar dicha cantidad de vidas.
En el juego de arcade Donkey Kong , es imposible avanzar más allá del nivel 22 debido a un desbordamiento de números 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 alcanza el nivel 22, el número de tiempo/bonificación es 260, que es demasiado grande para su 256 de 8 bits. registro de valor, 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 mayor a 10,000, muestra solo los primeros 4 dígitos. El desbordamiento es la causa del famoso nivel de "pantalla dividida" en Pac-Man . [27] Tal 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; Posteriormente se solucionó en Beta 1.8. El mismo error también existía en Minecraft Bedrock Edition, pero ya 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 recibir una multa por exceder el límite de dinero restante después de pagar la tarifa de una carrera, lo que falla en el número entero. y otorga al jugador $65,535,000 más de lo que habría tenido después de volverse negativo. [29]
IBM: Microsoft Macro Assembler (MASM) versión 1.00, y probablemente todos los demás programas creados por el mismo compilador Pascal , tenían un desbordamiento de enteros y un error de firma en el código de configuración de la pila, lo que les impedía ejecutarse en máquinas o emuladores DOS más nuevos bajo algunas condiciones comunes. Configuraciones con más de 512 KB de memoria. El programa se bloquea o muestra un mensaje de error y sale a DOS. [30]
En agosto de 2016, una máquina de casino en el casino Resorts World 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, utilizando en su defensa que la máquina indicaba claramente que el pago máximo era de 10.000 dólares, por lo que cualquier premio que excediera esa cifra tenía que ser el resultado de un error de programación. La Comisión de Juego del Estado de Nueva York falló a favor del casino. [31]