PDF de programación - Sistema de análisis y filtraje de correo masivo no solicitado SPAM

CENTRO DE INVESTIGACI ´ON Y DE ESTUDIOS
AVANZADOS DEL INSTITUTO POLIT´ECNICO

NACIONAL

DEPARTAMENTO DE INGENIER´IA EL´ECTRICA

SECCI ´ON DE COMPUTACI ´ON

Sistema de an´alisis y filtraje de correo

masivo no solicitado SPAM

Tesis que presenta

Francisco Javier Alejandro Lagunes

Para obtener el grado de

Maestro en Ciencias

en la Especialidad de

Ingenier´ıa El´ectrica

opci´on Computaci´on

Director de la tesis:

Dr. Arturo D´ıaz P´erez

M´exico, D.F.

Julio 2005

ii

Resumen

El uso del correo electr´onico como medio de comunicaci´on y transmisi´on de informaci´on
va en aumento debido a su eficiencia y facilidad de uso. Desafortunadamente, por estas
mismas caracter´ısticas es utilizado para enviar correos masivos no solicitados (SPAM).
Los ´ındices de correo SPAM van en aumento, y por ello son necesarias t´ecnicas y m´etodos
para abatir este problema.

Esta tesis presenta el desarrollo de un filtro inteligente para la detecci´on y eliminaci´on
de correo SPAM. Este filtro esta construido por un conjunto de reglas deterministas y
heur´ısticas as´ı como un an´alisis estad´ıstico.

Las reglas deterministas rechazan correos cuyo emisor ha sido previamente identifica-
do como fuente de correo SPAM. Pero aceptan inmediatamente correos cuya fuente ha
sido validada por el usuario. Las reglas heur´ısticas analizan el tema y cuerpo de un men-
saje mediante la identificaci´on de palabras o frases consideradas como caracter´ısticas de
correo SPAM. Finalmente, el an´alisis estad´ıstico, basado en el teorema de Bayes, calcula
la probabilidad de que las frases de cierto tama˜no de un cierto mensaje pertenezcan a un
mensaje tipo SPAM. Posteriormente se realiza un c´alculo de probabilidad de que el correo
sea SPAM.

El filtro propuesto identifica y elimina correctamente la mayor´ıa del correo SPAM.
Adem´as es adaptable. La actualizaci´on se logra con la informaci´on de mensajes SPAM y
no SPAM. Los porcentajes de detecci´on mejoraron en un intervalo de 1 % a 4 % respecto
a los sistemas actuales que filtran el 95 % de correo SPAM. Todo esto se logra por la
combinaci´on de las reglas deterministas, las heur´ısticas y por el an´alisis estad´ıstico.

Palabras clave: correo electr´onico, SPAM, reglas deterministas y heur´ısticas, filtro proba-
bil´ıstico.

iii

iv

Abstract

Nowadays the electronic mail (email) is the most common service at the internet. People
usually use it for comunication and data transmision. However, its best features (eficiency
and facility of use) have increased its used as SPAM mail. The amount of SPAM mails is
rising every day, therefore, new SPAM-handling techniques are needed.

This thesis presents the development of an intelligent filter for detection and elimination
of SPAM mails. This filter is built using a set of deterministic and heuristic rules, and a
statistical analysis.

Deterministic rules reject such mails which senders have been previously identified
as spammers, but if the sender have been authenticated by the user, then the email is
accepted. Heuristic rules analyze the email’s subjet and body to identify SPAM words or
phrases. Finally, the statistical analysis calculates the email’s spam probability using the
Bayes theorem.

The filter proposed identifies and eliminates correctly the most of SPAM mails. Fu-

thermore, it adapts its behavior using the information of valid and SPAM mails.

The proposed system outperforms in 1 to 4 % to some of the best SPAM filters.

Keywords: electronic mail, SPAM mail, deterministic and heuristic rules, probabilistic
filter.

v

vi

Agradecimientos

Agradezco a mis padres Genoveva Lagunes Monz´on y Manuel Alejandro Guillen (fina-
do), a mis hermanos y seres queridos por su apoyo incondicional. Esta tesis est´a dedicada
a ustedes.

Agradezco a mi asesor, el Dr. Arturo D´ıaz P´erez por guiarme y aconsejarme en todo

momento, adem´as de compartirme sus conocimientos.

A mis sinodales, los Dres. Luis Gerardo de la Fraga y Guillermo Morales Luna, por su

aportaci´on para mejorar este documento de tesis.

Agradezco a Sofia por su amistad y apoyo en los aspectos administrativos durante mi

estancia en la maestr´ıa.

Agradezco al CINVESTAV por facilitarme las instalaciones en las que curse las mate-

rias, as´ı como el desarrollo este trabajo de tesis.

Agradezco a la secci´on de Computaci´on por permitirme formar parte del programa de

Maestr´ıa, as´ı mismo agradezco a los Dres. que me ense˜naron en sus clases.

Agradezco al CONACyT por la beca otorgada durante mi estancia en el programa
de maestr´ıa en el CINVESTAV. Este trabajo de tesis se deriv´o del proyecto CONACyT
titulado “Algoritmos y Arquitecturas con Dispositivos Reconfigurables”(Ref. CONACyT
31892-A) cuyo responsable es el Dr. Arturo D´ıaz P´erez.

Agradezco a mis compa˜neros y amigos por brindarme su amistad y apoyo, haciendo

de mi estancia en la maestr´ıa, algo agradable.

vii

viii

´Indice general

Resumen

Abstract

Agradecimientos

´Indice de figuras

´Indice de algoritmos

1. Introducci´on

1.1. Planteamiento del problema . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Objetivos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Metodolog´ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4. Organizaci´on de la tesis
. . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.1. Objetivo general
1.2.2. Objetivos espec´ıficos

2. Marco te´orico

2.3. Filtros inteligentes

2.1. Correo electr´onico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Procmail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. El fen´omeno del correo SPAM . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Alternativas para eliminar el correo SPAM . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1. Filtros con heur´ısticas
. . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2. Filtros adaptativos o bayesianos . . . . . . . . . . . . . . . . . . . .
2.4. Teorema de Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
2.5. Algoritmo basado en tokens
2.5.1. Proceso de entrenamiento . . . . . . . . . . . . . . . . . . . . . . .
2.5.2. Clasificaci´on de mensajes . . . . . . . . . . . . . . . . . . . . . . . .
2.5.3. Observaciones al algoritmo de an´alisis . . . . . . . . . . . . . . . . .

ix

III

V

VII

XI

XIII

1
3
3
3
3
4
6

7
7
11
14
14
15
16
16
17
19
19
23
28

2.6. Herramientas de detecci´on de SPAM . . . . . . . . . . . . . . . . . . . . .

29

3. Un algoritmo basado en frases para la clasificaci´on de mensajes

3.1. Motivaci´on del an´alisis basado en frases . . . . . . . . . . . . . . . . . . . .
3.2. Descripci´on del algoritmo basado en frases . . . . . . . . . . . . . . . . . .
3.2.1. Formaci´on de frases . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2. Proceso de entrenamiento . . . . . . . . . . . . . . . . . . . . . . .
3.2.3. Clasificaci´on de mensajes . . . . . . . . . . . . . . . . . . . . . . . .

4. Sistema de an´alisis y filtraje de SPAM

4.1. Arquitectura del sistema antispam . . . . . . . . . . . . . . . . . . . . . . .
4.1.1. Estructura de directorios y archivos usada por el sistema . . . . . .
4.1.2. An´alisis de mensajes basado en listas de usuarios conocidos . . . . .
4.1.3. An´alisis de mensajes basado en palabras clave . . . . . . . . . . . .
4.1.4. An´alisis de mensajes basado en frases clave . . . . . . . . . . . . . .
4.1.5. An´alisis probabil´ıstico basado en frases . . . . . . . . . . . . . . . .
4.2. Adaptaci´on del sistema en el contexto de procmail . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.1. Reglas de procmail

5. An´alisis de resultados

Infraestructura del ambiente de pruebas

5.1.
. . . . . . . . . . . . . . . . . . .
5.2. Caso de estudio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1. An´alisis basado en listas definidas . . . . . . . . . . . . . . . . . . .
5.2.2. An´alisis basado en frases clave . . . . . . . . . . . . . . . . . . . . .
5.2.3. An´alisis basado en palabras clave . . . . . . . . . . . . . . . . . . .
5.2.4. An´alisis estad´ıstico basado en tokens SpamAssassin . . . . . . . . .
5.2.5. An´alisis estad´ıstico basado en frases . . . . . . . . . . . . . . . . . .
5.3. Caso de estudio 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6. Conclusiones

6.1. Contribuciones
6.2. Trabajo futuro

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Bibliograf´ıa

33
34
36
37
37
42

47
48
51
54
56
57
59
63
63

69
69
70
71
72
72
73
74
76

79
79
81

83

x

´Indice de figuras

1.1. Esquema general de soluci´on del sistema antispam.

. . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .
2.1. Esquema del servicio de correo electr´onico.
2.2. Componentes de un correo electr´onico.
. . . . . . . . . . . . . . . . . . . .
2.3. Esquema b´asico de clasificaci´on de mensajes. . . . . . . . . . . . . . . . . .
2.4. Valores de probabilidad combinada total de mensaje.
. . . . . . . . . . . .

3.1. Comportamiento de la funci´on 3.1.

. . . . . . . . . . . . . . . . . . . . . .

4.1. Esquema general de un sistema clasificador de mensajes SPAM.
4.2. Esquema del sistema y su entorno.
4.3. Arquitectura general del sistema.
4.4. Entrenamiento del sistema de an´alisis de mensajes.
4.5. Procesos para la clasificaci´on de mensajes.

. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .

5.1. Porcentajes de clasificaci´on por m´odulos.
. . . . . . . . . . . . . . . . . . .
5.2. Porcentajes de clasificaci´on por m´odulos (caso 2) . . . . . . . . . . . . . . .

5

8
12
20
29

35

48
49
50
60
61

76
77

x