Pemenang International Obfuscated C Code Contest 1988, Xmas.c

 (udel.edu)
3 poin oleh GN⁺ 2023-12-24 | 1 komentar | Bagikan ke WhatsApp
  • Karya pemenang xmas.c dari International Obfuscated C Code Contest 1988 adalah kode C yang tampak seperti hasil ketikan acak, tetapi mencetak lirik The Twelve Days of Christmas
  • Di dalam kode yang lebih kecil daripada keluarannya, terdapat string terenkripsi, lalu kata dan frasa didekripsi dengan substitution cipher dan pemanggilan rekursif
  • Jika operator ternary diuraikan menjadi blok if-then-else dan diberi nama words serta shift, akan terlihat struktur di mana nilai t mengubah alur rekursi
  • shift memasangkan karakter di bagian depan dengan karakter 31 posisi setelahnya, dan words berisi potongan lirik terenkripsi yang dipisahkan oleh garis miring (/)
  • Meski hanya program sederhana untuk mencetak lirik, kombinasi substitution cipher, rekursi dua arah, kode yang tidak perlu, dan argumen yang tidak digunakan menjadikannya contoh obfuscation C yang kreatif

Apa yang dicetak oleh xmas.c

  • xmas.c adalah program C pemenang International Obfuscated C Code Contest 1988
  • Sang analis pertama kali melihat program ini sekitar tahun 2000, lalu membongkar kodenya pada November 2008 untuk memahami cara kerjanya
  • Jika dikompilasi dan dijalankan tanpa argumen, program ini mencetak lirik lagu Natal The Twelve Days of Christmas dari hari pertama hingga hari kedua belas
  • Komentar pada kode asli menyebut bahwa program ini bahkan lebih kecil daripada bentuk “terkompresi” dari keluarannya, dan para juri merasa tampilannya seperti “hasil menekan mesin tik tua secara acak”

Struktur internal yang diuraikan agar mudah dibaca

  • Langkah pertama dalam analisis adalah mengubah semua bentuk a ? b : c menjadi blok if-then-else yang eksplisit
  • Dua string yang sulit dipahami diberi nama sesuai perannya
    • words: kumpulan kata dan frasa terenkripsi untuk membentuk lirik lagu Natal
    • shift: string substitusi untuk mengubah karakter terenkripsi menjadi karakter keluaran yang sebenarnya
  • main() dimulai dengan xmas(1, 0, '\0'), dan setelah itu satu fungsi xmas() menangani seluruh keluaran secara rekursif
  • Variabel t adalah nilai kunci yang mengendalikan arah rekursi dan perilaku percabangan

Substitution cipher dan data lirik

  • String shift pada praktiknya bekerja seperti dua string yang disambungkan
  • Karakter yang ditemukan di separuh depan didekripsi menjadi karakter yang berada 31 posisi setelahnya
    • Misalnya, karakter pertama ! pada string itu berpasangan dengan karakter baris baru yang berada 31 posisi kemudian
  • Cabang t < -50 menggeser string a satu karakter demi satu sampai karakter input _ ditemukan di dalam shift
    • Saat karakter yang cocok ditemukan, fungsi mencetak a[31] lalu mengembalikan nilai
  • String words adalah data lirik terenkripsi yang diuraikan dengan substitution cipher
    • Bentuk ordinal dan potongan lirik tiap bait dipisahkan oleh karakter garis miring (/)

Peran setiap cabang rekursif

  • Cabang t < -72 memanggil ulang fungsi dengan dua argumen pertama ditukar dan words diberikan sebagai argumen ketiga
    • Tujuan utamanya adalah membingungkan pembaca, sekaligus memungkinkan rekursi bersarang yang mengabaikan argumen ketiga
  • Cabang t < 0 mencari garis miring (/) ke-|t| di dalam string, lalu meneruskan string mulai dari karakter setelahnya
  • Cabang t == 0 mendekripsi dan mencetak string sampai garis miring berikutnya muncul, lalu mengembalikan 1
  • Cabang t == 1 dipanggil hanya sekali saat awal untuk memulai rekursi utama dengan xmas(2, 2, "%s")
  • Cabang t == 2 mencetak baris pertama dalam format "On the [ordinal] day of Christmas my true love gave to me\n"
  • Dua blok kondisi terakhir mempertahankan rekursi dalam dua arah
    • Menuruni tanggal saat ini dan mencetak lirik bait tersebut dalam urutan terbalik
    • Menaikkan tanggal hingga hari ke-12 sambil mengulang seluruh bait

Alur eksekusi yang terlihat setelah disederhanakan

  • Setelah perilakunya dipahami, kode ini dapat diubah menjadi versi yang jauh lebih sederhana dengan loop dan rutin pustaka string C
  • Bahkan pada versi yang disederhanakan, data inti words dan shift tetap dipertahankan
  • Cabang t < 0 menggunakan index(a, '/') untuk menemukan pemisah garis miring dan berpindah ke posisi potongan lirik yang diinginkan
  • Cabang t == 0 mendekripsi karakter dan mencetaknya dengan index(shift, *a++)[31]
  • Cabang t == 2 mencetak bagian awal satu bait dalam urutan berikut
    • "On the "
    • ordinal untuk hari tersebut
    • " my true love gave to me\n"

Mengapa obfuscation ini menarik

  • Jika terus disederhanakan sampai akhir, program ini pada dasarnya menjadi kode yang mencetak lirik
  • Namun versi aslinya menggunakan substitution cipher dan rekursi bersama-sama untuk membentuk struktur yang jauh lebih rumit daripada sekadar pencetak keluaran sederhana
  • Potongan kode kecil yang tidak perlu dan argumen acak yang sebenarnya tidak digunakan membuat kode ini semakin sulit dipahami
  • Memahami kode seperti ini berbeda dengan menulisnya sendiri, dan xmas.c dinilai sebagai contoh kreatif dari kode C

Bacaan terkait

1 komentar

 
GN⁺ 2023-12-24
Komentar Hacker News

  • Di dunia TeX juga ada contoh serupa, yaitu xii.tex
    Jika isi ini dimasukkan ke file .tex, menjalankan pdftex, lalu melihat PDF hasilnya, tampilannya seperti ini: https://shreevatsa.net/post/xii/

    • Ini tampaknya lebih seperti suatu bentuk kompresi logis, bukan sekadar obfuscation

  • Saya menyimpannya saat pertama kali dipublikasikan, tetapi berbeda dari nama file di artikel ini, file saya bernama carol.c
    Saat saya kompilasi dan jalankan di sistem modern, pada gcc -o carol carol.c muncul peringatan seperti return type defaults to ‘int’, type of ‘t’ defaults to ‘int’, dan type of ‘_’ defaults to ‘int’

    • Mulai GCC 14, int implisit tidak akan lagi diizinkan: https://fedoraproject.org/wiki/Changes/PortingToModernC#Remo...
    • Masalahnya ada pada pemanggilan xmas() di dalam main sebelum didefinisikan
      Jika dikompilasi dengan GCC di macOS, muncul error ISO C99 and later do not support implicit function declarations; kalau main() dipindahkan ke bawah, program terkompilasi dengan benar dan menghasilkan output yang tepat
    • Mengejutkan bahwa peringatannya ternyata sedikit, dan semuanya hanya muncul pada baris yang sama

  • Melihat ini membuat saya teringat pada kompleksitas Kolmogorov
    Program ini tampak seperti omong kosong, tetapi karena menghasilkan output yang diinginkan, saya jadi penasaran apakah ada program yang menghasilkan output yang sama tetapi lebih pendek dan tampak lebih tidak masuk akal
    Bagaimana cara menemukan program seperti itu?

    • Rekor saat ini untuk program C terpendek yang mencetak lirik 12 Days of Christmas adalah 431 byte: https://code.golf/12-days-of-christmas#c
    • Kemungkinan besar memang ada program yang lebih pendek
      Namun pencarian brute force sangat tidak efisien, jadi jawaban realistisnya kira-kira adalah “lakukan dengan cerdas” dalam arti matematis
      Secara umum, kompleksitas Kolmogorov tidak dapat dihitung, sehingga tidak ada program yang, ketika diberi sebuah string, dapat mengembalikan program terpendek yang menghitung string tersebut
      Meski begitu, pada prinsipnya mungkin saja seseorang membuktikan bahwa kompleksitas Kolmogorov untuk string tertentu adalah X
    • Dalam kebanyakan kasus, menghitung kompleksitas Kolmogorov secara langsung pada praktiknya mustahil, dan menurut saya kita hanya bisa membandingkannya dari sudut pandang kemungkinan, misalnya lebih lambat daripada versi atau nilai tertentu
      Karena itu, ini cocok untuk kompetisi dan kontes jangka panjang, dan karena kurva pertumbuhannya seperti log, penemuan menarik kadang muncul di bagian paling ujung
      Saat ini saya sedang mengadakan mini-kontes hingga Maret tahun depan untuk LLM yang mampu menghafal digit pi terbanyak; hadiah saat ini 100 dolar dan akan dibagikan sesuai proporsi kontribusi di ruang log
      Karena pi secara teoretis cukup dapat dikompresi, menarik untuk melihat apakah model dapat mempelajari himpunan bobot yang mendekati minimum description length (MDL) untuk merekonstruksi algoritme berkompresi tinggi dari data
      Namun belum jelas apakah ini bisa dilakukan dengan model siap pakai, jadi untuk sekarang saya akan membiarkannya sebagai kontes menghafal digit dan mengamatinya

  • Penjelasannya bagus, dan IOCCC tampaknya masih terus hidup pada 2023: https://www.ioccc.org/years.html

    • Jika melihat halaman itu, IOCCC terakhir ditampilkan sebagai tahun 2020
      Namun di beranda ada pembaruan Mei 2023 yang mengatakan mereka “berencana mengadakan IOCCC ke-28”
      Ada hal-hal yang layak ditunggu, seperti rilis Nethack

  • Baru-baru ini saya mengetahui hal menarik tentang The Twelve Days of Christmas: semua hadiahnya adalah jenis burung
    Bahkan para wanita yang melompat dan para bangsawan pun katanya begitu

  • Ada juga hasil riset yang saya lakukan sendiri lebih dari 20 tahun lalu: http://michaeldnahas.com/xmassong/index.html

  • Jika peringatannya dimatikan, ini masih berjalan bahkan di trunk: https://compiler-explorer.com/z/hGvs1e9jo

  • Ini mengingatkan saya pada kenangan indah pada 2022, saat dua semester terakhir saya di universitas, ketika dosen menunjukkan potongan kode ini begitu kuliah dimulai

    • Bisa juga dibaca sebagai lelucon bahwa ingatannya sudah samar karena itu sudah sangat lama, semacam “dua semester terakhir di universitas, berarti tahun lalu dong!”
      Saya tidak bisa membedakan apakah itu serius atau komedi yang sangat datar

  • Saya ingat saat kuliah, dosen saya memasukkan ini ke materi cetak bahasa C, jadi suatu kali saya pernah mengetiknya sendiri dengan tangan

  • Di Rosetta Code juga ada tugas serupa
    Yaitu program untuk mencetak Old Lady Swallowed a Fly, lagu yang bertambah secara berulang: https://rosettacode.org/wiki/Old_lady_swallowed_a_fly