Détection des débordements signés en C/C++

Question

À première vue, cette question peut sembler être une duplication de Comment détecter un dépassement d'entier ? Cependant, elle est en réalité très différente.

J'ai constaté que si la détection d'un dépassement de capacité d'un entier non signé est assez triviale, la détection d'un dépassement de capacité d'un entier non signé est plus difficile. signé Le débordement en C/C++ est en fait plus difficile que la plupart des gens ne le pensent.

La façon la plus évidente, mais aussi la plus naïve, de le faire serait quelque chose comme :

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

Le problème est que, selon la norme C, le dépassement des nombres entiers signés est comportement non défini. En d'autres termes, selon la norme, dès que vous provoquez ne serait-ce qu'un débordement signé, votre programme est tout aussi invalide que si vous déréférenciez un pointeur nul. Vous ne pouvez donc pas provoquer un comportement indéfini, puis essayer de détecter le débordement après coup, comme dans l'exemple de vérification post-condition ci-dessus.

Même si la vérification ci-dessus est susceptible de fonctionner sur de nombreux compilateurs, vous ne pouvez pas compter dessus. En effet, comme la norme C stipule que le débordement d'un entier signé n'est pas défini, certains compilateurs (comme GCC) vont optimiser le contrôle ci-dessus lorsque les drapeaux d'optimisation sont activés, car le compilateur suppose qu'un dépassement de capacité signé est impossible. Cela casse totalement la tentative de vérifier le débordement.

Donc, une autre façon possible de vérifier le débordement serait :

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

Cela semble plus prometteur, puisque nous n'ajoutons pas réellement les deux entiers ensemble avant de nous assurer à l'avance qu'une telle addition n'entraînera pas de dépassement de capacité. Ainsi, nous ne provoquons pas de comportement non défini.

Cependant, cette solution est malheureusement beaucoup moins efficace que la solution initiale, puisque vous devez effectuer une opération de soustraction juste pour tester si votre opération d'addition fonctionnera. Et même si vous ne vous souciez pas de cette (petite) perte de performance, je ne suis toujours pas convaincu que cette solution soit adéquate. L'expression lhs <= INT_MIN - rhs ressemble exactement au type d'expression que le compilateur pourrait optimiser, en pensant que le dépassement de capacité signé est impossible.

Y a-t-il une meilleure solution ? Quelque chose qui garantisse 1) de ne pas causer de comportement non défini, et 2) de ne pas donner au compilateur l'opportunité d'optimiser les vérifications de débordement ? Je pensais qu'il pourrait y avoir un moyen de le faire en convertissant les deux opérandes en non signés, et en effectuant des vérifications en utilisant votre propre arithmétique de complément à deux, mais je ne suis pas vraiment sûr de savoir comment faire.

Answer 1

Non, votre deuxième code n'est pas correct, mais vous êtes proche : si vous définissez

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

le résultat d'une addition est INT_MAX . ( INT_MAX est toujours un nombre impair). C'est donc une entrée valide. Mais dans votre routine, vous aurez INT_MAX - half == half1 et vous avorteriez. Un faux positif.

Cette erreur peut être réparée en mettant < au lieu de <= dans les deux contrôles.

Mais alors votre code n'est pas non plus optimal. Ce qui suit ferait l'affaire :

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

Pour voir que cela est valide, il faut ajouter symboliquement lhs des deux côtés des inégalités, et cela vous donne exactement les conditions arithmétiques que votre résultat est hors limites.

Answer 2

Votre approche de la soustraction est correcte et bien définie. Un compilateur ne peut pas l'optimiser.

Une autre approche correcte, si vous disposez d'un type d'entier plus grand, consiste à effectuer l'arithmétique dans le type le plus grand, puis à vérifier que le résultat tient dans le type le plus petit lors de la reconversion.

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 bon compilateur devrait convertir toute l'addition et les if dans un int -et un seul saut conditionnel sur dépassement de capacité, sans jamais effectuer la plus grande addition.

Editar: Comme Stephen l'a fait remarquer, j'ai du mal à faire en sorte qu'un compilateur (pas si bon), gcc, génère un asm sain. Le code qu'il génère n'est pas terriblement lent, mais certainement sous-optimal. Si quelqu'un connaît des variantes de ce code qui permettront à gcc de faire ce qu'il faut, j'aimerais les voir.

Answer 3

À mon avis, la manière la plus simple de traiter le code C++ avec un débordement sentencieux est d'utiliser SafeInt<T> . Il s'agit d'un modèle C++ multiplateforme hébergé sur code plex qui offre les garanties de sécurité que vous souhaitez ici.

• https://github.com/dcleblanc/SafeInt

Je trouve son utilisation très intuitive, car il fournit les mêmes modèles d'utilisation que les opérations numériques normales et exprime les flux supérieurs et inférieurs via des exceptions.

Answer 4

Si vous utilisez l'assembleur en ligne, vous pouvez vérifier l'option drapeau de débordement . Une autre possibilité est d'utiliser un système de gestion de l'information. type de données safeint . Je vous recommande de lire ce document sur Sécurité des nombres entiers .

Answer 5

Pourquoi pas :

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

Je pense que ça devrait marcher pour n'importe quel INT_MIN y INT_MAX (symétrique ou non) ; la fonction comme indiqué dans les clips, mais il devrait être évident comment obtenir d'autres comportements).