Pengujian simbolik dengan Halmos: Memanfaatkan pengujian yang ada untuk verifikasi formal

Verifikasi formal — proses menggunakan metode matematis untuk "memeriksa" program atau kontrak pintar di sejumlah input — umumnya dipandang sebagai alternatif yang lebih ringkas dan lebih komprehensif daripada pengujian tradisional untuk menulis kode yang lebih berkualitas dan lebih aman. Namun pada kenyataannya, verifikasi formal merupakan proses yang terbuka dan interaktif. Sama seperti pengujian unit, pengembang harus secara dinamis mendefinisikan dan melapisi spesifikasi formal, mengulangi pendekatan mereka saat kode dan analisis mereka berkembang. Selanjutnya, verifikasi formal hanya seefektif spesifikasinya, yang dapat memakan waktu lama untuk menulis (dan sering disertai dengan kurva belajar yang curam). 

Bagi banyak pengembang yang menganggap prosesnya menakutkan, pengujian unit seringkali merupakan rute yang lebih hemat biaya dan efisien waktu untuk memilah kebenaran program. Dalam praktiknya, verifikasi formal bukanlah alternatif yang lebih komprehensif untuk pengujian unit, tetapi pelengkap. Proses ini memiliki kekuatan dan keterbatasan yang berbeda, memberikan jaminan yang lebih besar bila digunakan bersama-sama. Pengembang akan selalu perlu menulis pengujian unit — jadi bagaimana jika kita dapat menggunakan properti yang sama untuk verifikasi formal?

Halmos, alat verifikasi formal sumber terbuka kami, memungkinkan pengembang untuk melakukannya menggunakan kembali properti yang sama ditulis untuk pengujian unit untuk spesifikasi formal melalui pengujian simbolik. Daripada harus membuat sekumpulan properti yang kuat dari awal, developer dapat menghindari pekerjaan duplikasi dan meningkatkan pengujian mereka beberapa spesifikasi sekaligus tanpa memulai dari awal. Kami merancang alat ini untuk digunakan, bersama dengan alat lainnya dalam proses verifikasi formal, sebagai jalan menuju verifikasi formal; pengembang dapat memulai dengan beberapa analisis dengan sedikit usaha, sebelum menambahkan lebih banyak lagi nanti dalam proses.

Dalam posting ini, kami membahas tantangan verifikasi formal, dan potensi untuk menjembatani kesenjangan antara pengujian unit dan verifikasi formal dengan pengujian simbolik. Kami kemudian menelusuri demo Halmos menggunakan kode kontrak pintar yang ada, dan melihat sekilas alat verifikasi formal lainnya (banyak sumber terbuka) yang tersedia untuk pengembang.

Verifikasi formal vs pengujian

Verifikasi formal — umumnya disukai oleh pengembang blockchain karena ketelitian dan kelengkapannya — adalah proses pembuktian kebenaran suatu program dengan memverifikasi bahwa program tersebut memenuhi properti kebenaran tertentu. Properti, yang khusus untuk program, biasanya disediakan secara eksternal dan diekspresikan menggunakan bahasa atau notasi formal yang didukung oleh alat verifikasi yang digunakan. Pengembang sering menganggap verifikasi formal sebagai solusi tombol tekan untuk menguji properti di semua kemungkinan skenario secara otomatis, namun pada kenyataannya, verifikasi formal dapat menjadi proses padat karya dan sangat interaktif.

Seperti verifikasi formal, pengujian unit melibatkan evaluasi apakah suatu program berfungsi seperti yang diharapkan; pengujian, bagaimanapun, hanya memeriksa perilaku program untuk beberapa input, sementara verifikasi formal dapat memeriksanya semua input yang mungkin. Baik pengujian maupun verifikasi formal memerlukan deskripsi tentang perilaku yang diharapkan dari program (dengan kasus uji yang digunakan dalam pengujian dan spesifikasi formal yang digunakan dalam verifikasi formal). Tapi, ketika digunakan bersama, mereka dapat memberikan pemeriksaan program yang lebih menyeluruh. Pengujian, misalnya, efektif untuk menemukan bug dan kesalahan sederhana, tetapi biasanya lebih cepat dan lebih mudah dilakukan. Verifikasi formal, meski lebih rumit untuk digunakan, cukup kuat untuk membuktikan tidak adanya kesalahan atau mengungkap bug halus yang mudah terlewatkan dalam pengujian atau tinjauan kode.

Spesifikasi overhead

Salah satu tantangan utama verifikasi formal adalah overhead penulisan dan pemeliharaan spesifikasi formal. Proses ini seringkali melibatkan tugas yang memakan waktu untuk menulis spesifikasi secara manual menggunakan bahasa khusus (yang perlu dipelajari oleh banyak pengembang terlebih dahulu). Prosesnya juga inkremental, biasanya dimulai dengan menulis properti sederhana dan memverifikasinya terlebih dahulu, kemudian secara bertahap menambahkan properti yang lebih kompleks di atasnya. Seperti pengujian, ini adalah proses terbuka, tanpa titik henti yang jelas, dan seseorang hanya dapat menambahkan properti sebanyak mungkin dalam kerangka waktu yang tersedia. Selain itu, saat pengembang mengubah kode saat sedang diverifikasi, mereka juga harus memperbarui spesifikasi yang ada, yang mengarah ke upaya pemeliharaan ekstra. Faktor-faktor ini dapat membuat verifikasi formal menjadi tugas yang menakutkan bagi beberapa pengembang yang ragu-ragu untuk melakukan biaya tambahan.

Dan meskipun pengujian dan verifikasi formal dapat meningkatkan kualitas kode saat digunakan bersama, keduanya memerlukan (terkadang mirip) deskripsi perilaku yang diharapkan dari program dalam bahasa dan format yang berbeda. Menulis dan mempertahankan deskripsi ini padat karya, dan mempertahankan dua bentuk berbeda dari deskripsi yang sama dapat terasa seperti upaya yang digandakan. Ini menimbulkan pertanyaan berikut: Apakah mungkin untuk menggambarkan perilaku yang diharapkan dengan cara yang dapat digunakan pengembang untuk pengujian dan verifikasi?

Menjembatani kesenjangan antara pengujian dan verifikasi formal dengan pengujian simbolik dan Halmos

Pengujian simbolik, praktik menjalankan pengujian dengan input simbolik, adalah metode verifikasi formal yang efektif yang mengurangi overhead spesifikasi. Pendekatan ini memungkinkan penggunaan kasus uji yang sama untuk pengujian dan verifikasi formal. Tidak seperti pengujian tradisional, yang memverifikasi bahwa suatu program bekerja dengan benar untuk sekumpulan input terbatas, pengujian simbolik memeriksa program untuk semua kemungkinan input, sehingga program yang lolos pengujian simbolik dapat dianggap diverifikasi secara formal.

Halmos adalah alat verifikasi formal yang dirancang untuk pengujian simbolik. Alih-alih membutuhkan spesifikasi terpisah atau mempelajari bahasa baru, Halmos menggunakan tes yang ada sebagai spesifikasi formal. Menjalankan tes melalui Halmos akan secara otomatis memverifikasi bahwa mereka lulus untuk semua masukan yang mungkin, atau memberikan contoh tandingan. Hal ini tidak hanya menghilangkan kebutuhan akan penulisan spesifikasi tambahan, tetapi juga memungkinkan penggunaan ulang pengujian yang ditulis untuk pengujian unit atau fuzzing, untuk tujuan verifikasi formal.

Dengan demikian, pengembang memiliki fleksibilitas yang lebih besar untuk memilih dari serangkaian opsi jaminan kualitas, termasuk pengujian unit, fuzzing, dan verifikasi formal, bergantung pada kebutuhan mereka saat ini. Misalnya, tes dapat dengan cepat mengidentifikasi kesalahan sederhana, mungkin dengan bantuan fuzzer yang menghasilkan input acak, dan kemudian Halmos dapat lebih meningkatkan kepercayaan pada kebenaran program di semua input.

Contoh: Menguji isPowerOfTwo() fungsi

Sebagai contoh, perhatikan hal berikut isPowerOfTwo() fungsi, yang menentukan apakah nomor yang diberikan adalah kekuatan dua. Fungsi ini menggunakan a algoritma manipulasi bit untuk efisiensi, tetapi dapat menjadi tantangan untuk membuktikan kebenarannya, terutama dalam kasus di mana inputnya bukan pangkat dua.

Bayangkan tes berikut untuk isPowerOfTwo() fungsi: ini membandingkan output sebenarnya dari fungsi dengan output yang diharapkan untuk input yang diberikan. Ini adalah pengujian berparameter (juga dikenal sebagai pengujian berbasis properti), artinya Anda dapat dengan mudah menjalankannya dengan nilai input yang berbeda, mungkin dengan alat fuzzing seperti Foundry.

Anda dapat menggunakan tes ini untuk memeriksa isPowerOfTwo() berfungsi melalui pengujian unit atau pengujian fuzz, menjalankannya dengan pilihan input. Tes seperti ini tidak dapat secara formal membuktikan kebenaran fungsi, karena secara komputasional tidak layak untuk menjalankan tes untuk setiap masukan yang mungkin.

Halmos, bagaimanapun, memungkinkan pengembang untuk menggunakan kembali tes yang sudah ada ini untuk verifikasi formal hanya dengan sedikit usaha ekstra. Alat ini memeriksa bahwa pengujian lulus untuk semua input yang mungkin dengan melakukan eksekusi simbolis dari pengujian dan kemudian memverifikasi bahwa pernyataan tidak pernah dilanggar, (atau, jika pernyataan is dilanggar, dengan memberikan contoh tandingan). Ini berarti bahwa jika tes melewati Halmos, kebenaran fungsi diverifikasi secara formal, artinya algoritma diimplementasikan dengan benar dan telah diterjemahkan secara akurat oleh kompiler ke dalam bytecode.

Batasan: Eksekusi simbolik terbatas

Secara umum tidak mungkin untuk melakukan pengujian simbolis yang lengkap dan sepenuhnya otomatis, karena ini akan memerlukan penyelesaian menghentikan masalah, yang diketahui tidak dapat diputuskan. Salah satu alasannya adalah seringkali tidak mungkin untuk menentukan secara otomatis berapa kali sebuah loop harus diulang secara simbolis. Akibatnya, verifikasi formal yang sepenuhnya otomatis umumnya tidak dapat diputuskan.

Mengingat keterbatasan mendasar ini, Halmos memprioritaskan otomatisasi daripada kelengkapan. Untuk tujuan ini, Halmos dirancang untuk melakukan penalaran simbolik terbatas untuk loop tak terbatas (di mana jumlah iterasi bergantung pada input program) atau array dengan panjang variabel (termasuk string). Ini mengorbankan beberapa kelengkapan, tetapi memungkinkan Halmos menghindari keharusan pengguna memberikan anotasi tambahan seperti invarian loop.

Sebagai contoh, pertimbangkan versi iteratif berikut dari isPowerOfTwo() fungsi, yang menampilkan while loop tanpa batas, di mana jumlah iterasi loop ditentukan oleh jumlah minimum bit yang diperlukan untuk mewakili nomor input.

Halmos secara simbolis mengiterasi perulangan tak terbatas ini hanya sampai batas tertentu. Misalnya, jika batas diatur ke 3, Halmos akan mengulangi loop paling banyak 3 kali dan tidak akan mempertimbangkan nilai input yang akan menyebabkan loop mengulang lebih dari 3 kali (yaitu, nilai apa pun yang lebih besar dari atau sama dengan 2^3 ). Dalam kasus khusus ini, menetapkan batas ke 256 atau lebih tinggi akan memungkinkan Halmos menjadi lengkap.

Demo: Verifikasi formal ERC721A dengan Halmos

Untuk mendemonstrasikan kemampuan Halmos, kami menggunakannya untuk menguji secara simbolis dan memverifikasi secara formal ERC721A, implementasi standar ERC721 yang sangat dioptimalkan untuk gas yang memungkinkan pencetakan batch dengan biaya yang hampir sama dengan pencetakan tunggal. ERC721A mencakup beberapa inovasi optimisasi untuk mencapai efisiensi ini; misalnya, gas dapat dihemat dengan menunda pembaruan data kepemilikan token hingga token ditransfer, bukan pada saat pencetakan. Ini memerlukan penggunaan struktur data dan algoritme yang kompleks untuk mengambil informasi kepemilikan secara efisien dari struktur data yang malas. Dan meskipun pengoptimalan ini meningkatkan efisiensi gas, pengoptimalan ini juga meningkatkan kerumitan kode dan menyulitkan untuk membuktikan kebenaran penerapannya. Hal ini menjadikan ERC721A kandidat yang baik untuk verifikasi formal, karena dapat meningkatkan kepercayaan dalam implementasi dan menguntungkan pengguna potensial.

Properti pengujian simbolik

Karena pengujian yang ada untuk ERC721A ditulis dalam JavaScript dengan Hardhat (yang saat ini tidak didukung oleh Halmos), kami menulis pengujian baru dalam Soliditas untuk fungsi titik masuk utama: mint(), burn(), dan transfer(). Pengujian ini memeriksa apakah setiap fungsi memperbarui kepemilikan dan saldo token dengan benar, dan hanya memengaruhi pengguna yang relevan tanpa mengubah saldo atau kepemilikan pengguna lain. Yang terakhir adalah non-sepele untuk dibuktikan karena penggunaan algoritma struktur data yang malas di ERC721A. Sebagai contoh, tes berikut memeriksa bahwa transfer() fungsi dengan benar memperbarui kepemilikan token yang ditentukan:

Tes lain memeriksa bahwa transfer() fungsi tidak mengubah keseimbangan untuk alamat lain, yang sulit dibuktikan seperti yang disebutkan sebelumnya:

Hasil verifikasi

Kami melakukan percobaan verifikasi menggunakan Halmos pada kontrak pintar ERC721A dengan menulis total Tes 19. Tes dijalankan melalui Halmos dengan loop unrolling bound 3, yang membutuhkan waktu 16 menit untuk menyelesaikannya. Rincian waktu verifikasi dapat dilihat pada tabel di bawah ini. Eksperimen dilakukan pada MacBook Pro dengan chip M1 Pro dan memori 16 GB.

uji	Waktu)
tesBurnBalanceUpdate	6.67
testBurnNextTokenIdTidak berubah	1.40
testBurnOtherBalancePreservation	5.69
testBurnOtherOwnershipPreservation	189.70
tesBurnOwnershipUpdate	3.81
persyaratan testBurn	71.95
tesMintBalanceUpdate	0.20
tesMintNextTokenIdUpdate	0.18
testMintOtherBalancePreservation	0.26
testMintOtherOwnershipPreservation	5.74
tesMintOwnershipUpdate	1.38
persyaratan testMint	0.09
testTransferBalanceTidak berubah	9.03
tesTransferBalanceUpdate	53.53
testTransferNextTokenIdTidak berubah	4.47
testTransferOtherBalancePreservasi	19.57
testTransferOtherOwnershipPreservation	430.61
testTransferOwnershipUpdate	18.71
ujiTransferPersyaratan	149.18

Sementara sebagian besar tes diselesaikan dalam hitungan detik, beberapa di antaranya membutuhkan waktu beberapa menit. Tes yang memakan waktu ini sulit untuk diverifikasi karena sifat kompleks dari kasus yang harus dipertimbangkan, dan terkait erat dengan kebenaran algoritme struktur data yang lambat.

Secara keseluruhan, hasil percobaan ini menunjukkan bahwa Halmos mampu memverifikasi kebenaran kode kontrak pintar secara efektif. Ini memberikan peningkatan kepercayaan pada integritas kode, terlepas dari kerumitan dan potensi kasus edge dari smart contract.

Bereksperimenlah dengan bug yang disuntikkan

Untuk mendemonstrasikan keefektifan penalaran terbatas Halmos, kami menggunakannya untuk mendeteksi bug di kontrak ERC721A versi sebelumnya. Versi ini memiliki masalah yang salah menangani luapan aritmatika dan berpotensi memungkinkan pencetakan batch sejumlah besar token, yang dapat merusak integritas struktur data yang lambat dan mengakibatkan beberapa pengguna kehilangan kepemilikan token mereka (masalah diselesaikan dalam versi saat ini). Kami menjalankan rangkaian 19 pengujian yang sama untuk ERC721A pada versi buggy, dan Halmos dapat menemukan contoh tandingan untuk properti dari mint() fungsi. Secara khusus, Halmos memberikan nilai masukan yang mengarah ke skenario eksploit yang dijelaskan di atas. Hasil percobaan ini menunjukkan bahwa, meskipun tidak lengkap, penalaran terbatas Halmos dapat menjadi cara yang efektif untuk mendeteksi dan mencegah bug yang dapat dieksploitasi dalam kontrak pintar.

Pekerjaan yang berhubungan

Alat verifikasi formal untuk bytecode kontrak cerdas Ethereum telah dikembangkan oleh berbagai tim. Alat-alat ini, termasuk Halmos, dapat digunakan untuk membantu memastikan keamanan dan kebenaran kontrak pintar. Membandingkan dan memahami berbagai fitur, kemampuan, dan batasan alat ini dapat membantu pengembang memilih alat yang paling tepat untuk kebutuhan unik mereka.

Sementara Halmos adalah tambahan berharga untuk perangkat yang tersedia untuk verifikasi kontrak pintar, ini dimaksudkan untuk melengkapi (bukan menggantikan) alat yang ada. Pengembang dapat menggabungkan Halmos dengan alat lain untuk mencapai tingkat jaminan yang lebih tinggi dalam kontrak mereka. Di bawah ini, kami membandingkan Halmos dengan beberapa alat formal terpilih yang mendukung bytecode EVM.

• K adalah kerangka verifikasi formal yang kuat yang memungkinkan verifikasi deduktif dan pembuktian teorema interaktif. Teori dan implementasinya yang mendasari memberikan tingkat ekspresi yang tinggi, sehingga cocok untuk memverifikasi program dan algoritme yang kompleks. Namun, perlu dicatat bahwa K tidak dirancang dengan penekanan berat pada verifikasi otomatis dan tidak memiliki fitur otomatisasi tertentu yang mungkin memerlukan lebih banyak upaya manual selama proses verifikasi. Untuk menggunakan framework K, spesifikasi formal ditulis dalam bahasa K, yang harus dipelajari sebelum digunakan. Kekuatannya sangat berguna dalam memverifikasi sistem yang kompleks, yang mungkin menantang untuk dianalisis menggunakan penalaran otomatis.
• Certora adalah alat verifikasi formal untuk kontrak pintar yang berfokus pada verifikasi otomatis dan mendukung pemeriksaan model terbatas, mirip dengan Halmos. Untuk menggunakan Certora, pengembang harus mempelajari bahasa baru mereka, CVL, untuk menulis spesifikasi. Bahasa ini memungkinkan deskripsi singkat dari banyak properti kritis melalui invarian kontrak, fitur yang saat ini tidak didukung oleh Halmos. Meskipun merupakan alat tertutup dan berpemilik, Certora menyediakan alat verifikasi formal yang tangguh, dengan pengembangan berkelanjutan dan dukungan pengguna yang baik.
  
  Halmos, di sisi lain, adalah alat sumber terbuka yang skalanya lebih kecil dan saat ini tidak memiliki beberapa fitur yang disediakan oleh Certora, tetapi dimaksudkan untuk berfungsi sebagai barang publik dan dimaksudkan sebagai solusi khusus untuk memverifikasi kontrak pintar dengan cepat tanpa kebutuhan untuk pengaturan dan pemeliharaan yang ekstensif.
• HEVM adalah alat verifikasi formal lain yang mirip dengan Halmos. Itu sebelumnya bagian dari DappTools, yang merupakan pendahulu dari Foundry. Baik HEVM dan Halmos memiliki fitur yang tidak memerlukan spesifikasi terpisah dan secara simbolis dapat menjalankan pengujian yang ada untuk mengidentifikasi pelanggaran pernyataan. Hal ini memungkinkan pengguna untuk menggunakan kedua alat secara bergantian atau menjalankannya secara paralel untuk pengujian yang sama, memberi mereka beberapa opsi untuk pengujian simbolik.
  
  Perlu dicatat bahwa, terlepas dari kesamaannya, HEVM dan Halmos telah dikembangkan secara independen dan berbeda dalam detail implementasinya; khususnya dalam hal optimasi dan strategi penalaran simbolik. Selain itu, HEVM ditulis dalam Haskell, sementara Halmos ditulis dalam Python, memberikan paparan ekosistem Python yang kaya. Memiliki kemampuan untuk menggunakan kedua alat tersebut memberi pengguna lebih banyak fleksibilitas dan opsi untuk memastikan keamanan dan kebenaran kontrak cerdas.

Halmos adalah open source, dan saat ini dalam fase beta. Kami secara aktif mengerjakan yang baru fitur dan fungsionalitas, termasuk kode cheat Foundry dan beberapa fitur kegunaan utama lainnya. Kami akan sangat menghargai pemikiran Anda tentang fitur mana yang paling penting, dan menyambut setiap umpan balik, saran, dan kontribusi untuk menjadikan Halmos alat yang lebih baik bagi semua orang.

**

Pandangan yang diungkapkan di sini adalah pandangan individu AH Capital Management, LLC (“a16z”) yang dikutip dan bukan pandangan a16z atau afiliasinya. Informasi tertentu yang terkandung di sini telah diperoleh dari sumber pihak ketiga, termasuk dari perusahaan portofolio dana yang dikelola oleh a16z. Meskipun diambil dari sumber yang dipercaya dapat dipercaya, a16z belum memverifikasi informasi tersebut secara independen dan tidak membuat pernyataan tentang keakuratan informasi saat ini atau yang bertahan lama atau kesesuaiannya untuk situasi tertentu. Selain itu, konten ini mungkin termasuk iklan pihak ketiga; a16z belum meninjau iklan tersebut dan tidak mendukung konten iklan apa pun yang terkandung di dalamnya.

Konten ini disediakan untuk tujuan informasi saja, dan tidak boleh diandalkan sebagai nasihat hukum, bisnis, investasi, atau pajak. Anda harus berkonsultasi dengan penasihat Anda sendiri mengenai hal-hal itu. Referensi ke sekuritas atau aset digital apa pun hanya untuk tujuan ilustrasi, dan bukan merupakan rekomendasi investasi atau penawaran untuk menyediakan layanan konsultasi investasi. Selanjutnya, konten ini tidak ditujukan atau dimaksudkan untuk digunakan oleh investor atau calon investor mana pun, dan dalam keadaan apa pun tidak dapat diandalkan saat membuat keputusan untuk berinvestasi dalam dana yang dikelola oleh a16z. (Penawaran untuk berinvestasi dalam dana a16z hanya akan dilakukan dengan memorandum penempatan pribadi, perjanjian berlangganan, dan dokumentasi lain yang relevan dari dana tersebut dan harus dibaca secara keseluruhan.) Setiap investasi atau perusahaan portofolio yang disebutkan, dirujuk, atau dijelaskan tidak mewakili semua investasi dalam kendaraan yang dikelola oleh a16z, dan tidak ada jaminan bahwa investasi tersebut akan menguntungkan atau bahwa investasi lain yang dilakukan di masa depan akan memiliki karakteristik atau hasil yang serupa. Daftar investasi yang dilakukan oleh dana yang dikelola oleh Andreessen Horowitz (tidak termasuk investasi yang penerbitnya tidak memberikan izin kepada a16z untuk mengungkapkan secara publik serta investasi yang tidak diumumkan dalam aset digital yang diperdagangkan secara publik) tersedia di https://a16z.com/investments /.

Bagan dan grafik yang disediakan di dalamnya hanya untuk tujuan informasi dan tidak boleh diandalkan saat membuat keputusan investasi apa pun. Kinerja masa lalu tidak menunjukkan hasil di masa depan. Konten berbicara hanya pada tanggal yang ditunjukkan. Setiap proyeksi, perkiraan, prakiraan, target, prospek, dan/atau pendapat yang diungkapkan dalam materi ini dapat berubah tanpa pemberitahuan dan mungkin berbeda atau bertentangan dengan pendapat yang diungkapkan oleh orang lain. Silakan lihat https://a16z.com/disclosures untuk informasi penting tambahan.