Das Spielen von Text-Abenteuerspielen ist pure Freude, aber die Freude ist ziemlich hirnfressend. Heute verfügen wir jedoch über alle diese Kapazitäten für nicht genutzte Prozessoren.
Was ist, wenn wir den Computer dazu bringen, das Spiel selbstständig zu durchlaufen, und wir uns einfach in den Stuhl zurücklehnen und zusehen müssen? Wir brauchen nicht einmal all diese neuen neuronalen Netze, sondern eher einfache Brute Force.
Wir werfen einfach einen Haufen halbzufälligen Text am Eingang des Textspiels ab und sehen, was passiert. In der Welt der Informationssicherheit spricht man von Fuzzing.
Das Ziel wird die Z-Machine sein, ein Interpreter für virtuelle Maschinen, der 1979 von Joel Berez und Mark Blanck entwickelt wurde und das Herzstück der Infocom Games darstellt. Dies ist ein ideales Ziel für Fuzzing-Abenteuer, da es gut dokumentiert ist und viele unterstützende Tools und Bibliotheken enthält.
Zork startete auf dem Atari 800XL (Sebastian Grunwald, CC 3.0)Mini Zork
Das Spiel, das wir auf den
Kopf stellen werden -
MINI-ZORK-1: The Great Underground Empire . Dies ist eine Demoversion von Infokomovskys erstem Zorka, der zum Booten von einer Kassette und nicht von einer Diskette entwickelt wurde. Im Wesentlichen war es eine Anzeige, die in der Beilage des britischen Commodore-User-Magazins
Zzap! 64 aus den 1990er Jahren veröffentlicht wurde.
Für diejenigen, die Zork noch nicht gespielt haben:
MINI-ZORK I: The Great Underground Empire Copyright (c) 1988 Infocom, Inc. All rights reserved. ZORK is a registered trademark of Infocom, Inc. Release 34 / Serial number 871124 West of House You are standing in an open field west of a white house, with a boarded front door. You could circle the house to the north or south. There is a small mailbox here. >
Tipp> fordert den Benutzer auf, Befehle wie OPEN MAILBOX oder GO NORTH einzugeben, um im Spiel voranzukommen. Das Ziel ist es, "die Schätze des Great Underground Empire zu finden und sie in deiner Beutebox zu sammeln", während du Rätsel löst und Feinde stürzt.
Spielen wir die Jagd nach Verben (und Nomen)
Das Benutzerhandbuch mit Zork enthält Beispiele für mögliche Befehle wie OPEN THE WOODEN DOOR und WARLOCK, TAKE THE SPELL SCROLL THEN FOLLOW ME. Die Benutzer mussten jedoch selbstständig raten, wie sie ein bestimmtes Rätsel lösen sollten.
Verben wie GET und DROP (GET / DROP) sind ziemlich offensichtlich, ebenso wie die standardmäßigen acht Kardinalpunkte und up / down (UP / DOWN) und gleichzeitig in und out (IN / OUT). Die Benutzer mussten aber auch ATTACK, POOL und PRAY verwenden und magische Wörter aussprechen, die nicht im Handbuch enthalten waren. Die Situation, in der das Spiel den Spielern nicht genügend Hinweise gab, nannten sie spöttisch "Verbjagd".
Um Befehle zu generieren, benötigt Fuzzer eine Liste von Wörtern, die vom Spiel akzeptiert werden, sein Vokabular. Die Z-Maschine wählt diese Liste als Spielwörterbuch aus (sie befindet sich an einem Standardort in der Datei jedes Spiels).
(Dies ist eine Art Betrug, ja! Aber es gibt wirklich keine andere Möglichkeit, dem Computer zu erklären, welche Wörter zu verwenden sind, da einige Verben an keiner Stelle im Text erwähnt werden.)
Der einfachste Weg, Befehle zu generieren, besteht darin, zufällig ein oder mehrere Wörter zu verwenden, in unserem Fall ein oder zwei. Wir wissen nicht, welche Wörter Verben sind und welche Substantive. Daher generieren wir viele seltsame Befehle wie "OOPS SEHEN" und "TREIBER UNTEN".
Offensichtlich ist dies ziemlich ineffizient, da wir N * N-Kombinationen (wobei N die Größe des Vokabulars ist) sortieren müssen, um genau den Befehl wie „KILL TROLL“ zu finden.
Wir können jedoch ein wenig schummeln. Wir scannen alle Wörter in der Textausgabe des Spiels und wählen die Wörter aus, die in unserem Wörterbuch enthalten sind. Und wählen Sie ein Wort aus dieser Liste (anstelle eines vollständigen Wörterbuchs). Wenn wir zum Beispiel NORTH, WEST, HOUSE und MAILBOX im Text sehen, verwenden wir diese Wörter mit größerer Wahrscheinlichkeit.
Suchen Sie nach Story-Markern
Wenn wir nur zufällige Befehle geben, bekommen wir eine Menge Unsinn, auf den der Parser schwört:
>about painti [ !] >leathe guideb [ "leathe" , .]
(Wortschatzwörter sind in der Z-Maschine nicht länger als sechs Zeichen, daher erzeugen wir Wörter wie „leathe“.)
Ein solcher Stampfen an Ort und Stelle wird jedoch ewig dauern. Wie können wir feststellen, welche Wege vielversprechender sind als andere? Wir werden nach Markern suchen, um die Geschichte zu promoten.
Die Z-Machine verfügt über eine PRINT-Anweisung, mit der Text auf der Konsole gedruckt wird. Oft handelt es sich dabei um Fragmente von Beschreibungen wie "West of the House" und "Bottle Shattered". Wir werden jeden von ihnen als Marker registrieren.
Immer wenn wir einen neuen Marker sehen, speichern wir die aktuelle Passage - eine Liste der Teams, die wir im aktuellen Spiel durchgeführt haben.
Wir ordnen diese Liste dem aktuellen Marker zu, damit wir (hoffentlich) den gleichen Text in der Ausgabe erhalten, nachdem wir die gleichen Befehle abgespielt haben.
Bei jedem Spielstart wird ein bestimmter Zielmarker und damit die dazugehörige Passage ausgewählt. Der Suchalgorithmus wählt häufiger neue als alte Marker aus.
Wir werden die Teams nicht wörtlich in jedem Spiel wiederholen, aber wir werden ein paar zufällige Teams hinzufügen und die Reihenfolge mischen. Wenn wir einen neuen Marker sehen, erhöhen wir den Parameter "Erfolg", dessen Wachstum zeigt, dass es möglich ist, die Befehlsliste seltener zu ändern. Wenn dieser Parameter ausreichend wächst, markieren wir diesen Marker als „stabil“, da wir eine vorhersehbare Passage haben, die zu ihm führt.
Auf der Suche nach einem kurzen Weg
Die Art und Weise, wie wir durch das Spiel gehen, ist oft wirkungslos. Hier ist die Liste der Befehle, die zum Generieren des Markers "Wheeeeeeeeee !!!!!" verwendet wurden:
curse, art, body gate, incant count, the, the egg, repent, from the, the consum, what, leathe, trap- see, breath here, what intnum, about here, leathe guideb, about, about here, pot, here, see, here about, about, self, here about, mangle, see, rug, the, reply, elvish, say, stilet beetle, say toss, pray, gate about, what bolt, guideb, wooden, say knock, say sit, trail and, here, pray leathe, intnum, one, pray one, jump
Alles was wir wirklich tun müssen, ist den letzten Befehl einzugeben: JUMP (oder DIVE). Der Suchalgorithmus weiß jedoch nicht, welche der vorherigen Befehle für die Anzeige von "Wheeeeeeeeee !!!!!" erforderlich sind.
Wir müssen die Passage reduzieren - um sie so kurz wie möglich zu halten. Wenn wir eine Markierung sehen, ersetzen wir die zugehörige Passage nach Möglichkeit durch eine kürzere Liste von Befehlen. Dies führt uns schneller zum Zielmarker, sodass wir nach Erreichen des Ziels mehr Experimentierbewegungen ausführen können.
Viele Marker, wie zum Beispiel "Wheeeeeeeeee !!!!!", sind nicht interessant, da wir sie zu Beginn des Spiels in einer Runde erreichen können. Indem wir die Liste der Befehle reduzieren, können wir möglicherweise bestätigen, dass dies der Fall ist, und sie somit aus der Liste der potenziellen Zielmarkierungen entfernen.
Mehr als Worte
Da wir direkten Zugriff auf den internen Status der Z-Maschine haben, können wir etwas anderes als die Textausgabe verwenden, um unsere Suche zu steuern. Beispielsweise können wir beheben, wann sich ein Objekt von Raum zu Raum bewegt hat oder wann sich andere Eigenschaften und Flags für das Objekt geändert haben. Nennen Sie es VM-Markierungen (Virtual Machine Markers) und korrigieren Sie sie parallel zu Textmarkierungen:
@mv_30_15 (#30) #15 @f_176_10_1 "" (10) ""(#176)
Wir brauchen das, weil die Textausgabe nicht die ganze Geschichte erzählt. Wenn Sie zum Beispiel ein Schwert oder eine Lampe aufnehmen, erreichen Sie dieselbe Markierung „Taken“. Die VM-Markierung teilt dem Suchalgorithmus mit, wann ein neuer Status der virtuellen Maschine erreicht wurde, zum Beispiel, wenn ein Spieler in einen neuen Raum wechselt oder ein Objekt aufgenommen oder weggeworfen wurde.
Eine virtuelle Maschine brechen
Den Stand des Spiels zu untersuchen, ist ein ziemlich langsamer Prozess. Eine der ersten Aufgaben im Spiel ist es, den Troll zu töten, wodurch Sie nicht weiter gehen können. Zuvor muss der Spieler jedoch etwas höher im Haus ein Schwert finden.
Um den Suchprozess zu beschleunigen, knacken wir die Z-Maschine und bringen den Stand des Spiels auf das, was wir zuvor gesehen haben. Wir haben beispielsweise versehentlich ein Schwert in die Hand eines Spielers geschoben, wodurch es möglich wurde, den Befehl "STAB" (Stich) erfolgreich auszuführen. ("ATTACK TROLL" funktioniert nur, wenn "WITH SWORD" hinzugefügt wird. "STAB" (Stechen) impliziert jedoch bereits das Vorhandensein eines scharfen Objekts und funktioniert daher.)
Wir knacken nur stabile Marker. Wenn wir das Spiel also zuverlässig wiederholen können und die Hände des Spielers sich als Schwert erweisen, können wir diesen Zustand hacken: "Das Schwert befindet sich in den Händen des Spielers". Dann können wir die Teams, mit denen das Schwert gehoben wurde, mit den Teams kombinieren, die den Kerker hinuntergingen, um herauszufinden, auf welchem Weg wir den Troll angreifen müssen.
Das Beispiel des Trolls ist vor allem der Jesuit, weil es in der Regel mehrere Schläge dauert, um es zu beenden, und jeder Angriff ein zufälliges Ergebnis liefert. Da unser Algorithmus kürzere Pässe bevorzugt, ist es vorzuziehen, sich an eine optimistische Vorhersage über unsere Kampffähigkeiten zu halten.
Nach 530.000 Komplettlösungen und 10.600.000 Teams (200 Teams pro Spiel) haben wir endlich herausgefunden, wie wir den Troll angreifen können:
north, east, open window, into, west, light, lift trap, small hi, get, west, light, tug large, lift trap, down, north, stab
Es gibt immer noch ein paar unnötige Befehle und wir verstehen immer noch nicht, dass wir ihn mehrmals schlagen müssen, aber wir können damit umgehen.
Tödliches Hobby
Der Suchalgorithmus kennt den Unterschied zwischen dem Sammeln von Objekten, dem Werfen von Objekten und dem Bewegen eines Spielers von Raum zu Raum nicht. Der einzige Weg, wie er Fortschritt definiert, besteht darin, Marker der Geschichte fortschreiten zu sehen.
Dadurch entwickelt sich schnell im Suchalgorithmus ein Gespür für ... Mord! Insbesondere, um einen Spieler zu töten, weil es so einfach und unkompliziert ist: Geben Sie "ATTACK" ein:
>attack [ ] , ! **** **** , , . , . c-. , .
In Mini Zorka ist der erste Tod nicht das Ende des Spiels, der Spieler teleportiert sich an einen anderen Ort und Ihre Sachen sind verstreut. Für einen Suchalgorithmus ist der Tod einfach ein Objekt, das sich von einem Raum in einen anderen bewegt und Markierungen für die Bewegung der Geschichte entlang des Weges erstellt. Dieses Hobby führt dazu, dass andere lustige Fehler im Spiel aufgedeckt werden, beispielsweise die Fähigkeit des Spielers, seine Hände in den Fluss zu werfen.
Das Spiel erzielt 0 bis 350 Punkte, basierend auf dem Lösen von Rätseln und dem Sammeln von Schätzen. Wenn ein Spieler stirbt, wird er um 10 Punkte reduziert. Wir können den Account als Heuristik verwenden, aber dies kann riskantes Verhalten übermäßig reduzieren - die Liebe, in dunkle Orte zu wandern oder Trolle zu bekämpfen.
Der Suchalgorithmus interessiert sich auch sehr für das, was der Spieler nicht sieht, wie NPCs, die sich zwischen Räumen bewegen. Der Marker @ mv_112_37 zeigt beispielsweise die Bewegung eines Diebes in einen bestimmten Raum an. Der Suchalgorithmus schafft es, diesen Marker durch wiederholtes Ausführen von Z- oder WAIT-Befehlen zu reproduzieren, wobei im Wesentlichen erwartet wird, dass der Dieb den Zielraum erreicht.
Er mag es auch, Objekte an verschiedenen Orten aufzunehmen und wegzuwerfen, weil jede Bewegung des Objekts ein neuer Marker ist. Wer weiß? Vielleicht führt das Werfen dieses Blattes auf einem Waldweg zum Sieg im Spiel! (Sprecher: nein, das wird es nicht.)
Fuzzing identifiziert ausnahmslos Fehler im Programm, und dieses Spiel ist nicht anders, obwohl es weiterhin besteht. Er fand heraus, wie man das Wort "Clrthatrqdc" zu Beginn des Spiels generiert:
>tie up [ ] With a Clrthatrqdc!?!
Dies scheint eine nicht initialisierte Variable zu sein, die nicht-textuelle Daten anzeigt. Die Kodierung von komprimiertem Text in der Z-Maschine erfolgt größtenteils in alphabetischer Reihenfolge, da Sie nicht so viel zufälligen Müll sehen, als wenn Sie versuchen, eine Binärdatei als ASCII-Datei zu drucken. (Derzeit ist dieses Wort
bei Google nur zweimal vorhanden (
bereits viermal, ca. übersetzt ).)
Komplettlösung
Um das Spiel zu gewinnen, müssen wir unsere geplünderten Waren zurück in die Beutebox ziehen und jedes Objekt hineinstecken. Es wird lange dauern, bis unser einfacher Suchalgorithmus auf dieses Verhalten stößt, insbesondere da er dazu neigt, Energie und Zeit zu verschwenden, um Objekte von Raum zu Raum zu bewegen.
Die Komplizierung eines Algorithmus aus zufälligen Recherchen erfordert Zeit, daher müssen wir beim Hinzufügen neuer Funktionen selektiv vorgehen. Wir wollen auch a priori Wissen im Spiel vermeiden - mit anderen Worten, wir wollen nur ein bisschen schummeln.
Wenn Sie experimentieren möchten,
schauen Sie sich den Quellcode auf GitHub an , der
JSZM (den Interpreter von Z-Machine Daniel Legenbauer) verwendet. Viele
Spiele sind verfügbar (nur Versionen bis zu 3 werden unterstützt.)
Das Graham Nelson
Z-Machine Standards- Dokument, das sich seit einigen Jahrzehnten mit der Z-Machine befasst, ist ebenfalls verfügbar.
Und muss ich Z-Machine-Unterstützung für
8bitworkshop hinzufügen ? Geben Sie mir Bescheid!