SPAM email
Aplicación de las Redes
Bayesianas a la detección de
correo basura
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
Bayesiana
Un 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 & Lin
2002 Pual Graham
2002 Brian Burton
2003 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
loo
k
20
years
younger
0
0
1
1
1
1
0
0
Modelo Básico:
Clase: (spam,legitimo)
P(s) = 0.5
P(l) = 1-P(s) = 0.5
Palabra:
nude
P(n / s) = 0.8
P(n / l) = 0.01
Objetivo: P(s/n)
P(n/s) P(s)
Regla Bayes: P(s/n) =
P(n)
P(n/s)P(n)
=
P(n/s)P(n) + P(n/l)P(l)
= 0.987
Clase: (spam, legitimo)
P(s) = 0.5
P(l) = 1-P(s) = 0.5
nude
P(n / s) = 0.8
girls P(g / s) = 0.7
P(g / l) = 0.2
P(n / l) = 0.01
Objetivo: P(s/n,g)
Regla Bayes: P(s/n,g) =
P(n,g/s) P(s)
P(n,g)
Cómo calculamos?
Aprovechamos la independencia representadas en la red:
Conocida la clase, los distintos términos se hacen independientes
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)
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 !!
En general,
spam
legitimo
........
ultimate porn
sex
ultimate porn sex
0
0
0
rich
rich
0
look
20
loo
k
20
years
1
1
years younger
younger
........
1
1
Características a considerar
I

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 considerar
II

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
Spam
36 (92%)
9
legitimo
3
175(95%)
total
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 subfrases conteniendo una combinación de las
palabras de la
3. Calcular un valor hash (32-bit) de estas subfrases.
B. Yerazunis CMR114
Paso 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)
Paso 2: generar las sub-frases a partir de las
palabras en cada ventana
Texto en la ventana:
‘Click here to buy viagra’
... Nos da las siguientes
sub-frases
Click
Click here
Click
to
Click here to
Click
buy
Click here
buy
Click
to buy
Click here to buy
Click
Click here
Click
to
Click here to
Click
buy
Click here
buy
Click
to buy
Click here to buy
viagra
viagra
viagra
viagra
viagra
viagra
viagra
viagra
Paso 3: obtener el valor hash de 32-bits a partir de
las sub-frases
Click
Click here
Click
to
Click here to
Click
buy
Click here
buy
Click
to buy
Click here to buy
Click
Click here
Click
to
Click here to
Click
buy
Click here
buy
Click
to buy
Click here to buy
viagra
viagra
viagra
viagra
viagra
viagra
viagra
viagra
32-bit hash
E06BF8AA
12FAD10F
7B37C4F9
113936CF
1821F0E8
46B99AAD
B7EE69BF
19A78B4D
56626838
AE1B0B61
5710DE73
33094DBB
B. Yerazunis CMR114
Evalua 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ético
Cabecera:
From no incluye un nombre real 1.149
To está vacio 2.497
Cuerpo:
XXX photos, 2.9
"No se puede considerar spam", 1
Clasificador Bayesiano con 99%, 5.200
El valor final se obtiene como una suma de los
distintos pesos
Umbral = 7
Acierto 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.

Descargar

decsai.ugr.es