Cette instance de REDOCS vise à inventer une méthode automatique ou semi-automatique pour générer mécaniquement un jeu d’entrées fournissant une couverture d’arêtes à 100% sur chacune de plusieurs implémentations open-source en langage C de parseurs X.509.
X.509 est le format le plus courant pour représenter les certificats de clés publiques utilisés dans nombre de protocoles cryptographiques. Par exemple, si vous lisez ce sujet en 2022 dans un navigateur web, le sujet a été envoyé à travers une connexion HTTPS, et l’une des premières étapes de l’établissement de cette connexion a été l’envoi par le serveur d’un certificat X.509 qui l’identifie. Cliquer sur le petit cadenas vous donnera des détails supplémentaires sur le certificat utilisé par le serveur. De plus, il y a fort à parier que du côté du client (votre ordinateur), les données du certificat ont été décodées du format X.509 par du logiciel écrit dans le langage C, un langage qui a les deux défauts de rendre facile de faire des erreurs et de donner des conséquences catastrophiques du point de vue de la sécurité à certaines erreurs (allant jusqu’à l’exécution de code arbitraire par l’attaquant dans les pire cas). D’où l’intérêt pour un jeu de fichiers qui, utilisés comme entrées pour les implémentations les plus courantes de parseurs de certificats X.509, exercent le maximum de comportements possibles dans ces implémentations, dans le but d’y découvrir des bugs.
En test structurel, la couverture d’arêtes est l’un des critères qui permet de dire qu’une suite de tests exerce suffisamment le programme testé : chacune des branches “then” et “else” de chaque “if” du code testé est parcourue pour au moins un test. Ce critère a l’avantage d’être facile à mesurer en utilisant des outils open-source (option -fprofile-arcs dans GCC/Gcov).
Les artefacts seront d’une part, la méthode inventée pour générer mécaniquement une suite de tests, qui pourra être appliquée à d’autres problèmes similaires, et d’autre part, la suite de tests elle-même, qui aura une grande valeur immédiate pour identifier de possibles bugs dans les implémentations utilisées comme référence ou d’autres implémentations de parseurs X.509.
Remarque diverses :
- Le problème général de la génération automatique d’entrées avec un objectif de couverture structurelle du code cible a déjà été étudié. Des techniques existent qui passent très bien à l’échelle en pratique mais peuvent avoir des difficultés à générer les entrées qui couvrent les traitements profonds du code cible. D’autres semblent plus prometteuses sur le papier mais ont des difficultés pour traiter les logiciels cibles complexes. Utilisons les noms improbables AFL et KLEE pour ces catégories respectivement. Le but n’est pas de réinventer ces techniques qui ont déjà été l’objet d’années de recherches, mais de voir si elles peuvent être utilisées de manière créative dans un cas particulier, sans se limiter non plus à ces deux catégories de techniques.
- On peut s’attendre à trouver, si l’on cherche, deux sortes de corpus sur Internet :
- d’une part, des corpus construits pour illustrer la richesse du format X.509. On peut s’attendre à ce que ces corpus ne couvrent pas complètement les chemins d’erreur des implémentations de référence, mais seulement les chemins qui traitent les extensions non supportées.
- d’autre part, des corpus générés automatiquement en consacrant une quantité monumentale de ressources à l’application d’un outil de type AFL à une implémentation particulière. On peut s’attendre à ce que ces corpus ne couvrent pas les extensions non supportées par l’implémentation particulière visée, ni les divers chemins d’erreur que d’autres implémentations peuvent avoir. De tels corpus pourront être utilisés comme référence mais deux contraintes implicites de ce sujet REDOCS sont que des solutions ne sont pas “télécharger le corpus que Google a généré en y consacrant des milliards d’heures CPU” ni “utiliser des milliards d’heures CPU pour faire comme Google”.
- Dans les applications open-source utilisées comme référence, le parser X.509 sera probablement une fraction de la fonctionalité, d’où la nécessité de définir “couverture à 100%” d’une manière accomodante :
- Seules les fonctions atteintes (couverture > 0%) auront à être couvertes. Ce choix ne laisse qu’un petit souci possible avec les pointeurs de fonctions, qui pourra être détecté et résolu de manière ad-hoc.
- Pour une implémentation qui a d’autres fonctionnalités que de parser les certificats X.509, il y aura une fonction qui dispatche l’exécution selon la ligne de commande utilisée, qui sera partiellement couverte par une suite de tests qui ne fait que parser des certificats X.509. Ce cas sera facile à reconnaître.
- Il pourra y avoir des fonctions utilitaires générales qui ne sont utilisées que dans un cas particulier quand l’implémentation est utilisée uniquement pour parser des certificats X.509. Ceci est l’un des écueils classiques de la génération automatique de tests avec objectif de couverture structurelle. En pratique on investigue et on écrit une ligne de justification, en espérant que la situation ne se produira pas trop souvent. Il peut aussi y avoir des tests de robustesse qui ne peuvent pas être rendus faux, mais dans ce cas il sera possible de proposer aux développeurs de les transformer en assertions.
- Le sujet utilise les mots “semi-automatique”. Étant données les contraintes de temps, il sera possible de fournir une méthode dont certaines étapes sont décrites pour être effectuées manuellement par un humain sans aucune créativité. On pourra penser à Blaise Pascal écrivant des algorithmes alors que l’ordinateur n’a pas été inventé, ou encore à la définition originelle du mot “computer” en anglais comme un être humain qui applique mécaniquement un algorithme décrit en des termes de plus haut niveau qu’un programme informatique.