Model Fil-C yang Disederhanakan

 (corsix.org)
2 poin oleh GN⁺ 10 jam lalu | 1 komentar | Bagikan ke WhatsApp
  • Struktur yang melacak pointer C/C++ bersama metadata AllocationRecord yang dilampirkan, lalu melakukan pemeriksaan batas memori saat dereferensi
  • Cara kerja yang memindahkan nilai pointer asli beserta metadata yang sesuai, atau mengubahnya menjadi pemanggilan khusus Fil-C, mencakup penugasan pointer, aritmetika, pengiriman argumen fungsi, nilai balik, hingga pemanggilan malloc·free
  • Metadata pointer di dalam memori heap disimpan terpisah di invisible_bytes; saat load·store pointer, nilai dan metadata dibaca serta ditulis bersama, dan pemeriksaan alignment juga diterapkan
  • filc_free hanya membebaskan visible_bytes dan invisible_bytes sambil mempertahankan AllocationRecord itu sendiri; pembersihan setelahnya ditangani garbage collector, dan variabel lokal yang alamatnya mungkin escape akan mengalami promosi ke heap
  • Meski kompleksitas implementasi nyata seperti thread, function pointer, dan optimasi memori·kinerja masih tersisa, pendekatan ini tetap dapat dimanfaatkan untuk verifikasi keamanan memori pada kode C/C++ skala besar atau sebagai contoh sistem konkret untuk pointer provenance

Model Fil-C yang Disederhanakan

  • Fil-C menggunakan struktur yang melacak metadata AllocationRecord* bersama pointer untuk menangani kode C/C++ secara aman terhadap memori
    • Implementasi nyatanya menggunakan penulisan ulang LLVM IR, tetapi model sederhananya berbentuk transformasi otomatis atas kode sumber C/C++
    • Untuk setiap variabel lokal bertipe pointer di tiap fungsi, ditambahkan variabel lokal AllocationRecord* yang bersesuaian
    • Sebagai contoh, untuk T1* p1 ditambahkan AllocationRecord* p1ar = NULL
  • Penugasan dan perhitungan sederhana pada variabel lokal pointer dilakukan dengan memindahkan AllocationRecord* bersama nilai pointer aslinya
    • p1 = p2 diubah menjadi p1 = p2, p1ar = p2ar
    • p1 = p2 + 10 juga disertai p1ar = p2ar
    • Cast dari integer ke pointer mengatur metadata menjadi NULL
    • Cast dari pointer ke integer dipertahankan apa adanya
  • Pada pengiriman argumen fungsi dan nilai balik, AllocationRecord* juga ikut diteruskan bersama pointer, dan pemanggilan pustaka standar tertentu diganti dengan fungsi khusus Fil-C
    • Pemanggilan malloc dan free masing-masing diubah menjadi bentuk filc_malloc, filc_free
    • Sebagai contoh, p1 = malloc(x); free(p1); menjadi {p1, p1ar} = filc_malloc(x); filc_free(p1, p1ar);
  • filc_malloc tidak hanya mengalokasikan satu blok memori yang diminta, tetapi melakukan tiga alokasi
    • Alokasi objek AllocationRecord
    • Alokasi visible_bytes untuk data aktual
    • Alokasi invisible_bytes dengan calloc untuk menyimpan metadata tak terlihat
    • AllocationRecord berisi field visible_bytes, invisible_bytes, dan length

Dereferensi dan Pemeriksaan Batas

  • Saat pointer didereferensi, dilakukan pemeriksaan batas menggunakan AllocationRecord* yang menyertainya
    • Memastikan metadata pointer bukan NULL
    • Menghitung selisih antara posisi pointer saat ini dan alamat awal visible_bytes
    • Memastikan offset lebih kecil dari total panjang
    • Memastikan panjang tersisa cukup untuk ukuran target dereferensi
  • Baik pembacaan maupun penulisan menerapkan prosedur pemeriksaan yang sama
    • Pemeriksaan dilakukan sebelum x = *p1
    • Pemeriksaan dengan bentuk yang sama juga dilakukan sebelum *p2 = x
  • Dengan struktur ini, akses pointer yang melampaui rentang alokasi yang dituju dapat diblokir

Pointer di Dalam Heap dan invisible_bytes

  • Pointer yang disimpan di memori heap tidak bisa dikelola compiler sebagai variabel terpisah seperti variabel lokal, sehingga digunakan invisible_bytes
    • Jika ada pointer di posisi visible_bytes + i, maka AllocationRecord* yang sesuai disimpan di posisi invisible_bytes + i
    • Dengan kata lain, invisible_bytes berfungsi seperti array dengan tipe elemen AllocationRecord*
  • Saat membaca atau menulis nilai pointer dari/ke memori, selain pemeriksaan batas biasa juga ditambahkan pemeriksaan alignment
    • Memastikan offset i adalah kelipatan dari sizeof(AllocationRecord*)
    • Hanya jika syarat ini terpenuhi invisible_bytes dapat diakses dengan aman seperti array AllocationRecord**
  • Saat load pointer, metadata juga dimuat bersama pointer data
    • p2 = *p1 diikuti dengan penambahan p2ar = *(AllocationRecord**)(p1ar->invisible_bytes + i) setelah p2 = *p1
  • Saat store pointer, bukan hanya nilai pointer yang disimpan tetapi juga metadata yang bersesuaian
    • *p1 = p2 akan menjalankan *(AllocationRecord**)(p1ar->invisible_bytes + i) = p2ar setelah penyimpanan data aktual

filc_free dan Garbage Collector

  • filc_free membebaskan dua blok memori hanya ketika pointer bukan NULL, setelah melakukan pemeriksaan kecocokan dengan AllocationRecord
    • Memastikan par != NULL
    • Memastikan p == par->visible_bytes
    • Membebaskan visible_bytes dan invisible_bytes
    • Lalu mengubah visible_bytes, invisible_bytes menjadi NULL dan length menjadi 0
  • Walau filc_malloc melakukan tiga alokasi, filc_free tidak membebaskan objek AllocationRecord itu sendiri
    • Perbedaan ini ditangani oleh garbage collector
  • Untuk model sederhana, GC stop-the-world sudah memadai, sementara Fil-C nyata menggunakan kolektor paralel, konkuren, dan inkremental
    • GC melakukan pelacakan dengan mengikuti objek AllocationRecord
    • AllocationRecord yang tak lagi dapat dijangkau diproses sebagai target pembebasan
  • GC juga melakukan dua tugas tambahan
    • Saat membebaskan AllocationRecord yang tak lagi dapat dijangkau, GC memanggil filc_free
    • Semua pointer yang mengarah ke AllocationRecord dengan length 0 diubah menjadi satu AllocationRecord normal tunggal dengan panjang 0
  • Dengan perilaku ini, tidak memanggil free pun tidak otomatis berujung pada kebocoran memori
    • GC akan melakukan pembebasan secara otomatis
    • Namun pemanggilan free tetap memungkinkan memori dibebaskan lebih awal daripada GC
  • Setelah free, AllocationRecord terkait pada akhirnya akan menjadi tak terjangkau dan bisa dibersihkan kemudian

Escape Alamat Variabel Lokal dan Promosi ke Heap

  • Dengan adanya GC, cakupan penanganan aman terhadap alamat variabel lokal menjadi lebih luas
    • Jika alamat variabel lokal diambil, dan compiler tidak bisa membuktikan bahwa alamat itu tidak escape keluar dari masa hidup variabel, maka variabel tersebut dipromosikan menjadi alokasi heap
  • Variabel lokal seperti ini dialokasikan melalui malloc, bukan di stack
    • Tidak perlu menyisipkan free yang terpisah
    • GC yang akan menangani pengumpulannya

Versi memmove ala Fil-C

  • memmove di pustaka standar C menangani memori arbitrer, sehingga compiler menghadapi masalah karena tidak dapat mengetahui apakah di dalamnya ada pointer
  • Untuk mengatasi ini digunakan heuristik
    • Pointer di dalam memori arbitrer harus sepenuhnya berada di dalam rentang memori tersebut
    • Pointer harus ter-align dengan benar
  • Karena aturan ini, bahkan pemindahan 8 byte yang sama pun dapat menghasilkan perilaku berbeda
    • Jika 8 byte yang ter-align dipindahkan sekaligus dengan memmove, bagian invisible_bytes yang sesuai juga ikut dipindahkan
    • Jika memmove dilakukan 8 kali masing-masing 1 byte, invisible_bytes tidak ikut dipindahkan

Kompleksitas Tambahan dalam Implementasi Nyata

  • Thread

    • Konkruensi adalah faktor yang meningkatkan kompleksitas GC
    • filc_free tidak dapat langsung membebaskan memori
      • Karena bisa terjadi race condition antara thread yang sedang membebaskan memori dan thread lain yang mengakses memori yang sama
    • Operasi atomik pada pointer juga memerlukan penanganan tambahan
      • Karena penulisan ulang dasar mengubah load/store pointer menjadi dua kali load/store, sehingga merusak atomisitas

  • Function pointer

    • Metadata tambahan pada AllocationRecord menandai apakah visible_bytes bukan data biasa melainkan pointer ke kode yang dapat dieksekusi
    • Pemanggilan melalui function pointer p1 memeriksa p1 == p1ar->visible_bytes dan juga memeriksa apakah p1ar memang merepresentasikan function pointer
    • Untuk mencegah serangan type confusion pada function pointer, verifikasi type signature juga diperlukan pada ABI pemanggilan
    • Salah satu caranya adalah membuat semua fungsi memiliki type signature yang sama
      • Semua argumen diperlakukan seolah-olah dimasukkan ke dalam struct dan diteruskan lewat memori
      • Di batas ABI, setiap fungsi menerima hanya satu AllocationRecord tunggal yang sesuai dengan struct tersebut

  • Optimasi penggunaan memori

    • Dapat dipertimbangkan agar filc_malloc tidak langsung mengalokasikan invisible_bytes, tetapi menundanya sampai benar-benar diperlukan
    • Dapat juga dipertimbangkan menempatkan AllocationRecord dan visible_bytes bersama dalam satu alokasi
    • Jika malloc dasar menempelkan metadata di bagian depan setiap alokasi, metadata itu juga bisa dimasukkan ke dalam AllocationRecord

  • Optimasi kinerja

    • Keamanan memori Fil-C datang dengan biaya performa
    • Masih ada ruang untuk menerapkan berbagai teknik guna merebut kembali sebagian performa yang hilang

Kapan Fil-C Digunakan

  • Fil-C dapat digunakan ketika kode C/C++ skala besar tampak berjalan, tetapi verifikasi keamanan memorinya tidak ada, dan demi keamanan memori pengguna bersedia menerima penggunaan GC serta penurunan performa yang besar
    • Disebut sebagai kemungkinan langkah sementara sebelum menulis ulang ke Java, Go, atau Rust
  • Fil-C juga bisa dijalankan untuk tujuan pendeteksian bug memori seperti ASan
    • Kode C/C++ dapat dijalankan di bawah Fil-C untuk memeriksa bug memori
  • Pada bahasa yang bahasa saat compile time dan runtime-nya sama, serta memiliki keamanan compile time yang kuat, Fil-C bisa dipakai untuk evaluasi compile time yang aman
    • Zig disebut sebagai contoh
    • Meski evaluasi runtime tidak aman, evaluasi compile time dapat menggunakan konfigurasi ala Fil-C
  • Fil-C juga bermakna sebagai contoh sistem konkret yang menangani pointer provenance
    • Diajukan pertanyaan tentang kemungkinan optimasi mengubah if (p1 == p2) { f(p1); } menjadi if (p1 == p2) { f(p2); } saat tipe p1 dan p2 sama
    • Di Fil-C, karena AllocationRecord* yang diteruskan ke f bisa berbeda, jawabannya dinyatakan jelas: tidak bisa
    • Dalam hal ini, Fil-C berperan sebagai contoh sistem konkret yang memiliki pointer provenance

Bacaan terkait

1 komentar

 
GN⁺ 10 jam lalu
Opini Hacker News
  • Mencoba memasang invisicaps ke sesuatu seperti chibicc atau slimcc tampaknya akan jadi eksperimen yang cukup menarik
    Ada juga ruang untuk menguji reference counting atau varian dari invisible capability system, dan mungkin bisa menghemat memori dengan imbalan sedikit biaya indirect reference
  • Saya membuat filc-bazel-template dan membungkusnya sebagai Bazel target
    Semoga ini membantu orang yang ingin membuat hermetic builds dengan menggunakan keduanya bersama-sama
  • Saya tidak begitu paham maksud kalimat ini
    Upon freeing an unreachable AllocationRecord, call filc_free on it.
    Menurut saya, maksudnya adalah sebelum membebaskan AR yang tidak dapat dijangkau, bebaskan dulu memori yang ditunjuk oleh field visible_bytes dan invisible_bytes
  • Menurut saya, Fil-C adalah salah satu proyek yang paling diremehkan yang pernah saya lihat sejauh ini
    Dibanding mengatakan “rewrite it in Rust” demi keamanan, gagasan bahwa program C yang sudah ada bisa dikompilasi menjadi sepenuhnya memory-safe terasa jauh lebih menarik
    • Menurut saya ada beberapa hal yang harus dilihat bersama
      Pertama, Fil-C itu lebih lambat dan lebih besar. Kalau itu tidak masalah, orang mungkin sudah memilih Java atau C# lebih dulu daripada Rust dalam 10 tahun terakhir
      Kedua, ini tetap berarti menulis C. Untuk memelihara kode lama itu masuk akal, tetapi kalau banyak menulis kode baru, saya merasa Rust jauh lebih nyaman
      Ketiga, Fil-C adalah keamanan runtime, sedangkan Rust bisa mengekspresikan sebagian hal di compile time. Lebih jauh lagi, bahasa seperti WUFFS berusaha membuktikan keamanan di tahap kompilasi tanpa runtime check, jadi meskipun kodenya masih bisa salah secara logis, arahnya adalah mencegah crash atau arbitrary code execution
    • Saya tidak melihat ini sebagai sesuatu yang diremehkan. Sudah ada cukup banyak diskusi terkait
      Ada thread seperti Fil-Qt: A Qt Base build with Fil-C experience, Linux Sandboxes and Fil-C, Ported freetype, fontconfig, harfbuzz, and graphite to Fil-C, A Note on Fil-C, Notes by djb on using Fil-C, Fil-C: A memory-safe C implementation, dan Fil's Unbelievable Garbage Collector
    • Keterbatasan utama Fil-C menurut saya adalah bahwa ini runtime memory safety
      Anda masih bisa menulis kode yang tidak memory-safe, hanya saja sekarang hasilnya lebih cenderung menjadi crash yang pasti daripada kerentanan
      Jika Anda membuat sesuatu seperti web API yang menerima input tak tepercaya, masalah seperti ini pada akhirnya bisa berujung pada denial-of-service, jadi memang lebih baik, tetapi sulit dibilang sudah cukup baik
      Saya tidak bermaksud meremehkan pekerjaan Fil-C, hanya saja pendekatan runtime memang punya batasan yang jelas
    • Terima kasih atas ketertarikannya
      Namun, agar adil, Fil-C cukup jauh lebih lambat daripada Rust, dan juga memakai lebih banyak memori
      Di sisi lain, Fil-C mendukung safe dynamic linking, dan dalam beberapa hal bisa dibilang lebih ketat soal keamanan daripada Rust
      Pada akhirnya ini trade-off, jadi menurut saya tinggal pilih sesuai kebutuhan masing-masing
    • Menurut saya, jarang ada programmer C/C++ yang matanya langsung berbinar ketika diberi tahu bahwa mereka bisa menambahkan garbage collector ke program mereka
      Jadi meskipun ide ini menarik secara teknis, secara emosional tampaknya tidak mudah diterima
  • Menurut saya, Fil-C tidak memory-safe dalam situasi data race
    Nilai capability dan pointer bisa terkoyak saat assignment, sehingga bila interleaving thread sedang buruk, objek bisa diakses dengan pointer yang salah dan memicu arbitrary misbehavior
    Keterbatasan seperti ini sendiri masih bisa diterima, tetapi saya menyayangkan suasana ketika orang yang menunjukkan masalah ini justru diserang keras bahkan oleh para pendukungnya
    • Setahu saya, bagian itu ditangani dengan atomic ops
      Sayangnya, itu juga salah satu penyebab besar overhead-nya
  • Menurut saya ini pada akhirnya hanyalah variasi lain dari teknik keluarga fat pointers
    Pendekatan seperti ini sudah berkali-kali diimplementasikan lalu ditinggalkan karena jaminan keamanannya tidak cukup, sulit melewati non-fat ABI boundaries, atau overhead-nya besar
    • Namun sekarang ada lagi kecenderungan fat pointers didukung langsung oleh hardware, jadi mungkin belum tentu ini ditolak terlalu dini
      Lagi pula, menurut saya filc juga tidak bisa dijelaskan hanya sebagai fat pointer biasa
    • Saya juga rasa perlu melihat bahwa hardware memory tagging sudah tersedia di berbagai platform