Это перевод блогозаписи Стивена Хагга: Fuzzing the Z-Machine

Фаззинг Z-машины

Играть в текстовые приключенческие игры сплошное удовольствие, но удовольствие это довольно мозгозатратное. Но ведь сегодня у нас есть все вот эти вот простаивающие процессорные мощности.

Что если мы заставим компьютер самостоятельно проходить игру, а нам останется лишь откинуться в кресле и наблюдать? Нам даже не понадобятся все эти новомодные нейросети, достаточно простой грубой силы.

Мы просто закинем на вход текстовой игры кучу полу-случайного текста и посмотрим что выйдет. В мире инфобезопасности это называется «фаззинг».

Целью будет Z-Машина, виртуальная машина-интерпретатор, разработанная Джоэлом Березом и Марком Бланком в 1979 году, сердце Инфокомовских игр. Это идеальная цель для фаззинга адвентюр, так как она хорошо документирована и для неё есть множество вспомогательных инструментов и библиотек.



Зорк, запущенный на Atari 800XL (Себастьян Грюнвальд, CC 3.0)

Мини-Зорк

Игра, которую будем фаззить — МИНИ-ЗОРК-1: Великая подземная империя. Это демо-версия Инфокомовского первого Зорка, рассчитанная на загрузку с кассеты, а не с дискеты. По сути, это была реклама, опубликованная в приложении к британскому журналу пользователей Commodore'а "Zzap! 64" в 1990.

Для тех, кто не играл в Зорк, вот что вы видите после загрузки игры:

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.

>

Подсказка > приглашает пользователя вводить команды типа OPEN MAILBOX или GO NORTH чтобы продвигаться в игре. Цель — «найти сокровища Великой Подземной Империи и собрать их в свой ящик для добычи» по пути решая головоломки и повергая врагов.

Сыграем в охоту на глаголы (и существительные)

Руководство пользователя в комплекте с Зорком приводит примеры возможных команд, типа OPEN THE WOODEN DOOR и WARLOCK, TAKE THE SPELL SCROLL THEN FOLLOW ME. Однако, пользователям приходилось самостоятельно догадываться как решить конкретную загадку.

Глаголы типа ВЗЯТЬ и БРОСИТЬ (GET/DROP) довольно очевидны, также как и стандартные восемь сторон света и верх/вниз (UP/DOWN), а заодно и внутрь/наружу (IN/OUT). Но пользователям также приходилось использовать АТАКОВАТЬ, НАДУТЬ и МОЛИТЬСЯ, а также произносить волшебные слова, которых не было в руководстве. Ситуацию, когда игра не давала достаточно подсказок игрокам, они насмешливо называли «охотой на глагол».

Для генерации команд, фаззеру понадобится список слов принимаемых игрой, её словарный запас. Z-машина выделяет этот список как словарь игры (он находится в стандартном месте в файле каждой игры).

(Это своего рода жульничество, да! Но тут уж действительно нет другого способа объяснить компьютеру какие слова использовать, раз уж некоторые глаголы в тексте нигде не упоминаются.)

Самый простой способ генерации команд — это случайно взять одно или больше слов, в нашем случае — одно или два. Мы не знаем какие слова глаголы, а какие существительные, так что нагенерируем множество странноватых команд типа «SEE OOPS» и «DRIVER BELOW».

Очевидно это довольно неэффективно, ведь нам придётся перебрать N*N комбинаций (где N — размер словарного запаса) чтобы найти ту самую команду вроде «KILL TROLL».

Однако мы можем немного смухлевать. Мы просканируем все слова на текстовом выходе игры и будем выбирать те, которые встречаются в нашем словаре. И выберем слово из этого списка (вместо полного словаря). Например, если в тексте мы увидим NORTH, WEST, HOUSE, и MAILBOX мы с большей вероятностью используем эти слова.

Поиск маркеров продвижения истории

Просто выдавая случайные команды, мы получим много всякой бессмыслицы, на которую парсер будет ругаться:

>about painti
[В этом предложении нет глагола!]

>leathe guideb
[Вы использовали слово "leathe" способом, который я не понимаю.]

(Словарные слова — не более чем шесть символов в длину в Z-Машине, поэтому мы генерируем такие слова как «leathe».)

Однако такое топтание на месте займёт вечность. Как нам определить какие пути более перспективны, чем другие? Мы будем искать маркеры продвижения истории.

У Z-Машины есть инструкция PRINT, которая выводит текст в консоль. Часто это фрагменты описания, типа “Запад Дома” и “бутылка разлетелась”. Мы зарегистрируем каждый из них как маркер.

Всякий раз, когда мы видим новый маркер, мы сохраняем текущее прохождение — список команд которые мы выполнили в текущей игре.

Мы ассоциируем это список с текущим маркером, таким образом мы можем (надеемся) получить такой же текст на выходе после перепроигрывания таких же команд.

Каждый запуск игры выбирает конкретный целевой маркер, и, следовательно, связанное с ним прохождение. Поисковый алгоритм выбирает новые маркеры чаще, чем старые.

Мы не будем переигрывать команды дословно в каждой игре, но будем добавлять несколько случайных команд, и перемешивать порядок. Когда мы увидим новый маркер мы увеличим параметр «успех», рост которого покажет, что можно реже изменять список команд. Когда этот параметр подрастёт достаточно, мы пометим этот маркер как «стабильный», раз уж у нас есть предсказуемое прохождение, которое к нему приводит.

Ищем короткий путь

Пути, которыми мы проходим игру часто неэффективны. Вот список команд, который был использован для генерации маркера “Wheeeeeeeeee!!!!!”:

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

Все, что нам реально надо сделать — это ввести последнюю команду: JUMP (или DIVE). Но алгоритм поиска не знает, какие из предыдущих команд необходимы для вывода “Wheeeeeeeeee!!!!!”

Нам нужно сократить прохождения — сделать их как можно короче. Когда мы видим маркер, мы заменяем связанное прохождение более коротким списком команд, если это возможно. Это приводит нас к целевому маркеру быстрее, давая нам больше ходов для экспериментов после достижения цели.

Многие маркеры, такие как “Wheeeeeeeeee!!!!!” — не интересны, так как мы можем достигнуть их за один ход в самом начале игры. Уменьшая их списки команд, мы в конце концов сможем подтвердить, что так оно и есть, и, таким образом, удалить их из списка потенциальных целевых маркеров.

Больше, чем слова

Так как мы имеем прямой доступ к внутреннему состоянию Z-машины, мы можем использовать нечто кроме текстового вывода, чтобы управлять нашим поиском. Например, мы можем зафиксировать, когда объект переместился из комнаты в комнату, или когда у объекта изменились другие свойства и флаги. Назовём это VM-маркерами (маркерами виртуальной машины), и зафиксируем их параллельно с текстовыми маркерами:

@mv_30_15      Игрок (#30) идёт на восток в комнату #15
@f_176_10_1    Игрок устанавливает флаг "открыто" (10) на объекте "окно"(#176)

Нам это нужно, потому что текстовый вывод не рассказывает нам всю историю. Например, взяв в руки меч или лампу мы достигнем одного и того же маркера “Taken.” А VM-маркер расскажет алгоритму поиска, когда достигается новое состояние виртуальной машины, например, когда игрок переходит в новую комнату, или объект был подобран или выброшен.

Ломаем виртуальную машину

Исследование состояния игры это довольно медленный процесс. Одной из первых задач в игре-убить тролля, который не даёт пройти дальше. Однако до этого игроку необходимо найти меч в доме чуть выше.

Для того, чтобы ускорить поисковый процесс, мы взломаем Z-машину и приведём состояние игры к тому, что мы видели ранее. Например, мы случайно переместили меч в руку игрока, что дало возможность успешно выполнить команду «STAB» (заколоть). («ATTACK TROLL» не сработает, если только мы не добавим «WITH SWORD», но «STAB» (заколоть) уже подразумевает наличие острого объекта и потому срабатывает.)

Мы будем взламывать только стабильные маркеры, так, если мы можем надежно повторить прохождение игры и в руках игрока оказывается меч, мы разрешим взлом этого состояния: «меч в руках игрока». Тогда мы сможем объединить команды, используемые, чтобы поднять меч с командами, используемыми, чтобы спуститься в подземелье, по пути выясняя, что мы должны напасть на тролля.

Пример с троллем особенно иезуитский, потому что, как правило, нужно несколько ударов, чтобы добить его, и каждая атака даёт случайный результат. Поскольку наш алгоритм предпочитает более короткие прохождения, предпочтительнее придерживаться оптимистичного прогноза о наших боевых способностях.

После 530,000 прохождений и 10,600,000 команд (200 команд на игру) мы, наконец, выяснили как напасть на тролля:

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

Всё ещё есть несколько ненужных команд, и мы всё ещё не поняли, что должны ударить его несколько раз, но мы справимся.

Роковое увлечение

Поисковый алгоритм не знает разницы между собиранием объектов, выбрасыванием объектов, и перемещением игрока из комнаты в комнату. Единственное, как он определяет прогресс это видя маркеры продвижения истории.

Это быстро развивает в алгоритме поиска вкус к… Убийству! К убийству игрока, в частности, потому что это так легко и просто: вводишь «ATTACK»:

>attack
[храбрый любитель приключений]
Фу, ты мёртв!

    ****  Вы умерли **** 

Ну, возможно, вы заслуживаете еще один шанс. Я не могу восстановить вас полностью, но ведь нельзя получить всё и сразу.

Опушка Леса
Пути ведут в лес на запад и cеверо-запад. Кроме того, хорошо заметная тропа простирается на восток.

В Мини-Зорке, первая смерть — не конец игры, игрок телепортируется в другое место, и ваши вещи разбросаны. Для алгоритма поиска, смерть — это просто объект, перемещающийся из одной комнаты в другую, по пути создающий маркеры продвижения истории. Это увлечение приводит к разоблачению других забавных багов в игре, как, например, способности игрока бросить свои руки в реку.

Игра ведёт счет от 0 до 350 очков, основанный на решении головоломок и сборе сокровищ. Когда игрок умирает, то он снижается на 10 баллов. Мы можем использовать счёт в качестве эвристики, но это может чрезмерно снизить рискованное поведение — любовь к забреданию в темные места, или к сражению с троллями.

Алгоритм поиска также живо интересуется тем, что игрок не видит, вроде NPC, перемещающихся между комнатами. Например, маркер @mv_112_37 обозначает перемещение вора в определенную комнату. Алгоритму поиска удается воспроизвести этот маркер, многократно выполняя команды Z или WAIT, по сути ожидая чтобы вор достиг целевой комнаты.

Он также любит подбирать и выбрасывать объекты в разных местах, потому что каждое движение объекта — это новый маркер. Кто знает? Может, выбрасываение этого листика на лесной тропинке приведёт к победе в игре! (Рассказчик: нет, не приведёт.)

Фаззинг неизменно выявляет ошибки в программе, и эта игра ничем не отличается, хоть и упорствует. Он придумал, как сгенерировать слово “Clrthatrqdc” в самом начале игры:

>tie up
[храбрый искатель приключений]
With a   Clrthatrqdc!?!

Это, похоже, неинициализированная переменная указывающая на нетекстовые данные. Кодирование скомпрессированного текста в Z-машине преимущественно буквенное, потому вы видите не так много случайного мусора как при попытке распечатать бинарный файл как ASCII. (На текущий момент это слово находится в Google только дважды (Уже четырежды, прим.перев.).)

Прохождение игры

Чтобы выиграть игру, нам придется притаскивать наше награбленное добро обратно к ящику с добычей и запихивать в него каждый объект. Это займет много времени для нашего простого алгоритма поиска, чтобы наткнуться на такое поведение, особенно учитывая его склонности к растрате сил и времени на перемещение объектов из комнаты в комнату.

Усложнение алгоритма от случайного исследования требует времени, потому мы должны быть избирательны при добавлении новых возможностей. Такж мы хотим избежать априорного знания в игре — иными словами, мы хотим лишь немного схитрить.

Если вы хотите поэкспериментировать, зацените исходный код на GitHub, который использует JSZM (интерпретатор Z-Машины Даниэля Легенбауэра) Доступно множество игр (поддерживается только версии до 3.)

Также доступен документ "Стандарты Z-Машины" Грэма Нельсона, который имел дело с Z-машиной уже пару десятков лет.

И нужно ли добавить поддержку Z-Машины на 8bitworkshop? Дайте мне знать!