Perilaku dan kebenaran yang tidak terdefinisi tidak didefinisikan

Istilah "perilaku tidak terbatas" dalam bahasa C dan C ++ menunjukkan situasi di mana secara harfiah "apa yang tidak terjadi". Secara historis, kasus-kasus di mana kompiler C sebelumnya (dan arsitektur di atasnya) berperilaku dengan cara yang tidak sesuai dikaitkan dengan perilaku yang tidak terbatas, dan komite untuk mengembangkan standar, dalam kebijaksanaan tanpa batasnya, memutuskan untuk tidak memutuskan apa pun tentang hal ini (mis., Untuk tidak memberikan preferensi beberapa salah satu implementasi yang bersaing). Perilaku tidak terbatas juga disebut situasi yang mungkin di mana standar, biasanya sangat lengkap, tidak meresepkan perilaku tertentu. Istilah ini memiliki makna ketiga, yang pada zaman kita menjadi semakin relevan: perilaku yang tidak terbatas - ini adalah peluang untuk optimasi. Dan pengembang di C dan C ++ menyukai optimasi; mereka secara mendesak membutuhkan kompiler untuk melakukan segala upaya untuk mempercepat kode.

Artikel ini pertama kali diterbitkan di situs web Layanan Kriptografi. Terjemahan diterbitkan dengan izin dari penulis Thomas Pornin.

Ini adalah contoh klasik:

void foo(double *src, int *dst) { int i; for (i = 0; i < 4; i ++) { dst[i] = (int)src[i]; } } 

Kami akan mengkompilasi kode GCC ini pada platform x86 64-bit untuk Linux (saya bekerja pada versi terbaru Ubuntu 18.04, versi GCC - 7.3.0). Kami mengaktifkan optimisasi penuh, dan kemudian melihat daftar assembler, yang kami gunakan tombol "-Wall -O9 -S " (argumen " -O9 " menetapkan tingkat optimalisasi GCC maksimum, yang dalam praktiknya setara dengan " -O3 ", meskipun dalam beberapa fork GCC ditentukan dan level lebih tinggi). Kami mendapatkan hasil sebagai berikut:

  .file "zap.c" .text .p2align 4,,15 .globl foo .type foo, @function foo: .LFB0: .cfi_startproc movupd (%rdi), %xmm0 movupd 16(%rdi), %xmm1 cvttpd2dq %xmm0, %xmm0 cvttpd2dq %xmm1, %xmm1 punpcklqdq %xmm1, %xmm0 movups %xmm0, (%rsi) ret .cfi_endproc .LFE0: .size foo, .-foo .ident "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0" .section .note.GNU-stack,"",@progbits 

Masing-masing dari dua instruksi movupd pertama memindahkan dua nilai ganda ke register SSE2 128-bit ( ganda memiliki ukuran 64 bit, sehingga register SSE2 dapat menyimpan dua nilai ganda ). Dengan kata lain, empat nilai awal dibaca pertama, dan hanya kemudian mereka dilemparkan ke int (operasi cvttpd2dq ). Operasi punpcklqdq memindahkan empat bilangan bulat 32-bit yang diterima menjadi satu register SSE2 (% xmm0 ), yang isinya kemudian dituliskan ke RAM ( movups ). Dan sekarang yang utama: program C kami secara resmi mengharuskan akses ke memori terjadi dalam urutan berikut:

• Baca nilai ganda pertama dari src [0] .
• Tulis nilai pertama dari tipe int ke dst [0] .
• Baca nilai ganda kedua dari src [1] .
• Tulis nilai kedua dari tipe int ke dst [1] .
• Baca nilai ganda ketiga dari src [2] .
• Tulis nilai ketiga dari tipe int ke dst [2] .
• Baca nilai ganda keempat dari src [3] .
• Tulis nilai keempat dari tipe int ke dst [3] .

Namun, semua persyaratan ini hanya masuk akal dalam konteks mesin abstrak, yang didefinisikan oleh standar C; prosedur pada mesin sungguhan dapat bervariasi. Kompiler bebas untuk mengatur ulang atau memodifikasi operasi, asalkan hasilnya tidak bertentangan dengan semantik mesin abstrak (aturan yang disebut as-jika adalah "seolah-olah"). Dalam contoh kami, urutan tindakan hanya berbeda:

• Baca nilai ganda pertama dari src [0] .
• Baca nilai ganda kedua dari src [1] .
• Baca nilai ganda ketiga dari src [2] .
• Baca nilai ganda keempat dari src [3] .
• Tulis nilai pertama dari tipe int ke dst [0] .
• Tulis nilai kedua dari tipe int ke dst [1] .
• Tulis nilai ketiga dari tipe int ke dst [2] .
• Tulis nilai keempat dari tipe int ke dst [3] .

Ini adalah bahasa C: semua isi memori pada akhirnya adalah byte (yaitu, slot dengan nilai tipe unsigned char , tetapi dalam praktiknya, grup delapan bit), dan operasi penunjuk sewenang-wenang diizinkan. Secara khusus, src dan pointer dst dapat digunakan untuk mengakses bagian memori yang tumpang tindih ketika dipanggil (situasi ini disebut "aliasing"). Dengan demikian, urutan baca dan tulis mungkin penting jika byte ditulis dan kemudian dibaca lagi. Agar perilaku aktual program sesuai dengan abstrak yang didefinisikan oleh standar C, kompiler harus bergantian antara operasi baca dan tulis, memberikan siklus penuh memori yang diakses pada setiap iterasi. Kode yang dihasilkan akan lebih besar dan bekerja lebih lambat. Untuk pengembang C, ini akan menjadi kesedihan.

Di sini, untungnya, perilaku tak terbatas datang untuk menyelamatkan. Standar C menyatakan bahwa nilai tidak dapat diakses melalui pointer yang tipenya tidak sesuai dengan tipe saat ini dari nilai-nilai ini. Sederhananya, jika nilainya ditulis ke dst [0] , di mana dst adalah pointer int , maka byte yang sesuai tidak dapat dibaca melalui src [1] , di mana src adalah pointer ganda , karena dalam kasus ini kami akan mencoba mengakses nilai, yang sekarang bertipe int , menggunakan pointer dari tipe yang tidak kompatibel. Dalam hal ini, perilaku yang tidak terdefinisi akan terjadi. Ini dinyatakan dalam paragraf 7 bagian 6.5 standar ISO 9899: 1999 ("C99") (dalam edisi baru 9899: 2018, atau "C17", kata-katanya tidak berubah). Persyaratan ini disebut aturan aliasing yang ketat. Akibatnya, kompiler C diizinkan untuk bertindak dengan asumsi bahwa operasi akses memori yang mengarah ke perilaku tidak terdefinisi karena pelanggaran aturan aliasing yang ketat tidak terjadi. Dengan demikian, kompiler dapat mengatur ulang operasi baca dan tulis dalam urutan apa pun, karena mereka tidak boleh mengakses bagian memori yang tumpang tindih. Inilah yang dimaksud dengan optimasi kode.

Arti dari perilaku tidak terdefinisi, singkatnya, adalah ini: kompilator dapat mengasumsikan bahwa tidak akan ada perilaku tidak terdefinisi, dan menghasilkan kode berdasarkan asumsi ini. Dalam kasus aturan aliasing yang ketat - asalkan aliasing terjadi, perilaku tidak terbatas memungkinkan untuk optimasi penting yang jika tidak akan sulit untuk diterapkan. Secara umum, setiap instruksi dalam prosedur pembuatan kode yang digunakan oleh kompiler memiliki dependensi yang membatasi algoritma perencanaan operasi: sebuah instruksi tidak dapat dijalankan sebelum instruksi yang bergantung padanya, atau setelah instruksi yang bergantung padanya. Dalam contoh kami, perilaku tidak terdefinisi menghilangkan ketergantungan antara operasi tulis pada dst [] dan operasi baca "berikutnya" dari src [] : ketergantungan seperti itu hanya dapat ada dalam kasus ketika perilaku tidak terdefinisi terjadi ketika mengakses memori. Demikian pula, konsep perilaku terdefinisi memungkinkan kompiler untuk menghapus kode yang tidak dapat dieksekusi tanpa memasukkan keadaan perilaku tidak terdefinisi.

Semua ini, tentu saja, adalah baik, tetapi perilaku seperti itu kadang-kadang dianggap sebagai pengkhianatan berbahaya oleh kompiler. Anda sering dapat mendengar frasa: "Kompilator menggunakan konsep perilaku tidak terbatas sebagai alasan untuk memecahkan kode saya." Misalkan seseorang menulis sebuah program yang menambahkan bilangan bulat dan ketakutan meluap - ingat kasus Bitcoin . Dia dapat berpikir seperti ini: untuk merepresentasikan bilangan bulat, prosesor menggunakan kode tambahan, yang berarti jika overflow terjadi, itu akan terjadi karena hasilnya akan dipotong ke ukuran tipe, mis. 32 bit Ini berarti bahwa hasil luapan dapat diprediksi dan diperiksa dengan suatu pengujian.

Pengembang bersyarat kami akan menulis ini:

 #include <stdio.h> #include <stdlib.h> int add(int x, int y, int *z) { int r = x + y; if (x > 0 && y > 0 && r < x) { return 0; } if (x < 0 && y < 0 && r > x) { return 0; } *z = r; return 1; } int main(int argc, char *argv[]) { int x, y, z; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); if (add(x, y, &z)) { printf("%d\n", z); } else { printf("overflow!\n"); } return 0; } 

Sekarang mari kita coba kompilasi kode ini menggunakan GCC:

 $ gcc -W -Wall -O9 testadd.c $ ./a.out 17 42 59 $ ./a.out 2000000000 1500000000 overflow! 

Ok, sepertinya berhasil. Sekarang coba kompiler lain, misalnya, Dentang (saya punya versi 6.0.0):

 $ clang -W -Wall -O3 testadd.c $ ./a.out 17 42 59 $ ./a.out 2000000000 1500000000 -794967296 

Apa?

Ternyata ketika operasi dengan tipe integer yang ditandatangani mengarah ke hasil yang tidak dapat diwakili oleh tipe target, kami memasuki wilayah perilaku yang tidak ditentukan. Tetapi kompiler dapat berasumsi bahwa itu tidak terjadi. Secara khusus, mengoptimalkan ekspresi x> 0 && y> 0 && r <x , kompilator menyimpulkan bahwa karena nilai-nilai x dan y benar - benar positif, pemeriksaan ketiga tidak mungkin benar (jumlah dua nilai tidak boleh kurang dari salah satu dari mereka), dan Anda dapat melewati seluruh operasi ini. Dengan kata lain, karena meluap adalah perilaku yang tidak terdefinisi, itu "tidak dapat terjadi" dari sudut pandang kompiler, dan semua instruksi yang bergantung pada keadaan ini dapat dihapus. Mekanisme untuk mendeteksi perilaku tidak terdefinisi telah hilang begitu saja.

Standar tidak pernah menetapkan asumsi bahwa "semantik yang ditandatangani" (yang sebenarnya digunakan dalam operasi prosesor) digunakan dalam perhitungan dengan tipe yang ditandatangani; ini terjadi bukan karena tradisi - bahkan pada masa itu ketika kompiler tidak cukup pintar untuk mengoptimalkan kode, dengan fokus pada sejumlah nilai. Anda dapat memaksa Dentang dan GCC untuk menerapkan semantik pembungkus untuk tipe yang ditandatangani menggunakan flag -fwrapv (di Microsoft Visual C, Anda dapat menggunakan -d2UndefIntOverflow-, seperti dijelaskan di sini ). Namun, pendekatan ini tidak dapat diandalkan, bendera mungkin hilang ketika kode ditransfer ke proyek lain atau ke arsitektur lain.

Hanya sedikit orang yang tahu bahwa overflow tipe karakter melibatkan perilaku yang tidak terdefinisi. Ini dinyatakan dalam paragraf 5 bagian 6.5 dari standar C99 dan C17:

Jika pengecualian terjadi ketika mengevaluasi ekspresi (mis., Jika hasilnya tidak didefinisikan secara matematis atau di luar kisaran nilai valid dari jenis yang diberikan), perilaku tersebut tidak terdefinisi.

Namun untuk tipe yang tidak ditandatangani, semantik modular dijamin. Paragraf 9 bagian 6.2.5 mengatakan yang berikut:

Overflow tidak pernah terjadi dalam perhitungan dengan operan yang tidak ditandatangani, karena hasil yang tidak dapat diwakili oleh tipe integer yang tidak ditandatangani yang dihasilkan modulo bilangan yang satu lebih dari nilai maksimum yang diwakili oleh jenis yang dihasilkan.

Contoh lain dari perilaku tidak terdefinisi dalam operasi dengan tipe yang ditandatangani adalah operasi divisi. Seperti semua orang tahu, hasil pembagian dengan nol tidak ditentukan secara matematis, oleh karena itu, menurut standar, operasi ini memerlukan perilaku yang tidak terdefinisi. Jika pembagi nol dalam operasi idiv pada prosesor x86, pengecualian prosesor dilemparkan. Seperti permintaan interupsi, pengecualian prosesor ditangani oleh sistem operasi. Pada sistem mirip Unix, seperti Linux, pengecualian prosesor yang dipicu oleh operasi idiv diterjemahkan ke dalam sinyal SIGFPE , yang dikirim ke proses, dan diakhiri dengan pengendali default (jangan heran bahwa "FPE" adalah singkatan dari "pengecualian titik mengambang" (pengecualian dalam operasi floating point), sementara idiv bekerja dengan bilangan bulat). Tetapi ada situasi lain yang mengarah pada perilaku yang tidak terdefinisi. Pertimbangkan kode berikut:

 #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int x, y; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); printf("%d\n", x / y); return 0; }  : $ gcc -W -Wall -O testdiv.c $ ./a.out 42 17 2 $ ./a.out -2147483648 -1 zsh: floating point exception (core dumped) ./a.out -2147483648 -1 

Dan kebenarannya adalah: pada mesin ini (x86 yang sama untuk Linux), tipe int mewakili kisaran nilai dari -2,147.483.648 hingga +2.147.448.647. Jika Anda membagi -2.147.448.648 dengan -1, Anda harus mendapatkan +2.147.483.648 Tetapi angka ini tidak berada dalam kisaran nilai int . Karena itu, perilaku tidak didefinisikan. Apa pun bisa terjadi. Dalam hal ini, proses dihentikan secara paksa. Pada sistem lain, terutama dengan prosesor kecil yang tidak memiliki operasi divisi, hasilnya dapat bervariasi. Dalam arsitektur seperti itu, divisi dilakukan secara terprogram - dengan bantuan prosedur yang biasanya disediakan oleh kompiler, dan sekarang dapat melakukan apa pun yang diinginkan dengan perilaku yang tidak terbatas, karena memang itulah yang sebenarnya.

Saya perhatikan bahwa SIGFPE dapat diperoleh dalam kondisi yang sama dan dengan bantuan operator modulo ( % ). Dan pada kenyataannya: di bawahnya terletak operasi idiv yang sama, yang menghitung hasil bagi dan sisanya, sehingga pengecualian prosesor yang sama dipicu. Menariknya, standar C99 mengatakan bahwa ekspresi INT_MIN% -1 tidak dapat mengarah pada perilaku yang tidak terdefinisi, karena hasilnya didefinisikan secara matematis (nol) dan dengan jelas memasuki kisaran nilai dari tipe target. Dalam versi C17, teks paragraf 6 bagian 6.5.5 telah diubah, dan sekarang kasus ini juga diperhitungkan, yang membawa standar lebih dekat ke situasi nyata pada platform perangkat keras umum.

Ada banyak situasi tidak jelas yang juga mengarah pada perilaku yang tidak terdefinisi. Lihatlah kode ini:

 #include <stdio.h> #include <stdlib.h> unsigned short mul(unsigned short x, unsigned short y) { return x * y; } int main(int argc, char *argv[]) { int x, y; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); printf("%d\n", mul(x, y)); return 0; } 

Apakah Anda berpikir bahwa suatu program, mengikuti standar C, harus mencetak jika kita meneruskan faktor 45.000 dan 50.000 ke fungsi?

• 18.048
• 2.250.000.000
• Tuhan selamatkan Ratu!

Jawaban yang benar ... ya, semua yang di atas! Anda mungkin berpendapat seperti ini: karena short unsigned adalah tipe unsigned, itu seharusnya mendukung semantik pembungkus modulo 65 536, karena pada prosesor x86 ukuran jenis ini, sebagai aturan, adalah tepat 16 bit (standar juga memungkinkan ukuran yang lebih besar, tetapi dalam prakteknya, ini masih tipe 16-bit). Karena secara matematis produk adalah 2.250.000.000, maka akan dipotong modulo 65.536, yang memberikan jawaban 18.048. Namun, berpikir dengan cara ini, kita lupa tentang perluasan tipe integer. Menurut standar C (bagian 6.3.1.1, paragraf 2), jika operan adalah tipe yang ukurannya benar-benar lebih kecil dari ukuran int , dan nilai-nilai tipe ini dapat diwakili oleh tipe int tanpa kehilangan bit (dan kami hanya memiliki case ini: pada x86 saya di bawah Linux memiliki ukuran int 32 bit, dan ia dapat secara eksplisit menyimpan nilai dari 0 hingga 65.535), kemudian kedua operan dilemparkan ke int dan operasi sudah dilakukan pada nilai yang dikonversi. Yaitu: produk dihitung sebagai nilai dari tipe int, dan hanya setelah kembali dari fungsi itu dikembalikan ke unsigned short (yaitu, pada saat inilah pemotongan modulo 65 536 terjadi). Masalahnya adalah bahwa secara matematis hasil sebelum transformasi terbalik adalah 2,250 juta, dan nilai ini melebihi kisaran int , yang merupakan tipe yang ditandatangani. Akibatnya, kita mendapatkan perilaku yang tidak terdefinisi. Setelah itu, apa pun bisa terjadi, termasuk serangan patriotisme Inggris yang tiba-tiba.

Namun, dalam praktiknya, dengan kompiler biasa, hasilnya adalah 18.048, karena masih belum ada optimasi yang dapat mengambil keuntungan dari perilaku tidak terbatas dalam program khusus ini (orang dapat membayangkan lebih banyak skenario buatan di mana ia benar-benar akan menyebabkan masalah).

Akhirnya, contoh lain, sekarang di C ++:

 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <array> int main(int argc, char *argv[]) { std::array<char, 16> tmp; int i; if (argc < 2) { return EXIT_FAILURE; } memset(tmp.data(), 0, 16); if (strlen(argv[1]) < 16) { strcpy(tmp.data(), argv[1]); } for (i = 0; i < 17; i ++) { printf(" %02x", tmp[i]); } printf("\n"); } 

Ini bukan tipikal “bad awful strcpy () !” Bagi Anda. Memang, di sini fungsi strcpy () dijalankan hanya jika ukuran string sumber, termasuk terminal nol, cukup kecil. Selain itu, elemen-elemen array secara eksplisit diinisialisasi ke nol, sehingga semua byte dalam array memiliki nilai yang diberikan, terlepas dari apakah string besar atau kecil dilewatkan ke fungsi. Pada saat yang sama, loop pada akhirnya salah: ia membaca satu byte lebih dari yang seharusnya.

Jalankan kode:

 $ g++ -W -Wall -O9 testvec.c $ ./a.out foo 66 6f 6f 00 00 00 00 00 00 00 00 00 00 00 00 00 10 58 ffffffca ff ffffac ffffffc0 55 00 00 00 ffffff80 71 34 ffffff99 07 ffffffba ff ffffea ffffffd0 ffffffe5 44 ffffff83 fffffffd 7f 00 00 00 00 00 00 00 00 00 00 10 58 ffffffca ffffffac ffffffc0 55 00 00 ffffff97 7b 12 1b ffffffa1 7f 00 00 02 00 00 00 00 00 00 00 ffffffd8 ffffffe5 44 ffffff83 fffffffd 7f 00 00 00 ffffff80 00 00 02 00 00 00 60 56 (...) 62 64 3d 30 30 zsh: segmentation fault (core dumped) ./a.out foo ++? 

Anda dapat secara naif menolak: well, ia membaca byte tambahan di luar batas array; tetapi ini tidak begitu menakutkan, karena pada stack byte ini masih ada, ia dipetakan ke memori, jadi satu-satunya masalah di sini adalah elemen ketujuh belas ekstra dengan nilai yang tidak diketahui. Siklus masih akan mencetak tepat 17 integer (dalam format heksadesimal) dan berakhir tanpa keluhan.

Tetapi kompiler memiliki pendapat sendiri tentang masalah ini. Dia sangat menyadari bahwa bacaan ketujuh belas memprovokasi perilaku yang tidak terbatas. Menurut logikanya, setiap instruksi selanjutnya berada dalam limbo: tidak ada persyaratan bahwa setelah perilaku tidak pasti sesuatu harus ada sama sekali (instruksi formal bahkan sebelumnya mungkin sedang diserang, karena perilaku tidak terbatas juga bekerja di arah yang berlawanan). Dalam kasus kami, kompiler hanya akan mengabaikan pemeriksaan kondisi di loop, dan akan berputar selamanya, atau lebih tepatnya, sampai mulai membaca di luar memori yang dialokasikan untuk stack, setelah itu sinyal SIGSEGV akan bekerja.

Ini lucu, tetapi jika GCC memulai dengan pengaturan yang kurang agresif untuk optimisasi, itu akan memberi peringatan:

 $ g++ -W -Wall -O1 testvec.c testvec.c: In function 'int main(int, char**)': testvec.c:20:15: warning: iteration 16 invokes undefined behavior [-Waggressive-loop-optimizations] printf(" %02x", tmp[i]); ~~~~~~^~~~~~~~~~~~~~~~~ testvec.c:19:19: note: within this loop for (i = 0; i < 17; i ++) { ~~^~~~ 

Pada -O9, peringatan ini entah bagaimana menghilang. Mungkin faktanya adalah bahwa pada tingkat optimasi yang tinggi, kompiler lebih agresif memberlakukan penyebaran loop. Mungkin (tetapi tidak akurat) bahwa ini adalah bug GCC (dalam arti hilangnya peringatan; dengan demikian, tindakan GCC dalam hal apa pun tidak bertentangan dengan standar, karena tidak memerlukan penerbitan "diagnostik" dalam situasi ini).

Kesimpulan: jika Anda menulis kode dalam C atau C ++, berhati-hatilah dan hindari situasi yang mengarah pada perilaku tidak terdefinisi, bahkan ketika sepertinya “tidak apa-apa”.

Tipe integer yang tidak ditandatangani adalah penolong yang baik dalam perhitungan aritmatika, karena mereka dijamin semantik modular (tetapi Anda masih bisa mendapatkan masalah terkait dengan ekstensi tipe integer). Pilihan lain - karena alasan tertentu tidak populer - adalah tidak menulis dalam C dan C ++ sama sekali. Karena beberapa alasan, solusi ini tidak selalu cocok. Tetapi jika Anda dapat memilih bahasa untuk menulis program, mis. ketika Anda baru memulai proyek baru pada platform yang mendukung Go, Rust, Java, atau bahasa lain, mungkin lebih menguntungkan jika menolak menggunakan C sebagai "bahasa default". Pilihan alat, termasuk bahasa pemrograman, selalu merupakan kompromi. Jebakan C, terutama perilaku yang tidak terbatas dalam operasi dengan tipe yang ditandatangani, menyebabkan biaya tambahan untuk pemeliharaan kode lebih lanjut, yang sering diremehkan.