Prouver un algorithme

Un programme qui a passé mille tests peut encore échouer au mille et unième. « Tester un programme peut montrer la présence de bugs, jamais leur absence », écrit Edsger Dijkstra en 1970. Pour être sûr, il faut raisonner sur le code lui-même. Face à un algorithme, on se pose trois questions :

S'arrête-t-il ?C'est la terminaison : aucune entrée ne doit le faire tourner indéfiniment.
Calcule-t-il juste ?C'est la correction : le résultat est bien celui qu'on attendait.
Assez vite ?C'est la complexité, sujet de la page Complexité.

Cette page traite des deux premières, avec deux outils qui se ressemblent par le nom et se complètent : le variant, qui prouve qu’une boucle s’arrête, et l’invariant, qui prouve qu’elle calcule juste.

Dire ce qu’on attend

Avant de prouver qu’un programme est juste, il faut dire ce que « juste » veut dire. C’est la spécification, un contrat en deux parties : les préconditions, ce que l’on suppose des entrées, et les postconditions, ce que l’on garantit en sortie.

préconditions$a$ et $b$ entiers,
$a \geqslant 0$ et $b > 0$
→
algorithmeq, r = division(a, b)
→
postconditions$a = bq + r$
et $0 \leqslant r < b$

Le contrat de la division euclidienne. Si l'appelant ne respecte pas les préconditions, par exemple avec b = 0, l'algorithme n'est tenu à rien.

Un algorithme est correct s’il respecte son contrat. La distinction suivante n’est pas un détail :

Correction partiellePour toute entrée qui vérifie les préconditions, s'il s'arrête, la sortie vérifie les postconditions. Une boucle infinie est partiellement correcte : elle ne renvoie jamais rien de faux !
Correction totaleLa correction partielle, et l'algorithme s'arrête toujours. C'est ce qu'on veut prouver : correction partielle + terminaison.
1999
Mars Climate Orbiter

La sonde se désintègre dans l'atmosphère de Mars. Un logiciel au sol fournissait des impulsions en livres-force × secondes, quand le logiciel de navigation les attendait en newtons × secondes. Chaque programme était juste ; c'est le contrat entre les deux qui n'était pas écrit.

S’arrêter

Le variant de boucle

Une boucle for parcourt un nombre de tours fixé d’avance. Le danger vient des boucles while et des fonctions récursives, qui peuvent tourner sans fin. Pour prouver qu’une boucle while s’arrête, on exhibe un variant : une quantité entière, positive tant que la boucle tourne, et qui diminue strictement à chaque tour.

L’argument tient en une image : un escalier dont chaque marche est un entier positif. Depuis la marche $462$, on peut descendre longtemps, mais pas indéfiniment : une suite d’entiers positifs strictement décroissante finit toujours par s’arrêter. La boucle fait donc un nombre fini de tours.

Dans l’algorithme d’Euclide, le variant est b :

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
462 147 21 0 avant la boucletour 1tour 2tour 3 : sortie

Le variant b pour pgcd(1071, 462) : un entier positif qui diminue strictement à chaque tour, jusqu'à la sortie.

À chaque tour, b est remplacé par le reste de la division de a par b, qui est un entier compris entre $0$ et $b - 1$ : il reste positif et devient strictement plus petit. Dans la multiplication égyptienne ou l’exponentiation rapide, le variant est le nombre que l’on divise par $2$ à chaque tour. Le choix du variant n’est pas toujours aussi évident, mais l’idée est toujours la même : trouver ce qui s’use.

2008
Les baladeurs Zune bloqués le 31 décembre

Le 31 décembre 2008, tous les baladeurs Zune 30 Go de Microsoft se figent pour la journée. Leur horloge calculait l'année à partir du nombre de jours écoulés depuis 1980, avec une boucle dont la quantité jours ne diminuait pas dans un cas : le 366e jour d'une année bissextile. Il manquait un variant.

Voici la boucle fautive, traduite en Python. Le 31 décembre 2008 est le $10\,593^\text{e}$ jour depuis le 1er janvier 1980, et 2008 est bissextile : dans la branche des années bissextiles, si jours vaut exactement $366$, rien ne change, et la boucle tourne indéfiniment. Un compteur de tours l’arrête ici artificiellement.

Les fonctions récursives

Pour une fonction récursive, le raisonnement est le même : il faut qu’une quantité entière positive diminue strictement d’un appel à l’appel suivant, et que les cas de base arrêtent la descente. C’est le plus souvent l’argument lui-même, comme n dans factorielle(n), qui appelle factorielle(n - 1).

Ce n’est pas toujours aussi visible. La fonction 91 de John McCarthy appelle $M(n + 11)$, avec un argument plus grand, puis s’applique au résultat :

Elle s’arrête pourtant toujours, et renvoie $\color{#15803d}{91}$ pour tout $n \leqslant 100$. On le démontre par récurrence sur $\color{#B45309}{101 - n}$, la distance qui sépare $n$ du cas de base. Pour $90 \leqslant n \leqslant 100$, $n + 11$ dépasse $100$, donc $M(n + 11) = n + 1$ et $M(n) = M(n + 1)$ : de proche en proche, $M(n) = M(101) = 91$. Pour $n < 90$, l’appel intérieur $M(n + 11)$ porte sur un entier plus proche de $101$ ; par hypothèse de récurrence, il s’arrête et vaut $91$, et $M(n) = M(91) = 91$. Ce n’est pas l’argument qui diminue d’un appel à l’autre, mais la distance $101 - n$ dans la preuve.

La suite de Syracuse

On part d’un entier $n$ : s’il est pair, on le divise par $2$, sinon on le remplace par $3n + 1$, et l’on recommence jusqu’à tomber sur $1$. Partant de $\color{#2563EB}{6}$ : $6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to \color{#15803d}{1}$.

def vol(n):
    etapes = 0
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        etapes += 1
    return etapes

Cette boucle s’arrête-t-elle pour tout $n$ ? Personne ne le sait. La conjecture, énoncée par Lothar Collatz dans les années 1930, a été vérifiée par ordinateur pour tous les entiers jusqu’à $2^{68}$, soit près de $3 \times 10^{20}$. En 2019, Terence Tao a montré qu’elle est vraie « presque » pour tous les entiers, en un sens précis. Mais aucun variant n’est connu : la suite monte et descend de façon imprévisible, et Paul Erdős disait que les mathématiques ne sont peut-être pas encore prêtes pour de tels problèmes.

Le problème de l’arrêt

Faute de savoir le faire à la main, pourrait-on écrire un programme qui décide, pour n’importe quel programme et n’importe quelle entrée, s’il s’arrête ? En 1936, Alan Turing démontre que c’est impossible. Supposons qu’une telle fonction termine(programme, entree) existe, et écrivons :

def paradoxe(programme):
    if termine(programme, programme):
        while True:         # boucle sans fin
            pass
    else:
        return

Que fait paradoxe(paradoxe) ?

Si elle s'arrête…c'est que termine(paradoxe, paradoxe) a répondu non : elle ne s'arrête pas.
Si elle ne s'arrête pas…c'est que termine a répondu oui : elle s'arrête.

Les deux cas sont contradictoires : la fonction termine ne peut pas exister. C’est le même mécanisme que dans le théorème d’incomplétude de Gödel. Il n’existera donc jamais d’outil universel pour prouver la terminaison. Il reste à la prouver programme par programme, comme on vient de le faire.

Calculer juste

L’invariant de boucle

Pour prouver qu’une boucle calcule ce qu’on attend, on cherche une propriété qui reste vraie d’un tour à l’autre, un invariant. La preuve a exactement la forme d’une démonstration par récurrence :

récurrenceinvariant de boucle 1
Initialisationla propriété est vraie au rang 0
Initialisationl'invariant est vrai avant le premier tour
2
Héréditévraie au rang k ⇒ vraie au rang k + 1
Conservationvrai au début d'un tour ⇒ vrai à la fin
3
Conclusionvraie à tout rang
Sortieinvariant vrai et condition de boucle fausse ⇒ postcondition

La troisième étape est propre aux boucles : c’est là qu’on récolte le fruit de la preuve. En sortie, on dispose de deux informations à la fois, l’invariant et la négation de la condition de boucle, et c’est leur réunion qui doit donner la postcondition.

L’animation suit quatre boucles tour par tour, avec leur variant, qui diminue jusqu’à la sortie, et leur invariant, qui ne bouge pas.

Pour l’algorithme d’Euclide, l’invariant est $\mathrm{pgcd}(a, b)$. Si $a = bq + r$, tout diviseur commun de $a$ et $b$ divise $r = a - bq$, et tout diviseur commun de $b$ et $r$ divise $a = bq + r$ : les couples $(a, b)$ et $(b, r)$ ont les mêmes diviseurs communs, donc le même pgcd. Le tour de boucle conserve l’invariant. En sortie, $b = 0$, et $\mathrm{pgcd}(a, 0) = a$ :

pgcd(1071, 462)= pgcd(462, 147)= pgcd(147, 21)= pgcd(21, 0)= 21

L'invariant, en vert, ne change pas d'un tour à l'autre ; le variant, en orange, diminue jusqu'à 0.

Pour la multiplication égyptienne, l’invariant est $\color{#15803d}{a \times b + p}$. Si $a$ est pair, on remplace $a$ par $\frac{a}{2}$ et $b$ par $2b$, ce qui ne change pas leur produit. Si $a$ est impair, on remplace $a$ par $\frac{a - 1}{2}$, $b$ par $2b$ et $p$ par $p + b$, et $\frac{a-1}{2} \times 2b + p + b = ab + p$. En sortie, $a = 0$, et $p$ vaut le produit cherché.

Trouver l’invariant est la partie créative de la preuve. Il dit ce que la boucle a déjà accompli : « le pgcd n’a pas changé », « ce qui reste à ajouter vaut $a \times b$ ».

2014
Apple et le « goto fail »

Dans le code qui vérifie l'authenticité d'une connexion sécurisée sur iPhone et Mac, une ligne goto fail; se retrouve écrite deux fois. La seconde est toujours exécutée, et saute la dernière vérification de signature : pendant plus d'un an, des connexions frauduleuses sont acceptées. Le programme s'arrêtait toujours ; il ne calculait pas juste.

La dichotomie, enfin juste

La recherche dichotomique est l’exemple type d’une boucle facile à imaginer et difficile à écrire juste. L’invariant est un dessin : si $x$ est dans la liste, il est dans la zone qui va de l’indice $g$ à l’indice $d$ ; tout ce qui est à gauche est trop petit, tout ce qui est à droite trop grand.

23571113171923
gmd

On cherche x = 19. La zone en bleu contient forcément x s'il est dans la liste. Comme L[m] = 17 < 19, toute la partie g…m est trop petite : la zone devient m + 1…d, et rétrécit.

Avec cet invariant, la version correcte s’écrit sans hésiter :

1
Initialisationla zone est la liste entière : l'invariant est vrai.
2
Conservationsi L[m] < x, comme L est triée, les cases de g à m sont toutes plus petites que x : x, s'il est dans la zone, est entre m + 1 et d. Le cas L[m] > x est symétrique. La zone rétrécit d'au moins une case : le variant d − g + 1 diminue strictement.
3
Sortiesi l'on sort par return True, on a trouvé x. Sinon, la condition g ≤ d est fausse : la zone est vide, et l'invariant dit que x n'est pas dans L.

La preuve désigne exactement l’erreur de la version fausse. Avec while g < d, on sort quand g vaut d : la zone contient encore une case, jamais examinée, et l’invariant ne permet plus de conclure.

Écrire l’invariant d’abord : le drapeau hollandais

Un invariant ne sert pas qu’à vérifier un programme après coup : on peut l’écrire avant le code, et laisser le code en découler. Dijkstra en donne un exemple célèbre : ranger en un seul passage, par échanges, des boules rouges, blanches et bleues, comme les bandes du drapeau néerlandais.

On commence par décrire une situation intermédiaire, avec trois indices r, i et w : les cases avant r sont rouges, celles de r à i (exclu) blanches, celles de i à w (exclu) pas encore examinées, celles à partir de w bleues. Au départ, r = i = 0 et w = n : tout est à examiner. À la fin, la zone à examiner doit être vide. Reste à écrire un tour de boucle qui examine la boule en i et rétablit l’invariant ; il n’y a que trois cas, et chacun se déduit du dessin.

À chaque tour, soit i augmente, soit w diminue : w - i est un variant, et chaque boule n’est examinée qu’une fois. C’est la partition en trois zones qu’utilisent les meilleures versions du tri rapide quand le tableau contient beaucoup de valeurs égales au pivot. Le tri par insertion suit la même démarche, avec l’invariant « les i premières cases sont triées », tout comme le tas, construit autour de l’invariant « chaque parent est plus petit que ses enfants ».

Les fonctions récursives

Pour une fonction récursive, la preuve de correction est une récurrence, dont la structure est celle du code lui-même. Prenons l’exponentiation rapide :

def puissance(x, n):
    if n == 0:
        return 1
    p = puissance(x, n // 2)
    if n % 2 == 0:
        return p * p
    return p * p * x

On montre, par récurrence forte sur $n$, que puissance(x, n) renvoie $x^n$. Pour $n = 0$, elle renvoie $1 = x^0$. Si la propriété est vraie pour tous les entiers plus petits que $n \geqslant 1$, elle l’est en particulier pour $k = \lfloor n/2 \rfloor < n$, et p vaut $x^k$. Si $n = 2k$, la fonction renvoie $x^k \times x^k = x^{2k}$ ; si $n = 2k + 1$, elle renvoie $x^{2k} \times x = x^{2k+1}$. Dans les deux cas, c’est $x^n$. Une fonction récursive se prouve souvent plus facilement qu’une boucle : l’hypothèse de récurrence tient lieu d’invariant, et elle est donnée par la définition même de la fonction.

Faire vérifier par la machine

Les assertions

Entre le test et la preuve, il y a un intermédiaire : écrire la spécification et l’invariant dans le code, sous forme d’assertions. L’instruction assert condition ne fait rien si la condition est vraie, et arrête le programme avec une erreur sinon. Une précondition violée est ainsi détectée à l’entrée de la fonction, plutôt que par un résultat absurde trois fonctions plus loin.

Ce n’est pas une preuve : les assertions ne sont vérifiées que sur les entrées effectivement essayées. Mais elles rendent visible le raisonnement, et le moindre écart est signalé à l’endroit où il se produit.

2014
Heartbleed

Dans OpenSSL, qui chiffre une grande partie du web, le client envoie un petit message que le serveur lui renvoie en écho, avec sa longueur annoncée. Le serveur ne vérifiait pas que cette longueur correspondait à la longueur réelle. En annonçant 64 Ko pour un message d'un octet, on récupérait des morceaux de la mémoire du serveur, mots de passe et clés compris. Une précondition non vérifiée.

La preuve formelle

À la fin des années 1960, Robert Floyd et Tony Hoare transforment ces raisonnements en un calcul. Un triplet de Hoare affirme que si la propriété $P$ est vraie avant l’instruction $C$, alors $Q$ est vraie après :

{ x ≥ 0 }x = x + 1{ x ≥ 1 }

Précondition en bleu, instruction en noir, postcondition en vert. Des règles permettent d'enchaîner ces triplets instruction par instruction, et d'en déduire celui d'une boucle à partir de son invariant.

Il devient alors possible de faire vérifier une preuve par un logiciel, qui ne laisse passer aucun cas oublié. Ces méthodes sont coûteuses, mais elles sont employées là où une erreur ne pardonne pas :

  • le logiciel de pilotage automatique de la ligne 14 du métro parisien, mise en service en 1998, a été développé avec la méthode B : le code est produit à partir d’un modèle dont on a prouvé les propriétés de sécurité ;
  • le compilateur C CompCert, conçu à l’Inria par Xavier Leroy, est accompagné d’une preuve, vérifiée par l’assistant de preuve Coq, que le code produit fait exactement ce que dit le code source ;
  • c’est en tentant de prouver formellement Timsort, l’algorithme de tri de Python et de Java, que des chercheurs ont découvert en 2015 un bug passé inaperçu pendant treize ans.
Ariane 501

Le 4 juin 1996, trente-sept secondes après son décollage, le premier exemplaire de la fusée Ariane 5 se met en travers de sa trajectoire et se désintègre. En cause, une ligne du logiciel de navigation, repris tel quel d’Ariane 4 : la conversion d’une mesure de vitesse horizontale, stockée dans un nombre à virgule sur $64$ bits, en un entier signé sur $\color{#DC2626}{16}$ bits, qui ne peut pas dépasser $\color{#DC2626}{32\,767}$. Ariane 5, plus puissante, accélérait beaucoup plus vite qu’Ariane 4, et la valeur a débordé. Le calcul fautif ne servait même plus à rien après le décollage.

L’algorithme était juste. C’est l’hypothèse implicite sur les nombres qui était fausse : sur une machine, un entier n’est pas un entier mathématique, et une preuve qui l’oublie ne prouve rien. C’est l’objet de la page suivante, Les nombres en machine.

À retenir
  • On prouve un algorithme par rapport à une spécification : des préconditions sur les entrées, des postconditions sur la sortie.
  • Terminaison : un variant, entier positif qui diminue strictement à chaque tour.
  • Correction : un invariant, avec trois étapes, initialisation, conservation, sortie ; à la sortie, invariant et condition de boucle fausse donnent ensemble la postcondition.
  • Aucun programme ne peut décider, pour tout programme, s’il s’arrête : la terminaison se prouve au cas par cas.