Verifikasi program formal dalam praktik

66

Sebagai seorang insinyur perangkat lunak, saya menulis banyak kode untuk produk industri. Hal-hal yang relatif rumit dengan kelas, utas, beberapa upaya desain, tetapi juga beberapa kompromi untuk kinerja. Saya melakukan banyak pengujian, dan saya bosan dengan pengujian, jadi saya tertarik pada alat bukti formal, seperti Coq, Isabelle ... Bisakah saya menggunakan salah satunya untuk membuktikan secara resmi bahwa kode saya bebas dari bug dan dilakukan dengan itu? - tetapi setiap kali saya memeriksa salah satu alat ini, saya pergi dengan tidak yakin bahwa mereka dapat digunakan untuk rekayasa perangkat lunak sehari-hari. Sekarang, itu hanya bisa saya, dan saya mencari petunjuk / pendapat / ide tentang itu :-)

Secara khusus, saya mendapat kesan bahwa untuk membuat salah satu alat ini bekerja bagi saya akan membutuhkan investasi besar untuk mendefinisikan dengan tepat objek yang tepat, metode ... dari program yang sedang dipertimbangkan. Saya kemudian bertanya-tanya apakah pepatah tidak akan kehabisan tenaga mengingat ukuran semua yang harus dihadapi. Atau mungkin saya harus menghilangkan efek samping (alat-alat yang tepat tampaknya sangat baik dengan bahasa deklaratif), dan saya bertanya-tanya apakah itu akan menghasilkan "kode terbukti" yang tidak dapat digunakan karena tidak akan cepat atau cukup kecil. Juga, saya tidak memiliki kemewahan mengubah bahasa tempat saya bekerja, itu perlu Java atau C ++: Saya tidak bisa memberi tahu bos saya bahwa saya akan kode dalam OXXXml mulai sekarang, karena itu satu-satunya bahasa di yang saya dapat membuktikan kebenaran kode ...

Bisakah seseorang dengan pengalaman lebih banyak alat bukti formal berkomentar? Sekali lagi - Saya akan SENANG menggunakan alat pepatah formal, saya pikir mereka hebat, tetapi saya memiliki kesan mereka berada di menara gading yang tidak dapat saya jangkau dari parit rendah Java / C ++ ... (PS: I juga CINTA Haskell, OCaml ... jangan salah paham: Saya penggemar bahasa deklaratif dan bukti formal, saya hanya mencoba melihat bagaimana saya bisa secara realistis membuat itu berguna untuk rekayasa perangkat lunak)

Pembaruan: Karena ini cukup luas, mari kita coba pertanyaan yang lebih spesifik berikut: 1) apakah ada contoh menggunakan prover untuk membuktikan kebenaran program Java / C ++ industri? 2) Apakah Coq akan cocok untuk tugas itu? 3) Jika Coq cocok, haruskah saya menulis program dalam Coq terlebih dahulu, kemudian menghasilkan C ++ / Java dari Coq? 4) Bisakah pendekatan ini menangani threading dan optimalisasi kinerja?

programming-languages program-correctness software-verification jujur
sumber
3
Saya mendapatkan dan menghargai masalah Anda, tetapi saya tidak mengerti apa pertanyaan ini setelah (sebagai posting SE). Diskusi? Pengalaman? Tidak cocok untuk SE. "Apa pun yang bisa saya lakukan?" nada membuat saya merasa ini adalah pertanyaan yang terlalu luas.
Raphael
3
Begitu ... Saya setuju pertanyaan ini tidak dirumuskan dengan jelas. Jadi, katakanlah: 1) apakah ada contoh menggunakan prover untuk membuktikan kebenaran program Java / C ++ industri? 2) Apakah Coq akan cocok untuk tugas itu? 3) Jika Coq cocok, haruskah saya menulis program dalam Coq terlebih dahulu, lalu apakah Coq menghasilkan C ++ / Java dari itu? 4) Bisakah pendekatan ini mengatasi threading dan optimalisasi kinerja?
Frank
2
Jadi itu empat pertanyaan. 1) mungkin lebih baik di Rekayasa Perangkat Lunak karena Anda tidak mungkin bertemu dengan (banyak) profesional industri di sini. 2) rasanya agak subjektif, tetapi kami mungkin memiliki orang-orang di sini yang dapat menawarkan perspektif objektif. 3) sejauh yang saya tahu benar-benar subyektif. 4) Merupakan pertanyaan yang bagus untuk situs ini. Singkatnya: harap pisahkan pertanyaan Anda, pergi ke Rekayasa Perangkat Lunak dengan yang pertama dan berpikir keras apakah Anda dapat mengharapkan jawaban objektif (!) Di sini (!) Sebelum memposting 2).
Raphael
10
Anda sedang menggambarkan mimpi verifikasi formal, tetapi kami sangat jauh dari berada di sana. AFAIK, verifikasi program adalah tugas yang tidak rutin, dan hanya berlaku untuk program yang sangat sederhana. Yang mengatakan, saya pikir pertanyaan ini tepat untuk situs ini, dan saya akan menghargai seseorang dari daerah mengakui batas-batas bidang mereka, menjelaskan state-of-the-art dan keterbatasan (mungkin dengan menghubungkan ke beberapa survei ).
Yuval Filmus
9
Masalah dengan memverifikasi program C ++ adalah bahwa C ++ bukan bahasa yang didefinisikan dengan baik. Saya tidak berpikir verifikasi skala besar dimungkinkan sampai banyak bagian dari sistem perangkat lunak (OS, perpustakaan, bahasa pemrograman) benar-benar dirancang ulang untuk mendukung verifikasi. Seperti diketahui, Anda tidak bisa hanya membuang 2.00000 baris kode pada seseorang dan mengatakan "verifikasi!". Anda perlu memverifikasi dan menulis kode bersama, dan Anda perlu menyesuaikan kebiasaan pemrograman Anda dengan fakta bahwa Anda juga memverifikasi.
Andrej Bauer

Jawaban:

35

Saya akan mencoba memberikan jawaban singkat untuk beberapa pertanyaan Anda. Harap diingat bahwa ini bukan bidang penelitian saya, jadi sebagian info saya mungkin sudah kedaluwarsa / salah.

  1. Ada banyak alat yang secara khusus dirancang untuk membuktikan secara resmi properti Java dan C ++.

    Namun saya perlu melakukan penyimpangan kecil di sini: apa artinya membuktikan kebenaran suatu program? Pemeriksa tipe Java membuktikan properti formal dari program Java, yaitu bahwa kesalahan tertentu, seperti menambahkan floatdan int, tidak pernah dapat terjadi! Saya membayangkan Anda tertarik pada properti yang jauh lebih kuat, yaitu bahwa program Anda tidak pernah bisa masuk ke keadaan yang tidak diinginkan, atau bahwa output dari fungsi tertentu sesuai dengan spesifikasi matematika tertentu. Singkatnya, ada gradien luas dari apa yang "membuktikan sebuah program yang benar" dapat berarti, dari properti keamanan sederhana menjadi bukti penuh bahwa program memenuhi spesifikasi terperinci.

    Sekarang saya akan berasumsi bahwa Anda tertarik untuk membuktikan sifat kuat tentang program Anda. Jika Anda tertarik pada properti keamanan (program Anda tidak dapat mencapai kondisi tertentu), maka secara umum tampaknya pendekatan terbaik adalah memeriksa model . Namun jika Anda ingin menentukan secara lengkap perilaku program Java, taruhan terbaik Anda adalah menggunakan bahasa spesifikasi untuk bahasa itu, misalnya JML . Ada bahasa seperti itu untuk menentukan perilaku program C, misalnya ACSL , tapi saya tidak tahu tentang C ++.

  2. Setelah Anda memiliki spesifikasi, Anda perlu membuktikan bahwa program tersebut sesuai dengan spesifikasi itu.

    Untuk ini Anda memerlukan alat yang memiliki pemahaman formal tentang spesifikasi Anda dan semantik operasional bahasa Anda (Java atau C ++) untuk mengekspresikan teorema kecukupan , yaitu bahwa pelaksanaan program menghormati spesifikasi.

    Alat ini juga harus memungkinkan Anda untuk merumuskan atau menghasilkan bukti teorema itu. Sekarang kedua tugas ini (menentukan dan membuktikan) cukup sulit, sehingga mereka sering dipisahkan menjadi dua:

    • Satu alat yang mem-parsing kode, spesifikasi dan menghasilkan teorema kecukupan. Seperti yang disebutkan Frank, Krakatau adalah contoh dari alat semacam itu.

    • Satu alat yang membuktikan teorema, secara otomatis atau interaktif. Coq berinteraksi dengan Krakatau dengan cara ini, dan ada beberapa alat otomatis yang kuat seperti Z3 yang juga dapat digunakan.

    Satu (minor) poin: ada beberapa teorema yang terlalu sulit untuk dibuktikan dengan metode otomatis, dan pembuktian teorema otomatis diketahui kadang-kadang memiliki bug kesehatan yang membuat mereka kurang dapat dipercaya. Ini adalah area di mana Coq bersinar dalam perbandingan (tetapi tidak otomatis!).

  3. Jika Anda ingin menghasilkan kode Ocaml, maka pasti menulis dalam Coq (Gallina) terlebih dahulu, kemudian ekstrak kodenya. Namun, Coq buruk dalam menghasilkan C ++ atau Java, jika itu mungkin.

  4. Bisakah alat di atas menangani masalah threading dan kinerja? Mungkin tidak, masalah kinerja dan threading paling baik ditangani oleh alat yang dirancang khusus, karena masalah tersebut sangat sulit. Saya tidak yakin saya punya alat untuk merekomendasikan di sini, meskipun proyek PolyNI Martin Hofmann tampaknya menarik.

Kesimpulannya: verifikasi formal untuk program Java dan C ++ "dunia nyata" adalah bidang yang besar dan berkembang dengan baik, dan Coq cocok untuk bagian-bagian dari tugas itu. Anda dapat menemukan ikhtisar tingkat tinggi di sini misalnya.

cody
sumber
Terima kasih untuk posting ini dan referensi yang Anda tambahkan. IMHO, tujuan insinyur perangkat lunak adalah untuk dapat dengan cepat melepaskan sistem yang akan 1) selalu memberikan hasil yang benar, 2) tidak pernah gagal. Saya dapat melihat masalah regresi di sini, di mana Anda mungkin ingin membuktikan bahwa spesifikasi itu sendiri adalah "bebas bug" :-) jenis seperti mencoba mendefinisikan "proposisi sebenarnya dari suatu bahasa" dengan bahasa meta, kemudian membutuhkan meta lain bahasa untuk itu, lalu satu lagi ...
Frank
6
Masalahnya adalah apa yang "diinginkan" oleh pengguna biasanya tidak dinyatakan dalam bahasa formal! Secara umum tidak ada jawaban formal untuk pertanyaan: "apakah spesifikasi formal ini sesuai dengan ide informal saya?". Dimungkinkan untuk menguji spesifikasi formal, dan membuktikan bahwa ia memiliki sifat matematika tertentu, tetapi pada akhirnya Anda perlu menghubungkan matematika dengan dunia nyata, yang merupakan proses non-formal.
cody
Ya tentu saja - saya selalu menyadari metode formal hanya bisa dimulai dari titik yang didefinisikan dengan baik. Jika spesifikasi itu sesuai atau tidak dengan kebutuhan pengguna kehidupan nyata yang disadari / tidak sadar / belum ditemukan adalah masalah lain, tidak dapat diatasi dengan metode formal (tapi tentu saja masalah bagi insinyur).
Frank
Teorema menurut definisi merupakan proposisi yang terbukti. Jadi, Anda mungkin tidak bermaksud "membuktikan teorema".
nbro
@nbro Wikipedia tampaknya setuju dengan Anda. Mathworld, bagaimanapun, mendefinisikan teorema untuk menjadi proposisi yang " dapat dibuktikan benar dengan operasi matematika yang diterima". Dalam hal ini, memberikan bukti teorema tidak hanya mungkin, tetapi perlu untuk membenarkan menyebut mereka begitu! :) (ini adalah tandingan, tentu saja)
cody
15

Saya ingin menyebutkan tiga aplikasi luar biasa dari metode formal / alat verifikasi formal dalam industri atau sistem nyata non-sepele. Perhatikan bahwa saya memiliki sedikit pengalaman tentang topik ini dan saya hanya mempelajarinya dari membaca makalah.

  1. Alat open source Java Pathfinder (disingkat JPF) yang dirilis oleh NASA pada tahun 2005 adalah sistem untuk memverifikasi program bytecode Java yang dapat dieksekusi (lihat Java Pathfinder @ wiki ). Ini telah digunakan untuk mendeteksi ketidakkonsistenan dalam perangkat lunak eksekutif untuk K9 Rover di NASA Ames.

  2. Makalah ini: Menggunakan Model Memeriksa untuk Menemukan Kesalahan Sistem File Serius @ OSDI'04 menunjukkan bagaimana menggunakan pengecekan model untuk menemukan kesalahan serius dalam sistem file. Sebuah sistem yang disebut FiSC diterapkan pada tiga sistem file yang banyak digunakan, teruji berat: ext3, JFS, dan ReiserFS, dan 32 bug serius ditemukan. Itu memenangkan Penghargaan Kertas Terbaik.

  3. Makalah ini: Bagaimana Amazon Web Services Menggunakan Metode Formal @ CACM'15 menjelaskan bagaimana AWS menerapkan metode formal untuk produk-produknya seperti S3, DynamoDB, EBS, dan manajer kunci yang didistribusikan secara internal. Ini berfokus pada alat TLA + Lamport . Omong-omong, Lamport secara intensif menggunakan kotak alat TLA-nya sendiri. Dia sering memberikan verifikasi formal (cukup lengkap) dalam TLA tentang algoritma / teorema yang diajukan oleh dirinya sendiri (dan juga rekan penulis) dalam lampiran pada makalah.

Hengxin
sumber
4

Spesifikasi formal suatu program adalah (kurang lebih) sebuah program yang ditulis dalam bahasa pemrograman lain. Akibatnya, spesifikasi pasti akan mencakup bug sendiri.

Keuntungan dari verifikasi formal adalah, karena program dan spesifikasinya adalah dua implementasi terpisah, bug mereka akan berbeda. Tetapi tidak selalu: satu sumber bug, kasus yang sering diabaikan, akan sering cocok. Dengan demikian, verifikasi formal bukan obat mujarab: itu masih bisa melewatkan sejumlah bug yang tidak sepele.

Kelemahan dari verifikasi formal adalah bahwa hal itu dapat memaksakan sesuatu seperti dua kali biaya implementasi, mungkin lebih (Anda memerlukan spesialis dalam spesifikasi formal, dan Anda perlu menggunakan lebih atau kurang alat eksperimental yang menyertainya; yang tidak akan murah ).

Saya kira menyiapkan test case dan scaffolding untuk menjalankannya secara otomatis akan lebih baik jika menggunakan waktu Anda.

vonbrand
sumber
The keuntungan dari verifikasi formal adalah bahwa .... Sebuah kedua kelemahan dari verifikasi formal adalah bahwa ... ini adalah membingungkan.
hengxin
Saya pikir ketidakcocokan antara spesifikasi dan tugas informal adalah masalah analisis persyaratan perangkat lunak bukan masalah pemrograman.
Kaveh
3

Verifikasi formal sekarang dimungkinkan untuk program yang menulis subset C ++ yang dirancang untuk sistem tertanam yang kritis terhadap keselamatan. Lihat http://eschertech.com/papers/CanCPlusPlusBeMadeAsSafeAsSpark.ppt untuk presentasi singkat, dan http://eschertech.com/papers/CanCPlusPlusBeMadeAsSafeAsSpark.pdf untuk makalah lengkapnya.

dc42
sumber
5
Terima kasih atas tautannya. Setidaknya gambaran umum singkat dari konten mereka akan berguna, untuk menjaga agar tautan tidak membusuk, terutama karena tautan Anda ke situs web perusahaan: tautan tersebut cenderung ditata ulang secara berkala, sehingga membunuh semua tautan ke situs.
David Richerby
2

Anda mengajukan beberapa pertanyaan berbeda. Saya setuju kelihatannya metode verifikasi formal untuk aplikasi industri / komersial tidak begitu umum. kita harus menyadari bahwa banyak prinsip "verifikasi formal" dibangun dalam kompiler untuk menentukan kebenaran program! jadi, jika Anda menggunakan kompiler modern, Anda menggunakan sebagian besar state-of-the-art dalam verifikasi formal.

Anda mengatakan "Saya bosan dengan pengujian" tetapi verifikasi formal bukan benar-benar pengganti untuk pengujian. dengan cara yang merupakan variasi pada pengujian.

Anda menyebutkan Jawa. ada banyak metode verifikasi formal canggih yang dibangun ke dalam program verifikasi java yang disebut FindBugs yang memang dapat dijalankan melalui basis kode besar. Perhatikan itu akan muncul "positif palsu dan negatif palsu" dan hasilnya perlu ditinjau / dianalisis oleh pengembang manusia. Tetapi perhatikan bahkan jika itu tidak memunculkan cacat fungsional yang sebenarnya, ia biasanya muncul "antipatterns" yang harus dihindari dalam kode pula.

Anda tidak lagi menyebutkan aplikasi khusus Anda selain "industri". Verifikasi formal dalam praktik cenderung bergantung pada aplikasi tertentu.

Teknik verifikasi formal tampaknya banyak digunakan dalam EE untuk membuktikan kebenaran rangkaian misalnya dalam desain mikroprosesor.

Berikut adalah contoh survei alat verifikasi formal di bidang EE oleh Lars Philipson .

vzn
sumber
2
Itu menyesatkan untuk mengatakan bahwa "banyak" verifikasi formal "prinsip dibangun ke dalam kompiler untuk menentukan kebenaran program". Apa yang Anda rujuk adalah pengecekan tipe statis yang dilakukan oleh beberapa kompiler, tetapi properti yang diverifikasi agak sederhana, misalnya menghindari menambahkan angka dan string. Ini membantu, tetapi jauh dari apa yang biasanya dipahami oleh "verifikasi formal".
Martin Berger
2
tidak merujuk pada pemeriksaan tipe statis secara khusus, meskipun itu adalah salah satu contoh sederhana / umum. teknik optimasi kompiler imho, yang tersebar luas dan canggih, kira-kira mirip dengan prinsip verifikasi formal, karena melibatkan teknik canggih untuk menentukan / menunjukkan kesetaraan varian program yang dioptimalkan. jadi sepertinya penting untuk menghindari masalah "memindahkan tiang gawang" di sini dan tidak menganggap itu hanya karena seorang kompiler melakukannya atau dibangun ke dalam kompiler, bukan verifikasi formal.
vzn
2
sepakat ini bukan pemahaman bersama. teknik optimisasi secara kasar membuat model perilaku program, misalnya loop atau subrutin, dan mengoptimalkan model itu, dan kemudian menghasilkan kode baru yang terbukti setara. jadi beberapa optimasi ini cukup canggih dalam menyusun ulang kode & bagi saya mereka menggunakan prinsip verifikasi formal. sepertinya ada banyak contoh lain dari metode verifikasi formal dalam kompiler ... pertanyaan awal mengajukan banyak pertanyaan berbeda seperti yang telah dicatat, saya tidak akan mencoba menjawab semua pertanyaan yang terkandung di dalamnya.
vzn
2
omong-omong tampaknya ada beberapa prinsip verifikasi formal yang juga digunakan dalam JRE, mesin runtime java, misalnya optimasi dinamis, dll ...
vzn
3
itu adalah " impian verifikasi formal" yang dirujuk oleh filmus di atas, yang merupakan abstraksi chimera, dan industri pragmatis / utilitarian / realistis sebagian besar mengenalinya. basis kode besar telah dikenal selama puluhan tahun secara inheren memiliki bug / cacat per K-baris kode dan ini tidak akan pernah berubah tidak peduli bagaimana teori / teknologi berkembang, itu adalah fakta sifat manusia . dan pada kenyataannya teorema matematika yang diciptakan manusia memiliki sifat yang sama, meskipun ini tidak dihargai secara luas! yxy
vzn
1

Mungkin, pemeriksa model mungkin bermanfaat.

http://alloytools.org/documentation.html Alloy adalah pemeriksa model.

Presentasi yang bagus menjelaskan konsep pengecekan model menggunakan Paduan: https://www.youtube.com/watch?v=FvNRlE4E9QQ

Dalam rangkaian alat yang sama muncul 'pengujian berbasis properti', mereka semua mencoba menemukan contoh tandingan untuk model spesifikasi perangkat lunak Anda yang diberikan.

tik tik
sumber