Lompat ke konten

Tinjauan ilmiah

Pemeriksaan Model untuk Logika Kendali: Spesifikasi, Contoh Tandingan, dan Ruang Keadaan

Redaksi ARSTEMA · · 9 menit baca

Abstrak

Pemeriksaan model merupakan metode verifikasi formal yang menilai apakah perilaku suatu model memenuhi sifat yang dirumuskan secara eksplisit. Tinjauan ini membahas spesifikasi temporal, penafsiran contoh tandingan, dan teknik untuk menangani besarnya ruang keadaan. Sumber mencakup uraian metode, tinjauan contoh tandingan, serta studi kasus proteksi perlintasan trem dan perencanaan produksi. Contoh tandingan dapat menunjukkan lintasan yang melanggar persyaratan, tetapi kegunaannya bergantung pada keterbacaan jejak bagi pemakai. Pada kasus perlintasan, insinyur perkeretaapian mengalami kesulitan menilai pelanggaran karena hampir tidak mungkin menemukan letak galat dari contoh tandingan UPPAAL. Penulis studi tersebut mengusulkan pemetaan balik agar contoh tandingan ditampilkan pada model tingkat tinggi. Pemeriksaan kasus yang sama menunjukkan bahwa persyaratan ketersediaan bergantung pada konfigurasi, sedangkan persyaratan fungsional tidak. Representasi simbolik, reduksi urutan parsial, penyempurnaan abstraksi, dan pemeriksaan terbatas menangani ledakan ruang keadaan melalui pendekatan yang berbeda. Dalam kasus produksi, keterbatasan memori membatasi ukuran model yang dapat ditelusuri secara menyeluruh, sementara eksplorasi juga dipakai untuk mencari rencana produksi.

Kata kunci: pemeriksaan model; verifikasi formal; logika kendali; contoh tandingan; ruang keadaan; perencanaan produksi

Pendahuluan

Sistem kendali merespons keadaan operasi sesuai dengan aturan yang dinyatakan dalam rancangannya. Ketika beberapa proses berlangsung bersamaan, pembacaan aturan secara terpisah tidak selalu memperlihatkan semua akibat gabungannya. Pemeriksaan model menawarkan cara untuk menelaah perilaku yang dinyatakan dalam model dan membandingkannya dengan persyaratan formal. Metode ini digunakan pada perangkat keras dan perangkat lunak, termasuk sistem dengan proses yang berlangsung secara bersamaan (Clarke dkk., 2012).

Ada perbedaan antara menggambarkan urutan kerja dan memeriksa apakah urutan yang dimungkinkan memenuhi persyaratan. Model menyatakan keadaan dan peralihan yang dapat terjadi, sedangkan persyaratan menyatakan perilaku yang diharapkan. Pemeriksa model memadukan keduanya untuk menilai sifat yang dipilih. Jika sifat tertentu tidak berlaku, alat dapat menghasilkan contoh tandingan, yaitu jejak perilaku yang menunjukkan pelanggaran sifat tersebut (Clarke dkk., 2012; Debbi, 2018).

Dalam perkeretaapian, pemeriksaan dapat digunakan untuk menelaah spesifikasi fungsi proteksi. Dalam perencanaan produksi, eksplorasi ruang keadaan juga dapat diarahkan untuk menemukan rencana yang memenuhi pembatasan dan memperbaiki sasaran produksi.

Model, persyaratan, dan arti hasil pemeriksaan

Model berbasis keadaan menyatakan keadaan yang dapat ditempati sistem serta transisi yang menghubungkannya. Dalam uraian Clarke dan rekan, sistem reaktif dimodelkan dengan himpunan keadaan terbatas, hubungan transisi, dan penanda yang menyatakan proposisi yang benar pada setiap keadaan. Lintasan merupakan urutan keadaan yang saling terhubung oleh transisi. Representasi ini memungkinkan perilaku ditelaah berdasarkan kemungkinan perpindahan keadaan dan interaksi antarkomponen (Clarke dkk., 2012).

Pemodelan memerlukan pemilihan rincian yang relevan terhadap sifat yang hendak diperiksa. Penyederhanaan membantu membentuk representasi yang dapat dianalisis dan menghubungkan pertanyaan verifikasi dengan perilaku yang penting bagi persyaratan. Pada studi perlintasan, pemodelan ditempatkan pada tingkat rancangan fungsi agar insinyur dapat memeriksa spesifikasi sebelum tahap implementasi (Clarke dkk., 2012; Lukács dan Bartha, 2022).

Persyaratan merupakan sasaran pemeriksaan yang dibedakan dari deskripsi perilaku model. Logika temporal menyediakan cara menyatakan hubungan antara keadaan dan perkembangan perilaku sepanjang waktu. Suatu sifat, misalnya, dapat menyatakan bahwa setiap permintaan akhirnya memperoleh tanggapan atau bahwa keadaan galat tidak dapat dicapai. Perumusan yang jelas menghubungkan kebutuhan operasional dengan pertanyaan yang dijawab oleh pemeriksa model (Clarke dkk., 2012).

Pilihan logika memengaruhi pertanyaan yang dapat dinyatakan. Logika temporal linear membahas sifat sepanjang lintasan, sedangkan logika temporal bercabang dapat menyatakan sifat tentang lintasan yang mungkin dari suatu keadaan. Keduanya memiliki kemampuan pengungkapan yang berbeda. Pemilihan bahasa sifat mengikuti hubungan yang hendak diperiksa antara keadaan, lintasan, dan kemungkinan perilaku sistem (Clarke dkk., 2012).

Lukács dan Bartha menjelaskan tiga kemungkinan hasil pemeriksaan. Persyaratan dapat dinyatakan terpenuhi pada model, atau ditemukan pelanggaran yang disertai contoh tandingan. Kemungkinan lainnya ialah pemeriksaan tidak selesai karena memori tidak cukup atau dihentikan sebelum selesai karena berlangsung terlalu lama. Kategori terakhir menyatakan bahwa proses pemeriksaan tidak menghasilkan putusan tentang pemenuhan persyaratan (Lukács dan Bartha, 2022).

Kasus perlintasan trem menempatkan pekerjaan spesifikasi dalam konteks rekayasa sistem perkeretaapian. Lingkungan yang diusulkan membantu insinyur membangun spesifikasi fungsi dengan menggabungkan pemodelan tingkat tinggi dan pemeriksaan model. Persyaratan dari ahli domain diubah melalui bahasa antara yang dibatasi sebelum dirumuskan dalam logika temporal bercabang. Proses ini menghubungkan uraian kebutuhan dengan bentuk yang dapat diperiksa alat (Lukács dan Bartha, 2022).

Contoh tandingan dan penafsiran hasil

Contoh tandingan merupakan keluaran diagnostik ketika sifat yang sesuai untuk pemeriksaan gagal. Jejaknya memperlihatkan perilaku model yang menyebabkan pertentangan dengan sifat yang diperiksa. Debbi membahas contoh tandingan sebagai sarana membantu perancang menemukan sumber galat dan meninjau algoritme untuk menghasilkan contoh yang lebih kecil dan informatif. Ukuran dan keterbacaan keluaran menjadi pertimbangan karena jejak harus dipahami oleh orang yang mengenal rancangan (Debbi, 2018).

Pembacaan jejak mencakup keadaan awal dan transisi yang menyusunnya. Dengan menelusuri langkah menuju pelanggaran, tim dapat memeriksa perilaku yang ditampilkan serta hubungan antara sifat formal dan kebutuhan yang dimaksud. Kegiatan ini menghubungkan kemampuan diagnostik alat dengan pekerjaan rekayasa persyaratan dalam kasus perkeretaapian (Debbi, 2018; Lukács dan Bartha, 2022).

Pada pemeriksaan komponen kasus perlintasan, insinyur perkeretaapian mengalami kesulitan menilai hasil pelanggaran persyaratan. Ketika UPPAAL memberikan contoh tandingan, mereka hampir tidak dapat menemukan letak galat penyebab pelanggaran dari jejak tersebut. Lukács dan Bartha mengusulkan pengembangan pemetaan balik atau anotasi agar contoh tandingan dapat ditampilkan pada model tingkat tinggi yang digunakan insinyur (Lukács dan Bartha, 2022).

Bentuk sifat memengaruhi arti keluaran diagnostik. Clarke dan rekan secara khusus menjelaskan contoh tandingan ketika spesifikasi yang berlaku untuk semua lintasan ternyata salah. Rumusan sifat dan informasi tentang model membantu menghubungkan jejak dengan persyaratan yang sedang dinilai. Tinjauan Debbi menempatkan pembuatan contoh tandingan yang ringkas dan informatif sebagai bagian dari persoalan penyajian hasil tersebut (Clarke dkk., 2012; Debbi, 2018).

Ledakan ruang keadaan dan pilihan pemeriksaan

Ruang keadaan adalah himpunan keadaan yang berkaitan dengan perilaku model. Pada sistem dengan proses yang berlangsung bersamaan, kemungkinan gabungan keadaan dapat bertambah sangat besar ketika variabel dan proses bertambah. Clarke dan rekan menyebut persoalan ini sebagai ledakan ruang keadaan. Dampaknya bersifat praktis: pencarian yang dapat dirumuskan dapat membutuhkan sumber daya komputasi yang besar (Clarke dkk., 2012).

Pemeriksaan keadaan eksplisit mengakses keadaan sebagai bagian dari pencarian. Pendekatan simbolik menggunakan representasi himpunan keadaan, misalnya diagram keputusan biner, sehingga keadaan tidak harus dicantumkan secara individual dengan cara yang sama. Menurut Clarke dan rekan, representasi simbolik sering kali jauh lebih ringkas dalam praktik. Pilihan representasi dengan demikian memengaruhi cara pemeriksa menyimpan dan mengolah informasi tentang model (Clarke dkk., 2012).

Reduksi urutan parsial memanfaatkan independensi tindakan dalam proses yang tersusun secara asinkron, yaitu proses yang tidak harus maju secara serempak. Tujuannya ialah menghindari penelusuran yang tidak perlu atas urutan tindakan yang setara bagi pemeriksaan yang relevan. Dalam perencanaan produksi, pembatasan pencarian juga digunakan untuk mengarahkan eksplorasi menuju sasaran rencana yang dipilih (Clarke dkk., 2012; Edelkamp dan Greulich, 2018).

Abstraksi menyederhanakan representasi dengan menghilangkan rincian yang dianggap tidak relevan terhadap sifat tertentu. Penyempurnaan abstraksi yang dipandu contoh tandingan, atau CEGAR, mencari tingkat rincian yang memadai secara bertahap. Teorema pelestarian sifat yang dijelaskan Clarke dan rekan menyatakan bahwa sifat universal yang berlaku pada model abstrak juga berlaku pada model konkret yang diwakilinya. Namun, model abstrak dapat menghasilkan contoh tandingan semu, yaitu jejak yang muncul akibat abstraksi tetapi tidak sesuai dengan perilaku model konkret. Analisis jejak semacam itu digunakan untuk menyempurnakan abstraksi sebelum pemeriksaan diulang (Clarke dkk., 2012).

Pemeriksaan model terbatas atau BMC mencari contoh tandingan sampai batas panjang lintasan dengan bantuan pemecah keterpenuhan Boolean, yaitu alat untuk mencari nilai variabel yang memenuhi rumusan logika Boolean. Batas pencarian dapat dinaikkan ketika contoh tandingan belum ditemukan. Untuk sifat keselamatan, Clarke dan rekan menyatakan bahwa pemeriksaan contoh tandingan yang panjangnya lebih pendek daripada diameter sistem mencukupi. Diameter adalah jumlah transisi terkecil untuk menjangkau seluruh keadaan yang dapat dicapai (Clarke dkk., 2012).

Dalam pengalaman industri yang dirangkum Clarke dan rekan, BMC memiliki keunggulan dibandingkan pemeriksaan simbolik berbasis diagram keputusan biner: contoh tandingan ditemukan lebih cepat, panjangnya minimum, dan memori yang digunakan lebih sedikit. Teknik ini juga menghindarkan pengguna dari pemilihan urutan variabel yang diperlukan pada pendekatan diagram keputusan biner (Clarke dkk., 2012).

Kasus produksi memperlihatkan kaitan ukuran model dan memori yang tersedia. Pada eksperimen Z2 dengan batas RAM 16 GB, model waktu virtual lokal atau LVT dapat menelusuri seluruh ruang keadaan sampai 3 kendaraan pengangkut. Model sistem peristiwa diskret atau DES dapat menelusuri seluruh ruang keadaan untuk tidak lebih dari 2 kendaraan. Pada jumlah kendaraan yang lebih besar untuk masing-masing model, pencarian dihentikan ketika mencapai batas memori tersebut (Edelkamp dan Greulich, 2018).

Representasi simbolik, reduksi urutan parsial, abstraksi, dan pemeriksaan terbatas menanggapi ledakan ruang keadaan melalui pilihan yang berbeda. Representasi simbolik mengubah cara himpunan keadaan disimpan dan diolah. Reduksi urutan parsial memanfaatkan independensi tindakan, abstraksi memilih tingkat rincian, sedangkan BMC membatasi panjang pencarian. Sifat yang ingin diperiksa dan bentuk hasil menjadi dasar pemilihan teknik (Clarke dkk., 2012).

Dari verifikasi kendali ke perencanaan produksi

Pada sistem perkeretaapian, spesifikasi fungsi berkaitan dengan perilaku yang diharapkan dari sistem proteksi. Lukács dan Bartha menggunakan kasus perlindungan perlintasan antara trem dan jalan untuk menggambarkan metodologi pemodelan serta verifikasi. Kasus tersebut dipilih karena arsitekturnya cukup sederhana untuk cakupan artikel dan dapat memperlihatkan ciri utama pendekatan yang diusulkan (Lukács dan Bartha, 2022).

Lingkungan yang diusulkan menempatkan insinyur perkeretaapian sebagai pengguna spesifikasi fungsi. Kebutuhan dapat berasal dari berbagai sumber dan memiliki tingkat keformalan yang berbeda. Pada pemeriksaan komponen titik deteksi, kebutuhan dalam bahasa alami diubah menjadi rumusan logika temporal bercabang. Penulis melaporkan bahwa pengolahan persyaratan memerlukan banyak interaksi dengan insinyur bidang terkait (Lukács dan Bartha, 2022).

Selain contoh persyaratan yang ditampilkan dalam studi perlintasan, penulis memeriksa 50 persyaratan lain pada 90 konfigurasi. Mereka menemukan bahwa persyaratan yang berkaitan dengan ketersediaan bergantung pada konfigurasi, sedangkan persyaratan fungsional tidak bergantung pada konfigurasi. Temuan ini memperlihatkan peran konfigurasi dalam membaca hasil pemeriksaan komponen pada kasus tersebut (Lukács dan Bartha, 2022).

Edelkamp dan Greulich memakai SPIN pada kasus Z2, sistem monorel fisik untuk perakitan lampu belakang. Lantai produksi direpresentasikan sebagai proses yang saling berkomunikasi, sedangkan perpindahan barang dimodelkan melalui kanal. Selain memvalidasi rancangan model, penulis memanfaatkan eksplorasi untuk mencari rencana yang mengoptimalkan produksi.

Dalam sistem fisik Z2, stasiun perakitan dihubungkan oleh monorel dan kendaraan pengangkut membawa produk sesuai kebutuhan proses. Model analisis menyederhanakan sistem menjadi proses reaktif. Produk direpresentasikan sebagai pesan yang bergerak melalui proses, sementara kanal membantu menggambarkan aliran dan antrean. Representasi tersebut menerjemahkan unsur produksi ke dalam struktur yang dapat dieksplorasi oleh pemeriksa model (Edelkamp dan Greulich, 2018).

Sasaran perencanaan pada kasus itu memperhitungkan waktu perjalanan dan waktu tunggu, bukan hanya jumlah langkah dalam rencana. Penulis menggunakan pencarian cabang dan batas dengan pembatasan untuk memperoleh rencana, serta membandingkannya dengan eksplorasi acak berbasis pencarian Monte Carlo. Pencarian cabang dan batas mempertahankan sasaran biaya ketika menelusuri kemungkinan rencana, sedangkan pendekatan pembanding menggunakan eksplorasi acak untuk mencari solusi (Edelkamp dan Greulich, 2018).

Keterbatasan tinjauan

Sumber mencakup uraian teoretis, tinjauan tentang contoh tandingan, dan studi kasus dari domain yang berbeda. Kasus tersebut memakai model, persyaratan, alat, serta tujuan yang berbeda sehingga tidak menyediakan perbandingan terkontrol tentang keunggulan setiap teknik pada sistem yang sama. Hasil penerapan berkaitan dengan model dan kondisi yang dijelaskan masing-masing penulis. Hubungan antara model, lingkungan, dan implementasi menentukan cakupan kesimpulan tentang sistem yang diterapkan (Clarke dkk., 2012; Lukács dan Bartha, 2022).

Kesimpulan

Pemeriksaan model membantu menilai hubungan antara perilaku yang dimungkinkan oleh model dan persyaratan formal yang dipilih. Contoh tandingan dapat mengarahkan perhatian pada lintasan yang melanggar sifat. Kasus perlintasan menunjukkan pentingnya penyajian hasil yang dapat ditafsirkan oleh ahli domain dan hubungan hasil dengan konfigurasi yang diperiksa.

Ledakan ruang keadaan mendorong penggunaan representasi simbolik, reduksi, abstraksi, dan pencarian terbatas. Kasus perlintasan dan perencanaan produksi menunjukkan penggunaan eksplorasi model untuk tujuan yang berbeda. Kesimpulan penerapannya bergantung pada kesesuaian model, persyaratan, asumsi, dan cakupan pencarian dengan sistem yang ditelaah.

Daftar pustaka

  1. Clarke dkk. (2012). Model Checking and the State Explosion Problem. Springer-Verlag. https://www.cs.cmu.edu/~emc/papers/Conference%20Papers/Model%20Checking%20and%20the%20State%20Explosion%20Problem.pdf
  2. Debbi (2018). Counterexamples in Model Checking - A survey. Informatica. https://www.informatica.si/index.php/informatica/article/view/1442
  3. Lukács dan Bartha (2022). Formal Modeling and Verification of the Functionality of Electronic Urban Railway Control Systems Through a Case Study. Urban Rail Transit. https://link.springer.com/article/10.1007/s40864-022-00177-8
  4. Edelkamp dan Greulich (2018). A case study of planning for smart factories. International Journal on Software Tools for Technology Transfer. https://link.springer.com/article/10.1007/s10009-018-0498-1

Pelajari lebih dalam di ARSTEMA Academy