Technique automatisée d’exploration de fonctions de hachage entières

 (github.com/skeeto)
3 points par GN⁺ 2024-05-06 | 1 commentaires | Partager sur WhatsApp
  • Hash Function Prospector est un outil qui génère aléatoirement en masse des fonctions de hachage entières, les compile en JIT pour évaluer leur comportement d’avalanche, puis affiche la meilleure fonction courante en syntaxe C
  • L’évaluation repose sur le score d’avalanche, c’est-à-dire le nombre moyen de bits de sortie qui restent inchangés lorsqu’on inverse un seul bit d’entrée ; plus il est faible, mieux c’est, et la valeur idéale est 0
  • La recherche vise des fonctions de hachage entières 32 bits et 64 bits ; à cause du compilateur JIT, l’exécution de l’outil lui-même n’est prise en charge que sur x86-64, mais les fonctions découvertes peuvent être utilisées dans d’autres environnements
  • Les principales fonctions découvertes utilisent une structure xorshift-multiply-xorshift ; la fonction lowbias32 en 2 rounds montre un biais plus faible, avec un très léger écart, que le finalizer 32 bits de MurmurHash3, et triple32 en 3 rounds s’approche de la limite théorique du biais
  • La mesure exacte du biais peut être effectuée pour les fonctions 32 bits avec -E et -e, tandis qu’un outil séparé, hp16, s’occupe des hachages 16 bits ; il faut faire attention aux règles de promotion des entiers en C

Rôle de Hash Function Prospector

  • Hash Function Prospector est un outil automatisé de découverte de fonctions de hachage entières
  • Il génère aléatoirement des dizaines de milliards de fonctions de hachage entières, les compile en JIT, puis évalue leur comportement d’avalanche
  • Parmi les fonctions générées, la meilleure à l’instant donné est affichée en syntaxe C
  • Un article associé, Prospecting for Hash Functions, est lié

Critères d’évaluation et périmètre pris en charge

  • Le score d’avalanche est le nombre moyen de bits de sortie qui restent inchangés lorsqu’on inverse un bit d’entrée
    • Plus le score est faible, mieux c’est
    • Idéalement, tous les bits de sortie s’inversent avec une probabilité de 50 %, ce qui donne un score de 0
  • Prospector peut générer des fonctions de hachage entières 32 bits et 64 bits
  • L’ensemble des options est disponible via l’aide -h
  • À cause du compilateur JIT, l’outil lui-même n’est pris en charge que sur x86-64
    • En revanche, les fonctions de hachage découvertes peuvent être utilisées partout

Opérations réversibles utilisées pour l’exploration

  • Le générateur compose aléatoirement des fonctions à partir de 9 opérations réversibles sélectionnées
  • La liste des opérations est la suivante
    • x = ~x
    • x ^= constant
    • x *= constant | 1
    • x += constant
    • x ^= x >> constant
    • x ^= x << constant
    • x += x << constant
    • x -= x << constant
    • x <<<= constant
    • x = bswap(x)
  • Techniquement, x = ~x peut être exprimé comme x ^= constant, mais comme il est peu probable que le générateur choisisse par hasard cette constante XOR, l’opération est traitée séparément

Fonctions de hachage 32 bits découvertes

  • Fonctions à 2 rounds

    • L’une des familles de fonctions utiles découvertes suit la structure xorshift-multiply-xorshift à 2 rounds
    • TheIronBorn a trouvé, à l’aide d’une optimisation combinatoire, les meilleurs paramètres connus de cette structure, avec le résultat [16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501
    • lowbias32 est une permutation 32 bits à 2 rounds, avec un faible biais, légèrement inférieur à celui du finalizer 32 bits de MurmurHash3
    • Le biais exact de lowbias32 est 0.17353355999581582
    • La structure a été découverte par Prospector, puis les paramètres ont été ajustés par hill climbing et algorithme génétique
    • L’inverse lowbias32_r est également fourni
    • prospector32 est une fonction découverte uniquement à l’aide de Prospector
    • Son biais exact est 0.34968228323361017
    • Son biais est plus élevé que celui de lowbias32 ci-dessus
    • Pour explorer aléatoirement des constantes de multiplication alternatives, il faut spécifier le motif suivant
    • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

  • Fonctions à 3 rounds

    • En ajoutant un round multiply-xorshift supplémentaire à la même structure, on peut atteindre la limite théorique du biais avec des paramètres soigneusement choisis
    • triple32 a un biais exact de 0.020888578919738908
    • Le README explique qu’elle est indiscernable d’une PRF parfaite, c’est-à-dire d’une permutation aléatoire de tous les entiers 32 bits
    • L’inverse triple32_r est également fourni
    • La liste des constantes à 3 rounds comprend des résultats de faible biais allant de 0.020888578919738908 à environ 0.022984943828687553
    • triple32inc, qui ajoute une opération d’incrémentation avant triple32, corrige le problème hash(0) = 0 et réduit encore légèrement le biais
    • Son biais exact est 0.020829410544597495
    • Son inverse triple32inc_r effectue x-- à la fin

Mesure exacte du biais

  • Le mode -E évalue le biais d’une fonction de hachage donnée
  • Par défaut, Prospector utilise une estimation pour évaluer rapidement le biais
    • Cette estimation n’est pas déterministe et les résultats sont bruités
  • Pour mesurer le biais exact par exploration exhaustive, on utilise l’option -e
  • La fonction à tester peut être définie de deux façons
    • avec -p et un motif
    • avec -l et une bibliothèque partagée contenant la fonction hash()
  • La méthode par bibliothèque partagée permet aussi de tester des fonctions de hachage qui ne peuvent pas être représentées dans le formalisme limité de Prospector
  • Par défaut, l’entrée est traitée comme une fonction de hachage 32 bits
  • Le commutateur -8 teste les fonctions 64 bits en mode estimation
    • Les fonctions de hachage 64 bits prennent trop de temps pour qu’un test exhaustif exact soit disponible

hp16 pour les hachages 16 bits

  • Les hachages 16 bits ayant des contraintes différentes, un outil séparé, hp16, est fourni
  • Contrairement à Prospector en 32 et 64 bits, hp16 est entièrement portable et peut s’exécuter sur presque tous les systèmes
  • hp16 peut aussi générer et évaluer des s-box de 128 KiB
  • Comme les hachages 16 bits peuvent être nécessaires sur des machines dépourvues d’instructions de multiplication rapides, il existe aussi des options pour omettre certaines opérations pendant l’exploration
    • -m
    • -r

Résultats 16 bits et précautions pour l’implémentation en C

  • Voici quelques exemples de résultats actuels en 16 bits
    • xorshift-multiply à 2 rounds hash16_xm2 : biais 0.0085905051336723701
    • xorshift-multiply à 3 rounds hash16_xm3 : biais 0.0045976709018820602
    • hash16_s6 sans multiplication : biais 0.023840118344741465
  • hash16_s6, sans multiplication, est présenté comme équivalent à une certaine forme de xorshift-multiply
  • Un bon hachage xorshift à 3 rounds trouvé rapidement avec hp16 -Xn3 est une bonne approximation d’une bonne s-box de hp16 -S
  • Lorsqu’on écrit des opérations 16 bits en C, il faut faire attention aux règles de promotion des entiers
    • Par exemple, dans une implémentation 32 bits, un opérande non signé de 16 bits peut être promu en entier signé 32 bits
    • Dans ce cas, cela peut produire un résultat incorrect dans certaines situations
    • Le code C généré par ce programme veille à promouvoir les opérations 16 bits en unsigned int lorsque c’est nécessaire

À lire aussi

1 commentaires

 
GN⁺ 2024-05-06
Avis de Hacker News

  • Je ne le connais pas personnellement, mais j’aime son code.
    J’aime particulièrement sa bibliothèque JSON https://github.com/skeeto/pdjson, ses bibliothèques d’analyse d’options https://github.com/skeeto/optparse et https://github.com/skeeto/getopt, son décodeur UTF-8 sans branchement https://github.com/skeeto/branchless-utf8, sa pile sans verrou https://github.com/skeeto/lstack et sa bibliothèque de trie https://github.com/skeeto/trie.
    J’aime aussi son goût en matière de licences, puisque tous les projets ci-dessus sont distribués sous The Unlicense.

    • Skeeto est une légende. Pour moi, il est du même calibre que Fabrice Bellard.
      Je le suis sur GitHub depuis des années, et il sort toujours de petits outils de niche étranges et intéressants. Branchless UTF-8 en est un exemple bien connu.
    • Il est aussi l’auteur de elfeed https://github.com/skeeto/elfeed, « An Emacs web feeds client », dont l’implémentation minimaliste m’a beaucoup inspiré.

  • Bonjour, je suis la personne qui a créé MurmurHash. C’est un travail intéressant, et c’est amusant de voir que l’approche multiplication-shift-XOR a si bien tenu dans le temps.

    • Le XOR-shift compense deux faiblesses de la multiplication : les bits de poids fort n’ont pas de bits au-dessus d’eux pouvant les influencer, et les bits de poids faible n’ont pas de bits en dessous d’eux dont ils peuvent subir l’influence.
    • Comme MurmurHash, ceux-ci semblent destinés à être des hachages non cryptographiques.
      Cela dit, il me semble que l’idée avalanche + biais laisse pas mal de choses de côté. Par exemple, la fonction triple32 listée à la fin a un biais exact de 0.020888578919738908, et si FabriceNeyret2 l’implémente dans ShaderToy, on obtient ce genre d’image : https://www.shadertoy.com/view/WttXWX ou https://i.imgur.com/qU2P5rx.png
      Mais si l’on applique une simple dérivation de pente de normal map, on voit apparaître pas mal de lignes de « cristaux » bien visibles. Il existe sans doute un terme technique pour ce genre de crêtes : https://i.imgur.com/IHWT1GM.png
      Au passage, il me semble que toute cette idée date déjà d’il y a environ 5 ans : https://nullprogram.com/blog/2018/07/31/

  • Ayant eu l’occasion de développer de bonnes fonctions de hachage, j’ai souvent pensé à l’idée de recherche automatique de hachages.
    C’est chouette de voir ce genre de travail. Il serait intéressant de le brancher sur SMHasher3, une variante bien améliorée et plus rapide de l’ancienne suite de tests de hachage de Frank J. T. Wojcik, afin d’évaluer automatiquement les sorties. On pourrait aussi n’utiliser qu’une partie des tests pour aller vite, avec un échec rapide.
    L’étendre aux hachages 64 bits et 128 bits serait aussi intéressant, mais l’espace de recherche devient évidemment plus grand. À ce sujet, j’avais aussi écrit du code NodeJS pour mesurer l’avalanche sur la multiplication par des nombres premiers 64 bits, afin de choisir des valeurs pour Rain.
    [Rain]: https://github.com/dosyago/rain
    [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

  • Il serait intéressant de généraliser cela aux opérations disponibles dans l’extension de manipulation de bits de RISC-V. On pourrait découvrir des fonctions robustes à utiliser plus tard, lorsque ces instructions seront plus largement déployées.
    La multiplication sans retenue peut aussi élargir l’ensemble des opérations réversibles, et elle est rapide sur certains matériels existants. Le CRC est aussi lié dans une certaine mesure, mais disponible sur un ensemble de matériels plus large, et devrait être un sous-ensemble strict de ce que CLMUL peut trouver.
    Comme beaucoup d’usages du hachage ne s’intéressent qu’aux bits de poids faible ou aux bits de poids fort de la valeur de hachage, il serait aussi intéressant d’évaluer le biais des plages de bits de poids fort/faible, ou les restes modulo plusieurs nombres. Une fonction qui semble non biaisée sur la sortie complète peut devenir meilleure ou pire selon des métriques qui n’observent pas toute la sortie, ou avec des entrées non uniformes comme du texte ASCII.

  • Quelqu’un peut expliquer pourquoi c’est cool et à quoi ça sert ?

    • Ça ressemble à un outil qui génère des séquences d’instructions pour créer des fonctions de hachage, puis évalue la qualité de ces fonctions
      L’objectif semble être que, lorsqu’un bit d’entrée change, autant de bits de sortie que possible changent de façon aussi aléatoire que possible. Il produit le code C de la meilleure fonction de hachage parmi celles générées
      C’est donc utile quand on a besoin d’une fonction de hachage mais qu’on estime que les fonctions existantes ne sont pas assez bonnes, ou quand on étudie les fonctions de hachage et qu’on a besoin de nouvelles idées de structures. La génération de code en elle-même est cool, et le faire au hasard est un premier pas vers quelque chose d’encore plus cool : la programmation génétique. Et les humains semblent aimer, depuis environ 15 ans, faire brûler des cycles CPU aux ordinateurs pour calculer des hachages qui ne serviront presque jamais
    • Ces fonctions sont indispensables aux tables de hachage. On trouve aussi les noms associés hash map et hash set
      Une table de hachage est une excellente structure de données qui permet d’implémenter de nombreux algorithmes de façon simple et efficace. Cette efficacité dépend de la capacité à produire un hachage petit pour les données, par exemple sur 32 ou 64 bits, et presque unique
      Par exemple, pour hacher des noms d’utilisateur, si on n’utilise que le code ASCII de la première lettre du nom, beaucoup de noms d’utilisateur seront mappés vers le même nombre, et ça fonctionnera mal. C’est ce qu’on appelle une collision, et quand il y en a beaucoup, une table de hachage devient très inefficace
      Une meilleure approche consiste à prendre des bits dans tout le nom d’utilisateur et à les mélanger d’une manière ou d’une autre, afin que throwaway_1237 et throwaway_12373 donnent des nombres différents. La fonction de hachage effectue ce mapping, et la propriété d’avalanche décrit à quel point elle évite bien les collisions
      En général, il y a un compromis entre la vitesse d’une fonction de hachage réelle et sa capacité à éviter les collisions. Les fonctions de hachage de tout premier plan ont souvent une allure assez étrange, avec des multiplications par des constantes bizarres, des XOR, des décalages, etc., et il est très difficile pour un humain d’estimer les performances d’une telle fonction absconse en la regardant
      Ce code essaie aléatoirement plusieurs fonctions de hachage et les fait s’affronter. Si ça marche, c’est cool parce que cela peut améliorer les performances réelles d’une structure de données fondamentale utilisée dans de nombreux langages et bibliothèques
    • Comme ce sont des fonctions de hachage pour entiers, on peut les utiliser quand on a besoin d’un hachage rapide d’entiers dans des ensembles ou des maps. Si les fonctions divergent suffisamment les unes des autres, elles fournissent aussi des hachages rapides pour des filtres de Bloom

  • Il y a quelques semaines, j’ai implémenté 1brc en Go https://github.com/infogulch/1brc-go, et ce dépôt m’a donné envie de chercher une fonction de hachage parfaite sur mesure pour que chaque station d’observation tombe dans son propre bucket sans collision
    Puis j’ai vu la règle qui interdit de personnaliser la fonction de hachage en fonction des données avant le démarrage du programme, et j’ai abandonné l’idée
    J’avais créé un banc de test qui essayait des constantes arbitraires, des valeurs initiales, des constantes de multiplication, des quantités de décalage/rotation, etc., et affichait les meilleures constantes trouvées jusque-là selon le nombre de buckets en collision et le nombre de collisions. Je crois être descendu, avec un taux de remplissage d’environ 40 %, à seulement deux valeurs en collision dans un unique bucket. Fait intéressant, les constantes les plus performantes incluaient des nombres de positions de décalage similaires indépendamment des autres constantes, donc j’ai fini par coder ces valeurs en dur

    • À noter qu’il existe de meilleures techniques pour trouver des fonctions de hachage parfaites minimales. Celle-ci est plutôt facile à implémenter : https://cmph.sourceforge.net/chd.html

  • Ce serait vraiment intéressant de pouvoir fournir son propre générateur de données d’entrée. En pratique, les données ne sont souvent pas binaires et aléatoires, mais structurées d’une manière ou d’une autre, et cette structure pourrait permettre d’obtenir une très bonne fonction de hachage

  • Se limiter à des opérations réversibles présente des avantages mathématiques, mais exclut aussi beaucoup de choses
    Quand j’ai fait quelque chose de similaire, je pensais au hachage parfait, où l’ensemble des entrées est connu à l’avance. L’approche classique utilise un tableau de constantes, mais je voulais voir s’il était possible de compresser davantage, surtout si les entrées sont déjà de petits entiers. Évidemment, c’est possible avec des formes du type hash -= hash >> gap_index
    J’ai donc essayé une liste d’environ 100 opérations primitives. Certaines se recoupaient entre elles, mais il était utile de les considérer séparément. Puis je me suis lassé et je n’en ai rien fait comme projet

    • Quels sont ces « avantages mathématiques » quand on se limite à des opérations réversibles, et pourquoi les opérations réversibles sont-elles souhaitables dans ce contexte ?

  • Je ne comprends pas exactement ce que ça fait. Est-ce que ça cherche le meilleur résultat jamais obtenu ? Sinon, je me demande pourquoi la meilleure valeur change à chaque exécution
    Je me demande aussi si quelqu’un connaît un mécanisme pour découvrir une bonne fonction de hachage quand on sait que les entiers appartiennent à une plage donnée, par exemple uniquement entre 10 000 et 200 000, afin de les placer dans un nombre optimal de buckets de hachage

    • C’est une approche qui essaie des valeurs au hasard pour trouver la meilleure parmi celles testées pendant cette exécution
      Il n’est pas réaliste de parcourir tout l’espace de recherche en une seule exécution pour trouver l’optimum absolu, et comme l’ordre des essais est aléatoire, les valeurs peuvent changer d’une exécution à l’autre
      Si vous avez simplement besoin d’un « bon » hachage, le mieux est presque toujours d’utiliser une fonction de hachage générique. Si les nombres sont très grands et que la plage est très petite, vous pouvez appliquer un offset pour ramener la valeur minimale à 0 et utiliser un hachage plus petit et plus rapide. Si vous voulez trouver le « choix parfait » pour une plage précise, cette approche aléatoire est probablement ce qui s’en rapproche le plus, et il suffit de modifier le test pour qu’il s’exécute sur cet intervalle

  • Je me demande si utiliser la même constante pour deux multiplications ne réduirait pas la taille du code, ce qui pourrait aussi rendre le calcul légèrement plus rapide
    J’ai aussi mis à jour la réponse StackOverflow : https://stackoverflow.com/questions/664014/what-integer-hash...