Desbordamiento de enteros - Integer overflow

El desbordamiento de enteros se puede demostrar a través del desbordamiento de un odómetro , una versión mecánica del fenómeno. Todos los dígitos se establecen en el máximo de 9 y el siguiente incremento del dígito blanco provoca una cascada de adiciones transferidas que configuran todos los dígitos en 0, pero no hay un dígito más alto (dígito de 1,000,000) para cambiar a 1, por lo que el contador se restablece a cero. Esto es envolver en contraste con saturar .

En la programación de computadoras , se produce un desbordamiento de enteros 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 más alto que el máximo o más bajo 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 se ajusta al máximo (es decir, módulo a potencia de la base , generalmente dos en las computadoras modernas, pero a veces diez u otra base).

Una condición de desbordamiento puede dar como resultado un comportamiento no deseado. En particular, si no se ha anticipado la posibilidad, el desbordamiento puede comprometer la confiabilidad y seguridad de un programa .

Para algunas aplicaciones, como temporizadores y relojes, puede ser deseable envolver en 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 involucre operandos sin signo nunca puede desbordarse".

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 "limitarían", es decir, se establecerían en el valor mínimo o máximo en el rango representable, en lugar de envolverlos.

Origen

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 la memoria, lo que permite que los números sean arbitrariamente largos y se evite el desbordamiento, el ancho del registro limita el tamaño de los números que se pueden operar (por ejemplo, sumar o restar) usando un instrucción única por operación. Los anchos de registro binario típicos para enteros sin signo incluyen:

  • 4 bits: valor máximo representable 2 4 - 1 = 15
  • 8 bits: valor máximo representable 2 8 - 1 = 255
  • 16 bits: valor máximo representable 2 16 - 1 = 65.535
  • 32 bits: valor máximo representable 2 32 - 1 = 4.294.967.295 (el ancho más común para computadoras personales a partir de 2005),
  • 64 bits: valor máximo representable 2 64 - 1 = 18,446,744,073,709,551,615 (el ancho más común para CPU de computadoras personales , a partir de 2017),
  • 128 bits: valor máximo representable 2 128 - 1 = 340.282.366.920.938.463.463.374.607.431.768.211.455

Cuando una operación aritmética produce un resultado mayor que el máximo anteriormente para un número entero de N bits, un desbordamiento reduce el resultado al modulo N-ésima potencia de 2, reteniendo sólo los bits menos significativos del resultado y causando efectivamente una envoltura alrededor .

En particular, multiplicar o sumar dos enteros puede resultar en un valor inesperadamente pequeño, y restar de un entero pequeño puede causar un ajuste a un valor positivo grande (por ejemplo, la suma de un 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 en complemento a dos de −1).

Tal envoltura puede causar detrimentos de seguridad: si se usa un valor desbordado como el número de bytes para asignar para un búfer, el búfer se asignará inesperadamente pequeño, lo que podría provocar un desbordamiento del búfer que, según el uso del búfer, podría en a su vez causa la ejecución de código arbitrario.

Si la variable tiene un tipo de entero con signo , un programa puede suponer que una variable siempre contiene un valor positivo. Un desbordamiento de entero puede hacer que el valor se ajuste y se vuelva negativo, lo que viola la suposición del programa y puede conducir a un comportamiento inesperado (por ejemplo, la suma de un entero 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 usar tipos enteros sin signo para valores que un programa espera y supone que nunca serán negativos).

Banderas

La mayoría de las computadoras tienen dos indicadores de procesador dedicados para verificar las 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 encaja 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 de suma con acarreo o resta con prestado inmediatamente siguiente usaría el contenido de esta bandera para modificar un registro o una ubicación de memoria que contiene la parte más alta de un valor de varias palabras.

La bandera de desbordamiento se establece cuando el resultado de una operación en números con signo no tiene el signo que uno predeciría 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 el resultado con signo representado en forma de complemento a dos no encajaría en el número dado de bits.

Variaciones de definición y ambigüedad

Para un tipo sin firmar, cuando el resultado ideal de una operación está fuera del rango representable del tipo y el resultado devuelto se obtiene mediante un ajuste, 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 involucre operandos sin firmar nunca puede desbordarse".

Cuando el resultado ideal de una operación de entero está fuera del rango representable del tipo y el resultado devuelto se obtiene mediante sujeció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 de envoltura y desbordamiento de saturación.

El término subdesbordamiento se usa más comúnmente para matemáticas de punto flotante y no para matemáticas enteras. Pero, se pueden encontrar muchas referencias al subdesbordamiento de enteros. Cuando se utiliza el término subdesbordamiento de enteros, significa que el resultado ideal estaba más cerca de menos infinito que el valor representable del tipo de salida más cercano a menos infinito. Cuando se utiliza el término subdesbordamiento de enteros, la definición de desbordamiento puede incluir todos los tipos de desbordamientos o solo puede incluir 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 los casos extremos. Considere el caso en el que el resultado ideal tiene el valor 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, 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 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 en un número entero, entonces se debe aplicar el redondeo primero para obtener una salida de número entero ideal de 127. Dado que el número entero redondeado está en el rango de salidas, el estándar C no clasificaría esta conversión como un desbordamiento. .

Comportamiento inconsistente

Vale la pena señalar que el comportamiento ante la ocurrencia de un desbordamiento puede no ser consistente en todas las circunstancias. En el lenguaje de programación Rust, por ejemplo, mientras que la funcionalidad se proporciona 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 integrado en modo 'depuración' y uno integrado en modo 'lanzamiento'. En C, el desbordamiento de enteros sin signo se define para envolver, mientras que el desbordamiento de enteros con signo provoca un comportamiento indefinido .

Métodos para abordar problemas de desbordamiento de enteros

Manejo de desbordamiento de enteros en varios lenguajes de programación
Idioma Entero sin signo Entero con signo
Ada módulo el módulo del tipo elevar Constraint_Error
C / C ++ módulo de potencia de dos comportamiento indefinido
C# módulo de potencia de 2 en contexto no verificado; System.OverflowExceptionse plantea en contexto comprobado
Java N / A módulo de potencia de dos
JavaScript todos los números son de punto flotante de doble precisión, excepto el nuevo BigInt
MATLAB Los enteros incorporados se saturan. Enteros de punto fijo configurables para envolver o saturar
Python 2 N / A convertir a tipo largo (bigint)
Semilla7 N / A aumentar OVERFLOW_ERROR
Esquema N / A convertir a bigNum
Simulink configurable para envolver o saturar
Charla N / A convertir a LargeInteger
Rápido Provoca errores a menos que se utilicen operadores de desbordamiento especiales.

Detección

En tiempo de ejecución aplicación de detección de desbordamiento UBSanestá disponible para los compiladores C .

En Java 8, hay métodos sobrecargados , por ejemplo Math.addExact(int, int), como , que se lanzarán ArithmeticExceptionen caso de desbordamiento.

El equipo de respuesta a emergencias informáticas (CERT) desarrolló el modelo de enteros As-if Infinitely Ranged (AIR), un mecanismo en gran parte automatizado para eliminar el desbordamiento y el truncamiento de enteros en C / C ++ mediante el manejo de errores en tiempo de ejecución.

Evitación

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 de programación o un entorno 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 con anticipación, a menudo es posible garantizar 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 de forma más segura y sólida que no se produzca un desbordamiento accidental.

Manejo

Si se anticipa que puede ocurrir un desbordamiento, entonces se pueden insertar pruebas en el programa para detectar cuándo sucede, o está a punto de ocurrir, y hacer otro procesamiento 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 desbordada no válida y probablemente funcione mal como consecuencia. Este proceso completo se puede automatizar: es posible sintetizar automáticamente un controlador para un desbordamiento de enteros, donde el controlador es, por ejemplo, una salida limpia.

Las CPU generalmente tienen una forma de detectar esto para admitir la adición de números más grandes que su tamaño de registro, generalmente usando un bit de estado; la técnica se llama aritmética de precisión múltiple. Por lo tanto, es posible agregar dos números cada dos bytes de ancho usando solo una adición de bytes en pasos: primero agregue los bytes bajos y luego agregue los bytes altos, pero si es necesario llevar a cabo los bytes bajos, esto es un desbordamiento aritmético del adición de bytes y se hace necesario detectar e incrementar la suma de los bytes altos.

Manejar el posible desbordamiento de un cálculo a veces puede presentar una opción entre realizar una verificación antes del cálculo real (para determinar si se producirá o no un desbordamiento), o después (para considerar si es probable que haya ocurrido o no en función del valor resultante). . Se debe tener cuidado con la última opción. En primer lugar, dado que puede no ser un método de detección confiable (por ejemplo, una adición no necesariamente se ajusta a un valor más bajo). En segundo lugar, porque la aparición de un desbordamiento en sí mismo puede ser en algunos casos un comportamiento indefinido . En el lenguaje de programación C, el desbordamiento de tipos de enteros sin signo resulta en un ajuste, sin embargo, el desbordamiento de tipos de enteros con signo es un comportamiento indefinido; en consecuencia, un compilador de C es libre de asumir que el programador se ha asegurado de que no se pueda producir un desbordamiento firmado y, por lo tanto, puede optimizar silenciosamente cualquier verificación posterior al cálculo que implique verificar el resultado para detectarlo sin advertir al programador de que esto ha sido hecho. Por lo tanto, es aconsejable preferir siempre implementar las verificaciones antes que los cálculos y no después de ellos.

Propagación explícita

si un valor es demasiado grande para ser almacenado, 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 bandera. A veces, estos valores se denominan NaN , que significa "no es un número". Esto es útil para que el problema se pueda verificar una vez al final de un cálculo largo en lugar de después de cada paso. Esto a menudo se admite en hardware de punto flotante llamado FPU .

Soporte de lenguaje de programación

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 el desbordamiento, mientras que Python (desde 2.4) convierte sin problemas la representación interna del número para que coincida con su crecimiento, eventualmente representando it as long- cuya capacidad sólo está limitada por la memoria disponible.

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. 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 el tipo de una variable en una palabra del tamaño de una máquina (fixnum) y reducir el nivel de seguridad del tipo a cero para un bloque de código en particular.

En marcado contraste con los lenguajes más antiguos como C, algunos lenguajes más nuevos, como Rust, por ejemplo, proporcionan una funcionalidad incorporada que permite una fácil detección y elección del usuario sobre cómo se debe manejar el desbordamiento caso por caso. En Rust, aunque el uso de operadores matemáticos básicos naturalmente carece de tal 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 enteros. Estos métodos brindan a los usuarios varias opciones entre realizar una operación 'comprobada' (o 'desbordada') (que indica si se produjo o no un desbordamiento a través del tipo de retorno); una operación 'sin control'; una operación que realiza el ajuste, o una operación que realiza la saturación en los límites numéricos.

Aritmética saturada

En gráficos por 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 sombras de gris. Una operación que uno puede querer apoyar 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 con solo ceñirse 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 vuelven blancos y todos los valores "más oscuros que el negro" "Simplemente conviértete en negro.

Ejemplos de

El desbordamiento aritmético imprevisto es una causa bastante común de errores de programa . 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 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 , genera un error si la suma (aunque no la media resultante) es demasiado grande para ser representada y, por lo tanto, se desborda.

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 . El software se consideraba libre de errores ya que se había utilizado en muchos vuelos anteriores, pero los que usaban cohetes más pequeños que generaban una aceleración menor que Ariane 5. Frustrantemente, la parte del software en la que se produjo el error de desbordamiento ni siquiera fue requerida para ser funcionando para el Ariane 5 en el momento en que hizo 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 causa real 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 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; el volcado de datos empujó la boquilla del motor hacia un lado, lo que hizo que el cohete fuera del control aerodinámico y precipitó su rápida ruptura en el aire.

El 30 de abril de 2015, la Autoridad Federal de Aviación de EE. UU. Anunció que ordenará a los operadores de Boeing 787 que reinicien 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 ram , y Boeing implementó una actualización de software en el cuarto trimestre. La Agencia Europea de Seguridad Aérea siguió el 4 de mayo de 2015. El error ocurre después de 2³¹ centisegundos (248.55134814815 días), lo que indica una de 32 bits firmado entero .

Los errores de desbordamiento son evidentes en algunos juegos de computadora. En el juego de 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 toma el número de nivel en el que se encuentra un usuario, lo multiplica por 10 y agrega 40. Cuando alcanzan el nivel 22, el número de tiempo / bonificación es 260, que es demasiado grande para su registro de valor de 256 bits de 8 bits, por lo que se reinicia. a 0 y da los 4 restantes como tiempo / bonificación - demasiado corto para terminar el nivel. En Donkey Kong Jr. Math , cuando se trata de calcular un número superior a 10,000, solo muestra los primeros 4 dígitos. Overflow es la causa del famoso nivel de "pantalla dividida" en Pac-Man . El notorio error Nuclear Gandhi en Civilization fue supuestamente causado por un subdesbordamiento de enteros que ocurrió cuando el juego intentó restar 2 del nivel de agresión predeterminado de Gandhi de 1, configurándolo en 255, casi 26 veces más alto que el máximo normal de 10. ( Sid Meier afirmó en una entrevista que esto fue, de hecho, intencional.) Tal error también causó las "Tierras Lejanas" en Minecraft que existieron desde el período de desarrollo de Infdev hasta Beta 1.7.3; Más tarde se corrigió en Beta 1.8, pero todavía existe en las versiones Pocket Edition y Windows 10 Edition de Minecraft . En el juego Super NES Lamborghini American Challenge , el jugador puede hacer que su cantidad de dinero caiga por debajo de $ 0 durante una carrera al ser multado por encima del límite de dinero restante después de pagar la tarifa de una carrera, lo que falla en el número entero y le otorga al jugador $ 65,535,000. más de lo que hubiera tenido después de volverse negativo. Un error similar ocurre en STALKER: Clear Sky, donde el jugador puede caer en una cantidad negativa viajando rápidamente sin fondos suficientes, luego procede al evento en el que el jugador es robado y se le quita toda su moneda. Después de que el juego intenta quitarle el dinero del jugador a una cantidad de $ 0, se le otorga 2147482963 en la moneda del juego.

En la estructura de datos de Pokémon en los juegos de Pokémon, la cantidad de puntos de experiencia obtenidos se almacena en un número entero de 3 bytes. Sin embargo, en la primera y segunda generación, se calcula que el grupo de experiencia medio lento, que requiere 1.059.860 puntos de experiencia para alcanzar el nivel 100, tiene -54 puntos de experiencia en el nivel 1 (un nivel que no se suele encontrar durante el juego normal). Debido a que el número entero no está firmado, el valor se convierte en 16.777.162. Si el Pokémon obtiene menos de 54 puntos de experiencia en una batalla, entonces el Pokémon saltará instantáneamente al nivel 100.

Un error de firma de enteros en el código de configuración de la pila emitido por el compilador Pascal impidió que Microsoft / IBM MACRO Assembler Versión 1.00 (MASM), un programa DOS de 1981, y muchos otros programas compilados con el mismo compilador, se ejecutaran en algunas configuraciones con más de 512 KB de memoria.

Microsoft / IBM Macro Assembler (MASM) Versión 1.00, y probablemente todos los demás programas construidos 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 impedía que se ejecutaran en máquinas DOS más nuevas o emuladores en algunos sistemas comunes. configuraciones con más de 512 KB de memoria. El programa se cuelga o muestra un mensaje de error y sale a DOS.

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ándola de mal funcionamiento, utilizando en su defensa que la máquina indicaba claramente que el pago máximo era de $ 10,000, por lo que cualquier premio que exceda eso tenía que ser el resultado de un error de programación. La Corte Suprema de Iowa falló a favor del casino.

Ver también

Referencias

enlaces externos