crab

Crab: une bibliothèque C ++ pour la construction du programme Analyses statiques

Le crabe est une bibliothèque C ++ pour la construction d'analyses statiques du programme basées sur l'interprétation abstraite. Le crabe fournit un ensemble riche de domaines abstraits, des résolveurs de point de fixation basés sur Kleene, ainsi que des analyses différentes telles que Dataflow, inter-procédurale et arriérée. La conception du crabe est assez modulaire afin qu'il soit facile de plumer de nouveaux domaines et résolveurs abstraits ou de créer de nouvelles analyses.

Les domaines abstraits du crabe peuvent raisonner sur le contenu de la mémoire, les tableaux de type C et les propriétés numériques. Le crabe utilise des implémentations efficaces de domaines numériques populaires tels que les zones et les octagones et les nouveaux domaines pour raisonner, par exemple, sur des termes symboliques (aka des fonctions non interprétées). Le crabe met également en œuvre des domaines non relationnels populaires tels que l'intervalle ou les congruences à l'aide de cartes environnementales efficaces, et permet la combinaison de domaines arbitraires via des constructions de produits réduites standard. Le crabe fournit également des domaines non convexes tels que des intervalles disjonctifs spécialisés appelés boîtes basées sur des diagrammes de décision linéaires et une stratégie de partitionnement de valeur plus générale qui soulève un domaine arbitraire à une excession excessive de son achèvement de disjonction. En plus de ces domaines, tous développés par des auteurs de crabe, la bibliothèque de crabe intègre des bibliothèques de domaine abstraites populaires telles que Apron, Elina et Pplite.

Le crabe fournit le solveur FixPoint entrelacé de pointe qui utilise la faible commande topologique de Bourdconcle pour sélectionner l'ensemble des points d'élargissement. Pour atténuer les pertes de précision pendant l'élargissement, le crabe met en œuvre certaines techniques populaires telles que l'élargissement avec des seuils et l'élargissement de lookahead.

Le crabe fournit deux implémentations différentes d'analyses interprocédurales: une analyse interprocédurale descendante descendante avec un support pour les appels récursifs, et un hybride d'analyse ascendante + top down. Enfin et surtout, le crabe met également en œuvre une analyse vers l'arrière plus expérimentale qui peut être utilisée pour calculer les conditions préalables nécessaires et / ou réduire le nombre de fausses alarmes.

Le crabe n'analyse pas directement un langage de programmation grand public, mais il analyse à la place sa propre représentation intermédiaire basée sur CFG appelée Crabir. Le crabir est du code à trois adhésions et il est fortement dactylographié. Dans le crabir, le flux de contrôle est défini via des instructions GOTO non déterministes. Outre les opérations booléennes et arithmétiques standard, Crabir fournit des déclarations spéciales de suppression et d'affirmer. Le premier peut être utilisé pour affiner le flux de contrôle et le second fournit un mécanisme simple pour vérifier les propriétés définies par l'utilisateur. Malgré sa conception simple, le crabir est assez riche pour représenter des langues telles que LLVM.

Le crabe est activement en cours de développement. Si vous trouvez un bug, veuillez ouvrir un problème GitHub. Les demandes de traction avec de nouvelles fonctionnalités sont les bienvenues. La documentation disponible se trouve dans notre wiki. Si vous utilisez cette bibliothèque, veuillez citer ce document.

Fenêtre	Ubuntu	OS X	Couverture
TBD		TBD

Docker

Une version (nocturne) prédéfinie du crabe qui exécute tous les tests peut être obtenue à l'aide de Docker:

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

Exigences

Le crabe est écrit en C ++ et s'appuie sur la bibliothèque Boost. Les principales exigences sont:

• Compilateur C ++ 11
• Boost> = 1,65
• GMP
• Mpfr (if -DCRAB_USE_APRON=ON ou -DCRAB_USE_ELINA=ON )
• Flint (seulement si -DCRAB_USE_PPLITE=ON )

Dans Linux, vous pouvez installer des exigences en tapant les commandes:

 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

Compilation et installation

Pour installer du crabe, tapez:

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

Le répertoire tests contient de nombreux exemples de la façon de créer des programmes écrits en crabir et de calcul des invariants en utilisant différentes analyses et domaines abstraits. Pour compiler ces tests, ajoutez l'option -DCRAB_ENABLE_TESTS=ON la ligne 2.

Et puis, par exemple, pour exécuter test1 :

 build/test-bin/test1

Inclure des bibliothèques de domaines abstraites tierces

Les domaines des boîtes / tabliers / elina / pplite nécessitent des bibliothèques tierces. Pour éviter le fardeau pour les utilisateurs qui ne sont pas intéressés par ces domaines, l'installation des bibliothèques est facultative.

• Si vous souhaitez utiliser le domaine des boîtes, ajoutez -DCRAB_USE_LDD=ON l'option.

• Si vous souhaitez utiliser les domaines de la bibliothèque de tabliers, ajoutez -DCRAB_USE_APRON=ON l'option.

• Si vous souhaitez utiliser les domaines de la bibliothèque Elina, ajoutez -DCRAB_USE_ELINA=ON l'option.

• Si vous souhaitez utiliser les domaines de la bibliothèque PPLITE, ajoutez -DCRAB_USE_PPLITE=ON l'option.

Important: Apron et Elina ne sont actuellement pas compatibles, vous ne pouvez donc pas activer -DCRAB_USE_APRON=ON et -DCRAB_USE_ELINA=ON en même temps.

Par exemple, pour installer du crabe avec des boîtes et un tablier, type:

 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 	

Les lignes 3 et 4 téléchargeront, compileront et installeront respectivement les boîtes et les domaines du tablier. Remplacez apron à la ligne 4 par elina ou pplite si vous souhaitez utiliser Elina ou Pplite à la place. Si vous avez déjà compilé et installé ces bibliothèques dans votre machine, sautez les commandes aux lignes 3 et 4 et ajoutez les options suivantes à la ligne 2.

• Pour tablier: -DAPRON_ROOT=$APRON_INSTALL_DIR
• Pour Elina: -DELINA_ROOT=$ELINA_INSTALL_DIR
• Pour les boîtes: -DCUDD_ROOT=$CUDD_INSTALL_DIR -DLDD_ROOT=$LDD_INSTALL_DIR
• Pour pplite: -DPPLITE_ROOT=$PPLITE_INSTALL_DIR -DFLINT_ROOT=$FLINT_INSTALL_DIR

Utilisation de la bibliothèque de crabe dans d'autres projets C ++

Pour inclure le crabe dans votre application C ++, vous devez:

• Inclure les fichiers d'en-tête C ++ situés sur $INSTALL_DIR/crab/include , et

• Reliez votre application avec les bibliothèques de crabe installées dans $INSTALL_DIR/crab/lib .

Si vous compilez avec des boîtes / tabliers / elina / pplite, vous devez également inclure $INSTALL_DIR/EXT/include et lier avec $INSTALL_DIR/EXT/lib où EXT=apron|elina|ldd|pplite .

Cmake

Si votre projet utilise cmake , il vous suffit d'ajouter CMakeLists.txt de votre projet:

 add_subdirectory(crab)
include_directories(${CRAB_INCLUDE_DIRS})

Puis liez votre exécutable avec ${CRAB_LIBS}

Faire

Si votre projet utilise make , lisez cet échantillon de Makefile.