Vérification formelle : Les outils de preuve de programme qui garantissent la fiabilité
Une exploration des techniques permettant de prouver mathématiquement la correction de vos programmes informatiques
Points essentiels à retenir
- Les outils de preuve de programme permettent de vérifier formellement la correction des programmes et d'éliminer certaines classes d'erreurs avant l'exécution.
- Les préconditions et postconditions forment le contrat que le programme doit respecter, définissant les états valides avant et après l'exécution d'une fonction.
- Les assertions sont des points de contrôle intégrés au code qui vérifient que certaines conditions sont respectées pendant l'exécution.
Introduction aux outils de preuve de programme
Les outils de preuve de programme sont des logiciels spécialisés permettant de vérifier mathématiquement la correction d'un programme informatique. Contrairement aux tests qui ne peuvent confirmer que l'absence d'erreurs pour les cas testés, la preuve formelle peut garantir l'absence totale de certaines classes d'erreurs dans toutes les situations possibles.
Ces outils s'appuient sur des méthodes formelles issues de la logique mathématique pour analyser le comportement d'un programme. Ils vérifient que le programme respecte ses spécifications et qu'il ne contient pas de bugs comme les dépassements de mémoire, les divisions par zéro ou les deadlocks.
Pourquoi utiliser des outils de preuve ?
Dans les systèmes critiques (aéronautique, médical, nucléaire), une simple erreur de programmation peut avoir des conséquences catastrophiques. Les outils de preuve apportent une garantie mathématique que le programme fonctionne correctement selon ses spécifications, ce que les tests traditionnels ne peuvent pas garantir à 100%.
Les avantages de la vérification formelle
- Détection précoce des erreurs, avant même l'exécution du programme
- Garantie mathématique de correction pour les propriétés vérifiées
- Documentation précise du comportement attendu du programme
- Réduction des coûts de maintenance à long terme
Principaux outils de preuve de programme
De nombreux outils de vérification formelle existent, chacun avec ses spécificités et son domaine d'application :
| Outil | Langage cible | Type d'analyse | Particularités |
|---|---|---|---|
| Frama-C | C | Analyse statique | Utilise le langage de spécification ACSL, système modulaire avec plugins |
| Coq | Multiple | Assistant de preuve | Système très expressif, utilisé pour des preuves complexes |
| Why3 | WhyML | Plateforme de vérification | Interface avec plusieurs prouveurs automatiques |
| JML | Java | Annotation et vérification | Intégré aux commentaires Java |
| Z3 | Multiple | Solveur SMT | Prouveur automatique développé par Microsoft |
Comprendre le radar des capacités des outils de preuve
Les différents outils de preuve se distinguent par leurs capacités dans plusieurs dimensions. Le graphique ci-dessous illustre les forces relatives des principaux outils selon différents critères d'évaluation :
Syntaxe et utilisation des outils de preuve
Bien que chaque outil possède sa propre syntaxe, ils partagent des concepts fondamentaux comme les préconditions, les postconditions et les invariants. Voici comment ces concepts sont exprimés dans différents outils :
Annotations en ACSL (pour Frama-C)
ACSL (ANSI/ISO C Specification Language) est le langage d'annotation utilisé avec Frama-C pour spécifier le comportement attendu des programmes C :
/*@ requires x > 0;
@ ensures \result == x * x;
@ assigns \nothing;
*/
int carre(int x) {
return x * x;
}
Dans cet exemple :
requires: spécifie la précondition (x doit être positif)ensures: spécifie la postcondition (le résultat doit être égal à x²)\result: désigne la valeur de retour de la fonctionassigns: indique quelles variables peuvent être modifiées (ici aucune)
Assertions en Python
Python propose une instruction assert native qui vérifie une condition pendant l'exécution du programme :
def diviser(a, b):
assert b != 0, "Le diviseur ne peut pas être zéro"
return a / b
resultat = diviser(10, 2) # Fonctionnement normal
resultat = diviser(10, 0) # Lève une AssertionError
Développement en Coq
Coq utilise un langage fonctionnel proche de ML avec des notations spécifiques pour les preuves :
Definition est_pair (n : nat) : bool :=
match n with
| 0 => true
| S 0 => false
| S (S n') => est_pair n'
end.
Theorem est_pair_correct : forall n,
est_pair n = true <-> exists k, n = 2 * k.
Proof.
(* Preuve mathématique ici *)
Qed.
JML pour Java
Java Modeling Language (JML) intègre les annotations directement dans les commentaires Java :
/**
* @requires x >= 0;
* @ensures \result >= 0 && \result * \result <= x && (\result+1) * (\result+1) > x;
*/
public int racineEntiere(int x) {
int r = 0;
while ((r+1) * (r+1) <= x) {
r++;
}
return r;
}
Exécution et vérification avec les outils de preuve
Le processus de vérification formelle comprend généralement les étapes suivantes :
Étapes du processus de vérification
- Spécification : Définir formellement le comportement attendu du programme
- Annotation : Ajouter les préconditions, postconditions et invariants au code
- Vérification : Utiliser l'outil de preuve pour vérifier que le programme respecte ses spécifications
- Itération : Corriger les erreurs et renforcer les spécifications si nécessaire
Exemple avec Frama-C
Pour exécuter une vérification avec Frama-C, suivez ces étapes :
- Installez Frama-C :
apt-get install frama-c(sur Debian/Ubuntu) - Créez votre fichier C avec les annotations ACSL
- Lancez la vérification :
frama-c -wp fichier.c - Analysez les résultats dans l'interface graphique ou en ligne de commande
Voici un exemple de sortie de Frama-C :
[wp] Running WP plugin...
[wp] Collecting axiomatic usage
[kernel] Parsing FRAMAC_SHARE/libc/__fc_builtin_for_normalization.i (no preprocessing)
[wp] 2 goals scheduled
[wp] [Goal 1/2] Postcondition of function 'carre' : Valid
[wp] [Goal 2/2] Assertion 'x > 0' : Valid
[wp] Proved goals: 2 / 2
[wp] Qed: 2 (100%)
Comment introduire un programme à vérifier
Pour introduire un programme à vérifier, vous devez suivre une méthodologie structurée :
- Analysez les requis fonctionnels et non-fonctionnels du programme
- Identifiez les propriétés qui doivent être vérifiées
- Choisissez l'outil de preuve adapté à votre langage et vos besoins
- Traduisez les propriétés en annotations formelles (préconditions, postconditions, invariants)
- Procédez à la vérification incrémentale en commençant par les propriétés les plus simples
Préconditions et postconditions
Les préconditions et postconditions sont au cœur de la programmation par contrat et de la vérification formelle. Elles définissent un contrat entre le fournisseur d'une fonction et son utilisateur :
Définition et rôle
- Précondition : Condition qui doit être vraie avant l'exécution d'une fonction. Elle représente la responsabilité de l'appelant.
- Postcondition : Condition qui doit être vraie après l'exécution d'une fonction. Elle représente la garantie fournie par la fonction.
Exemple d'application
Prenons l'exemple d'une fonction de racine carrée entière :
/*@ requires n >= 0;
@ ensures \result * \result <= n && (\result+1) * (\result+1) > n;
*/
int racine_entiere(int n) {
int r = 0;
/*@ loop invariant r * r <= n;
@ loop variant n - r;
*/
while ((r+1) * (r+1) <= n) {
r++;
}
return r;
}
Ici, la précondition stipule que l'entrée doit être positive, et la postcondition garantit que le résultat est la plus grande valeur entière r telle que r² ≤ n.
Structure conceptuelle des préconditions et postconditions
Les assertions dans la preuve de programme
Les assertions sont des points de contrôle dans le code qui vérifient que certaines conditions sont respectées pendant l'exécution. Elles constituent un mécanisme puissant pour la détection précoce des erreurs.
Rôle des assertions
Les assertions servent plusieurs objectifs :
- Documenter les hypothèses du programmeur
- Détecter rapidement les violations de ces hypothèses
- Faciliter le débogage en localisant précisément les erreurs
- Rendre le code plus robuste et fiable
Exemple d'utilisation des assertions en C
#include <assert.h>
int tableau_maximum(int tableau[], int taille) {
assert(taille > 0); // La taille doit être positive
int max = tableau[0];
for (int i = 1; i < taille; i++) {
if (tableau[i] > max) {
max = tableau[i];
}
}
return max;
}
Comparaison des mécanismes d'assertion
Différents langages proposent différentes syntaxes pour les assertions :
| Langage | Syntaxe | Comportement | Activation/Désactivation |
|---|---|---|---|
| C | assert(condition); |
Arrêt du programme si faux | Définir NDEBUG pour désactiver |
| Java | assert condition : "message"; |
AssertionError si faux | Option -ea pour activer |
| Python | assert condition, "message" |
AssertionError si faux | Option -O pour désactiver |
| C++ | assert(condition); |
Arrêt du programme si faux | Définir NDEBUG pour désactiver |
Meilleures pratiques
- Utilisez des assertions pour vérifier les conditions qui doivent toujours être vraies
- Réservez les assertions pour les erreurs de programmation, pas pour les erreurs d'entrée utilisateur
- Formulez des messages d'assertion clairs et informatifs
- Ne mettez pas de code avec des effets de bord dans les assertions
Exemple vidéo : Introduction aux assertions
Cette vidéo explique clairement comment utiliser les assertions pour valider les hypothèses dans votre code et améliorer la qualité de vos programmes :
Exemples de programme avec annotations
Voici quelques exemples concrets d'utilisation des outils de preuve sur des programmes simples :
Recherche binaire prouvée correcte
/*@ requires \valid(t+(0..n-1));
@ requires n > 0;
@ requires \forall integer i, j; 0 <= i <= j < n ==> t[i] <= t[j];
@ ensures -1 <= \result < n;
@ ensures \result >= 0 ==> t[\result] == v;
@ ensures \result == -1 ==> \forall integer i; 0 <= i < n ==> t[i] != v;
*/
int recherche_binaire(int t[], int n, int v) {
int gauche = 0, droite = n-1, milieu;
/*@ loop invariant 0 <= gauche <= droite+1 <= n;
@ loop invariant \forall integer i; 0 <= i < gauche ==> t[i] < v;
@ loop invariant \forall integer i; droite < i < n ==> t[i] > v;
@ loop variant droite - gauche;
*/
while (gauche <= droite) {
milieu = gauche + (droite - gauche) / 2;
if (t[milieu] == v)
return milieu;
if (t[milieu] < v)
gauche = milieu + 1;
else
droite = milieu - 1;
}
return -1;
}
Tri par insertion avec preuve de correction
/*@ requires \valid(t+(0..n-1));
@ requires n > 0;
@ ensures \forall integer i, j; 0 <= i <= j < n ==> t[i] <= t[j];
@ assigns t[0..n-1];
*/
void tri_insertion(int t[], int n) {
int i, j, cle;
/*@ loop invariant 1 <= i <= n;
@ loop invariant \forall integer k1, k2; 0 <= k1 <= k2 < i ==> t[k1] <= t[k2];
@ loop variant n - i;
*/
for (i = 1; i < n; i++) {
cle = t[i];
/*@ loop invariant 0 <= j+1 <= i;
@ loop invariant \forall integer k; j+1 <= k < i ==> t[k] > cle;
@ loop invariant \forall integer k1, k2; 0 <= k1 <= k2 < j+1 ==> t[k1] <= t[k2];
@ loop invariant \forall integer k1, k2; j+1 <= k1 <= k2 < i+1 ==> t[k1] <= t[k2];
@ loop variant j;
*/
for (j = i-1; j >= 0 && t[j] > cle; j--) {
t[j+1] = t[j];
}
t[j+1] = cle;
}
}
Illustrations des concepts de preuve de programme
Exemple visuel de code avec annotations pour la vérification formelle
Les outils de preuve s'adaptent à différents langages de programmation
Foire aux questions (FAQ)
Références
- Assertions en Python pour améliorer la fiabilité du code - PythoniaFormation
-
Tutoriel d'assertions en Java avec exemples de code - CiteSchool
- Introduction à la preuve de programmes C avec Frama-C - Zeste de Savoir
- Programmation par contrat - Wikipédia
- Cours sur la preuve de programmes impératifs - École Polytechnique
- Introduction à la preuve de programmes et aux assertions - LORIA
Pour aller plus loin
Last updated April 7, 2025