Apakah bukti kebenaran kode pernah menjadi arus utama? [Tutup]

14

Semua kecuali program yang paling sepele diisi dengan bug dan segala sesuatu yang berjanji untuk menghapusnya sangat memikat. Saat ini, bukti kebenaran adalah kode yang sangat esoteris, terutama karena sulitnya mempelajari hal ini dan upaya ekstra yang diperlukan untuk membuktikan suatu program benar. Apakah Anda berpikir bahwa pembuktian kode akan lepas landas?

programming-practices Casebash
sumber

Jawaban:

8

Tidak benar-benar dalam pengertian itu, tetapi pemrograman fungsional murni baik di domain ini. Jika Anda menggunakan Haskell, kemungkinan program Anda benar jika kode dikompilasi. Kecuali dari IO, sistem tipe yang baik adalah bantuan yang baik.

Juga pemrograman untuk kontrak dapat membantu. Lihat Kontrak Kode Microsoft

Jonas
sumber
6
Maaf - Saya belum melakukan banyak "dunia nyata" Haskell, tapi saya sudah melakukan latihan tutorial yang cukup untuk beberapa kehidupan. Hanya karena kompilasi tidak berarti itu kemungkinan berhasil. Dibandingkan dengan misalnya Ada (dipilih karena ini adalah bahasa imperatif yang diketik secara statis), saya akan mengatakan Haskell sedikit lebih mudah, tetapi kebanyakan karena lebih ringkas (kompleksitas cyclomatic yang lebih rendah). Ketika berhadapan dengan IO monad, ada gangguan yang dapat membuat Haskell lebih sulit untuk mendapatkan yang benar - itu hanya cukup berbeda dari gaya imperatif bahwa ada hal-hal yang tidak dapat dilakukan secara alami.
Steve314
Pada "tidak dapat melakukan secara alami", pertimbangkan loop "sementara". Ya, Anda dapat memutar sendiri - tetapi kondisi sementara harus berada dalam monad karena perlu bereaksi terhadap efek samping dari loop body. Ini tidak hanya berarti Anda telah diberi izin untuk menyebabkan efek samping dalam kondisi sementara, tetapi juga membuatnya canggung untuk menggunakannya saat pengulangan. Hasil akhir - umumnya lebih mudah untuk menggunakan rekursi bahkan dalam kode monad IO - dan itu berarti Anda harus menyusun berbagai hal dengan cara tertentu.
Steve314
14

Semua kecuali program yang paling sepele

tidak dapat sepenuhnya dibuktikan benar dengan usaha yang wajar. Untuk bukti formal kebenaran, Anda memerlukan setidaknya spesifikasi formal, dan spesifikasi tersebut harus lengkap dan benar. Ini biasanya bukan apa-apa yang dapat Anda buat dengan mudah untuk sebagian besar program dunia nyata. Sebagai contoh, cobalah untuk menulis spesifikasi seperti itu untuk sesuatu seperti antarmuka pengguna situs diskusi ini, dan Anda tahu apa yang saya maksud.

Di sini saya menemukan artikel yang bagus tentang topik ini:

http://www.encyclopedia.com/doc/1O11-programcorrectnessproof.html

Doc Brown
sumber
Benar - untuk setiap proyek pemrograman ada transisi dari deskripsi informal masalah ke yang formal (biasanya, hari ini, dalam bentuk program), dan itu tidak hilang.
David Thornley
astree.ens.fr Lihat Aplikasi Industri Astrée di sini
zw324
@ZiyaoWei: alat seperti itu membantu, tetapi mereka hanya menemukan beberapa kesalahan formal, tidak lebih. Jika program satu baris suka printf("1")benar atau tidak (misalnya, karena persyaratannya adalah "mencetak angka acak yang terdistribusi secara merata dari 1 hingga 6") tidak dapat diputuskan oleh penganalisa statis semacam itu.
Doc Brown
10

Masalah dengan bukti formal adalah bahwa itu hanya memindahkan masalah mundur selangkah.

Mengatakan bahwa suatu program benar sama dengan mengatakan bahwa suatu program melakukan apa yang seharusnya dilakukan. Bagaimana Anda mendefinisikan apa yang harus dilakukan oleh program? Anda menentukannya. Dan bagaimana Anda mendefinisikan apa yang harus dilakukan program dalam kasus tepi yang tidak dicakup oleh spesifikasi? Nah, maka Anda harus membuat spek lebih rinci.

Jadi misalkan spec Anda akhirnya menjadi cukup rinci untuk menggambarkan perilaku yang benar dari setiap aspek dari seluruh program. Sekarang Anda perlu cara untuk membuat alat bukti Anda memahaminya. Jadi, Anda harus menerjemahkan spec ke dalam semacam bahasa formal yang dapat dipahami oleh alat bukti ... hei, tunggu sebentar!

Mason Wheeler
sumber
2
Juga .. "Waspadalah terhadap bug dalam kode di atas; Saya hanya membuktikannya benar, tidak mencobanya." - Donald Knuth
Brendan
8

Verifikasi formal telah jauh, tetapi biasanya industri / alat yang banyak digunakan tertinggal dari penelitian terbaru. Berikut beberapa upaya terbaru ke arah ini:

Spec # http://research.microsoft.com/en-us/projects/specsharp/ Ini adalah perpanjangan dari C # yang mendukung kontrak kode (kondisi sebelum / sesudah dan invarian) dan dapat menggunakan kontrak ini untuk melakukan berbagai jenis analisis statis .

Proyek serupa dengan ini ada untuk bahasa lain, seperti JML untuk java, dan Eiffel memiliki built-in yang cukup banyak.

Lebih jauh lagi, proyek-proyek seperti slam dan blast dapat digunakan untuk memverifikasi properti perilaku tertentu dengan anotasi / intervensi programmer minimal, tetapi masih tidak dapat berurusan dengan generalisasi penuh bahasa modern (hal-hal seperti integer overflow / pointer aritmatika tidak dimodelkan).

Saya percaya bahwa kita akan melihat lebih banyak teknik ini digunakan dalam praktek di masa depan. Kendala utama adalah bahwa invarian program sulit untuk disimpulkan tanpa anotasi manual, dan programmer biasanya tidak mau memberikan anotasi ini karena melakukannya terlalu membosankan / memakan waktu.

Lucina
sumber
4

Tidak kecuali jika metode pembuktian kode secara otomatis tanpa kerja pengembang yang luas muncul.

Fishtoaster
sumber
Pertimbangkan argumen ekonomi: mungkin lebih baik bagi pengembang untuk "membuang" waktu dengan bukti kebenaran daripada kehilangan uang karena kesalahan perangkat lunak.
Andres F.
Saya setuju dengan fishtoaster, kecuali jika itu menjadi jauh lebih sedikit sumber daya, banyak perangkat lunak bisnis biasa tidak akan memiliki biaya / manfaat untuk mendukung tingkat kebenaran itu. Dalam aplikasi LOB kepada audiensi yang ditahan kadang-kadang manfaat bisnis paling besar untuk biaya terkait laporan bug adalah menambahkan baris ke dokumen yang mengatakan "jangan lakukan itu"
Bill
3

Beberapa alat metode formal (seperti misalnya Frama-C untuk perangkat lunak kritis yang disematkan C) dapat dipandang sebagai (semacam) yang menyediakan, atau setidaknya memeriksa, bukti (kebenaran) dari perangkat lunak yang diberikan. (Frama-C memeriksa bahwa suatu program mematuhi spesifikasi yang diformalkan, dalam beberapa hal, dan menghormati invarian beranotasi yang secara eksplisit dijelaskan dalam program).

Di beberapa sektor, metode formal semacam itu dimungkinkan, misalnya DO-178C untuk perangkat lunak penting dalam pesawat sipil. Jadi dalam beberapa kasus, pendekatan seperti itu mungkin dan bermanfaat.

Tentu saja, mengembangkan perangkat lunak kurang kereta sangat mahal. Tetapi pendekatan metode formal masuk akal untuk beberapa jenis perangkat lunak. Jika Anda pesimistis, Anda mungkin berpikir bahwa bug dipindahkan dari kode ke spesifikasi formal (yang mungkin memiliki beberapa "bug", karena memformalkan perilaku yang dimaksud dari perangkat lunak itu sulit dan rawan kesalahan).

Basile Starynkevitch
sumber
3

Saya menemukan pertanyaan ini, dan saya pikir tautan ini mungkin menarik:

Aplikasi Industri Astrée

Membuktikan tidak adanya RTE dalam sistem yang digunakan oleh Airbus dengan lebih dari 130 ribu baris kode pada tahun 2003 tampaknya tidak buruk, dan saya ingin tahu apakah akan ada yang mengatakan bahwa ini bukan dunia nyata.

zw324
sumber
2

Tidak. Pepatah umum untuk ini adalah, "Dalam teori, teori dan praktik adalah sama. Dalam praktik, tidak."

Satu contoh yang sangat sederhana: Kesalahan ketik.

Sebenarnya menjalankan kode melalui pengujian unit menemukan hal-hal seperti itu dengan segera, dan serangkaian tes yang kohesif akan meniadakan kebutuhan akan bukti formal. Semua kasus penggunaan - kasus baik, buruk, kesalahan, dan tepi - harus disebutkan dalam tes unit, yang berakhir sebagai bukti kode yang lebih baik benar daripada bukti yang terpisah dari kode.

Terutama jika persyaratan berubah, atau algoritme diperbarui untuk memperbaiki bug - bukti formal lebih cenderung berakhir, sama dengan komentar kode yang sering didapat.

Izkata
sumber
3
Salah. Tidak ada pengujian unit yang dapat mencakup seluruh jajaran parameter yang mungkin. Bayangkan "unit testing" kompiler dengan cara ini, memastikan bahwa tidak ada perubahan semantik.
SK-logic
3
unit testing bukan cawan suci ...
Ryathal
1
@ Winston Ewert, ada kompiler terverifikasi (dan banyak assembler terverifikasi lainnya). Dan perangkat keras secara resmi diverifikasi lebih sering daripada perangkat lunak. Lihat di sini: gallium.inria.fr/ ~ xleroy
SK-logic
1
@ SK-logika, ya ada kompiler mainan yang terbukti benar untuk tujuan akademik. Tapi bagaimana dengan kompiler yang digunakan orang? Saya menduga sebagian besar kompiler diperiksa menggunakan berbagai bentuk pengujian otomatis dan hampir tidak ada bukti formal yang benar dilakukan.
Winston Ewert
1
@ Winston Ewert, bukti kebenaran praktis dan digunakan secara luas dalam kehidupan nyata. Apa yang tidak terlalu praktis adalah sebagian besar bahasa arus utama modern. Saya berharap mereka semua akan mati, sehingga nilai bukti kebenaran akan meningkat di masa depan.
SK-logic
1

Saya berpikir bahwa batasan yang dikenakan pada bukti kebenaran karena masalah penghentian mungkin menjadi penghalang terbesar untuk bukti kebenaran menjadi arus utama.

Paddyslacker
sumber
8
Masalah penghentian mengatakan bahwa kami tidak dapat menentukan apakah ada program sewenang-wenang yang dihentikan. Program-program ini dapat melakukan hal-hal aneh, seperti menguji setiap bilangan bulat untuk melihat apakah itu adalah prime Mersenne. Kami tidak melakukan ini dalam program normal!
Casebash
1
@Casebash, pertanyaannya adalah apakah ada subset program yang berguna yang masalah penyelesaiannya dapat diselesaikan. Itu sama sekali tidak jelas. Apakah kita dapat membatasi program kita sehingga kita tidak dapat melakukan hal-hal seperti menguji setiap integer tanpa merusak kemampuan kita untuk melakukan tugas-tugas yang bermanfaat?
Winston Ewert
1

Ini sudah digunakan oleh semua orang. Setiap kali Anda menggunakan pemeriksaan jenis bahasa pemrograman Anda, pada dasarnya Anda melakukan pembuktian matematika tentang kebenaran program Anda. Ini sudah bekerja dengan sangat baik - itu hanya mengharuskan Anda memilih jenis yang benar untuk setiap fungsi dan struktur data yang Anda gunakan. Semakin akurat jenisnya, semakin baik pula pengecekan yang Anda dapatkan. Jenis yang ada tersedia dalam bahasa pemrograman sudah memiliki alat yang cukup kuat untuk menggambarkan hampir semua perilaku yang mungkin. Ini berfungsi dalam setiap bahasa yang tersedia. C ++ dan bahasa statis hanya melakukan pemeriksaan dalam waktu kompilasi, sementara bahasa yang lebih dinamis seperti python melakukannya ketika program dijalankan. Pemeriksaan masih ada dalam semua bahasa ini. (misalnya, c ++ sudah mendukung pengecekan efek samping seperti halnya haskell,

tp1
sumber
Dengan sedikit tentang efek samping dalam C ++, apakah Anda merujuk pada kebenaran const?
Winston Ewert
ya, fungsi const + const member. Jika semua fungsi anggota Anda adalah const, semua data dalam objek tidak dapat dimodifikasi.
tp1
Mereka masih dapat dimodifikasi jika Anda menggunakan mutableatau const_cast. Saya tentu melihat koneksi yang Anda gambar di sana, tetapi rasa dua pendekatan tampaknya agak berbeda bagi saya.
Winston Ewert
Nah, itu sebabnya Anda harus memilih untuk menggunakannya - selalu ada cara untuk mengatasinya. Tetapi yang penting adalah bagaimana membuat kompiler memeriksa masalah di area tersebut.
tp1