De onverwachte alomtegenwoordigheid van spamdetectie-algoritmen

Als je wilt weten of twee spam-e-mails identiek zijn zonder elke byte erin te vergelijken - wat een onnodige hoeveelheid tijd zou vergen - verwerk je het bestand in een korte string, een zogenaamde cryptografische hashwaarde . Het ligt in de aard van een cryptografische hashfunctie dat zelfs de kleinste wijziging in een bestand een enorm verschillende hashwaarde oplevert, dus het is gemakkelijk te zien of twee bestanden identiek zijn.

Van Wikipedia: een cryptografische hashfunctie aan het werk. Merk op dat zelfs kleine veranderingen in de broninvoer de resulterende uitvoer drastisch veranderen.

Dit klinkt misschien triviaal, maar dat is het niet: als je al een voorbeeld hebt van een ongewenst bestand – zeg maar een stukje spam-e-mail – en je wilt het paarsgewijs vergelijken met miljoenen andere e-mails die via je servers worden gestreamd, moet je in staat zijn om identificeer het snel. Het vergelijken van reeksen van 40 cijfers is aanzienlijk eenvoudiger dan het lezen van miljoenen penispil-e-mails helemaal.

Het probleem met cryptografische hashfuncties is dat zelfs de kleinste wijziging in het bronbestand een hashwaarde oplevert die totaal anders is. Met andere woorden, ze zijn nutteloos voor het vergelijken van bestanden die functioneel identiek kunnen zijn, maar slechts een klein beetje anders.

Een oplossing voor dit probleem is wat bekend staat als een fuzzy hash of een rolling hash: in plaats van alleen het hele bestand te hashen, biedt het algoritme een continue stroom hash-waarden voor een rollend venster over de binaire [van het originele bestand] ],zegt David Frans, een senior onderzoeker bij Carnegie Mellon's Software Engineering Institute.

Door een aantal hashes van twee bestanden te vergelijken, kunt u het procentuele verschil daartussen bepalen.

Een benadering die generaliseert naar ... Alles?

Dit is waar fuzzy hashing echt handig wordt: plotseling heb je een algemene methode om snel te vergelijken ieder stroom van informatie.

Dus je ziet overal vage hashes opduiken. Hier is een poging van de eerder genoemde Dr. French om fuzzy hashes te gebruiken om snel te bepalen of een bestand op de computer van een gebruiker een virus of ander stukje malware is. En hier is een poging om fuzzy hashes te gebruiken om de concept-gensequentie te vergelijken van een micro-organisme naar een bekende sequentie van een verwant wezen. Dit is enorm voor genetici, voor wie de snelste manier om een ​​redelijk nauwkeurig genoom samen te stellen van een voorheen niet-gesequentieerd wezen is om de fragmenten van de genen waarvan de sequentie is bepaald, te vergelijken met een bekende sequentie.

En heb je je ooit afgevraagd hoe Google dubbele inhoud detecteert, zodat het je alleen de meest relevante resultaten kan opleveren, in plaats van de honderden exemplaren van een nieuwsartikel of naslagwerk die onvermijdelijk op splogs op internet terechtkomen? Fuzzy hashing, alweer ! Het kan zelfs identieke documenten detecteren die in totaal verschillende formaten zijn opgeslagen:

*Een veelvoorkomend geval is dat van hetzelfde document maar in verschillende formaten; in deze gevallen hebben we totaal verschillende documenten op binair niveau. De voor de hand liggende oplossing is om platte tekstconversies van al deze formaten te vergelijken, maar deze conversies zijn nooit identiek, vanwege de verschillende behandelingen van de converters op verschillende formatteringselementen (behandeling van tekstuele karakters, diakritische tekens, spatiëring, alinea's ...). In dit werk introduceren we de mogelijkheid om gebruik te maken van wat bekend staat als fuzzy-hashing. Het idee is om vingerafdrukken te maken van bestanden (of documenten, enz..). Op deze manier zou een vergelijking tussen twee vingerafdrukken ons een schatting kunnen geven van de nabijheid of afstand tussen twee bestanden, documenten, enz.

Verdorie, je kunt zien hoe belangrijk fuzzy hashing is omdat Michael Gregory Hoglund van Monte Sereno, CA zojuist een alomvattend patent op het proces , die hij het genereren van een digitale DNA-sequentie voor een data-object noemt. Voordat je het weet, heeft een patenttrol deze van Hoglund gekocht, en dan kan het echte plezier beginnen.

Fuzzy hashes zijn een van die onzichtbare stukjes loodgieterswerk, zoals het door Google uitgevonden MapReduce-algoritme dat ten grondslag ligt aan praktisch elke gigantische webservice die je maar kunt bedenken, dat van cruciaal belang is voor de werking van de wereldwijde bijenkorf waarvan we afhankelijk zijn.

Elke keer dat een computer moet vragen: Welke van deze dingen is niet zoals de andere? Het antwoord is: Vraag een fuzzy hash-functie!

Volg Mims op Twitter of neem contact met hem op via e-mail .

zich verstoppen