SPAM III: Envenenamiento Bayesiano

No, no se trata de la última pelí­cula de Steven Seagal. Por petición de una mayorí­a de nuestros lectores, concretamente dos, vamos a cerrar la trilogí­a del SPAM (I, II) viendo porqué los spammers solo han perdido una batalla y no la guerra. Repasaremos las mejoras que han hecho los malos a sus tácticas y algoritmos de penetración (Envenenamiento Bayesiano, Whitelisting Troyano) y como los buenos no se ha quedado dormidos en su defensa de nuestra bandeja de entrada y han desarroyado algoritmos capaces de analizar el contexto del email (filtros Bayesianos-Markovianos). Hay que ver como le da al coco esta gente.

Cuando en el post pasado sobre el SPAM introducimos los filtros bayesianos vimos que la cosa consistí­a tan solo en contar con que frecuencia sale cada palabra en los mails normales y en los de SPAM. Con ayuda del Teorema de Bayes y unos cuantos miles de ejemplos de mails de SPAM y no SPAM, podí­amos calcular la probabilidad de que cualquier nuevo correo que recibiesesmos fuese SPAM o no dadas las palabras que contiene w₁, w₂,… w_n mediante la siguiente fórmula*:

_{(*) Como confundir un email normal como SPAM es mucho mas grave que confundir un email SPAM con uno normal. Esta fórmula se suele modificar un poco. Pero no afecta a lo que explicaremos aqui.}

Si uno mira un poco la fórmula, enseguida se da cuenta de qué es lo que puede fallar: Cada palabra contribuye de forma idéntica a la probabilidad total. Ni la posición, ni la coocurrencia en el mismo texto de las palabras se tiene en cuenta, solo la frecuencia con la que la palabra aparece. Es decir, que si yo soy un spammer puedo entrenar mi propio filtro atiespam, ver qué palabras reducen la probabilidad de ser detectado y colarlas al principio de mis emails para así­ burlar, al menos en un numero relevante de casos, los filtros. Esto se conoce como evenenamiento bayesiano (Bayesian Poisoning).

Los malos han encontrado además una forma muy inteligente de conseguir aún más precisión a la hora llenar el SPAM de palabras que reduzcan su probabilidad de ser detectados. El uso de los Web Bugs [Ing], enlaces a imágenes invisibles escondidos en el texto HTML del correo. Si el mail de SPAM se va a la papelera directamente, nadie lo lee, y el spammer puede clasificarlo como inefectivo. Si el mail pasa el filtro, al ser abierto por el usuario, cargara la imagen desde el servidor del spammer, proporcionandole no solo nuestra IP, si no confirmándole que el mail ha sido efectivo contra nuestro filtro. De esta forma un spammer puede entrenar de forma automática un envenenador bayesiano para su correo basura y especí­fico para nuestro filtro (puede asi tantear las configuraciones de los filtros de gmail o Yahoo! mail).

Filtros Bayesianos-Markovianos

Como contratacan los buenos?. En principio con lo obvio: bloquear el código HTML de imágenes de los mails a no ser que el usuario pida lo contrario (vease gmail). Aún así­ sigue el peligro de que la gente consteste al spam, confirmando a la vez la dirección como real y la efectividad del método de penetración. Es necesario eliminar la ingenuidad de los filtros bayesianos. Necesitamos ser capaces de incorporar información sobre la posición y correlación de las palabras en el texto de cada mail. Qué algoritmo estratosférico mejorara nuestros filtros?: Pues sí­mplemente el mismo filtro bayesiano pero en vez de contar las palabras, se cuentan las frases. La fórmula es la misma de antes, pero donde hay esas w₁,…w_n póngase f₁,…f_n. Para generar las frases solo hace falta añadir un preprocesamiento al algoritmo que ya vimos:

1. Se va recorriendo el mail con una ventana* de por ejemplo de longitud tres.
2. Para cada grupo de tres palabras obtenido, se construyen todas las combinaciones posibles, inluyendo la omisión de cada palabra.
3. Se le da un peso a cada combinación f según el número de palabras N que contenga. Los filtros markovianos emplean la siguiente fórmula:

   

   Esto es importante porque permite al contexto imponerse sobre la influencia de una palabra individual.

4. Se trata cada combinación exactamente igual a como tratabamos cada palabra: Se apunta el número de apariciones en nuestras muestras de SPAM y no SPAM.
5. Ahora, podemos coger cualquier correo nuevo, mirar las combinaciones de palabras que tiene y empleando la fórmula del principio del post, si la probabilidad es alta lo eliminamos. La fórmula tiene que ser de nuevo ligeramente modificada para admitir los pesos pero eso es todo.

_{(*) Ventana corredera: Se cogen las tres primeras palabras y se procesan, a continuación se cogen la segunda tercera y cuarta y así­ sucesivamente. Cada vez avanzamos una palabra.}

Asi de facil.

-Así­ de facil?. Combinaciones de palabras de miles de mails y hay que apuntarlas todas?.

Efectivamente, si ya era mucho contar las palabras, contar las combinaciones de palabras puede disparar el tamaño de nuestras listas. No obstante se hace. El procedimiento concreto puede ser un poco pesado para tratarlo aqui y además esta genialmente explicado en las fuentes del final del post. Por contar algo diré que el truco está en no guardar todas las frases entera si no guardar un conjunto limitado de ellas, descritas cada una por identificador unico* de 64 bits (lo que nos permite, con permiso de nuestro disco duro, manejar 1.8*10¹⁹ combinaciones).

Con estos filtros ya no vale colar algunas palabras al principio del post para engañar al algoritmo. Poner en su lugar texto convencional, copiado de periódicos digitales por ejemplo, puede mejorar la penetración pero en el momento en que el spammer empiece a largar sobre su producto ahi estará el filtro Bayesiano-Markoviano para mandarlo a la mierda. Ahora sí­ que tenemos a los malos arrinconados, verdad?… VERDAD?.

_{(*) Valla proliferacion de asteriscos, eh?. Esto quiere decir que empleo una transformacion que asigna a cada combinacion de palabras que exista en el universo un numero único de 64 bits. Dos combinaciones nunca pueden tener el mismo numero. Esta bien, es mentira… alguna colisioncilla hay pero no afecta demasiado a la efectividad y hace los calculos factibles.}

Whitelisting Troyano

Hire,
i am here sitting in the internet caffe. Found your email and
decided to write. I maight be coming to your place in 14 days,
so I decided to email you. May be we can meet? I am 25 y.o.
girl. I have a picture if you want. No need to reply here as
this i!s not my email. Write me at kdokn@BounceEmail.info

Este tipo de emails logran atravesar con cierta frecuencia mi filtro de gmail porque son exactamente iguales a un mail válido, con errores ortográficos y todo. Vale, esos no los podemos detectar, pero no anuncian nada, para que los usan?. Pues para que los estúpidos contesten.

Con esto consiguen, primero, identificar a los débiles mentales susceptibles de comprar su basura y mucho más importante: Al responder al mail, el ususario está metiendo esa direccion pirata automáticamente en la lista blanca de su filtro (lo explicabamos aqui), con lo que no será revisada por el algoritmo si se mandan mails desde ella. Felicidades caballero, acaba de bajar el puente levadizo y pintarse una enorme diana en el culo.

Algunos Flecos

Y llegamos al final, por supuesto buenos y malos seguiran dándole al coco sin parar hasta el final de los tiempos. Tácticas de los buenos como Inoculation y Minefielding se quedan en el tintero para otra ocasión (o a tiro de google). Yo por mi parte voy a hacer un par de aclaraciones, citar las fuentes y me voy, que Berlin está soleado que da gusto inundado por lluvias torrenciales, en fin repasaré el post a ver.

Fuentes empleadas para este post:

La primera está en la página del CRM114 regex mutilator, un filtro anti-spam Markoviano-Bayesiano en constante evolución. Presenta una visión general, algunos tests y resultados. No explica en detalle aspectos importantes pero da alguna información util. La segunda, de los laboratorios de Mitsubishi Electric, es una joya. Repasa los actuales sistemas anti-spam, explica en detalle todo el proceso y propone un modelo unificado para su definición y comparación. Más que recomedable si el tema te interesa.

Pasandonos por el forro las condiciones de Bayes

En el post anterior habí­amos explicado que al aplicar el teorema de Bayes, mirabamos a techo y silbabamos intentando evitar que alguien se diese cuenta de que existe una dependencia estadí­stica entre las palabras (contexto) que estabamos ignorando. El uso de frases en vez de palabras no hace el fltro más correcto matemáticamente, más bien alreves. Al contener las frases palabras en común su dependencia estadí­stica es aún mayor. No obstante los filtros funcionan mejor por la modelización que se hace del contexto asi que, de nuevo, disimulemos.

Modelos de Markov y redes neuronales:

Respecto al lo Markovianos de los filtros es importante tener en cuenta que el nombre se lo han puesto probablemente tras la ingestión masiva de cerveza en un brainstormig demasiado relajado (probablemente tras ver los resultados comparativos con los filtros convencionales). El filtro Bayesiando-Markoviano es un Filtro Bayesiano Ingenuo que emplea frases como fenomenos estadí­sticos a modelizar (features). No son modelos de Markov [Ing] de verdad porque serí­a computacionalmente intratable.

Respecto a las redes neuronales, parece que no vienen a cuento pero sí­. Al final, un filtro bayesiano es equivalente a un perceptrón, elemento unidad de la red neuronal artificial convencional, y por tanto está sujeto a las mismas limitaciones de separación lineal de clases. Algunos argumentan que el empleo de pesos en los filtros Bayesianos-Markovianos eliminan esta limitación, pero esta sin demostrar. El asunto viene comentado en las dos fuentes que cito e igual tiene interés para los amantes de estos algoritmos de base neurológica, cada vez más en desuso.