Le dépassement d'entier provoque-t-il un comportement indéfini en raison de la corruption de la mémoire ?

Question

J'ai lu récemment que le dépassement des nombres entiers signés en C et C++ entraîne un comportement indéfini :

Si, lors de l'évaluation d'une expression, le résultat n'est pas défini mathématiquement ou ne se trouve pas dans la plage des valeurs représentables pour son type, le comportement est indéfini.

J'essaie actuellement de comprendre la raison de ce comportement indéfini. Je pense que le comportement indéfini se produit ici parce que l'entier commence à manipuler la mémoire autour de lui quand il devient trop grand pour s'adapter au type sous-jacent.

J'ai donc décidé d'écrire un petit programme de test dans Visual Studio 2015 pour vérifier cette théorie avec le code suivant :

#include <stdio.h>
#include <limits.h>

struct TestStruct
{
    char pad1[50];
    int testVal;
    char pad2[50];
};

int main()
{
    TestStruct test;
    memset(&test, 0, sizeof(test));

    for (test.testVal = 0; ; test.testVal++)
    {
        if (test.testVal == INT_MAX)
            printf("Overflowing\r\n");
    }

    return 0;
}

J'ai utilisé une structure ici pour éviter toute protection de Visual Studio en mode débogage, comme le remplissage temporaire des variables de la pile et ainsi de suite. La boucle sans fin devrait provoquer plusieurs débordements de test.testVal et c'est effectivement le cas, mais sans aucune conséquence autre que le débordement lui-même.

J'ai jeté un coup d'œil au vidage de la mémoire lors de l'exécution des tests de débordement et j'ai obtenu le résultat suivant ( test.testVal avait une adresse mémoire de 0x001CFAFC ):

0x001CFAE5  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x001CFAFC  94 53 ca d8 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Comme vous le voyez, la mémoire autour de l'int qui déborde continuellement est restée "intacte". J'ai testé ceci plusieurs fois avec un résultat similaire. Jamais la mémoire autour de l'int qui déborde n'a été endommagée.

Que se passe-t-il ici ? Pourquoi la mémoire autour de la variable n'est-elle pas endommagée ? test.testVal ? Comment cela peut-il provoquer un comportement indéfini ?

J'essaie de comprendre mon erreur et pourquoi il n'y a pas de corruption de mémoire lors d'un débordement d'entier.

Answer 1

Vous comprenez mal la raison du comportement indéfini. La raison n'est pas la corruption de la mémoire autour de l'entier - il occupera toujours la même taille qu'occupent les entiers - mais l'arithmétique sous-jacente.

Étant donné que les entiers signés ne sont pas tenus d'être codés en complément à 2, il ne peut y avoir d'indications spécifiques sur ce qui va se passer lorsqu'ils débordent. Un codage différent ou un comportement différent de l'unité centrale peuvent entraîner des résultats différents du débordement, y compris, par exemple, des arrêts de programme dus à des pièges.

Et comme pour tout comportement indéfini, même si votre matériel utilise le complément à 2 pour son arithmétique et a des règles définies pour le débordement, les compilateurs ne sont pas liés par celles-ci. Par exemple, pendant longtemps, GCC a optimisé toute vérification qui ne serait vraie que dans un environnement de complément à 2. Par exemple, if (x > x + 1) f() va être supprimé du code optimisé, car le débordement signé est un comportement indéfini, ce qui signifie qu'il ne se produit jamais (du point de vue du compilateur, les programmes ne contiennent jamais de code produisant un comportement indéfini), ce qui signifie que x ne peut jamais être supérieure à x + 1 .

Answer 2

Les auteurs de la norme ont laissé le débordement d'entier non défini parce que certaines plates-formes matérielles pouvaient piéger d'une manière dont les conséquences pouvaient être imprévisibles (y compris l'exécution de code aléatoire et la corruption de la mémoire qui en résulte). Bien que le matériel à complément à deux avec une gestion prévisible des débordements par silencieux était pratiquement établi comme un standard au moment de la publication de la norme C89 (parmi les nombreuses architectures de micro-ordinateurs reprogrammables que j'ai examinées, aucune n'utilise autre chose), les auteurs de la norme ne voulaient pas empêcher quiconque de produire des implémentations C sur des machines plus anciennes.

Sur les implémentations qui mettaient en œuvre la sémantique habituelle du complément à deux silencieux, un code tel que

int test(int x)
{
  int temp = (x==INT_MAX);
  if (x+1 <= 23) temp+=2;
  return temp;
}

retournerait, de manière 100% fiable, 3 lorsqu'on lui passe une valeur de INT_MAX, puisque l'ajout de 1 à INT_MAX donnerait 1 à INT_MAX donnerait INT_MIN, qui est bien sûr inférieur à 23.

Dans les années 1990, les compilateurs ont utilisé le fait que le débordement d'entier était un comportement non défini, plutôt que d'être défini comme un enveloppement de complément à deux, pour permettre diverses optimisations qui signifiaient que les résultats exacts des calculs qui débordaient ne seraient pas prévisibles, mais que les aspects du comportement qui ne dépendaient pas des résultats exacts resteraient sur les rails. Un compilateur des années 1990 qui recevrait le code ci-dessus le traiterait probablement comme si l'ajout de 1 à INT_MAX donnait une valeur numériquement supérieure d'une unité à INT_MAX, ce qui ferait que la fonction renverrait 1 plutôt que 3, ou bien il pourrait se comporter comme les anciens compilateurs, en retournant 3. Notez que dans le code ci-dessus, un tel traitement pourrait sauver une instruction sur de nombreuses plates-formes, puisque (x+1 <= 23) serait équivalent à (x <= 22). Un compilateur peut ne pas être cohérent dans son choix de 1 ou 3, mais le code généré ne ferait rien d'autre que de donner l'une de ces valeurs.

Depuis lors, cependant, il est devenu de plus en plus courant pour les compilateurs d'utiliser la norme de l'UE. l'incapacité de la norme à imposer des exigences sur le comportement du programme en cas de de débordement d'entier (un échec motivé par l'existence de matériel où les matériel dont les conséquences peuvent être réellement imprévisibles) pour justifier que les compilateurs lancer du code complètement à côté de la plaque en cas de débordement. Un compilateur moderne pourrait remarquer que le programme invoquera un comportement indéfini si x==INT_MAX, et donc conclure que cette valeur ne sera jamais transmise à la fonction. Si la fonction fonction ne reçoit jamais cette valeur, la comparaison avec INT_MAX peut être omise. omise. Si la fonction ci-dessus est appelée depuis une autre unité de traduction avec x==INT_MAX, elle pourrait donc renvoyer 0 ou 2 ; si elle est appelée depuis la même unité de traduction, l'effet pourrait être encore plus important. unité de traduction, l'effet pourrait être encore plus bizarre puisqu'un compilateur pourrait compilateur étendrait ses inférences sur x à l'appelant.

En ce qui concerne la question de savoir si le débordement peut entraîner une corruption de la mémoire, sur certains matériels anciens, c'est possible. Sur les anciens compilateurs fonctionnant sur du matériel moderne, ce n'est pas le cas. Sur les compilateurs hyper-modernes, le débordement annule le tissu du temps et de la causalité, donc tous les paris sont ouverts. Le débordement dans l'évaluation de x+1 pourrait effectivement corrompre la valeur de x qui avait été vue par la comparaison précédente avec INT_MAX, se comportant comme si la valeur de x en mémoire avait été corrompue. De plus, un tel comportement du compilateur supprimera souvent la logique conditionnelle qui aurait empêché d'autres types de corruption de la mémoire, permettant ainsi à une corruption arbitraire de la mémoire de se produire.

Answer 3

Un comportement indéfini est indéfini. Il peut faire planter votre programme. Il peut ne rien faire du tout. Il peut faire exactement ce que vous attendiez. Il peut invoquer des démons nasaux. Il peut supprimer tous vos fichiers. Le compilateur est libre d'émettre le code qu'il veut (ou aucun) lorsqu'il rencontre un comportement non défini.

Toute instance de comportement indéfini entraîne l'indéfinition de l'ensemble du programme - et pas seulement de l'opération qui est indéfinie, de sorte que le compilateur peut faire ce qu'il veut de n'importe quelle partie de votre programme. Y compris le voyage dans le temps : Un comportement non défini peut entraîner un voyage dans le temps (entre autres choses, mais le voyage dans le temps est le plus amusant). .

Il existe de nombreuses réponses et articles de blog sur le comportement indéfini, mais les suivants sont mes préférés. Je vous suggère de les lire si vous souhaitez en savoir plus sur le sujet.

• Guide du comportement indéfini en C et C++, 1ère partie
• Ce que tout programmeur C devrait savoir sur le comportement indéfini #1/3

Answer 4

Outre les conséquences ésotériques de l'optimisation, vous devez tenir compte d'autres problèmes, même avec le code que vous vous attendez naïvement à ce qu'un compilateur non optimisé génère.

• Même si vous savez que l'architecture est un complément à deux (ou autre), une opération de débordement peut ne pas définir les drapeaux comme prévu, donc une instruction comme if(a + b < 0) peut prendre la mauvaise branche : étant donné deux grands nombres positifs, lorsqu'ils sont additionnés, ils débordent et le résultat, comme le prétendent les puristes du complément à deux, est négatif, mais l'instruction d'addition peut ne pas activer le drapeau négatif).

• Une opération à plusieurs étapes peut avoir eu lieu dans un registre plus large que sizeof(int), sans être tronquée à chaque étape, et donc une expression comme (x << 5) >> 5 peuvent ne pas couper les cinq bits de gauche comme vous le supposez.

• Les opérations de multiplication et de division peuvent utiliser un registre secondaire pour les bits supplémentaires du produit et du dividende. Si la multiplication "ne peut pas" déborder, le compilateur est libre de supposer que le registre secondaire est égal à zéro (ou -1 pour les produits négatifs) et de ne pas le réinitialiser avant la division. Ainsi, une expression comme x * y / z peut utiliser un produit intermédiaire plus large que prévu.

Certains d'entre eux ressemblent à une précision supplémentaire, mais il s'agit d'une précision supplémentaire qui n'est pas attendue, qui ne peut pas être prédite ou sur laquelle on ne peut pas compter, et qui viole votre modèle mental de "chaque opération accepte des opérandes de complément à deux de N bits et renvoie les N bits les moins significatifs du résultat pour l'opération suivante".

Answer 5

Le comportement de dépassement des nombres entiers n'est pas défini par la norme C++. Cela signifie que toute implémentation du C++ est libre de faire ce qu'elle veut.

En pratique, cela signifie : ce qui est le plus pratique pour l'implémenteur. Et puisque la plupart des implémenteurs traitent int comme une valeur de complément à deux, l'implémentation la plus courante aujourd'hui est de dire qu'une somme débordante de deux nombres positifs est un nombre négatif qui a une certaine relation avec le vrai résultat. Il s'agit d'un mauvaise réponse et c'est autorisé par la norme, car la norme autorise tout.

Il y a un argument pour dire que le dépassement d'un nombre entier doit être traité comme une erreur tout comme la division d'un nombre entier par zéro. L'architecture 86 possède même la fonction INTO pour lever une exception en cas de dépassement. À un moment donné, cet argument pourrait avoir suffisamment de poids pour être intégré dans les compilateurs grand public, auquel cas un dépassement d'entier pourrait provoquer un crash. Ceci est également conforme à la norme C++, qui permet à une implémentation de faire n'importe quoi.

On pourrait imaginer une architecture dans laquelle les nombres seraient représentés sous forme de chaînes à terminaison nulle en mode little-endian, avec un octet zéro indiquant la fin du nombre. L'addition pourrait se faire en ajoutant octet par octet jusqu'à ce qu'un octet zéro soit atteint. Dans une telle architecture, un dépassement de capacité des nombres entiers pourrait écraser un zéro de fin de chaîne par un un, ce qui donnerait un résultat beaucoup, beaucoup plus long et pourrait corrompre les données à l'avenir. Ceci est également conforme à la norme C++.

Enfin, comme indiqué dans d'autres réponses, une grande partie de la génération et de l'optimisation du code dépend du raisonnement du compilateur sur le code qu'il génère et la façon dont il s'exécuterait. Dans le cas d'un débordement d'entier, il est tout à fait licite pour le compilateur (a) de générer du code pour l'addition qui donne des résultats négatifs lors de l'addition de grands nombres positifs et (b) d'informer sa génération de code en sachant que l'addition de grands nombres positifs donne un résultat positif. Ainsi, par exemple

if (a+b>0) x=a+b;

pourrait, si le compilateur sait que les deux a y b sont positifs, sans prendre la peine d'effectuer un test, mais sans condition pour ajouter a a b et mettre le résultat dans x . Sur une machine à deux compléments, cela pourrait conduire à l'introduction d'une valeur négative dans le champ x en violation apparente de l'intention du code. Ce serait tout à fait conforme à la norme.