211service.com
Den uventede ubiquity af spam-detektionsalgoritmer
Hvis du vil finde ud af, om to spam-e-mails er identiske uden at sammenligne hver enkelt byte i dem – hvilket ville tage unødig lang tid – fordøjer du filen til en kort streng, kendt som en kryptografisk hashværdi . Det ligger i karakteren af en kryptografisk hash-funktion, at selv den mindste ændring i en fil vil give en helt anderledes hashværdi, så det er nemt at se, om to filer er identiske.
Fra Wikipedia: En kryptografisk hash-funktion på arbejde. Bemærk, at selv små ændringer i kildeinput ændrer det resulterende output drastisk.
Dette lyder måske trivielt, men det er det ikke: Hvis du allerede har et eksempel på en uønsket fil – f.eks. et stykke spam-e-mail – og du vil sammenligne det parvis med millioner af andre e-mails, der streamer gennem dine servere, skal du være i stand til at identificere det hurtigt. At sammenligne 40-cifrede strenge er betydeligt nemmere end at læse millioner af penispille-e-mails hele vejen igennem.
Problemet med kryptografiske hash-funktioner er, at selv den mindste ændring i kildefilen giver en hashværdi, der er helt anderledes. Med andre ord er de ubrugelige til at sammenligne filer, der kan være funktionelt identiske, men kun en lille smule anderledes.
En løsning på dette problem er det, der er kendt som en fuzzy hash eller en rullende hash: i stedet for blot at hash hele filen, giver algoritmen en kontinuerlig strøm af hash-værdier for et rullende vindue over den binære [af den originale fil] ],siger David French, seniorforsker ved Carnegie Mellon's Software Engineering Institute.
Ved at sammenligne en masse hashes fra to filer, kan du bestemme den procentvise forskel mellem dem.
En tilgang, der generaliserer til... Alt?
Det er her fuzzy hashing bliver virkelig nyttigt: Pludselig har du en generel metode til hurtigt at sammenligne nogen strøm af information.
Så du ser fuzzy hashes dukke op overalt. Her er en indsats fra førnævnte Dr. French at bruge fuzzy hashes til hurtigt at afgøre, om en fil på en brugers computer er en virus eller andet stykke malware. Og her er et forsøg på at bruge fuzzy hashes til at sammenligne udkastet til gensekvens af en mikroorganisme til en kendt sekvens fra et beslægtet væsen. Dette er enormt for genetikere, for hvem den hurtigste måde at samle et nogenlunde nøjagtigt genom fra et tidligere ikke-sekventeret væsen er at sammenligne de sekventerede fragmenter af dets gener med en kendt sekvens.
Og har du nogensinde undret dig over, hvordan Google registrerer duplikeret indhold, så det kun kan levere de mest relevante resultater til dig i stedet for de hundredvis af kopier af en nyhedsartikel eller opslagsværk, der uundgåeligt ender på splogs spredt over internettet? Fuzzy hashing igen ! Det kan endda registrere identiske dokumenter, der er gemt i helt forskellige formater:
*En hyppig sag er det samme dokument, men i forskellige formater; i disse tilfælde vil vi have helt andre dokumenter på binært niveau. Den oplagte løsning er at sammenligne almindelig tekstkonverteringer af alle disse formater, men disse konverteringer er aldrig identiske på grund af de forskellige behandlinger af konverterene på forskellige formateringselementer (behandling af tekstlige tegn, diakritiske tegn, mellemrum, afsnit …). I dette arbejde introducerer vi muligheden for at bruge det, der er kendt som fuzzy-hashing. Ideen er at producere fingeraftryk af filer (eller dokumenter osv..). På denne måde kunne en sammenligning mellem to fingeraftryk give os et skøn over nærheden eller afstanden mellem to filer, dokumenter osv.
For helvede, du kan se, hvor vigtigt fuzzy hashing er, fordi Michael Gregory Hoglund fra Monte Sereno, CA lige har modtaget en altomfattende patent på processen , som han kalder at generere en digital DNA-sekvens for et dataobjekt. Før du ved af det, vil en patenttrold have købt denne fra Hoglund, og så kan det virkelige sjov begynde.
Fuzzy hashes er en af de usynlige stykker VVS, som MapReduce-algoritmen opfundet af Google, der understøtter praktisk talt enhver gigantisk webservice, du kan komme i tanke om, og som er afgørende for driften af det globale hive-sind, som vi er afhængige af.
Når som helst en computer skal spørge, hvilken af disse ting er ikke som den anden? Svaret er: Spørg en fuzzy hash-funktion!
