211service.com
La ubicuidad inesperada de los algoritmos de detección de spam
Si desea averiguar si dos correos electrónicos no deseados son idénticos sin comparar cada byte en ellos, lo que llevaría una cantidad de tiempo indebida, digiera el archivo en una cadena corta, conocida como valor hash criptográfico . Está en la naturaleza de una función hash criptográfica que incluso el cambio más mínimo en un archivo producirá un valor hash tremendamente diferente, por lo que es fácil saber si dos archivos son idénticos.
De Wikipedia: una función hash criptográfica en funcionamiento. Tenga en cuenta que incluso los pequeños cambios en la entrada de la fuente cambian drásticamente la salida resultante.
Esto puede parecer trivial, pero no lo es: si ya tiene un ejemplo de un archivo no deseado, digamos un correo electrónico no deseado, y desea compararlo por pares con millones de otros correos electrónicos que se transmiten a través de sus servidores, debe poder hacerlo. identificarlo rápidamente. Comparar cadenas de 40 dígitos es significativamente más fácil que leer millones de correos electrónicos de píldoras para el pene de principio a fin.
El problema con las funciones hash criptográficas es que incluso el cambio más mínimo en el archivo de origen produce un valor hash que es completamente diferente. En otras palabras, son inútiles para comparar archivos que pueden ser funcionalmente idénticos pero solo un poco diferentes.
Una solución a este problema es lo que se conoce como hash difuso, o hash rodante: en lugar de simplemente aplicar hash a todo el archivo, el algoritmo proporciona un flujo continuo de valores hash para una ventana móvil sobre el binario [del archivo original ],dice David French, investigador senior del Instituto de Ingeniería de Software de Carnegie Mellon.
Al comparar un montón de hashes de dos archivos, puede determinar la diferencia porcentual entre ellos.
Un enfoque que se generaliza a ... ¿todo?
Aquí es donde el hash difuso se vuelve realmente útil: de repente, tienes un método de propósito general para comparar rápidamente ningún flujo de información.
Entonces ves que aparecen hashes difusos por todas partes. Aquí está un esfuerzo del Dr. French antes mencionado utilizar hashes difusos para determinar rápidamente si un archivo en la computadora de un usuario es un virus u otra pieza de malware. Y aquí hay un intento de usar hashes difusos para comparar la secuencia de genes en borrador de un microorganismo a una secuencia conocida de una criatura relacionada. Esto es enorme para los genetistas, para quienes la forma más rápida de ensamblar un genoma razonablemente preciso a partir de una criatura previamente no secuenciada es comparar los fragmentos secuenciados de sus genes con una secuencia conocida.
¿Y se ha preguntado alguna vez cómo detecta Google el contenido duplicado para poder ofrecerle solo los resultados más relevantes, en lugar de los cientos de copias de un artículo de noticias o trabajo de referencia que inevitablemente terminan en splogs esparcidos por Internet? Hash difuso, de nuevo ! Incluso puede detectar documentos idénticos que están almacenados en formatos completamente diferentes:
* Un caso frecuente es el de un mismo documento pero en diferentes formatos; en estos casos tendremos documentos completamente diferentes a nivel binario. La solución obvia es comparar conversiones de texto plano de todos estos formatos, pero estas conversiones nunca son idénticas, debido a los diferentes tratamientos de los convertidores sobre varios elementos de formato (tratamiento de caracteres textuales, diacríticos, espaciado, párrafos…). En este trabajo presentamos la posibilidad de utilizar lo que se conoce como fuzzy-hashing. La idea es producir huellas dactilares de archivos (o documentos, etc.). De esta forma, una comparación entre dos huellas dactilares podría darnos una estimación de la cercanía o distancia entre dos archivos, documentos, etc.
Demonios, puede decir cuán importante es el hash difuso porque Michael Gregory Hoglund de Monte Sereno, CA acaba de recibir una patente que lo abarca todo sobre el proceso , que él llama generar una secuencia de ADN digital para un objeto de datos. Antes de que te des cuenta, un troll de patentes habrá comprado este en Hoglund, y entonces puede comenzar la verdadera diversión.
Los hashes difusos son una de esas piezas invisibles de fontanería, como el algoritmo MapReduce inventado por Google que sustenta prácticamente todos los servicios web gigantes que puedas imaginar, que son fundamentales para el funcionamiento de la mente colmena global de la que dependemos.
Cada vez que una computadora debe preguntar: ¿Cuál de estas cosas no es como la otra? La respuesta es: ¡Pregunte a una función hash difusa!
Sigue a Mims en Twitter o contáctalo por correo electrónico .