Fuzzing Z-machines

Playing text adventure games is pure pleasure, but pleasure is quite brain-consuming. But today we have all of these idle processor capacities.



What if we make the computer go through the game on our own, and we just have to lean back in the chair and watch? We don’t even need all these newfangled neural networks, rather simple brute force.



We just drop a bunch of semi-random text at the entrance of the text game and see what happens. In the world of information security, this is called fuzzing.



The goal will be the Z-Machine, a virtual machine interpreter developed by Joel Berez and Mark Blanck in 1979, the heart of the Infocom Games. This is an ideal target for adventuring fuzzing, as it is well documented and has many supporting tools and libraries.







Zork launched on the Atari 800XL (Sebastian Grunwald, CC 3.0)

Mini Zork

The game that we will fuzz - MINI-ZORK-1: The Great Underground Empire . This is a demo version of Infokomovsky first Zorka, designed to boot from a cassette, not from a floppy disk. Essentially, it was an ad published in the 1990s supplement to Commodore’s British user magazine, Zzap! 64 .



For those who have not played Zork, here is what you see after loading the game:

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. >
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Hint> invites the user to enter commands like OPEN MAILBOX or GO NORTH to advance in the game. The goal is “to find the treasures of the Great Underground Empire and collect them in your loot box” along the way solving puzzles and plunging enemies.

Let's play the hunt for verbs (and nouns)

The user manual complete with Zork gives examples of possible commands, such as OPEN THE WOODEN DOOR and WARLOCK, TAKE THE SPELL SCROLL THEN FOLLOW ME. However, users had to guess independently how to solve a particular riddle.



Verbs of type TAKE and DROP (GET / DROP) are pretty obvious, as are the standard eight cardinal points and up / down (UP / DOWN), and at the same time in and out (IN / OUT). But users also had to use ATTACK, POOL and PRAY, as well as utter magic words that were not in the manual. The situation when the game did not give enough clues to the players, they mockingly called "verb hunting."



To generate commands, fuzzer will need a list of words accepted by the game, its vocabulary. The Z-machine selects this list as a game dictionary (it is located in a standard place in the file of each game).



(This is a kind of scam, yes! But there really is no other way to explain to the computer which words to use, since some verbs are not mentioned anywhere in the text.)



The easiest way to generate commands is to randomly take one or more words, in our case, one or two. We don’t know which words are verbs, and which nouns, so we generate a lot of strange commands like “SEE OOPS” and “DRIVER BELOW”.



Obviously, this is quite inefficient, because we have to sort through N * N combinations (where N is the size of the vocabulary) to find the very team like “KILL TROLL”.



However, we can cheat a little. We will scan all the words on the text output of the game and we will choose those that are found in our dictionary. And choose a word from this list (instead of a complete dictionary). For example, if we see NORTH, WEST, HOUSE, and MAILBOX in the text, we are more likely to use these words.

Search for story markers

Just issuing random commands, we get a lot of nonsense, which the parser will swear:

 >about painti [    !] >leathe guideb [   "leathe" ,    .]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

(Vocabulary words are no more than six characters in length in the Z-Machine, so we generate words like “leathe”.)



However, such a stomp on the spot will take forever. How do we determine which paths are more promising than others? We will look for markers for promoting the story.



The Z-Machine has a PRINT instruction that prints text to the console. Often these are fragments of descriptions such as “West of the House” and “the bottle has shattered”. We will register each of them as a marker.



Whenever we see a new marker, we save the current passage - a list of teams that we performed in the current game.



We associate this list with the current marker, so we can (hopefully) get the same text in the output after replaying the same commands.



Each launch of the game selects a specific target marker, and, therefore, the passage associated with it. The search algorithm selects new markers more often than old ones.



We will not replay teams verbatim in each game, but we will add a few random teams, and mix the order. When we see a new marker, we will increase the “success” parameter, the growth of which will show that it is possible to change the list of commands less often. When this parameter grows enough, we will mark this marker as “stable”, since we have a predictable passage that leads to it.

We are looking for a short way

The ways in which we go through the game are often ineffective. Here is the list of commands that was used to generate the “Wheeeeeeeeee !!!!!” marker:

 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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

All we really need to do is enter the last command: JUMP (or DIVE). But the search algorithm does not know which of the previous commands are needed to display “Wheeeeeeeeee !!!!!”



We need to reduce the passage - to make them as short as possible. When we see a marker, we replace the associated passage with a shorter list of commands, if possible. This leads us to the target marker faster, giving us more moves to experiment after reaching the goal.



Many markers, such as “Wheeeeeeeeee !!!!!”, are not interesting, since we can achieve them in one turn at the very beginning of the game. By reducing their list of commands, we will eventually be able to confirm that this is the case, and thus remove them from the list of potential target markers.

More than words

Since we have direct access to the internal state of the Z-machine, we can use something other than text output to control our search. For example, we can fix when an object has moved from room to room, or when other properties and flags have changed on the object. We call this VM markers (virtual machine markers), and fix them in parallel with text markers:

 @mv_30_15  (#30)      #15 @f_176_10_1    "" (10)   ""(#176)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

We need this because the text output does not tell us the whole story. For example, picking up a sword or lamp, we will reach the same marker “Taken.” And the VM marker will tell the search algorithm when a new state of the virtual machine is reached, for example, when a player moves to a new room, or an object has been picked up or thrown away.

Breaking a virtual machine

Investigating the state of the game is a rather slow process. One of the first tasks in the game is to kill the troll, which does not allow you to go further. However, before that, the player needs to find the sword in the house a little higher.



In order to speed up the search process, we will crack the Z-machine and bring the state of the game to what we saw earlier. For example, we accidentally moved a sword into a player’s hand, which made it possible to successfully execute the “STAB” command (stab). (“ATTACK TROLL” will not work unless we add “WITH SWORD”, but “STAB” (stabbing) already implies the presence of a sharp object and therefore works.)



We will crack only stable markers, so if we can reliably repeat the game and the sword is in the player’s hands, we will allow hacking of this state: “the sword is in the player’s hands”. Then we can combine the teams used to raise the sword with the teams used to go down the dungeon, finding out along the way that we must attack the troll.



The example of the troll is especially Jesuit, because, as a rule, it takes several strokes to finish it, and each attack gives a random result. Since our algorithm prefers shorter passes, it is preferable to adhere to an optimistic forecast about our combat abilities.



After 530,000 passes and 10,600,000 teams (200 teams per game), we finally figured out how to attack the troll:

 north, east, open window, into, west, light, lift trap, small hi, get, west, light, tug large, lift trap, down, north, stab
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

There are still a few unnecessary commands, and we still do not understand that we have to hit him several times, but we can handle it.

Fatal hobby

The search algorithm does not know the difference between collecting objects, throwing objects, and moving a player from room to room. The only way he defines progress is by seeing markers of storytelling.



This quickly develops in the search algorithm a taste for ... Murder! To kill a player, in particular, because it is so easy and simple: enter "ATTACK":

 >attack [  ] ,  ! ****   **** , ,     .      ,       .          c-.  ,      .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

In Mini Zorka, the first death is not the end of the game, the player teleports to another place, and your things are scattered. For the search algorithm, death is simply an object moving from one room to another, creating markers for moving the story along the way. This hobby leads to the exposure of other funny bugs in the game, such as the player’s ability to throw his hands into the river.



The game scores from 0 to 350 points, based on solving puzzles and collecting treasures. When a player dies, he is reduced by 10 points. We can use the account as a heuristic, but this can excessively reduce risky behavior - the love of wandering into dark places, or of fighting trolls.



The search algorithm is also keenly interested in what the player does not see, like NPCs moving between rooms. For example, the marker @ mv_112_37 indicates the movement of a thief to a specific room. The search algorithm manages to reproduce this marker by repeatedly executing Z or WAIT commands, essentially expecting the thief to reach the target room.



He also loves picking up and throwing objects in different places, because every movement of the object is a new marker. Who knows? Maybe throwing this leaf on a forest path will lead to victory in the game! (Narrator: no, it will not.)



Fuzzing invariably identifies errors in the program, and this game is no different, although it persists. He figured out how to generate the word “Clrthatrqdc” at the very beginning of the game:

 >tie up [  ] With a Clrthatrqdc!?!
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

This seems to be an uninitialized variable indicating non-textual data. The encoding of compressed text in the Z-machine is mostly alphanumeric, because you see not so much random garbage as when you try to print a binary file as ASCII. (Currently, this word is only twice on Google ( Already four times, approx. Transl. ).)

Walkthrough

To win the game, we will have to drag our looted goods back to the loot box and stuff every object into it. It will take a long time for our simple search algorithm to stumble upon this behavior, especially given its tendency to waste power and time moving objects from room to room.



Complicating an algorithm from random research takes time, so we must be selective when adding new features. We also want to avoid a priori knowledge in the game - in other words, we only want to cheat a little.



If you want to experiment, check out the source code on GitHub , which uses JSZM (the interpreter of Z-Machine Daniel Legenbauer). Many games are available (only versions up to 3 are supported.)



The Graham Nelson Z-Machine Standards document, which has been dealing with the Z-machine for a couple of decades, is also available.



And do I need to add Z-Machine support on 8bitworkshop ? Let me know!