Insiden ketika malloc merusak JPGLoader Serenity, atau: Rahasia memenangkan lotre (2021)

• Kesalahan warna JPG di SerenityOS tampak seperti masalah urutan argumen RGB/BGR, tetapi sebenarnya bermula dari JPGLoader yang menyerahkan komponen yang membutuhkan urutan tertentu pada urutan iterasi HashTable
• Dengan diperkenalkannya malloc_good_size() di AK+LibC, Vector dan HashTable mulai memanfaatkan ukuran chunk malloc yang sebenarnya, dan akibatnya jumlah bucket HashTable berubah sehingga bug tersembunyi terungkap
• Kode lama secara kebetulan membaca komponen Y, Cb, Cr pada urutan yang benar, dan berkat hasil int_hash serta jumlah bucket yang kebetulan cocok, kesalahan pemrosesan stream Huffman tertutupi
• Penelusuran penyebab dimulai saat JPGLoader.cpp tidak berubah baru-baru ini, dan karena perubahan AK dalam bisect 1000 commit, OS berukuran sekitar 3400 file harus di-rebuild penuh beberapa kali
• Perbaikan akhir adalah membuat komponen diiterasi dalam urutan deterministik, sementara tambalan sementara yang sekadar mengubah urutan argumen warna bisa memunculkan masalah yang sama lagi saat urutan berubah berikutnya

---

Kesalahan warna JPG yang tampak seperti kebingungan RGB/BGR

• Terjadi masalah di SerenityOS ketika gambar JPG dibuka, warnanya ditampilkan secara keliru
• Jika urutan argumen konstruktor Color di JPGLoader.cpp diubah, gambar tampak normal
  • Kode lama: diteruskan dalam urutan Y, Cb, Cr
  • Perubahan sementara: diteruskan dalam urutan Cr, Cb, Y
• Namun perubahan non-revert terakhir pada JPGLoader.cpp menurut Git sudah lebih dari sebulan sebelumnya, dan ada ingatan bahwa gambar latar JPG masih terlihat normal 1–2 minggu sebelumnya
• Karena itu, kemungkinannya lebih besar bukan sekadar kesalahan urutan channel warna, melainkan perubahan lain yang mengekspos bug lama

Bisect yang menjadi sulit karena perubahan AK

• SerenityOS menggunakan pustaka standarnya sendiri, AK(Agnostic Kit)
  • AK berperan mirip C++ STL, tetapi diubah bersama kode sistem operasi dalam repositori yang sama
• Jika AK berubah, cakupan dampaknya menjadi luas
  • Pustaka standar di-include oleh hampir semua kode
  • Karena definisi template C++ harus berada di header, perubahan header AK memicu recompilation yang luas
• Setiap melewati commit yang berisi perubahan AK, seluruh sistem operasi harus dibangun ulang
  • Sekitar 3400 file pada saat artikel ditulis
  • Selama melakukan bisect pada rentang 1000 commit, build penuh dilakukan 4–5 kali di laptop Sandy Bridge Mobile tahun 2011
• ccache juga tidak bisa menangani kasus ini, dan karena laju perubahan proyek SerenityOS yang cepat, AK berubah kira-kira sekali setiap 100 commit

Masalah tersembunyi yang diungkap malloc_good_size()

• Setelah melakukan bisect 1000 commit, perubahan yang merusak warna JPG ditemukan bukan di JPGLoader, melainkan di sisi AK+LibC
• Commit yang mengungkap masalah adalah f89e8fb71a4893911ee5125f34bd5bbb99327d33
  • Judul: AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable
  • Waktu penulisan: 15 Mei 2021
• Commit ini mengimplementasikan API macOS malloc_good_size()
  • Mengembalikan ukuran alokasi aktual untuk ukuran alokasi yang diminta
  • Misalnya, jika permintaan 35 byte secara internal memakai chunk 64 byte, sisa 29 byte dapat dimanfaatkan
• Setelah perubahan ini, Vector, HashTable, dan lainnya mulai lebih memanfaatkan memori yang tersedia di dalam chunk malloc
• Karena pada commit tepat sebelumnya gambar JPG ditampilkan normal, perubahan ini dipersempit sebagai penyebab tereksposnya masalah lama yang tersembunyi

Decoding yang bergantung pada kapasitas HashTable

• Awalnya dicurigai ada kemungkinan JPGLoader atau kode level atas secara keliru bergantung pada kapasitas Vector dan menulis langsung ke sana
• Perubahan terkait ada di HashTable dan Vector, dan keduanya digunakan dalam kode JPGLoader
• Ketika baris penerapan kmalloc_good_size() di sisi HashTable dihapus secara acak lalu di-build ulang, masalahnya hilang
  • Kode yang dihapus adalah bagian yang menyesuaikan kapasitas bucket baru dengan ukuran alokasi aktual
• Dari hasil ini dipastikan bahwa perubahan jumlah bucket pada HashTable memengaruhi hasil decoding JPG
• HashTable bukan container yang digunakan seperti stream data berurutan, jadi secara struktur tidak semestinya bergantung pada kapasitas atau urutan iterasinya

Cara komponen JPG diproses

• JPGLoader lama membaca informasi komponen dari bagian Start of Frame pada file JPG dan menyimpannya ke struct Component
• Setiap Component memiliki serial_id yang menunjukkan posisinya dalam file JPG
  • Urutan komponen JPG umumnya harus Y, Cb, Cr
• Komponen-komponen ini disimpan dalam HashTable
  • Kemudian digunakan untuk dibandingkan dengan urutan komponen pada bagian Start of Scan guna memastikan apakah urutannya sesuai yang diharapkan
• Pada tahap decoding, komponen-komponen ini diiterasi sambil menggunakan informasi yang diperlukan untuk transformasi macroblock
• Masalahnya ada pada memasukkan komponen yang urutannya penting ke HashTable lalu mengiterasinya dengan iterator default

Perbedaan urutan iterasi antara commit yang rusak dan yang normal

• Pada commit yang menghasilkan warna rusak, output debug mengiterasi komponen dalam urutan berikut
  • 0
  • 2
  • 1
• Pada commit normal tepat sebelumnya, urutannya berbeda
  • 0
  • 1
  • 2
• Perbedaan ini berkaitan dengan hasil yang tampak seperti pembalikan channel warna
• Saat mencoba mengubah urutan komponen secara manual bersama CxByte, muncul kesalahan berikut
  • Huffman stream exhausted. This could be an error!
  • Failed to build Macroblock 3277
• Kesalahan ini menunjukkan bahwa decoding JPG sensitif terhadap urutan stream, dan memastikan bahwa urutan iterasi komponen adalah penyebab utamanya

Urutan HashTable yang kebetulan cocok

• Akar masalahnya adalah menyimpan objek yang membutuhkan urutan ke HashTable lalu mengiterasinya dengan iterator default
• Hash ID komponen JPG melewati int_hash dan digunakan untuk memilih bucket
• Sebelumnya, dua kebetulan terjadi bersamaan
  • Hasil int_hash untuk nilai 0, 1, 2 stabil
  • Jumlah bucket AK::HashTable kebetulan pas sehingga komponen ditempatkan dalam urutan yang benar
• Berkat kebetulan ini, JPGLoader membaca stream Huffman untuk tiap komponen dalam urutan yang benar, dan bug tersebut tertutupi sejak awal
• Ketika malloc_good_size() diperkenalkan, jumlah bucket HashTable berubah, urutan komponen ikut berubah, dan muncul gambar dengan channel merah dan biru yang tertukar

Perbaikan akhir dengan iterasi deterministik

• Setelah sekitar 10 jam debugging, commit perbaikan dibuat
• Commit perbaikannya adalah a10ad24c760bfe713f1493e49dff7da16d14bf39
  • Judul: LibGfx: Make JPGLoader iterate components deterministically
  • Waktu penulisan: 31 Mei 2021
• Inti perbaikannya adalah membuat JPGLoader mengiterasi komponen dalam urutan deterministik
• Cara sekadar mengubah urutan argumen Color juga membuat gambar tampak normal untuk saat itu, tetapi jika perubahan lain kelak mengubah urutan iterasi lagi, masalahnya bisa muncul kembali
• Masalah yang tampak seperti kesalahan tampilan kecil ternyata merupakan contoh ketika ketergantungan yang keliru pada urutan iterasi container berpadu dengan perubahan ukuran alokasi hingga akhirnya terungkap

[GN⁺]

Komentar Hacker News

• Ini salah satu alasan banyak implementasi tabel hash memasukkan unsur acak ke dalam algoritmanya
  Karena urutan elemen berubah setiap kali dijalankan, kalau tanpa sengaja bergantung pada urutan, masalahnya akan cepat terlihat
  Jika algoritma hash bersifat tetap, orang bisa membuat key yang menumpuk di bucket yang sama dan menyalahgunakannya untuk serangan denial-of-service; masalah keamanan semacam ini juga cukup baik dicegah

  • Sekarang justru banyak implementasi yang menjamin tabel hash selalu diiterasi sesuai urutan penyisipan
    Saya lebih suka yang seperti ini, karena tidak perlu setiap kali memutuskan apakah butuh map terurut atau map tidak terurut
    Beberapa kali saya mengira map tidak terurut sudah cukup, tapi ternyata salah karena alasan yang halus
  • Unsur acak tidak masalah kalau berupa seed yang bisa ditetapkan, disimpan, dicatat di log, dan direproduksi
    Kalau tidak, itu ide yang benar-benar buruk karena membuat masalah lain jauh lebih sulit di-debug
    Keacakan bukan teman, melainkan musuh
    Sekitar 20 tahun lalu, ada cara menyerang server web Java dengan memanipulasi parameter URL agar semuanya masuk ke bucket yang sama, dan itu menjadi serangan denial-of-service besar
    Kalau ingatan saya benar, server web PHP juga mengalami masalah keamanan yang persis sama
    Masalah itu diperbaiki dengan menambahkan seed ke tabel hash, dan tentu saja seed tersebut bisa dikendalikan oleh developer. Karena keacakan bukan teman, melainkan musuh

• Ini terlihat seperti kasus yang waktunya bisa dihemat jika mereka melakukan sedikit lebih banyak debugging, daripada langsung melakukan bisect ala pencarian biner secara membabi buta
  Pada akhirnya, log yang mencetak urutan komponen memang tetap harus ditambahkan

• Debugging-nya bagus, tapi pesan commit-nya juga luar biasa
  Penyebab dan perbaikannya dipadatkan dengan baik dalam beberapa paragraf

• Kalau menunggu cukup lama, C++ juga akan mendapat fitur yang setara dengan malloc_good_size
  https://github.com/cplusplus/papers/issues/18

• Judulnya perlu [2021]

• Ini bukan kesalahan Gunnar. Masalahnya ada pada pihak yang menyimpan data yang memiliki urutan ke dalam file hash
  Selama puluhan tahun melakukan pekerjaan ini, saya sudah beberapa kali mengalami situasi ketika perubahan tata letak memori membongkar bug yang tersembunyi
  Setiap kali itu terjadi, debugging memakan waktu dari beberapa jam sampai beberapa hari
  Kalau pemrograman tidak sulit, kita tidak akan dibutuhkan. Hanya saja saya tidak tahu seberapa lama kalimat ini masih bertahan di era model bahasa besar

  • Benar. Bahkan andaikan itu kesalahan Gunnar sekalipun, rasanya tidak perlu ditulis di pesan commit
    Gunnar memperbaiki sesuatu, dan dalam prosesnya hanya mengungkap masalah pada kode lama yang sudah rusak
    Namun sebagai balasan atas upaya itu, ia mendapat kalimat seperti “Gunnar, I like you, but please don't make me go through this again. :^)”
  • Selama model bahasa besar dilatih dengan kode yang mengandung bug, mereka akan menyarankan kode yang mengandung bug
  • Benar. Dan berbeda dari judulnya, ini juga bukan kesalahan malloc()

• Setahu saya, di SerenityOS ada orang-orang yang saling membantu dengan resource pengujian atau PC

• Membangun SerenityOS dari awal 4–5 kali di laptop Sandy Bridge Mobile keluaran 2011 itu mirip seperti mencoba melakukan pengembangan Windows Vista dengan komputer dari periode antara Windows 3.1 dan Windows 95

  • Dari sisi selang waktu memang benar, tetapi dari sisi performa nyata berbeda
    Sejak 2011, CPU relatif tidak berubah sedrastis itu, sedangkan antara Windows 3.1 dan Vista, x64 menjadi umum dan CPU multicore menjadi lazim
  • Perbandingan yang bagus. CPU developer itu kira-kira berusia 13 tahun
    Vista dirilis internasional pada awal 2007, jadi CPU yang berusia 13 tahun pada saat rilis berarti buatan 1994, sekitar setahun setelah Pentium orisinal keluar
    Saat itu masih banyak orang memakai 486 DX2-66 yang andal
    Cukup mengesankan bahwa CPU berusia 13 tahun masih bisa dipakai untuk mengerjakan proyek modern masa kini. Dulu, sulit mengatakan hal yang sama
    Semoga CPU yang dirilis hari ini juga masih nyaman dipakai sampai setelah 2037
  • Selama setahun terakhir saya memakai Lenovo i5 2011 dengan Windows 11 sebagai desktop utama, lengkap dengan dua monitor
    Visual Studio juga berjalan baik, dan Photoshop hanya sedikit lambat pada tool AI bawaan sistem
    Tab Chrome mungkin ada sekitar 200 yang terbuka, ditambah Slack, WhatsApp, dan 3 browser untuk pengujian
    CapCut rasanya akan lebih enak kalau sedikit lebih cepat untuk editing 4K, tapi proyek 2K yang kompleks masih cukup tertangani
    Baru pada proyek After Effects yang kompleks saya sedikit menyentuh batasnya. Itu yang tidak ia sukai
    Memang sudah waktunya upgrade, tapi untuk sistem yang pada dasarnya diselamatkan dari tempat sampah, ini cukup lumayan

• Saat melihat “Alien Lenna” saya merasa déjà vu, dan ternyata memang itu tulisan yang pernah saya lihat dan bahkan komentari dulu
  https://news.ycombinator.com/item?id=27374942 (2021)