Show HN: Meretas lawan dengan board game meja berbasis assembly RISC-V

 (punkx.org)
3 poin oleh GN⁺ 2023-10-01 | 1 komentar | Bagikan ke WhatsApp
  • PROJEKT: OVERFLOW adalah game pembelajaran yang mengubah assembly RISC-V dan buffer overflow menjadi aturan board game, sehingga pemain bisa langsung menelusuri manipulasi memori, stack, dan return address
  • Para pemain berbagi memori dan program yang sama, lalu bersaing dengan model penjadwalan preemptif yang mengeksekusi hanya 10 instruksi per giliran tanpa memori virtual
  • Penentuan menang-kalah bercabang dari alur membuat shellcode dengan menyalin instruksi yang ada, lalu menimpa return address lawan untuk mengarahkannya ke game_over()
  • Akses memori yang salah, baca/tulis tak selaras, dan instruksi ilegal akan menyebabkan crash dan menjalankan exception handler; perubahan alamat trap dan monkeypatch nop menjadi variabel strategi utama
  • Tersedia versi web, papan untuk dicetak, serta game helper untuk ESP32 dan mobile, tetapi sebagian aturan masih disesuaikan sehingga rasanya lebih mirip puzzle peretasan eksperimental

Tujuan game dan model eksekusi

  • PROJEKT: OVERFLOW adalah proyek yang membahas assembly RISC-V dan buffer overflow dalam bentuk board game meja
  • Tujuan utamanya adalah menyalin instruksi yang ada untuk membuat shellcode kecil di dalam memori, melompat ke kode itu melalui buffer overflow, lalu menimpa return address lawan agar memanggil fungsi game_over()
  • Strateginya melampaui eksekusi kode sederhana dan juga mencakup pengaturan exception handler serta monkeypatch
  • Semua pemain berbagi memori dan program yang sama, serta memakai prosesor yang sama secara time-sharing
    • Dalam satu giliran, 10 instruksi dijalankan
    • stack pointer tiap pemain dimulai dari posisi yang berbeda
    • Tidak ada memori virtual

Alur build dan pembuatan papan

  • Kode dikompilasi dengan riscv64-unknown-elf-gcc untuk target RV32
    • Opsi utama mencakup -march=rv32g, -mabi=ilp32, -ffreestanding, -nostdlib, -nostartfiles, -O0, dan lainnya
    • Berkat -O0, machine code menjadi verbose tetapi lebih mudah diikuti
  • Materi untuk papan dibuat dengan mem-parsing output riscv64-unknown-elf-objdump -S -l -fd game
    • Instruksi ▲ dan ✎ dimodifikasi
    • Offset lompatan diubah dari heksadesimal ke desimal
    • Assembly dirapikan dan dicocokkan dengan source code
    • SVG dibuat lalu dikonversi ke PDF dengan Inkscape

Pencetakan dan perlengkapan

  • Papan digunakan dengan mencetak PDF bagian kiri dan kanan
  • Ukuran cetak yang disarankan adalah A3; A4 juga bisa tetapi kecil
  • Perlengkapannya adalah 1 penanda untuk instruksi nop, 1 penanda untuk alamat trap, 2 penanda per pemain untuk program counter dan stack pointer, serta pensil dan penghapus
  • Versi web mendukung permainan solo dan bermain bersama teman, dan juga tersedia game helper untuk ESP32 dan mobile

Aturan dasar dan jalannya giliran

  • Kondisi awalnya sebagai berikut
    • Semua register dimulai dari 0, tetapi register return address ra dimulai dari 1000
    • sp Player 1 diinisialisasi ke 2244, dan sp Player 2 ke 3844
    • pc kedua pemain dimulai dari alamat awal fungsi main, yaitu 1000
    • Penanda trap diletakkan di alamat 1000
    • Semua alamat memori bernilai 0 kecuali program yang telah dimuat sebelumnya
    • Penanda instruksi nop pada awalnya tidak diletakkan di papan
  • Dalam satu giliran, 10 instruksi harus dijalankan, dan lompatan seperti jal, beq juga harus diikuti sebagaimana adanya
  • Pemain boleh menghentikan gilirannya setelah menjalankan setidaknya 1 instruksi, lalu membawa sisa jumlah instruksi ke giliran berikutnya
    • Batas maksimum instruksi yang bisa diakumulasikan adalah 20

Monkeypatch dan kondisi kemenangan

  • Pada awal tiap giliran, setelah menjalankan tepat 1 instruksi, pemain boleh memindahkan penanda instruksi nop ke alamat mana pun dalam fungsi yang saat itu tidak sedang dijalankan oleh para pemain
  • Saat pc mencapai alamat tersebut, instruksi itu akan berfungsi sebagai no-operation
  • Jika memindahkan penanda nop, pemain kehilangan giliran saat ini dan giliran berikutnya, dan lawan dapat mengeksekusi hingga 20 instruksi pada giliran berikutnya
  • Aturan monkeypatch ini masih belum seimbang dan terus sedikit berubah tiap beberapa hari
  • Dalam hard mode, game berakhir jika Anda meretas lawan sehingga memanggil fungsi game_over()
  • Jika tidak ada pihak yang bisa lagi mengarahkan lawannya ke game_over(), hasilnya seri
  • Dalam easy mode, pemain pertama yang mengeksekusi ret di main dan keluar dari loop utama menjadi pemenang

Simbol khusus dan penanganan pengecualian

  • ✎ memungkinkan pemilihan angka 12-bit sebarang dari 0 sampai 4095 sebagai nilai immediate untuk instruksi li
  • ▲ memungkinkan pemilihan nilai dalam rentang ±128 byte dari stack pointer milik sendiri pada instruksi load
    • Misalnya jika sp adalah 2180, maka yang dapat dipilih adalah 2052 hingga 2308
  • Tindakan terlarang akan menyebabkan program crash
    • Menimpa alamat memori di bawah 1192
    • Membaca atau menulis tak selaras pada alamat yang bukan kelipatan 4
    • Menjalankan instruksi ilegal
  • Jika crash terjadi, exception handler akan dijalankan dan melompat ke alamat trap
    • Alamat trap awalnya 1000, tetapi bisa ditimpa di fungsi set_trap()
    • Saat exception terjadi, program counter disetel ke nilai tertentu lalu eksekusi berlanjut
  • Jika kecurangan atau kesalahan terdeteksi, status program, memori, dan register pemain tersebut akan di-reset

Aturan ekspansi 3–4 pemain

  • sp Player 3 disetel ke 2116
  • sp Player 4 disetel ke 3716
  • Jika ada 3 pemain atau lebih, simbol ▲ hanya bisa dipakai pada rentang -128 byte dari stack pointer
  • Jika dimainkan dengan lebih dari 2 pemain, game menjadi cukup tidak stabil dan cepat rusak
  • Mencapai kondisi kemenangan menjadi lebih sulit, tetapi permainan jadi lebih seru dan kacau

Contoh strategi peretasan

  • Crash bisa digunakan sebagai strategi menyerang untuk menghambat progres lawan
  • Jika trap handler diubah ke fungsi game_over, pemain pertama yang crash akan kalah
    • Dalam kondisi ini, penanda nop menjadi sangat kuat
    • Jika lawan menaruh nop di atas ret dari fungsi yang sedang Anda jalankan, Anda bisa kalah
  • Di fungsi bug(), jika index dioverflow menjadi 400 atau -400, Anda bisa mengakses stack lawan dan menimpa return address-nya
    • Sebagai contoh, untuk berpindah dari alamat 3784 ke 2184, (3784 - 2184) / 4 = 400, jadi dibutuhkan index -400
  • Dengan fungsi copy(), instruksi tertentu bisa disalin untuk membuat shellcode pendek di memori
    • Contoh shellcode adalah kombinasi li a4, ✎, li a5, ✎, sw a4, 0(a5), ret untuk melakukan penulisan sebarang
    • Jika instruksi ret disalin, return address akan disetel ke titik awal shellcode sehingga menjadi loop tak berujung
  • Di fungsi bug(), jika index disetel ke 6, variabel value bisa ditulis ke atas saved return address stack di 28(sp)
    • Saat bug() mengembalikan kontrol, nilai 28(sp) akan disalin ke register return address
    • Jika alamat shellcode yang Anda buat dimasukkan ke sana, maka eksekusi bisa melompat ke memori

Interpretasi instruksi dan perubahan

  • Semua lompatan bersifat relatif terhadap program counter saat ini, walaupun di disassembler terlihat seperti alamat absolut
    • Misalnya, machine code 1903 untuk jal a4, 0 akan menjadi loop tak berujung saat dijalankan
  • Daftar instruksi game yang valid dirangkum dari instruksi RV32 JRI dengan machine code 0 sampai 4095, dalam bentuk yang menggunakan a0, a4, a5, sp, ra, dan sebagainya
  • Log perubahan 0.0.6 mencakup perubahan dari while(run) menjadi while(*prun)
    • Lawan kini bisa memaksa crash dengan memicu dereferensi tak selaras
    • Aturan NOP telah diubah sehingga hanya bisa ditempatkan pada fungsi yang tidak sedang dijalankan

Desain dan materi pembelajaran

  • Persegi di sisi kiri dan kanan papan adalah pesan biner yang dienkode dalam ASCII
    • Persegi putih berarti 1, persegi hitam berarti 0
  • Warna yang digunakan hanya merah, biru, hitam, dan putih agar cocok untuk cetak murah dan tetap terbaca di printer hitam-putih
  • Tidak ada syntax highlighting
    • Ini dipilih agar tidak ada bagian kode yang tampak lebih penting hanya karena tema, dan supaya pemain fokus serta menilai sendiri
  • Materi belajar assembly RISC-V mencakup riscv-programming.org, cs3410 risc-v interpreter, rvcodecjs dari luplab, dan lainnya
  • Untuk belajar C, bagian awal Beej's Guide to C Programming digunakan
  • Tersedia PDF latihan assembly siap cetak yang membahas variabel, pemanggilan fungsi, pointer, string, struct, array, rekursi, dan lainnya, serta versi “assembly hangman” model isi-kosong

Bacaan terkait

1 komentar

 
GN⁺ 2023-10-01
Opini Hacker News

  • Benar-benar mengesankan. Yang paling hebat terutama adalah ia berhasil membuat putrinya yang berusia 12 tahun ikut memainkannya
    Kapan kira-kira kita bisa mengharapkan versi CHERI? :-D

    • Karena “CHERI memiliki tiga tujuan desain inti untuk meningkatkan keamanan TCB bahasa C modern secara signifikan melalui dukungan prosesor untuk perlindungan memori bergranularitas halus dan isolasi perangkat lunak yang dapat diskalakan, dan desainnya memerlukan penyesuaian cermat karena persyaratan yang terkadang saling bertentangan,” sepertinya versi CHERI akan sulit :)
    • Saat berusia 12 tahun, saya menulis assembly 6502. Dalam lingkungan komputer sekarang, tidak mudah bagi anak 12 tahun untuk melakukan itu
    • Pada era 8-bit, itu usia yang umum untuk mulai mengenal komputer

  • Core War adalah gim yang dimainkan di arena memori sebuah virtual machine yang mendukung bahasa assembly simulasi sederhana. Saya pertama kali melihatnya di Scientific American pada 1984, dan karena saat itu saya sudah sekitar 15 tahun memprogram, saya mengenali bahwa gim itu terinspirasi oleh gim yang lebih tua dari Bell Labs, Darwin
    Darwin dibuat pada 1961 dan berjalan di IBM 7090. Program-program bersaing memperebutkan sumber daya, dan program yang menyalin diri untuk menguasai seluruh ruang yang dialokasikan akan menang. Gim itu tidak bertahan lama setelah Robert Morris Sr. membuat program yang tak terkalahkan. Lihat [2]
    Pada pertengahan 1970-an, Software Practice and Experience adalah salah satu jurnal ilmu komputer favorit saya, dan sering memuat kolom Computer Recreations yang ditulis dengan nama pena Aleph-Null. Saat kuliah pascasarjana, saya menikmati mengimplementasikan beberapa gim dari kolom itu. Jurnalnya mahal, tetapi jika Anda mahasiswa, kemungkinan besar bisa menemukannya di perpustakaan kampus seperti saya dulu. Edisi-edisi tahun 1970-an memuat topik seperti compiler Pascal, Algol 68, dan pemrograman konkuren, sehingga mudah dan menarik dibaca; lewat tulisan N. Wirth saya mengenal Module[3,4] dan kemudian Oberon[5]
    [1] https://en.wikipedia.org/wiki/Core_War
    [2] https://en.wikipedia.org/wiki/Darwin_(programming_game)
    [3] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [4] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [5] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43801909...

  • Saya punya teman yang bilang ia suka gim tetapi tidak punya otak untuk coding; lewat Human Resource Machine, ia pada dasarnya jadi melakukan coding, dan beberapa solusinya lebih baik daripada solusi saya yang sudah berpengalaman bertahun-tahun

    • Kadang-kadang sudut pandang baru jauh lebih membantu daripada yang kita kira
      Anak saya yang berusia 12 tahun tidak suka matematika, tetapi ia luar biasa jago di Human Resource Machine dan SpaceChem. Saya jadi bertanya-tanya apakah matematika SMA dan matematika dalam pemrograman pada dasarnya memang berbeda

  • Sangat menarik. Kalau memikirkan ukuran memori komputer saat ini, saya selalu merasa mnemonic pendek adalah pilihan engineering yang kurang baik
    Di sini pun, hal pertama yang harus dilakukan adalah mempelajari dan mengingat apa yang dilakukan instruksi. Jika namanya dibuat lebih deskriptif, akan jauh lebih mudah dipelajari, diingat, dan dibaca kodenya. Mencurigakan bahwa orang-orang tidak sering melakukannya
    Fakta bahwa kerentanan jenis ini mungkin terjadi juga menurut saya menunjukkan kegagalan desain sistem secara keseluruhan. Bukan berarti ini bukan gim yang menyenangkan atau bukan cara belajar yang baik, tetapi dalam engineering, masalah struktural terlalu mudah diterima. Kebanyakan orang bahkan tidak sampai melihat cacat struktural itu

    • Versi awalnya punya pseudo-assembly yang jauh lebih mudah dibaca, dan saya juga mempertimbangkan arah seperti itu. Namun pada akhirnya saya ingin putri saya nyaman membaca output objdump, dan saya tidak melihat mempelajari beberapa mnemonic sebagai masalah besar
      Menurut saya anak-anak benar-benar merespons dengan baik ketika tidak diremehkan. Setidaknya begitu dengan anak saya
      Anda pikir ada orang yang tidak menganggap arbitrary read dan write sebagai cacat struktural? Ribuan orang menangani masalah itu dan sudah membuat kemajuan yang cukup besar. Pada saat yang sama, menurut saya peek dan poke tetap menyenangkan

  • Ini benar-benar keren. Saya ingin mencobanya di kantor

  • Kelihatannya cukup seru. Menurut Anda cocok untuk usia berapa?

    • Kondisi menang yang mudah, yaitu keluar dari main loop dengan buffer overflow cepat di bug(), menurut saya bisa dilakukan anak usia 10–15 tahun
      Putri saya berusia 12 tahun dan kami bersenang-senang memainkannya bersama. Kondisi menang yang sulit, yaitu membuat lawan melompat ke fungsi game_over(), lebih sulit, tetapi sepertinya bisa dicapai dalam 5–6 bulan
      Untuk orang dewasa, saya kurang tahu. Sebagian orang begitu takut pada assembly seolah-olah itu ciptaan iblis, jadi mungkin lebih sulit membuat mereka bermain daripada anak-anak

  • Yang menarik adalah kita cenderung melihat dunia sebagai cermin diri kita sendiri
    Seberapa besar kemungkinannya bahwa karena saya tertarik pada buffer overflow dan pemrograman, putri saya juga tentu akan sangat tertarik? Jika ditambah fakta bahwa ia anak pertama dan anak kedua perempuan, peluangnya tampak makin kecil, tetapi saya tetap melihat banyak ayah yang mendorongnya
    Saat membuat proyek seperti ini, saya penasaran apakah ia setidaknya sadar sampai taraf tertentu bahwa ini adalah proyek vanity. Bagaimanapun, saya tertarik pada hal semacam ini, jadi saya senang ia membukanya untuk publik

    • Yang lebih menarik adalah betapa mudahnya orang membuat asumsi besar demi membuat argumennya terdengar masuk akal
      Anda menyiratkan bahwa pembuat proyek memaksakan ini kepada putrinya karena kesombongannya sendiri, tetapi apa dasar Anda? Saya melihat-lihat beberapa halaman situsnya dan sama sekali tidak menemukan hal yang mengisyaratkan itu; justru ada beberapa ungkapan lembut bahwa putrinya menikmatinya dan sangat tertarik
      Mengapa Anda menyingkirkan kemungkinan bahwa putrinya sendiri yang awalnya terus penasaran tentang apa yang dilakukan ayahnya di komputer? Bisa saja dimulai kecil, lalu berkembang menjadi proses dua arah antara seseorang yang berbagi minat dan rekan penjelajah cilik
      Saya juga tidak tahu kenyataannya seperti apa, tetapi Anda pun tidak. Dari pengalaman saya beberapa tahun terlibat dalam pendidikan, anak-anak adalah pembelajar yang jauh lebih hebat daripada yang umumnya dipercaya. Struktur sekolah mungkin salah satu alasannya, tetapi di intinya mungkin ada keyakinan yang membatasi seperti ini. Saya ingin memberi tepuk tangan kepada ayah ini karena mencoba berbagi minat dan semangatnya dengan putrinya dan dunia
    • Sebagai seorang ayah, saya hanya mencoba mengajarkan semua yang bisa saya ajarkan. Kadang itu pemrograman, kadang bela diri, kadang meditasi
      Sebagian dari itu akan bernilai, sebagian tidak. Peluangnya selalu tidak menguntungkan. Begitulah hidup

  • Kalau jalur kode RISC-V 64-bit sudah stabil, bekerja cukup baik, dan bahkan “buffer overflow” hilang, bagaimana rencana mereka menghadapi keusangan terencana ketika C/C++ tidak selalu mengubah sintaksnya untuk mereka? Jiwa-jiwa malang…

  • Tunggu dulu.
    Board game tabletop yang melibatkan coding assembly? Kenapa saya tidak memikirkan ini sebelumnya? :D

  • PL/I melakukan hal-hal dengan benar seperti pemeriksaan batas string/array dan stack yang tumbuh ke atas, bukan ke bawah
    https://www.acsac.org/2002/papers/classic-multics.pdf