Bisakah teknik verifikasi program mencegah bug dari genre Heartbleed terjadi?

9

Mengenai masalah Heartbleed bug, Bruce Schneier menulis dalam Crypto-Gram-nya tanggal 15 April: 'Bencana "adalah kata yang tepat. Pada skala 1 hingga 10, ini adalah 11. ' Saya membaca beberapa tahun yang lalu bahwa kernel dari sistem operasi tertentu telah diverifikasi secara ketat dengan sistem verifikasi program modern. Maka dapatkah bug dari genre Heartbleed dapat dicegah terjadi melalui penerapan teknik verifikasi program hari ini atau apakah ini belum realistis atau bahkan pada dasarnya tidak mungkin?

cryptography correctness-proof security software-verification program-correctness Mok-Kong Shen
sumber
2
Berikut ini adalah analisis menarik dari pertanyaan ini oleh J. Regehr.
Martin Berger

Jawaban:

6

Untuk menjawab pertanyaan Anda dengan cara yang paling ringkas - ya, bug ini berpotensi tertangkap oleh alat verifikasi formal. Memang, properti "tidak pernah mengirim blok yang lebih besar dari ukuran detak jantung yang dikirim" cukup sederhana untuk diformalkan dalam sebagian besar bahasa spesifikasi (misalnya LTL).

Masalahnya (yang merupakan kritik umum terhadap metode formal) adalah bahwa spesifikasi yang Anda gunakan ditulis oleh manusia. Memang, metode formal hanya menggeser tantangan pencarian bug dari menemukan bug menjadi mendefinisikan apa bug itu. Ini adalah tugas yang sulit.

Juga, perangkat lunak verifikasi formal terkenal sulit karena masalah ledakan negara. Dalam hal ini, ini sangat relevan, karena berkali-kali untuk menghindari ledakan negara, kami mengabstraksi batasan. Sebagai contoh, ketika kita ingin mengatakan "setiap permintaan diikuti oleh hibah, dalam 100000 langkah", kita memerlukan formula yang sangat panjang, jadi kita abaikan dengan rumus "setiap permintaan akhirnya diikuti oleh hibah".

Dengan demikian, dalam kasus yang menyayat hati, bahkan ketika berusaha untuk memformalkan persyaratan, ikatan yang dipermasalahkan bisa saja disingkirkan, menghasilkan perilaku yang sama.

Singkatnya, kemungkinan bug ini bisa dihindari dengan menggunakan metode formal, tetapi harus ada manusia yang menentukan properti ini sebelumnya.

Shaull
sumber
5

Pemeriksa program komersial seperti Klocwork atau Coverity mungkin dapat menemukan Heartbleed karena ini merupakan hal yang relatif sederhana "lupa melakukan kesalahan pemeriksaan batas," yang merupakan salah satu masalah utama yang mereka rancang untuk diperiksa. Tetapi ada cara yang jauh lebih sederhana: gunakan tipe data abstrak buram yang diuji dengan baik agar bebas dari buffer overrun.

Ada sejumlah tipe data abstrak "string aman" yang tersedia untuk pemrograman C. Yang paling saya kenal adalah Vstr . Penulis, James Antill, memiliki diskusi besar tentang mengapa Anda perlu string tipe data abstrak dengan konstruktor sendiri metode-metode / pabrik dan juga daftar string tipe data abstrak lainnya untuk C .

Logika Pengembaraan
sumber
2
Cakupan tidak menemukan Heartbleed, lihat analisis ini oleh John Regehr.
Martin Berger
Tautan yang bagus! Ini menunjukkan moral yang sebenarnya dari cerita ini: verifikasi program tidak dapat menebus abstraksi yang dirancang dengan buruk (atau tidak ada).
Pengembaraan Logika
2
Tergantung apa yang Anda maksud dengan verifikasi program. Jika Anda maksud analisis statis, maka ya, itu selalu merupakan perkiraan, sebagai konsekuensi langsung dari teorema Rice. Jika Anda memverifikasi perilaku penuh dalam procer teorema interaktif, maka Anda mendapatkan jaminan bahwa program tersebut memenuhi spesifikasinya, tetapi itu sangat melelahkan. Dan Anda masih menghadapi masalah bahwa spesifikasi Anda mungkin salah (lihat misalnya ledakan Ariane 5).
Martin Berger
1
@ MartinBerger: Coverity menemukannya sekarang .
Pasang kembali Monica - M. Schröder
4

Jika Anda menghitung sebagai "  teknik verifikasi program  " kombinasi pengecekan runtime terikat dan fuzzing, ya bug khusus ini bisa saja tertangkap .

Fuzzing yang tepat akan menyebabkan yang sekarang terkenal memcpy(bp, pl, payload);membaca batas blok memori plmilik. Pada dasarnya pengecekan terikat dapat menangkap akses semacam itu, dan dalam praktiknya, dalam kasus khusus ini, bahkan versi debug mallocyang peduli untuk mengikat-periksa parameter memcpyakan melakukan pekerjaan (tidak perlu mengacaukan dengan MMU di sini) . Masalahnya, melakukan tes fuzzing pada setiap jenis paket jaringan membutuhkan upaya.

fgrieu
sumber
1
Sementara benar secara umum, IIRC, dalam kasus OpenSSL penulis menerapkan manajemen memori internal mereka sendiri sehingga jauh lebih kecil kemungkinannya untuk memcpymencapai batas sebenarnya dari wilayah (besar) yang semula diminta dari sistem malloc.
William Price
Ya, dalam hal OpenSSL seperti pada saat bug, memcpy(bp, pl, payload)harus memeriksa batas yang digunakan oleh mallocpenggantian OpenSSL , bukan sistem malloc. Itu mengesampingkan pengecekan terikat otomatis pada tingkat biner (setidaknya tanpa pengetahuan mendalam tentang mallocpenggantian itu). Harus ada kompilasi ulang dengan level-level wizardry menggunakan misalnya makro C yang mengganti token mallocatau apa pun pengganti yang digunakan OpenSSL; dan sepertinya kita perlu sama memcpykecuali dengan trik MMU yang sangat pintar.
fgrieu
4

Menggunakan bahasa yang lebih ketat tidak hanya memindahkan posting tujuan dari mendapatkan implementasi yang benar untuk mendapatkan spesifikasi yang benar. Sulit untuk membuat sesuatu yang sangat salah namun konsisten secara logis; itulah sebabnya kompiler menangkap begitu banyak bug.

Aritmatika Pointer seperti yang biasanya dirumuskan tidak sehat karena sistem jenis tidak benar-benar berarti apa yang seharusnya berarti. Anda dapat menghindari masalah ini sepenuhnya dengan bekerja dalam bahasa sampah yang dikumpulkan (pendekatan normal yang membuat Anda juga membayar abstraksi). Atau Anda bisa lebih spesifik tentang jenis petunjuk apa yang Anda gunakan, sehingga kompiler dapat menolak apa pun yang tidak konsisten atau tidak dapat dibuktikan benar seperti yang tertulis. Ini adalah pendekatan dari beberapa bahasa seperti Rust.

Tipe yang dibangun setara dengan bukti, jadi jika Anda menulis sistem tipe yang melupakan ini, maka semua hal salah. Asumsikan untuk sementara waktu bahwa ketika kita mendeklarasikan suatu tipe, sebenarnya kita maksudkan bahwa kita menyatakan kebenaran tentang apa yang ada dalam variabel.

  • int * x; // Pernyataan palsu. x ada dan tidak menunjuk ke int
  • int * y = z; // Hanya benar jika z terbukti menunjuk ke int
  • * (x + 3) = 5; // Hanya benar jika (x + 3) menunjuk ke int dalam array yang sama dengan x
  • int c = a / b; // Hanya benar jika b bukan nol, seperti: "bukan nol int b = ...;"
  • nullable int * z = NULL; // nullable int * tidak sama dengan int *
  • int d = * z; // Pernyataan salah, karena z dapat dibatalkan
  • if (z! = NULL) {int * e = z; } // Oke karena z bukan nol
  • gratis (y); int w = * y; // Pernyataan salah, karena kamu tidak lagi ada di w

Di dunia ini, pointer tidak boleh nol. Dereferensi NullPointer tidak ada, dan pointer tidak harus diperiksa untuk nullness di mana saja. Sebagai gantinya, "nullable int *" adalah tipe yang berbeda yang dapat nilainya diekstraksi menjadi null atau ke sebuah pointer. Ini berarti bahwa pada titik di mana asumsi non-nol dimulai Anda masuk log pengecualian Anda atau turun cabang nol.

Di dunia ini, kesalahan susunan di luar batas juga tidak ada. Jika kompiler tidak dapat membuktikan bahwa ia dalam batas, maka cobalah untuk menulis ulang sehingga kompiler dapat membuktikannya. Jika tidak bisa, maka Anda harus memasukkan Assumption secara manual di tempat itu; kompiler dapat menemukan kontradiksi di kemudian hari.

Juga, jika Anda tidak dapat memiliki pointer yang tidak diinisialisasi, maka Anda tidak akan memiliki pointer ke memori yang tidak diinisialisasi. Jika Anda memiliki pointer ke memori yang dibebaskan, maka itu harus ditolak oleh kompiler. Di Rust, ada berbagai jenis penunjuk untuk membuat jenis bukti ini masuk akal untuk diharapkan. Ada pointer yang dimiliki secara eksklusif (yaitu: tidak ada alias), pointer ke struktur yang sangat abadi. Jenis penyimpanan default tidak dapat diubah, dll.

Ada juga masalah menegakkan tata bahasa yang sebenarnya didefinisikan dengan baik pada protokol (yang mencakup anggota antarmuka), untuk membatasi area permukaan input untuk persis apa yang diantisipasi. Hal tentang "kebenaran" adalah: 1) Singkirkan semua kondisi yang tidak ditentukan 2) Pastikan konsistensi logis . Kesulitan untuk sampai ke sana banyak berhubungan dengan penggunaan alat yang sangat buruk (dari sudut pandang kebenaran).

Inilah sebabnya mengapa dua praktik terburuk adalah variabel global dan goto. Hal-hal ini mencegah menempatkan kondisi pra / post / invarian di sekitar apa pun. Itu juga sebabnya tipe sangat efektif. Ketika tipe semakin kuat (akhirnya menggunakan Tipe Dependen untuk memperhitungkan nilai aktual), mereka mendekati sebagai bukti kebenaran konstruktif dalam diri mereka sendiri; membuat program yang tidak konsisten gagal dikompilasi.

Perlu diingat bahwa ini bukan hanya tentang kesalahan bodoh. Ini juga tentang mempertahankan basis kode dari penyusup yang pintar. Akan ada kasus di mana Anda harus menolak kiriman tanpa bukti properti penting yang dihasilkan mesin seperti "ikuti protokol yang ditentukan secara formal".

rampok
sumber
1

verifikasi perangkat lunak otomatis / formal berguna dan dapat membantu dalam beberapa kasus, tetapi seperti yang telah ditunjukkan oleh orang lain, ini bukan peluru perak. orang dapat menunjukkan bahwa OpenSSL rentan dalam hal open source dan belum digunakan secara komersial dan industri, digunakan secara luas, dan tidak perlu ditinjau secara mendalam sebelum rilis (orang bertanya-tanya apakah ada pengembang berbayar pada proyek tersebut). cacat ditemukan pada dasarnya melalui tinjauan kode pasca-rilis, dan kode itu tampaknya ditinjau pra-rilis (perhatikan meskipun mungkin tidak ada cara untuk melacak siapa yang melakukan tinjauan kode internal). "momen yang dapat diajar" dengan heartbleed (di antara banyak lainnya) pada dasarnya adalah tinjauan kode yang lebih baik sebelum rilis kode yang sangat sensitif, mungkin lebih baik dilacak. mungkin OpenSSL sekarang akan lebih banyak diteliti.

lebih banyak bkg dari media yang merinci asalnya:

vzn
sumber