Comportement indéfini et vérité non définie

Le terme «comportement indéfini» dans le langage C et C ++ désigne une situation dans laquelle littéralement «ce qui ne se produit tout simplement pas». Historiquement, les cas où les compilateurs précédents pour C (et les architectures sur celui-ci) se comportaient de manière incompatible étaient attribués à un comportement indéfini, et le comité chargé d'élaborer la norme, dans sa sagesse illimitée, a décidé de ne rien décider à ce sujet (c'est-à-dire de ne pas donner de préférence une des implémentations concurrentes). Les comportements indéfinis étaient également appelés situations possibles dans lesquelles la norme, généralement si exhaustive, ne prescrivait aucun comportement spécifique. Ce terme a une troisième signification, qui à notre époque devient de plus en plus pertinente: comportement indéfini - c'est l'occasion d'optimisation. Et les développeurs en C et C ++ adorent les optimisations; ils demandent instamment aux compilateurs de tout mettre en œuvre pour accélérer le code.

Cet article a été publié pour la première fois sur le site Web des services de cryptographie. La traduction est publiée avec la permission de l'auteur Thomas Pornin.

Voici un exemple classique:

void foo(double *src, int *dst) { int i; for (i = 0; i < 4; i ++) { dst[i] = (int)src[i]; } } 

Nous compilerons ce code GCC sur une plate-forme x86 64 bits pour Linux (je travaille sur la dernière version d'Ubuntu 18.04, version GCC - 7.3.0). Nous activons l' optimisation complète, puis examinons la liste des assembleurs, pour laquelle nous utilisons les clés "-W -Wall -O9 -S " (l'argument " -O9 " définit le niveau maximal d'optimisation GCC, qui en pratique équivaut à " -O3 ", bien que dans certaines fourches GCC définis et niveaux supérieurs). On obtient le résultat suivant:

  .file "zap.c" .text .p2align 4,,15 .globl foo .type foo, @function foo: .LFB0: .cfi_startproc movupd (%rdi), %xmm0 movupd 16(%rdi), %xmm1 cvttpd2dq %xmm0, %xmm0 cvttpd2dq %xmm1, %xmm1 punpcklqdq %xmm1, %xmm0 movups %xmm0, (%rsi) ret .cfi_endproc .LFE0: .size foo, .-foo .ident "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0" .section .note.GNU-stack,"",@progbits 

Chacune des deux premières instructions movupd déplace deux valeurs doubles vers le registre SSE2 128 bits (le double a une taille de 64 bits, de sorte que le registre SSE2 peut stocker deux valeurs doubles ). En d'autres termes, quatre valeurs initiales sont lues en premier, puis elles sont converties en int (opération cvttpd2dq ). L'opération punpcklqdq déplace les quatre entiers 32 bits reçus dans un registre SSE2 (% xmm0 ), dont le contenu est ensuite écrit dans la RAM ( movups ). Et maintenant l'essentiel: notre programme C nécessite formellement que l'accès à la mémoire se fasse dans l'ordre suivant:

• Lisez la première valeur double de src [0] .
• Écrivez la première valeur de type int dans dst [0] .
• Lisez la deuxième valeur double de src [1] .
• Écrivez la deuxième valeur de type int dans dst [1] .
• Lisez la troisième valeur double de src [2] .
• Écrivez la troisième valeur de type int dans dst [2] .
• Lisez la quatrième valeur double de src [3] .
• Écrivez la quatrième valeur de type int dans dst [3] .

Cependant, toutes ces exigences n'ont de sens que dans le contexte d'une machine abstraite, que la norme C définit; la procédure sur une machine réelle peut varier. Le compilateur est libre de réorganiser ou de modifier les opérations, à condition que leur résultat ne contredit pas la sémantique de la machine abstraite (la règle dite as-if est «comme si»). Dans notre exemple, l'ordre d'action est juste différent:

• Lisez la première valeur double de src [0] .
• Lisez la deuxième valeur double de src [1] .
• Lisez la troisième valeur double de src [2] .
• Lisez la quatrième valeur double de src [3] .
• Écrivez la première valeur de type int dans dst [0] .
• Écrivez la deuxième valeur de type int dans dst [1] .
• Écrivez la troisième valeur de type int dans dst [2] .
• Écrivez la quatrième valeur de type int dans dst [3] .

Il s'agit du langage C: tous les contenus de la mémoire sont finalement des octets (c'est-à-dire des emplacements avec des valeurs de type char non signé , mais en pratique, des groupes de huit bits), et toute opération de pointeur arbitraire est autorisée. En particulier, les pointeurs src et dst peuvent être utilisés pour accéder à des parties de mémoire qui se chevauchent lors de l'appel (cette situation est appelée «aliasing»). Ainsi, l'ordre de lecture et d'écriture peut être important si des octets sont écrits puis relus. Pour que le comportement réel du programme corresponde à l'abstrait défini par la norme C, le compilateur devrait alterner entre les opérations de lecture et d'écriture, fournissant un cycle complet d'accès à la mémoire à chaque itération. Le code résultant serait plus grand et fonctionnerait beaucoup plus lentement. Pour les développeurs C, ce serait un chagrin.

Ici, heureusement, un comportement indéfini vient à la rescousse. La norme C indique que les valeurs ne sont pas accessibles via des pointeurs dont le type ne correspond pas aux types actuels de ces valeurs. Autrement dit, si la valeur est écrite dans dst [0] , où dst est un pointeur int , alors les octets correspondants ne peuvent pas être lus via src [1] , où src est un double pointeur, car dans ce cas, nous essayons d'accéder valeur, qui est maintenant de type int , en utilisant un pointeur d'un type incompatible. Dans ce cas, un comportement indéfini se produirait. Cela est indiqué au paragraphe 7 de la section 6.5 de la norme ISO 9899: 1999 («C99») (dans la nouvelle édition 9899: 2018 ou «C17», le libellé n'a pas changé). Cette exigence est appelée la règle d'alias stricte. Par conséquent, le compilateur C est autorisé à agir sur l'hypothèse que les opérations d'accès à la mémoire conduisant à un comportement indéfini en raison de la violation de la règle d'alias stricte ne se produisent pas. Ainsi, le compilateur peut réorganiser les opérations de lecture et d'écriture dans n'importe quel ordre, car elles ne doivent pas accéder aux parties de mémoire qui se chevauchent. C'est à cela que sert l'optimisation du code.

En bref, la signification d'un comportement indéfini est la suivante: le compilateur peut supposer qu'il n'y aura pas de comportement indéfini et générer du code basé sur cette hypothèse. Dans le cas de la règle d'aliasing stricte - à condition que l'aliasing ait lieu, le comportement indéfini permet d'importantes optimisations qui seraient autrement difficiles à implémenter. De manière générale, chaque instruction dans les procédures de génération de code utilisées par le compilateur a des dépendances limitant l'algorithme de planification des opérations: une instruction ne peut pas être exécutée avant les instructions dont elle dépend, ou après les instructions qui en dépendent. Dans notre exemple, un comportement non défini élimine les dépendances entre les opérations d'écriture dans dst [] et les opérations de lecture «suivantes» de src [] : une telle dépendance ne peut exister que dans les cas où un comportement non défini se produit lors de l'accès à la mémoire. De même, le concept de comportement non défini permet au compilateur de supprimer simplement le code qui ne peut pas être exécuté sans entrer dans un état de comportement non défini.

Tout cela, bien sûr, est bon, mais un tel comportement est parfois perçu comme une trahison perfide par le compilateur. Vous pouvez souvent entendre la phrase: "Le compilateur utilise le concept de comportement indéfini comme excuse pour casser mon code." Supposons que quelqu'un écrive un programme qui additionne des entiers et craint un débordement - rappelez-vous le cas de Bitcoin . Il peut penser comme ceci: pour représenter des entiers, le processeur utilise du code supplémentaire, ce qui signifie que si un débordement se produit, cela se produira parce que le résultat sera tronqué à la taille du type, c'est-à-dire 32 bits Ainsi, le résultat d'un débordement peut être prédit et vérifié par un test.

Notre développeur conditionnel écrira ceci:

 #include <stdio.h> #include <stdlib.h> int add(int x, int y, int *z) { int r = x + y; if (x > 0 && y > 0 && r < x) { return 0; } if (x < 0 && y < 0 && r > x) { return 0; } *z = r; return 1; } int main(int argc, char *argv[]) { int x, y, z; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); if (add(x, y, &z)) { printf("%d\n", z); } else { printf("overflow!\n"); } return 0; } 

Essayons maintenant de compiler ce code en utilisant GCC:

 $ gcc -W -Wall -O9 testadd.c $ ./a.out 17 42 59 $ ./a.out 2000000000 1500000000 overflow! 

Ok, ça semble marcher. Essayez maintenant un autre compilateur, par exemple Clang (j'ai la version 6.0.0):

 $ clang -W -Wall -O3 testadd.c $ ./a.out 17 42 59 $ ./a.out 2000000000 1500000000 -794967296 

Quoi?

Il s'avère que lorsqu'une opération avec des types entiers signés conduit à un résultat qui ne peut pas être représenté par le type cible, nous entrons sur le territoire d'un comportement indéfini. Mais le compilateur peut supposer que cela ne se produit pas. En particulier, en optimisant l'expression x> 0 && y> 0 && r <x , le compilateur conclut que puisque les valeurs de x et y sont strictement positives, la troisième vérification ne peut pas être vraie (la somme de deux valeurs ne peut être inférieure à aucune d'entre elles), et vous pouvez ignorer toute cette opération. En d'autres termes, le débordement étant un comportement indéfini, il «ne peut pas se produire» du point de vue du compilateur et toutes les instructions qui dépendent de cet état peuvent être supprimées. Le mécanisme de détection des comportements indéfinis a tout simplement disparu.

La norme n'a jamais prescrit l'hypothèse que la «sémantique signée» (qui est en fait utilisée dans les opérations du processeur) est utilisée dans les calculs avec des types signés; cela s'est produit plutôt par tradition - même à l'époque où les compilateurs n'étaient pas assez intelligents pour optimiser le code, en se concentrant sur une plage de valeurs. Vous pouvez forcer Clang et GCC à appliquer la sémantique d' encapsulation aux types signés à l'aide de l'indicateur -fwrapv (dans Microsoft Visual C, vous pouvez utiliser -d2UndefIntOverflow-, comme décrit ici ). Cependant, cette approche n'est pas fiable, le drapeau peut disparaître lorsque le code est transféré vers un autre projet ou vers une autre architecture.

Peu de gens savent que les débordements de types de caractères impliquent un comportement indéfini. Ceci est indiqué au paragraphe 5 de la section 6.5 des normes C99 et C17:

Si une exception se produit lors de l'évaluation d'une expression (c'est-à-dire si le résultat n'est pas défini mathématiquement ou se situe en dehors de la plage de valeurs valides d'un type donné), le comportement n'est pas défini.

Pour les types non signés, cependant, la sémantique modulaire est garantie. Le paragraphe 9 de la section 6.2.5 dit ce qui suit:

Un débordement ne se produit jamais dans les calculs avec des opérandes non signés, puisqu'un résultat qui ne peut pas être représenté par le type entier non signé résultant est tronqué modulo un nombre qui est un de plus que la valeur maximale représentée par le type résultant.

Un autre exemple de comportement non défini dans les opérations avec des types signés est l'opération de division. Comme tout le monde le sait, le résultat de la division par zéro n'est pas déterminé mathématiquement, par conséquent, selon la norme, cette opération entraîne un comportement indéfini. Si le diviseur est nul dans l'opération idiv sur le processeur x86, une exception de processeur est levée. Comme les demandes d'interruption, les exceptions de processeur sont gérées par le système d'exploitation. Sur les systèmes de type Unix, tels que Linux, l'exception de processeur déclenchée par l'opération idiv est traduite en un signal SIGFPE , qui est envoyé au processus, et se termine par le gestionnaire par défaut (ne soyez pas surpris que «FPE» signifie «exception à virgule flottante» (exception dans opérations en virgule flottante), tandis que idiv fonctionne avec des entiers). Mais il y a une autre situation qui conduit à un comportement indéfini. Considérez le code suivant:

 #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int x, y; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); printf("%d\n", x / y); return 0; }  : $ gcc -W -Wall -O testdiv.c $ ./a.out 42 17 2 $ ./a.out -2147483648 -1 zsh: floating point exception (core dumped) ./a.out -2147483648 -1 

Et la vérité est: sur cette machine (le même x86 pour Linux), le type int représente une plage de valeurs de -2 147 483 648 à + 2 147 483 647. Si vous divisez -2 147 483 648 par -1, vous devriez obtenir + 2 147 483 648 Mais ce nombre n'est pas dans la plage des valeurs int . Par conséquent, le comportement n'est pas défini. Tout peut arriver. Dans ce cas, le processus est interrompu de force. Sur un autre système, en particulier avec un petit processeur qui n'a pas d'opération de division, le résultat peut varier. Dans de telles architectures, la division est effectuée par programme - en utilisant la procédure généralement fournie par le compilateur, et maintenant il peut faire tout ce qui lui plaît avec un comportement indéfini, car c'est ce qu'il est.

Je note que SIGFPE peut être obtenu dans les mêmes conditions et avec l'aide de l'opérateur modulo ( % ). Et en fait: en dessous se trouve la même opération idiv , qui calcule à la fois le quotient et le reste, de sorte que la même exception de processeur est déclenchée. Fait intéressant, la norme C99 dit que l'expression INT_MIN% -1 ne peut pas conduire à un comportement indéfini, car le résultat est défini mathématiquement (zéro) et tombe uniquement dans la plage de valeurs du type cible. Dans la version C17, le texte du paragraphe 6 de la section 6.5.5 a été modifié, et maintenant ce cas est également pris en compte, ce qui rapproche la norme de la situation réelle sur les plates-formes matérielles courantes.

Il existe de nombreuses situations non évidentes qui conduisent également à un comportement indéfini. Jetez un oeil à ce code:

 #include <stdio.h> #include <stdlib.h> unsigned short mul(unsigned short x, unsigned short y) { return x * y; } int main(int argc, char *argv[]) { int x, y; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); printf("%d\n", mul(x, y)); return 0; } 

Pensez-vous qu'un programme, suivant la norme C, devrait s'imprimer si nous transmettons les facteurs 45 000 et 50 000 à la fonction?

• 18 048
• 2 250 000 000
• Dieu sauve la reine!

La bonne réponse ... oui, toutes ces réponses! Vous avez peut-être argumenté comme ceci: comme un court non signé est un type non signé, il devrait prendre en charge le sémantique de wrapper modulo 65 536, car sur un processeur x86, la taille de ce type, en règle générale, est exactement de 16 bits (la norme autorise également une taille plus grande, mais en pratique, il s'agit toujours d'un type 16 bits). Puisque mathématiquement le produit est 2 250 000 000, il sera tronqué modulo 65 536, ce qui donne une réponse de 18 048. Cependant, en pensant de cette façon, nous oublions l'extension des types entiers. Selon la norme C (section 6.3.1.1, paragraphe 2), si les opérandes sont d'un type dont la taille est strictement inférieure à la taille de int , et les valeurs de ce type peuvent être représentées par le type int sans perte de bits (et nous avons juste ce cas: sur mon x86 sous Linux a une taille int de 32 bits, et il peut explicitement stocker des valeurs de 0 à 65 535), puis les deux opérandes sont convertis en int et l'opération est déjà effectuée sur les valeurs converties. A savoir: le produit est calculé comme une valeur de type int, et seulement en revenant de la fonction il est ramené en short non signé (c'est-à-dire, c'est à ce moment que la troncature modulo 65 536 se produit). Le problème est que mathématiquement le résultat avant la transformation inverse est de 2,250 millions, et cette valeur dépasse la plage de int , qui est un type signé. En conséquence, nous obtenons un comportement indéfini. Après cela, tout peut arriver, y compris des accès soudains de patriotisme anglais.

Cependant, dans la pratique, avec des compilateurs ordinaires, le résultat est de 18 048, car il n'y a toujours pas d'optimisation qui pourrait tirer parti du comportement indéfini de ce programme particulier (on pourrait imaginer des scénarios plus artificiels où cela causerait vraiment des problèmes).

Enfin, un autre exemple, maintenant en C ++:

 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <array> int main(int argc, char *argv[]) { std::array<char, 16> tmp; int i; if (argc < 2) { return EXIT_FAILURE; } memset(tmp.data(), 0, 16); if (strlen(argv[1]) < 16) { strcpy(tmp.data(), argv[1]); } for (i = 0; i < 17; i ++) { printf(" %02x", tmp[i]); } printf("\n"); } 

Ce n'est pas le typique «mauvais horrible strcpy () !» Pour vous. En effet, ici la fonction strcpy () n'est exécutée que si la taille de la chaîne source, y compris le zéro terminal, est suffisamment petite. De plus, les éléments du tableau sont explicitement initialisés à zéro, donc tous les octets du tableau ont une valeur donnée, indépendamment du fait qu'une grande ou une petite chaîne soit passée à la fonction. En même temps, la boucle à la fin est incorrecte: elle lit un octet de plus qu'elle ne devrait.

Exécutez le code:

 $ g++ -W -Wall -O9 testvec.c $ ./a.out foo 66 6f 6f 00 00 00 00 00 00 00 00 00 00 00 00 00 10 58 ffffffca ff ffffac ffffffc0 55 00 00 00 ffffff80 71 34 ffffff99 07 ffffffba ff ffffea ffffffd0 ffffffe5 44 ffffff83 fffffffd 7f 00 00 00 00 00 00 00 00 00 00 10 58 ffffffca ffffffac ffffffc0 55 00 00 ffffff97 7b 12 1b ffffffa1 7f 00 00 02 00 00 00 00 00 00 00 ffffffd8 ffffffe5 44 ffffff83 fffffffd 7f 00 00 00 ffffff80 00 00 02 00 00 00 60 56 (...) 62 64 3d 30 30 zsh: segmentation fault (core dumped) ./a.out foo ++? 

Vous pouvez naïvement vous opposer: eh bien, il lit un octet supplémentaire au-delà des limites du tableau; mais ce n'est pas si effrayant, car sur la pile cet octet est toujours là, il est mappé en mémoire, donc le seul problème ici est le dix-septième élément supplémentaire avec une valeur inconnue. Le cycle imprimera toujours exactement 17 entiers (au format hexadécimal) et se terminera sans aucune plainte.

Mais le compilateur a sa propre opinion à ce sujet. Il est bien conscient que la dix-septième lecture provoque un comportement indéfini. Selon sa logique, toute instruction ultérieure est dans les limbes: il n'y a aucune exigence qu'après un comportement indéfini quelque chose devrait exister du tout (formellement, même les instructions précédentes peuvent être attaquées, car le comportement indéfini fonctionne également dans la direction opposée). Dans notre cas, le compilateur ignorera simplement la vérification de condition dans la boucle, et il tournera pour toujours, ou plutôt, jusqu'à ce qu'il commence à lire en dehors de la mémoire allouée à la pile, après quoi le signal SIGSEGV fonctionnera.

C'est drôle, mais si GCC démarre avec des paramètres d'optimisation moins agressifs, il donnera un avertissement:

 $ g++ -W -Wall -O1 testvec.c testvec.c: In function 'int main(int, char**)': testvec.c:20:15: warning: iteration 16 invokes undefined behavior [-Waggressive-loop-optimizations] printf(" %02x", tmp[i]); ~~~~~~^~~~~~~~~~~~~~~~~ testvec.c:19:19: note: within this loop for (i = 0; i < 17; i ++) { ~~^~~~ 

À -O9, cet avertissement disparaît en quelque sorte. Le fait est peut-être qu'à des niveaux d'optimisation élevés, le compilateur applique de manière plus agressive le déploiement de la boucle. Il est possible (mais inexact) qu'il s'agit d'un bogue GCC (dans le sens d'une perte d'avertissement; ainsi, les actions de GCC ne contredisent en aucun cas la norme, car il ne nécessite pas l'émission de «diagnostics» dans cette situation).

Conclusion: si vous écrivez du code en C ou C ++, soyez extrêmement prudent et évitez les situations qui conduisent à un comportement indéfini, même quand il semble que «ça va».

Les types entiers non signés sont une bonne aide dans les calculs arithmétiques, car ils garantissent une sémantique modulaire (mais vous pouvez toujours rencontrer des problèmes liés à l'extension des types entiers). Une autre option - pour une raison impopulaire - est de ne pas écrire du tout en C et C ++. Pour plusieurs raisons, cette solution n'est pas toujours adaptée. Mais si vous pouvez choisir la langue dans laquelle écrire le programme, c'est-à-dire lorsque vous venez de démarrer un nouveau projet sur une plate-forme prenant en charge Go, Rust, Java ou d'autres langages, il peut être plus rentable de refuser d'utiliser C comme «langage par défaut». Le choix des outils, dont un langage de programmation, est toujours un compromis. Les pièges de C, en particulier le comportement indéfini dans les opérations avec des types signés, entraînent des coûts supplémentaires pour la maintenance ultérieure du code, qui sont souvent sous-estimés.