Rilevamento dell’overflow firmato in C / C ++

A prima vista, questa domanda potrebbe sembrare un duplicato di Come rilevare l’overflow dei numeri interi? , tuttavia è in realtà significativamente diverso.

Ho scoperto che mentre rilevando un overflow di interi non firmati è piuttosto banale, il rilevamento di un overflow con segno in C / C ++ è in realtà più difficile di quanto la maggior parte della gente pensi.

Il modo più ovvio, ma ingenuo, per farlo sarebbe qualcosa di simile:

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

Il problema è che secondo lo standard C, l’overflow dei caratteri interi con segno è un comportamento indefinito. In altre parole, in base allo standard, non appena si causa anche un overflow con segno, il proprio programma è altrettanto invalido come se si dereferenziasse un puntatore nullo. Quindi non è ansible causare un comportamento indefinito, quindi provare a rilevare l’overflow dopo il fatto, come nell’esempio di controllo post-condizione sopra riportato.

Anche se il controllo di cui sopra è probabile che funzioni su molti compilatori, non puoi contare su di esso. Infatti, poiché lo standard C dice che l’overflow dei numeri interi con segno è indefinito, alcuni compilatori (come GCC) ottimizzeranno il controllo di cui sopra quando vengono impostati i flag di ottimizzazione, poiché il compilatore presuppone un overflow con segno imansible. Questo interrompe totalmente il tentativo di verificare l’overflow.

Quindi, un altro modo ansible per verificare l’overflow sarebbe:

 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; } 

Questo sembra più promettente, dal momento che non aggiungiamo effettivamente i due numeri interi finché non ci accertiamo in anticipo che l’esecuzione di tale aggiunta non comporterà un overflow. Quindi, non causiamo alcun comportamento indefinito.

Tuttavia, questa soluzione è purtroppo molto meno efficiente della soluzione iniziale, dal momento che è necessario eseguire un’operazione di sottrazione solo per verificare se l’operazione di aggiunta funzionerà. E anche se non ti importa di questo (piccolo) successo in termini di prestazioni, non sono ancora del tutto convinto che questa soluzione sia adeguata. L’espressione lhs <= INT_MIN - rhs sembra esattamente come il tipo di espressione che il compilatore potrebbe ottimizzare, pensando che l’overflow firmato sia imansible.

Quindi c’è una soluzione migliore qui? Qualcosa che è garantito a 1) non causa un comportamento indefinito, e 2) non fornisce al compilatore l’opportunità di ottimizzare i controlli di overflow? Stavo pensando che ci potrebbe essere un modo per farlo, convertendo entrambi gli operandi in unsigned, ed eseguendo dei controlli facendo rotolare la propria aritmetica a complemento a due, ma non sono proprio sicuro di come farlo.

Il tuo approccio con la sottrazione è corretto e ben definito. Un compilatore non può ottimizzarlo.

Un altro approccio corretto, se si dispone di un tipo intero più grande disponibile, è quello di eseguire l’aritmetica nel tipo più grande e quindi verificare che il risultato rientri nel tipo più piccolo quando lo si converte indietro

 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 buon compilatore dovrebbe convertire l’intera aggiunta e l’istruzione if in un’aggiunta int -size e un singolo jump-over-overflow condizionale e non eseguire mai l’aggiunta più grande.

Edit: Come Stephen ha sottolineato, sto avendo problemi a ottenere un compilatore (non così buono), gcc, per generare il sano asm. Il codice che genera non è terribilmente lento, ma certamente non ottimale. Se qualcuno conosce varianti su questo codice che farà sì che gcc faccia la cosa giusta, mi piacerebbe vederle.

No, il tuo secondo codice non è corretto, ma sei vicino: se lo imposti

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

il risultato di un’aggiunta è INT_MAX . ( INT_MAX è sempre un numero dispari). Quindi questo è un input valido. Ma nella tua routine avrai INT_MAX - half == half1 e INT_MAX - half == half1 . Un falso positivo.

Questo errore può essere riparato mettendo < invece di <= in entrambi i controlli.

Ma poi anche il tuo codice non è ottimale. Il seguente dovrebbe fare:

 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; } 

Per vedere che questo è valido, devi aggiungere simbolicamente lhs su entrambi i lati delle disuguaglianze, e questo ti dà esattamente le condizioni aritmetiche che il tuo risultato è fuori dai limiti.

IMHO, il modo più semplice per gestire il codice C ++ con overflow siginoso è usare SafeInt . Questo è un modello C ++ multipiattaforma ospitato su code plex che fornisce le garanzie di sicurezza che desideri qui.

Lo trovo molto intuitivo da usare in quanto fornisce molti degli stessi schemi di utilizzo delle normali operazioni numeriche ed esprime sovra e sottostanti attraverso le eccezioni.

Per il caso gcc, dalle note sulla versione di gcc 5.0 possiamo vederlo ora fornisce un __builtin_add_overflow per il controllo dell’overflow in aggiunta:

È stato aggiunto un nuovo set di funzioni built-in per aritmetica con controllo di overflow: __builtin_add_overflow, __builtin_sub_overflow e __builtin_mul_overflow e per compatibilità con clang anche altre varianti. Questi builtin hanno due argomenti integrali (che non hanno bisogno di avere lo stesso tipo), gli argomenti sono estesi al tipo con segno di precisione infinito, +, – o * viene eseguito su quelli, e il risultato è memorizzato in una variabile intera puntata a dall’ultimo argomento. Se il valore memorizzato è uguale al risultato di precisione infinito, le funzioni predefinite restituiscono false, altrimenti true. Il tipo della variabile intera che manterrà il risultato può essere diverso dai tipi dei primi due argomenti.

Per esempio:

 __builtin_add_overflow( rhs, lhs, &result ) 

Possiamo vedere dal documento gcc Funzioni integrate per eseguire operazioni aritmetiche con overflow Controllando che:

[…] queste funzioni integrate hanno un comportamento completamente definito per tutti i valori degli argomenti.

clang fornisce anche una serie di builtin aritmetici controllati :

Clang fornisce una serie di builtin che implementano l’aritmetica controllata per le applicazioni di sicurezza critiche in un modo che sia veloce e facilmente esprimibile in C.

in questo caso il builtin sarebbe:

 __builtin_sadd_overflow( rhs, lhs, &result ) 

Se si utilizza l’assemblatore inline, è ansible controllare il flag di overflow . Un’altra possibilità è che puoi usare un tipo di dati safeint . Raccomando di leggere questo documento su Integer Security .

Che ne dite di:

 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); } } 

Penso che dovrebbe funzionare per qualsiasi INT_MIN e INT_MAX legittimi (simmetrici o meno); la funzione come clip mostrati, ma dovrebbe essere ovvio come ottenere altri comportamenti).

Potresti avere una migliore fortuna nella conversione a numeri interi a 64 bit e testare condizioni simili come quella. Per esempio:

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

Potresti dare un’occhiata più da vicino a come funziona l’estensione dei segni qui, ma penso sia corretto.

Il modo più veloce ansible è usare il GCC integrato:

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

Su x86, GCC lo compila in:

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

che utilizza il rilevamento di overflow incorporato nel processore.

Se non sei d’accordo con l’uso dei builtin di GCC, il modo più veloce è usare le operazioni bit sui bit di segno. L’overflow firmato si verifica anche quando:

  • i due operandi hanno lo stesso segno, e
  • il risultato ha un segno diverso rispetto agli operandi.

Il bit di segno di ~(lhs ^ rhs) è attivo se gli operandi hanno lo stesso segno e il bit di segno di lhs ^ sum è acceso se il risultato ha un segno diverso rispetto agli operandi. Quindi puoi fare l’aggiunta in forma non firmata per evitare comportamenti non definiti, e quindi usare il bit di segno di ~(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; } 

Questo compila in:

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

che è molto più veloce di un casting a 64 bit su una macchina a 32 bit (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 

Secondo me, il controllo più semplice sarebbe il controllo dei segni degli operandi e dei risultati.

Esaminiamo la sum: l’overflow potrebbe verificarsi in entrambe le direzioni, + o -, solo quando entrambi gli operandi hanno lo stesso segno. E, ovviamente, l’overflow sarà quando il segno del risultato non sarà lo stesso del segno degli operandi.

Quindi, un controllo come questo sarà sufficiente:

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

Modifica: come suggerito da Nils, questa è la condizione corretta if :

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

E da quando l’istruzione

 add eax, ebx 

porta a un comportamento indefinito? Non c’è nulla di simile nella refferenza del set di istruzioni Intel x86.

La soluzione ovvia è convertire in unsigned, per ottenere il comportamento di overflow senza segno ben definito:

 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; } 

Ciò sostituisce il comportamento di overflow con segno non definito con la conversione definita dall’implementazione di valori fuori intervallo tra firmati e non firmati, quindi è necessario controllare la documentazione del compilatore per sapere esattamente cosa accadrà, ma dovrebbe almeno essere ben definito, e dovrebbe fare la cosa giusta su qualsiasi macchina a due complementi che non generi segnali sulle conversioni, che è praticamente ogni macchina e compilatore C costruito negli ultimi 20 anni.

In caso di aggiunta di due valori long , il codice portabile può dividere il valore long in parti int basso e alto (o in parti short nel caso in cui abbia le stesse dimensioni di 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' 

L’utilizzo dell’assieme inline è il modo più rapido se si rivolge a una particolare CPU:

 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' 

Penso che questo funzioni:

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

L’uso di volatile impedisce al compilatore di ottimizzare il test in quanto ritiene che la sum potrebbe essere cambiata tra l’addizione e la sottrazione.

Usando gcc 4.4.3 per x86_64 l’assembly per questo codice fa l’addizione, la sottrazione e il test, sebbene memorizzi tutto nello stack e le operazioni di stack non necessarie. Ho anche provato a register volatile int sum = ma l’assemblaggio era lo stesso.

Per una versione con solo int sum = (non volatile o registro) la funzione non ha eseguito il test e ha effettuato l’aggiunta utilizzando solo un’istruzione lea ( lea è Load Effective Address e viene spesso utilizzata per aggiungere senza toccare il registro flags).

La tua versione è più grande e ha molti più salti, ma non so quale sarebbe meglio .