1. Pendahuluan: Bisakah Anda Mengubah Telur Dadar Kembali Menjadi Telur Mentah?

Dalam pengembangan perangkat lunak sehari-hari, kompiler (seperti GCC, Clang/LLVM, atau MSVC) menerjemahkan kode sumber C, C++, atau Rust yang mudah dibaca manusia menjadi file eksekusi kode mesin (.exe PE di Windows atau biner ELF di Linux). Namun, apa yang terjadi jika kita harus bergerak ke arah sebaliknya—misalnya ketika analis keamanan membedah ransomware, insinyur mengaudit driver tertutup, atau perusahaan harus memperbaiki sistem warisan berusia 25 tahun yang kode sumbernya telah hilang? Bisakah kita memasukkan biner mesin ke dalam Dekompilator (Decompiler) dan memulihkan kode sumber C aslinya?

Dalam komunitas rekayasa balik (reverse engineering), ada sebuah pepatah klasik: “Kompilasi itu seperti mengocok dan menggoreng telur menjadi omelet (telur dadar); dekompilasi adalah usaha mengubah omelet tersebut kembali menjadi telur mentah utuh di dalam cangkangnya."

Secara matematis dan teori informasi, fungsi kompilasi $\mathcal{C}: \text{Source} \to \text{Binary}$ adalah pemetaan banyak-ke-satu (non-injektif) yang bersifat lossy (menghilangkan informasi). Tak terhingga banyaknya program sumber yang berbeda—baik nama variabel, komentar, struktur perulangan (for vs. while), maupun fungsi inline—akan menghasilkan urutan byte mesin yang persis sama setelah optimasi (-O2, -O3). Karena entropi bersyarat $H(\text{Source} \mid \text{Binary}) > 0$, tidak ada fungsi invers deterministik $\mathcal{C}^{-1}$ yang dapat memulihkan informasi yang telah dihapus oleh kompilasi dan penghapusan simbol (strip). Lebih buruk lagi, menurut Teorema Rice dan Masalah Berhenti (Halting Problem) Turing, memisahkan byte instruksi dari data secara eksak, menyelesaikan semua target lompatan tak langsung (jmp rax), atau menentukan aliasing penunjuk bersifat tak terputuskan secara matematis (undecidable).

Meski demikian, dekompilator industri modern—seperti IDA Pro (Hex-Rays), Ghidra (dirilis oleh NSA), Binary Ninja, dan angr—secara rutin mengubah megabyte kode assembly menjadi pseudocode C yang bersih dan terstruktur. Artikel ini membedah enam tahapan algoritma utama di balik dekompilator modern.

2. Apa yang Dihancurkan oleh Kompilasi: Pipa Kompilasi Maju

1. Frontend (Parsing & Pemeriksaan Tipe $\to$ IR): komentar, makro #define, alias typedef, nama variabel lokal, dan syntactic sugar lenyap saat diturunkan ke Representasi Menengah (LLVM IR).
2. Optimizer Middle-End (-O2 / -O3): Function Inlining melebur batas antarfungsi; Loop Unrolling dan vektorisasi SIMD merombak struktur perulangan; Strength Reduction mengganti pembagian bilangan bulat x / 10 dengan perkalian titik-tetap konstanta ajaib (imul 0x66666667).
3. Alokasi Register Backend & strip: register virtual SSA yang tak terbatas dipetakan lewat pewarnaan graf ke hanya 16 register fisik pada x86-64. Akibatnya, satu register fisik seperti rax dipakai berulang kali untuk puluhan variabel berbeda dengan tipe berbeda, sementara strip menghapus tabel simbol (.symtab) dan informasi debug DWARF.

  flowchart TD
    subgraph Forward ["Kompilasi Maju (Kehilangan Informasi Tak Terbalikkan)"]
        S1["Kode Sumber Tingkat Tinggi (.c / .cpp / .rs)<br/>Nama, Struct, Typedef, Perulangan Terstruktur"]
        S2["Middle-End IR (LLVM IR)<br/>Syntactic Sugar Dihapus, Fungsi Di-inline, Loop Di-unroll"]
        S3["Biner Mesin Tanpa Simbol (.exe / ELF)<br/>Register Dipakai Ulang, Tipe Dihapus, Lompatan Datar"]
        S1 -->|"Frontend"| S2 -->|"Optimizer & Backend"| S3
    end

    subgraph Backward ["Dekompilasi Terbalik (Rekonstruksi Algoritmik)"]
        D1["1. Disassembly<br/>Aliran Byte ke Instruksi (Linear Sweep vs. Recursive Traversal)"]
        D2["2. IR Lifting & Transformasi SSA<br/>Flag Eksplisit, Pemisahan Rentang Hidup, Rantai Def-Use"]
        D3["3. Analisis Stack Frame & Inferensi Tipe Kekisi<br/>Memulihkan Pointer, Offset Struct, Signedness"]
        D4["4. Penstrukturan Aliran Kontrol (Pemulihan AST)<br/>Pohon Dominator & Pelipatan Wilayah Bebas-Goto (DREAM)"]
        D1 --> D2 --> D3 --> D4
    end

    S3 ==>|"Masukan ke Dekompilator"| D1

3. Tahap 1: Disassembly — Memisahkan Instruksi dari Data

Pada arsitektur panjang instruksi variabel seperti x86-64 ($1$ hingga $15$ byte), kompiler sering menyisipkan data baca-saja—terutama tabel lompatan (Jump Tables) untuk pernyataan switch—langsung di dalam bagian kode .text.

1. Linear Sweep (objdump -d): mendekode byte demi byte secara berurutan dari awal hingga akhir, tetapi salah mengartikan tabel lompatan sebagai instruksi palsu.
2. Recursive Traversal (IDA Pro / Ghidra): mulai dari titik masuk yang diketahui (main, simbol ekspor) dan mengikuti graf aliran kontrol nyata вдоль instruksi percabangan (je, jmp, call). Untuk menyelesaikan lompatan tak langsung (jmp [rbx + rcx*8]), dekompilator menggunakan Backward Slicing dan Value-Set Analysis (VSA) guna menemukan pemeriksaan batas cmp rcx, 12; ja default dan menyimpulkan ukuran tabel lompatan.

4. Tahap 2: IR Lifting dan Bentuk Static Single Assignment (SSA)

Instruksi mesin asli memiliki efek samping implisit yang rumit (satu instruksi sub eax, ebx pada x86 menimpa enam flag status sekaligus: ZF, CF, SF, OF, PF, AF). Dekompilator pertama-tama mengangkat (Lifting) kode asli ke Representasi Menengah independen-arsitektur (P-code di Ghidra, Microcode di Hex-Rays), lalu mengubahnya ke Bentuk SSA (Static Single Assignment) di mana setiap variabel hanya diberi nilai tepat satu kali (dengan fungsi $\phi$ $\text{rax}_3 = \phi(\text{rax}_1, \text{rax}_2)$ pada titik pertemuan cabang):

• Penghapusan Flag Mati (Dead Flag Elimination): lebih dari $90\%$ perhitungan flag yang tidak pernah dibaca oleh lompatan bersyarat langsung dihapus lewat rantai Def-Use.
• Propagasi Ekspresi: definisi ZF_2 = (eax_2 == 0) disubstitusikan langsung ke dalam if (ZF_2) untuk membentuk if (eax_2 == 0).
• Pemisahan Rentang Hidup (Live-Range Splitting): jaring SSA terpisah yang kebetulan berbagi register fisik rax secara otomatis dipecah menjadi variabel lokal C yang independen (int v1; vs. Node *v2;)!

5. Tahap 3: Analisis Stack Frame dan Inferensi Tipe Berbasis Kekisi (Lattice)

Meskipun kode mesin tidak memiliki tipe eksplisit, semantik instruksi CPU memberikan batasan tipe aljabar (Type Constraints) yang ketat:

• Bertanda (int) vs. Tak Bertanda (unsigned int): cabang bersyarat jg / jl (Greater/Less), pembagian bertanda idiv, geser kanan aritmetika sar, dan perluasan tanda movsxd membuktikan bilangan bulat bertanda (int); sedangkan ja / jb (Above/Below), div, geser logika shr, dan perluasan nol movzx membuktikan bilangan bulat tak bertanda (unsigned int)!
• Rekonstruksi Pointer dan struct: dereferensi [rbx] menghasilkan batasan $\text{ptr}(\tau)$. Mengakses beberapa offset konstan ([rbx + 0], [rbx + 8], [rbx + 16]) mengungkap bahwa rbx adalah pointer ke struct S *.
• Kekisi Tipe (Type Lattice) dan Unifikasi: mengikuti Alan Mycroft (1999) dan sistem TIE (CMU), dekompilator menyusun semua tipe ke dalam kekisi terurut parsial $(\mathcal{L}, \sqsubseteq)$ antara $\top$ (vektor bit mentah) dan $\bot$ (konflik tipe / union), menyelesaikan pertidaksamaan subtipe secara global melalui batas bawah terbesar (Meet $\sqcap$).

  flowchart TD
    TOP["⊤ (Top: Vektor Bit Mentah N-bit bit64)"]
    NUM["num64 (Bilangan Bulat Skalar atau Pointer)"]
    FLT["float64 (Double IEEE 754: addsd, mulsd)"]
    SINT["int64_t (Signed: sar, idiv, jg, jl, movsxd)"]
    UINT["uint64_t (Unsigned: shr, div, ja, jb)"]
    PTR["ptr(τ) (Pointer: dereferensi [reg])"]
    STRUCT["struct S* (Pointer Struct: akses [reg + offset])"]
    BOT["⊥ (Bottom: Konflik Tipe → Cast atau Union)"]

    TOP --> NUM
    TOP --> FLT
    NUM --> SINT
    NUM --> UINT
    UINT --> PTR
    PTR --> STRUCT
    SINT --> BOT
    STRUCT --> BOT
    FLT --> BOT

6. Tahap 4: Penstrukturan Aliran Kontrol — Menghapus goto untuk Memulihkan if dan while

Untuk melipat graf aliran kontrol (CFG) menjadi pohon sintaks abstrak (AST) terstruktur (Cifuentes 1994), dekompilator menghitung Pohon Dominator dan Pohon Pasca-Dominator:

1. Deteksi Perulangan Alami: tepi balik (Back-Edge) $n \to h$ di mana $h$ mendominasi $n$ ($h \text{ dom } n$) mendefinisikan perulangan alami dengan kepala $h$ (while, for, atau do-while).
2. Deteksi Percabangan (if-then-else): pasca-dominator langsung dari simpul percabangan menandai titik temu eksak struktur berlian if-else.
3. Penstrukturan Bebas-goto (Algoritma DREAM): bahkan untuk CFG tak tereduksi akibat optimasi, algoritma DREAM (“No More Gotos”, Yakdan et al. 2015) menghitung Kondisi Ketercapaian (Reaching Conditions) boolean dan menerapkan minimisasi logika untuk menghasilkan kode C 100% bebas goto!

7. Batas Dekompilasi: Kamuflase Optimasi, Obfuskasi, dan Dekompilator Neural (LLM)

Sementara perangkat obfuskasi (OLLVM, VMProtect) menyerang analisis statis melalui Control-Flow Flattening (CFF), Opaque Predicates, Mixed Boolean-Arithmetic (MBA, $x+y \equiv (x\oplus y) + 2(x\land y)$), dan Virtualization Obfuscation (mengubah kode asli menjadi bytecode mesin virtual acak), dekade 2020-an menghadirkan Dekompilasi Neural berbasis LLM (LLM4Decompile) yang memadukan analisis program formal dengan kecerdasan buatan statistik untuk menebak kembali nama variabel yang bermakna dan menerjemahkan ulang kode teroptimasi menjadi bahasa C yang alami.