Reducer test case adalah alat debugging yang diremehkan

• Saat mencari bagian yang menyebabkan masalah dalam input besar, reducer test case otomatis mengecilkan input sehingga debugging menjadi lebih mudah
• Reducer menerima program, input, dan tes interestingness, lalu berulang kali memeriksa apakah kandidat input yang lebih pendek mereproduksi masalah yang sama
• Bahkan reducer sederhana berbasis penghapusan baris bisa menyisakan satu kata panjang dari /usr/share/dict/words, dan pada contoh C memangkas 78 baris menjadi 54 baris dalam waktu kurang dari 10 detik
• Tes interestingness harus ditulis akurat dan cepat karena ada risiko over-reduction, eksekusi lambat, eksekusi tak berujung, dan lingkungan eksekusi paralel
• Selain panjang input, metrik seperti frekuensi terjadinya error atau panjang jejak eksekusi dapat dimasukkan ke tes interestingness untuk membantu debugging bug non-deterministik dan log jejak yang besar

---

Penyusutan test case

• Saat sebuah program crash pada input besar dan tidak jelas bagian input mana yang menjadi penyebab, mengecilkan input memudahkan identifikasi akar masalah
• Penyusutan manual dilakukan dengan menghapus sebagian input di editor teks lalu memeriksa apakah crash yang sama tetap terjadi
• Dalam penyusutan manual, manusia mudah melewatkan banyak peluang penghapusan, dan setelah penghapusan program bisa selesai normal atau menghasilkan error normal lain
• Jika penghapusan baru efektif ketika bagian A dan B yang saling berjauhan dihapus bersama, ruang pencarian menjadi jauh lebih besar

Struktur dasar reducer test case

• Reducer test case adalah alat yang menerima program, input, dan tes interestingness untuk membuat input menjadi lebih pendek
• Tes interestingness mengembalikan 0 jika input yang telah disusutkan mereproduksi error yang diminati, dan nilai selain 0 jika tidak
• Penyusutan 95~99% umum terjadi, dan dapat membuat debugging jauh lebih mudah
• Reducer tetap bisa bekerja tanpa memahami secara semantik bagian input mana yang perlu dihapus

• Contoh reducer sederhana

  • Program contoh membaca baris dari file dan mencetak Word too long jika ada baris yang panjangnya lebih dari 25
  • Tes interestingness mengembalikan 0 bila keluaran program berisi Word too long, dan 1 bila tidak
  • Reducer Python sederhana membaca input per baris, menulis kandidat input dengan satu baris dihapus ke file sementara, lalu menjalankan tes interestingness
  • Jika kandidat input menarik, input saat ini diganti dengan kandidat itu, dan bila sudah tidak bisa diperkecil lagi hasilnya dicetak ke stdout
  • Hasil saat dijalankan pada /usr/share/dict/words menyisakan hanya antidisestablishmentarianism

Reducer yang lebih kuat dan Shrink Ray

• Contoh program C 78 baris membahas masalah yang menghasilkan keluaran berbeda pada pengaturan FAST=0 dan FAST=1
• Tes interestingness lulus hanya jika setelah dikompilasi dengan dua pengaturan itu, keluaran FAST=0 adalah 0d754a56 dan keluaran FAST=1 berbeda dari nilai tersebut
• Reducer sederhana dapat menyusutkan input C 78 baris menjadi 54 baris dalam waktu kurang dari 10 detik, sekitar 30% berdasarkan jumlah baris
• Jika i=0 ditambahkan agar penghapusan dimulai lagi dari baris pertama setiap kali kandidat menarik ditemukan, waktu eksekusi naik hampir 10 kali lipat dan 3 baris tambahan berhasil dihapus
• Shrink Ray menyediakan berbagai aturan penyusutan dan eksekusi paralel, dan dengan --no-clang-delta ia tidak memakai pengetahuan khusus tentang C
• Setelah sekitar 15 menit, Shrink Ray telah mengurangi input lebih dari 60% berdasarkan byte, dan pada kasus lain menemukan penyusutan sekitar 90% setelah kira-kira 20 menit lalu melanjutkan hingga 99%
• Shrink Ray memahami sintaks komentar standar dan mencoba menghapusnya di tahap awal, serta juga mencoba mengecilkan integer ke nilai yang lebih kecil

Sulitnya menulis tes interestingness

• Karena reducer test case mengikuti tes interestingness secara harfiah, tes yang keliru lolos dapat menyebabkan over-reduction, yaitu input menyusut melampaui titik yang diinginkan
• Shrink Ray secara eksplisit memeriksa apakah tes interestingness menerima input kosong, dan situasi seperti ini cukup sering terjadi
• Pada contoh C, jika hanya memeriksa apakah dua keluaran berbeda, maka perbedaan keluaran yang tidak penting atau menyesatkan bisa diklasifikasikan sebagai input menarik
• Pemeriksaan test "$slow_out" = "0d754a56" memastikan versi lambat benar-benar menjalankan perilaku yang diharapkan, sehingga mengurangi kemungkinan over-reduction

• Kecepatan dan timeout

  • Jika tes interestingness cepat, reducer bisa dijalankan ratusan kali per detik
  • Bahkan contoh berukuran sedang bisa menghasilkan ratusan ribu percobaan penyusutan, jadi optimasi tes interestingness sangat memengaruhi total waktu
  • Ada kasus di mana tes interestingness dibuat sekitar 3 kali lebih cepat dengan mematikan pembuatan core dump otomatis
  • Reducer bisa menghapus baris seperti i-=1 dan mengubah program yang tadinya selesai menjadi program yang berjalan tanpa akhir
  • Jika program berjalan dalam 0,1 detik tetapi timeout ditetapkan 60 detik, seluruh proses penyusutan akan melambat drastis
  • Untuk program yang cepat, timeout biasanya dibulatkan ke atas menjadi 1~2 detik, sedangkan untuk kasus lain dipakai sekitar 1,5~2 kali waktu eksekusi awal

• Eksekusi paralel

  • Reducer seperti Shrink Ray menjalankan tes interestingness secara paralel
  • Shrink Ray menjalankan setiap tes interestingness di direktori sementara dan membersihkan direktori itu secara otomatis
  • Dalam beberapa kasus, direktori sementara saja tidak cukup, dan langkah yang dibutuhkan berbeda-beda tergantung kasusnya

Mendorong determinisme dengan tes interestingness

• Potongan contoh menghasilkan error pembagian dengan nol karena len([])==0, tetapi karena kondisi random.random() < 0.33, masalah itu hanya muncul pada sekitar sepertiga eksekusi
• Bug non-deterministik membuat error muncul dan hilang secara acak, sehingga pengujian hipotesis menjadi lebih sulit dan memakan waktu
• Jika reducer menghapus pemanggilan random.random() atau mengubah ekspresi kondisi, error non-deterministik bisa berubah menjadi error deterministik
• Non-determinisme nyata sering kali melibatkan interaksi merugikan antara beberapa bagian input, sehingga sulit dihilangkan
• Reducer test case bekerja seperti algoritma hill-climbing yang memakai panjang input sebagai metrik pengganti untuk “lebih baik”
• Pendekatan hill-climbing mudah terjebak di optimum lokal, dan input yang lebih pendek tidak selalu lebih baik untuk menelusuri error

• Pendekatan eksekusi berulang

  • Saat menangani bug non-deterministik, tes interestingness sering dijalankan beberapa kali pada input yang sama, dan input diterima jika error yang diminati muncul setidaknya sekali
  • Cara ini dapat membantu meningkatkan frekuensi munculnya error
  • Tes yang lulus bila error muncul setidaknya sekali tetap menerima input non-deterministik, sehingga selama penyusutan berlangsung non-determinisme justru bisa meningkat
  • Cara yang lebih ketat adalah tes yang hanya menerima input bila error muncul pada semua dari n kali pengulangan
  • Tes yang ketat membuat peluang input awal lolos menjadi rendah sehingga sulit memulai Shrink Ray; pada contoh dengan syarat 3 kali pengulangan, peluang lolos awal hanya 3,6%
  • Jalan keluar yang praktis adalah memulai dengan tes “error muncul setidaknya sekali dari n kali”, lalu setelah mendapatkan input yang disusutkan dengan error lebih sering muncul, beralih ke tes “error muncul n kali berturut-turut”

Counter global dan metrik tujuan lainnya

• Intervensi manual memang kuat, tetapi mengharuskan kita mengawasi Shrink Ray dan mudah melewatkan momen yang tepat untuk campur tangan
• Jika ingin mengarahkan reducer dengan sifat selain panjang input, sifat itu bisa dipaksakan di dalam satu tes interestingness
• Dalam debugging yk, panjang jejak eksekusi—yakni nilai yang mendekati jumlah instruksi yang dijalankan program—lebih penting daripada panjang input
• Keluaran YKD_LOG="$t:jit-asm" menulis trace IR tekstual dan instruksi mesin ke file, dan keluaran jit-asm yang pendek mempermudah debugging
• wc -l digunakan untuk menghitung jumlah baris file log sebagai metrik pengganti yang mendekati panjang jejak
• Tes interestingness memperlakukan input sebagai tidak menarik jika jumlah baris jejak saat ini lebih besar dari nilai minimum sebelumnya, dan nilai minimum itu disimpan di /tmp/global_best
• Cara ini tidak aman untuk penyusutan paralel dan mengandung asumsi tentang cara reducer memanggil tes, tetapi untuk skrip singkat sekali pakai ketidaksempurnaan ini dianggap masih dapat diterima
• Pada kasus segfault yk, penyusutan biasa masih menyisakan jejak 40K baris, tetapi teknik ini menghasilkan jejak 10.1K baris alih-alih input yang lebih kecil, dan memungkinkan akar bug ditemukan dalam 30 menit

Ringkasan inti

• Reducer test case bukan alat yang hanya berguna bagi penulis compiler; alat ini juga bisa dipakai untuk masalah non-compiler
• Selain tujuan dasar mengurangi panjang input, sifat seperti frekuensi error, waktu wall-clock, tingkat non-determinisme, dan panjang jejak dapat diarahkan melalui tes interestingness
• Akurasi, kecepatan eksekusi, timeout, dan keamanan eksekusi paralel dari tes interestingness sangat menentukan efektivitas reducer di dunia nyata
• Meski hampir tidak memahami makna input dan program, reducer tetap bisa mempertahankan masalah dalam bentuk yang lebih kecil dan meningkatkan produktivitas debugging

[GN⁺]

Pendapat di Lobste.rs

• Saya benar-benar penasaran, adakah orang yang tidak mengakui nilai dari penyusutan kasus uji otomatis? Kata “diremehkan” terdengar seolah ada orang yang tidak selalu menginginkan penyusutan kasus uji
  Bahkan jika bug bisa langsung diisolasi, bukankah kita tetap membutuhkan kasus yang sudah diperkecil untuk uji regresi?

  • Kebanyakan developer mungkin bahkan belum pernah memikirkannya sebagai sebuah teknik
  • Kalimat pertama artikel itu adalah “Test-case reducers are less well known than they should be, [...]”, dan sebagai orang yang selama beberapa tahun menganjurkan orang memakai fuzzing dan property-based testing, itu terasa tepat
    Keduanya sering menyertakan pengecilan contoh kegagalan atau bentuk seperti “shrinking”, dan berkat itu jadi jauh lebih praktis digunakan
  • Saya kurang lebih tahu soal ini di fuzzer. Setelah fuzzer menemukan contoh kegagalan, ia otomatis mengecilkannya, dan bagian itu bekerja sangat baik
    Namun dari pengalaman saya dengan fuzzing secara umum, khususnya memakai AmericanFuzzyLop dan AFL++, penyiapannya terlalu menyakitkan sehingga saya cenderung menghindarinya
    Sebagian besar bug yang saya temui juga lebih dekat ke “ini salah untuk seorang pengguna di suatu tempat” daripada “kalau file input ini dimasukkan maka perilakunya salah”. Kadang bisa dipersempit menjadi “jika serangkaian langkah dijalankan dalam kondisi tertentu maka terjadi perilaku salah”, tetapi 1) saya tidak benar-benar tahu bagaimana menerapkan penyusut kasus uji otomatis ke “pengguna melakukan sesuatu secara berurutan”, dan 2) begitu saya menemukan cara mereproduksinya secara lokal, 99% pekerjaan debugging praktis sudah selesai
    Sepertinya penulis akan menganggap sikap saya ini sebagai bentuk “meremehkan”
  • Saya rasa sangat sedikit orang yang bahkan tahu apa itu penyusutan kasus uji

• Artikel dan contohnya mengatakan bahwa reducer seharusnya lebih luas digunakan juga di situasi non-compiler, tetapi sudut pandangnya tetap cukup berat ke arah penulis compiler
  Seperti yang ditulis ~silentbicycle, kebanyakan penyusutan kasus uji terjadi dalam konteks fuzzer atau property-based testing, dan kemampuan penyusutan sudah tertanam di dalam framework yang lebih besar. Compiler adalah salah satu ranah yang agak unik di mana penyusut kasus uji mandiri berguna. Saya tidak terlalu yakin ada banyak kasus lain di mana penyusut mandiri benar-benar membantu
  Bagian tentang determinisme juga menarik. Contohnya dimulai dari file input yang memicu bug, yaitu skrip, sehingga sifat deterministiknya muncul dari situ, bukan karena interpreter sebagai program yang mengandung bug itu sendiri bersifat deterministik. Tidak jelas apakah artikel itu bermaksud bahwa teknik “interestingness” juga bekerja pada situasi non-compiler dengan program buggy yang sendiri bersifat non-deterministik
  Sebagai cara menyesuaikan masalah pengujian agar cocok untuk fuzzing dan penyusutan kasus uji, saya menyarankan membuat sekumpulan perintah imperatif bernomor. Setiap perintah diberi pemeriksaan konsistensi ringan yang bisa mendeteksi kegagalan pengujian, sehingga kasus yang tidak langsung crash juga bisa tertangkap. Pemeriksaan konsistensi yang berat sebaiknya dipisah menjadi perintah tersendiri agar tidak terlalu memperlambat pengujian. Dalam pengujian acak sederhana, harness pengujian cukup memilih perintah secara acak sampai ada sesuatu yang rusak; lalu saat beralih ke harness fuzzer, cukup gunakan aliran byte input fuzz untuk memilih perintah. Dengan begitu, Anda otomatis mendapatkan hal-hal baik seperti uji regresi yang deterministik dan penyusutan kasus uji
  Saya tidak pernah mendapat hasil berarti dengan secara eksplisit menyuruh libfuzzer mengurangi kasus uji, mungkin karena libfuzzer sudah melakukannya selama menghasilkan input. Karena itu saya tidak pernah terlalu termotivasi mencoba lebih banyak pemeriksaan interestingness yang membantu fuzzer umum mengecilkan kasus uji. Saya penasaran apakah orang lain pernah berhasil

  • Sangat setuju. Saya sering memakai pendekatan seperti ini. Buat representasi simbolik dari interface yang memiliki state, lalu biasanya buat interpreter sederhana berbasis switch-case atau match, hasilkan daftar operasi secara acak untuk dijalankan, lalu kecilkan input yang memicu assert yang menangkap pelanggaran pra/pasca-kondisi atau korupsi internal
    Mau disebut property-based testing, fuzzing, atau lightweight model checking, pendekatan ini bisa sangat efektif untuk menemukan bug yang dalam. Saya sudah melihat banyak interface stateful di mana tiap operasi secara terpisah benar, tetapi asumsi satu sama lain sedikit tidak cocok, dan ketika operasi-operasi ini digabung dengan cara yang tak terduga, itu membesar menjadi korupsi internal
    Menjalankan daftar operasi itu berdampingan dengan implementasi sederhana seperti hash table atau list berbasis in-memory, lalu memeriksa apakah hasilnya cocok, juga sangat berguna. Jika ada perbedaan, biasanya itu bug atau kasus batas yang perlu didokumentasikan lebih baik
  • Saya kadang menangani optimisasi transportasi, dan sering menemui skenario yang cukup kompleks di mana invariant rusak. Akan sangat bagus jika ada penyusut kasus uji, tetapi dulu saya harus puas mengecilkannya secara manual[0]
    Sayangnya file datanya terlalu kompleks sehingga shrinkray tampaknya sulit menanganinya. Ia membaca data tabular dari beberapa “file” berbeda, dan ada dependensi jarak jauh juga, jadi sepertinya saya harus mengenkodekan sendiri pengetahuan domain tentang cara mengecilkannya
    Melihat laju perkembangan AI, jika nanti muncul skenario seperti ini lagi saya mungkin akan menulis reducer khusus
    [0] Kalau mau membawa ontologi yang agak kabur, masalah optimisasi adalah masalah pencarian untuk meminimalkan biaya, yang pada dasarnya sama seperti compiler, jadi ini bukan contoh yang sepenuhnya ideal

• Saya membaca ini tiga kali untuk mencoba memahami bagaimana menerapkannya pada tes yang ditulis dengan pytest
  Saya ingin mengurangi kompleksitas test suite saya, jadi mungkin saya akan membacanya untuk keempat kalinya saat sedang tidak bekerja

  • Jika Anda memakai Python, langkah pertama adalah mengadopsi Hypothesis, yang sudah punya penyusutan kasus uji bawaan

• Tahun lalu saat melihat masalah urutan eksekusi tes di CI, saya membuat sebuah alat yang membantu mengecilkan daftar tes
  Pada dasarnya caranya dengan menjalankan potongan baris yang terus dibelah dua
  Skripnya sendiri cukup penuh bug, tetapi keren juga melihat daftar 5000 tes menyusut menjadi daftar sekitar 4 tes yang memicu bug konkurensi saya
  Saya benar-benar penasaran apakah Shrink Ray akan langsung bekerja untuk kasus saya. Saya sungguh merasa “mengecilkan himpunan baris berdasarkan tes” seharusnya menjadi fitur yang ada dalam kumpulan alat command-line standar

• Terkait topik ini, property-based testing juga memakai pendekatan yang cukup mirip, yaitu “mengecilkan” ruang keadaan dari input yang dihasilkan untuk membuat contoh tandingan bagi pengujian
  Keunggulan property-based testing adalah ruang pencarian bisa diarahkan dan distrukturkan. Input bisa dibuat sebagai himpunan transisi yang menggerakkan state machine yang memodelkan program
  Saya selalu heran melihat teknik ini masih terlalu jarang dipakai, bahkan di ranah yang sangat cocok seperti database dan sistem terdistribusi. Minggu lalu saja saya membuat tes seperti ini di $WORK dalam waktu kurang dari beberapa jam, dan dengan cepat menemukan bahwa sistem kami tidak konvergen. Tes itu menghasilkan jejak yang rapi dan langsung bisa dipahami saat ditunjukkan ke rekan kerja
  Secara pribadi, menurut saya ini adalah teknik pengujian dengan imbal hasil terhadap investasi terbaik saat melakukan debugging sistem yang kompleks