Le «bug de niveau 256» dans le jeu de Pacman peut-il être considéré comme une erreur de segmentation non gérée?

51

J'essaie d'expliquer les erreurs de segmentation à quelqu'un, et je pensais au kill-screen de niveau 256 dans Pacman, à la manière dont il est déclenché par un dépassement d'entier et à la similitude de son comportement avec "l'état inconnu" souvent décrit dans une segmentation. faute.

Je tiens à dire que c’est un bon exemple de ce que j’appelle une "erreur de segmentation non gérée", mais je préférerais obtenir un deuxième avis avant de propager de fausses informations.

J'ai essayé de le rechercher, mais tout ce que j'obtiens, ce sont des documents sur le bogue lui-même, ainsi que la collaboration entre Hipster Whale et Namco.

Alors, considéreriez-vous le comportement au niveau 256 de Pacman comme un exemple de violation de segmentation non gérée?

Braden Best
la source
3
Voici une description exacte du bogue, ainsi qu'un correctif pour le résoudre: donhodges.com/how_high_can_you_get2.htm
abligh
26
Les erreurs de segmentation sont générées par le matériel afin d'éviter tout accès illégal à la mémoire. Je ne suis pas un expert de Pacman, mais le matériel sur lequel il était installé ne comportait presque certainement pas cette fonction de sécurité.
BlueRaja - Danny Pflughoeft
3
Selon Wikipédia, Pacman a utilisé un Z80. Z80s n'avait certainement pas de protection de la mémoire.
Gort the Robot
Ce n'est pas une erreur de segmentation: le système ne dispose d'aucune forme de protection de la mémoire. La faute de Pac-Man au niveau 256 est simplement un dépassement d’entier qui n’est pas correctement géré par le code du jeu.
bwDraco
3
Pour votre information, je ne pense pas que cela soit considéré comme un bug. Un bogue est une défaillance ou une anomalie d'un programme informatique ou d'un système qui entraîne un résultat incorrect ou inattendu, ou un comportement imprévu. C'était intentionnellement programmé de cette façon, car on pensait que personne n'atteindrait ce niveau. En réalité, sa conception logicielle est juste médiocre.
Keltari

Réponses:

113

Définitivement pas.

L'accès à une adresse mémoire que vous n'avez pas allouée est toujours une erreur de programmation. Et agir sur les informations que vous en retirez produit un comportement indéfini, c'est beaucoup. Je ne sais pas du tout à quelle plate-forme le Pac-man original a été écrit, mais je suis presque sûr qu'il a eu ce comportement, comme n'importe quelle autre machine von Neumann.

Cependant, "faute de segmentation" est un terme technique désignant une condition beaucoup plus spécifique. Cela se produit lorsque l'ordinateur détecte automatiquement que cela se produit et met fin au processus plutôt que de laisser un comportement indéfini se produire. Cela nécessite un modèle de mémoire spécifique (segmenté) avec un étiquetage de propriété sophistiqué. Je ne pense pas que les jeux d'arcade de 1980 aient eu cela, et en fait le comportement du jeu suggère que l'erreur n'a pas été détectée, et le comportement indéfini s'est produit.

Kilian Foth
la source
19
@ B1KMusic: Vous demandez vraiment "ce code 'bug' est-il un exemple d'invocation d'un comportement indéfini via un accès mémoire hors limite", et la réponse est "oui". Toute rationalisation consistant à capter, ignorer, ne pas recevoir de signal SIGSEGV est source de confusion.
Courses de légèreté avec Monica
5
@ B1KMusic tous les dépassements de mémoire tampon ne provoquent pas un segfault. Cela dépend de la façon dont la mémoire a été allouée. Si la mémoire est allouée de manière statique (un grand tampon divisé manuellement en différentes zones) et que la zone immédiatement derrière le dernier niveau a été utilisée pour quelque chose (comme des graphiques de sprite), elle ne serait pas par défaut.
Monstre à cliquet
6
Ces anciens systèmes d'arcade utilisaient des systèmes d'exploitation primitifs qui donnaient au jeu un contrôle quasi total sur le matériel, à l'instar des premières versions de DOS. L'idée d'une erreur de segmentation dans ce type d'architecture est sans fondement, car elle suppose que le processus en cours d'exécution (Pac-Man) ne possède pas toute la mémoire. Pour plus d'informations, vous pouvez en savoir plus sur le projet MAME et son historique.
20
Le comportement indéfini n'est pas une propriété des machines de von Neumann, c'est une propriété de C, le langage de programmation. Les programmes écrits en langage assembleur ne peuvent pas présenter de comportement indéfini, car le comportement des instructions en langage assembleur est toujours bien défini (même si les résultats sont parfois non spécifiés).
Dietrich Epp
8
@Snowman, une telle couche n'existe pas sur une machine Pac-Man. Il n'y a pas de chargeur - le jeu est en ROM d'exécution sur place. Il n'y a pas de gestion de la mémoire - tout est statique. Il n'y a pas de "services"; le jeu accède directement au matériel et il n'y a pas un octet de code sur le système qui ne fasse pas partie du jeu et qui soit écrit pour le jeu.
Hobbs
38

Il semble que vous confondiez "comportement indéfini" et "erreur de segmentation".

Une erreur de segmentation non gérée n'existe pas. Une erreur de segmentation est la gestion des erreurs, par définition.

Si aucun système d'exploitation n'a détecté le mauvais accès à la mémoire et mis fin au processus pour des raisons de sécurité, vous ne présentez pas d'erreur de segmentation.

Si quelque chose, alors, c'est un assez bon exemple de la façon dont UB ne résulte pas toujours en une erreur de segmentation.

Courses de légèreté avec Monica
la source
2
Pour être précis, le système d'exploitation peut décider de mettre fin au processus (c'est-à-dire de façon irrécupérable). Les systèmes d’exploitation modernes préfèrent plutôt y mettre fin , ce qui peut être capturé et traité, FWIW.
Edmz
@black: N'est-ce pas ce que j'ai dit?
Courses de légèreté avec Monica
15
Ce n'est peut-être même pas un "comportement indéfini". Si Pacman a été écrit en assemblage pur, alors le code a fait exactement ce qu'on lui a dit de faire d'une manière parfaitement définie. Pas un comportement indéfini, mais simplement un bug. En tant que tel, le code fonctionnerait exactement de la même manière que sur tout système possédant un port parfait du jeu de puces sous-jacent.
Gort the Robot
@StevenBurnap: C'est vrai.
Courses de légèreté avec Monica
@black Quelle est la différence entre 'kill' et 'terminate'? Autre que le fait que 'tuer' est normalement un vocabulaire UNIX et que 'terminer' est plus Windows-y?
Brandin
24

Aucun de ces termes n'est approprié pour un bogue dans un jeu d'arcade programmé en langage assembleur et fonctionnant sans le matériel de protection de la mémoire ou le système d'exploitation.

Le "comportement indéfini" est un terme technique en C et dans les langages apparentés, inventé par le comité des normes C en 1989. Le code a un comportement indéfini lorsque la spécification de langage ne définit pas ce qu'il va faire. Le langage d'assemblage Z80 n'existe pas: l'effet de chaque opcode avec toutes les entrées possibles est bien défini. La signification anglaise classique de "comportement indéfini" peut être lue pour s'appliquer - l'écran de suppression est un comportement qui n'a pas été défini par les auteurs du jeu - mais je ne l'utiliserais pas dans ce contexte car il est trop probable qu'il donne le mauvais impression.

"Erreur de segmentation" est un terme technique de POSIX, dérivé du jargon de la programmation de système PDP. Les erreurs de segmentation se produisent lorsqu'un programme tente d'accéder à une adresse de mémoire qui n'est pas "mappée" sur quoi que ce soit: le matériel et le système d'exploitation le détectent et arrêtent le programme défectueux, d'une manière soigneusement définie qui permet au programme de récupérer . Quelque chose commecela aurait pu être le résultat d'un bogue dans le programme de jeu Pac-Man, car la carte de circuit imprimé Pac-Man n'occupe qu'un peu moins de la moitié de l'espace d'adressage de 64 ko de la Z80 avec ROM, RAM et périphériques, mais je n'ai ' t été capable de savoir ce que le matériel réel ferait si le logiciel tentait d’accéder à une mémoire non mappée. Quoi qu’il en soit, il serait inapproprié de le qualifier de "défaut de segmentation", car le "système d’exploitation" de Pac-Man (dans la mesure où il en possède même un) n’est pas une implémentation de Unix et, là encore, donnerait la mauvaise impression.

Le bogue de niveau 256, quant à lui, n’accède pas à la mémoire non mappée, il est donc inutile.

Il est exact de dire que le jeu a un bogue qui se manifeste en passant au niveau 256. Il est également exact de dire que la cause première du bogue est un débordement d’entier et que ses conséquences sont une corruption de la mémoire (ou, de manière équivalente, des violations). de mémoire et type de sécurité ). Ce sont tous des termes CS à usage général définis sans référence à un langage ou à un environnement de système d'exploitation particulier.

Il est également exact d'observer que les effets du bogue ressemblent aux effets, dans un environnement moderne, de bogues de corruption de mémoire qui ne provoquent pas d' erreurs de segmentation. Si vous lisez l'un des écrits sur l'exploit de Project Zero , vous verrez une similarité remarquable avec l' analyse de Don Hodges sur l'écran de suppression de Pac-Man .

Notez qu'un émulateur qui ne reproduit pas fidèlement l'écran de neutralisation lorsqu'il est alimenté par les ROM Pac-Man n'émule pas correctement le matériel de jeu.

zwol
la source
L'expression "comportement indéfini" n'a peut-être pas été utilisée de cette manière avant 1989, mais l'idée que cette expression décrit est aussi ancienne que la programmation elle-même. Common Lisp: The Language (Presse numérique, 1984; ISBN 0-932376-41-X) utilisait les mots "c'est une erreur" pour signifier exactement la même chose. Par exemple: « Il est une erreur d'appeler cette fonction avec x <0 » signifie que le programmeur ne doit pas permettre à la fonction à appeler avec x <0 et que la mise en œuvre a été autorisé à faire littéralement tout l'implémenteur voulait faire si le programmeur de l'application ne s'est pas conformé.
Salomon Slow
5
@jameslarge Je comprends ce que vous voulez dire, mais je pense toujours que c'est une erreur d'appliquer ce concept à Pac-Man. Nous pouvons dire que l'écran de suppression est un bug, car le jeu ne se comporte clairement pas comme prévu par le concepteur. Nous ne pouvons pas dire que le jeu a provoqué un comportement indéfini , car il n'y a aucune spécification de langage pour dire "le programmeur ne peut faire X" pour aucune valeur de X. (Je suppose que l'utilisation des opcodes non documentés Z80 pourrait être admissible, sauf beaucoup de jeux d'arcade ont utilisé ceux-ci et autant que je sache, ils ont tous des effets prévisibles.)
jeudi
1
C'est la meilleure réponse. "Comportement indéfini" signifie que le codeur a écrit du code pour lequel le résultat ne peut pas être annoncé sur la base du standard. Si Pacman est écrit en assembleur Z80 (et je crois que c'était le cas), alors le code écrit avait une signification entièrement définie, que le programme fasse ou non quelque chose que le codeur n'avait pas l'intention de faire.
Gort the Robot
8

Le bogue de niveau 256 dans Pac Man se traduit par la lecture par le programme de données dépassant la fin de la table voulue, mais constituant toujours une mémoire lisible , et écrivant dans des parties de l'écran dépassant celles que le programme a l'intention d'écrire, mais toujours bien dans les zones de l'écran que le programme est autorisé à écrire . Aucune autre zone de mémoire n'est affectée.

La raison pour laquelle le bogue rend le jeu injouable est que la machine détermine le moment où un joueur mange des points en examinant ce qui est à l'écran et décide qu'un niveau est terminé lorsque le joueur a mangé 244 points. En écrasant une partie de l'écran, le bogue empêche le joueur de manger 244 points. par conséquent, le jeu ne créditera jamais le joueur d’avoir terminé le niveau et ne rechargera pas l’écran de points.

supercat
la source
1
Lorsque vous vous tuez au niveau 256, les points réapparaissent, mais vous n'en perdez aucun.
Ave
@ardaozkal: La routine d'élaboration des niveaux efface plus de 100 points et en dessine quelques-uns. Si un joueur avait suffisamment de vies, il serait éventuellement possible de manger suffisamment de points pour progresser d'un niveau, mais cela nécessiterait plus de 30 vies.
Supercat
Je me souviens de regarder une vidéo où le joueur avait assez de vies, et il a réussi ... et je viens de le trouver .
Ave
@ardaozkal: Combien de vies sont nécessaires pour effacer le niveau et combien de vies un joueur peut-il avoir sur une machine non modifiée ?
Supercat
Vous ne pouvez même pas atteindre le niveau 256 sur une machine non modifiée.
Ave
1

Comme dit précédemment non, ce n'est pas une faute distincte. J'ajouterai pourquoi le problème survient: c'est un débordement .

Les numéros de niveau sont stockés sur un octet, la plage est donc comprise entre 0 et 255. Chaque fois que vous terminez un niveau, le compteur est incrémenté. Au niveau 256, le compteur est en fait 0 à cause du débordement.

Cependant, le jeu tente d'afficher des fruits en bas du niveau. Le nombre / type de fruits dépend du niveau. La formule affiche un fruit par niveau fini en dessous du niveau 8. Selon le compteur, vous êtes au niveau 0 donc en dessous de 8. Le test est alors valide et vous devez imprimer 255 fruits (l'ancienne valeur du niveau). Ce qui est impossible et donne cet écran en panne.

Romain Picot
la source