Mengapa porting over integer overflow bukanlah ide yang baik

Artikel ini berfokus pada perilaku yang tidak ditentukan dan optimisasi kompiler, terutama dalam konteks overflow bilangan bulat yang ditandatangani.

Catatan dari penerjemah: dalam bahasa Rusia tidak ada korespondensi yang jelas dalam konteks yang digunakan dari kata "wrap" / "wrapping". Ada istilah matematis " transfer ", yang dekat dengan fenomena yang dijelaskan, dan istilah "carry flag" adalah mekanisme untuk mengatur flag pada prosesor selama integer overflow. Pilihan terjemahan lain mungkin ungkapan “rotasi / flip / revolusi sekitar nol”. Lebih baik mencerminkan arti "bungkus" dibandingkan dengan "membawa", karena menunjukkan transisi angka ketika meluap dari kisaran positif ke negatif. Namun, ternyata, kata-kata ini terlihat tidak biasa dalam teks untuk pembaca tes. Untuk kesederhanaan, di masa depan kita akan menggunakan kata "transfer" sebagai terjemahan dari istilah "wrap".

Penyusun bahasa C (dan C ++) dalam pekerjaan mereka semakin dipandu oleh konsep perilaku tidak terbatas - gagasan bahwa perilaku suatu program untuk beberapa operasi tidak diatur oleh standar dan bahwa, ketika membuat kode objek, kompiler memiliki hak untuk melanjutkan dari asumsi bahwa program tidak melakukan operasi tersebut. Banyak programmer menentang pendekatan ini, karena kode yang dihasilkan dalam kasus ini mungkin tidak berperilaku seperti yang dimaksudkan oleh pembuat program. Masalah ini menjadi lebih akut, karena kompiler menggunakan metode optimasi yang lebih canggih, yang mungkin akan didasarkan pada konsep perilaku tidak terbatas.

Dalam konteks ini, contoh dengan overflow integer yang ditandatangani adalah indikatif. Sebagian besar pengembang C menulis kode untuk mesin yang menggunakan kode tambahan untuk mewakili bilangan bulat, dan penambahan dan pengurangan dalam representasi ini diimplementasikan dengan cara yang persis sama, dalam aritmatika yang tidak ditandatangani. Jika jumlah dua bilangan bulat positif dengan tanda meluap - yaitu, menjadi lebih besar dari jenis yang ditampung - prosesor akan mengembalikan nilai yang, diinterpretasikan sebagai pelengkap biner dari nomor yang ditandatangani, akan dianggap negatif. Fenomena ini disebut "transfer", karena hasilnya, mencapai batas atas kisaran nilai, "ditransfer" dan dimulai dari batas bawah.

Untuk alasan ini, Anda terkadang dapat melihat kode ini di C:

int b = a + 1000; if (b < a) { //  puts("input too large!"); return; } 

Tugas pernyataan if adalah untuk mendeteksi kondisi overflow (dalam hal ini, itu terjadi setelah menambahkan 1000 ke nilai variabel a ) dan melaporkan kesalahan. Masalahnya adalah bahwa dalam C, ditandatangani integer overflow adalah salah satu kasus perilaku tidak terdefinisi. Untuk beberapa waktu, kompiler selalu menganggap kondisi seperti itu salah: jika Anda menambahkan 1000 (atau angka positif lainnya) ke nomor lain, hasilnya tidak boleh kurang dari nilai awal. Jika overflow terjadi, maka ada perilaku yang tidak terdefinisi, dan tidak membiarkan ini sudah (tampaknya) menjadi perhatian programmer. Oleh karena itu, kompilator dapat memutuskan bahwa operator kondisional dapat sepenuhnya dihapus untuk tujuan optimasi (setelah semua, kondisi selalu salah, tidak mempengaruhi apa pun, sehingga Anda dapat melakukannya tanpa itu).

Masalahnya adalah bahwa dengan optimasi ini, kompiler menghapus cek yang ditambahkan programmer secara khusus untuk mendeteksi perilaku yang tidak terdefinisi dan memprosesnya. Di sini Anda dapat melihat bagaimana ini terjadi dalam praktik. (Catatan: godbolt.org, situs tempat contoh berada, sangat keren! Anda dapat mengedit kode dan segera melihat bagaimana berbagai kompiler memprosesnya, dan ada banyak dari mereka. Eksperimen!). Harap dicatat bahwa kompiler tidak menghapus pemeriksaan untuk overflow jika Anda mengubah tipe menjadi unsigned, karena perilaku overflow unsigned di C didefinisikan (lebih tepatnya, hasilnya ditransfer dengan aritmatika yang tidak ditandatangani, sehingga overflow tidak benar-benar terjadi).

Apakah ini salah? Seseorang berkata ya, meskipun jelas bahwa banyak pengembang kompiler menganggap keputusan ini sah. Jika saya mengerti dengan benar, argumen utama para pendukung (edit: tergantung implementasi) dari transfer selama overflow adalah sebagai berikut:

• Meluap adalah perilaku yang bermanfaat.
• Migrasi adalah perilaku yang diharapkan oleh programmer.
• Semantik perilaku luapan tidak terbatas tidak memberikan keuntungan yang nyata.
• Standar bahasa C untuk perilaku yang tidak terdefinisi memungkinkan implementasi untuk "sepenuhnya mengabaikan situasi, dan hasilnya akan tidak dapat diprediksi," tetapi ini tidak memberikan kompiler hak untuk mengoptimalkan kode berdasarkan pada asumsi bahwa situasi dengan perilaku yang tidak terdefinisi tidak terjadi sama sekali.

Mari kita menganalisis setiap item secara bergantian:

Migrasi Melimpah - Perilaku Berguna?

Migrasi berguna terutama ketika Anda perlu melacak overflow yang sudah terjadi. (Jika ada masalah lain yang dapat diselesaikan dengan transfer dan tidak dapat diselesaikan dengan menggunakan variabel integer yang tidak ditandatangani, saya tidak dapat segera mengingat contoh-contoh tersebut, dan saya menduga ada beberapa dari mereka). Sementara transfer benar-benar menyederhanakan masalah menggunakan variabel yang meluap secara tidak benar, itu jelas bukan obat mujarab (ingat perkalian atau penambahan dua kuantitas yang tidak diketahui dengan tanda yang tidak diketahui).

Dalam kasus sepele, ketika transfer hanya memungkinkan Anda untuk melacak luapan yang muncul, juga tidak sulit untuk mengetahui sebelumnya apakah itu akan terjadi. Contoh kami dapat ditulis ulang sebagai berikut:

 if (a > INT_MAX - 1000) { //    puts("input too large!"); return; } int b = a + 1000; 

Artinya, alih-alih menghitung penjumlahan dan kemudian mencari tahu apakah terjadi overflow atau tidak, memeriksa hasilnya untuk konsistensi matematis, Anda dapat memeriksa apakah penjumlahan tersebut melebihi jumlah maksimum yang cocok dengan tipe tersebut. (Jika tanda kedua operan tidak diketahui, verifikasi harus sangat rumit, tetapi hal yang sama berlaku untuk verifikasi selama transfer).

Mengingat semua ini, saya menemukan argumen yang tidak meyakinkan bahwa pemindahan berguna dalam kebanyakan kasus.

Apakah migrasi seperti yang diharapkan oleh programer?

Lebih sulit untuk berdebat dengan argumen ini, karena jelas bahwa kode setidaknya beberapa programmer C mengasumsikan semantik transfer dengan overflow integer yang ditandatangani. Tetapi fakta ini saja tidak cukup untuk mempertimbangkan semantik seperti itu lebih disukai (perhatikan bahwa beberapa kompiler memungkinkan Anda untuk mengaktifkannya jika perlu).

Solusi yang jelas untuk masalah (pemrogram mengharapkan perilaku ini) adalah membuat kompiler memberikan peringatan ketika mengoptimalkan kode, dengan asumsi tidak ada perilaku yang tidak ditentukan. Sayangnya, seperti yang kita lihat pada contoh di godbolt.org menggunakan tautan di atas, kompiler tidak selalu melakukan ini (Gcc versi 7.3 - ya, tetapi versi 8.1 - tidak, jadi ada langkah mundur).

Apakah semantik perilaku luapan tidak terbatas tidak memberikan keuntungan nyata?

Jika komentar ini benar dalam semua kasus, maka itu akan berfungsi sebagai argumen yang kuat dalam mendukung fakta bahwa penyusun harus mematuhi semantik transfer secara default, karena mungkin akan lebih baik untuk memungkinkan pemeriksaan overflow, bahkan jika mekanisme ini tidak benar dari sudut pandang teknis - meskipun akan karena dapat digunakan dalam kode yang berpotensi rusak.

Saya berasumsi bahwa optimasi ini (penghapusan pemeriksaan kondisi kontradiktif matematis) dalam program C biasa sering dapat diabaikan, karena penulisnya berusaha untuk kinerja terbaik dan masih mengoptimalkan kode secara manual: yaitu, jika jelas bahwa pernyataan if ini berisi suatu kondisi , yang tidak akan pernah benar, programmer cenderung menghapusnya sendiri. Bahkan, saya menemukan bahwa dalam beberapa penelitian efektivitas optimasi seperti itu dipertanyakan, diuji dan ternyata praktis tidak signifikan dalam kerangka uji kontrol. Namun, meskipun optimasi ini hampir tidak pernah memberikan keuntungan dalam bahasa C, generator kode dan optimisasi kompiler sebagian besar bersifat universal dan dapat digunakan dalam bahasa lain - dan bagi mereka kesimpulan ini mungkin salah. Mari kita ambil bahasa C ++ dengan tradisi misalkan mengandalkan optimizer untuk menghapus konstruksi yang berlebihan dalam kode templat, daripada melakukannya secara manual. Tetapi ada bahasa yang dikonversi oleh transporter ke C, dan kode yang berlebihan di dalamnya juga dioptimalkan oleh kompiler C.

Selain itu, bahkan jika Anda terus memeriksa luapan, itu sama sekali bukan fakta bahwa biaya langsung untuk mentransfer variabel integer akan menjadi minimal bahkan pada mesin yang menggunakan kode tambahan. Arsitektur Mips, misalnya, hanya dapat melakukan operasi aritmatika dalam register dengan ukuran tetap (32 bit). Tipe short int , pada umumnya, memiliki ukuran 16 bit, dan char - 8 bit; ketika variabel salah satu dari jenis ini disimpan dalam register, ukurannya akan membesar, dan untuk mentransfernya dengan benar, perlu untuk melakukan setidaknya satu operasi tambahan dan, mungkin, menggunakan register tambahan (untuk mengakomodasi bitmask yang sesuai). Saya harus mengakui bahwa saya tidak berurusan dengan kode untuk Mips untuk waktu yang lama, jadi saya tidak yakin tentang biaya pasti dari operasi ini, tetapi saya yakin itu bukan nol dan bahwa masalah yang sama dapat terjadi pada arsitektur RISC lainnya.

Apakah standar bahasa melarang penghindaran transfer variabel jika itu dimaksudkan oleh arsitektur?

Jika Anda melihat, argumen ini sangat lemah. Esensinya adalah bahwa standar yang seharusnya memungkinkan implementasi (kompiler) untuk menafsirkan "perilaku tidak terbatas" hanya sampai batas tertentu. Dalam teks standar itu sendiri - dalam fragmen yang menjadi tujuan advokasi pemindahan banding - berikut ini dikatakan (ini adalah bagian dari definisi istilah "perilaku tidak terbatas"):

CATATAN: Perilaku tidak terdefinisi dapat berupa mengabaikan situasi sepenuhnya, sementara hasilnya tidak dapat diprediksi, ...

Idenya adalah bahwa kata-kata "benar-benar mengabaikan situasi" tidak menyarankan bahwa suatu peristiwa yang mengarah ke perilaku yang tidak terdefinisi - misalnya, meluap selama penambahan - tidak dapat terjadi, tetapi jika itu terjadi, kompiler harus terus bekerja seolah-olah dalam daripada tidak pernah terjadi, tetapi juga memperhitungkan hasil yang akan berubah jika dia mengirimkan prosesor permintaan untuk melakukan operasi seperti itu (dengan kata lain, seolah-olah kode sumber diterjemahkan ke dalam kode mesin dengan cara yang mudah dan naif).

Pertama-tama, harus dicatat bahwa teks ini diberikan sebagai "catatan", dan karena itu tidak normatif (yaitu, ia tidak dapat meresepkan sesuatu), menurut arahan ISO yang disebutkan dalam pengantar standar:

Sesuai dengan Bagian 3 dari Arahan ISO / IEC, kata pengantar ini, pengantar untuk teks, catatan, catatan kaki dan contoh-contoh juga untuk tujuan informasi saja.

Karena perikop “perilaku tidak terbatas” ini adalah catatan, maka perikop ini tidak menentukan apa pun. Harap perhatikan bahwa definisi "perilaku tidak terbatas" saat ini adalah:

perilaku yang timbul dari penggunaan desain perangkat lunak yang tidak dapat ditoleransi atau tidak benar atau data yang salah, di mana Standar Internasional ini tidak memaksakan persyaratan apa pun .

Saya menyoroti ide utama: tidak ada persyaratan yang dikenakan pada perilaku tidak terbatas; daftar "kemungkinan jenis perilaku tidak terdefinisi" dalam catatan hanya berisi contoh dan tidak bisa menjadi resep akhir. Ungkapan "tidak menuntut" tidak bisa ditafsirkan sebaliknya.

Beberapa orang, yang mengembangkan argumen ini, berpendapat bahwa, terlepas dari teksnya, komite bahasa, ketika merumuskan kata-kata ini, berarti bahwa perilaku secara keseluruhan harus sesuai dengan arsitektur perangkat keras tempat program berjalan, sebisa mungkin, menyiratkan terjemahan yang naif ke dalam kode mesin. Ini mungkin benar, walaupun saya belum melihat bukti (misalnya, dokumen sejarah) yang mendukung argumen ini. Namun, meskipun demikian, bukan fakta bahwa pernyataan ini berlaku untuk versi teks saat ini.

Pikiran terakhir

Argumen yang mendukung transfer sebagian besar tidak dapat dipertahankan. Mungkin argumen terkuat diperoleh jika kita mengkombinasikannya: programmer yang kurang berpengalaman (yang tidak tahu seluk-beluk bahasa C dan perilaku tidak terbatas di dalamnya) kadang-kadang mengharapkan transfer, dan itu tidak mengurangi kinerja - meskipun yang terakhir tidak benar dalam semua kasus, dan bagian pertama tidak meyakinkan dalam semua kasus, dan bagian pertama tidak meyakinkan. jika Anda mempertimbangkannya secara terpisah.

Secara pribadi, saya lebih suka bahwa overflow diblokir (trapping) daripada membungkus. Yaitu, sehingga program macet, dan tidak terus bekerja - dengan perilaku tidak pasti atau hasil yang berpotensi salah, karena dalam kedua kasus muncul kerentanan. Solusi seperti itu, tentu saja, akan sedikit mengurangi kinerja pada sebagian besar (?) Arsitektur, terutama pada x86, tetapi, di sisi lain, kesalahan overflow akan segera diidentifikasi dan mereka tidak akan dapat mengambil keuntungan dari atau mendapatkan hasil yang salah dengan menggunakannya sepanjang jalan. program. Selain itu, secara teori, kompiler dengan pendekatan ini dapat dengan aman menghapus pengecekan overflow yang berlebihan, karena itu pasti tidak akan terjadi, meskipun, seperti yang saya lihat, baik Dentang maupun GCC tidak menggunakan kesempatan ini.

Untungnya, baik interupsi maupun porting diimplementasikan dalam kompiler yang paling sering saya gunakan adalah GCC. Untuk beralih di antara mode, argumen baris perintah -ftrapv dan -fwrapv digunakan, masing-masing.

Tentu saja, ada banyak tindakan yang mengarah pada perilaku yang tidak terdefinisi - integer overflow hanya salah satunya. Saya sama sekali tidak berpikir bahwa adalah berguna untuk menafsirkan semua kasus ini sebagai perilaku yang tidak terbatas, dan saya yakin ada banyak situasi khusus di mana semantik harus ditentukan oleh bahasa atau, setidaknya, diserahkan pada kebijaksanaan implementasi. Dan saya takut interpretasi yang terlalu bebas dari konsep ini oleh produsen kompiler: jika perilaku kompiler tidak memenuhi ide intuitif pengembang, terutama mereka yang secara pribadi membaca teks standar, ini dapat menyebabkan kesalahan nyata; jika perolehan kinerja dalam hal ini dapat diabaikan, lebih baik untuk mengabaikan interpretasi tersebut. Dalam salah satu posting berikut, saya mungkin akan melihat beberapa masalah ini.

Suplemen (tanggal 24 Agustus 2018)

Saya menyadari bahwa banyak di atas dapat ditulis lebih baik. Di bawah ini saya meringkas dan menjelaskan kata-kata saya secara singkat dan menambahkan beberapa komentar kecil:

• Saya tidak berpendapat bahwa perilaku tidak terbatas lebih disukai untuk membawa overflow - melainkan, dalam praktiknya, transfer tidak jauh lebih baik daripada perilaku tidak terbatas. Secara khusus, masalah keamanan dapat diperoleh dalam kasus pertama, dan dalam kasus kedua - dan saya bertaruh bahwa banyak kerentanan yang disebabkan oleh luapan yang tidak terperangkap dalam waktu (kecuali untuk mereka yang bertanggung jawab untuk menghapus cek yang salah oleh kompiler) sebenarnya berasal dari - karena transfer hasil, tetapi bukan karena perilaku yang tidak terdefinisi terkait dengan overflow.
• Satu-satunya keuntungan nyata dari transfer adalah bahwa pemeriksaan overflow tidak dihapus. Meskipun dengan cara ini Anda dapat melindungi kode dari beberapa skenario serangan, masih ada kemungkinan sebagian dari luapan tidak akan diperiksa sama sekali (mis. Programmer akan lupa menambahkan cek semacam itu) dan tidak akan diperhatikan.
• Jika masalah keamanan tidak begitu penting, dan kecepatan tinggi program muncul, perilaku yang tidak terdefinisi akan memberikan optimisasi yang lebih menguntungkan dan peningkatan produktivitas yang lebih besar, setidaknya dalam beberapa kasus. Di sisi lain, jika keamanan diutamakan, porting penuh dengan kerentanan.
• Ini berarti bahwa jika Anda memilih antara gangguan, transferensi, dan perilaku tidak terdefinisi, ada beberapa tugas di mana transferensi dapat bermanfaat.
• Adapun pemeriksaan untuk luapan yang telah terjadi, saya percaya bahwa meninggalkan mereka berbahaya, karena itu menciptakan kesan yang salah bahwa mereka bekerja dan akan selalu bekerja. Mengganggu luapan menghindari masalah ini; peringatan yang memadai - kurangi itu.
• Saya pikir setiap pengembang yang menulis kode keamanan-kritis idealnya memiliki perintah yang baik dari semantik bahasa di mana ia menulis, serta menyadari jebakannya. Untuk C, ini berarti Anda perlu mengetahui semantik dari overflow dan seluk-beluk perilaku yang tidak terdefinisi. Sangat menyedihkan bahwa beberapa programmer belum tumbuh ke level ini.
• Saya telah menemukan klaim bahwa "sebagian besar programmer C mengharapkan migrasi sebagai perilaku default," tetapi saya tidak tahu bukti untuk ini. (Dalam artikel itu, saya menulis "beberapa programmer," karena saya tahu beberapa contoh dari kehidupan nyata, dan secara umum saya ragu bahwa ada orang yang akan berdebat dengan ini).
• Ada dua masalah berbeda: apa yang dituntut oleh standar bahasa C dan apa yang harus diterapkan oleh kompiler. Saya (umumnya) menyukai cara standar mendefinisikan perilaku overflow yang tidak terdefinisi. Dalam posting ini, saya berbicara tentang apa yang harus dilakukan oleh kompiler.
• Ketika overflow terganggu, tidak perlu memeriksa setiap operasi untuk itu. Idealnya, program dengan pendekatan ini berperilaku konsisten dalam hal aturan matematika, atau berhenti bekerja. Dalam hal ini, keberadaan "luapan sementara" menjadi mungkin, yang tidak mengarah pada tampilan hasil yang salah. Kemudian baik ekspresi a + b - b dan ekspresi (a * b) / b dapat dioptimalkan ke (yang pertama juga dimungkinkan selama transfer, tetapi yang terakhir tidak lagi ada).

Catatan Terjemahan artikel ini diterbitkan di blog dengan izin dari penulis. Teks asli: Davin McCall " Wrap on integer overflow bukan ide yang baik ".

Tautan terkait tambahan dari tim PVS-Studio:

1. Andrey Karpov. Perilaku yang tidak terdefinisi lebih dekat dari yang Anda pikirkan .
2. Will Dietz, Peng Li, John Regehr, dan Vikram Adve. Memahami Overflow Integer di C / C ++ .
3. V1026. Variabel bertambah dalam loop. Perilaku yang tidak terdefinisi akan terjadi jika bilangan bulat ditandatangani .
4. Stackoverflow Apakah integer overflow yang ditandatangani masih merupakan perilaku yang tidak terdefinisi dalam C ++?