Cómo funciona un filtro anti-spam

En los últimos 2 meses he recibido en mi cuenta de gmail 2053 correos basura, de los cuales aproximadamente un 98.5% se han ido directamente a la papelera. Se calcula que entre el 70% y el 80% del mail circulando es SPAM. En un post anterior explicamos el origen de este fenómeno y qué podí­amos hacer para reducirlo. Ahora veremos como se las arreglan Google, Yahoo & Cia para mantener nuestra bandeja de entrada los más limpia posible mediante algoritmos inteligentes (y algunos no tan inteligentes). Como siempre con la mí­nima cantidad de matemáticas posibles.

Un filtro antiespam es en realidad la combinación de varias técnicas diferentes. Por organizarlo un poco podrí­amos llamarlas: Listas Negras, Listas Blancas y Discriminación Inteligente:

Listas negras (Blacklists):

Es el procedimiento más simple. Si se tiene toda la seguridad de que una determinada dirección de correo es de un spammer, simplemente se manda directamente todos sus mails a la papelera y asunto arreglado. Por supuesto esto no es tan facil porque las direcciones de correo (los dominios) se pueden falsificar y están apareciendo nuevas fuentes de spam constantemente. Hay muchas organizaciones (lista) dedicadas al la creación de listas negras, que despues venden esta información a los ISPs (proveedores de internet).

Lamentablemente estas organizaciones no son completamente de fiar y en ocasiones introducen direcciones equivocadas en sus listas. Y lo que es peor piden dinero para salir de ellas (experiencia personal con el proveedor de listas negras de Netcom). Al final, esto ha causado unas cuantas demandas judiciales (inglés) que le han arreado directamente en la linea de flotación a este método. No obstante como primera linea de defensa contra el SPAM y manejadas con cuidado siguen siendo efectivas.

Las listas blancas son menos radicales y se emplean para no tener que revisar todo el correo con nuestros algoritmos (esto puede suponer un ahorro de recurso considerable). Simplemente consiste en una lista de direcciones que no hace falta revisar como por ejemplo:

• Direcciones oficialmente reconocidas como no SPAM, las newletters de periódicos, o clubes conocidos.
• Tu lista segura. Servicios de correo como por ejemplo hotmail te permite confeccionar una.
• Tu lista de contactos, así­ que no metas a ningun spammer en ella.
• En general, direcciones a las que has mandado mails. Se supone que nunca vas a cartearte con un robot emite correo.

Al igual que las negras, las listas blancas, pueden ser burladas si se disfraza la dirección de correo para simular una conocida. Qué dirección puede conocer un spammer de tus contactos?. Pues la tuya misma. Por ejemplo en mi cuenta hotmail recibo periódicamente un correo de SPAM que simula tener mi propia dirección (en mayusculas). El zoquete del filtro me advierte (una vez abierto) que la dirección no ha podido ser certificada por el sender ID (un acuerdo de Microsoft y cia para poder identificar direcciones). Muy habil.

íšltimamente los spammers consiguen emular direcciones de listas de distribución de correo conocidas y llegar directamente a nuesta bandeja de entrada. No obstante esto no es tan crí­tico como que manden tus mails a la papelera.

Discriminación inteligente

Los dos metodos anteriores, a parte de su limitado porcentaje de eficiencia, tienen una pega fundamental. La adaptabilidad. De 2006 a 2007 la cantidad de SPAM se ha doblado de 31.000.000 a 60.000.000 según computerworld ( ejemplo gráfico del periodo 1997-2004). Este es un negocio en alza y los spammers están continuamente cambiando de estrategia para burlar las mejoras en los filtros. Para vencerlos no basta con una decena de becarios picando código de perl, tenemos que automatizar el aprendizaje nuevos criterios de discriminación. Es posible diseñar un algoritmo que haga eso?. Sí­, hay múltiples formas pero una de ellas, por su sencillez y efectividad, se ha comido con patatas a todas las demás en los últimos años:

Los filtros Bayesianos

Si pasando rápidamente la vista por los mails no leidos en tu Outlook o gmail ves la palabra «Viagra». Sabes que hay una muy alta probabilidad de que sea SPAM. Lo mismo con «Vicodin», «Xanax», «Penis enlargement», etc… Es decir, hay un conjunto de palabras, que por su significado, aparecen mucho más frecuentemente en los textos del SPAM que en los mails convencionales. De hecho, si tuviesemos, como tienen las empresas de correo electrónico, millones de ejemplos de SPAM y de correos convencionales, podrí­amos hacer lo siguiente:

• 1. Hacemos una lista con todas las palabras que aparecen en el total de nuestros correos (tanto SPAM como no SPAM).
• 2. Cogemos cada palabra de la lista y apuntamos cuantas veces sale en correos de SPAM y cuantas veces sale en correos no de SPAM.
• 3. Ahora, podemos coger cualquier correo nuevo, mirar las palabras que tiene y puntuarlo según contenga más o menos palabras que aparecen frecuentemente en el SPAM. Si contiene demasiadas lo eliminamos.

Asi de facil. Este sistema no solo es extraordinariamente sencillo, si no que nos permite incorporar nueva información sobre el cambiante SPAM simplemente añadiendo los nuevos mails de SPAM a nuestra base de datos. El usuario puede también incrementar nuestra base de datos gracias al lazo de realimentacion (hey! en el dibujo) o incluso crear sus propia base de datos particular. Esto último les hace más complicada la vida a los spammers a la hora de despistar a los filtros con un método general.

Matemáticamente, lo que estamos haciendo es utilizar la probabilidad condicionada que define el teorema de Bayes de ahi abajo, donde w₁, w₂,… w_n serí­an las palabras que contiene el mail que estamos analiz… Sal de debajo de la meeeesa!, ya sé que tienes un trauma desde selectividad con Bayes, pero de verdad que es una gilipollez.

Basta con sabe leer lo que pone. Primero olvidemonos de las probabilidades P(algo) esas. Los hombres de verdad las substituimos por el numero de casos en los que ocurre algo, dividido por el total de casos que estudiamos, y pista!*. Respecto a la barrita esa vertical de dentro de la P, eso es la probabilidad condicionada. Que simplemente significa que a la hora de contar casos, nos tenemos que restringir a los casos en los que también se da lo que viene a la derecha de la barrita. Ahora si, verdad?. Olvidandonos de la ecuacion intermedia del dibujo podemos leer:

La probabilidad de que el correo que analizamos sea SPAM dadas las palabras w₁, w₂,… w_n que contiene, son iguales a la probabilidad de ocurrencia del SPAM, en general, multiplicado por la probabilidad de cada una de esas palabras cuando las encontramos en el SPAM (lo que calculamos en 2.) y dividido por la probabilidad de ocurrencia de esas palabras.

Supongo que todaví­a habra algún despistado que diga que el paso de la ecuacion intermedia a la de abajo del dibujo requiere la independencia estadí­stica de las palabras entre sí­ y que eso no se cumple. Pues claro que no se cumple!, pero funciona!. Y no solo no se cumple, las palabras en un texto tienen una gran dependencia estadí­stica entre sí­. La aparición de una palabra suele afectar a la probabilidad de la aparición de otra enormemente. Lo llamamos contexto y es lo que empleamos los humanos para intepretar los mensajes. No obstante, si tengo que elegir entre tragar con este fallo teórico, o con mi bandeja llena de ofertas para alargarme el pene, prefiero lo primero.

_{(*) Huelga decir que los hombres de verdad que hacen eso sin la suficiente cantidad de casos totales y que simultaneamente son ingenieros, tienden a intersectarse con el conjunto de los hombres parados en un plazo relativamente corto de tiempo. Si eres un matemático y coges menos de infinitos casos para aproximar una probabilidad, tengo entendido que te empalan en una hiper-esfera de |R⁴}

Pequeños Flecos

Si todaví­a no se han dado cuenta de que hace un buen rato que no estas trabajando en la hoja de cálculo y te quedan ganas de leer, hay cosas bastante interesantes por ahi:

Un Plan para el SPAM:

Excelente artí­culo (ingles) que me introdujo en el mundo de los filtros anti-spam. Es casi todo texto eso si, pero profundiza un poquito más que yo sin llegar a ser pesado matemáticamente. También merece la pena visitar la colección gráfica (ingles) de SPAM de Raymond Chen, que contiene la imagen que enlacé más arriba.

Una Implementación Real:

Esto ha sido una introducción muy general a los filtros atiespam modernos. En realidad no tenemos que limitarnos a las palabras como elemento discriminantes. Podemos coger grupos de palabras cercanas y añadir otros criterios. El uso de expresiones regulares tambien incrementa mucho la eficiencia de los filtros. Actualmente los filtros Bayesianos-Markovianos son los que mejores resultados estan dando. Si quieres ver una implementación real puedes visitar la página del CRM114 (ingles). También tienen Papers disponibles.

Matemáticas, matemáticas, quiero matemáticas:

Bueno pues si sabes ingles, no es ningún problema. En esta (ingles) página de la wikipedia encontraras mucha información sobre los clasificadores bayesianos. Por ejemplo se suele emplear la probabilidad de SPAM dividida por la probabilidad de no SPAM como parametro para discriminar, es el llamado ratio de verosimilitud. Manipulando esa expresion, y si no me he equivocado, puede demostrarse que los filtros bayesianos convencionales están limitados a clases separables linealmente [amantes de las redes neuronales hacen la ola].