Keamanan memori berbasis tipe tanpa pengelolaan memori manual atau pengumpulan sampah runtime?

Katakanlah kita menginginkan bahasa pemrograman fungsional yang murni, seperti Haskell atau Idris, yang ditujukan untuk pemrograman sistem tanpa pengumpulan sampah dan tidak memiliki runtime (atau setidaknya tidak lebih dari "runtimes" C dan Rust). Sesuatu yang bisa berjalan, lebih atau kurang, pada bare metal.

Apa sajakah pilihan untuk keamanan memori statis yang tidak memerlukan manajemen memori manual atau pengumpulan sampah runtime, dan bagaimana mungkin masalahnya diselesaikan dengan menggunakan sistem tipe fungsional murni mirip dengan Haskell atau Idris?

Secara kasar, ada dua strategi utama untuk manajemen memori manual yang aman.

1. Pendekatan pertama adalah menggunakan beberapa logika substruktural seperti logika linier untuk mengontrol penggunaan sumber daya. Ide ini telah melayang pada dasarnya sejak awal logika linear, dan pada dasarnya bekerja pada pengamatan bahwa dengan melarang aturan kontraksi struktural, setiap variabel digunakan paling banyak sekali, sehingga tidak ada alias. Akibatnya, perbedaan antara pembaruan di tempat dan alokasi ulang tidak terlihat oleh program, sehingga Anda dapat menerapkan bahasa Anda dengan manajemen memori manual.

   Inilah yang dilakukan Rust (menggunakan sistem tipe affine). Jika Anda tertarik pada teori bahasa bergaya Rust, salah satu makalah terbaik untuk dibaca adalah L3: A Linear Language dengan Lokasi Ahmed . Sebagai tambahan, kalkulus LFPL Damiano Mazza disebutkan juga linier, memiliki bahasa lengkap yang berasal darinya dalam bahasa RAML .

   Jika Anda tertarik pada verifikasi gaya Idris, Anda harus melihat bahasa ATS Xi et al , yang merupakan bahasa gaya Rust / L3 dengan dukungan untuk verifikasi berdasarkan tipe indeks gaya Haskell, hanya membuat bukti-tidak relevan dan linier untuk memberikan lebih banyak kontrol atas kinerja.

   Pendekatan dependen yang lebih agresif adalah bahasa F-star yang dikembangkan di Microsoft Research, yang merupakan teori tipe dependen penuh. Bahasa ini memiliki antarmuka monadik dengan kondisi pra dan pasca dalam semangat Teori Tipe Hoare Nanevski et al (atau bahkan Jenis Linear dan Ketergantungan Saya sendiri ), dan memiliki subset yang ditentukan yang dapat dikompilasi dengan kode C tingkat rendah - pada kenyataannya, mereka telah mengirimkan kode kripto yang diverifikasi sebagai bagian dari Firefox!

   Untuk lebih jelasnya, baik F-star maupun HTT bukanlah bahasa yang diketik secara linear, tetapi bahasa indeks untuk monad mereka biasanya didasarkan pada logika pemisahan Reynold dan O'Hearn , yang merupakan logika substruktural terkait dengan logika linier yang telah melihat kesuksesan besar sebagai bahasa pernyataan untuk logika Hoare untuk program pointer.

2. Pendekatan kedua adalah hanya menentukan perakitan apa (atau IR tingkat rendah apa pun yang Anda inginkan) lakukan, dan kemudian menggunakan beberapa bentuk linear atau logika pemisahan untuk alasan tentang perilakunya dalam asisten bukti secara langsung. Pada dasarnya, Anda dapat menggunakan asisten bukti atau bahasa yang diketik secara dependen sebagai assembler makro yang sangat mewah yang hanya menghasilkan program yang benar.

   Jensen et al. Logika pemisahan tingkat tinggi untuk kode tingkat rendah adalah contoh yang sangat murni dari ini - ia membangun logika pemisahan untuk perakitan x86! Namun, ada banyak proyek dalam nada ini, seperti Perangkat Lunak Toolchain Terverifikasi di Princeton dan proyek CertiKOS di Yale.

Semua pendekatan ini akan "terasa" seperti sedikit seperti Rust, karena melacak kepemilikan dengan membatasi penggunaan variabel adalah kunci untuk semuanya.

Tipe linear dan logika pemisahan sama-sama hebat, tetapi dapat membutuhkan sedikit upaya programmer. Menulis daftar tertaut yang aman di Rust bisa sangat sulit, misalnya.

Tetapi ada alternatif yang membutuhkan upaya programmer jauh lebih sedikit, meskipun dengan jaminan kurang ketat. Aliran kerja (yang cukup lama) adalah untuk menjamin keamanan memori dengan menggunakan (biasanya setumpuk) wilayah. Menggunakan inferensi wilayah, kompilator dapat secara statis memutuskan bagian mana dari data yang dialokasikan harus masuk ke, dan membatalkan alokasi wilayah ketika keluar dari ruang lingkup.

Inferensi wilayah terbukti aman (tidak dapat membatalkan alokasi memori yang dapat dicapai) dan memerlukan campur tangan programmer minimal, tetapi ini bukan "total" (artinya masih dapat bocor memori, meskipun jelas jauh lebih baik daripada "tidak melakukan apa-apa"), jadi biasanya digabungkan dengan GC dalam praktiknya. ItuMLtonKompiler ML Kit menggunakan wilayah untuk menghilangkan sebagian besar panggilan GC, tetapi masih memiliki GC karena masih akan membocorkan memori. Menurut beberapa perintis awal di daerah, inferensi wilayah sebenarnya tidak diciptakan untuk tujuan ini (itu untuk paralelisasi otomatis, saya pikir); tapi ternyata itu bisa digunakan untuk manajemen memori juga.

Untuk titik awal, saya akan mengatakan pergi untuk kertas "Implementasi Nilai-Panggilan Diketik λ-kalkulus menggunakan tumpukan Wilayah" oleh Mads Tofte dan Jean-Pierre Talpin. Untuk lebih banyak makalah tentang inferensi wilayah, lihat makalah lain oleh M. Tofte dan J.-P. Talpin, beberapa karya Pierre Jouvelot, serta Greg Morrisett, Mike Hicks, dan serangkaian makalah Dan Grossman di Cyclone.

Skema sepele untuk sistem "bare metal" adalah dengan tidak mengizinkan semua alokasi memori runtime. Ingat, bahkan malloc/freepasangan C membutuhkan pustaka runtime. Tetapi bahkan ketika semua objek didefinisikan pada waktu kompilasi, mereka dapat didefinisikan dengan cara yang aman.

Masalah utama di sini adalah fiksi nilai-nilai abadi dalam bahasa fungsional murni, yang dibuat saat program berjalan. Perangkat keras nyata (dan tentu saja sistem logam telanjang) bergantung pada RAM yang bisa berubah, yang pasokannya terbatas. Runtime dari implementasi bahasa fungsional dalam praktiknya secara dinamis mengalokasikan RAM ketika nilai-nilai "tidak berubah" baru dibuat, dan sampah mengumpulkannya ketika nilai "tidak berubah" tidak lagi diperlukan.

Dan untuk masalah yang paling menarik, masa hidup setidaknya beberapa nilai tergantung pada input runtime (pengguna), sehingga masa pakai tidak dapat ditentukan secara statis. Tetapi bahkan jika seumur hidup tidak bergantung pada input, itu bisa sangat tidak sepele. Ikuti program sederhana ini berulang kali untuk menemukan bilangan prima hanya dengan memeriksa setiap angka secara berurutan, memeriksa semua bilangan prima hingga sqrt(N). Jelas kebutuhan ini menjaga bilangan prima dan dapat mendaur ulang memori yang digunakan untuk non-bilangan prima.