Jogar jogos de aventura em texto é puro prazer, mas o prazer consome bastante o cérebro. Mas hoje temos todas essas capacidades ociosas do processador.
E se nós fizermos o computador passar pelo jogo por conta própria, e apenas tivermos que nos recostar na cadeira e assistir? Nem precisamos de todas essas redes neurais novas, uma força bruta simples.
Apenas colocamos um monte de texto semi-aleatório na entrada do jogo de texto e vemos o que acontece. No mundo da segurança da informação, isso é chamado de difusão.
O objetivo será o Z-Machine, um intérprete de máquina virtual desenvolvido por Joel Berez e Mark Blanck em 1979, o coração dos Jogos Infocom. Este é um alvo ideal para aventurar fuzzing, pois está bem documentado e possui muitas ferramentas e bibliotecas de suporte.
Zork lançado no Atari 800XL (Sebastian Grunwald, CC 3.0)Mini Zork
O jogo que vamos brincar -
MINI-ZORK-1: O Grande Império Subterrâneo . Esta é uma versão demo do Infokomovsky first Zorka, projetada para inicializar a partir de um cassete, não de um disquete. Essencialmente, era um anúncio publicado no suplemento dos anos 90 da revista britânica de usuários do Commodore,
Zzap! 64 .
Para aqueles que não jogaram Zork, eis o que você vê após o carregamento do jogo:
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. >
Dica> convida o usuário a inserir comandos como OPEN MAILBOX ou GO NORTH para avançar no jogo. O objetivo é "encontrar os tesouros do Grande Império Subterrâneo e colecioná-los em sua caixa de itens" ao longo do caminho, resolvendo quebra-cabeças e mergulhando inimigos.
Vamos procurar os verbos (e substantivos)
O guia do usuário completo com o Zork fornece exemplos de possíveis comandos, como ABRIR A PORTA DE MADEIRA e WARLOCK, FAÇA O ROLO DE Feitiço E Me Siga. No entanto, os usuários tiveram que adivinhar independentemente como resolver um enigma específico.
Verbos como GET e DROP (GET / DROP) são bastante óbvios, assim como os oito pontos cardinais padrão e para cima / para baixo (UP / DOWN), e ao mesmo tempo dentro e fora (IN / OUT). Mas os usuários também tiveram que usar ATTACK, POOL e PRAY, além de pronunciar palavras mágicas que não estavam no manual. A situação em que o jogo não dava pistas suficientes para os jogadores, eles zombavam de "caça aos verbos".
Para gerar comandos, o fuzzer precisará de uma lista de palavras aceitas pelo jogo, seu vocabulário. A máquina Z seleciona essa lista como um dicionário de jogo (está localizado em um local padrão no arquivo de cada jogo).
(É uma espécie de fraude, sim! Mas, na verdade, não há outra maneira de explicar ao computador quais palavras usar, pois alguns verbos não são mencionados em nenhum lugar do texto.)
A maneira mais fácil de gerar comandos é pegar aleatoriamente uma ou mais palavras, no nosso caso, uma ou duas. Como não sabemos quais palavras são verbos e quais substantivos, geramos muitos comandos estranhos, como "VER OOPS" e "CONDUTOR ABAIXO".
Obviamente, isso é bastante ineficiente, porque precisamos classificar as combinações N * N (onde N é o tamanho do vocabulário) para encontrar o próprio comando como "KILL TROLL".
No entanto, podemos trapacear um pouco. Analisaremos todas as palavras na saída de texto do jogo e escolheremos as que são encontradas em nosso dicionário. E escolha uma palavra dessa lista (em vez de um dicionário completo). Por exemplo, se virmos NORTH, WEST, HOUSE e MAILBOX no texto, teremos mais chances de usar essas palavras.
Pesquisar marcadores de história
Apenas dando comandos aleatórios, temos muitas bobagens que o analisador jurará:
>about painti [ !] >leathe guideb [ "leathe" , .]
(As palavras do vocabulário não têm mais que seis caracteres no Z-Machine, por isso geramos palavras como "leathe".)
No entanto, esse golpe no local levará uma eternidade. Como podemos determinar quais caminhos são mais promissores que outros? Procuraremos marcadores para promover a história.
O Z-Machine possui uma instrução PRINT que imprime texto no console. Frequentemente, esses são fragmentos de descrições, como "Oeste da casa" e "Garrafa quebrada". Vamos registrar cada um deles como um marcador.
Sempre que vemos um novo marcador, salvamos a passagem atual - uma lista de equipes que realizamos no jogo atual.
Associamos esta lista ao marcador atual, para que possamos (espero) obter o mesmo texto na saída depois de reproduzir os mesmos comandos.
Cada lançamento do jogo seleciona um marcador de alvo específico e, portanto, a passagem associada a ele. O algoritmo de pesquisa seleciona novos marcadores com mais frequência do que os antigos.
Não reproduziremos as equipes literalmente em cada jogo, mas adicionaremos algumas equipes aleatórias e misturaremos a ordem. Quando virmos um novo marcador, aumentaremos o parâmetro "success", cujo crescimento mostrará que é possível alterar a lista de comandos com menos frequência. Quando esse parâmetro cresce o suficiente, marcamos esse marcador como "estável", pois temos uma passagem previsível que leva a ele.
Procurando um caminho curto
As maneiras pelas quais passamos pelo jogo geralmente são ineficazes. Aqui está a lista de comandos que foram usados para gerar o marcador "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
Tudo o que realmente precisamos fazer é inserir o último comando: JUMP (ou DIVE). Mas o algoritmo de pesquisa não sabe quais dos comandos anteriores são necessários para exibir "Wheeeeeeeeee !!!!!"
Precisamos reduzir a passagem - para torná-los o mais curto possível. Quando vemos um marcador, substituímos a passagem associada por uma lista mais curta de comandos, se possível. Isso nos leva ao marcador de destino mais rapidamente, oferecendo mais movimentos para experimentar depois de atingir a meta.
Muitos marcadores, como “Wheeeeeeeeee !!!!!”, não são interessantes, pois podemos alcançá-los de uma só vez no início do jogo. Ao reduzir sua lista de comandos, finalmente poderemos confirmar que é esse o caso e removê-los da lista de possíveis marcadores de destino.
Mais que palavras
Como temos acesso direto ao estado interno da máquina Z, podemos usar algo diferente da saída de texto para controlar nossa pesquisa. Por exemplo, podemos corrigir quando um objeto foi movido de sala em sala ou quando outras propriedades e sinalizadores foram alteradas no objeto. Chame-o de marcadores de VM (marcadores de máquina virtual) e corrija-os paralelamente aos marcadores de texto:
@mv_30_15 (#30) #15 @f_176_10_1 "" (10) ""(#176)
Precisamos disso porque a saída de texto não nos conta toda a história. Por exemplo, pegando uma espada ou uma lâmpada, chegaremos ao mesmo marcador “Tirada”. E o marcador da VM informará o algoritmo de busca quando um novo estado da máquina virtual for atingido, por exemplo, quando um jogador se mudar para uma nova sala ou um objeto for retirado ou jogado fora.
Quebrando uma máquina virtual
Investigar o estado do jogo é um processo bastante lento. Uma das primeiras tarefas do jogo é matar o troll, o que não permite que você vá além. No entanto, antes disso, o jogador precisa encontrar uma espada na casa um pouco mais alto.
Para acelerar o processo de busca, quebraremos a máquina Z e levaremos o estado do jogo ao que vimos anteriormente. Por exemplo, acidentalmente movemos uma espada para a mão de um jogador, o que tornou possível executar com êxito o comando "STAB" (facada). (“ATTACK TROLL” não funcionará a menos que adicionemos “WITH SWORD”, mas “STAB” (facada) já implica a presença de um objeto pontiagudo e, portanto, funciona.)
Quebraremos apenas marcadores estáveis; portanto, se pudermos repetir com segurança o jogo e as mãos do jogador se tornarem uma espada, permitiremos o hackeamento desse estado: "a espada está nas mãos do jogador". Então podemos combinar as equipes usadas para levantar a espada com as equipes usadas para descer a masmorra, descobrindo ao longo do caminho que devemos atacar o troll.
O exemplo do troll é especialmente jesuíta, porque, em regra, são necessários vários golpes para terminá-lo, e cada ataque dá um resultado aleatório. Como nosso algoritmo prefere passes mais curtos, é preferível aderir a uma previsão otimista sobre nossas habilidades de combate.
Após 530.000 orientações e 10.600.000 equipes (200 equipes por jogo), finalmente descobrimos como atacar o troll:
north, east, open window, into, west, light, lift trap, small hi, get, west, light, tug large, lift trap, down, north, stab
Ainda existem alguns comandos desnecessários, e ainda não entendemos que precisamos atingi-lo várias vezes, mas podemos lidar com isso.
Passatempo fatal
O algoritmo de busca não sabe a diferença entre coletar objetos, arremessar objetos e mover um jogador de sala em sala. A única maneira de definir o progresso é ver marcadores da história progredindo.
Isso rapidamente desenvolve no algoritmo de busca um gosto por ... Assassinato! Para matar um jogador, em particular, porque é tão fácil e simples: digite "ATAQUE":
>attack [ ] , ! **** **** , , . , . c-. , .
Em Mini Zorka, a primeira morte não é o fim do jogo, o jogador se teleporta para outro lugar e suas coisas são espalhadas. Para um algoritmo de busca, a morte é simplesmente um objeto que se move de uma sala para outra, criando marcadores para mover a história ao longo do caminho. Esse hobby leva à exposição de outros insetos engraçados no jogo, como a capacidade do jogador de jogar as mãos no rio.
O jogo marca de 0 a 350 pontos, com base na resolução de quebra-cabeças e coleta de tesouros. Quando um jogador morre, ele é reduzido em 10 pontos. Podemos usar a conta como heurística, mas isso pode reduzir excessivamente o comportamento arriscado - o amor de vaguear por lugares escuros ou de lutar contra trolls.
O algoritmo de busca também está profundamente interessado no que o jogador não vê, como os NPCs se movendo entre as salas. Por exemplo, o marcador @ mv_112_37 indica o movimento de um ladrão para uma sala específica. O algoritmo de busca consegue reproduzir esse marcador executando repetidamente comandos Z ou WAIT, esperando essencialmente que o ladrão alcance a sala de destino.
Ele também gosta de pegar e jogar objetos em lugares diferentes, porque cada movimento do objeto é um novo marcador. Quem sabe Talvez jogar esta folha no caminho da floresta leve à vitória no jogo! (Narrador: não, não será.)
Fuzzing invariavelmente identifica erros no programa, e este jogo não é diferente, embora persista. Ele descobriu como gerar a palavra "Clrthatrqdc" no início do jogo:
>tie up [ ] With a Clrthatrqdc!?!
Essa parece ser uma variável não inicializada, indicando dados não textuais. A codificação de texto compactado na máquina Z é basicamente alfabética, porque você vê tanto lixo aleatório quanto quando tenta imprimir um arquivo binário como ASCII. (No momento, essa palavra
está apenas duas vezes no Google (
já quatro vezes, aprox. Transl. ).)
Passo a passo
Para ganhar o jogo, teremos que arrastar nossos itens saqueados de volta para a caixa de itens e colocar todos os objetos nele. Levará muito tempo para nosso algoritmo de busca simples se deparar com esse comportamento, especialmente devido à sua tendência a desperdiçar energia e tempo movendo objetos de sala em sala.
A complicação de um algoritmo a partir de pesquisas aleatórias leva tempo, portanto, devemos ser seletivos ao adicionar novos recursos. Também queremos evitar conhecimento a priori no jogo - em outras palavras, queremos apenas trapacear um pouco.
Se você quiser experimentar,
confira o código-fonte no GitHub , que usa
JSZM (o intérprete do Z-Machine Daniel Legenbauer). Muitos
jogos estão disponíveis (somente versões de até 3 são suportadas).
O documento Graham Nelson
Z-Machine Standards , que lida com a Z-machine há algumas décadas, também está disponível.
E preciso adicionar o suporte da Z-Machine no
8bitworkshop ? Me avise!