Débordement d'entier - Integer overflow

Le débordement d'entiers peut être démontré par un débordement d' odomètre , une version mécanique du phénomène. Tous les chiffres sont définis au maximum 9 et l'incrément suivant du chiffre blanc provoque une cascade d'ajouts de report mettant tous les chiffres à 0, mais il n'y a pas de chiffre supérieur (chiffre de 1 000 000) à changer en 1, donc le compteur se remet à zéro. C'est enveloppant contrairement à saturer .

Dans la programmation informatique , un débordement d'entier se produit lorsqu'une opération arithmétique tente de créer une valeur numérique qui est en dehors de la plage pouvant être représentée avec un nombre donné de chiffres - soit supérieure au maximum, soit inférieure à la valeur minimale représentable.

Le résultat le plus courant d'un débordement est que les chiffres représentables les moins significatifs du résultat sont stockés ; on dit que le résultat s'enroule autour du maximum (c'est-à-dire modulo une puissance de la base , généralement deux dans les ordinateurs modernes, mais parfois dix ou une autre base).

Une condition de débordement peut donner des résultats conduisant à un comportement inattendu. En particulier, si la possibilité n'a pas été anticipée, un débordement peut compromettre la fiabilité et la sécurité d' un programme .

Pour certaines applications, telles que les minuteries et les horloges, le bouclage en cas de débordement peut être souhaitable. La norme C11 stipule que pour les entiers non signés, l'enveloppement modulo est le comportement défini et le terme débordement ne s'applique jamais : « un calcul impliquant des opérandes non signés ne peut jamais déborder ».

Sur certains processeurs tels que les unités de traitement graphique (GPU) et les processeurs de signal numérique (DSP) qui prennent en charge l' arithmétique de saturation , les résultats débordés seraient « bloqués », c'est-à-dire réglés sur la valeur minimale ou maximale dans la plage représentable, plutôt qu'enroulés.

Origine

La largeur de registre d'un processeur détermine la plage de valeurs qui peuvent être représentées dans ses registres. Bien que la grande majorité des ordinateurs puissent effectuer une arithmétique à précision multiple sur des opérandes en mémoire, permettant aux nombres d'être arbitrairement longs et d'éviter les débordements, la largeur du registre limite les tailles des nombres qui peuvent être exploités (par exemple ajoutés ou soustraits) à l'aide d'un une seule instruction par opération. Les largeurs de registre binaires typiques pour les entiers non signés incluent :

  • 4 bits : valeur maximale représentable 2 4 - 1 = 15
  • 8 bits : valeur maximale représentable 2 8 − 1 = 255
  • 16 bits : valeur maximale représentable 2 16 − 1 = 65 535
  • 32 bits : valeur représentable maximale 2 32 − 1 = 4 294 967 295 (la largeur la plus courante pour les ordinateurs personnels à partir de 2005),
  • 64 bits : valeur représentable maximale 2 64 − 1 = 18 446 744 073 709 551 615 (la largeur la plus courante pour les processeurs d' ordinateurs personnels , à partir de 2017),
  • 128 bits : valeur maximale représentable 2 128 − 1 = 340 282 366 920 938 463 463 374 607 431 768 211 455

Lorsqu'une opération arithmétique produit un résultat supérieur au maximum ci-dessus pour un entier de N bits, un débordement réduit le résultat à la puissance modulo N-ième de 2, en ne conservant que les bits les moins significatifs du résultat et en provoquant effectivement un bouclage .

En particulier, la multiplication ou l'addition de deux nombres entiers peut donner une valeur étonnamment petite, et la soustraction d'un petit nombre entier peut entraîner un retour à une grande valeur positive (par exemple, l'addition d'entiers 8 bits 255 + 2 donne 1, ce qui est 257 mod 2 8 , et de même la soustraction 0 − 1 donne 255, une représentation en complément à deux de −1).

Un tel bouclage peut nuire à la sécurité : si une valeur de dépassement est utilisée comme nombre d'octets à allouer pour un tampon, le tampon sera alloué de manière inattendue, ce qui peut conduire à un débordement de tampon qui, selon l'utilisation du tampon, pourrait en provoquer l'exécution de code arbitraire.

Si la variable a un type entier signé , un programme peut supposer qu'une variable contient toujours une valeur positive. Un débordement d'entier peut entraîner l'enroulement de la valeur et la rendre négative, ce qui viole l'hypothèse du programme et peut entraîner un comportement inattendu (par exemple, l'addition d'un entier 8 bits de 127 + 1 donne -128, un complément à deux de 128). (Une solution à ce problème particulier consiste à utiliser des types entiers non signés pour les valeurs qu'un programme attend et suppose qu'elles ne seront jamais négatives.)

Drapeaux

La plupart des ordinateurs ont deux indicateurs de processeur dédiés pour vérifier les conditions de débordement.

Le drapeau de retenue est activé lorsque le résultat d'une addition ou d'une soustraction, en considérant les opérandes et le résultat comme des nombres non signés, ne rentre pas dans le nombre de bits donné. Ceci indique un débordement avec un report ou un emprunt du bit de poids fort . Une opération d' ajout avec retenue ou de soustraction avec emprunt immédiatement suivante utiliserait le contenu de cet indicateur pour modifier un registre ou un emplacement de mémoire qui contient la partie supérieure d'une valeur multi-mots.

L' indicateur de débordement est activé lorsque le résultat d'une opération sur des nombres signés n'a pas le signe que l'on prédirait à partir des signes des opérandes, par exemple un résultat négatif lors de l'addition de deux nombres positifs. Cela indique qu'un débordement s'est produit et que le résultat signé représenté sous forme de complément à deux ne tiendrait pas dans le nombre de bits donné.

Variations de définition et ambiguïté

Pour un type non signé, lorsque le résultat idéal d'une opération est en dehors de la plage représentable du type et que le résultat renvoyé est obtenu par encapsulation, cet événement est généralement défini comme un débordement. En revanche, la norme C11 définit que cet événement n'est pas un débordement et stipule "un calcul impliquant des opérandes non signés ne peut jamais déborder".

Lorsque le résultat idéal d'une opération d'entier est en dehors de la plage représentable du type et que le résultat renvoyé est obtenu par serrage, cet événement est généralement défini comme une saturation. L'utilisation varie selon qu'une saturation est ou non un débordement. Pour lever l'ambiguïté, les termes débordement enveloppant et débordement saturant peuvent être utilisés.

Le terme sous-débordement est le plus souvent utilisé pour les calculs à virgule flottante et non pour les calculs à nombre entier. Mais, de nombreuses références peuvent être trouvées pour le sous-dépassement d'entier. Lorsque le terme sous-dépassement d'entier est utilisé, cela signifie que le résultat idéal était plus proche de moins l'infini que la valeur représentable du type de sortie la plus proche de moins l'infini. Lorsque le terme de débordement d'entier est utilisé, la définition de débordement peut inclure tous les types de débordements ou ne peut inclure que les cas où le résultat idéal était plus proche de l'infini positif que la valeur représentable du type de sortie la plus proche de l'infini positif.

Lorsque le résultat idéal d'une opération n'est pas un entier exact, la signification du débordement peut être ambiguë dans les cas extrêmes. Considérons le cas où le résultat idéal a la valeur 127,25 et la valeur représentable maximale du type de sortie est 127. Si le débordement est défini comme la valeur idéale étant en dehors de la plage représentable du type de sortie, alors ce cas serait classé comme un débordement. Pour les opérations qui ont un comportement d'arrondi bien défini, la classification de débordement peut devoir être reportée jusqu'à ce que l'arrondi soit appliqué. La norme C11 définit que les conversions de virgule flottante en nombre entier doivent arrondir vers zéro. Si C est utilisé pour convertir la valeur à virgule flottante 127,25 en entier, alors l'arrondi doit être appliqué en premier pour donner une sortie entière idéale de 127. Étant donné que l'entier arrondi est dans la plage des sorties, la norme C ne classerait pas cette conversion comme un débordement .

Comportement incohérent

Il convient de noter que le comportement en cas de débordement peut ne pas être cohérent dans toutes les circonstances. Dans le langage de programmation Rust par exemple, alors que la fonctionnalité est fournie pour donner aux utilisateurs le choix et le contrôle, le comportement pour l'utilisation de base des opérateurs mathématiques est naturellement fixe ; ce comportement fixe diffère cependant entre un programme construit en mode 'debug' et un programme construit en mode 'release'. En C, le débordement d'entier non signé est défini pour s'enrouler, tandis que le débordement d'entier signé provoque un comportement indéfini .

Méthodes pour résoudre les problèmes de débordement d'entier

Gestion des débordements d'entiers dans divers langages de programmation
Langue Entier non signé Entier signé
Ada modulo le module du type augmenter Constraint_Error
C / C++ puissance modulo de deux comportement indéfini
C# puissance modulo de 2 en contexte non contrôlé ; System.OverflowExceptionest levé dans un contexte vérifié
Java N / A puissance modulo de deux
JavaScript tous les nombres sont à virgule flottante double précision sauf le nouveau BigInt
MATLAB Les entiers intégrés saturent. Entiers à virgule fixe configurables pour envelopper ou saturer
Python 2 N / A convertir en type long (bigint)
Graine7 N / A augmenter OVERFLOW_ERROR
Schème N / A convertir en bigNum
Simulink configurable pour envelopper ou saturer
Petite conversation N / A convertir en LargeInteger
Rapide Provoque une erreur à moins d'utiliser des opérateurs de débordement spéciaux.

Détection

L'implémentation de la détection de débordement à l'exécution UBSanest disponible pour les compilateurs C .

En Java 8, il existe des méthodes surchargées , comme par exemple Math.addExact(int, int), qui se lanceront ArithmeticExceptionen cas de débordement.

L'équipe d'intervention d'urgence informatique (CERT) a développé le modèle d'entier As-if Infinitely Ranged (AIR), un mécanisme largement automatisé pour éliminer le débordement d'entier et la troncature en C/C++ à l'aide de la gestion des erreurs d'exécution.

Évitement

En allouant des variables avec des types de données suffisamment volumineux pour contenir toutes les valeurs pouvant éventuellement y être calculées et stockées, il est toujours possible d'éviter les débordements. Même lorsque l'espace disponible ou les types de données fixes fournis par un langage ou un environnement de programmation sont trop limités pour permettre aux variables d'être allouées de manière défensive avec des tailles généreuses, en ordonnant soigneusement les opérations et en vérifiant les opérandes à l'avance, il est souvent possible de s'assurer a priori que le résultat ne sera jamais plus grand que ce qui peut être stocké. Les outils d' analyse statique , la vérification formelle et les techniques de conception par contrat peuvent être utilisés pour garantir avec plus de confiance et de robustesse qu'un débordement ne peut pas se produire accidentellement.

Manutention

S'il est prévu qu'un débordement se produise, des tests peuvent être insérés dans le programme pour détecter quand cela se produit, ou est sur le point de se produire, et effectuer d'autres traitements pour l'atténuer. Par exemple, si un résultat important calculé à partir d'une entrée utilisateur déborde, le programme peut s'arrêter, rejeter l'entrée et peut-être demander à l'utilisateur une entrée différente, plutôt que le programme continue avec l'entrée débordée invalide et fonctionne probablement mal en conséquence. Ce processus complet peut être automatisé : il est possible de synthétiser automatiquement un gestionnaire pour un débordement d'entier, où le gestionnaire est par exemple une sortie propre.

Les processeurs disposent généralement d'un moyen de détecter cela pour prendre en charge l'ajout de nombres supérieurs à la taille de leur registre, généralement à l'aide d'un bit d'état ; la technique est appelée arithmétique à précision multiple. Ainsi, il est possible d'ajouter deux nombres chacun de deux octets de large en utilisant juste une addition d'octets par étapes : d'abord ajouter les octets de poids faible puis ajouter les octets de poids fort, mais s'il est nécessaire d'effectuer des octets de poids faible c'est un débordement arithmétique du addition d'octets et il devient nécessaire de détecter et d'incrémenter la somme des octets de poids fort.

La gestion d'un éventuel débordement d'un calcul peut parfois présenter un choix entre effectuer une vérification avant le calcul réel (pour déterminer si un débordement va se produire ou non) ou après (pour déterminer s'il s'est probablement produit en fonction de la valeur résultante) . Il faut faire preuve de prudence envers ce dernier choix. Premièrement, puisqu'il peut ne pas s'agir d'une méthode de détection fiable (par exemple, un ajout peut ne pas nécessairement être ramené à une valeur inférieure). Deuxièmement, parce que l'occurrence du débordement lui-même peut dans certains cas être un comportement indéfini . Dans le langage de programmation C, le débordement de types entiers non signés entraîne un emballage, mais le débordement de types entiers signés est un comportement indéfini ; par conséquent, un compilateur C est libre de supposer que le programmeur s'est assuré qu'un débordement signé ne peut pas se produire et ainsi il peut optimiser silencieusement tout contrôle ultérieur au calcul qui implique de vérifier le résultat pour le détecter sans avertir le programmeur que cela a été terminé. Il convient donc de toujours préférer mettre en œuvre des contrôles avant les calculs et non après eux.

Propagation explicite

si une valeur est trop grande pour être stockée, une valeur spéciale peut lui être attribuée indiquant qu'un débordement s'est produit, puis toutes les opérations successives peuvent renvoyer cette valeur d'indicateur. De telles valeurs sont parfois appelées NaN , pour "pas un nombre". Ceci est utile pour que le problème puisse être vérifié une fois à la fin d'un long calcul plutôt qu'après chaque étape. Ceci est souvent pris en charge dans le matériel à virgule flottante appelé FPU .

Prise en charge du langage de programmation

Les langages de programmation implémentent diverses méthodes d'atténuation contre un débordement accidentel : Ada , Seed7 (et certaines variantes de langages fonctionnels), déclenchent une condition d'exception en cas de débordement, tandis que Python (depuis 2.4) convertit de manière transparente la représentation interne du nombre pour correspondre à sa croissance, représentant finalement comme long– dont la capacité n'est limitée que par la mémoire disponible.

Dans les langages avec prise en charge native de l'arithmétique de précision arbitraire et de la sécurité des types (tels que Python , Smalltalk ou Common Lisp ), les nombres sont automatiquement promus à une taille plus grande lorsque des débordements se produisent ou des exceptions levées (conditions signalées) lorsqu'une contrainte de plage existe. L'utilisation de tels langages peut donc être utile pour atténuer ce problème. Cependant, dans certains de ces langages, des situations sont toujours possibles où un débordement d'entier peut se produire. Un exemple est l'optimisation explicite d'un chemin de code qui est considéré comme un goulot d'étranglement par le profileur. Dans le cas de Common Lisp , cela est possible en utilisant une déclaration explicite pour annoter une variable en un mot de taille machine (fixnum) et abaisser le niveau de sécurité de type à zéro pour un bloc de code particulier.

Contrairement aux langages plus anciens comme le C, certains langages plus récents, comme Rust par exemple, fournissent des fonctionnalités intégrées qui permettent une détection facile et le choix de l'utilisateur sur la façon dont le débordement doit être géré au cas par cas. Dans Rust, alors que l'utilisation d'opérateurs mathématiques de base manque naturellement d'une telle flexibilité, les utilisateurs peuvent alternativement effectuer des calculs via un ensemble de méthodes fournies par chacun des types primitifs entiers. Ces méthodes offrent aux utilisateurs plusieurs choix entre effectuer une opération « vérifiée » (ou « débordante ») (qui indique si un débordement s'est produit ou non via le type de retour ); une opération « non contrôlée » ; une opération qui effectue un habillage ou une opération qui effectue une saturation aux bornes numériques.

Arithmétique saturée

En infographie ou en traitement du signal , il est courant de travailler sur des données allant de 0 à 1 ou de -1 à 1. Par exemple, prenez une image en niveaux de gris où 0 représente le noir, 1 représente le blanc et les valeurs intermédiaires représentent nuances de gris. Une opération que l'on peut vouloir prendre en charge est d'éclaircir l'image en multipliant chaque pixel par une constante. L'arithmétique saturée permet de multiplier aveuglément chaque pixel par cette constante sans se soucier du débordement en s'en tenant simplement à un résultat raisonnable selon lequel tous ces pixels plus grands que 1 (c'est-à-dire "plus brillants que le blanc" ) deviennent simplement blancs et toutes les valeurs "plus sombres que noires " juste devenir noir.

Exemples

Un débordement arithmétique imprévu est une cause assez fréquente d' erreurs de programme . De tels bogues de débordement peuvent être difficiles à découvrir et à diagnostiquer car ils peuvent se manifester uniquement pour des ensembles de données d'entrée très volumineux, qui sont moins susceptibles d'être utilisés dans les tests de validation.

Prendre la moyenne arithmétique de deux nombres en les additionnant et en divisant par deux, comme cela se fait dans de nombreux algorithmes de recherche , provoque une erreur si la somme (bien que pas la moyenne résultante) est trop grande pour être représentée et déborde donc.

Un débordement arithmétique non traité dans le logiciel de pilotage du moteur a été la principale cause du crash du vol inaugural de 1996 de la fusée Ariane 5 . Le logiciel avait été considéré comme exempt de bogues puisqu'il avait été utilisé dans de nombreux vols précédents, mais ceux-ci utilisaient des fusées plus petites qui généraient une accélération inférieure à Ariane 5. De manière frustrante, la partie du logiciel dans laquelle l'erreur de débordement s'était produite n'avait même pas besoin d'être fonctionnant pour l'Ariane 5 au moment où il a causé l'échec de la fusée - il s'agissait d'un processus de régime de lancement pour un prédécesseur plus petit d'Ariane 5 qui était resté dans le logiciel lorsqu'il a été adapté pour la nouvelle fusée. De plus, la cause réelle de l'échec était une faille dans la spécification technique de la façon dont le logiciel a traité le débordement lorsqu'il a été détecté : il a effectué un vidage de diagnostic sur son bus, qui aurait été connecté à l'équipement de test lors des tests du logiciel pendant le développement. mais était connecté aux moteurs de direction de fusée pendant le vol ; le vidage de données a poussé la tuyère du moteur d'un côté, ce qui a mis la fusée hors de contrôle aérodynamique et a précipité sa rupture rapide dans les airs.

Le 30 avril 2015, la Federal Aviation Authority des États-Unis a annoncé qu'elle ordonnerait aux opérateurs de Boeing 787 de réinitialiser périodiquement son système électrique, afin d'éviter un débordement d'entier qui pourrait entraîner une perte d'alimentation électrique et le déploiement d'une turbine à air dynamique, et Boeing a déployé une mise à jour logicielle dans le quatrième trimestre. L' Agence européenne de la sécurité aérienne a suivi le 4 mai 2015. L'erreur se produit après 2³¹ centisecondes (248,55134814815 jours), indiquant un entier signé de 32 bits .

Les bugs de débordement sont évidents dans certains jeux informatiques. Dans le jeu d'arcade Donkey Kong , il est impossible de passer au-delà du niveau 22 en raison d'un débordement d'entier dans son temps/bonus. Le jeu prend le numéro de niveau auquel se trouve un utilisateur, le multiplie par 10 et ajoute 40. Lorsqu'ils atteignent le niveau 22, le nombre de temps/bonus est de 260, ce qui est trop grand pour son registre de 8 bits de 256 valeurs, il se réinitialise donc. à 0 et donne les 4 restants comme temps/bonus – trop court pour terminer le niveau. Dans Donkey Kong Jr. Math , lorsque vous essayez de calculer un nombre supérieur à 10 000, seuls les 4 premiers chiffres sont affichés. Le débordement est à l'origine du fameux niveau "écran partagé" dans Pac-Man . Le bug notoire de Nuclear Gandhi dans Civilization aurait été causé par un dépassement d'entier qui s'est produit lorsque le jeu a tenté de soustraire 2 du niveau d'agression par défaut de Gandhi de 1, le fixant à 255, près de 26 fois plus élevé que le maximum normal de 10. ( Sid Meier a affirmé dans une interview que c'était, en fait, intentionnel.) Un tel bogue a également causé les « terres lointaines » dans Minecraft qui existaient depuis la période de développement d'Infdev jusqu'à la version bêta 1.7.3 ; il a ensuite été corrigé dans la version bêta 1.8 mais existe toujours dans les versions Pocket Edition et Windows 10 Edition de Minecraft . Dans le jeu Super NES Lamborghini American Challenge , le joueur peut faire chuter son montant d'argent en dessous de 0 $ pendant une course en se voyant imposer une amende dépassant la limite de l'argent restant après avoir payé les frais d'une course, ce qui modifie le nombre entier et accorde au joueur 65 535 000 $. plus qu'il n'en aurait eu après être devenu négatif. Un problème similaire se produit dans STALKER: Clear Sky où le joueur peut tomber dans un montant négatif en voyageant rapidement sans fonds suffisants, puis en procédant à l'événement où le joueur se fait voler et se voit confisquer toute sa monnaie. Une fois que le jeu a tenté de retirer l'argent du joueur à un montant de 0 $, le joueur reçoit 2147482963 dans la devise du jeu.

Dans la structure de données de Pokémon dans les jeux Pokémon, le nombre de points d'expérience gagnés est stocké dans un entier de 3 octets. Cependant, dans les première et deuxième générations, le groupe d'expérience Moyennement lent, qui nécessite 1 059 860 points d'expérience pour atteindre le niveau 100, est calculé pour avoir -54 points d'expérience au niveau 1 (un niveau qui n'est généralement pas rencontré pendant le jeu normal). En raison de l'entier non signé, la valeur devient 16 777 162. Si le Pokémon obtient moins de 54 points d'expérience dans une bataille, alors le Pokémon passera instantanément au niveau 100.

Un bogue de signature d'entier dans le code de configuration de la pile émis par le compilateur Pascal empêchait Microsoft / IBM MACRO Assembler Version 1.00 (MASM), un programme DOS de 1981, et de nombreux autres programmes compilés avec le même compilateur, de s'exécuter sous certaines configurations avec plus de 512 Ko de mémoire.

Microsoft / IBM Macro Assembler (MASM) Version 1.00, et probablement tous les autres programmes construits par le même compilateur Pascal, avaient un dépassement d'entier et une erreur de signature dans le code de configuration de la pile, ce qui les empêchait de s'exécuter sur des machines DOS ou des émulateurs plus récents sous certains configurations avec plus de 512 Ko de mémoire. Le programme se bloque ou affiche un message d'erreur et quitte le DOS.

En août 2016, une machine de casino du casino Resorts World a imprimé un ticket de prix de 42 949 672,76 $ à la suite d'un bug de débordement. Le casino a refusé de payer ce montant, le qualifiant de dysfonctionnement, utilisant pour sa défense le fait que la machine indiquait clairement que le paiement maximum était de 10 000 $, de sorte que tout prix dépassant ce montant devait être le résultat d'un bug de programmation. La Cour suprême de l'Iowa a statué en faveur du casino.

Voir également

Les références

Liens externes