L’incident où malloc a cassé le JPGLoader de Serenity, ou : la méthode pour gagner à la loterie (2021)

 (sin-ack.github.io)
1 points par GN⁺ 2024-07-08 | 1 commentaires | Partager sur WhatsApp
  • L’erreur de couleur JPG de SerenityOS ressemblait à un problème d’ordre des arguments RGB/BGR, mais elle venait en réalité du fait que JPGLoader confiait l’ordre de composants nécessitant un ordre précis à l’ordre d’itération d’une HashTable
  • Avec l’introduction de malloc_good_size() dans AK+LibC, Vector et HashTable se sont mis à exploiter la taille réelle des chunks malloc, ce qui a modifié le nombre de buckets de la HashTable et révélé un bug caché
  • Le code existant lisait par hasard les composants JPG Y, Cb, Cr dans le bon ordre ; la correspondance entre le résultat de int_hash et le nombre de buckets masquait une erreur de traitement du flux de Huffman
  • La recherche de la cause a commencé alors que JPGLoader.cpp n’avait pas été modifié récemment, et pendant un bisect sur 1 000 commits, des changements dans AK ont imposé plusieurs reconstructions complètes de l’OS, soit environ 3 400 fichiers
  • Le correctif final a consisté à parcourir les composants dans un ordre déterministe ; se contenter de changer l’ordre des arguments de couleur n’aurait été qu’un expédient susceptible de recréer le même problème au prochain changement d’ordre

Une erreur de couleur JPG qui ressemblait à une confusion RGB/BGR

  • Dans SerenityOS, l’ouverture d’images JPG provoquait un affichage incorrect des couleurs
  • En changeant l’ordre des arguments du constructeur Color dans JPGLoader.cpp, l’image semblait redevenir normale
    • Code existant : passage dans l’ordre Y, Cb, Cr
    • Changement provisoire : passage dans l’ordre Cr, Cb, Y
  • Mais le dernier changement non-revert récent de JPGLoader.cpp remontait, d’après Git, à plus d’un mois, et le souvenir était qu’une image de fond JPG s’affichait correctement une à deux semaines auparavant
  • Il devenait donc probable qu’il ne s’agissait pas d’une simple erreur d’ordre des canaux de couleur, mais qu’un autre changement avait exposé un bug existant

Un bisect rendu difficile par les changements dans AK

  • SerenityOS utilise sa propre bibliothèque standard, AK (Agnostic Kit)
    • AK joue un rôle proche de la STL C++, mais évolue dans le même dépôt que le code du système d’exploitation
  • Quand AK change, la portée de l’impact est large
    • La bibliothèque standard est incluse par presque tout le code
    • Les templates C++ devant être définis dans les headers, une modification des headers d’AK déclenche de vastes recompilations
  • À chaque commit contenant un changement dans AK, il fallait reconstruire tout le système d’exploitation
    • Environ 3 400 fichiers au moment de l’écriture
    • Pendant le bisect sur une plage de 1 000 commits, une compilation complète a été effectuée 4 à 5 fois sur un ordinateur portable Sandy Bridge Mobile de 2011
  • ccache n’a pas pu gérer ce cas, et en raison du rythme rapide des changements dans le projet SerenityOS, AK était modifié environ une fois tous les 100 commits

Le problème caché révélé par malloc_good_size()

  • Après avoir bisecté 1 000 commits, le changement qui cassait les couleurs JPG a été trouvé non pas dans JPGLoader, mais du côté de AK+LibC
  • Le commit qui révélait le problème était f89e8fb71a4893911ee5125f34bd5bbb99327d33
    • Titre : AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable
    • Date : 15 mai 2021
  • Ce commit implémente l’API macOS malloc_good_size()
    • Elle renvoie, pour une taille d’allocation demandée, la taille réellement allouée
    • Par exemple, si une demande de 35 octets utilise en interne un chunk de 64 octets, les 29 octets restants peuvent être exploités
  • Après ce changement, Vector, HashTable et d’autres structures ont commencé à mieux utiliser la mémoire disponible dans les chunks malloc
  • Comme l’image JPG s’affichait correctement au commit précédent, la piste s’est resserrée autour de ce changement comme révélateur d’un problème caché existant

Un décodage qui dépendait de la capacité de la HashTable

  • Au départ, le soupçon portait sur un éventuel code dans JPGLoader ou dans du code de plus haut niveau qui dépendrait à tort de la capacité d’un Vector pour y écrire directement
  • Le changement concernait à la fois HashTable et Vector, tous deux utilisés dans le code de JPGLoader
  • En supprimant au hasard la ligne appliquant kmalloc_good_size() côté HashTable, puis en reconstruisant, le problème a disparu
    • Le code supprimé était la partie qui ajustait la nouvelle capacité en buckets à la taille réelle allouée
  • Ce résultat a confirmé qu’un changement du nombre de buckets de la HashTable influençait le résultat du décodage JPG
  • Une HashTable n’étant pas un conteneur destiné à être utilisé comme un flux de données contigu, sa capacité ou son ordre d’itération ne devaient pas être des dépendances du code

La manière dont les composants JPG étaient traités

  • L’ancien JPGLoader lisait les informations de composants dans la section Start of Frame du fichier JPG et les stockait dans une structure Component
  • Chaque Component possédait un serial_id indiquant sa position dans le fichier JPG
    • L’ordre des composants JPG doit généralement être Y, Cb, Cr
  • Ces composants étaient stockés dans une HashTable
    • Ils étaient ensuite utilisés pour vérifier que l’ordre des composants dans la section Start of Scan correspondait à l’ordre attendu
  • À l’étape du décodage, ces composants étaient parcourus afin d’utiliser les informations nécessaires à la transformation des macroblocs
  • Le problème venait du fait que des composants pour lesquels l’ordre est important étaient placés dans une HashTable, puis parcourus avec l’itérateur par défaut

Différence d’ordre d’itération entre le commit cassé et le commit fonctionnel

  • Dans le commit produisant les couleurs cassées, la sortie de debug parcourait les composants dans l’ordre suivant
    • 0
    • 2
    • 1
  • Dans le commit fonctionnel précédent, l’ordre était différent
    • 0
    • 1
    • 2
  • Cette différence se traduisait par un résultat ressemblant à une inversion des canaux de couleur
  • En modifiant manuellement l’ordre des composants avec CxByte, l’erreur suivante est apparue
    • Huffman stream exhausted. This could be an error!
    • Failed to build Macroblock 3277
  • Cette erreur a montré que le décodage JPG était sensible à l’ordre du flux, et a confirmé que l’ordre de parcours des composants était la cause principale

Un ordre de HashTable qui tombait juste par hasard

  • La cause fondamentale était le stockage d’objets nécessitant un ordre dans une HashTable, puis leur parcours via l’itérateur par défaut
  • Le hash des ID de composants JPG passait par int_hash pour sélectionner les buckets
  • Jusqu’alors, deux hasards coïncidaient
    • Les résultats de int_hash pour les valeurs 0, 1, 2 étaient stables
    • Le nombre de buckets de AK::HashTable tombait juste pour placer les composants dans le bon ordre
  • Grâce à cette coïncidence, JPGLoader lisait le flux de Huffman dans le bon ordre pour chaque composant, et le bug était masqué depuis le début
  • L’introduction de malloc_good_size() a modifié le nombre de buckets de la HashTable, ce qui a changé l’ordre des composants et fait apparaître des images où les canaux rouge et bleu étaient inversés

Le correctif final : un parcours déterministe

  • Après environ 10 heures de debug, un commit de correction a été créé
  • Le commit de correction est a10ad24c760bfe713f1493e49dff7da16d14bf39
    • Titre : LibGfx: Make JPGLoader iterate components deterministically
    • Date : 31 mai 2021
  • Le cœur du correctif était de faire en sorte que JPGLoader parcoure les composants dans un ordre déterministe
  • Changer simplement l’ordre des arguments de Color faisait aussi paraître l’image normale sur le moment, mais un autre changement ultérieur de l’ordre d’itération aurait pu la casser à nouveau
  • Ce qui ressemblait à une petite erreur d’affichage s’est révélé être un cas où une dépendance incorrecte à l’ordre d’itération d’un conteneur et un changement de taille d’allocation se sont combinés pour exposer un bug

À lire aussi

1 commentaires

 
GN⁺ 2024-07-08
Commentaires Hacker News

  • C’est l’une des raisons pour lesquelles beaucoup d’implémentations de tables de hachage introduisent un élément aléatoire dans l’algorithme
    Comme l’ordre des éléments change à chaque exécution, si l’on dépend de cet ordre par erreur, le problème apparaît rapidement
    Si l’algorithme de hachage est fixe, on peut fabriquer des clés qui se retrouvent dans le même bucket et les exploiter pour une attaque par déni de service ; ce mécanisme aide aussi assez bien à prévenir ce type de problème de sécurité

    • De nos jours, à l’inverse, beaucoup d’implémentations garantissent que la table de hachage sera toujours parcourue dans l’ordre d’insertion
      Je préfère cette approche, parce qu’elle évite de devoir décider à chaque fois si l’on a besoin d’une map triée ou non triée
      Il m’est arrivé plusieurs fois de penser qu’une map non triée suffisait, pour découvrir que c’était faux pour des raisons subtiles
    • Si l’élément aléatoire est une graine qui peut être forcée, enregistrée, loguée et reproduite, très bien
      Sinon, c’est vraiment une mauvaise idée, car cela rend le débogage d’autres problèmes beaucoup plus difficile
      Le hasard n’est pas un ami, c’est un ennemi
      Il y a une vingtaine d’années, une attaque contre les serveurs web Java consistait à manipuler les paramètres d’URL pour qu’ils tombent tous dans le même bucket, ce qui provoquait une grosse attaque par déni de service
      Si ma mémoire est bonne, les serveurs web PHP ont connu exactement le même problème de sécurité
      Cela a été corrigé en ajoutant une graine à la table de hachage, et cette graine était évidemment contrôlable par le développeur. Parce que le hasard n’est pas un ami, c’est un ennemi

  • Cela ressemble à un cas où un peu plus de débogage aurait fait gagner du temps, plutôt que de faire à l’aveugle une recherche dichotomique par bisect
    Les logs affichant l’ordre des composants devaient de toute façon finir par être ajoutés

  • Le débogage était bon, mais le message de commit est lui aussi excellent
    Il condense très bien la cause et le correctif en quelques paragraphes

  • Si l’on attend assez longtemps, C++ finira aussi par avoir une fonctionnalité équivalente à malloc_good_size
    https://github.com/cplusplus/papers/issues/18

  • Le titre a besoin de [2021]

  • Ce n’est pas la faute de Gunnar. Le problème vient de ceux qui ont stocké des données ordonnées dans un fichier de hachage
    En plusieurs décennies dans ce métier, j’ai vu plusieurs fois des situations où un changement dans l’agencement mémoire révélait un bug caché
    À chaque fois, le débogage prend de quelques heures à plusieurs jours
    Si la programmation n’était pas difficile, on n’aurait pas besoin de nous. Je ne sais simplement pas combien de temps cette phrase tiendra encore à l’ère des grands modèles de langage

    • Exact. Même si c’était la faute de Gunnar, il ne me semble pas nécessaire de l’écrire dans le message de commit
      Gunnar a amélioré quelque chose, et cela n’a fait que révéler un problème dans un vieux code cassé
      Mais en récompense de cet effort, il se retrouve avec une phrase comme « Gunnar, I like you, but please don't make me go through this again. :^) »
    • Tant que les grands modèles de langage seront entraînés sur du code bogué, ils proposeront du code bogué
    • Exact. Et contrairement au titre, ce n’est pas non plus la faute de malloc()

  • Il me semble que SerenityOS dispose de ressources de test ou de personnes qui s’entraident avec des PC

  • Avoir compilé SerenityOS 4 ou 5 fois depuis zéro sur un portable Sandy Bridge Mobile de 2011, c’est un peu comme essayer de faire du développement Windows Vista sur un ordinateur sorti entre Windows 3.1 et Windows 95

    • En termes d’intervalle de temps, oui, mais pas en termes de performances réelles
      Depuis 2011, les CPU n’ont pas évolué de façon aussi spectaculaire, alors qu’entre Windows 3.1 et Vista, le x64 s’est démocratisé et les CPU multicœurs sont devenus courants
    • Bonne comparaison. Le CPU du développeur a environ 13 ans
      Vista est sorti à l’international début 2007 ; un CPU vieux de 13 ans au moment de cette sortie daterait donc de 1994, environ un an après l’arrivée du Pentium original
      À l’époque, beaucoup de gens utilisaient encore un bon vieux 486 DX2-66 fiable
      Le fait qu’un CPU vieux de 13 ans puisse encore servir aujourd’hui sur un projet moderne est assez impressionnant. À l’époque, on aurait difficilement pu en dire autant
      J’espère que les CPU qui sortent aujourd’hui resteront utilisables de façon satisfaisante au-delà de 2037
    • Depuis un an, j’utilise comme poste principal un Lenovo i5 de 2011 avec Windows 11 et deux écrans
      Visual Studio tourne bien, et Photoshop aussi, à part les outils d’IA intégrés au système qui sont juste un tout petit peu lents
      J’ai probablement environ 200 onglets Chrome ouverts, avec Slack, WhatsApp et trois navigateurs de test en plus
      Pour le montage 4K, j’aimerais que CapCut soit un peu plus rapide, mais il tient très bien sur des projets 2K complexes
      Il ne commence à atteindre ses limites que sur des projets After Effects complexes. Ça, il n’aime pas
      Il faudra que je fasse une mise à niveau, mais pour une machine récupérée quasiment à la poubelle, c’est plutôt pas mal

  • En voyant « Alien Lenna », j’ai eu une impression de déjà-vu ; effectivement, c’était un article que j’avais déjà lu et même commenté
    https://news.ycombinator.com/item?id=27374942 (2021)