Bermain game petualangan teks adalah kesenangan murni, tetapi kesenangan cukup menguras otak. Tetapi hari ini kita memiliki semua kapasitas prosesor yang tidak digunakan ini.
Bagaimana jika kita membuat komputer melalui permainan kita sendiri, dan kita hanya harus bersandar di kursi dan menonton? Kami bahkan tidak membutuhkan semua jaringan saraf bermodel baru ini, kekuatan kasar yang sederhana.
Kami baru saja meletakkan sekelompok teks semi-acak di pintu masuk permainan teks dan melihat apa yang terjadi. Dalam dunia keamanan informasi, ini disebut fuzzing.
Tujuannya adalah Z-Machine, juru bahasa mesin virtual yang dikembangkan oleh Joel Berez dan Mark Blanck pada 1979, jantung dari Infocom Games. Ini adalah target ideal untuk petualangan fuzzing, karena didokumentasikan dengan baik dan memiliki banyak alat dan perpustakaan pendukung.
Zork diluncurkan di Atari 800XL (Sebastian Grunwald, CC 3.0)Zork Mini
Game yang akan kita fuzz -
MINI-ZORK-1: The Great Underground Empire . Ini adalah versi demo Zorka pertama Infokomovsky, yang dirancang untuk boot dari kaset, bukan dari floppy disk. Pada dasarnya, itu adalah sebuah iklan yang diterbitkan dalam suplemen tahun 1990-an untuk majalah pengguna Commodore di Inggris,
Zzap! 64 .
Bagi yang belum pernah bermain Zork, inilah yang Anda lihat setelah memuat 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. >
Petunjuk> mengundang pengguna untuk memasukkan perintah seperti OPEN MAILBOX atau GO NORTH untuk maju dalam permainan. Tujuannya adalah "untuk menemukan harta dari Kekaisaran Bawah Tanah Besar dan mengumpulkannya di dalam kotak jarahan Anda" di sepanjang jalan memecahkan teka-teki dan menjatuhkan musuh.
Ayo mainkan perburuan kata kerja (dan kata benda)
Panduan pengguna lengkap dengan Zork memberikan contoh-contoh perintah yang mungkin seperti BUKA PINTU KAYU dan WARLOCK, MENGAMBIL SPELL SCROLL THEN FOLLOW ME. Namun, pengguna harus menebak secara mandiri bagaimana memecahkan teka-teki tertentu.
Kata kerja seperti GET dan DROP (GET / DROP) cukup jelas, seperti halnya delapan poin kardinal standar dan naik / turun (Atas / Bawah), dan pada saat yang sama masuk dan keluar (IN / OUT). Tetapi pengguna juga harus menggunakan SERANGAN, KOLAM dan BERDOA, serta mengucapkan kata-kata ajaib yang tidak ada dalam manual. Situasi ketika permainan tidak memberikan petunjuk yang cukup kepada para pemain, mereka secara mengejek menyebut "perburuan kata kerja."
Untuk menghasilkan perintah, fuzzer akan membutuhkan daftar kata yang diterima oleh permainan, kosa katanya. Mesin-Z memilih daftar ini sebagai kamus game (ini terletak di tempat standar di file setiap game).
(Ini semacam penipuan, ya! Tapi benar-benar tidak ada cara lain untuk menjelaskan kepada komputer kata-kata apa yang digunakan, karena beberapa kata kerja tidak disebutkan di mana pun dalam teks.)
Cara termudah untuk menghasilkan perintah adalah dengan secara acak mengambil satu atau lebih kata, dalam kasus kami, satu atau dua. Kami tidak tahu kata mana yang kata kerja, dan kata benda mana, jadi kami menghasilkan banyak perintah aneh seperti "LIHAT OOPS" dan "DRIVER DI BAWAH".
Jelas, ini sangat tidak efisien, karena kita harus memilah-milah kombinasi N * N (di mana N adalah ukuran kosakata) untuk menemukan perintah seperti "KILL TROLL".
Namun, kita bisa sedikit curang. Kami akan memindai semua kata pada output teks game dan akan memilih kata-kata yang ditemukan dalam kamus kami. Dan pilih kata dari daftar ini (bukan kamus lengkap). Misalnya, jika kita melihat NORTH, WEST, HOUSE, dan MAILBOX dalam teks, kita lebih cenderung menggunakan kata-kata ini.
Cari penanda cerita
Hanya dengan memberikan perintah acak, kita mendapatkan banyak omong kosong yang akan disumpah oleh parser:
>about painti [ !] >leathe guideb [ "leathe" , .]
(Kata-kata kosakata panjangnya tidak lebih dari enam karakter di Z-Machine, jadi kami menghasilkan kata-kata seperti "leathe".)
Namun, gerakan seperti itu di tempat akan memakan waktu selamanya. Bagaimana kita bisa menentukan jalur mana yang lebih menjanjikan daripada yang lain? Kami akan mencari spidol untuk mempromosikan sejarah.
Z-Machine memiliki instruksi PRINT yang mencetak teks ke konsol. Seringkali ini adalah fragmen deskripsi, seperti "West of the House" dan "bottle shattered". Kami akan mendaftarkan masing-masing sebagai penanda.
Setiap kali kami melihat penanda baru, kami menyimpan bagian saat ini - daftar tim yang kami lakukan dalam permainan saat ini.
Kami mengaitkan daftar ini dengan marker saat ini, sehingga kami dapat (mudah-mudahan) mendapatkan teks yang sama di output setelah memutar ulang perintah yang sama.
Setiap peluncuran game memilih penanda target tertentu, dan, oleh karena itu, bagian yang terkait dengannya. Algoritma pencarian memilih penanda baru lebih sering daripada yang lama.
Kami tidak akan memutar ulang tim kata demi kata di setiap pertandingan, tetapi kami akan menambahkan beberapa tim acak, dan mencampur pesanan. Ketika kita melihat penanda baru, kita akan meningkatkan parameter "sukses", yang pertumbuhannya akan menunjukkan bahwa mungkin untuk mengubah daftar perintah lebih jarang. Ketika parameter ini tumbuh cukup, kami menandai penanda ini sebagai "stabil", karena kami memiliki bagian yang dapat diprediksi yang mengarah ke sana.
Mencari jalan pintas
Cara kita menjalani permainan sering kali tidak efektif. Berikut adalah daftar perintah yang digunakan untuk menghasilkan penanda "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
Yang perlu kita lakukan hanyalah memasukkan perintah terakhir: JUMP (atau DIVE). Tetapi algoritma pencarian tidak tahu perintah mana yang diperlukan untuk menampilkan “Wheeeeeeeeee !!!!!”
Kita perlu mengurangi bagian itu - untuk membuatnya sesingkat mungkin. Ketika kami melihat penanda, kami mengganti bagian terkait dengan daftar perintah yang lebih pendek, jika memungkinkan. Ini membawa kita ke penanda target lebih cepat, memberi kita lebih banyak gerakan untuk bereksperimen setelah mencapai tujuan.
Banyak spidol, seperti "Wheeeeeeeeee !!!!!", tidak menarik, karena kita dapat mencapainya dalam satu putaran di awal permainan. Dengan mengurangi daftar perintah mereka, kami pada akhirnya akan dapat mengonfirmasi bahwa ini adalah masalahnya, dan dengan demikian menghapusnya dari daftar penanda target potensial.
Lebih dari sekedar kata-kata
Karena kami memiliki akses langsung ke keadaan internal mesin-Z, kami dapat menggunakan sesuatu selain output teks untuk mengontrol pencarian kami. Misalnya, kita dapat memperbaiki ketika suatu objek telah berpindah dari satu ruangan ke ruangan lain, atau ketika properti dan bendera lainnya telah berubah pada objek tersebut. Sebut saja penanda VM (penanda mesin virtual), dan perbaiki secara paralel dengan penanda teks:
@mv_30_15 (#30) #15 @f_176_10_1 "" (10) ""(#176)
Kami membutuhkan ini karena output teks tidak memberi tahu kami keseluruhan cerita. Misalnya, mengambil pedang atau lampu, kita akan mencapai penanda yang sama "Diambil." Dan penanda VM akan memberi tahu algoritma pencarian ketika keadaan baru dari mesin virtual tercapai, misalnya, ketika seorang pemain pindah ke kamar baru, atau sebuah benda telah diambil atau dibuang.
Memecah mesin virtual
Menyelidiki kondisi permainan adalah proses yang agak lambat. Salah satu tugas pertama dalam permainan adalah untuk membunuh troll, yang tidak memungkinkan Anda untuk melangkah lebih jauh. Namun, sebelum itu, pemain perlu menemukan pedang di rumah sedikit lebih tinggi.
Untuk mempercepat proses pencarian, kami akan memecahkan mesin-Z dan membawa keadaan permainan ke apa yang kami lihat sebelumnya. Sebagai contoh, kami secara tidak sengaja memindahkan pedang ke tangan pemain, yang memungkinkan untuk mengeksekusi perintah "STAB" dengan sukses. ("ATTACK TROLL" tidak akan berfungsi kecuali jika kita menambahkan "WITH SWORD", tetapi "STAB" (stabbing) sudah menyiratkan adanya benda tajam dan karenanya berfungsi.)
Kami hanya akan memecahkan marker stabil, jadi jika kami dapat mengulangi permainan dengan andal dan tangan pemain berubah menjadi pedang, kami akan memungkinkan peretasan keadaan ini: "pedang ada di tangan pemain". Kemudian kita bisa menggabungkan tim yang digunakan untuk mengangkat pedang dengan tim yang digunakan untuk turun ke ruang bawah tanah, mencari tahu sepanjang jalan bahwa kita harus menyerang troll.
Contoh troll ini terutama Jesuit, karena, sebagai aturan, dibutuhkan beberapa pukulan untuk menyelesaikannya, dan setiap serangan memberikan hasil acak. Karena algoritme kami lebih suka lintasan yang lebih pendek, lebih baik mengikuti ramalan optimis tentang kemampuan tempur kami.
Setelah 530.000 penelusuran dan 10.600.000 tim (200 tim per pertandingan), kami akhirnya menemukan cara untuk menyerang troll:
north, east, open window, into, west, light, lift trap, small hi, get, west, light, tug large, lift trap, down, north, stab
Masih ada beberapa perintah yang tidak perlu, dan kami masih tidak mengerti bahwa kami harus memukulnya beberapa kali, tetapi kami dapat mengatasinya.
Hobi fatal
Algoritme pencarian tidak mengetahui perbedaan antara mengumpulkan objek, melempar objek, dan memindahkan pemain dari satu kamar ke kamar lainnya. Satu-satunya cara dia mendefinisikan kemajuan adalah dengan melihat tanda-tanda perkembangan sejarah.
Ini dengan cepat berkembang dalam rasa pencarian untuk ... Pembunuhan! Untuk membunuh pemain, khususnya, karena sangat mudah dan sederhana: masukkan "ATTACK":
>attack [ ] , ! **** **** , , . , . c-. , .
Di Mini Zorka, kematian pertama bukanlah akhir dari permainan, pemain berteleportasi ke tempat lain, dan barang-barang Anda tersebar. Untuk algoritma pencarian, kematian hanyalah sebuah objek yang bergerak dari satu ruangan ke ruangan lain, menciptakan penanda untuk memindahkan cerita di sepanjang jalan. Hobi ini mengarah pada pemaparan bug lucu lainnya dalam permainan, seperti kemampuan pemain untuk melemparkan tangannya ke sungai.
Gim ini skor dari 0 hingga 350 poin, berdasarkan pada memecahkan teka-teki dan mengumpulkan harta. Ketika seorang pemain meninggal, ia berkurang 10 poin. Kita dapat menggunakan akun sebagai heuristik, tetapi ini dapat secara berlebihan mengurangi perilaku berisiko - cinta berkeliaran di tempat gelap, atau melawan troll.
Algoritme pencarian juga sangat tertarik pada apa yang tidak dilihat oleh pemain, seperti NPC yang bergerak di antara kamar-kamar. Misalnya, penanda @ mv_112_37 menunjukkan perpindahan pencuri ke ruangan tertentu. Algoritme pencarian berhasil mereproduksi penanda ini dengan berulang kali mengeksekusi perintah Z atau WAIT, pada dasarnya mengharapkan pencuri mencapai ruang target.
Dia juga suka mengambil dan membuang benda di tempat yang berbeda, karena setiap gerakan objek adalah penanda baru. Siapa tahu Mungkin melempar daun ini di jalan hutan akan membawa kemenangan dalam permainan! (Narator: tidak, tidak akan.)
Fuzzing selalu mengidentifikasi kesalahan dalam program, dan permainan ini tidak berbeda, meskipun terus berlanjut. Dia menemukan cara untuk menghasilkan kata "Clrthatrqdc" di awal permainan:
>tie up [ ] With a Clrthatrqdc!?!
Ini tampaknya merupakan variabel tidak diinisialisasi yang menunjukkan data non-tekstual. Pengkodean teks terkompresi di mesin-Z sebagian besar alfabet, karena Anda melihat tidak begitu banyak sampah acak seperti ketika Anda mencoba untuk mencetak file biner seperti ASCII. (Saat ini, kata
ini hanya dua kali di Google (
Sudah empat kali, kira-kira. Terjemahan ).)
Panduan
Untuk memenangkan permainan, kita harus menyeret barang rampasan kita kembali ke kotak jarahan dan memasukkan semua benda ke dalamnya. Algoritma pencarian sederhana kami akan membutuhkan waktu lama untuk menemukan perilaku ini, terutama mengingat kecenderungannya untuk menyia-nyiakan daya dan memindahkan objek dari waktu ke waktu.
Menyulitkan suatu algoritma dari riset acak membutuhkan waktu, jadi kita harus selektif ketika menambahkan fitur baru. Kami juga ingin menghindari pengetahuan apriori dalam permainan - dengan kata lain, kami hanya ingin sedikit menipu.
Jika Anda ingin bereksperimen,
lihat kode sumber di GitHub , yang menggunakan
JSZM (penerjemah dari Z-Machine Daniel Legenbauer). Banyak
permainan tersedia (hanya versi hingga 3 yang didukung).
Dokumen Graham Nelson
Z-Machine Standards , yang telah berurusan dengan Z-machine selama beberapa dekade, juga tersedia.
Dan apakah saya perlu menambahkan dukungan Z-Machine di
8bitworkshop ? Beritahu saya!