Détection automatique de bugs

2009-09-04T22:12:55+02:00

L’Ours & Hippy crew vous présente son second billet feat. Cygal. Sous le regard hippie de blueblue aux commandes des platines d’édition — que l’on reconnaît grâce au manque d’originalité de son titre frigido-sérieux — l’artiste nous a concocté en direct de derrière le studio un nouvel article…
Qui nous parle du chant des insectes déviants,
Leurs pesticides heuristiques,
Et ses recettes hygiéniques,
À inculquer absolument aux ptits enfants !

—minh

Cette réaction traite d’un point qui va finir par ressembler à une obsession de ma part^☃ : la correction de bugs. Plus précisément, ce papier traite de la détection automatique de bugs. Le but est d’obtenir du programme assez d’informations pour pouvoir remarquer des comportements anormaux.

☃ : Alors que pas du tout, je suis encore à la recherche d’un fétiche.

C’est d’une certaine manière ce qu’apporte le typage à la compilation : les types apportent suffisament d’informations pour pouvoir détecter un certain nombre d’erreurs avant qu’elles n’apparaissent à l’exécution. L’analyse qui est faite ici est aussi statique, et se base sur un principe général qui peut s’appliquer à un nombre étonnament varié d’erreurs possibles. Les auteurs du papier ont ainsi détecté des centaines de bugs dans les noyaux Linux et BSD, principalement dans des drivers pas toujours maintenus.

Des langages comme OCaml sont capables d’inférer les types utilisés dans un programme, c’est-à-dire les deviner à partir du code. Le principe est ici le même, sauf qu’on essaie d’inférer du sens pour nous aider à trouver des erreurs.

Présentation du papier

Les exemples donnés ici sont directement tirés du papier : Bugs as deviant behavior (PDF, 16 pages).

Le principe est donc d’inférer le maximum d’informations possible dans chaque fonction, et d’essayer de détecter les contradictions présentes. L’existence d’une contradiction entre deux lignes montre qu’il y a forcément une erreur, même si le système ne peut pas forcément savoir de quelle ligne il s’agit.

Le montant d’informations qu’il est possible d’obtenir à partir d’un code source automatiquement est non seulement limité, mais on doit parfois se baser sur des informations peut-être fausses. C’est pourquoi j’ai séparé la présentation en deux courtes parties :

une sur ce qui est appelé les « MUST beliefs » dans le papier (on est certain qu’il y a une erreur) ;
et une autre sur les « MAY beliefs » (il y a très probablement une erreur).

MUST beliefs

Ainsi, prenons un exemple simple, tiré d’une version du noyau Linux aussi vieille que le papier.

/* 2.4.7 drivers/char/mxser.c */
int mxser_write(struct tty_struct *tty, ...) {
  struct mxser_struct *info = tty->driver_data;
  unsigned long flags;

  if (!tty || !info->xmit_buf)
    return(0);
  ...

Le bug ici vient du déréférencement du pointeur tty alors qu’il pourrait valoir NULL. C’est quelque chose qui peut arriver assez vite si l’on ni porte pas attention, par exemple pendant l’évolution d’un code source. Regardons comment notre programme fonctionne dans ce cas précis.

*info = tty->driver_data: Le pointeur tty est déréférencé, ce qui veut dire que le programmeur estime qu’il ne peut pas être nul.
if (!tty || !info->xmit_buf): La nullité du pointeur tty est testée, ce qui veut dire que le programmeur estime qu’il peut être nul.

On a donc une contradiction : l’une des deux lignes pose problème, ce qui être un bug. Et en effet si le pointeur peut être nul, il est dangereux de le déréférencer.

En pratique, il y a beaucoup trop de faux positifs. Par exemple, les macros vérifient souvent que leur arguments ne sont pas nul, et une fois que leur expansion est faite, on ne fait pas la différence avec le code normal. Les auteurs ont donc modifié leur programme (basé sur GCC apparement) pour annoter les expansions de macros, et ne pas les traiter pendant l’algorithme. D’autres problèmes ont été traités pour pouvoir montrer de réelles erreurs, je vous laisse lire le papier si ça vous intéresse.

MAY beliefs

Dans l’exemple sur les pointeurs donné ci-dessus et quelques autres, le programme est capable de dire avec certitude qu’il y a un problème. Cependant, ce n’est souvent pas possible de l’affirmer avec certitude : les informations inférées lors de la lecture du code ne sont pas forcément exactes. Ce n’est pas une raison de les ignorer, mais il faut les traiter avec prudence. L’idée est alors de rassembler un maximum de cas d’utilisations similaires, et d’en déduire les cas érronés. Par exemple, si une fonction est utilisée 999 fois d’une certaine manière, et autrement ailleurs, on peut supposer que le cas seul est érroné.

Donnons encore une fois un exemple pour expliquer cette pratique.

lock lk;            // Lock
int a, b;           // Variables potentially
                    // protected by l
void foo() {
       lock(lk);    // Enter critical section
       a = a + b;   // MAY: a, b protected by l
       unlock(lk);  // Exit critical section
       b = b + 1;   // MUST: b not protected by l
}
void bar() {
       lock(lk);
       a = a + 1;   // MAY: a protected by l
       unlock(lk);
}
void baz() {
       a = a + 1;   // MAY: a protected by l
       unlock(lk);
       b = b - 1;   // MUST: b not protected by l
       a = a / 5;   // MUST: a not protected by l
}

Supposons que lock() soit un appel système qui existe, et qui bloque l’accès aux données du noyau.^‽ On suppose donc que toute variable modifiée entre deux locks peut être concernée par ce lock. Une fois que l’on sait à peu près quelles sont les chances estimées que la variable soit concernée par le lock lk, on peut dire à l’utilisateur à quel point une utilisation en dehors du lock peut être dangereuse.

‽ : Pour information, le Big Kernel Lock a été créé, puis est enlevé petit à petit.

Ici, la fonction foo nous permet de dire que a est sûrement concerné par le lock lk, et que b peut l’être (mais moins de chance, vu que l’accès ne se fait qu’en lecture, non ?). La fonction bar montre que a est la seule variable utilisée dans le lock, donc il commence à y avoir de grandes chances que ce soit effectivement a qui est protégé. Dans baz, a est utilisé en dehors d’un lock, donc c’est certainement un bug qu’il faut corriger !

Cette manière d’essayer de deviner des informations plausibles pour ensuite essayer de détecter des erreurs a elle aussi de nombreuses applications décrites dans le papier. Certaines ne sont que des idées placées en plein milieu sans aucun rapport : d’ailleurs le style du papier laisse à désirer, le tout n’est pas très structuré, soyez avertis si vous comptez le lire (sachez aussi que je ne prétends pas faire mieux :). Une de ces idées consiste en la vérification de la cohérence d’une API proposée d’une version stable à une autre. Si on compare les croyances obtenues par notre système entre deux versions stables, elle doivent être exactement les mêmes. Sinon cela implique une possibilité de casser les applications utilisant l’API en question. Cela peut être aussi trouvé via l’utilisation de tests (potentiellement unitaires), mais c’est plus compliqué à mettre en place : un effort de la part du programmeur est impératif, et un test doit être exécuté, contrairement à l’analyse qui est ici statique.

N’hésitez pas à lire le papier si ces quelques lignes ne vous ont pas endormies : un certain nombre d’autres techniques intéressantes pour par exemple :

inférer le maximum d’information d’un code (notamment avec le nom des fonctions) ;
vérifier que la gestion d’erreurs d’un programme est efficace ;
que les pointeurs sont utilisés correctement dans le kernel (différence entre kernel pointer et user pointer) ;
détecter des fuites mémoires ;
etc.

Enseignements à tirer ?

Pour m’être amusé pendant tout un été à corriger des bugs, je commence à avoir une idée des pratiques à éviter ou au contraire à encourager pour éviter l’apparition de bugs. Le principe de base de ces pratiques est d’apporter le maximum d’informations à celui qui va lire le code (sans parler des commentaires). Ainsi, si un programme est capable de penser que telle façon de faire quelque chose est une erreur, c’est que certainement un humain qui va passer par là sans savoir comment fonctionne le code va aussi penser à une erreur, ou du moins ne va pas comprendre au premier abord ce qui se passe.

C’est l’origine de plusieurs pratiques couramment encouragées en programmation. Citons ici KISS et la minimisation des effets de bords. La première permet à tout le monde de mieux comprendre un code, de mieux comprendre ce qu’il fait exactement pour pouvoir l’utiliser et le modifier la conscience tranquille.

La seconde permet de pouvoir utiliser une fonction sans avoir peur qu’elle casse autre chose ailleurs. Ça permet aussi d’utiliser de la composition de fonction sans risque. Il y a beaucoup de choses à dire sur cette pratique, mais retenez que l’intérêt principal est de ne pas cacher les canaux par lesquels transite l’information pour rendre le code le plus compréhensible et facile à modifier possible. Moins le programmeur qui lit le code a de chances d’être surpris, moins il y a de chances d’avoir des problèmes par la suite.

Ainsi, certains 'design patterns' ont beau résoudre des problèmes, ils ajoutent souvent une couche d’abstraction qu’il faut pouvoir traverser pour comprendre exactement ce qui se passe. Cette couche empêche l’échange d’informations entre deux parties du code qui intéragissent pourtant directement, ce qui provoquera forcément des bugs, qui auraient pu être détectés autrement. De la même manière, trop de généricité empêche une vision claire du code qu’on a sous les yeux. Cela a causé certains problèmes qui sont devenus tellement fréquents qu’il a fallu inventer d’autres design patterns pour les éviter. L’important est d’en être conscient et d’ajouter d’autres mesures de protection quand le bon sens où le compilateur ne peut plus aider à filtrer les erreurs.

De la même manière, utiliser son langage de manière idiomatique et rester consistant dans son formattage, sa façon de penser et les techniques utilisées est important. Cela permet au lecteur de retirer beaucoup d’informations rapidement, et donc de pouvoir se concentrer sur les points importants.

Si le programme a cru détecter une erreur qui n’était en fait qu’un faux positif, il reste néanmoins important d’essayer de corriger le code : tous les humains qui le liront risqueront de faire la même erreur et de ne pas comprendre ce qui se passe. Dans ce sens là, les exemples présents dans le papier sont instructifs : se sont des erreurs qui peuvent sembler anodines mais qui restent importantes.

Ours & Hippy — le blog

Détection automatique de bugs

Présentation du papier

MUST beliefs

MAY beliefs

Enseignements à tirer ?