Kann der "Level 256 Bug" im Pacman-Spiel als unbehandelter Segfault angesehen werden?

51

Ich versuche, jemandem Segmentierungsfehler zu erklären, und ich habe über den Kill-Screen der Stufe 256 in Pacman nachgedacht, wie er durch einen Ganzzahlüberlauf ausgelöst wird und wie ähnlich das Verhalten dem in einer Segmentierung oft beschriebenen "unbekannten Zustand" ist Fehler.

Ich möchte sagen, dass dies ein gutes Beispiel für das ist, was ich einen "unbehandelten Fehler" nenne, aber ich würde lieber eine zweite Meinung einholen, bevor ich möglicherweise Fehlinformationen verbreite.

Ich habe versucht, es nachzuschlagen, aber alles, was ich bekomme, sind Dokumente über den Fehler selbst sowie die Zusammenarbeit zwischen Hipster Whale und Namco.

Würden Sie das Verhalten in Level 256 von Pacman als Beispiel für eine nicht behandelte Segmentierungsverletzung ansehen?

Braden Best
quelle
3
Hier ist eine genaue Beschreibung des Fehlers zusammen mit einem Patch, um ihn zu beheben: donhodges.com/how_high_can_you_get2.htm
abligh
26
Segmentierungsfehler werden von der Hardware ausgelöst, um unzulässigen Speicherzugriff zu vermeiden. Ich bin kein Experte für Pacman, aber die Hardware, auf der es lief, verfügte mit ziemlicher Sicherheit nicht über diese Sicherheitsfunktion.
BlueRaja - Danny Pflughoeft
3
Laut Wikipedia verwendete Pacman eine Z80. Z80s hatten definitiv keinen Speicherschutz.
Gort the Robot
Es ist kein Segfault - das System verfügte über keinerlei Speicherschutz. Der Fehler, den Pac-Man auf Level 256 erleidet, ist einfach ein Ganzzahlüberlauf, der vom Spielcode nicht korrekt behandelt wird.
bwDraco
3
Zu Ihrer Information, ich glaube nicht, dass dies ein Fehler ist. Ein Fehler ist ein Fehler in einem Computerprogramm oder -system, der zu einem falschen oder unerwarteten Ergebnis führt oder sich unbeabsichtigt verhält. Es wurde absichtlich so programmiert, da man das Gefühl hatte, dass niemand auf dieses Niveau kommen würde. In Wirklichkeit ist es nur schlechtes Software-Design.
Keltari

Antworten:

113

Definitiv nicht.

Der Zugriff auf eine Speicheradresse, die Sie nicht zugewiesen haben, ist immer ein Programmierfehler. Wenn Sie auf die Informationen reagieren, die Sie daraus erhalten, führt dies zu undefiniertem Verhalten, das sehr genau ist. Ich habe keine Ahnung, für welche Plattform der ursprüngliche Pac-Man geschrieben wurde, aber ich bin mir ziemlich sicher, dass er dieses Verhalten wie jede andere von Neumann-Maschine aufweist.

"Segmentierungsfehler" ist jedoch ein Fachbegriff für eine viel spezifischere Bedingung. Dies geschieht, wenn der Computer dies automatisch erkennt und den Vorgang beendet, anstatt undefiniertes Verhalten zuzulassen. Dies erfordert ein spezifisches (segmentiertes) Speichermodell mit ausgefeilten Besitzerkennzeichnungen. Ich glaube nicht , 1980 Arcade - Spiele , die hatten, und das Verhalten des Spiels in der Tat darauf hin , dass der Fehler wurde nicht erkannt, und das nicht definiertes Verhalten hat auftreten.

Kilian Foth
quelle
19
@ B1KMusic: Sie fragen sich wirklich : " Ist dieser Codefehler ein Beispiel für das Aufrufen von undefiniertem Verhalten durch Speicherzugriff außerhalb der Grenzen?" Und die Antwort lautet "Ja". Alle Rationalisierungen über das Erfassen, Ignorieren und Nichterhalten eines SIGSEGV-Signals sind nur verwirrend.
Leichtigkeit Rennen mit Monica
5
@ B1KMusic Nicht alle Pufferüberläufe führen zu einem Segfault. Es hängt davon ab, wie der Speicher zugewiesen wurde. Wenn der Speicher statisch zugewiesen ist (ein großer Puffer manuell in verschiedene Zonen aufgeteilt) und der Bereich unmittelbar hinter der letzten Ebene für etwas verwendet wurde (z. B. für Sprite-Grafiken), würde dies nicht zu Fehlern führen.
Ratschenfreak
6
Diese alten Arcade-Systeme verwendeten primitive Betriebssysteme, mit denen das Spiel fast die volle Kontrolle über die Hardware hatte, ähnlich wie in früheren DOS-Versionen. Die Idee eines Segfault in dieser Art von Architektur ist ein Nichtstarter, da davon ausgegangen wird, dass der eine laufende Prozess (Pac-Man) nicht den gesamten Speicher besitzt. Für weitere Informationen kann man das MAME-Projekt und seine Geschichte nachlesen .
20
Undefiniertes Verhalten ist keine Eigenschaft von Neumann-Maschinen, sondern eine Eigenschaft von C, der Programmiersprache. In Assemblersprache geschriebene Programme können kein undefiniertes Verhalten aufweisen, da das Verhalten von Assembleranweisungen immer genau definiert ist (auch wenn die Ergebnisse manchmal nicht genau angegeben sind).
Dietrich Epp
8
@Schneemann Auf einer Pac-Man-Maschine gibt es keine solche Schicht. Es gibt keinen Loader - das Spiel befindet sich im Execute-In-Place-ROM. Es gibt keine Speicherverwaltung - alles ist statisch. Es gibt keine "Dienste"; Das Spiel greift direkt auf Hardware zu und es gibt kein Byte Code auf dem System, das nicht Teil des Spiels ist und für das Spiel geschrieben wurde.
Hobbs
38

Es sieht so aus, als ob Sie "undefiniertes Verhalten" und "Segmentierungsfehler" verwechseln.

Es gibt keinen unbehandelten Segfault. Ein Segmentierungsfehler ist per Definition eine Fehlerbehandlung.

Wenn Sie kein Betriebssystem haben, das den fehlerhaften Speicherzugriff erkannt und den Vorgang aus Sicherheitsgründen abgebrochen hat, liegt kein Segmentierungsfehler vor.

Wenn überhaupt, dann ist dies ein ziemlich gutes Beispiel dafür, dass UB nicht immer zu einem Segfehler führt.

Leichtigkeit Rennen mit Monica
quelle
2
Um genau zu sein das O kann entscheiden , zu töten (dh unwiederbringlich) den Prozess. Moderne Betriebssysteme ziehen es stattdessen vor, FWIW zu beenden , was abgefangen und gehandhabt werden kann.
Edmz
@black: Habe ich das nicht gesagt?
Leichtigkeit Rennen mit Monica
15
Es darf nicht einmal "undefiniertes Verhalten" sein. Wenn Pacman in reiner Assembly geschrieben wurde, dann hat der Code genau das getan, was er auf eine absolut definierte Weise tun sollte. Kein undefiniertes Verhalten, sondern nur ein Fehler. Aus diesem Grund würde der Code auf allen Systemen mit einem perfekten Port des zugrunde liegenden Chipsatzes genauso ausgeführt.
Gort the Robot
@StevenBurnap: Das stimmt.
Leichtigkeit Rennen mit Monica
@black Was ist der Unterschied zwischen 'kill' und 'terminate'? Abgesehen von der Tatsache, dass 'kill' normalerweise UNIX-Vokabular ist und 'terminate' eher Windows-y ist?
Brandin
24

Keiner dieser Begriffe ist für einen Fehler in einem Arcade-Spiel geeignet, das in Assemblersprache programmiert wurde und ohne die Vorteile von Speicherschutzhardware oder Betriebssystem ausgeführt wird.

"Undefiniertes Verhalten" ist ein Begriff in C und verwandten Sprachen, der 1989 vom C-Normungsausschuss geprägt wurde. Code hat ein undefiniertes Verhalten, wenn die Sprachspezifikation nicht definiert, was er tun soll. In der Assemblersprache Z80 gibt es so etwas nicht: Die Wirkung jedes Opcodes bei jeder möglichen Eingabe ist genau definiert. Die konventionelle englische Bedeutung von "undefined behaviour" kann als zutreffend gelesen werden - der Kill Screen ist ein Verhalten, das nicht von den Leuten definiert wird, die das Spiel geschrieben haben -, aber ich würde es in diesem Zusammenhang nicht verwenden, weil es zu wahrscheinlich ist, dass es falsch ist Eindruck.

"Segmentierungsfehler" ist ein Begriff in POSIX, der sich letztendlich aus der Programmiersprache für PDP-Systeme ableitet. Segmentierungsfehler treten auf, wenn ein Programm versucht, auf eine Speicheradresse zuzugreifen, die keiner "Zuordnung" unterliegt: Die Hardware und das Betriebssystem erkennen dies und beenden das fehlerhafte Programm auf eine genau festgelegte Weise, die es dem Programm ermöglicht, sich zu erholen . So etwas wieDies könnte auf einen Fehler im Pac-Man-Spielprogramm zurückzuführen sein, da die Pac-Man-Platine nur etwas weniger als die Hälfte des 64-KB-Adressraums des Z80 mit ROM, RAM und Peripheriegeräten belegt. Ich konnte nicht herausfinden, was die reale Hardware tun würde, wenn die Software auf nicht zugeordneten Speicher zugreifen würde. Was auch immer es tun würde, wenn, wäre es unangemessen, als „Segmentation fault“ zu beschreiben, weil das „Betriebssystem“ für Pac-Man (soweit sie noch hat man) ist nicht eine Implementierung von Unix und wieder, es würde den falschen Eindruck erwecken.

Der Fehler der Stufe 256 greift indessen nicht auf nicht zugeordneten Speicher zu, so dass dies nicht möglich ist.

Es ist richtig zu sagen, dass das Spiel einen Fehler hat, der sich beim Aufsteigen auf Level 256 manifestiert. Es ist auch richtig zu sagen, dass die Hauptursache des Fehlers ein ganzzahliger Überlauf ist und dass seine Konsequenzen eine Speicherbeschädigung (oder gleichwertig Verstöße) sind des Gedächtnisses und der Typensicherheit ). Dies sind alles allgemeine CS-Begriffe, die ohne Bezugnahme auf eine bestimmte Sprache oder Betriebssystemumgebung definiert wurden.

Man kann auch genau beobachten, dass die Auswirkungen des Fehlers den Auswirkungen von Fehlern mit Speicherbeschädigung in einer modernen Umgebung ähnlich sind, die keine Segmentierungsfehler hervorrufen. Wenn Sie eine der Project Zero- Exploit-Beschreibungen lesen, werden Sie eine bemerkenswerte Ähnlichkeit mit Don Hodges ' Analyse des Pac-Man-Kill-Bildschirms feststellen .

Beachten Sie, dass ein Emulator, der den Kill-Bildschirm beim Laden der Pac-Man-ROMs nicht originalgetreu wiedergibt, die Spielhardware nicht richtig emuliert.

zwol
quelle
Der Ausdruck "undefiniertes Verhalten" wurde möglicherweise nicht genau so vor 1989 im Druck verwendet, aber die Idee, die dieser Ausdruck beschreibt, ist so alt wie die Programmierung selbst. Common Lisp: Die Sprache (Digital Press, 1984; ISBN 0-932376-41-X) verwendete die Wörter "es ist ein Fehler", um genau dasselbe zu bedeuten. ZB "Es ist ein Fehler, diese Funktion mit x <0 aufzurufen" bedeutete, dass der Programmierer nicht zulassen sollte, dass die Funktion mit x <0 aufgerufen wird, und dass die Implementierung buchstäblich alles tun durfte, was der Implementierer wollte, wenn Der Anwendungsprogrammierer hat die Anforderungen nicht erfüllt.
Solomon Slow
5
@jameslarge Ich verstehe, was Sie meinen, aber ich denke immer noch, dass es ein Fehler ist, dieses Konzept auf Pac-Man anzuwenden. Wir können sagen, dass der Kill Screen ein Bug ist, da sich das Spiel eindeutig nicht wie vom Designer beabsichtigt verhält. Wir können nicht sagen, dass das Spiel undefiniertes Verhalten provoziert hat , da es keine Sprachspezifikation gibt , die besagt , dass der Programmierer unter keinen Umständen X für einen Wert von X tun darf Viele Arcade-Spiele haben diese verwendet und AFAIK haben alle vorhersehbare Auswirkungen.)
zwol
1
Das ist die beste Antwort. "Undefiniertes Verhalten" bedeutet, dass der Codierer Code geschrieben hat, für den das Ergebnis basierend auf dem Standard nicht vorhergesagt werden kann. Wenn Pacman in einer Z80-Assembly geschrieben ist (und ich glaube, das war es), hatte der geschriebene Code eine vollständig definierte Bedeutung, unabhängig davon, ob das Programm etwas tat, was der Codierer nicht beabsichtigte.
Gort the Robot
8

Der Level-256-Fehler in Pac Man führt dazu, dass das Programm Daten liest , die über das Ende der beabsichtigten Tabelle hinausgehen, aber immer noch lesbar sind , und in Teile des Bildschirms schreibt, die über denjenigen liegen, die das Programm schreiben möchte, jedoch nicht noch gut in den Bereichen des Bildschirms, die das Programm schreiben darf . Andere Speicherbereiche sind nicht betroffen.

Der Grund, warum der Fehler das Spiel nicht mehr spielbar macht, ist, dass der Computer durch Überprüfen der Bildschirmanzeige feststellt, wann ein Spieler Punkte isst, und dass ein Level abgeschlossen ist, wenn der Spieler 244 Punkte gegessen hat. Durch das Überschreiben eines Teils des Bildschirms ist es dem Spieler aufgrund des Fehlers nicht möglich, 244 Punkte zu essen. Infolgedessen wird das Spiel dem Spieler niemals das Abschließen des Levels und das Neuladen des Bildschirms mit Punkten gutschreiben.

Superkatze
quelle
1
Wenn du dich in Level 256 tötest, erscheinen die Punkte erneut, aber du verlierst keine.
Ave
@ardaozkal: Die Level-Draw-Routine löscht mehr als 100 Punkte und zeichnet ein paar. Wenn ein Spieler genug Leben hätte, wäre es irgendwann möglich, genug Punkte zu essen, um ein Level voranzutreiben, aber das würde mehr als 30 Leben erfordern.
Supercat
Ich erinnere mich, dass ich ein Video gesehen habe, in dem der Spieler genug Leben hatte, und er es geschafft hat ... und ich habe es gerade gefunden .
Ave
@ardaozkal: Wie viele Leben sind erforderlich, um das Level zu beenden, und wie viele Leben kann ein Spieler auf einer nicht modifizierten Maschine haben?
Supercat
Auf einem nicht modifizierten Computer können Sie nicht einmal Level 256 erreichen.
Ave
1

Wie gesagt nein, es ist kein Seg-Fehler. Ich werde hinzufügen, warum das Problem auftritt: Es ist ein Überlauf .

Die Ebenennummern werden in einem Byte gespeichert, sodass der Bereich zwischen 0 und 255 liegt. Jedes Mal, wenn Sie ein Level abschließen, wird der Zähler inkrementiert. Auf Stufe 256 ist der Zähler aufgrund des Überlaufs tatsächlich 0.

Das Spiel versucht jedoch, einige Früchte am unteren Rand des Levels anzuzeigen. Die Fruchtanzahl / -art ist abhängig vom Füllstand. Die Formel zeigt eine Frucht pro abgeschlossenem Level unter Level 8 an. Entsprechend dem Zähler sind Sie auf Level 0, also unter 8. Der Test ist dann wahr und Sie müssen 255 Früchte drucken (der alte Level-Wert). Welches ist unmöglich und gibt diesen fehlerhaften Bildschirm.

Romain Picot
quelle