Apa sebenarnya Memeriksa Model Simbolik?

8

Saya tahu bahwa Symbolic Model Checking adalah state space traversal berdasarkan representasi set negara dan hubungan transisi sebagai rumus seperti dalam CTL menggunakan model seperti Kripke Model. Saya tahu teorinya. Tetapi saya merasa sulit untuk memahami aplikasi yang sebenarnya. Di mana tepatnya itu digunakan? Apa sebenarnya yang dilakukannya dan bagaimana cara kerjanya?

Dapatkah seseorang menjelaskan dengan contoh nyata dan menghubungkan teori dengan praktik?

formal-methods model-checking software-verification Xpleria
sumber
1
Ini sepertinya luas bagi saya. "Apa fungsinya?" bagian mungkin cakupannya masuk akal (atau tidak), tetapi "di mana itu digunakan?" adalah a) pertanyaan lain seluruhnya dan b) mungkin terlalu luas.
Raphael
Tetapi sebuah contoh dapat diambil dan dijelaskan berdasarkan itu. Itu tidak terlalu luas.
Xpleria
2
Mengapa Anda tidak puas dengan deskripsi Pemeriksaan Model Simbolik dalam buku teks standar, misalnya, "Prinsip-prinsip Memeriksa Model" oleh Christel Baier dan Joost-Pieter Katoen? Bagian mana yang Anda bingung?
hengxin
Mereka berbicara tentang 'bagaimana seharusnya itu dilakukan' tetapi tidak 'bagaimana tepatnya itu dilakukan'. Saya mencoba menghubungkan teori dan implementasi praktis. Saya masih baru dalam hal ini dan saya perlu contoh.
Xpleria
1
Anda mungkin berada di situs yang salah. Komputer ilmu adalah tentang konsep-konsep ( "bagaimana hal itu harus dilakukan"), Anda harus bertanya praktisi tentang "bagaimana hal itu dilakukan" bagian.
Raphael

Jawaban:

4

Pemeriksaan Model Simbolik adalah Pengecekan Model yang berfungsi pada status simbolik. Yaitu, mereka mengkodekan negara bagian ke dalam representasi simbolik, biasanya Memerintahkan Binary Decision Diagram (OBDDs).

Pertanyaannya adalah apa yang mereka lakukan dan bagaimana cara kerjanya.

Pertama-tama Anda memiliki kode sumber untuk beberapa aplikasi. Anda kemudian mengubah kode sumber Anda menjadi beberapa grafik transisi-negara seperti Struktur Kripke. Negara diisi dengan proposisi atom yang menggambarkan apa yang benar di negara tertentu. Dalam Model Simbolik Memeriksa proposisi atom dikodekan sebagai OBDD untuk menghemat ruang dan meningkatkan kinerja.

Pemeriksa Model kemudian mulai pada beberapa keadaan awal, dan mengeksplorasi keadaan, mencari kesalahan dalam grafik transisi-negara. Jika menemukan kesalahan, ia akan sering menghasilkan test case yang menunjukkan kesalahan. Ia menggunakan OBDD simbolis untuk menavigasi ruang negara secara optimal. Seandainya saya bisa menjelaskan lebih banyak di sana tetapi masih belajar.

Tapi pada dasarnya itu. Anda memiliki program yang dikonversi menjadi model formal (grafik transisi-negara), dan kemudian Anda menggunakan optimasi simbolis untuk menavigasi ruang keadaan untuk mencari kesalahan (dengan membandingkannya dengan spesifikasi LTL / CTL). Dan jika kesalahan ditemukan, Pemeriksa Model memberi Anda beberapa hal untuk membantu mendokumentasikan dan menyelesaikannya.

Lance Pollard
sumber
5

Pemeriksaan model simbol dapat sangat berguna untuk memverifikasi kebenaran komunikasi dan protokol keamanan. Sebagai contoh:

  • Model simbolis dari implementasi OAUTH2 dapat membantu memeriksa konsekuensi yang tidak diinginkan di mana musuh memperoleh token otentikasi rahasia atau data tidak langsung terkait yang dapat membantu mereka bertentangan dengan proses.
  • Model simbolik dari protokol kriptografi, seperti jabat tangan TLS, dapat membantu memverifikasi bahwa desain kriptografi tidak memiliki konsekuensi yang tidak diinginkan.

Ini bekerja dengan menulis deskripsi simbolis dari semua fungsi primitif dan algoritma protokol, dan kemudian memiliki pemeriksa model simbolis, seperti ProVerif , melintasi ruang keadaan dan berusaha untuk mendeteksi kombinasi keadaan yang menghasilkan hasil yang tidak menguntungkan. Dalam kasus ProVerif, model simbolik dijelaskan menggunakan kalkulus Pi yang diterapkan sebagai bahasa pemodelan. Ini memungkinkan uraian protokol dalam sintaks yang fungsional, seperti ML.

kaepora
sumber