Le problème de l'arrêt - et pourquoi il est important

Par les participants du forum alt.comp.virus.
(Ces pages de sécurité sont le résultat d'un effort collectif continu.)


Menu principal

Le problème de l'arrêt - et pourquoi il est important
Par Kurt Wismer

Le problème de l'arrêt est très technique et je ne traiterai certainement pas de manière adéquate ses aspects techniques (et de toute façon je n'écris pas ce texte pour les techniciens). La version courte est que le problème de l'arrêt nous dit ce qui n'est pas possible dans l'informatique.

L'idée de base est la suivante: il n'y a pas d'ensemble d'étapes qu'une personne ou un ordinateur puisse suivre qui détermine toujours en un laps de temps fini si un programme quelconque finit par s'arrêter (terminera/cessera son exécution). Etant donné que suivre des étapes (des instructions) est tout ce qu'un ordinateur sait faire, ceci est très significatif pour les ordinateurs et les logiciels.

La raison pour laquelle ceci est intéressant et utile est que nous pouvons l'appliquer à d'autres choses; par là j'entends que si l'on peut démontrer que faire X peut être réduit au problème de l'arrêt, alors nous avons par ce fait prouvé qu'il est impossible de faire X.

Maintenant, progressons un peu: créer un ensemble d'étapes qui détermineront toujours dans un laps de temps fini si un programme quelconque exécute la fonction Y peut être réduit au problème de l'arrêt. Tout ce que vous devez faire est dire que la fonction Y est une fonction d'arrêt et vous verrez que c'est trivialement vrai. Du code qui fait qu'un programme se termine n'a rien de spécial qui le rendrait difficile à trouver; le problème est de déterminer si ce code sera exécuté. En réalité, le problème de l'arrêt est un cas spécial de ce principe plus général.

Créer un ensemble d'étapes qui détermineront toujours dans un laps de temps fini si un programme quelconque est un virus peut être réduit au problème de l'arrêt. Pour être un virus, un programme doit exécuter une fonction de reproduction et comme vous ne pouvez pas toujours déterminer (en suivant un ensemble d'étapes) si un programme quelconque exécute cette fonction, vous ne pouvez pas toujours déterminer si ce programme est un virus.

Créer un ensemble d'étapes qui détermineront toujours dans un laps de temps fini si un programme quelconque exécute d'autres fonctions virales peut être réduit au problème de l'arrêt... je suis sûr que vous pouvez maintenant en deviner la raison.

Ce n'est pas beau. Il semblerait que nous ne puissions pas dire beaucoup à propos de programmes quelconques, et non seulement cela est absolument vrai, mais c'est aussi l'essentiel. Le problème de l'arrêt est important parce qu'il nous montre ce qui n'est pas faisable, afin que nous puissions séparer les affirmations impossibles des affirmations possibles, afin que nous puissions comprendre ce qui empêche les éditeurs anti-virus de détecter tous les virus possibles, et afin que, lorsque quelqu'un demande "pourquoi il ne regarde pas simplement le code pour savoir ce qu'il fait", nous sachions pourquoi cela ne fonctionnera pas. Savoir ce qui n'est pas possible est sans doute le meilleur outil que nous avons pour voir clair dans le brouhaha et identifier la publicité mensongère dans le domaine antiviral.

En plus de cela, le fait de connaître ces limitations concernant l'identification des agissements de programmes quelconques nous fait comprendre que le problème des virus (chevaux de Troie/logiciels espions/adware/etc.) ne peut-être résolu par des moyens purement techniques avec notre paradigme informatique actuel. Bien que des changements aient été proposés pour le paradigme informatique actuel afin de mieux gérer le problème, ces changements auraient pour résultat des ordinateurs beaucoup plus restrictifs vis-à-vis des utilisateurs, des programmeurs et de l'innovation, et on peut seulement spéculer si il y aurait réellement eu l'effet désiré sur le problème des virus.

Cependant, les nouvelles du front antiviral ne sont pas toutes mauvaises. Bien que le problème d'arrêt dise effectivement que la détection de virus parfaite est impossible, il ne dit rien sur la distance qui peut nous séparer de la perfection. En pratique, tous les virus connus peuvent théoriquement être détectés (comme ils sont connus, il est beaucoup plus facile d'indiquer à un programme ce qu'il doit rechercher). En ajoutant l'heuristique, beaucoup ou même la plupart des virus dérivés peuvent être détectés, peu importe s'ils sont connus ou pas. Puis une couche de  technologie bac-à-sable nous permet de nous approcher encore plus de la détection parfaite (mais pas tout-à-fait, car la technologie bac-à-sable ne résoud pas le problème de l'arrêt). Ce n'est sans doute pas de la détection parfaite mais en pratique elle s'est avérée suffisamment bonne la plupart du temps.


(Kurt Wismer - Janvier 2006)