Tak Ada Bit yang Tertinggal: Memakai Brute-Force Lifting untuk Mencapai Rekompilasi Biner yang Sepenuhnya Statis

Rekompilasi biner adalah teknik untuk beroperasi langsung pada kode eksekutabel, menjanjikan otomatisasi penambalan mitigasi keamanan pada biner warisan dan migrasi biner antar instruction set architecture (ISA). Namun, belum ada sistem yang sepenuhnya otomatis yang dapat secara andal mengangkat biner eksekutabel arbitrer ke representasi antara kompilator (IR) seperti LLVM IR, atau menerjemahkan biner non-trivial dari satu ISA ke ISA lain secara sepenuhnya statis dan andal. Masalah intinya adalah memulihkan control flow graph (CFG) suatu program secara statis tidak mungkin dilakukan secara umum: cabang terkomputasi dapat melompat ke target yang tidak dapat ditentukan tanpa benar-benar menjalankan program. Sistem yang ada mengandalkan mekanisme fallback runtime, sehingga sebagian besar mesin penerjemahan biner harus menyertai program yang diterjemahkan di mesin target. Artikel ini menyajikan sistem binary lifting seluruh program yang sepenuhnya statis dan tidak memerlukan dukungan penerjemahan runtime di target. Alih-alih berupaya membedakan kode dari data, penulis memperlakukan setiap offset byte sebagai calon target cabang dan mengangkat seluruh biner secara brute-force, membangun superset CFG yang secara konservatif memuat semua alur kendali yang layak. Cabang terkomputasi yang tak dapat diselesaikan secara statis dengan demikian direduksi menjadi pencarian dalam tabel dispatch yang menunjuk ke jalur alur kendali hasil terjemahan yang bersesuaian.

Pendekatan yang diusulkan adalah sistem binary lifting sepenuhnya statis yang menghindari dukungan penerjemahan runtime. Wawasan kuncinya adalah memperlakukan setiap offset byte dalam biner sebagai calon target cabang, alih-alih berupaya membedakan kode dari data. Brute-force lifting ini membangun superset control flow graph (CFG) yang secara konservatif memuat semua alur kendali yang layak. Untuk cabang terkomputasi yang tak dapat diselesaikan secara statis, sistem mereduksinya menjadi pencarian dalam tabel dispatch yang menunjuk ke jalur alur kendali hasil terjemahan yang bersesuaian. Penulis mengimplementasikan prototipe rekompilator biner dari biner x86-64 ke LLVM IR, tanpa memerlukan heuristik kode/data. Proses lifting dapat diformalkan sebagai berikut: untuk biner $B$ dengan offset byte $O=\{0,1,\dots ,|B|-1\}$, superset CFG $G=(V,E)$ dibangun dengan $V\subseteq O$ merepresentasikan alamat awal instruksi potensial, dan $E$ merepresentasikan sisi alur kendali yang mungkin. Setiap offset byte $o\in O$ dianggap sebagai calon target cabang, dan fungsi lifting

menerjemahkan byte mulai dari $o$ menjadi instruksi LLVM IR. Tabel dispatch memetakan setiap offset ke blok kode hasil terjemahan yang bersesuaian. Arsitektur keseluruhannya diilustrasikan dalam diagram Mermaid berikut: