Pada suatu malam musim gugur yang gelap dan penuh badai di tahun 1988 di Madison, Wisconsin, profesor ilmu komputer Barton Miller sedang duduk di depan terminal rumahnya, berusaha bekerja jarak jauh ke workstation UNIX universitas melalui modem dial-up 1200-baud dan saluran telepon analog. Di luar, badai petir hebat sedang mengamuk. Setiap kali petir menyambar, interferensi elektromagnetik menyuntikkan derau (noise) acak ke kabel telepon, merusak aliran karakter ASCII yang dikirim ke shell UNIX.

Apa yang terjadi selanjutnya membuat Miller terpana: setiap kali derau saluran menyuntikkan urutan byte acak ke utilitas standar UNIX yang telah teruji — seperti vi, cc, awk, sed, csh, dan indent — program-program inti tersebut tidak sekadar mencetak pesan kesalahan sintaks, melainkan runtuh satu per satu dengan kesalahan segmentasi (SIGSEGV, Segmentation Fault) atau membeku dalam perulangan tak terbatas.

Terkejut oleh kerapuhan tersebut, Miller menugaskan mahasiswa pascasarjananya untuk membangun generator aliran karakter acak yang ia beri nama “Fuzz”. Hasilnya mengguncang komunitas rekayasa perangkat lunak: antara 25% hingga 33% dari seluruh utilitas standar UNIX di tujuh varian komersial dan akademik langsung crash saat diberi aliran byte murni acak.

Lebih dari tiga setengah dekade kemudian, Fuzzing (Fuzz Testing) telah berevolusi dari generator derau buta menjadi teknik penemuan kerentanan otomatis paling produktif dalam ilmu komputer — menggabungkan instrumentasi kompilator, algoritma genetika evolusioner, pemecah kendala SMT, dan pemetaan memori bayangan (Shadow Memory). Infrastruktur OSS-Fuzz milik Google saja telah secara otomatis menemukan lebih dari 10.000 kerentanan keamanan dan lebih dari 36.000 bug pada proyek open-source kritis seperti OpenSSL, SQLite, FFmpeg, dan kernel Linux.

Mengapa ribuan unit test buatan manusia melewatkan kerusakan memori fatal yang justru ditemukan oleh mutasi otomatis dalam hitungan menit? Artikel ini membedah ledakan комбинаtorial ruang input, empat paradigma fuzzing, arsitektur internal AFL / AFL++ / LibFuzzer (bitmap 64 KB di cache L1, bukti matematis pergeseran >> 1, Forkserver, dan penjadwalan rantai Markov), AddressSanitizer (ASan), serta algoritma Delta Debugging (ddmin) karya Andreas Zeller.

Bab 1: Jurang Kombinatorial Ruang Input dan Efek Lampu Jalan

1.1 Buffer 64 Byte Menyimpan $10^{154}$ Kemungkinan Semesta

Mengapa pengujian unit manual tidak dapat memberantas bug perangkat lunak? Alasan mendasarnya terletak pada ledakan kombinatorial ruang input. Bayangkan sebuah fungsi C sederhana yang mengurai header biner sepanjang $N = 64$ byte. Karena setiap byte memiliki $|\Sigma| = 2^8 = 256$ kemungkinan nilai, jumlah total input 64 byte yang mungkin adalah:

Sebagai perbandingan, bilangan Eddington (perkiraan jumlah total proton di seluruh alam semesta teramati) hanya sekitar $10^{80}$. Bahkan jika seluruh prosesor di Bumi menguji satu triliun ($10^{12}$) input per detik без henti sejak Big Bang 13,8 miliar tahun lalu, kita belum akan menjelajahi $10^{-124}$ bagian dari buffer 64 byte tersebut.

1.2 Efek Lampu Jalan (Streetlight Effect) dan “Weird Machine”

Saat menulis unit test manual, pengembang secara tak sadar terjebak dalam Efek Lampu Jalan (bias observasi): seperti orang yang mencari kunci yang hilang di malam hari hanya di bawah lampu jalan karena terang, manusia hanya menguji jalur normal sesuai spesifikasi dan nilai batas yang sudah terpikirkan saat menulis kode (0, -1, NULL). Padahal, kerentanan kritis bersembunyi di kegelapan “Weird Machine” (Bratus et al.) — mesin 상태 tak disengaja yang muncul dari interaksi integer overflow dan asumsi tersembunyi parser:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int parse_image_chunk(const uint8_t *buf, size_t len) {
    if (len < 16) return -1;
    uint32_t magic  = *(const uint32_t *)(buf + 0);
    uint16_t width  = *(const uint16_t *)(buf + 4);
    uint16_t height = *(const uint16_t *)(buf + 6);
    uint8_t  flags  = buf[8];

    if (magic != 0x494D4721) return -1;          // Mengharapkan tanda "IMG!"
    if (width == 0 || height == 0) return -1;    // Pengembang sudah menguji batas 0!

    uint16_t alloc_size = width * height;        // [BUG] Integer overflow 16-bit!
    if (flags & 0x80) alloc_size += 16;
    uint8_t *pixel_buf = malloc(alloc_size);     // Hanya mengalokasikan 0 atau 16 byte
    memcpy(pixel_buf, buf + 16, (size_t)width * height); // Menyalin 65.536 byte -> merusak heap!
    ...
}

Ketika width = 256, height = 256, perkalian $256 \times 256 = 65536 \equiv 0 \pmod{2^{16}}$ menyebabkan wraparound pada bilangan bulat 16-bit alloc_size menjadi 0, mengalokasikan hanya 16 byte via malloc(16), lalu menimpa 64 KB memori heap melalui memcpy.

Bab 2: Empat Paradigma Utama Fuzzing

Untuk menembus penjaga seperti if (magic != 0x494D4721) (peluang tebakan acak $2^{-32} \approx 1 / 4,29\times 10^9$), fuzzing berkembang melalui empat paradigma:

Dalam eksekusi konkolik (Concrete + Symbolic), byte input dimodelkan sebagai variabel simbolik $\vec{\alpha}$ dan kondisi cabang terakhir dinegasikan untuk SMT solver:

Sebaliknya, AFL (dirilis oleh Michał Zalewski pada 2013), AFL++, dan LibFuzzer menggantikan SMT solver dengan seleksi alam Darwinian yang dipandu oleh cakupan tepi (edge coverage).

  flowchart LR
    SeedQueue["Antrean Benih (Seed Corpus)<br/>Input 'menarik' yang disimpan"] --> NextInput["1. Pemilihan Benih<br/>(Penjadwalan AFLFast / Entropic)"]
    NextInput --> Mutator["2. Mesin Mutasi Genetik<br/>(Bitflips, Arith, CmpLog, Havoc, Splice)"]
    Mutator --> ForkServer["3. Eksekusi Kecepatan Tinggi<br/>(Forkserver / Persistent Mode)"]
    ForkServer --> Bitmap["4. Bitmap Memori Bersama 64 KB<br/>(Pelacakan Transisi Tepi CFG)"]
    ForkServer --> Sanitizer{"Crash atau<br/>Jebakan Sanitizer?"}
    Sanitizer -- "Ya (SIGSEGV / ASan)" --> Triage["Triase & Minimisasi Crash<br/>(Stack Hash & ddmin)"]
    Sanitizer -- "Tidak" --> NewCov{"Tepi CFG Baru atau<br/>Bucket Hitungan Baru?"}
    Bitmap --> NewCov
    NewCov -- "Ya (Peningkatan Fitness!)" --> AddQueue["Promosikan ke Antrean Benih<br/>(Menjadi Induk Generasi Berikutnya)"]
    AddQueue --> SeedQueue
    NewCov -- "Tidak (Jalur Redundan)" --> Discard["Buang Input Hasil Mutasi Segera"]

Bab 3: Di Dalam Mesin AFL — Instrumentasi Tepi, Bitmap 64 KB, dan Bukti Matematis >> 1

3.1 Mengapa Cakupan Tepi (Edge Coverage) Mengungguli Cakupan Blok Dasar

Jika fuzzer hanya mencatat blok dasar (node) mana yang dikunjungi, setelah menjalankan jalur $A \to B \to C$ semua blok $\{A, B, C\}$ telah ditandai. Ketika input kedua melewati blok inisialisasi $B$ dan mengambil jalur langsung $A \to C$ (memicu dereferensi pointer NULL di $C$), karena $\{A, C\} \subset \{A, B, C\}$, fuzzer berbasis node akan membuang input tersebut sebagai redundan! Dengan mencatat pasangan transisi terarah (tepi/edge) $(B_{\text{prev}} \to B_{\text{cur}})$, AFL langsung mengenali bahwa tepi $(A \to C)$ adalah jalur baru.

3.2 Trampolin 3 Baris, Cache L1 64 KB, dan Keharusan Matematis >> 1

AFL menyuntikkan tiga operasi berikut di awal setiap blok dasar saat kompilasi:

1
2
3
4
5
6
7
8

/* Compile-time random 16-bit ID assigned to the current basic block */
cur_location = <COMPILE_TIME_RANDOM_16BIT>;

/* Record the transition edge (prev -> cur) in the 64 KB shared bitmap */
shared_mem[cur_location ^ prev_location]++;

/* Right-shift by 1 bit to preserve directionality and self-loops */
prev_location = cur_location >> 1;

Mengapa shared_mem berukuran tepat $2^{16} = 65.536$ byte (64 KB)? Karena 64 KB muat sepenuhnya di dalam cache data L1/L2 inti CPU modern, mencegah cache miss ke DRAM utama dan menyelesaikan pencatatan hanya dalam ~1 nanodetik.

Mengapa pergeseran kanan 1-bit (>> 1) pada prev_location = cur_location >> 1; mutlak diperlukan secara matematis? Tanpa pergeseran tersebut, operator XOR ($\oplus$) mengalami dua degenerasi aljabar fatal:

1. Hilangnya arah akibat sifat komutatif ($A \oplus B = B \oplus A$): Lompatan $A \to B$ dan lompatan balik $B \to A$ menghasilkan indeks bitmap yang sama persis.
2. Musnahnya self-loop akibat sifat nilpoten ($A \oplus A = 0$): Setiap blok yang melompat ke dirinya sendiri ($A \to A$) menghasilkan $0$, sehingga seluruh self-loop di dalam program bertabrakan di satu byte tunggal shared_mem[0]!

Pergeseran >> 1 mematahkan simetri dan nilpotensi sekaligus dalam satu siklus clock CPU. Selain itu, AFL mengelompokkan jumlah eksekusi ke dalam 8 bucket logaritmik ($1, 2, 3, 4\text{–}7, 8\text{–}15, 16\text{–}31, 32\text{–}127, 128\text{–}255$) untuk mendeteksi tonggak iterasi loop tanpa membanjiri antrean.

3.3 Forkserver, Persistent Mode, dan Penjadwalan Rantai Markov (AFLFast / Entropic)

Untuk menghilangkan overhead besar dari execve() dan dynamic linker (ld.so), Forkserver AFL menghentikan proses tepat sebelum main() dan menggandakan proses anak hanya melalui Copy-on-Write (fork()) lewat pipa fd 198/199. Persistent Mode (LLVMFuzzerTestOneInput) bahkan menghilangkan fork(), memanggil fungsi target di dalam loop memori hingga lebih dari $100.000\text{ execs/dtk}$. Dipadukan dengan CmpLog (RedQueen) dan penjadwal AFLFast / Entropic berbasis rantai Markov serta entropi informasi Shannon $H(s)$, fuzzer memfokuskan energi mutasi pada cabang-cabang langka:

Bab 4: Mengubah Kerusakan Memori Senyap Menjadi Crash Instan — Arsitektur Sanitizer

Karena MMU perangkat keras hanya memeriksa izin akses pada tingkat halaman $4\text{ KB}$, heap overflow sebesar 1 byte atau Use-After-Free hampir tidak pernah memicu SIGSEGV. AddressSanitizer (ASan) mengatasi hal ini melalui pemetaan memori bayangan (Shadow Memory) 1:8:

Setiap 8 byte memori aplikasi yang sejajar dipetakan ke 1 byte bayangan: 0x00 berarti seluruh 8 byte valid, $1 \le k \le 7$ berarti hanya $k$ byte pertama yang valid, dan nilai negatif menandai Redzone beracun (0xfa di heap, 0xf1 di stack) atau memori bebas yang ditahan di Antrean Karantina (0xfd untuk menangkap Use-After-Free). Sebelum setiap akses memori, kompilator menyisipkan pemeriksaan:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/* Compiler-injected ASan check before an N-byte memory access (N = 1, 2, 4) */
uintptr_t shadow_addr = (addr >> 3) + ASAN_SHADOW_OFFSET;
int8_t shadow_val = *(int8_t *)shadow_addr;

if (UNLIKELY(shadow_val != 0)) {
    /* For partial 8-byte words (1 <= shadow_val <= 7) or negative redzones */
    if (shadow_val < 0 || (int8_t)((addr & 7) + N) > shadow_val) {
        __asan_report_error(pc, bp, sp, addr, is_write, N);
    }
}

Dikombinasikan dengan UBSan (perilaku tak terdefinisi & integer overflow), MSan (pelacakan bit-demi-bit memori yang belum diinisialisasi), TSan (deteksi data race dengan vector clock), dan Differential Fuzzing, setiap penyimpangan halus langsung diubah menjadi laporan crash yang presisi.

Bab 5: Triase Crash dan Delta Debugging (ddmin) Andreas Zeller

Ribuan file crash duplikat pertama-tama dikelompokkan berdasarkan akar masalahnya menggunakan Stack Hash dari frame panggilan teratas saat kesalahan terjadi. Selanjutnya, untuk menyusutkan file crash berukuran beberapa megabyte $c$ (panjang $N$) yang penuh dengan derau mutasi menjadi contoh minimal, algoritma Delta Debugging (ddmin) karya Andreas Zeller secara otomatis mencari kasus uji 1-minimal $c^*$ di mana menghapus satu byte pun akan menghilangkan crash:

Dengan mempartisi input menjadi $n$ potongan $\Delta_1, \dots, \Delta_n$ (dimulai dari $n=2$), ddmin menguji setiap himpunan bagian $\Delta_i$, lalu setiap komplemen $\nabla_i = c \setminus \Delta_i$, dan menggandakan granularitas $n \leftarrow \min(2n, |c|)$ bila belum ada pengurangan yang berhasil. Melalui pencarian biner yang diperumum ini, ddmin (afl-tmin dan C-Reduce) mampu memeras file 10 MB menjadi Proof-of-Concept (PoC) berukuran belasan byte hanya dalam $\mathcal{O}(\log_2 N)$ langkah pada kasus terbaik.