c++ c undefined-behavior signed integer-overflow

Detectando desbordamiento firmado en C/C++



undefined-behavior signed (12)

A primera vista, esta pregunta puede parecer un duplicado de Cómo detectar el desbordamiento de enteros? Sin embargo, en realidad es significativamente diferente.

Descubrí que aunque detectar un desbordamiento de enteros sin signo es bastante trivial, detectar un desbordamiento firmado en C / C ++ es realmente más difícil de lo que la mayoría de la gente piensa.

La forma más obvia, aunque ingenua, de hacerlo sería algo así como:

int add(int lhs, int rhs) { int sum = lhs + rhs; if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) { /* an overflow has occurred */ abort(); } return sum; }

El problema con esto es que de acuerdo con el estándar C, el desbordamiento de entero con signo es un comportamiento indefinido. En otras palabras, de acuerdo con el estándar, tan pronto como incluso causa un desbordamiento firmado, su programa es tan inválido como si hubiera desreferenciado un puntero nulo. Por lo tanto, no puede causar un comportamiento indefinido, y luego tratar de detectar el desbordamiento después del hecho, como en el ejemplo de verificación posterior a la condición anterior.

Aunque es probable que la verificación anterior funcione en muchos compiladores, no puede contar con ella. De hecho, dado que el estándar C dice que el desbordamiento de entero con signo no está definido, algunos compiladores (como GCC) optimizarán la verificación anterior cuando se establecen los indicadores de optimización, porque el compilador supone que un desbordamiento firmado es imposible. Esto rompe totalmente el intento de controlar el desbordamiento.

Entonces, otra forma posible de verificar el desbordamiento sería:

int add(int lhs, int rhs) { if (lhs >= 0 && rhs >= 0) { if (INT_MAX - lhs <= rhs) { /* overflow has occurred */ abort(); } } else if (lhs < 0 && rhs < 0) { if (lhs <= INT_MIN - rhs) { /* overflow has occurred */ abort(); } } return lhs + rhs; }

Esto parece más prometedor, ya que en realidad no agregamos los dos enteros juntos hasta que nos aseguramos de antemano que la realización de dicho complemento no dará lugar a un desbordamiento. Por lo tanto, no causamos ningún comportamiento indefinido.

Sin embargo, desafortunadamente, esta solución es mucho menos eficiente que la solución inicial, ya que debe realizar una operación de resta solo para probar si su operación de adición funcionará. E incluso si no te importa este golpe de rendimiento (pequeño), todavía no estoy del todo convencido de que esta solución sea adecuada. La expresión lhs <= INT_MIN - rhs parece exactamente el tipo de expresión que el compilador podría optimizar, pensando que el desbordamiento firmado es imposible.

Entonces, ¿hay una mejor solución aquí? Algo que está garantizado para 1) no causar un comportamiento indefinido, y 2) no proporcionar al compilador la oportunidad de optimizar los controles de desbordamiento de distancia? Estaba pensando que podría haber alguna manera de hacerlo lanzando los dos operandos a unsigned, y realizando verificaciones haciendo rodar su propia aritmética de complemento de dos, pero no estoy muy seguro de cómo hacerlo.

Creo que esto funciona:

int add(int lhs, int rhs) { volatile int sum = lhs + rhs; if (lhs != (sum - rhs) ) { /* overflow */ //errno = ERANGE; abort(); } return sum; }

El uso de volátiles evita que el compilador optimice la prueba porque cree que esa sum puede haber cambiado entre la suma y la resta.

Usando gcc 4.4.3 para x86_64, el ensamblaje de este código realiza la suma, la resta y la prueba, aunque almacena todo en la pila y las operaciones de pila innecesarias. Incluso intenté register volatile int sum = pero el montaje fue el mismo.

Para una versión con solo int sum = (no volátil o registro) la función no hizo la prueba e hizo la adición usando solo una instrucción lea ( lea es Load Effective Address y se usa a menudo para hacer una adición sin tocar el registro de indicadores).

Su versión es un código más grande y tiene muchos más saltos, pero no sé cuál sería mejor .

En caso de agregar dos valores long , el código portátil puede dividir el valor long en partes bajas y altas (o en partes short en caso de que el long tenga el mismo tamaño que int ):

static_assert(sizeof(long) == 2*sizeof(int), ""); long a, b; int ai[2] = {int(a), int(a >> (8*sizeof(int)))}; int bi[2] = {int(b), int(b >> (8*sizeof(int))}); ... use the ''long'' type to add the elements of ''ai'' and ''bi''

El uso del ensamblaje en línea es la manera más rápida si se dirige a una CPU en particular:

long a, b; bool overflow; #ifdef __amd64__ asm ( "addq %2, %0; seto %1" : "+r" (a), "=ro" (overflow) : "ro" (b) ); #else #error "unsupported CPU" #endif if(overflow) ... // The result is stored in variable ''a''

En mi humilde opinión, la forma más oriental de lidiar con el código de C ++ sentsitive de desbordamiento es utilizar SafeInt<T> . Esta es una plantilla de C ++ multiplataforma hospedada en código plex que proporciona las garantías de seguridad que usted desea aquí.

Me parece muy intuitivo de usar, ya que proporciona muchos de los mismos patrones de uso que las opertaciones numéricas normales y expresa los flujos superiores e inferiores a través de excepciones.

La manera más rápida posible es usar el GLC incorporado:

int add(int lhs, int rhs) { int sum; if (__builtin_add_overflow(lhs, rhs, &sum)) abort(); return sum; }

En x86, GCC compila esto en:

mov %edi, %eax add %esi, %eax jo call_abort ret call_abort: call abort

que usa la detección de desbordamiento incorporada del procesador.

Si no está de acuerdo con el uso de interfaces internas de GCC, la siguiente forma más rápida es usar operaciones de bits en los bits de signo. El desbordamiento firmado además ocurre cuando:

  • los dos operandos tienen el mismo signo, y
  • el resultado tiene un signo diferente que los operandos.

El bit de signo de ~(lhs ^ rhs) está activado si los operandos tienen el mismo signo, y el bit de signo de lhs ^ sum está activado si el resultado tiene un signo diferente al de los operandos. Entonces puede hacer la suma en forma sin firmar para evitar el comportamiento indefinido, y luego usar el bit de signo de ~(lhs ^ rhs) & (lhs ^ sum) :

int add(int lhs, int rhs) { unsigned sum = (unsigned) lhs + (unsigned) rhs; if ((~(lhs ^ rhs) & (lhs ^ sum)) & 0x80000000) abort(); return (int) sum; }

Esto se compila en:

lea (%rsi,%rdi), %eax xor %edi, %esi not %esi xor %eax, %edi test %edi, %esi js call_abort ret call_abort: call abort

que es bastante más rápido que la conversión a un tipo de 64 bits en una máquina de 32 bits (con gcc):

push %ebx mov 12(%esp), %ecx mov 8(%esp), %eax mov %ecx, %ebx sar $31, %ebx clt add %ecx, %eax adc %ebx, %edx mov %eax, %ecx add $-2147483648, %ecx mov %edx, %ebx adc $0, %ebx cmp $0, %ebx ja call_abort pop %ebx ret call_abort: call abort

La solución obvia es convertir a unsigned, para obtener el comportamiento de desbordamiento sin firmar bien definido:

int add(int lhs, int rhs) { int sum = (unsigned)lhs + (unsigned)rhs; if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) { /* an overflow has occurred */ abort(); } return sum; }

Esto reemplaza el comportamiento de desbordamiento firmado indefinido con la conversión definida por la implementación de valores fuera de rango entre firmado y sin firmar, por lo que debe verificar la documentación de su compilador para saber exactamente qué sucederá, pero al menos debe estar bien definido, y debería hacer lo correcto en cualquier máquina de dos componentes que no genere señales en las conversiones, que es prácticamente cualquier máquina y compilador de C construido en los últimos 20 años.

No, su segundo código no es correcto, pero está cerca: si establece

int half = INT_MAX/2; int half1 = half + 1;

el resultado de una adición es INT_MAX . ( INT_MAX siempre es un número impar). Entonces esta es una entrada válida. Pero en tu rutina tendrás INT_MAX - half == half1 y INT_MAX - half == half1 . Un falso positivo.

Este error puede repararse poniendo < lugar de <= en ambas comprobaciones.

Pero también tu código no es óptimo. Lo siguiente haría:

int add(int lhs, int rhs) { if (lhs >= 0) { if (INT_MAX - lhs < rhs) { /* would overflow */ abort(); } } else { if (rhs < INT_MIN - lhs) { /* would overflow */ abort(); } } return lhs + rhs; }

Para ver que esto es válido, debe agregar simbólicamente lhs en ambos lados de las desigualdades, y esto le proporciona exactamente las condiciones aritméticas de que su resultado está fuera de límites.

Para el caso de gcc, de las notas de la versión de gcc 5.0 podemos ver que ahora también proporciona un __builtin_add_overflow para verificar el desbordamiento:

Se ha agregado un nuevo conjunto de funciones integradas para aritmética con control de desbordamiento: __builtin_add_overflow, __builtin_sub_overflow y __builtin_mul_overflow y para compatibilidad con clang también otras variantes. Estos builtins tienen dos argumentos integrales (que no necesitan tener el mismo tipo), los argumentos se extienden a un tipo de firma de precisión infinita, +, - o * se realiza en esos, y el resultado se almacena en una variable entera apuntada a por el último argumento. Si el valor almacenado es igual al resultado de precisión infinita, las funciones incorporadas devuelven falso, de lo contrario es verdadero. El tipo de la variable entera que contendrá el resultado puede ser diferente de los tipos de los primeros dos argumentos.

Por ejemplo:

__builtin_add_overflow( rhs, lhs, &result )

Podemos ver en el documento gcc Funciones incorporadas para realizar operaciones aritméticas con desbordamiento Comprobando que:

[...] estas funciones incorporadas tienen un comportamiento completamente definido para todos los valores de argumento.

clang también proporciona un conjunto de construcciones aritméticas comprobadas :

Clang proporciona un conjunto de instrucciones internas que implementan la aritmética comprobada para aplicaciones críticas de seguridad de una manera rápida y fácilmente expresable en C.

en este caso, el builtin sería:

__builtin_sadd_overflow( rhs, lhs, &result )

Por mí, la comprobación más simple sería verificar los signos de los operandos y de los resultados.

Examinemos la suma: el desbordamiento podría ocurrir en ambas direcciones, + o -, solo cuando ambos operandos tengan el mismo signo. Y, obviamente, el desbordamiento será cuando el signo del resultado no será el mismo que el de los operandos.

Entonces, un cheque como este será suficiente:

int a, b, sum; sum = a + b; if (((a ^ ~b) & (a ^ sum)) & 0x80000000) detect_oveflow();

Editar: como sugirió Nils, esta es la condición correcta if :

((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)

Y desde cuando la instrucción

add eax, ebx

conduce a un comportamiento indefinido? No existe tal cosa en la referencia del conjunto de instrucciones Intel x86.

Puede que tengas más suerte convirtiendo números enteros de 64 bits y probando condiciones similares como esa. Por ejemplo:

#include <stdint.h> ... int64_t sum = (int64_t)lhs + (int64_t)rhs; if (sum < INT_MIN || sum > INT_MAX) { // Overflow occurred! } else { return sum; }

Es posible que desee examinar de cerca cómo funcionará la extensión de signo aquí, pero creo que es correcto.

Qué tal si:

int sum(int n1, int n2) { int result; if (n1 >= 0) { result = (n1 - INT_MAX)+n2; /* Can''t overflow */ if (result > 0) return INT_MAX; else return (result + INT_MAX); } else { result = (n1 - INT_MIN)+n2; /* Can''t overflow */ if (0 > result) return INT_MIN; else return (result + INT_MIN); } }

Creo que debería funcionar para cualquier INT_MIN e INT_MAX legítimos (simétricos o no); la función como se muestra en los clips, pero debería ser obvio cómo obtener otros comportamientos).

Su enfoque con la resta es correcto y bien definido. Un compilador no puede optimizarlo.

Otro enfoque correcto, si tiene un tipo entero más grande disponible, es realizar la aritmética en el tipo más grande y luego verificar que el resultado se ajuste al tipo más pequeño al convertirlo de nuevo

int sum(int a, int b) { long long c; assert(LLONG_MAX>INT_MAX); c = (long long)a + b; if (c < INT_MIN || c > INT_MAX) abort(); return c; }

Un buen compilador debe convertir la suma completa y la instrucción if en una suma de tamaño total y un único salto de desbordamiento condicional y nunca realizar la suma más grande.

Editar: Como Stephen señaló, estoy teniendo problemas para obtener un compilador (no tan bueno), gcc, para generar el asm en su sano juicio. El código que genera no es terriblemente lento, pero ciertamente no es óptimo. Si alguien conoce variantes en este código que harán que gcc haga lo correcto, me encantaría verlas.