L'Analyse Formelle de Code C avec Frama-C et WP: Guide Complet des Annotations ACSL
Une plongée approfondie dans la vérification formelle de programmes C pour garantir leur correction et fiabilité
Points Essentiels à Retenir
- Frama-C et WP constituent un framework puissant pour la vérification formelle de programmes C en utilisant des méthodes mathématiques rigoureuses
- Les annotations ACSL permettent de spécifier formellement le comportement attendu du code à travers des préconditions, postconditions et assertions
- La preuve déductive via WP permet de démontrer mathématiquement que le code respecte sa spécification, essentiel pour les systèmes critiques
Introduction à Frama-C et WP
Frama-C (Framework for Modular Analysis of C programs) est un outil open-source développé par le CEA et Inria pour l'analyse formelle de programmes C. Il est particulièrement utilisé dans les domaines critiques comme l'aéronautique, le nucléaire et les systèmes embarqués où la fiabilité du code est cruciale.
Le plugin WP (Weakest Precondition) est un composant essentiel de Frama-C qui permet la vérification déductive des propriétés du code. En utilisant le calcul de la plus faible précondition, WP génère des obligations de preuve à partir des annotations ACSL et tente de les prouver mathématiquement.
Qu'est-ce que ACSL?
ACSL (ANSI/ISO C Specification Language) est un langage de spécification formelle conçu pour annoter le code C. Il permet de définir des contrats pour les fonctions, incluant des préconditions, postconditions, invariants et assertions qui servent de base à la vérification formelle.
Applications pratiques
Frama-C avec WP et ACSL est utilisé dans divers contextes:
- Vérification de systèmes critiques (avionique, centrales nucléaires)
- Validation de logiciels embarqués
- Détection précoce des bugs et vulnérabilités
- Documentation formelle du comportement des fonctions
Syntaxe et Fonctions Principales d'ACSL
Les annotations ACSL sont insérées dans le code C sous forme de commentaires spéciaux. Voici les éléments fondamentaux de sa syntaxe:
Types d'Annotations
| Type d'Annotation | Syntaxe | Description |
|---|---|---|
| Précondition | /*@ requires <condition>; */ |
Condition qui doit être vraie avant l'exécution de la fonction |
| Postcondition | /*@ ensures <condition>; */ |
Condition qui doit être vraie après l'exécution de la fonction |
| Effets de bord | /*@ assigns <variables>; */ |
Liste des variables que la fonction peut modifier |
| Assertion | /*@ assert <condition>; */ |
Condition qui doit être vraie à un point précis du code |
| Invariant de boucle | /*@ loop invariant <condition>; */ |
Condition maintenue à chaque itération d'une boucle |
| Variant de boucle | /*@ loop variant <expression>; */ |
Expression qui décroît strictement pour garantir la terminaison |
Fonctions et Prédicats Spéciaux
Prédicats de validité mémoire
ACSL offre plusieurs prédicats pour raisonner sur la validité des pointeurs et la mémoire:
\valid(p): Le pointeur p est valide (peut être déréférencé)\valid_read(p): Le pointeur p est valide pour la lecture\valid(p+(0..n-1)): Tous les éléments du tableau de p[0] à p[n-1] sont valides\separated(p1, p2): Les zones mémoire pointées par p1 et p2 sont distinctes
Références spéciales
\result: Valeur de retour de la fonction\old(expr): Valeur de l'expression expr avant l'exécution de la fonction\nothing: Utilisé avec assigns pour indiquer qu'aucune variable n'est modifiée
Ce graphique radar illustre les caractéristiques des différentes constructions ACSL en termes de complexité, fréquence d'utilisation et puissance expressive. Les prédicats de mémoire sont les plus complexes mais aussi les plus expressifs, tandis que les préconditions sont les plus fréquemment utilisées.
Comment Introduire et Insérer des Annotations ACSL
Les annotations ACSL sont intégrées directement dans le code source C sous forme de commentaires spéciaux. Il existe deux formats principaux:
Formats des Annotations
- Commentaires sur une ligne: Commencent par
//@ - Commentaires multi-lignes: Commencent par
/*@et se terminent par*/
Exemple Complet d'Annotations
/*@
requires n >= 0;
ensures \result >= 0;
ensures \result * \result == n || \result * \result < n && (\result+1) * (\result+1) > n;
assigns \nothing;
*/
int sqrt_approx(int n) {
int i = 0;
/*@
loop invariant i >= 0;
loop invariant i * i <= n;
loop variant n - i;
*/
while (i * i <= n) {
i++;
}
return i - 1;
}
Dans cet exemple, nous avons:
- Une précondition qui exige que n soit positif ou nul
- Deux postconditions qui spécifient que le résultat est une approximation entière valide de la racine carrée
- Une clause assigns qui indique que la fonction ne modifie aucune variable externe
- Des invariants de boucle qui sont maintenus à chaque itération
- Un variant de boucle qui prouve la terminaison
Placement Stratégique des Annotations
Pour les fonctions
Les contrats de fonction (préconditions, postconditions, effets de bord) doivent être placés juste avant la déclaration de la fonction.
Pour les boucles
Les invariants et variants de boucle doivent être placés juste avant la déclaration de la boucle.
Pour les assertions
Les assertions peuvent être placées n'importe où dans le corps d'une fonction pour vérifier des conditions intermédiaires.
Exécution et Vérification avec Frama-C et WP
Pour vérifier formellement un programme C avec les annotations ACSL, il faut suivre un processus en plusieurs étapes:
Installation de Frama-C
Avant de commencer, assurez-vous d'avoir installé Frama-C et ses dépendances. Selon votre système d'exploitation:
Sur Linux (Debian/Ubuntu)
sudo apt-get install frama-cSur macOS (avec Homebrew)
brew install frama-cÀ partir des sources
Consultez la documentation officielle sur frama-c.com.
Commandes d'Exécution
Pour analyser un fichier C annoté avec ACSL, utilisez les commandes suivantes:
Mode ligne de commande
frama-c -wp fichier.cAvec l'interface graphique
frama-c-gui -wp fichier.cOptions importantes
-wp-rte: Vérifie automatiquement l'absence d'erreurs à l'exécution (débordements, divisions par zéro, etc.)-wp-print: Affiche les obligations de preuve générées-wp-prover alt-ergo,cvc4,z3: Spécifie les prouveurs à utiliser
Cette vidéo présente une démonstration pratique de la vérification formelle avec Frama-C et illustre les concepts fondamentaux abordés dans cet exposé.
Contrats de Fonction: Préconditions et Postconditions
Les contrats de fonction sont au cœur de la vérification déductive avec Frama-C. Ils définissent le comportement attendu d'une fonction en termes de conditions d'entrée et de sortie.
Rôle des Préconditions
Les préconditions (requires) spécifient les conditions qui doivent être satisfaites avant l'appel d'une fonction. Elles constituent les obligations de l'appelant et les hypothèses sur lesquelles le développeur de la fonction peut s'appuyer.
Exemples de préconditions
/*@
requires a != 0; // Le diviseur ne doit pas être nul
requires \valid(result); // Le pointeur result doit être valide
*/
void divide(int n, int a, int* result) {
*result = n / a;
}
Rôle des Postconditions
Les postconditions (ensures) spécifient les conditions qui doivent être satisfaites après l'exécution d'une fonction. Elles constituent les garanties fournies par la fonction et les propriétés sur lesquelles l'appelant peut compter.
Exemples de postconditions
/*@
requires a != 0 && \valid(result);
ensures *result == n / a; // Le résultat contient la division
ensures \old(n) == n && \old(a) == a; // n et a sont inchangés
*/
void divide(int n, int a, int* result) {
*result = n / a;
}
Comportements Conditionnels
ACSL permet également de spécifier des comportements différents selon les conditions d'entrée:
/*@
requires \valid(result);
behavior division_possible:
assumes a != 0;
ensures *result == n / a;
ensures \result == 0; // Code de retour: succès
behavior division_impossible:
assumes a == 0;
ensures \result == -1; // Code de retour: erreur
complete behaviors; // Les comportements couvrent tous les cas
disjoint behaviors; // Les comportements sont mutuellement exclusifs
*/
int divide_safe(int n, int a, int* result) {
if (a == 0) return -1;
*result = n / a;
return 0;
}
Assertions et Points de Vérification
Les assertions sont des vérifications ponctuelles dans le code qui permettent de s'assurer que certaines propriétés sont maintenues pendant l'exécution.
Assertions ACSL
En ACSL, les assertions sont introduites avec le mot-clé assert et doivent être prouvées statiquement par Frama-C:
void increment_array(int* array, int size) {
/*@ requires \valid(array + (0 .. size-1)); */
/*@ requires size > 0; */
for (int i = 0; i < size; i++) {
/*@ assert 0 <= i < size; */
array[i]++;
}
/*@ assert array[0] > \old(array[0]); */
}
Différence avec les assertions C standard
Les assertions ACSL diffèrent des assertions C standard (assert() de <assert.h>) :
- Les assertions ACSL sont vérifiées statiquement à la compilation par Frama-C
- Les assertions C sont vérifiées dynamiquement à l'exécution
On peut utiliser les deux types d'assertions de manière complémentaire:
#include <assert.h>
void increment_array(int* array, int size) {
/*@ requires \valid(array + (0 .. size-1)); */
/*@ requires size > 0; */
assert(array != NULL); // Assertion C standard (runtime)
for (int i = 0; i < size; i++) {
/*@ assert 0 <= i < size; */ // Assertion ACSL (static)
array[i]++;
}
}
- Contraintes sur les entrées
- Bornes des paramètres"] Postconditions["Postconditions (ensures)"] PostExemples["- Propriétés du résultat
- Relations entre entrées/sorties
- État de la mémoire"] EffetsBord["Effets de bord (assigns)"] AssignsExemples["- Variables modifiées
- Régions mémoire affectées
- \nothing (fonction pure)"] Assertions["Assertions et vérifications"] PointsVerif["Assertions (assert)"] AssertExemples["- Conditions intermédiaires
- Invariants ponctuels
- Vérifications de sécurité"] Boucles["Annotations de boucles"] Invariants["Invariants (loop invariant)"] Variants["Variants (loop variant)"] Predicats["Prédicats spéciaux"] MemoryPred["Prédicats mémoire"] ValidPred["- \valid, \valid_read
- \separated
- \initialized"] SpecialVars["Variables spéciales"] ResultVar["- \result (valeur de retour)
- \old (valeur avant exécution)"]
Ce diagramme présente une vision globale de la hiérarchie des annotations ACSL et de leurs différentes catégories, illustrant comment les différents concepts s'articulent pour former un système complet de spécification formelle.
Exemples Concrets d'Utilisation
Examinons quelques exemples complets qui illustrent l'utilisation de Frama-C avec ACSL pour la vérification de code C.
Exemple 1: Fonction de Recherche Binaire
/*@
requires \valid(arr + (0 .. n-1));
requires n > 0;
requires \forall int i, j; 0 <= i < j < n ==> arr[i] <= arr[j]; // tableau trié
behavior found:
assumes \exists int i; 0 <= i < n && arr[i] == key;
ensures 0 <= \result < n;
ensures arr[\result] == key;
behavior not_found:
assumes \forall int i; 0 <= i < n ==> arr[i] != key;
ensures \result == -1;
complete behaviors;
disjoint behaviors;
*/
int binary_search(int* arr, int n, int key) {
int low = 0, high = n - 1;
/*@
loop invariant 0 <= low <= high + 1 <= n;
loop invariant \forall int i; 0 <= i < low ==> arr[i] < key;
loop invariant \forall int i; high < i < n ==> arr[i] > key;
loop variant high - low + 1;
*/
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
Pour vérifier cette fonction avec Frama-C:
frama-c -wp -wp-rte binary_search.cExemple 2: Calcul de Factorielle
/*@
requires n >= 0;
requires n <= 12; // Pour éviter les dépassements en int
ensures \result > 0;
ensures n == 0 ==> \result == 1;
ensures n > 0 ==> \result == n * factorial(n-1);
assigns \nothing;
*/
int factorial(int n) {
if (n == 0)
return 1;
else {
/*@ assert n > 0; */
return n * factorial(n - 1);
}
}
Cette fonction illustre l'utilisation des annotations ACSL pour une fonction récursive, avec une postcondition qui définit la relation de récurrence.
Galerie d'Images: Frama-C en Action
Capture d'écran montrant Frama-C détectant une tentative d'écriture hors limites dans un tableau
Interface graphique de Frama-C montrant les résultats d'analyse d'un programme
Foire Aux Questions (FAQ)
Références
- Frama-C - Framework for Modular Analysis of C programs
- ACSL by Example - GitHub
- Introduction à la preuve de programmes C avec Frama-C et son greffon WP
- Introduction to C program proof with Frama-C and its WP plugin (PDF)
- The Dogged Pursuit of Bug-Free C Programs – Communications of the ACM
Recommandations
Last updated April 9, 2025