211service.com
L'ubiquité inattendue des algorithmes de détection de spam
Si vous voulez savoir si deux e-mails de spam sont identiques sans comparer chaque octet qu'ils contiennent - ce qui prendrait un temps excessif - vous digérez le fichier en une courte chaîne, connue sous le nom de valeur de hachage cryptographique . C'est dans la nature d'une fonction de hachage cryptographique que même le plus petit changement dans un fichier produira une valeur de hachage très différente, il est donc facile de dire si deux fichiers sont identiques.
De Wikipedia : Une fonction de hachage cryptographique au travail. Notez que même de petits changements dans l'entrée source modifient considérablement la sortie résultante.
Cela peut sembler trivial, mais ce n'est pas le cas : si vous avez déjà un exemple de fichier indésirable - disons un courrier indésirable - et que vous souhaitez le comparer par paires à des millions d'autres e-mails diffusés sur vos serveurs, vous devez être en mesure de l'identifier rapidement. Comparer des chaînes à 40 chiffres est beaucoup plus facile que de lire des millions d'e-mails de pilules pour pénis.
Le problème avec les fonctions de hachage cryptographique est que même le plus petit changement dans le fichier source donne une valeur de hachage complètement différente. En d'autres termes, ils sont inutiles pour comparer des fichiers qui peuvent être fonctionnellement identiques mais seulement un peu différents.
Une solution à ce problème est ce qu'on appelle un hachage flou ou un hachage glissant : au lieu de simplement hacher l'intégralité du fichier, l'algorithme fournit un flux continu de valeurs de hachage pour une fenêtre glissante sur le binaire [du fichier d'origine ],dit David French, chercheur principal au Software Engineering Institute de Carnegie Mellon.
En comparant un tas de hachages de deux fichiers, vous pouvez déterminer la différence en pourcentage entre eux.
Une approche qui se généralise à… tout ?
C'est là que le hachage flou devient vraiment utile : du coup, vous avez une méthode polyvalente pour comparer rapidement quelconque flux d'informations.
Vous voyez donc des hachages flous apparaître partout. Voici un effort du Dr. French susmentionné utiliser des hachages flous pour déterminer rapidement si un fichier sur l'ordinateur d'un utilisateur est un virus ou un autre logiciel malveillant. Et voici une tentative d'utiliser des hachages flous pour comparer la séquence de gène brouillon d'un micro-organisme à une séquence connue d'une créature apparentée. C'est énorme pour les généticiens, pour qui le moyen le plus rapide d'assembler un génome raisonnablement précis à partir d'une créature précédemment non séquencée est de comparer les fragments séquencés de ses gènes à une séquence connue.
Et vous êtes-vous déjà demandé comment Google détecte le contenu en double afin qu'il ne puisse vous fournir que les résultats les plus pertinents, au lieu des centaines d'exemplaires d'un article d'actualité ou d'un ouvrage de référence qui se retrouvent inévitablement sur des splogs répartis sur Internet ? Hachage flou, encore ! Il peut même détecter des documents identiques qui sont stockés dans des formats complètement différents :
*Un cas fréquent est celui du même document mais dans des formats différents ; dans ces cas, nous aurons des documents complètement différents au niveau binaire. La solution évidente est de comparer les conversions en texte brut de tous ces formats, mais ces conversions ne sont jamais identiques, du fait des traitements différents des convertisseurs sur divers éléments de mise en forme (traitement des caractères textuels, diacritiques, espacements, paragraphes…). Dans ce travail, nous introduisons la possibilité d'utiliser ce que l'on appelle le flou flou. L'idée est de produire des empreintes de fichiers (ou documents, etc.). Ainsi, une comparaison entre deux empreintes digitales pourrait nous donner une estimation de la proximité ou de la distance entre deux fichiers, documents, etc.
Bon sang, vous pouvez dire à quel point le hachage flou est important parce que Michael Gregory Hoglund de Monte Sereno, CA vient de recevoir un brevet global sur le procédé , qu'il appelle générer une séquence d'ADN numérique pour un objet de données. Avant que vous ne le sachiez, un troll breveté aura acheté celui-ci à Hoglund, et alors le vrai plaisir pourra commencer.
Les hachages flous sont l'un de ces éléments de plomberie invisibles, comme l'algorithme MapReduce inventé par Google qui sous-tend pratiquement tous les services Web géants auxquels vous pouvez penser, qui est essentiel au fonctionnement de l'esprit-ruche mondial dont nous dépendons.
Chaque fois qu'un ordinateur doit se demander, laquelle de ces choses n'est pas comme l'autre ? La réponse est : demandez une fonction de hachage floue !
