Teknik C-Reduce yang Dapat Digunakan di Bahasa Apa Pun

• C-Reduce adalah alat untuk mengecilkan kode reproduksi bug compiler C, tetapi juga dapat diterapkan ke bahasa lain jika ada kondisi deterministik, reproduksi yang cepat, dan file sumber yang bisa dimodifikasi
• Contohnya adalah proses mengecilkan bug yang muncul saat menjalankan scrapscript di RustPython, dengan interesting.sh menentukan apakah bug tereproduksi dengan mencari pesan error tertentu
• Hanya dengan menjalankan creduce --not-c interesting.sh scrapscript.py, ukuran file berkurang dengan cepat, dan pada tahap awal terlihat progres hampir 50% lebih kecil
• --not-c adalah opsi untuk menghindari pass reduksi khusus C, sehingga membantu mengurangi waktu eksekusi yang tidak perlu pada input seperti Python
• Jika kondisi reproduksi bug dapat dibuat sebagai skrip singkat, laporan bug untuk bahasa selain C pun dapat dibuat lebih kecil dan lebih mudah ditangani dengan C-Reduce

---

Syarat Menggunakan C-Reduce untuk Input Selain C

• C-Reduce adalah alat buatan Regehr dan rekan-rekannya untuk meminimalkan kode reproduksi bug compiler C
• Saat file C 10.000 baris memicu bug Clang, alat ini dapat digunakan untuk mengecilkannya secara otomatis alih-alih mengirim file besar apa adanya
• Meski tampak seperti alat khusus C, C-Reduce juga dapat digunakan untuk input bahasa lain jika memenuhi syarat berikut

  • Kondisi deterministik

    • Metode reproduksi yang relatif cepat, yang membantu kecepatan reduksi
    • Satu atau lebih file sumber yang dapat dimodifikasi dan bisa diperkecil oleh C-Reduce
    • Kondisi deterministik juga dapat ditiru secara probabilistik menggunakan loop wrapper

Contoh Mengecilkan Reproduksi Bug RustPython

• Sebuah bug terjadi saat menjalankan scrapscript di RustPython, dan untuk melaporkannya dibuat skrip interesting.sh
• Skrip menjalankan scrapscript.py dengan path absolut ke binary RustPython, lalu mencari string berikut pada output, termasuk standard error
  • tried to push value onto stack but overflowed max_stackdepth
• Perintah eksekusinya adalah sebagai berikut
  • creduce --not-c interesting.sh scrapscript.py
• C-Reduce menjalankan interestingness test secara paralel dan dengan cepat mengecilkan ukuran file
  • Contoh progres ditampilkan sebagai 0,5%, 9,2%, 18,1%, 47,5%, dan seterusnya
  • Dalam beberapa detik, file berkurang hampir 50%
  • Saat tulisan selesai, reduksi telah mencapai 96,9%
• Jika --not-c tidak digunakan, C-Reduce memakai banyak pass khusus C
  • Pada input Python, pass seperti ini dapat memperlambat waktu eksekusi
  • Kemungkinan besar tidak benar-benar mengubah hasilnya sendiri
• Konten terkait kemudian dipindahkan ke halaman Delta debugging

[GN⁺]

Komentar Hacker News

• Karena file yang sudah diperkecil tidak dibagikan, saya mencobanya sendiri. Saya membangun RustPython, mengambil scrapscript.py, lalu mengubah path di interesting.sh dan menjalankan nix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.py; pada akhirnya proses berhenti di sekitar 96,4%, 7347 byte, dan hasilnya ada di https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...

  • Tiba-tiba terpikir, ada orang lain yang khawatir selama proses reduksi program bisa rusak dan melakukan operasi destruktif pada mesin lokal. Kalau reducer dijalankan sebagai Nix derivation source-to-source, mungkin perilaku berbahaya bisa dicegah dan juga lebih mudah didistribusikan ke remote builder
  • Sebagai catatan, shrinkray kalau dijalankan sekitar 10 menit bisa menyusut hingga 162 byte: https://gist.github.com/DRMacIver/ee025c90b4867125b382a13aaa...
    Kalau dibiarkan lebih lama mungkin bisa sedikit lebih baik, tapi kelihatannya hampir berhenti total jadi saya bosan dan mematikannya

• John Regehr, penulis C-Reduce, juga menyarankan untuk mencoba Shrinkray untuk penggunaan ini. Katanya Shrinkray dibuat agar bekerja independen dari format, dan cocok bahkan pada kasus yang tidak ditangani baik oleh C-Reduce: https://mastodon.social/@regehr/113489759789563570

  • Apakah repositori ini repositori resmi Shrinkray? https://github.com/DRMacIver/shrinkray
  • Saya juga ingin menyebut cvise: https://github.com/marxin/cvise
    Ini adalah alternatif Python yang juga bekerja cukup baik untuk bahasa selain C

• Ada makalah tahun 2012 oleh John Regehr dan penulis lain yang menjelaskan cara kerjanya: https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei...

  • Saya sudah membaca makalah itu, tapi masih belum paham bagaimana ini bisa bekerja. Kelihatannya ia memahami tokenisasi, penggabungan baris, penghapusan token, dan semacamnya untuk bahasa pemrograman arbitrer; saya penasaran apakah ada makalah lain yang menjelaskan algoritmenya secara terpisah
  • Makalah ini bukan tentang keseluruhan C-Reduce, melainkan tentang 3 pengecil test case yang spesifik domain yang ditambahkan ke proyek
    Kalau saya ingat benar, sebagian besar reduksi nonspesifik-domain di C-Reduce lebih mirip brute force sederhana

• Saya baru saja mengetahui C-Reduce, tapi langsung terpikat. Rasanya mirip saat pertama kali menemukan git bisect
  Saya harus menyimpannya di sudut pikiran untuk dipakai suatu hari nanti kalau situasinya pas

  • Saat bekerja di tim compiler C/C++ pada pekerjaan pertama saya setelah lulus kuliah, saya melakukan pekerjaan seperti ini secara manual. Cukup mengejutkan bahwa pekerjaan yang sama bisa diotomatisasi
  • Saya mengalami masalah yang tampaknya bug compiler pada cc65, compiler C untuk prosesor 6502. Targetnya seperti C64, NES, Apple 1
    Saya jadi ingin menyiapkannya. Ternyata VICE mendukung fitur untuk “mengeluarkan” ke file di sistem operasi host, jadi sepertinya pengujian bisa dijalankan di emulator
  • Sangat bagus bila dipakai bersama generator input uji acak

• Delta debugging bukan konsep baru: https://en.wikipedia.org/wiki/Delta_debugging
  Implementasi delta debugging buatan saya, delta, sudah berumur lebih dari 19 tahun: https://github.com/dsw/delta
  Pada masa ketika Microsoft menyebut open source sebagai “kanker”, Microsoft Research sampai mengirim orang ke kantor saya untuk meminta agar ini dipublikasikan, jadi saya merilisnya sebagai open source. Presentasi pengantar LLVM oleh Latner juga menyebutnya sebagai “alat delta debugging standar”, jadi ini alat yang cukup dikenal: https://aosabook.org/en/v1/llvm.html

  • C-Reduce sedikit lebih canggih daripada delta debugging sederhana. Menurut abstrak makalah 2012, "Test-Case Reduction for C Compiler Bugs", hasil C-Reduce rata-rata lebih dari 25 kali lebih kecil dibanding reducer lain maupun reducer yang sebelumnya paling sering dipakai oleh pengembang compiler
    Artinya, reduksi program yang efektif membutuhkan sesuatu yang lebih dari sekadar delta debugging sederhana. Tentu saja, C-Reduce sendiri sekarang juga sudah berumur 12 tahun
    Pada saat yang sama, BugPoint, alat LLVM yang ditautkan itu, khusus untuk LLVM IR, sedangkan C-Reduce tampak lebih umum. Alat dan teknik minimisasi test case otomatis masih asing bagi sebagian besar pengembang, jadi meskipun idenya sudah lama dikenal di bidang ini, tulisan ini tetap bisa bermanfaat

• Saya menemukan tulisan dengan contoh sebelum-dan-sesudah: https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta...
  Meski begitu, saya masih belum benar-benar paham bagaimana ia tahu apa yang harus dihapus pada tiap iterasi. Pasti ada tokenisasi sampai tingkat tertentu, tapi saya tidak tahu bagaimana itu bekerja lintas banyak bahasa pemrograman

• creduce memang luar biasa
  Saat mengembangkan backend target LLVM yang aneh, saya menulis skrip pengujian yang membuat program uji acak dengan CSmith selama berjam-jam. Begitu terjadi crash, skrip itu otomatis menjalankan C-Reduce dan menyisakan file untuk diperiksa; itu benar-benar sangat membantu

• Juga bekerja baik untuk SQL. Saya memakainya di pekerjaan, dan mengetahuinya lewat https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu...

• Sulit dipercaya kalau tidak dijelaskan kenapa ini juga bekerja untuk bahasa selain C. Saya tidak mengira ini bohong, tapi mengejutkan bahwa ini bisa dilakukan tanpa LLM

  • Singkatnya, beberapa pass reduksi cukup tergeneralisasi ke bahasa keluarga C, dan pass-pass ini termasuk yang paling efektif.
    Misalnya, setelah input ditokenisasi dengan cara ala C lalu potongan sepanjang kira-kira 1~13 dibuang secara acak, ini cukup ampuh menghapus qualifier atau atribut yang tidak perlu karena kebanyakan bahasa yang mirip C punya aturan tokenisasi serupa. Pass yang menghapus unit tanda kurung seimbang (), {}, [] juga berguna di hampir semua bahasa. Penghapusan komentar dan spasi juga efektif karena banyak bahasa memakai gaya /* */, // yang sama seperti C.
    Sebenarnya tidak banyak pass yang benar-benar khusus untuk C/C++. Dari pengalaman, salah satu kelemahan besar creduce justru adalah buruknya tahap reduksi untuk menghapus template, yaitu pekerjaan yang tampaknya relatif mudah diotomatisasi
  • Saya sarankan melihat sekilas makalah PLDI yang ditautkan asmeurer. Ringkasannya bagus.
    Sebagian transformasi cukup spesifik ke C karena memakai frontend Clang, dan sebagian lagi cukup umum sehingga kemungkinan besar bekerja untuk bahasa keluarga Algol. Karena ini alat modular, kalau mau Anda juga bisa menambahkan transformasi yang memahami bahasa lain
  • Ini lebih dekat ke ilmu komputer gaya lama. Semoga HN belum sampai melupakan ilmu komputer tradisional seperti itu.
    Yang dibicarakan di sini adalah hal-hal seperti algoritme, bukan machine learning menyeramkan. Termasuk juga hal seperti memakai Prolog untuk AI, meski ada kelemahan kecil bahwa itu tidak terlalu berhasil untuk tujuan membuat AI
  • Kalau tidak paham cara kerjanya, saya tidak tahu apakah aman memakainya seperti ini. Apakah creduce bisa saja menjalankan skrip input yang sudah diubah lalu menghapus file saya atau bahkan melahap makan siang saya?
  • Kalau menebak tanpa membaca makalahnya, ini tampaknya mirip fuzzer yang menerapkan mutasi ke arah memperkecil ukuran input

• Dibandingkan dengan dustmite, bagaimana? https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...