211service.com
L'ubiquità inaspettata degli algoritmi di rilevamento dello spam
Se vuoi scoprire se due email di spam sono identiche senza confrontare ogni singolo byte in esse - il che richiederebbe un tempo eccessivo - digerisci il file in una breve stringa, nota come valore hash crittografico . È nella natura di una funzione hash crittografica che anche la più piccola modifica in un file produca un valore hash molto diverso, quindi è facile dire se due file sono identici.
Da Wikipedia: una funzione hash crittografica al lavoro. Si noti che anche piccoli cambiamenti nell'input della sorgente modificano drasticamente l'output risultante.
Può sembrare banale, ma non lo è: se hai già un esempio di un file indesiderato, ad esempio un'e-mail di spam, e vuoi confrontarlo a coppie con milioni di altre e-mail in streaming attraverso i tuoi server, devi essere in grado di identificarlo rapidamente. Confrontare stringhe di 40 cifre è significativamente più facile che leggere milioni di e-mail di pillole per il pene fino in fondo.
Il problema con le funzioni hash crittografiche è che anche la più piccola modifica nel file sorgente produce un valore hash completamente diverso. In altre parole sono inutili per confrontare file che possono essere funzionalmente identici ma solo leggermente diversi.
Una soluzione a questo problema è il cosiddetto hash fuzzy, o hash rolling: invece di eseguire l'hashing dell'intero file, l'algoritmo fornisce un flusso continuo di valori hash per una finestra mobile sul binario [del file originale ],dice David French, ricercatore senior presso il Software Engineering Institute di Carnegie Mellon.
Confrontando un mucchio di hash da due file, puoi determinare la differenza percentuale tra loro.
Un approccio che generalizza a... tutto?
È qui che l'hashing fuzzy diventa davvero utile: all'improvviso, hai un metodo generico per confrontare rapidamente qualunque flusso di informazioni.
Quindi vedi hash sfocati spuntare dappertutto. ecco uno sforzo del suddetto Dr. French utilizzare hash fuzzy per determinare rapidamente se un file sul computer di un utente è un virus o un altro malware. e ecco un tentativo di utilizzare hash fuzzy per confrontare la sequenza del gene bozza di un microrganismo a una sequenza nota di una creatura correlata. Questo è enorme per i genetisti, per i quali il modo più veloce per assemblare un genoma ragionevolmente accurato da una creatura precedentemente non sequenziata è confrontare i frammenti sequenziati dei suoi geni con una sequenza nota.
E ti sei mai chiesto come Google rileva i contenuti duplicati in modo da poterti fornire solo i risultati più pertinenti, invece delle centinaia di copie di un articolo di notizie o di un lavoro di riferimento che inevitabilmente finiscono negli splog diffusi su Internet? Hashing sfocato, di nuovo ! Può persino rilevare documenti identici che sono archiviati in formati completamente diversi:
*Un caso frequente è quello dello stesso documento ma in formati diversi; in questi casi avremo documenti completamente diversi a livello binario. La soluzione ovvia è confrontare le conversioni di testo normale di tutti questi formati, ma queste conversioni non sono mai identiche, a causa dei diversi trattamenti dei convertitori sui vari elementi di formattazione (trattamento dei caratteri testuali, segni diacritici, spaziatura, paragrafi …). In questo lavoro introduciamo la possibilità di utilizzare il cosiddetto fuzzy-hashing. L'idea è quella di produrre impronte di file (o documenti, ecc.). In questo modo, un confronto tra due impronte digitali potrebbe darci una stima della vicinanza o distanza tra due file, documenti, ecc.
Diavolo, puoi dire quanto sia importante l'hashing fuzzy perché Michael Gregory Hoglund di Monte Sereno, CA ha appena ricevuto un brevetto onnicomprensivo sul processo , che chiama generazione di una sequenza di DNA digitale per un oggetto dati. Prima che tu te ne accorga, un troll dei brevetti avrà comprato questo da Hoglund, e quindi il vero divertimento può iniziare.
Gli hash fuzzy sono uno di quei pezzi invisibili dell'impianto idraulico, come l'algoritmo MapReduce inventato da Google che è alla base praticamente di ogni gigantesco servizio web a cui puoi pensare, che è fondamentale per il funzionamento della mente alveare globale da cui dipendiamo.
Ogni volta che un computer deve chiedere, quale di queste cose non è come l'altra? La risposta è: chiedi una funzione di hash fuzzy!
