sea dsa
1.0.0
SeaDsa adalah titik poin berbasis unifikasi konteks, lapangan, dan array-sensitif untuk analisis untuk kode bitcode LLVM yang terinspirasi oleh DSA. SeaDsa adalah urutan besarnya lebih terukur dan tepat daripada Dsa dan implementasi SeaDsa sebelumnya berkat peningkatan penanganan sensitivitas konteks, penambahan sensitivitas aliran parsial, dan jenis kesadaran.
Meskipun SeaDsa dapat menganalisis bitcode LLVM sewenang -wenang, itu telah dirancang untuk digunakan dalam verifikasi program program C/C ++. Ini dapat digunakan sebagai alat yang berdiri sendiri atau bersama-sama dengan kerangka kerja verifikasi Seahorn dan analisisnya.
Cabang ini mendukung LLVM 14.
SeaDsa ditulis dalam C ++ dan menggunakan pustaka Boost. Persyaratan utamanya adalah:
Untuk menjalankan tes, instal paket berikut:
sudo pip install lit OutputChecksudo easy_install networkxsudo apt-get install libgraphviz-devsudo easy_install pygraphvizGraph , Cell , dan Node , didefinisikan dalam include/Graph.hh dan src/Graph.cc .include/Local.hh dan src/DsaLocal.cc .include/BottomUp.hh dan src/DsaBottomUp.cc .include/TopDown.hh dan src/DsaTopDown.cc .include/Cloner.hh dan src/Clonner.cc .include/FieldType.hh , include/TypeUtils.hh , src/FieldType.cc , dan src/TypeUtils.cc .include/AllocWrapInfo.hh dan src/AllocWrapInfo.cc . Instruksi tentang menjalankan tolok ukur verifikasi program, bersama dengan resep untuk membangun proyek dunia nyata dan hasil kami, dapat ditemukan di TEA-DSA-Extras.
SeaDsa berisi dua direktori: include dan src . Karena SeaDsa menganalisis LLVM Bitcode, file header LLVM dan pustaka harus dapat diakses saat membangun dengan SeaDsa .
Jika proyek Anda menggunakan cmake maka Anda hanya perlu menambahkan CMakeLists.txt proyek Anda.
include_directories(seadsa/include)
add_subdirectory(seadsa)
Jika Anda sudah menginstal llvm-14 di mesin Anda:
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX=run -DLLVM_DIR=__here_llvm-14__/share/llvm/cmake ..
cmake --build . --target install
Jika tidak:
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX=run ..
cmake --build . --target install
Untuk menjalankan tes:
cmake --build . --target test-sea-dsa
Pertimbangkan program C yang disebut tests/c/simple.c :
#include <stdlib.h>
typedef struct S {
int * * x ;
int * * y ;
} S ;
int g ;
int main ( int argc , char * * argv ){
S s1 , s2 ;
int * p1 = ( int * ) malloc ( sizeof ( int ));
int * q1 = ( int * ) malloc ( sizeof ( int ));
s1 . x = & p1 ;
s1 . y = & q1 ;
* ( s1 . x ) = & g ;
return 0 ;
} Hasilkan Bitcode:
clang -O0 -c -emit-llvm -S tests/c/simple.c -o simple.ll
Opsi -O0 digunakan untuk menonaktifkan optimisasi dentang. Secara umum, itu adalah ide yang baik untuk memungkinkan optimisasi dentang. Namun, untuk contoh sepele seperti simple.c , dentang menyederhanakan terlalu banyak sehingga tidak ada yang berguna yang akan diamati. Opsi -c -emit-llvm -S menghasilkan bitcode dalam format yang dapat dibaca manusia.
Jalankan sea-dsa pada bitcode dan cetak grafik memori ke format dot:
seadsa -sea-dsa=butd-cs -sea-dsa-type-aware -sea-dsa-dot simple.ll
Opsi -sea-dsa=butd-cs -sea-dsa-type-aware memungkinkan analisis yang diterapkan dalam makalah FMCAD'19 kami (lihat referensi). Perintah ini akan menghasilkan file FUN.mem.dot untuk setiap fungsi FUN dalam program bitcode. Dalam kasus kami, satu -satunya fungsi adalah main dan dengan demikian, ada satu file bernama main.mem.dot . File dihasilkan di direktori saat ini. Jika Anda ingin menyimpan file .dot di direktori yang berbeda DIR lalu tambahkan opsi -sea-dsa-dot-outdir=DIR
Visualisasikan main.mem.dot dengan mengubahnya menjadi file pdf :
dot -Tpdf main.mem.dot -o main.mem.pdf
open main.mem.pdf // replace with you favorite pdf viewer
Dalam model memori kami, nilai pointer diwakili oleh sel yang merupakan sepasang objek memori dan offset. Objek memori direpresentasikan sebagai node dalam grafik memori. Tepi berada di antara sel.
Setiap bidang node mewakili sel (yaitu, offset di simpul). Misalnya, bidang simpul <0,i32**> dan <8,i32**> -masing menunjuk %6 dan %15 , masing -masing adalah dua sel yang berbeda dari objek memori yang sama. Bidang <8,i32**> mewakili sel pada offset 8 pada objek memori yang sesuai dan jenisnya adalah i32** . Tepi hitam mewakili hubungan titik-ke antara sel. Mereka diberi label dengan angka yang mewakili offset di node tujuan. Tepi biru menghubungkan parameter formal fungsi dengan sel. Tepi ungu menghubungkan variabel penunjuk LLVM dengan sel. Node dapat memiliki penanda seperti S (tumpukan memori yang dialokasikan), H (heap alokasi memori), M (memori yang dimodifikasi), R (Baca memori), E (memori yang dialokasikan secara eksternal), dll. Jika sebuah node merah maka itu berarti bahwa analisis kehilangan sensitivitas bidang untuk simpul itu. Label {void} digunakan untuk menunjukkan bahwa node telah dialokasikan tetapi belum digunakan oleh program.
sea-dsa juga dapat menyelesaikan panggilan tidak langsung. Panggilan tidak langsung adalah panggilan di mana Callee tidak diketahui secara statis. sea-dsa mengidentifikasi semua kemungkinan calle dari panggilan tidak langsung dan menghasilkan grafik panggilan LLVM sebagai output.
Pertimbangkan contoh ini dalam tests/c/complete_callgraph_5.c :
struct class_t ;
typedef int ( * FN_PTR )( struct class_t * , int );
typedef struct class_t {
FN_PTR m_foo ;
FN_PTR m_bar ;
} class_t ;
int foo ( class_t * self , int x )
{
if ( x > 10 ) {
return self -> m_bar ( self , x + 1 );
} else
return x ;
}
int bar ( class_t * self , int y ) {
if ( y < 100 ) {
return y + self -> m_foo ( self , 10 );
} else
return y - 5 ;
}
int main ( void ) {
class_t obj ;
obj . m_foo = & foo ;
obj . m_bar = & bar ;
int res ;
res = obj . m_foo ( & obj , 42 );
return 0 ;
}Ketik perintah:
clang -c -emit-llvm -S tests/c/complete_callgraph_5.c -o ex.ll
sea-dsa --sea-dsa-callgraph-dot ex.ll
Ini menghasilkan file .dot yang disebut callgraph.dot di direktori saat ini. Sekali lagi, file .dot dapat dikonversi ke file .pdf dan dibuka dengan perintah:
dot -Tpdf callgraph.dot -o callgraph.pdf
open callgraph.pdf
sea-dsa juga dapat mencetak beberapa statistik tentang proses resolusi grafik panggilan (perhatikan bahwa Anda perlu memanggil clang dengan -g untuk mencetak informasi file, baris, dan kolom):
sea-dsa --sea-dsa-callgraph-stats ex.ll
=== Sea-Dsa CallGraph Statistics ===
** Total number of indirect calls 0
** Total number of resolved indirect calls 3
%16 = call i32 %12(%struct.class_t* %13, i32 %15) at tests/c/complete_callgraph_5.c:14:12
RESOLVED
Callees:
i32 bar(%struct.class_t*,i32)
%15 = call i32 %13(%struct.class_t* %14, i32 10) at tests/c/complete_callgraph_5.c:23:16
RESOLVED
Callees:
i32 foo(%struct.class_t*,i32)
%11 = call i32 %10(%struct.class_t* %2, i32 42) at tests/c/complete_callgraph_5.c:36:9
RESOLVED
Callees:
i32 foo(%struct.class_t*,i32)
Semantik pointer dari panggilan eksternal dapat ditentukan dengan menulis pembungkus yang memanggil salah satu fungsi ini yang didefinisikan dalam seadsa/seadsa.h :
extern void seadsa_alias(const void *p, ...);extern void seadsa_collapse(const void *p);extern void seadsa_mk_seq(const void *p, unsigned sz); seadsa_alias menyatukan semua sel argumen, seadsa_collapse memberi tahu sea-dsa untuk runtuh (yaitu, hilangnya sensitivitas lapangan) sel yang ditunjuk oleh p , dan seadsa_mk_seq mengatakan kepada sea-dsa untuk menandai urutan node yang diarahkan oleh p dengan ukuran sz .
Misalnya, pertimbangkan panggilan eksternal foo ditentukan sebagai berikut:
extern void* foo(const void*p1, void *p2, void *p3);
Misalkan penunjuk yang dikembalikan harus disatukan ke p2 tetapi tidak ke p1 . Selain itu, kami ingin runtuhnya sel yang sesuai dengan p3 . Kemudian, kita dapat mengganti prototipe foo di atas dengan definisi berikut:
#include "seadsa/seadsa.h"
void* foo(const void*p1, void *p2, void*p3) {
void* r = seadsa_new();
seadsa_alias(r,p2);
seadsa_collapse(p3);
return r;
}
"Model memori yang peka terhadap konteks untuk verifikasi program C/C ++" oleh A. Gurfinkel dan JA Navas. Di Sas'17. (Kertas) | (Slide)
"Analisis Pointer Berbasis Unifikasi Tanpa Oversharing" oleh J. Kuderski, JA Navas dan A. Gurfinkel. Di fmcad'19. (Kertas)
