crab

Kepiting: Perpustakaan C ++ untuk Analisis Statis Program Membangun

Kepiting adalah perpustakaan C ++ untuk membangun analisis statis program berdasarkan interpretasi abstrak. Kepiting menyediakan serangkaian domain abstrak yang kaya, pemecah fixpoint berbasis Kleene, serta analisis yang berbeda seperti DataFlow, antar-prosedural dan mundur. Desain kepiting cukup modular sehingga mudah untuk plugin domain dan pemecah abstrak baru atau membangun analisis baru.

Domain Abstrak Kepiting dapat beralasan tentang isi memori, array seperti C dan sifat numerik. Kepiting menggunakan implementasi yang efisien dari domain numerik populer seperti zona dan oktagon dan domain baru untuk bernalar, misalnya, tentang istilah simbolik (alias fungsi yang tidak diinterpretasikan). Kepiting juga mengimplementasikan domain non-relasional yang populer seperti interval atau kongruensi menggunakan peta lingkungan yang efisien, dan memungkinkan kombinasi domain sewenang-wenang melalui konstruksi produk yang berkurang. Kepiting juga menyediakan domain non-cembung seperti interval disjungtif khusus yang disebut kotak berdasarkan diagram keputusan linier dan strategi partisi nilai yang lebih umum yang mengangkat domain sewenang-wenang ke keterlambatan yang berlebihan dari penyelesaian disjungsi. Selain domain ini, semua dikembangkan oleh penulis kepiting, perpustakaan kepiting mengintegrasikan perpustakaan domain abstrak yang populer seperti apron, elina, dan pplite.

Kepiting menyediakan pemecah Fixpoint Interleaved yang canggih yang menggunakan pemesanan topologi lemah Bourdoncle untuk memilih himpunan titik pelebaran. Untuk mengurangi kerugian presisi selama pelebaran, kepiting mengimplementasikan beberapa teknik populer seperti pelebaran dengan ambang batas dan pelebaran lookahead.

Kepiting menyediakan dua implementasi analisis antar-prosedural yang berbeda: top-down dengan analisis antar-prosedural memoisasi dengan dukungan untuk panggilan rekursif, dan hibrida analisis bottom-up + top down. Terakhir, kepiting juga mengimplementasikan analisis terbelakang yang lebih eksperimental yang dapat digunakan untuk menghitung prasyarat yang diperlukan dan/atau mengurangi jumlah alarm palsu.

Kepiting tidak menganalisis secara langsung bahasa pemrograman utama tetapi sebaliknya ia menganalisis representasi perantara berbasis CFG sendiri yang disebut Crabir. Crabir adalah kode tiga alamat dan sangat diketik. Dalam Crabir, aliran kontrol didefinisikan melalui instruksi GOTO non-deterministik. Terlepas dari operasi boolean dan aritmatika standar, Crabir memberikan pernyataan khusus dan menegaskan pernyataan. Yang pertama dapat digunakan untuk memperbaiki aliran kontrol dan yang terakhir menyediakan mekanishm sederhana untuk memeriksa properti yang ditentukan pengguna. Terlepas dari desainnya yang sederhana, Crabir cukup kaya untuk mewakili bahasa seperti LLVM.

Kepiting aktif dalam pengembangan. Jika Anda menemukan bug, buka masalah github. Permintaan tarik dengan fitur baru sangat disambut. Dokumentasi yang tersedia dapat ditemukan di wiki kami. Jika Anda menggunakan perpustakaan ini, silakan mengutip kertas ini.

Windows	Ubuntu	OS X.	Cakupan
Tbd		Tbd

Buruh pelabuhan

Versi kepiting pra-dibangun (malam) yang menjalankan semua tes dapat diperoleh dengan menggunakan Docker:

docker pull seahorn/crab:bionic
docker run -v ` pwd ` :/host -it seahorn/crab:bionic

Persyaratan

Kepiting ditulis dalam C ++ dan bergantung pada perpustakaan Boost. Persyaratan utamanya adalah:

• Kompiler C ++ 11
• Boost> = 1.65
• GMP
• Mpfr (if -DCRAB_USE_APRON=ON atau -DCRAB_USE_ELINA=ON )
• Flint (hanya jika -DCRAB_USE_PPLITE=ON )

Di Linux, Anda dapat menginstal persyaratan yang mengetik perintah:

 sudo apt-get install libboost-all-dev libboost-program-options-dev
sudo apt-get install libgmp-dev
sudo apt-get install libmpfr-dev	
sudo apt-get install libflint-dev

Kompilasi dan Instalasi

Untuk memasang kepiting, ketik:

 1. mkdir build && cd build
 2. cmake -DCMAKE_INSTALL_PREFIX=$INSTALL_DIR ../
 3. cmake --build . --target install 

Direktori tests berisi banyak contoh cara membangun program yang ditulis dalam crabir dan menghitung invarian menggunakan analisis dan domain abstrak yang berbeda. Untuk mengkompilasi tes ini tambahkan opsi -DCRAB_ENABLE_TESTS=ON to line 2.

Dan kemudian, misalnya, untuk menjalankan test1 :

 build/test-bin/test1

Sertakan perpustakaan domain abstrak pihak ketiga

Domain kotak/celemek/elina/pplite memerlukan perpustakaan pihak ketiga. Untuk menghindari beban bagi pengguna yang tidak tertarik pada domain tersebut, pemasangan perpustakaan adalah opsional.

• Jika Anda ingin menggunakan domain Boxes maka tambahkan -DCRAB_USE_LDD=ON Opsi.

• Jika Anda ingin menggunakan domain pustaka apron maka tambahkan -DCRAB_USE_APRON=ON opsi.

• Jika Anda ingin menggunakan Domain Perpustakaan Elina maka tambahkan -DCRAB_USE_ELINA=ON Opsi.

• Jika Anda ingin menggunakan domain pustaka pplite maka tambahkan -DCRAB_USE_PPLITE=ON option.

Penting: Apron dan Elina saat ini tidak kompatibel sehingga Anda tidak dapat mengaktifkan -DCRAB_USE_APRON=ON dan -DCRAB_USE_ELINA=ON pada saat yang sama.

Misalnya, untuk menginstal kepiting dengan kotak dan celemek, ketik:

 1. mkdir build && cd build
 2. cmake -DCMAKE_INSTALL_PREFIX=$INSTALL_DIR -DCRAB_USE_LDD=ON -DCRAB_USE_APRON=ON ../
 3. cmake --build . --target ldd && cmake ..
 4. cmake --build . --target apron && cmake ..	
 5. cmake --build . --target install 	

Baris 3 dan 4 masing -masing akan mengunduh, menyusun, dan menginstal kotak dan domain apron. Ganti apron di baris 4 dengan elina atau pplite jika Anda ingin menggunakan Elina atau pplite sebagai gantinya. Jika Anda telah menyusun dan menginstal perpustakaan ini di mesin Anda, lalu lewati perintah di baris 3 dan 4 dan tambahkan opsi berikut di baris 2.

• Untuk apron: -DAPRON_ROOT=$APRON_INSTALL_DIR
• Untuk elina: -DELINA_ROOT=$ELINA_INSTALL_DIR
• Untuk kotak: -DCUDD_ROOT=$CUDD_INSTALL_DIR -DLDD_ROOT=$LDD_INSTALL_DIR
• Untuk pplite: -DPPLITE_ROOT=$PPLITE_INSTALL_DIR -DFLINT_ROOT=$FLINT_INSTALL_DIR

Menggunakan perpustakaan kepiting di proyek C ++ lainnya

Untuk memasukkan kepiting ke dalam aplikasi C ++ Anda yang Anda butuhkan:

• Sertakan file header C ++ yang terletak di $INSTALL_DIR/crab/include , dan

• Tautkan aplikasi Anda dengan pustaka kepiting yang diinstal dalam $INSTALL_DIR/crab/lib .

Jika Anda mengkompilasi dengan kotak/apron/elina/pplite, Anda juga perlu menyertakan $INSTALL_DIR/EXT/include dan tautan dengan $INSTALL_DIR/EXT/lib di mana EXT=apron|elina|ldd|pplite .

Cmake

Jika proyek Anda menggunakan cmake maka Anda hanya perlu menambahkan CMakeLists.txt proyek Anda.

 add_subdirectory(crab)
include_directories(${CRAB_INCLUDE_DIRS})

Dan kemudian tautkan executable Anda dengan ${CRAB_LIBS}

Membuat

Jika proyek Anda menggunakan make , baca sampel ini Makefile.