211service.com
Den oväntade spridningen av skräppostdetekteringsalgoritmer
Om du vill ta reda på om två skräppostmeddelanden är identiska utan att jämföra varenda byte i dem – vilket skulle ta onödigt lång tid – smälter du ihop filen till en kort sträng, känd som en kryptografiskt hashvärde . Det ligger i karaktären av en kryptografisk hashfunktion att även den minsta förändringen i en fil kommer att ge ett helt annorlunda hashvärde, så det är lätt att avgöra om två filer är identiska.
Från Wikipedia: En kryptografisk hashfunktion på jobbet. Observera att även små ändringar i källingången drastiskt förändrar den resulterande utsignalen.
Det här kan låta trivialt, men det är det inte: om du redan har ett exempel på en oönskad fil – säg ett skräppostmeddelande – och du vill jämföra det parvis med miljontals andra e-postmeddelanden som strömmar genom dina servrar, måste du kunna identifiera det snabbt. Att jämföra 40-siffriga strängar är betydligt lättare än att läsa miljontals e-postmeddelanden om penispiller hela vägen igenom.
Problemet med kryptografiska hashfunktioner är att även den minsta förändringen i källfilen ger ett hashvärde som är helt annorlunda. Med andra ord är de värdelösa för att jämföra filer som kan vara funktionellt identiska men bara lite annorlunda.
En lösning på detta problem är vad som kallas en fuzzy hash, eller en rullande hash: istället för att bara hasha hela filen, tillhandahåller algoritmen en kontinuerlig ström av hashvärden för ett rullande fönster över binären [av originalfilen] ],säger David French, seniorforskare vid Carnegie Mellons Software Engineering Institute.
Genom att jämföra ett gäng hash från två filer kan du bestämma den procentuella skillnaden mellan dem.
Ett tillvägagångssätt som generaliserar till... Allt?
Det är här fuzzy hashing blir riktigt användbart: plötsligt har du en generell metod för att snabbt jämföra några informationsström.
Så du ser luddiga hash som dyker upp överallt. Här är en insats av den tidigare nämnda Dr. French att använda fuzzy hash för att snabbt avgöra om en fil på en användares dator är ett virus eller annan skadlig kod. Och här är ett försök att använda fuzzy hash för att jämföra utkastet till gensekvensen av en mikroorganism till en känd sekvens från en besläktad varelse. Detta är enormt för genetiker, för vilka det snabbaste sättet att sammanställa ett någorlunda exakt genom från en tidigare osekvenserad varelse är att jämföra de sekvenserade fragmenten av dess gener med en känd sekvens.
Och har du någonsin undrat hur Google upptäcker duplicerat innehåll så att det bara kan ge dig de mest relevanta resultaten, istället för de hundratals exemplar av en nyhetsartikel eller referensverk som oundvikligen hamnar på sploggar spridda över Internet? Fuzzy hashing, igen ! Den kan till och med upptäcka identiska dokument som lagras i helt olika format:
*Ett vanliga fall är samma dokument men i olika format; i dessa fall kommer vi att ha helt andra dokument på binär nivå. Den uppenbara lösningen är att jämföra omvandlingar av vanlig text av alla dessa format, men dessa omvandlingar är aldrig identiska på grund av de olika behandlingarna av omvandlarna på olika formateringselement (behandling av texttecken, diakritiska tecken, mellanrum, stycken ...). I detta arbete introducerar vi möjligheten att använda vad som kallas fuzzy-hashing. Tanken är att ta fram fingeravtryck av filer (eller dokument, etc..). På så sätt kan en jämförelse mellan två fingeravtryck ge oss en uppskattning av närheten eller avståndet mellan två filer, dokument, etc.
Helvete, du kan se hur viktigt fuzzy hashing är eftersom Michael Gregory Hoglund från Monte Sereno, CA precis fick en ett heltäckande patent på processen , som han kallar generering av en digital DNA-sekvens för ett dataobjekt. Innan du vet ordet av kommer ett patenttroll att ha köpt den här från Höglund, och sedan kan det roliga börja.
Fuzzy hashes är en av dessa osynliga delar av VVS, som MapReduce-algoritmen som uppfanns av Google och som ligger till grund för praktiskt taget alla gigantiska webbtjänster du kan tänka dig, som är avgörande för driften av det globala hive-sinne som vi är beroende av.
När som helst en dator måste fråga, vilken av dessa saker är inte som den andra? Svaret är: Fråga en fuzzy hash-funktion!
