Vérification formelle : Les outils de preuve de programme qui garantissent la fiabilité

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 fonction
assigns : 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

mindmap root["Contrat de fonction"] Préconditions id1["Vérification des entrées"] id2["Protection contre les cas limites"] id3["Responsabilité de l'appelant"] Postconditions id4["Garantie sur les résultats"] id5["État du système après exécution"] id6["Responsabilité de la fonction"] Invariants id7["Propriétés préservées"] id8["État interne cohérent"] id9["Conditions sur les structures de données"]

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;
    }
}