Por qué no es buena idea portar el desbordamiento de enteros

Este artículo se centra en el comportamiento indefinido y las optimizaciones del compilador, especialmente en el contexto del desbordamiento de enteros con signo.

Nota del traductor: en ruso no existe una correspondencia clara en el contexto utilizado de la palabra "wrap" / "wrapping". Hay un término matemático " transferencia ", que está cerca del fenómeno descrito, y el término "bandera de acarreo" es un mecanismo para establecer una bandera en los procesadores durante el desbordamiento de enteros. Otra opción de traducción puede ser la frase "rotación / volteo / revolución alrededor de cero". Refleja mejor el significado de "envoltura" en comparación con "llevar", porque muestra la transición de números cuando se desborda de rango positivo a negativo. Sin embargo, resultó que estas palabras parecen inusuales en el texto para los lectores de prueba. Por simplicidad, en el futuro tomaremos la palabra "transferencia" como una traducción del término "envolver".

Los compiladores del lenguaje C (y C ++) en su trabajo se guían cada vez más por el concepto de comportamiento indefinido : la noción de que el comportamiento de un programa para algunas operaciones no está regulado por el estándar y que, al generar código objeto, el compilador tiene el derecho de proceder desde el supuesto de que el programa no realiza tales operaciones. Muchos programadores se opusieron a este enfoque, ya que el código generado en este caso puede no comportarse como el autor del programa previsto. Este problema se agudiza, ya que los compiladores utilizan métodos de optimización más sofisticados, que probablemente se basarán en el concepto de comportamiento indefinido.

En este contexto, un ejemplo con un desbordamiento de entero con signo es indicativo. La mayoría de los desarrolladores de C escriben código para máquinas que usan código adicional para representar enteros, y la suma y resta en esta representación se implementan exactamente de la misma manera, en aritmética sin signo. Si la suma de dos enteros positivos con un signo se desborda, es decir, se hace más grande de lo que el tipo acomoda, el procesador devolverá un valor que, interpretado como un complemento binario del número con signo, se considerará negativo. Este fenómeno se llama "transferencia", ya que el resultado, después de haber alcanzado el límite superior del rango de valores, se "transfiere" y comienza desde el límite inferior.

Por esta razón, a veces puedes ver este código en C:

int b = a + 1000; if (b < a) { //  puts("input too large!"); return; } 

La tarea de la instrucción if es detectar una condición de desbordamiento (en este caso, ocurre después de agregar 1000 al valor de la variable a ) e informar un error. El problema es que en C, el desbordamiento de enteros con signo es uno de los casos de comportamiento indefinido. Durante algún tiempo, los compiladores siempre han considerado que tales condiciones son falsas: si agrega 1000 (o cualquier otro número positivo) a otro número, el resultado no puede ser inferior al valor inicial. Si se produce un desbordamiento, entonces hay un comportamiento indefinido, y no permitir que esto ya sea (aparentemente) la preocupación del programador. Por lo tanto, el compilador puede decidir que el operador condicional se puede eliminar por completo para fines de optimización (después de todo, la condición siempre es falsa, no afecta nada, por lo que puede prescindir de ella).

El problema es que con esta optimización, el compilador eliminó la verificación que el programador agregó específicamente para detectar comportamientos indefinidos y procesarlos. Aquí puedes ver cómo sucede esto en la práctica. (Nota: ¡el sitio web godbolt.org, que alberga el ejemplo, es genial! Puede editar el código e inmediatamente ver cómo lo procesan los diferentes compiladores, y hay muchos de ellos. ¡Experimente!). Tenga en cuenta que el compilador no elimina la comprobación de desbordamiento si cambia el tipo a sin signo, ya que se define el comportamiento del desbordamiento sin signo en C (más precisamente, el resultado se transfiere con aritmética sin signo, por lo que el desbordamiento no ocurre realmente).

¿Entonces esto está mal? Alguien dice que sí, aunque es obvio que muchos desarrolladores de compiladores consideran legal esta decisión. Si entiendo correctamente, los argumentos principales de los partidarios (edición: dependiente de la implementación) de la transferencia durante el desbordamiento son los siguientes:

• Desbordarse es un comportamiento útil.
• La migración es el comportamiento que los programadores esperan.
• La semántica del comportamiento de desbordamiento indefinido no proporciona una ventaja notable.
• El estándar del lenguaje C para el comportamiento indefinido permite que la implementación "ignore completamente la situación, y el resultado será impredecible", pero esto no le da al compilador el derecho de optimizar el código basado en el supuesto de que la situación con el comportamiento indefinido no ocurre en absoluto.

Analicemos cada elemento por turno:

Migración por desbordamiento: ¿comportamiento útil?

La migración es útil principalmente cuando necesita rastrear un desbordamiento que ya ha ocurrido. (Si hay otros problemas que pueden resolverse mediante transferencia y no pueden resolverse utilizando variables enteras sin signo, no puedo recordar de inmediato tales ejemplos, y sospecho que hay pocos). Si bien la transferencia realmente simplifica el problema de usar variables desbordadas incorrectamente, definitivamente no es una panacea (recuerde la multiplicación o adición de dos cantidades desconocidas con un signo desconocido).

En casos triviales, cuando la transferencia simplemente le permite rastrear el desbordamiento que ha surgido, tampoco es difícil saber de antemano si ocurrirá. Nuestro ejemplo puede reescribirse de la siguiente manera:

 if (a > INT_MAX - 1000) { //    puts("input too large!"); return; } int b = a + 1000; 

Es decir, en lugar de calcular la suma y luego averiguar si se ha producido un desbordamiento o no, verificando la coherencia matemática del resultado, puede verificar si la suma excede el número máximo que se ajusta al tipo. (Si se desconoce el signo de ambos operandos, la verificación tendrá que ser muy complicada, pero lo mismo se aplica a la verificación durante la transferencia).

Dado todo esto, el argumento me parece poco convincente de que la transferencia es útil en la mayoría de los casos.

¿Es la migración el comportamiento que los programadores esperan?

Es más difícil discutir con este argumento, ya que es obvio que el código de al menos algunos programadores de C asume la semántica de transferencia con un desbordamiento de entero con signo. Pero este hecho por sí solo no es suficiente para considerar preferible tal semántica (tenga en cuenta que algunos compiladores le permiten habilitarla si es necesario).

Una solución obvia al problema (los programadores esperan este comportamiento) es hacer que el compilador emita una advertencia cuando optimice el código, suponiendo que no haya un comportamiento indefinido. Desafortunadamente, como vimos en el ejemplo en godbolt.org usando el enlace de arriba, los compiladores no siempre hacen esto (Gcc versión 7.3 - sí, pero versión 8.1 - no, así que hay un paso atrás).

¿La semántica del comportamiento de desbordamiento indefinido no ofrece una ventaja notable?

Si esta observación es cierta en todos los casos, entonces serviría como un fuerte argumento a favor del hecho de que los compiladores deben adherirse a la semántica de transferencia de forma predeterminada, ya que probablemente sería mejor permitir verificaciones de desbordamiento, incluso si este mecanismo es incorrecto desde un punto de vista técnico, aunque sería porque se puede usar en código potencialmente roto.

Supongo que esta optimización (eliminación de comprobaciones de condiciones matemáticamente contradictorias) en los programas normales de C a menudo se puede descuidar, ya que sus autores se esfuerzan por obtener el mejor rendimiento y aún optimizan el código manualmente: es decir, si es obvio que esta declaración contiene una condición , que nunca será cierto, es probable que el programador lo elimine él mismo. De hecho, descubrí que en varios estudios la efectividad de dicha optimización se puso en tela de juicio, se probó y resultó ser prácticamente insignificante en el marco de las pruebas de control. Sin embargo, aunque esta optimización casi nunca ofrece una ventaja en el lenguaje C, los generadores de código y las optimizaciones del compilador son en su mayor parte universales y pueden usarse en otros lenguajes, y para ellos esta conclusión puede ser incorrecta. Tomemos el lenguaje C ++ con su, digamos, tradición de confiar en el optimizador para eliminar construcciones redundantes en el código de la plantilla, en lugar de hacerlo manualmente. Pero hay lenguajes que el transportador convierte a C, y el código redundante en ellos también está optimizado por los compiladores de C.

Además, incluso si sigue buscando desbordamientos, no es un hecho que el costo directo de transferir variables enteras sea mínimo, incluso en máquinas que usan código adicional. La arquitectura Mips, por ejemplo, solo puede realizar operaciones aritméticas en registros de un tamaño fijo (32 bits). El tipo short int , como regla, tiene un tamaño de 16 bits y char - 8 bits; cuando una variable de uno de estos tipos se almacena en el registro, su tamaño se expandirá y, para transferirla correctamente, será necesario realizar al menos una operación adicional y, posiblemente, usar un registro adicional (para acomodar la máscara de bits correspondiente). Tengo que admitir que no he tratado con el código de Mips durante mucho tiempo, por lo que no estoy seguro sobre el costo exacto de estas operaciones, pero estoy seguro de que no es cero y que los mismos problemas pueden ocurrir en otras arquitecturas RISC.

¿Un estándar de lenguaje prohíbe evitar la envoltura de variables si está diseñado por la arquitectura?

Si nos fijamos, este argumento es especialmente débil. Su esencia es que el estándar supuestamente permite que la implementación (compilador) interprete el "comportamiento indefinido" solo de forma limitada. En el texto de la norma en sí, en ese fragmento al que apelan los defensores de la transferencia, se dice lo siguiente (esto es parte de la definición del término "comportamiento indefinido"):

NOTA: El comportamiento indefinido puede tomar la forma de ignorar completamente la situación, mientras que el resultado será impredecible, ...

La idea es que las palabras "ignorar completamente la situación" no sugieren que un evento que conduzca a un comportamiento indefinido, por ejemplo, desbordamiento durante la adición, no puede ocurrir, sino que si lo hace, el compilador debería continuar trabajando como si que nunca sucedió, pero también tenga en cuenta el resultado que resultará si le envía al procesador una solicitud para realizar dicha operación (en otras palabras, como si el código fuente se tradujera al código de la máquina de una manera directa e ingenua).

En primer lugar, debe tenerse en cuenta que este texto se proporciona como una "nota" y, por lo tanto, no es normativo (es decir, no puede prescribir algo), de acuerdo con la directiva ISO mencionada en la introducción a la norma:

De acuerdo con la Parte 3 de las Directivas ISO / IEC, este prefacio, introducción al texto, notas, notas al pie y ejemplos también son solo para fines informativos.

Dado que este pasaje de "comportamiento indefinido" es una nota, no prescribe nada. Tenga en cuenta que la definición actual de "comportamiento indefinido" es:

comportamiento derivado del uso de un diseño de software intolerable o incorrecto o datos incorrectos, a los cuales esta Norma Internacional no impone ningún requisito .

Destaqué la idea principal: no se imponen requisitos sobre el comportamiento indefinido; La lista de "posibles tipos de comportamiento indefinido" en la nota contiene solo ejemplos y no puede ser la receta final. La frase "no exige nada" no puede interpretarse de otra manera.

Algunos, al desarrollar este argumento, argumentan que, independientemente del texto, el comité de lenguaje, cuando formuló estas palabras, significaba que el comportamiento en su conjunto debería corresponder a la arquitectura del hardware en el que se ejecuta el programa, lo más posible, lo que implica una traducción ingenua en código de máquina. Esto puede ser cierto, aunque no he visto ninguna evidencia (por ejemplo, documentos históricos) en apoyo de este argumento. Sin embargo, incluso si esto fuera así, no es un hecho que esta declaración se aplique a la versión actual del texto.

Últimos pensamientos

Los argumentos a favor de la transferencia son en gran medida insostenibles. Quizás el argumento más sólido se obtenga si los combinamos: los programadores menos experimentados (que no conocen las complejidades del lenguaje C y el comportamiento indefinido en él) a veces esperan transferencia, y no reduce el rendimiento, aunque este último no es cierto en todos los casos, y la primera parte no es concluyente si lo consideras por separado.

Personalmente, preferiría que los desbordamientos se bloqueen (atrapando) en lugar de envolver. Es decir, para que el programa se bloquee y no continúe funcionando, con un comportamiento incierto o resultados potencialmente incorrectos, porque en ambos casos aparece una vulnerabilidad. Tal solución, por supuesto, reducirá ligeramente el rendimiento en la mayoría de las arquitecturas (?), Especialmente en x86, pero, por otro lado, los errores de desbordamiento se identificarán de inmediato y no podrán aprovecharlos ni obtener resultados incorrectos al usarlos en el camino programas Además, en teoría, los compiladores con este enfoque podrían eliminar de forma segura las comprobaciones de desbordamiento redundantes, ya que ciertamente no sucederá, aunque, como veo, ni Clang ni GCC aprovechan esta oportunidad.

Afortunadamente, tanto la interrupción como la transferencia se implementan en el compilador que uso con más frecuencia es GCC. Para cambiar entre modos, se utilizan los argumentos de línea de comando -ftrapv y -fwrapv , respectivamente.

Por supuesto, hay muchas acciones que conducen a un comportamiento indefinido: el desbordamiento de enteros es solo una de ellas. No creo en absoluto que sea útil interpretar todos estos casos como comportamiento indefinido, y estoy seguro de que hay muchas situaciones específicas en las que la semántica debe determinarse por el lenguaje o, al menos, dejarse a discreción de las implementaciones. Y me temo que los fabricantes de compiladores interpretan de manera demasiado libre este concepto: si el comportamiento del compilador no cumple con las ideas intuitivas de los desarrolladores, especialmente aquellos que leen personalmente el texto del estándar, esto puede conducir a errores reales; Si la ganancia de rendimiento en este caso es insignificante, es mejor abandonar tales interpretaciones. En una de las siguientes publicaciones, probablemente analizaré algunos de estos problemas.

Suplemento (del 24 de agosto de 2018)

Me di cuenta de que gran parte de lo anterior podría escribirse mejor. A continuación resumo y explico brevemente mis palabras y agrego algunas observaciones menores:

• No sostuve que el comportamiento indefinido sea preferible al desbordamiento, sino que, en la práctica, la transferencia no es mucho mejor que el comportamiento indefinido. En particular, se pueden obtener problemas de seguridad en el primer caso y en el segundo, y apuesto a que muchas de las vulnerabilidades causadas por desbordamientos que no se detectaron a tiempo (excepto aquellas de las cuales el compilador es responsable de eliminar las comprobaciones erróneas) en realidad provienen de - debido a la transferencia del resultado, pero no debido al comportamiento indefinido asociado con el desbordamiento.
• La única ventaja real de la transferencia es que no se eliminan las comprobaciones de desbordamiento. Aunque de esta manera puede proteger el código de algunos escenarios de ataque, es probable que algunos de los desbordamientos no se verifiquen en absoluto (es decir, el programador se olvidará de agregar dicha verificación) y pasarán desapercibidos.
• Si el problema de seguridad no es tan importante, y la alta velocidad del programa se destaca, entonces el comportamiento indefinido dará una optimización más rentable y un mayor aumento de la productividad, al menos en algunos casos. Por otro lado, si la seguridad es lo primero, la portabilidad está llena de vulnerabilidades.
• Esto significa que si elige entre interrupción, transferencia y comportamiento indefinido, hay muy pocas tareas en las que la transferencia puede ser útil.
• En cuanto a las comprobaciones del desbordamiento que se ha producido, creo que dejarlas es perjudicial, porque crea la falsa impresión de que funcionan y siempre funcionarán. Interrumpir los desbordamientos evita este problema; advertencias adecuadas: mitigarlo.
• Creo que cualquier desarrollador que escriba código crítico para la seguridad idealmente debería tener un buen dominio de la semántica del lenguaje en el que escribe, así como ser consciente de sus dificultades. Para C, esto significa que necesita conocer la semántica del desbordamiento y las sutilezas del comportamiento indefinido. Es triste que algunos programadores no hayan crecido a este nivel.
• Me he encontrado con la afirmación de que "la mayoría de los programadores de C esperan la migración como el comportamiento predeterminado", pero no conozco la evidencia de esto. (En el artículo, escribí "algunos programadores", porque conozco varios ejemplos de la vida real, y en general dudo que alguien discuta esto).
• Hay dos problemas diferentes: qué requiere el estándar del lenguaje C y qué compiladores deberían implementar. (Generalmente) me gusta la forma en que el estándar define el comportamiento de desbordamiento indefinido. En esta publicación, hablo sobre lo que deberían hacer los compiladores.
• Cuando se interrumpe el desbordamiento, no hay necesidad de verificar cada operación. Idealmente, el programa con este enfoque se comporta de manera consistente en términos de reglas matemáticas o deja de funcionar. En este caso, la existencia de un "desbordamiento temporal" se hace posible, lo que no conduce a la aparición de un resultado incorrecto. Entonces, tanto la expresión a + b - b como la expresión (a * b) / b se pueden optimizar a a (la primera también es posible durante la transferencia, pero la segunda ya no está presente).

Nota La traducción del artículo se publica en el blog con el permiso del autor. Texto original: Davin McCall " Ajustar el desbordamiento de enteros no es una buena idea ".

Enlaces relacionados adicionales del equipo PVS-Studio:

1. Andrey Karpov. El comportamiento indefinido está más cerca de lo que piensas .
2. Will Dietz, Peng Li, John Regehr y Vikram Adve. Comprender el desbordamiento de enteros en C / C ++ .
3. V1026. La variable se incrementa en el bucle. Se producirá un comportamiento indefinido en caso de desbordamiento de entero con signo .
4. Stackoverflow ¿El desbordamiento de entero con signo sigue siendo un comportamiento indefinido en C ++?