Aplicación de las Redes Bayesianas a la detección de
correo basura
SPAM email
Introducción Que es correo basura?
– correo no solicitado, generalmente corresponde a campañas publicitarias
Mensajes sexuales, ganar dinero rápidamente, ...
Por qué es un problema?– Económico: Implica un coste al usuario, uso
ancho de banda y espacio de disco– Mensajes importantes pueden ser borrados
cuando eliminamos bloques de forma rápida.
Es necesario "Filtrar" dichos mensajes
El negocio del correo spam
Una batería típica de spam puede tener un total de 1.000.000 de correos.
El spammer tiene una comisión media de 250$ por batería
Si asumimos que el receptor gana $5.15/hora y dedica 2 seg para borrar un spam, tenemos un coste 2.816$
Métodos para eliminar el spam
Listas negras de orígenes: – Eliminar TODOS los email enviados por un determinado
origen. Fuerzan al sitio a chequear el uso incorrecto por spammers.
(ORBS y SPEWS)(?) Puede ser ilegal!!
Listas negras de documentos: – Se utilizan valores hash de documentos enteros (en
lugar de almacenar el documento completo) siendo fáciles de transmitir.
(?) Un mínimo cambio en el documento, modifica el valor hash
Métodos para eliminar el spam
Uso de palabras clave:– Eliminan los mensajes que contengan dichas
palabras clave, independientemente de si son realmente spam o no.
(?) Se evitan insertando separadores, cometiendo errores ortográficos, etc.
Emparejamientos heurísticos:– Hacen uso del experto humano para identificar
reglas que hacen que permitan identificar el correo spam
(?) Necesita el experto humano
Métodos para eliminar el spam
Uso de Listas blancas:– En este caso, todo mail se asume como spam
salvo que tenga su origen en una lista blanca. En caso de detectar un spam se envía un email al remitente para permitir detectar si es un origen válido (e incluirlo en la lista) o no.
Filtros probabilísticos:– Permiten adaptarse a los cambios y ser
personalizados por los usuarios
Filtros probabilísticos Son una buena solución
– Determinan el grado de confianza con el que un determinado email es clasificado como spam
El costo de clasificar incorrectamente un correo spam es mucho menor que el de clasificar
incorrectamente un correo legítimo
Uso de clasificadores bayesianos
Aproximación BayesianaUn clasificador Bayesiano es una Red Bayesiana
aplicada a tareas de clasificación– Naive bayes
Ampliamente utilizado en los últimos años para realizar filtros.1998: Sahami et al (Microsoft): 1998: Pantel & Lin2002 Pual Graham2002 Brian Burton2003 W. Yerazunis Éxito mas que aceptable. Se diferencia en el conjunto de
variables que utilizan así como en el cálculo de probabilidades.
– Modelos más complejos (?)
Modelo Básico: Las características de un mensaje se
representan como un vector: Modelo de Espacio Vectorial.
Cada dimensión se corresponde con una posible palabra que puede aparecer en un email
ultimate porn sex rich look 20 years younger
0 0 0 0 1 1 1 1
nude
Modelo Básico:
Clase: (spam,legitimo)
Palabra:
P(s) = 0.5P(l) = 1-P(s) = 0.5
P(n / s) = 0.8P(n / l) = 0.01
Objetivo: P(s/n)
Regla Bayes: P(s/n) = P(n/s) P(s)
P(n)
P(n/s)P(n)
P(n/s)P(n) + P(n/l)P(l)= = 0.987
girlsnude
Clase: (spam, legitimo)
P(s) = 0.5
P(l) = 1-P(s) = 0.5
P(n / s) = 0.8
P(n / l) = 0.01
P(g / s) = 0.7
P(g / l) = 0.2
Objetivo: P(s/n,g)
Regla Bayes: P(s/n,g) = P(n,g/s) P(s)
P(n,g) Cómo calculamos?
P(n,g/s) =P(n/s)P(g/s)
P(n,g) = P(n,g,s) + P(n,g,l) =P(n,g/s) P(s) + P(n,g/l)P(l) =
P(n/s)P(g/s)P(s) + P(n/l)P(g/l)P(l)
Aprovechamos la independencia representadas en la red:
Conocida la clase, los distintos términos se hacen independientes
P(s/n,g) =P(n/s)P(g/s)P(s)
P(n/s)P(g/s)P(s) + P(n/l)P(g/l)P(l)= 0.996 !!
spamlegitimo
youngeryears20sex lookrichpornultimate
ultimate porn sex rich look 20 years younger
0 0 0 0 1 1 1 1
En general,
........
........
Características a considerarI Información textual específicas del correo
spam
– Palabras como Free, Money, “be over 21”, $$$
Por ejemplo en Sahami et al. utilizan 35 de estas características seleccionadas de forma manual a partir de filtros basados en reglas
Características a considerarII Información de tipo no textual,
– Nombre del dominio (.edu, .com)– Numero de receptores del mensaje– Dirección del correo (si nos conocida)– Lleva attachments– Hora de envio (los mensajes spam se suelen
enviar de noche)– Porcentaje de caracteres no alphanumerico,
Sahami utiliza 20 de estas características.
Selección de Características
Idea: Extraer aquellos rasgos de un correo que lo hacen ser spam– Mirar cuantas veces se ha visto una
característica en correos spam y legítimos– Crear una probabilidad para cada
característica– Combinar las probabilidades individuales
de las características
Selección de Características
Problema:– El espacio de variables para características textuales
es MUY grande (del orden de miles de variables) Ventajas de realizar la selección:
– Reducción del modelo: permite tener un control explícito sobre el modelo (un mejor ajuste)
– Atenúa el efecto de considerar la independencia entre variables.
– Utilizar todos las palabras hace que sea difícil de detectar los spam largos (disminuye la probabilidad a posteriori), abriendo la puerta para los spammers.
Filtrado Bayesiano El clasificador Bayesiano debe ser
entrenado considerando un conjunto representativo de mensajes email.
Es conveniente no ajustar las características sobre el mismo conjunto de datos que el utilizado para el aprendizaje
Entonces puede ser utilizado para la detección de correo spam.
Modelo Sahami Selección de Características:
– Utiliza la ley de Zipf: elimina las palabras que aparecen menos de 3 veces
– Calcula la cantidad de información mutua entre cada característica y la clase, seleccionando las de mayor valor (500):
MI(Xi,C) = P(Xi,C) log [P(Xi,C)/P(Xi)P( C)]
Un mensaje es considerado spam si la probabilidad a posteriori es mayor que 0.999
Resultados sobre escenario real:
Clasif.spam Clasif. legitimo total
Spam
legitimo
36 (92%)
3
9
175(95%)
45
177
Pantel y Lin Tienen un % de éxito del 92%, con
1.16% de falsos positivos. Ignoran las cabeceras de los
mensajes Hacen un stemming de las palabras No hacen selección de características
Modelo de Paul Grahan Su trabajo “A plan for Spam” tuvo una
gran repercusión pues podía detectar el 99.5% del correo spam con menos del 0.03% de falsos positivos.
Actualmente, una redefinición de lo que es una característica a considerar le permite identificar el 99.75% del correo spam.
Modelo de Paul Graham “I don´t think it’s a good idea to treat spam
filtering as a straight text classification problem. You can use text classification techniques, but solution can and should reflect the fact that the text is email, and spam in particular.
Spam is not just text; it has structure”
P. Graham. “Better bayesian filtering” Enero, 2003
Modelo Paul Graham La definición de palabra (token) es:
– Se preservan las mayúsculas/minúsculas– Las exclamaciones son caracteres válidos.– Puntos y comas se consideran si ocurren entre
dos dígitos.– Los rangos como 20-30$ se transforman en dos
tokens– Diferencia cuando un mismo token ocurre en la
seccion TO, FROM, SUBJECT, dentro de URL. Por ejemplo P(spam|”free”) = 0.6546 y la P(spam|Subject*free) =
0.9999
Modelo de P. Graham Para calcular las probabilidades considera
los 15 tokens más significativos. Introduce un sesgo para evitar los falsos
positivos.– Cuenta doblemente la ocurrencia de los tokens
en email legítimos. Puede conocer hasta un total de 187.000
tokens,
Modelo Brian Burton (SpamProbe)
Diferencias con el modelo de P. Graham– Diferente criterio a la hora de buscar los tokens.– Utiliza además pares de palabras– Utiliza la frecuencia de las palabras dentro del
documento.– Elimina códigos HTML para evitar falsos
positivos– Codifica los caracteres con 8 bits
Alcanza el 99.7% de efectividad
B. Yerazunis CMR114
El objetivo es crear MUCHAS características, que pueden estar invariantemente a lo largo del cuerpo del correo spam.
1. Mover una ventana de N palabras sobre el texto de entrada.
2. Para cada posición generar un conjunto de sub-frases conteniendo una combinación de las palabras de la
3. Calcular un valor hash (32-bit) de estas sub-frases.
B. Yerazunis CMR114Paso 1: Mover una ventana de N palabras sobre el
You can Click here to buy viagra online NOW!!!
You can Click here to buy viagra online NOW!!!
You can Click here to buy viagra online NOW!!!
You can Click here to buy viagra online NOW!!!
You can Click here to buy viagra online NOW!!!
... Y así sucesivamente ... (al paso 2)
Click Click hereClick toClick here toClick buyClick here buyClick to buyClick here to buy Click viagraClick here viagraClick to viagraClick here to viagra Click buy viagraClick here buy viagraClick to buy viagraClick here to buy viagra
... Nos da las siguientes sub-frases
Texto en la ventana: ‘Click here to buy viagra’
Paso 2: generar las sub-frases a partir de las palabras en cada ventana
Click Click hereClick toClick here toClick buyClick here buyClick to buy Click here to buyClick viagraClick here viagraClick to viagraClick here to viagra Click buy viagraClick here buy viagraClick to buy viagraClick here to buy viagra
Paso 3: obtener el valor hash de 32-bits a partir de las sub-frases
32-bit hash
E06BF8AA12FAD10F7B37C4F9113936CF1821F0E846B99AADB7EE69BF19A78B4D56626838AE1B0B615710DE7333094DBB
B. Yerazunis CMR114Evalua las características con un clasificador
Naive Bayes !!!!
Entrenado con 400Kbytes de spam seleccionado, 300Kbytes de email legitimo, sin listas negras, ni listas blancas, ...
Obtiene un porcentaje de éxito del 99.915%
SpamAssassin Utilizado en decsai !!!! Abanico de test heurísticos:
– Análisis de cabeceras: Los spamer utilizan un conjunto de "trucos" para enmascarar el correo spam
– Análisis de texto: Buscar las características del correo spam.
– Listas Negras: mail-abuse.org, ordb.org– Navaja: Vipul's Razor es una base de datos
colaborativa que contiene firmas de mensajes spam.
Ejemplos de test Obtiene probabilidades y después asigna pesos
utilizando un algoritmo genéticoCabecera:From no incluye un nombre real 1.149To está vacio 2.497
Cuerpo:XXX photos, 2.9"No se puede considerar spam", 1Clasificador Bayesiano con 99%, 5.200
El valor final se obtiene como una suma de los distintos pesosUmbral = 7Acierto 99%, Falsos positivos 0.1%
Es necesario seguir trabajando?
El correo spam muta, tratando de eludir los filtros.
Por tanto, la efectividad del un clasificador bajará con el tiempo.
Se estima que cada mes aparecen entre 1 y 3 nuevos métodos.