UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ
PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E
INFORMÁTICA INDUSTRIAL
ANDRÉ LUIZ PEREIRA DE FRANÇA
ESTUDO, DESENVOLVIMENTO E IMPLEMENTAÇÃO DE
ALGORITMOS DE APRENDIZAGEM DE MÁQUINA, EM
SOFTWARE E HARDWARE, PARA DETECÇÃO DE INTRUSÃO DE
REDE: UMA ANÁLISE DE EFICIÊNCIA ENERGÉTICA
DISSERTAÇÃO
CURITIBA
2015
ANDRÉ LUIZ PEREIRA DE FRANÇA
ESTUDO, DESENVOLVIMENTO E IMPLEMENTAÇÃO DE
ALGORITMOS DE APRENDIZAGEM DE MÁQUINA, EM
SOFTWARE E HARDWARE, PARA DETECÇÃO DE INTRUSÃO DE
REDE: UMA ANÁLISE DE EFICIÊNCIA ENERGÉTICA
Dissertação apresentada ao Programa de Pósgraduação em Engenharia Elétrica e Informática
Industrial da Universidade Tecnológica Federal do
Paraná como requisito parcial para obtenção do grau
de “Mestre em Ciências” – Área de Concentração:
Engenharia de Automação e Sistemas.
Orientador:
Prof. Dr. Volnei Antonio Pedroni
Coorientador: Dr. Ricardo Pereira Jasinski
CURITIBA
2015
Dados Internacionais de Catalogação na Publicação
F814e
2015
França, André Luiz Pereira
Estudo, desenvolvimento e implementação de algoritmos de
aprendizagem de máquina, em software e hardware, para detecção
de intrusão de rede : uma análise de eficiência energética /
André Luiz Pereira de França.-- 2015.
100 f.: il.; 30 cm
Texto em português, com resumo em inglês.
Dissertação (Mestrado) - Universidade Tecnológica Federal
do Paraná. Programa de Pós-Graduação em Engenharia Elétrica e
Informática Industrial, Curitiba, 2015.
Bibliografia: f. 97-100.
1. Sistemas de detecção de intrusão (Segurança do
computador). 2. Aprendizado do computador. 3. Árvores de
decisão. 4. Algoritmos computacionais. 5. Software –
Desenvolvimento. 6. Hardware - Avaliação. 7. Redes de
Computação - Medidas de segurança. 8. Métodos de simulação. 9.
Energia - Consumo. 10. Engenharia elétrica - Dissertações. I.
Pedroni, Volnei A. (Volnei Antonio), orient. II. Jasinski,
Ricardo Pereira, coorient. III. Universidade Tecnológica
Federal do Paraná - Programa de Pós-Graduação em Engenharia
Elétrica e Informática Industrial. IV. Título.
CDD 22 -- 621.3
Biblioteca Central da UTFPR, Câmpus Curitiba
AGRADECIMENTOS
Agradeço primeiramente à Santı́ssima Trindade: Deus Pai, Filho e Espı́rito Santo, por
me iluminar em cada decisão tomada até hoje e por sempre me mostrar o caminho certo a seguir.
Aos meus pais, Evaldo e Adilma, e às três Marias pelo incentivo, apoio e carinho.
À Taisa Costa pelo companheirismo ao longo do mestrado.
Ao meu orientador Prof. Dr. Volnei Pedroni pelo conhecimento técnico transmitido e
pela oportunidade de fazer parte da equipe do Laboratório de Microeletrônica da UTFPR.
Ao meu coorientador Dr. Ricardo Jasinski pela ajuda nas implementações e testes dos
algoritmos desenvolvidos ao longo do trabalho.
Ao colega de pesquisa MSc. Paulo Cemin pelo desenvolvimento da plataforma de
medição de consumo utilizada como ferramenta neste trabalho.
Aos colegas de pesquisa Prof.
Dr.
Altair Santin e Eduardo Viegas pelo
desenvolvimento do cenário de rede e do algoritmo de extração de caracterı́sticas, descritos
na seção 3.1 e pela realização das tarefas de seleção de caracterı́sticas descritas no inı́cio das
seções 4.1, 5.1 e 6.1 deste documento.
Aos colegas Diego Reis e José Galvão pela troca de experiências e conhecimentos nas
disciplinas cursadas.
À secretária do CPGEI Denise Erthal por responder, de prontidão, todas as perguntas
que fiz sobre o programa de mestrado.
Aos membros da banca avaliadora desta dissertação, professores Volnei Pedroni, Altair
Santin e André Mariano, pela revisão do documento e pelas sugestões de correções e melhorias,
que engrandeceram ainda mais o trabalho.
À Intel por promover, através de seu University Research Office, o projeto de pesquisa
e desenvolvimento do qual esta dissertação é resultado.
À Capes pelo apoio financeiro através da concessão da bolsa DS durante 12 meses.
Ao CNPq pelo apoio financeiro através da concessão da bolsa DTC durante 12 meses.
RESUMO
FRANÇA, André Luiz Pereira de. Estudo, Desenvolvimento e Implementação de Algoritmos
de Aprendizagem de Máquina, em Software e Hardware, para Detecção de Intrusão de Rede:
Uma Análise de Eficiência Energética. 2015. 100 f. Dissertação (Mestrado em Engenharia
Elétrica e Informática Industrial) – Programa de Pós-graduação em Engenharia Elétrica e
Informática Industrial, Universidade Tecnológica Federal do Paraná. Curitiba, 2015.
O constante aumento na velocidade da rede, o número de ataques e a necessidade de eficiência
energética estão fazendo com que a segurança de rede baseada em software chegue ao seu
limite. Um tipo comum de ameaça são os ataques do tipo probing, nos quais um atacante
procura vulnerabilidades a partir do envio de pacotes de sondagem a uma máquina-alvo. Este
trabalho apresenta o estudo, o desenvolvimento e a implementação de um algoritmo de extração
de caracterı́sticas dos pacotes da rede em hardware e de três classificadores de aprendizagem
de máquina (Árvore de Decisão, Naive Bayes e k-vizinhos mais próximos), em software e
hardware, para a detecção de ataques do tipo probing. O trabalho apresenta, ainda, resultados
detalhados de acurácia de classificação, taxa de transferência e consumo de energia para cada
implementação.
Palavras-chave: Detecção de Intrusão de Rede. Ataques Probing. Aprendizagem de Máquina.
Árvore de Decisão. Naive Bayes. KNN. Eficiência Energética.
ABSTRACT
FRANÇA, André Luiz Pereira de. Study, Development and Implementation of Machine
Learning Algorithms, in Software and Hardware, for Network Intrusion Detection: an Energy
Efficiency Analysis. 2015. 100 f. Dissertação (Mestrado em Engenharia Elétrica e Informática
Industrial) – Programa de Pós-graduação em Engenharia Elétrica e Informática Industrial,
Universidade Tecnológica Federal do Paraná. Curitiba, 2015.
The increasing network speeds, number of attacks, and need for energy efficiency are pushing
software-based network security to its limits. A common kind of threat is probing attacks, in
which an attacker tries to find vulnerabilities by sending a series of probe packets to a target
machine. This work presents the study, development, and implementation of a network packets
feature extraction algorithm in hardware and three machine learning classifiers (Decision Tree,
Naive Bayes, and k-nearest neighbors), in software and hardware, for the detection of probing
attacks. The work also presents detailed results of classification accuracy, throughput, and
energy consumption for each implementation.
Keywords: Network Intrusion Detection. Probing attacks. Machine Learning. Decision Tree.
Naive Bayes. KNN. Energy Efficiency.
LISTA DE FIGURAS
FIGURA 1
FIGURA 2
FIGURA 3
FIGURA 4
FIGURA 5
FIGURA 6
FIGURA 7
FIGURA 8
FIGURA 9
FIGURA 10
FIGURA 11
FIGURA 12
FIGURA 13
FIGURA 14
FIGURA 15
FIGURA 16
FIGURA 17
FIGURA 18
FIGURA 19
FIGURA 20
FIGURA 21
FIGURA 22
FIGURA 23
FIGURA 24
FIGURA 25
FIGURA 26
FIGURA 27
FIGURA 28
FIGURA 29
FIGURA 30
FIGURA 31
FIGURA 32
FIGURA 33
FIGURA 34
FIGURA 35
FIGURA 36
FIGURA 37
FIGURA 38
FIGURA 39
FIGURA 40
FIGURA 41
FIGURA 42
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
Divisão de um IDS quanto ao tipo e técnica de detecção . . . . . . . . . . . . . . . .
Etapas da Aprendizagem de Máquina num exemplo da literatura . . . . . . . . .
Histograma para a caracterı́stica comprimento do exemplo . . . . . . . . . . . . . .
Histograma para a caracterı́stica luminosidade do exemplo . . . . . . . . . . . . . .
Plano para as caracterı́sticas luminosidade e largura do exemplo . . . . . . . . .
Exemplo de uma Árvore de Decisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemplo gráfico da classificação pelo kNN . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Campos do cabeçalho IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Campos do cabeçalho UDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Campos do cabeçalho ICMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Campos do cabeçalho TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Cenário para geração de tráfego normal e de ataque . . . . . . . . . . . . . . . . . . . .
Montagem da chave da hash que acessa as linhas da tabela de atributos . . .
Células da tabela a serem consideradas para se obter o valor dos atributos
Fluxograma simplificado do extrator de caracterı́sticas . . . . . . . . . . . . . . . . . .
Ambiente para avaliação dos algoritmos em software . . . . . . . . . . . . . . . . . . .
Plataforma usada para medição do consumo energético em software . . . . .
Diagrama em blocos do extrator de caracterı́sticas em hardware . . . . . . . . .
Memória RAM que armazena os atributos dependentes da comunicação . .
Módulo de atualização das linhas da memória de atributos . . . . . . . . . . . . . .
Módulo de zeramento das células a serem apagadas da tabela de atributos
Módulo de controle do extrator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Máquina de estados que controla o extrator de caracterı́sticas . . . . . . . . . . . .
Kit com FPGA Cyclone IV GX para avaliação dos algoritmos em hardware
Circuito para medição do consumo do extrator em hardware . . . . . . . . . . . .
Árvore de Decisão para detecção de probing . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementação em hardware da Árvore de Decisão . . . . . . . . . . . . . . . . . . . .
Circuito para estimação da taxa de transferência dos classificadores . . . . . .
Circuito para medição do consumo dos classificadores em hardware . . . . .
Máquina de estados que controla o circuito de medição dos classificadores
Modelo Naive Bayes para detecção de probing . . . . . . . . . . . . . . . . . . . . . . . . .
Fluxograma do Naive Bayes para detecção de probing em software . . . . . .
Implementação combinacional do Naive Bayes em hardware . . . . . . . . . . . .
Implementação sequencial do Naive Bayes em hardware . . . . . . . . . . . . . . .
Fluxograma do kNN para detecção de probing em software . . . . . . . . . . . . .
Implementação do kNN em hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Circuito do Normalizador do kNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Circuito do Calculador de Distância do kNN . . . . . . . . . . . . . . . . . . . . . . . . . . .
Energia gasta na extração em hardware para diferentes frequências . . . . . .
Consumo de potência pelo no de classificadores em 50 MHz . . . . . . . . . . . .
Energia gasta na classificação em software e hardware (em 50 MHz) . . . . .
Energia gasta na classificação em hardware para diferentes frequências . .
19
24
24
25
25
26
30
33
33
33
33
40
44
45
46
48
49
51
52
53
54
55
55
57
57
60
62
63
64
66
68
71
73
74
78
79
80
81
86
92
93
94
LISTA DE QUADROS
QUADRO 1
QUADRO 2
QUADRO 3
QUADRO 4
QUADRO 5
QUADRO 6
QUADRO 7
QUADRO 8
–
–
–
–
–
–
–
–
Atributos dos pacotes considerados no banco de dados KDD 99 . . . . . . . .
Atributos extraı́dos diretamente do cabeçalho de cada pacote . . . . . . . . . . .
Atributos extraı́dos a partir da comunicação entre hosts . . . . . . . . . . . . . . . .
Como cada atributo do cabeçalho dos pacotes é extraı́do . . . . . . . . . . . . . . .
Como cada atributo dependente da comunicação é atualizado . . . . . . . . . .
Atributos selecionados para detecção de probing pela Árvore de Decisão
Atributos selecionados para detecção de probing pelo Naive Bayes . . . . .
Atributos selecionados para detecção de probing pelo kNN . . . . . . . . . . . .
32
41
42
43
47
60
67
77
LISTA DE TABELAS
TABELA 1
TABELA 2
TABELA 3
TABELA 4
TABELA 5
TABELA 6
TABELA 7
TABELA 8
TABELA 9
TABELA 10
TABELA 11
–
–
–
–
–
–
–
–
–
–
–
Probabilidades para o atributo udp sport na implementação do Naive Bayes
Área utilizada pelo extrator de caracterı́sticas implementado em hardware
Taxa de transferência dos extratores em software e hardware . . . . . . . . . . . .
Energia consumida na operação de extração em software e hardware . . . . .
Matriz de confusão para o classificador Árvore de Decisão . . . . . . . . . . . . . .
Matriz de confusão para o classificador Naive Bayes . . . . . . . . . . . . . . . . . . . .
Matriz de confusão para o classificador kNN . . . . . . . . . . . . . . . . . . . . . . . . . . .
Acurácia dos classificadores sobre a base de testes . . . . . . . . . . . . . . . . . . . . . .
Área utilizada pelos classificadores implementados em hardware . . . . . . . .
Taxa de transferência dos classificadores implementados . . . . . . . . . . . . . . . .
Energia consumida pelos classificadores implementados . . . . . . . . . . . . . . . .
70
84
85
85
87
88
88
88
89
90
92
LISTA DE SIGLAS
A/D
ARFF
DAQ
DoS
FIFO
FPGA
HIDS
ICMP
ID3
IDPS
IDS
IP
kNN
LED
NIDS
PCAP
PLL
R2L
RAM
ROM
SoC
SVM
TCP
U2R
UDP
USB
Analógico/Digital
Attribute-Relation File Format
Data AcQuisition
Denial of Service
First In First Out
Field-Programmable Gate Array
Host-based Intrusion Detection System
Internet Control Message Protocol
Iterative Dichotomiser 3
Intrusion Detection and Prevention System
Intrusion Detection System
Internet Protocol
k-Nearest Neighbors
Light-Emitting Diode
Network-based Intrusion Detection System
Packet CAPture
Phase-Locked Loop
Remote to Local
Random Access Memory
Read-Only Memory
System-on-a-Chip
Support Vector Machine
Transmission Control Protocol
User to Root
User Datagram Protocol
Universal Serial Bus
SUMÁRIO
1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 MOTIVAÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 OBJETIVOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Objetivo Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2 Objetivos Especı́ficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 ESTRUTURA DA DISSERTAÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 REVISÃO DE LITERATURA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1 SISTEMA DE DETECÇÃO DE INTRUSÃO (IDS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Detecção Baseada em Assinatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Detecção Baseada em Anomalia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 APRENDIZAGEM DE MÁQUINA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Extração de Caracterı́sticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Classificador Árvore de Decisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Classificador Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.4 Classificador k-Vizinhos Mais Próximos (kNN) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 APRENDIZAGEM DE MÁQUINA PARA DETECÇÃO DE INTRUSÃO . . . . . . . . .
2.3.1 Aplicações de Extração de Caracterı́sticas em Software e Hardware . . . . . . . . . . . . . .
2.3.2 Aplicações de Árvore de Decisão em Software e Hardware . . . . . . . . . . . . . . . . . . . . . .
2.3.3 Aplicações de Naive Bayes em Software e Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.4 Aplicações de kNN em Software e Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 DESENVOLVIMENTO DO EXTRATOR DE CARACTERÍSTICAS . . . . . . . . . . .
3.1 IMPLEMENTAÇÃO EM SOFTWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 AVALIAÇÃO EM SOFTWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 IMPLEMENTAÇÃO EM HARDWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 AVALIAÇÃO EM HARDWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 DESENVOLVIMENTO DA ÁRVORE DE DECISÃO . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1 IMPLEMENTAÇÃO EM SOFTWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 AVALIAÇÃO EM SOFTWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 IMPLEMENTAÇÃO EM HARDWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 AVALIAÇÃO EM HARDWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 DESENVOLVIMENTO DO NAIVE BAYES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1 IMPLEMENTAÇÃO EM SOFTWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 AVALIAÇÃO EM SOFTWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 IMPLEMENTAÇÃO EM HARDWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Versão Combinacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.2 Versão Sequencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 AVALIAÇÃO EM HARDWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 DESENVOLVIMENTO DO KNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1 IMPLEMENTAÇÃO EM SOFTWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 AVALIAÇÃO EM SOFTWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 IMPLEMENTAÇÃO EM HARDWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
14
16
16
16
17
18
18
20
21
22
23
26
28
29
31
31
35
36
37
39
39
48
50
56
59
59
61
62
63
67
67
72
72
72
73
75
76
76
79
79
6.4 AVALIAÇÃO EM HARDWARE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 RESULTADOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1 EXTRATOR DE CARACTERÍSTICAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 Área do Circuito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.2 Taxa de Transferência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.3 Consumo de Energia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 CLASSIFICADORES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.1 Acurácia de Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.2 Área dos Circuitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.3 Taxa de Transferência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.4 Consumo de Energia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3 PUBLICAÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
84
84
84
85
85
86
87
89
90
91
94
95
97
13
1
INTRODUÇÃO
Com o uso difundido da internet e surgimento diário de novas ameaças na grande rede,
torna-se fundamental a aplicação de sistemas de proteção. Um destes sistemas é o chamado
Sistema de Detecção de Intrusão (IDS). Dentre as classes de IDS, há o Sistema de Detecção
de Intrusão de Rede (NIDS), cuja finalidade é detectar possı́veis intrusões (ataques) a partir da
análise dos pacotes de rede (CORONA et al., 2013). Em caso de detecção de uma ameaça, um
alarme é gerado para o administrador de rede.
Um tipo comum de ameaça são os ataques do tipo probing, nos quais um atacante
envia pacotes de sondagem para uma máquina-alvo, na tentativa de encontrar portas abertas e
identificar serviços para, assim, explorar possı́veis vulnerabilidades. Os ataques do tipo probing
são executados com ferramentas farejadoras (sniffers) de rede e escaneadoras (scanners) de
portas (PUKKAWANNA et al., 2014). Geralmente os ataques do tipo probing precedem outros
tipos de ataque, então a detecção de tentativas de intrusão nessa fase inicial pode prevenir
ataques mais graves.
Quanto à técnica de detecção, um NIDS pode ser classificado em duas categorias:
baseado em assinatura e baseado em anomalia. A técnica de detecção por assinatura procura
por padrões de ataques conhecidos nos pacotes de rede. Por exemplo, os bytes do pacote podem
ser analisados em busca de ataques, combinação estranha de flags e tentativas de acesso não
autorizadas. O NIDS baseado em assinatura possui baixa taxa de alarmes falsos, pois procura
por padrões adicionados em seu banco de dados. Entretanto, não é possı́vel detectar novos tipos
de ataques (GARCÍA-TEODORO et al., 2009).
A técnica de detecção por anomalia consiste em capturar comportamentos que desviam
do comportamento normal da rede. Esse método se utiliza de dados de entrada para treinamento
e construção de um modelo padrão de comportamento. Quando alguma atividade na rede é
classificada como anormal, um alarme é gerado. Embora o NIDS baseado em anomalia possa
detectar novos ataques, há a possibilidade de que um alarme gerado seja falso (TSAI et al.,
2009). Apesar dessa desvantagem, como a rede sempre está sujeita a novas ameaças, a detecção
14
por anomalia é importante para NIDS. O desafio se encontra no projeto de um bom classificador
que deve possuir acurácia e baixa taxa de alarmes falsos.
A detecção por anomalia pode fazer uso de técnicas de Aprendizagem de Máquina.
Tais técnicas são comumente utilizadas para descobrir modelos de comportamento a partir de
um conjunto de dados de treinamento. As aplicações de Aprendizagem de Máquina utilizam
classificadores, que são funções que mapeiam dados em classes. Nesse caso, o NIDS pode,
então, classificar um evento como normal ou malicioso a partir de caracterı́sticas do próprio
evento (BRUGGER, 2004). Alguns exemplos de classificadores são: Árvore de Decisão, Naive
Bayes, k-Vizinhos Mais Próximos (kNN, do inglês k-Nearest Neighbors), Máquina de Vetor de
Suporte (SVM, do inglês Support Vector Machine) e Redes Neurais Artificiais.
A geração e o uso de um classificador são dois estágios separados. O estágio de
treinamento usa um conjunto de dados de treinamento e um algoritmo gerador do modelo.
Nessa fase são escolhidas as caracterı́sticas dos dados de entrada a serem examinadas e obtido
o modelo do classificador. No caso do NIDS, as caracterı́sticas são valores obtidos dos pacotes
ou de atividades da rede (WU; BANZHAF, 2010).
O segundo estágio é a classificação.
Nessa fase, executada em tempo real, as
caracterı́sticas são extraı́das de um determinado evento e enviadas para o modelo classificador.
No caso do NIDS, os eventos podem ser classificados em normal ou ataque (WU; BANZHAF,
2010).
1.1
MOTIVAÇÃO
Tradicionalmente, um NIDS é concebido em forma de software, e assim, integrado a
um sistema operacional. Um exemplo é a plataforma Snort, um NIDS de código aberto, que
possui versões para Windows e Unix (ROESCH, 1999).
Entretanto, os sistemas de rede, no geral, incluindo os sistemas de segurança,
enfrentam duas preocupações principais: taxa de transferência e eficiência energética. A
empresa Cisco relatou que o tráfego IP médio em 2013 foi de 158 terabits por segundo e
estimou que esse valor deve quase triplicar até 2018 (CISCO, 2014). Ao mesmo tempo, sistemas
computacionais já respondem por 6% de todo o consumo de energia mundial (SOMAVAT;
NAMBOODIRI, 2011), e dispositivos móveis reforçam a necessidade de aproveitar ao máximo
a energia disponı́vel.
No caso do NIDS, as altas taxas de transferência das redes atuais e o crescimento do
número de ataques impedem a análise de ameaças em tempo real (WU; BANZHAF, 2010).
15
Uma abordagem promissora para melhorar a taxa de transferência e a eficiência
energética de sistemas de rede é mover algoritmos de software para hardware. Usando circuitos
dedicados, tarefas que necessitam de muitas instruções em software podem ser realizadas num
único ciclo de clock em hardware. Como não há necessidade de suporte a algoritmos de
uso geral, o hardware resultante pode operar a uma fração do consumo de energia de um
processador genérico.
Para aplicação de NIDS em hardware, porém, um fator importante do software — a
flexibilidade — deve ser levado em consideração. Devido ao aumento na quantidade e variedade
de ameaças, os sistemas de segurança devem possibilitar mecanismos de atualização. Por isso,
implementações em hardware devem ter a caracterı́stica de reconfigurabilidade (CHEN et al.,
2011). Uma alternativa viável para atualização em hardware é usar FPGA.
Outra razão para o uso de hardware é a imunidade às infecções de software. Circuitos
de hardware são difı́ceis de serem modificados sem acesso direto, e podem ser isolados do
ambiente de software.
O uso de NIDS também é promissor em Sistemas em um Chip (SoCs). O número de
SoCs conectados à internet deve chegar a 50 bilhões até 2020 (EVANS, 2011). Uma vez que
SoCs estão associados com mobilidade e bateria, a segurança com eficiência energética é um
tópico importante.
Neste trabalho, serão apresentados os desenvolvimentos, implementações e avaliações
de um extrator de caracterı́sticas dos pacotes de rede em hardware (versão correspondente a um
extrator existente em software) e de três classificadores de Aprendizagem de Máquina (Árvore
de Decisão, Naive Bayes e kNN), em software e hardware, modelados para detecção de ataques
do tipo probing. Serão apresentadas comparações de eficiência energética, taxa de transferência
e acurácia entre as implementações.
Em geral, as ferramentas de NIDS comerciais utilizam a técnica de detecção por
assinatura, para evitar alarmes falsos. Na literatura, técnicas de detecção de intrusão por
anomalia têm sido propostas nos últimos anos.
Para seguir essa tendência, escolheu-se
utilizar algoritmos de Aprendizagem de Máquina nesta dissertação. A comparação entre
implementações de algoritmos em software e hardware também é outra tendência considerada.
Há poucos trabalhos sobre o desenvolvimento de classificadores para detecção de intrusão em
hardware e nenhum que desenvolve e compara esses algoritmos em software e hardware.
Entre os trabalhos que utilizam as técnicas de Aprendizagem de Máquina para detecção
de intrusão, os classificadores mais utilizados são o SVM, a Árvore de Decisão e o kNN (TSAI
16
et al., 2009). Neste trabalho, escolheu-se dois desses classificadores, Árvore de Decisão e kNN,
mais o Naive Bayes, para considerar uma complexidade incremental nas implementações dos
classificadores. O SVM será desenvolvido e implementado futuramente.
O ataque-alvo de detecção escolhido foi o probing, pois este compreende o primeiro
passo do atacante numa intrusão mais grave.
1.2
OBJETIVOS
1.2.1
OBJETIVO GERAL
Desenvolver, implementar e comparar, em software e hardware, algoritmos
necessários ao desenvolvimento de um NIDS baseado em anomalia para detecção de ataques
do tipo probing. Neste trabalho, foram considerados os seguintes algoritmos: um extrator de
caracterı́sticas dos pacotes de rede em hardware (baseado num extrator existente em software,
desenvolvido por Eduardo Viegas e Altair Santin) e três classificadores de Aprendizagem de
Máquina (Árvore de Decisão, Naive Bayes e kNN), em software e hardware, modelados para
detecção de probing.
1.2.2
OBJETIVOS ESPECÍFICOS
• Desenvolver e implementar, em hardware (FPGA), um algoritmo de extração de
caracterı́sticas dos pacotes de rede para detecção de probing, baseado em um extrator
existente em software.
• Desenvolver e implementar, em software e hardware (FPGA), o classificador Árvore de
Decisão para detecção de probing.
• Desenvolver e implementar, em software e hardware (FPGA), o classificador Naive Bayes
para detecção de probing.
• Desenvolver e implementar, em software e hardware (FPGA), o classificador kNN para
detecção de probing.
• Comparar a taxa de transferência e a eficiência energética entre o extrator de
caracterı́sticas existente em software e sua versão correspondente desenvolvida em
hardware.
• Comparar a acurácia de classificação, a taxa de transferência e a eficiência energética
entre as versões em software e hardware dos classificadores.
17
1.3
ESTRUTURA DA DISSERTAÇÃO
Esta dissertação está dividida em oito capı́tulos.
No primeiro capı́tulo foram
apresentados conceitos introdutórios sobre a importância do NIDS para segurança de rede,
técnicas de detecção de intrusão, problemas na implementação de NIDS em software e motivos
para a avaliação de NIDS em hardware.
No segundo capı́tulo será apresentada a revisão de literatura, abordando a
fundamentação teórica das técnicas de detecção de intrusão de rede e das técnicas de
Aprendizagem de Máquina e o estado da arte do uso de Aprendizagem de Máquina para
detecção de intrusão de rede, em software e hardware.
No terceiro capı́tulo será explicado o funcionamento de um extrator de caracterı́sticas
dos pacotes de rede existente em software e apresentada a implementação correspondente desse
extrator em hardware.
Nos quarto, quinto e sexto capı́tulos serão apresentados os desenvolvimentos e
implementações, em software e hardware, dos classificadores Árvore de Decisão, Naive Bayes
e kNN para detecção de probing.
No sétimo capı́tulo serão apresentados os resultados comparativos entre as diferentes
implementações dos algoritmos, incluindo acurácia de classificação, taxa de transferência e
eficiência energética.
Por fim, no capı́tulo oito, as conclusões e trabalhos futuros serão apresentados.
18
2
REVISÃO DE LITERATURA
Neste capı́tulo serão apresentados os conceitos que norteiam a dissertação. Nas seções
2.1 e 2.2 serão expostas, respectivamente, as fundamentações teóricas das técnicas de detecção
de intrusão e de Aprendizagem de Máquina. Na seção 2.3 serão apresentados alguns trabalhos
que usam Aprendizagem de Máquina para detecção de intrusão, em software e hardware.
2.1
SISTEMA DE DETECÇÃO DE INTRUSÃO (IDS)
Um Sistema de Detecção de Intrusão é uma ferramenta que monitora o tráfego de rede
ou as atividades do sistema em busca de tentativas de intrusões. Uma intrusão (frequentemente
também chamada de ataque) pode ser definida como uma atividade maliciosa que viola polı́ticas
de segurança de uma rede (CORONA et al., 2013). Em caso de identificação de tentativa de
intrusão, o IDS envia um alarme para a administração de rede (KIZZA, 2013). O IDS difere
do Sistema de Detecção e Prevenção de Intrusão (IDPS), pois este último detecta e procura
também impedir as tentativas de intrusão.
Quanto ao tipo, um IDS divide-se em IDS baseado em host (HIDS) e IDS baseado em
rede (NIDS), conforme mostra a figura 1. A imagem mostra, ainda, a divisão do IDS quanto
à técnica de detecção: baseado em assinatura e baseado em anomalia. Essas técnicas serão
explicadas mais adiante. Há também outras divisões não apresentadas.
Um HIDS é executado em um dispositivo individual na rede. O sistema monitora
dados do dispositivo, como dados do kernel do Sistema Operacional, arquivos do sistema e
aplicativos (CORONA et al., 2013). O HIDS registra o estado desses dados e compara com o
registro anterior. Se arquivos importantes do sistema foram modificados ou excluı́dos, um sinal
de alerta é enviado ao administrador (KIZZA, 2013).
Um NIDS coleta informações de um ou mais nós da rede, como as interfaces
ou dispositivos (CORONA et al., 2013). O sistema monitora o tráfego que entra em um
determinado dispositivo na rede em busca de intrusões (KIZZA, 2013). O NIDS trabalha em
19
Figura 1: Divisão de um IDS quanto ao tipo e técnica de detecção.
Fonte: Autoria Própria
modo promı́scuo, isto é, analisa todo o tráfego do ponto monitorado. Caso um ataque seja
detectado, um sinal de alerta é enviado ao administrador.
Há diferenças entre o NIDS e o Firewall. O Firewall é configurado com um conjunto
de regras, para permitir ou bloquear acesso a um serviço ou host particular. Independentemente
do conteúdo, o tráfego só é recebido caso condiga com padrões permitidos. Já o NIDS analisa
todos os pacotes da rede, independentemente da origem ser autorizada ou não.
Em geral, os ataques de rede no campo de detecção de intrusão podem ser divididos
em quatro principais categorias (KENDALL, 1999):
• Probes: ataques que visam obter informações sobre o sistema a fim de descobrir possı́veis
vulnerabilidades, ou seja, são utilizados para futuros ataques. Estes ataques incluem
farejamento da rede e escaneamento de portas e endereços. Exemplos: ip sweep, mscan,
nmap, saint e satan.
• Denial of Service (DoS): ataque que faz com que a memória ou algum outro recurso
computacional esteja tão ocupado, ou tão cheio, que não consiga atender os usuários
autorizados. Exemplos: apache2, back, land, mailbomb, syn flood, ping of death, process
table, smurf, syslogd, teardrop e udpstorm.
• User to Root (U2R): ataque no qual o atacante que possui uma conta normal na máquina
consegue obter acesso à conta de administrador, através de alguma vulnerabilidade.
Exemplos: eject, ffbconfig, fdformat, loadmodule, perl, ps e xterm;
• Remote to Local (R2L): ataque em que o objetivo é, a partir de alguma vulnerabilidade,
obter acesso a uma conta na máquina de forma remota. Exemplos: dictionary, ftp-write,
guest, imap, named, phf, sendmail, xlock e xsnoop.
20
Dois dos exemplos de ataques do tipo probing são ip sweep e nmap. No ataque
ip sweep, o atacante monitora a rede para descobrir quais máquinas estão disponı́veis. Isto
geralmente é feito a partir do envio de pacotes ICMP de ping a todos os possı́veis endereços
de uma sub-rede e verificação de quais máquinas respondem. Para detectar esse tipo de ataque,
pacotes de ping enviados a todas as máquinas da rede, vindos de uma mesma origem, podem
ser procurados (KENDALL, 1999).
O nmap é uma ferramenta para escaneamento de portas de uma rede. Assim, por
exemplo, pode ser efetuado um escaneamento para descobrir portas abertas numa determinada
máquina. A ferramenta permite que o usuário especifique quais as portas a serem escaneadas,
o intervalo de tempo entre os escaneamentos e se as portas devem ser escaneadas de forma
sequencial ou de forma aleatória. Um ataque de escaneamento de porta pode ser detectado
a partir da constatação de que pacotes tenham sido enviados a várias portas de uma máquina
dentro de uma janela de tempo (KENDALL, 1999).
2.1.1
DETECÇÃO BASEADA EM ASSINATURA
Quanto à técnica de detecção, um IDS divide-se em baseado em assinatura e baseado
em anomalia. No primeiro, o sistema mantém uma lista de padrões de ataques conhecidos e
monitora os eventos de rede à procura destes padrões (CATANIA; GARINO, 2012).
Uma vantagem do IDS baseado em assinatura é que as ameaças são detectadas
eficientemente e com uma baixa taxa de erros, pois o sistema consulta padrões de ataques
em seu banco de dados. Em compensação, esse sistema não consegue detectar novos tipos
de ataques ou variações dos ataques conhecidos. Além disso, na tentativa de deixar o sistema
atualizado, a lista de ataques conhecidos pode ficar grande de tal maneira que novos ataques
não possam ser incluı́dos.
Como exemplos de assinaturas podem ser citados: uma tentativa de conexão de um
endereço IP reservado e um pacote com combinação ilegal de flags do protocolo TCP. No
primeiro caso, a assinatura pode ser verificada a partir do campo endereço de origem do
cabeçalho IP. No segundo caso, as flags do cabeçalho TCP podem ser comparadas contra
combinações não permitidas previamente conhecidas.
Um dos NIDS mais utilizados comercialmente é o Snort, que detecta intrusões por
assinatura. O programa possui três modos de operação: farejamento, registro de pacote e
detector de intrusão de rede. No modo de farejamento, os pacotes da rede são lidos e mostrados
na tela. No modo de registro de pacote, os pacotes são gravados em disco. No modo de detecção
21
de intrusão, o tráfico é monitorado e comparado contra as assinaturas da ferramenta, podendose identificar diversos tipos de ataques de rede. A ferramenta permite, também, que o usuário
escreva assinaturas ou regras de detecção próprias (SOURCEFIRE, 2014).
2.1.2
DETECÇÃO BASEADA EM ANOMALIA
No IDS baseado em anomalia o objetivo é criar um modelo de comportamento normal
ou de anomalia, para assim classificar cada evento em uma dessas categorias. No caso em que o
comportamento normal é modelado, um alarme é gerado quando um evento desvia em relação
ao modelo. No caso em que o comportamento anômalo é modelado, um alarme é gerado quando
um evento condiz com o modelo (GARCÍA-TEODORO et al., 2009).
Uma vantagem desse sistema é que ataques previamente desconhecidos podem ser
detectados. Em compensação, o IDS baseado em anomalia é suscetı́vel a alarmes falsos, pois
uma ameaça pode ter caracterı́sticas semelhantes às de um evento legı́timo e vice-versa. Um
alarme é dito falso-positivo quando um evento legı́timo é classificado como ameaça, e falsonegativo quando uma ameaça é classificada como evento legı́timo. Há, ainda, as situações de
verdadeiro-positivo, quando uma ameaça é classificada como ameaça e verdadeiro-negativo,
quando um evento legı́timo é classificado como legı́timo.
Um IDS baseado em anomalia é eficiente se as taxas de falso-positivo e falsonegativo são baixas e as taxas de verdadeiro-positivo e verdadeiro-negativo são altas (GARCÍATEODORO et al., 2009). Para garantir a eficiência, o modelo deve ser atualizado sempre que
houver mudanças nas definições de comportamento normal ou de ataque.
Apesar da possibilidade de alarmes falsos, a detecção baseada em anomalia é uma
importante técnica para IDS, porque a rede sempre está exposta a novas ameaças. O desafio
consiste em descobrir fronteiras entre comportamentos normais e anômalos para uma boa
acurácia de classificação (WU; BANZHAF, 2010).
De acordo com o processo de modelagem de detecção, as técnicas de detecção
por anomalia podem ser divididas em três grupos: baseadas em estatı́stica, baseadas em
conhecimento e baseadas em Aprendizagem de Máquina (GARCÍA-TEODORO et al., 2009).
Nas técnicas baseadas em estatı́stica, o modelo de comportamento é criado a partir do
perfil estatı́stico do tráfego de rede. O perfil é construı́do a partir de métricas como a taxa de
tráfego, número de pacotes relativos a um protocolo, taxa de conexões, número de diferentes
endereços IP, etc. Em tempo real, o perfil estatı́stico do tráfego é obtido e comparado com o
perfil previamente traçado. Se o grau de irregularidade de um determinado evento superar um
22
certo limiar, o sistema gera um alarme (GARCÍA-TEODORO et al., 2009).
Uma vantagem das técnicas baseadas em estatı́stica é que um conhecimento prévio
sobre as atividades consideradas normais não é necessário. Uma desvantagem é a dificuldade de
configuração dos parâmetros estatı́sticos. Além disso, o sistema muitas vezes utiliza suposições
estáticas das atividades de rede (GARCÍA-TEODORO et al., 2009).
Nas técnicas baseadas em conhecimento, a classificação dos eventos de rede é feita
a partir de um conjunto de regras, envolvendo três fases. Primeiro, diferentes atributos e
classes são identificados a partir dos eventos de treinamento. Depois, um conjunto de regras,
parâmetros e procedimentos de classificação são deduzidos. Por fim, o evento é classificado.
Por exemplo, o conjunto de regras pode ser especificado manualmente por um especialista,
descrevendo assim o comportamento esperado (GARCÍA-TEODORO et al., 2009).
As técnicas baseadas em conhecimento têm como prós: robustez, flexibilidade e
escalabilidade. E como contras: dificuldade e tempo necessário para se obter conhecimento
sobre os eventos de rede a serem analisados (GARCÍA-TEODORO et al., 2009).
Nas técnicas baseadas em Aprendizagem de Máquina, classificadores podem ser
utilizados para construção de um modelo de comportamento para os eventos de rede, e assim
todo o tráfego pode ser testado usando esse modelo (TSAI et al., 2009). Se o classificador
assinalar o tráfego como ameaça, o sistema deve avisar a gerência de rede. As caracterı́sticas do
tráfego de rede que podem ser avaliadas incluem valores obtidos diretamente do cabeçalho
dos pacotes, como o tipo de protocolo e as flags do cabeçalho TCP, e variáveis de estado
dependentes da comunicação entre origem e destino, como número de bytes trocados (GOGOI
et al., 2012).
Os classificadores de Aprendizagem de Máquina possuem importantes caracterı́sticas,
como adaptabilidade, tolerância a erros e resiliência a ruı́dos (WU; BANZHAF, 2010). Também
são aplicáveis em tarefas de aprendizagem em que não há conhecimento prévio sobre os padrões
a serem classificados (BRUGGER, 2004). Mas são altamente dependentes do modelo gerado, e
consequentemente da qualidade dos dados de treinamento (GARCÍA-TEODORO et al., 2009).
2.2
APRENDIZAGEM DE MÁQUINA
Nesta seção será fundamentada a teoria da Aprendizagem de Máquina, visto que alguns
algoritmos de aprendizagem foram estudados, desenvolvidos e implementados para detecção de
probing no presente trabalho.
23
As técnicas de Aprendizagem de Máquina são usadas para classificar padrões de dados
em categorias ou classes. Para este fim, são utilizados dados de treinamento, previamente
categorizados, para construção de um modelo de aprendizado (classificador). Uma vez gerado
o modelo, novos padrões de dados podem ser classificados (MITCHELL, 1997).
Na fase de aprendizagem, utiliza-se um conjunto de dados de treinamento previamente
rotulados e um algoritmo gerador do modelo. Essa fase pode ser computacionalmente intensa
e a qualidade do conjunto de dados afeta diretamente a qualidade do modelo a ser obtido (WU;
BANZHAF, 2010).
Na fase de classificação, as mesmas caracterı́sticas avaliadas nos exemplos de
treinamento são extraı́das dos novos exemplos a serem classificados. Essas caracterı́sticas são
aplicadas, então, ao classificador para escolha das classes dos novos exemplos.
Em resumo, o ciclo do projeto em Aprendizagem de Máquina é dividido em cinco
etapas: obtenção de dados, escolha das caracterı́sticas, escolha do classificador, treinamento
(aprendizagem) e avaliação de resultados.
2.2.1
EXTRAÇÃO DE CARACTERÍSTICAS
Nesta seção será fundamentada a teoria da extração de caracterı́sticas, etapa preliminar
ao uso de um classificador. No presente trabalho, um algoritmo extrator de caracterı́sticas foi
implementado para detecção de probing.
Para a classificação de padrões por Aprendizagem de Máquina, o primeiro passo é
extrair caracterı́sticas que distinguem bem os padrões. As caracterı́sticas podem ser valores
numéricos e não-numéricos. Um caso clássico da literatura é a separação de duas espécies
de peixes: robalo e salmão (DUDA et al., 2002). Neste caso, uma câmera pode fotografar
os peixes, para que na sequência algumas caracterı́sticas sejam extraı́das. Antes da extração,
porém, é necessária uma etapa de pré-processamento, para isolar os peixes nas imagens. A
figura 2 mostra o arranjo do problema juntamente com as etapas necessárias para classificação.
O objetivo da extração de caracterı́sticas é reduzir a quantidade de dados, descrevendo
as amostras a partir de atributos ou caracterı́sticas. No problema exemplo, podem-se imaginar
algumas caracterı́sticas que diferenciam as duas espécies, como comprimento, luminosidade,
largura, número e forma das nadadeiras e posição da boca. A figura 3 mostra um possı́vel
histograma separando uma quantidade de robalo e salmão por comprimento. Na média, os
robalos parecem maiores que os salmões, porém não há um valor limiar de comprimento que
separe bem as duas classes.
24
Figura 2: Arranjo de um exemplo clássico de Aprendizagem de Máquina: separação de peixes em
salmão e robalo e etapas necessárias para classificação.
Fonte: Duda et al. (2002)
Figura 3: Histograma para a caracterı́stica comprimento para as duas classes.
Fonte: Duda et al. (2002)
Agora, na figura 4, tem-se um histograma separando os peixes por luminosidade.
Percebe-se que essa separação é mais satisfatória que a separação por comprimento. Ainda
assim, não há um valor limiar de luminosidade que separe completamente as duas classes. O
menor número de erros de classificação acontece para x*. Admitindo-se erros de classificação,
esse valor pode ser deslocado para a direita ou esquerda. Deve ser avaliado o custo para o erro,
pois para quem compra um robalo não há muita insatisfação caso o peixe entregue seja um
salmão, mas o caso inverso gera enorme insatisfação, pois o salmão é mais caro.
25
Figura 4: Histograma para a caracterı́stica luminosidade para as duas classes.
Fonte: Duda et al. (2002)
Na procura por outra caracterı́stica, pode-se observar que em geral o robalo é mais
largo que o salmão. Mas, considerando que nenhuma caracterı́stica sozinha separa bem as
classes, pode-se usar mais de uma caracterı́stica. Utilizando vetores do tipo v = (luminosidade,
largura) para descrever os exemplos no espaço bidimensional, obtém-se a figura 5. Pode-se
definir a reta mostrada como a fronteira de decisão, em que todos os pontos abaixo da reta são
classificados como salmão e todos os pontos acima da reta são classificados como robalo.
Figura 5: Salmões e robalos espalhados no plano conforme as caracterı́sticas luminosidade e
largura. A decisão de fronteira escolhida é a reta que melhor separa as duas classes.
Fonte: Duda et al. (2002)
A fronteira de decisão escolhida ainda produz erros de classificação, mas percebe-se
que esta generaliza o problema. Poderia ser escolhida uma fronteira não linear que mudasse
26
suas curvas para separar completamente as duas classes. Porém, o objetivo da aprendizagem é
generalizar a classificação para novos exemplos e não se adaptar completamente aos exemplos
de treinamento (DUDA et al., 2002).
2.2.2
CLASSIFICADOR ÁRVORE DE DECISÃO
Nesta subseção será fundamentada a teoria da Árvore de Decisão, pois este foi o
primeiro classificador desenvolvido e implementado para detecção de probing no presente
trabalho.
A Árvore de Decisão é implementada como um conjunto de regras ‘se-então’ e
classifica um exemplo atravessando uma estrutura em árvore até que uma folha associada a
uma classe seja atingida. Cada nó da árvore testa uma caracterı́stica (atributo) do exemplo a
ser classificado, e cada ramo, partindo de um nó, corresponde a um dos valores possı́veis da
caracterı́stica. Os nós finais são chamados de folhas e correspondem às possı́veis classes. A
Árvore de Decisão deve ser considerada quando o problema-alvo possui instâncias descritas
por um conjunto fixo de atributos com classes de saı́da discretas. (MITCHELL, 1997).
A figura 6 apresenta um exemplo de Árvore de Decisão para classificação de frutas. A
classificação é feita de cima para baixo, começando pela raiz da árvore na qual o atributo cor é
testado. A partir do valor do primeiro atributo, o próximo atributo (tamanho ou forma) é testado
no nó correspondente. Este processo se repete até que uma folha contendo uma das possı́veis
classes da instância seja selecionada: melancia, maçã, uva, banana, toranja, limão ou cereja.
Figura 6: Exemplo de uma Árvore de Decisão para classificação de frutas.
Fonte: Adaptado de Duda et al. (2002)
Um vetor do tipo v = (doce, vermelha, redonda, médio) para as caracterı́sticas (sabor,
cor, forma, tamanho) é classificado como maçã. No primeiro teste, o da cor, é selecionado o
27
terceiro ramo, pois a cor do exemplo a ser classificado é vermelha. O segundo teste, então, é o do
tamanho. Como no exemplo o tamanho é médio, esse é classificado como maçã. Esse simples
exemplo mostra uma das vantagens da Árvore de Decisão com relação a outros classificadores:
a interpretabilidade (DUDA et al., 2002). O modelo é composto por regras que são fáceis de
visualizar e de entender.
O algoritmo básico para a construção do modelo da árvore, a partir de exemplos de
treinamento previamente categorizados, é o ID3 (Iterative Dichotomiser 3). A primeira tarefa
é determinar qual o atributo a ser testado na raiz da árvore. Para isso, cada atributo é avaliado
a partir de um parâmetro estatı́stico — o ganho de informação — para determinar o quão bem
separa as classes dos exemplos de treinamento. O atributo com maior ganho de informação é
escolhido como raiz da árvore. Um nó descendente é então criado para cada valor possı́vel do
atributo raiz e o processo de avaliação dos atributos é repetido (MITCHELL, 1997).
No ID3 é realizada uma busca ‘gulosa’ por uma árvore que se encaixe com os exemplos
de treinamento, na qual o algoritmo nunca reconsidera as escolhas anteriores. Obrigatoriamente
os atributos também devem ter valores discretos para o cálculo do ganho de informação. Uma
evolução do ID3 é o algoritmo C4.5, que permite trabalhar com atributos de valores contı́nuos
(MITCHELL, 1997).
O ganho de informação faz uso de outro parâmetro estatı́stico: a entropia, que
caracteriza a pureza ou impureza de uma coleção aleatória de exemplos. A entropia de um
conjunto de exemplos S com c classes é definida na equação (1), na qual pi é a proporção de
exemplos da classe i em S (MITCHELL, 1997).
c
Entropia(S) = ∑ −pi log2 pi
(1)
i=1
A partir da entropia, pode ser calculado o ganho de informação G(S, A) de um atributo
A, relativo à coleção de exemplos S, conforme a equação (2). Nesta, Valores(A) é o conjunto
de todos os valores possı́veis do atributo A, Sv é o subconjunto de S para o qual A tem valor
v, |Sv | é a quantidade de exemplos de Sv e |S| é a quantidade de exemplos de treinamento de S
(MITCHELL, 1997).
Ganho(S, A) = Entropia(S) −
|Sv |
Entropia(Sv )
|S|
v∈Valores(A)
∑
(2)
A construção da Árvore de Decisão termina após todos os atributos terem sido
considerados nos nós da árvore.
28
2.2.3
CLASSIFICADOR NAIVE BAYES
Nesta subseção será fundamentada a teoria do Naive Bayes, pois este foi o segundo
classificador desenvolvido e implementado para detecção de probing no presente trabalho.
Os algoritmos bayesianos utilizam distribuições de probabilidade para descrever a
relação entre dados e classes. Para a classificação de um novo exemplo, são calculadas
as probabilidades desse pertencer a cada classe e, então, a classe de maior probabilidade
é assinalada.
O conhecimento prévio sobre o problema deve ser aplicado e quando as
probabilidades iniciais não são conhecidas, estes valores devem ser estimados a partir dos
exemplos de treinamento (MITCHELL, 1997). O teorema de Bayes é dado pela equação (3):
P(c|X) =
P(X|c)P(c)
P(X)
(3)
Em que:
• P(c|X) é a probabilidade da classe c dado o vetor X, ou seja, a probabilidade do vetor X
pertencer à classe c;
• P(X|c) é a probabilidade do vetor X dada a classe c, ou seja, a probabilidade do vetor X
existir tendo c como classe;
• P(c) é a probabilidade prévia da classe c, que não depende do vetor X;
• P(X) é a probabilidade prévia do vetor X existir;
Para calcular a classe de maior probabilidade, o denominador pode ser desprezado,
pois é uma constante que independe das classes. Assim, a classe a ser escolhida é dada pela
equação (4), em que c j corresponde às possı́veis classes do problema (MITCHELL, 1997).
c = arg max P(X|c j ) · P(c j )
(4)
O termo P(c j ) é calculado como o número de exemplos da classe c j divido pelo
número total de exemplos de treinamento. O termo P(X|c j ), com X tendo n atributos, é
calculado, para cada classe c j , considerando todas as combinações possı́veis dos diferentes
valores dos n atributos de X. Para simplificar essa condição, o classificador Naive Bayes assume
que os atributos são condicionalmente independentes. Assim, a probabilidade P(X|c j ) pode ser
calculada pelo produto das probabilidades individuais de cada atributo inferindo a classe c j
29
(MITCHELL, 1997). Se o vetor X tem n atributos, a classe escolhida pelo classificador Naive
Bayes é dada pela equação (5).
n
cnb = arg max
!
∏ P(ai|c j )
· P(c j )
(5)
i=1
Na equação, o subscrito nb indica Naive Bayes. Se o atributo ai de um exemplo de
teste tem valor v, o termo P(ai |c j ) é igual à divisão do número de exemplos de treinamento da
classe c j com atributo ai igual a v pelo número total de exemplos de treinamento.
Se os valores dos atributos forem contı́nuos, estes devem ser discretizados antes da
aplicação da equação. Isso é feito a partir da definição de intervalos de variação para os valores
de atributo. Assim, haverá probabilidades para cada intervalo (DUDA et al., 2002).
2.2.4
CLASSIFICADOR K-VIZINHOS MAIS PRÓXIMOS (KNN)
Nesta subseção será fundamentada a teoria do kNN, pois este foi o terceiro
classificador desenvolvido e implementado para detecção de probing no presente trabalho.
Alguns classificadores de Aprendizagem de Máquina, como a Árvore de Decisão e o
Naive Bayes, constroem uma descrição explı́cita da função-alvo de classificação a partir dos
exemplos de treinamento. O mesmo não acontece para os algoritmos baseados em instâncias.
Neste caso, não há construção de um modelo e a etapa de treinamento consiste simplesmente
em armazenar os exemplos de treinamento em memória (MITCHELL, 1997).
O algoritmo baseado em instâncias mais fundamental é o kNN, o qual classifica novas
instâncias a partir do grau de similaridade para com os exemplos de treinamento. Assim, a
aproximação da função-alvo acontece na hora da classificação e muda para cada nova instância.
O kNN assume que as instâncias podem ser representadas no espaço Euclidiano, em
que cada atributo corresponde a uma coordenada. Assim, por exemplo, num problema cujas
instâncias tenham três atributos, estas podem ser representadas no espaço tridimensional. Uma
implicação é que os atributos precisam ser valores numéricos. Para a classificação de uma
nova instância, o kNN procura os k exemplos de treinamento mais similares e atribui a classe
que mais aparece entre esses k exemplos. A medida de similaridade empregada é a distância
Euclidiana. Então, os k exemplos mais similares são os k vizinhos mais próximos da instância
de teste a ser classificada. O k é um parâmetro de projeto do classificador (MITCHELL, 1997).
Para encontrar os k vizinhos mais próximos de uma instância de teste, o algoritmo
precisa computar a distância dessa para todos os exemplos de treinamento.
A distância
30
Euclidiana entre duas instâncias v1 = (a1 , a2 , ..., an ) e v2 = (b1 , b2 , ..., bn ) de n atributos
é calculada conforme a equação (6).
O algoritmo também precisa manter os k pares
distância/classe correspondentes aos vizinhos, para que ao final das iterações, a classe de maior
ocorrência seja assinalada.
s
d(v1 , v2 ) =
n
∑ (bi − ai)2
(6)
i=1
O funcionamento gráfico do kNN pode ser conferido na figura 7. Neste problema, há
14 instâncias de treinamento: 7 da classe azul e 7 da classe vermelha. Cada instância possui
dois atributos, de modo que podem ser representadas no espaço bidimensional. Há também uma
instância de teste, representada em branco, a qual se quer classificar como azul ou vermelha.
Figura 7: Exemplo gráfico da classificação de uma instância em azul ou vermelha pelo kNN.
Fonte: Autoria Própria
Considerando a distância Euclidiana, temos que para:
• k = 1: A classe da instância de teste será vermelha, pois a instância de treinamento mais
próxima pertence à classe vermelha;
• k = 2: A classe da instância de teste pode ser vermelha ou azul (critério de projeto), pois
há uma instância de treinamento de cada classe nas proximidades;
• k = 3: A classe da instância de teste será azul, pois entre as três instâncias de treinamento
mais próximas, duas são da classe azul. Para esse caso é mostrada a região esférica que
abriga os três vizinhos mais próximos.
31
No exemplo, os atributos das instâncias têm magnitudes semelhantes. Mas em outros
casos isso pode não acontecer. Para evitar que atributos com um intervalo maior de valores
possı́veis tenham maior influência no cálculo da distância, é necessário normalizar os atributos.
Por exemplo, todos os atributos podem ser normalizados entre -1 e +1.
2.3
APRENDIZAGEM DE MÁQUINA PARA DETECÇÃO DE INTRUSÃO
Nesta seção será apresentado o estado da arte dos trabalhos que envolvem o uso de
extração de caracterı́sticas, Árvore de Decisão, Naive Bayes e kNN para detecção de intrusão,
em software e hardware.
2.3.1
APLICAÇÕES DE EXTRAÇÃO DE CARACTERÍSTICAS EM SOFTWARE E
HARDWARE
Para detectar intrusões, o primeiro passo é extrair caracterı́sticas dos pacotes de rede
para análise. A seguir, serão apresentados alguns trabalhos da literatura que aplicam extração
de caracterı́sticas. Em alguns casos não foram utilizados classificadores de Aprendizagem de
Máquina para detecção de intrusão, mas considera-se aqui que o processamento de atributos
dos pacotes antes da fase de detecção é uma forma de extração de caracterı́sticas.
Na literatura, boa parte dos estudos de detecção de intrusão por anomalia utiliza o
conjunto de dados público KDD 99 (UNIVERSITY OF CALIFORNIA, IRVINE, 1999). Este
foi construı́do a partir do banco de dados DARPA Intrusion Detection Evaluation Data Set,
gerado pelo Lincoln Labs do Massachusetts Institute of Technology em 1998. O laboratório
montou um ambiente para adquirir dados de uma simulação da rede local da Força Aérea
americana durante nove semanas. Na simulação também foram gerados ataques dos tipos
probing, DoS, U2R e R2L. Ao todo, foram gerados cinco milhões de conexões de treinamento
e dois milhões de conexões de teste.
Para avaliação do KDD 99 foram extraı́das 41 caracterı́sticas dos registros de conexões,
divididas em três grupos, conforme mostra o quadro 1. Apesar de ser bastante utilizado, o KDD
99 é antigo e, desde a sua montagem, os padrões de tráfego normal mudaram bastante e os
ataques de rede evoluı́ram. Por isso, novos conjuntos de dados para NIDS têm sido propostos.
Para geração do conjunto de dados geralmente utiliza-se um cenário de rede
envolvendo máquinas hosts e um servidor.
Gogoi et al. (2012) montaram um ambiente
composto por um roteador conectado à internet, switches para interconexão da rede local, um
servidor e máquinas clientes. Dentre os clientes, algumas máquinas eram responsáveis por gerar
32
Grupo de caracterı́sticas Quantidade
De pacotes individuais
9
De tráfico, considerando
uma janela de tempo
de 2 segundos
19
Do conteúdo da conexão
(carga útil dos pacotes)
13
Exemplos
tipo de protocolo, número de bytes enviados e
tipo de serviço de rede
número de conexões para o mesmo host,
número de conexões para o mesmo serviço e
porcentagem de conexões com erros
de sincronismo
número de tentativas de login sem sucesso,
número de acessos de administrador e
número de operações de criação de arquivo
Quadro 1: Atributos dos pacotes considerados no banco de dados KDD 99.
Fonte: Adaptado de UNIVERSITY OF CALIFORNIA, IRVINE (1999)
ataques contra máquinas vı́timas. Para geração do tráfego de ataque foram utilizados scripts em
linguagem C. Utilizou-se tráfego simulado de internet para produção dos registros normais.
Com relação às caracterı́sticas utilizadas para detecção de intrusão, há várias propostas
para classificação de tráfego em normal ou ataque. Davis e Clark (2011) escreveram uma
revisão do estado da arte no pré-processamento de dados envolvendo aplicações de NIDS,
incluindo uma lista grande de caracterı́sticas sugeridas pelos trabalhos analisados.
Para detecção de probing, em geral são utilizadas caracterı́sticas provenientes do
cabeçalho dos pacotes. A análise do cabeçalho reduz os requerimentos de processamento, pois
o cabeçalho corresponde apenas a uma pequena porção do pacote. Além disso, a abordagem
através do cabeçalho continua válida mesmo quando a carga útil do pacote está criptografada.
Outra vantagem do processamento apenas do cabeçalho é que existem ferramentas prontas para
este fim, como Libpcap, Tcpdump e NetFlow (DAVIS; CLARK, 2011).
Em geral, as caracterı́sticas analisadas são provenientes dos cabeçalhos IP, UDP, ICMP
e TCP, mostrados, respectivamente, nas figuras 8, 9, 10 e 11. Todos os pacotes de rede
possuem cabeçalho IP (20 bytes), após os 14 bytes do cabeçalho Ethernet. Os cabeçalhos UDP
(8 bytes), ICMP (8 bytes) e TCP (20 bytes), para os pacotes destes protocolos, aparecem após o
cabeçalho IP.
Alguns trabalhos consideram apenas caracterı́sticas individuais do cabeçalho dos
pacotes para detecção de probing. Um dos trabalhos pioneiros com essa propriedade foi o
Spade, que funciona como um plugin do Snort (STANIFORD et al., 2002). Foram considerados
como atributos os endereços IP de origem e destino e as portas de origem e destino, que
são extraı́dos a partir do próprio Snort.
probabilidades, para detecção de probing.
Utilizou-se uma técnica estatı́stica, baseada em
33
Figura 8: Campos do cabeçalho IP.
Fonte: Adaptado de Postel (1981a)
Figura 9: Campos do cabeçalho UDP.
Fonte: Adaptado de Postel (1980)
Figura 10: Campos do cabeçalho ICMP.
Fonte: Adaptado de Postel (1981b)
Figura 11: Campos do cabeçalho TCP.
Fonte: Adaptado de Postel (1981c)
34
Porém, como os ataques de rede podem ser encontrados a partir de um conjunto de
pacotes em vez de um único pacote, caracterı́sticas relativas à conexão também devem ser
consideradas (DAVIS; CLARK, 2011).
As caracterı́sticas relativas à conexão também podem vir do cabeçalho dos pacotes,
mas nesse caso são considerados os vários pacotes que compõem uma única conexão ou
múltiplas conexões. O tráfico numa única conexão é unidirecional e tem endereços e portas
em comum. As caracterı́sticas são observadas durante o fluxo de conexão, como contadores de
pacotes, contadores de bytes e tempo médio de chegada de pacotes (DAVIS; CLARK, 2011).
Estevez-Tapiador et al. (2003) consideraram as flags do cabeçalho TCP como
caracterı́sticas para detecção de ataques. Esses atributos foram extraı́dos com o tcpdump.
Para cada conexão, quantizou-se a sequência de combinação das flags em sı́mbolos, para uso
num modelo de Cadeias de Markov. Assim, foi possı́vel detectar ataques que modificavam o
comportamento normal das sessões TCP.
Quando múltiplas conexões são analisadas, como nos casos em que hosts utilizam
vários serviços diferentes (um por vez), considera-se uma certa janela de tempo. Nos trabalhos
da literatura, podem ser encontradas janelas que variam de 2s até 24h (DAVIS; CLARK, 2011).
Muraleedharan et al. (2010) consideraram os seguintes atributos: número de pacotes,
tamanho médio do pacote, duração média da sessão, número de sessões, número médio de
pacotes por sessão e número de sessões com apenas um pacote. A partir destes atributos,
extraı́dos com o NetFlow, construiu-se um modelo de comportamento normal para os protocolos
TCP, UDP e ICMP. Ataques probing e DoS foram detectadas a partir do teste Qui-quadrado.
Há alguns trabalhos que envolvem NIDS em hardware. Song e Lockwood (2005)
desenvolveram um sistema em FPGA (Xilinx XCV2000E) que implementa 222 regras do
Snort para detecção de intrusão a partir dos cabeçalhos dos pacotes. A entrada do circuito
é um pacote e os atributos analisados são os endereços IP e as portas de origem e destino e o
protocolo. Para extrair os atributos, simplesmente acessou-se o offset de cada campo. De acordo
com os valores dos atributos, os pacotes são compactados numa sequência de bits para serem
comparados com as assinaturas do Snort (armazenadas em blocos de memória RAM). Foram
utilizados o algoritmo Bit Vector (BV) e a estrutura de Memória de Conteúdo Endereçável
Ternária (TCAM) para resumir as informações dos pacotes a partir dos atributos. Foi obtida
uma taxa de transferência da ordem de 2,5 Gbps para a arquitetura completa.
Katashita et al. (2007) também desenvolveram um sistema que implementa regras do
Snort. Além de assinaturas para os cabeçalhos, foram incluı́das também assinaturas para a
35
carga útil dos pacotes, totalizando 1225 regras. A entrada do circuito é um pacote. O NIDS
incluiu duas placas com FPGA. A placa principal continha a FPGA Virtex-II Pro 100, na qual
foram sintetizados os circuitos de comparação das regras do Snort. Utilizou-se a técnica do
Autômato Finito Não-determinı́stico (NFA) para comparação dos bits das assinaturas. A placa
de interface continha a FPGA Virtex-II Pro 7, a qual recebia o tráfego ethernet e transmitia
para a placa principal via protocolo 10 Gigabit Ethernet XAUI. O circuito principal ocupou em
média 62.500 células lógicas. Obteve-se uma taxa de transferência de 10 Gbps para o NIDS.
Mediu-se ainda o consumo energético do sistema completo: 49 W.
Das et al. (2008) desenvolveram uma arquitetura, em FPGA (Xilinx Virtex II
xc2v1000), composta de um módulo de extração de caracterı́sticas e um módulo de detecção,
que utiliza a técnica estatı́stica Análise de Componentes Principais (PCA) para detectar port
scan e syn flood. A arquitetura tem como entrada o cabeçalho dos pacotes e considera as flags
do TCP ao longo de uma conexão como atributos. O módulo de extração tem quatro partes. A
primeira recebe os endereços IP e portas de origem e destino, que formam uma chave, e as flags
do TCP. A segunda parte é composta por funções hash de Jenkins, que fornecem um endereço
a partir da chave. A terceira parte é uma tabela, em forma de memória, que é acessada pelas
hashes e armazenam os valores das flags. A última parte do extrator calcula o valor agregado
dos atributos a partir da tabela. O extrator se mostrou eficiente, pois resumiu as informações
das conexões numa porção constante de memória. Para analisar os resultados da sistema foram
utilizados registros do KDD 99. Com relação ao extrator de caracterı́sticas, obteve-se uma taxa
de transferência da ordem de 21 Gbps.
A partir da análise dos trabalhos desta subseção, conclui-se que poucos trabalhos do
estado da arte apresentam resultados especı́ficos quando à extração de caracterı́sticas. Em
geral, os valores de taxas de transferência são apresentados para o sistema completo. Também
é pequeno o número de trabalhos que apresentam comparações entre implementações em
software e hardware e medições de consumo dos sistemas de detecção de intrusão.
Pode-se dizer, ainda, que boa parte dos trabalhos de detecção de intrusão em hardware
apresenta implementações das assinaturas do Snort, em detrimento das técnicas de detecção
por anomalia. Outros trabalhos com essa caracterı́stica são: (HARWAYNE-GIDANSKY et al.,
2009), (LE; PRASANNA, 2013) e (PONTARELLI et al., 2013).
2.3.2
APLICAÇÕES DE ÁRVORE DE DECISÃO EM SOFTWARE E HARDWARE
A Árvore de Decisão é uma boa escolha para detecção de intrusão por algumas
razões: os dados de entrada podem ser contı́nuos ou discretos, não há necessidade de pré-
36
processamento, o modelo é de fácil entendimento e o classificador não é computacionalmente
intenso. Além disso, as classes de saı́da são discretas: normal ou ataque. Uma desvantagem é
que se o modelo necessitar de atualização, a árvore inteira deve ser reconstruı́da.
Koshal e Bag (2012) criaram dois modelos detectores de intrusão, um com a Árvore
de Decisão e outro com o SVM. Os dados de treinamento e teste foram retirados do NSL-KDD,
um banco de dados criado a partir do KDD 99, mas com algumas melhorias como a exclusão
de registros duplicados (UNIVERSITY OF NEW BRUNSWICK, 2014). Antes do modelo da
árvore ser gerado, utilizou-se o algoritmo de Seleção de Caracterı́sticas baseado em Correlação
(CFS) que selecionou 11 atributos relevantes (para a classificação) do total de 41 atributos do
NSL-KDD. Mostrou-se que para o conjunto de teste, a árvore obteve uma acurácia de 99,9%.
Ibrahim et al. (2012) criaram quatro modelos detectores de intrusão com a Árvore de
Decisão, cada um com um tipo diferente de algoritmo: C5 (sucessor do algoritmo C4.5), CRT,
QUEST e CHAID. Os conjuntos de dados de treinamento e teste foram retirados do NSL-KDD
e os ataques alvo de detecção foram probing, DoS, R2L e U2R. Mostrou-se que para o conjunto
de teste, as acurácias para os diferentes algoritmos variaram de 93% a 99%.
Os dois trabalhos citados acima foram avaliados em software. Foram apresentados
apenas resultados de acurácia de classificação, sem avaliação de taxa de transferência e consumo
energético. Utilizou-se o NSL-KDD para modelagem dos classificadores, então a acurácia
obtida pode não ser a mesma no cenário de rede atual. Não foram encontrados trabalhos que
utilizam a Árvore de Decisão para detecção de intrusão de rede em hardware.
2.3.3
APLICAÇÕES DE NAIVE BAYES EM SOFTWARE E HARDWARE
Uma vantagem do Naive Bayes para detecção de intrusão é que as probabilidades são
constantes para cada intervalo de atributo e, numa implementação baseada em tabela, o modelo
pode ser facilmente atualizado sem alteração da estrutura do classificador.
Li e Li (2010) criaram um modelo detector de intrusão que utiliza o Naive Bayes em
conjunto com o algoritmo AdaBoost. Os dados de treinamento e teste foram retirados do KDD
99 e os ataques alvo de detecção foram probing, DoS, R2L e U2R. Foram utilizados apenas seis
atributos para geração do modelo. A acurácia obtida para a base de dados de teste foi de 84%.
Mukherjee e Sharma (2012) criaram um modelo detector de intrusão que utiliza o
Naive Bayes. Os conjuntos de dados de treinamento e teste foram retirados do NSL-KDD.
Foram avaliadas algumas técnicas de seleção de caracterı́sticas, para reduzir o total de atributos
utilizados na modelagem do Naive Bayes. Mostrou-se que para a classificação dos vetores do
37
conjunto de teste em normal ou probing, os modelos após seleção de caracterı́sticas foram mais
eficientes que o modelo do classificador utilizando todas as 41 caracterı́sticas do NSL-KDD.
Tuncer e Tatar (2010) desenvolveram um NIDS na FPGA Cyclone III. O processador
Nios II, que pode ser sintetizado no interior da FPGA, foi utilizado para extrair os atributos e
classificar os pacotes em normal ou ataque com o Naive Bayes. Os atributos considerados no
modelo foram: protocolo, tamanho do pacote, endereço IP de origem, endereço IP de destino,
porta de origem e porta de destino. Para construção do modelo, foram gerados 250 pacotes de
treinamento, dos quais 199 eram normais e 51 eram ataques. No momento da classificação, são
calculadas as probabilidades do pacote ser normal e de ser ataque. Se a primeira probabilidade
for maior, o pacote é encaminhado. Caso contrário, o pacote é descartado. O sistema embarcado
foi testado com o próprio conjunto de treinamento e nesse caso a acurácia foi de 97,2%.
Vijayasarathy et al. (2011) desenvolveram um sistema para detecção de ataques DoS,
com o classificador Naive Bayes, na FPGA Virtex 4. Para pacotes do protocolo TCP, os atributos
considerados foram as flags do cabeçalho e o intervalo de tempo de chegada entre os pacotes.
Este último atributo também foi considerado para os pacotes do protocolo UDP. Os pacotes
de treinamento e de teste foram retirados do KDD 99 e de tráfego gerado pela Society for
Electronic Transactions and Security (SETS), instituição da área de segurança de rede da Índia.
As acurácias, para os diferentes conjuntos de dados, ficaram acima de 97%.
Nos trabalhos citados nesta subseção, foram apresentados apenas resultados de
acurácia de classificação, sem avaliação de taxa de transferência e consumo energético. Em
software, o KDD 99 serviu como base de dados para modelagem dos classificadores, então a
acurácia obtida pode não ser a mesma no cenário de rede atual. No primeiro deles, há outro
problema. Não foi utilizado algoritmo de seleção para definir os atributos mais relevantes para
classificação e por isso a acurácia no conjunto de teste ficou abaixo de 85%.
Os trabalhos em hardware utilizaram bases de dados atuais (e também o KDD 99 no
último artigo), mas não houve maiores explicações sobre como essas bases foram geradas. No
primeiro deles, há outros problemas. A acurácia foi avaliada apenas na base de treinamento, e
assim não é possı́vel concluir se o modelo classificador é genérico. Além disso, foram utilizados
apenas 250 pacotes para treinamento.
2.3.4
APLICAÇÕES DE KNN EM SOFTWARE E HARDWARE
O classificador kNN é apropriado para detecção de intrusão porque fornece uma
fronteira não linear entre as classes normal e ataque. Além disso, o modelo pode ser facilmente
38
atualizado, pois consiste apenas em exemplos de treinamento armazenados em memória. Uma
desvantagem do kNN é o alto esforço computacional, que ocorre inteiramente na hora da
classificação e cresce com o número de instâncias de treinamento.
Li e Guo (2007) criaram um modelo detector de intrusão, baseado em anomalia,
que utiliza o kNN em conjunto com o algoritmo Transductive Confidence Machines (TCM).
Utilizou-se o TCM para reduzir o tamanho do conjunto de dados de treinamento necessário no
kNN. Os conjuntos de dados de treinamento e teste foram retirados do KDD 99 e os ataques
alvo de detecção foram probing, DoS, R2L e U2R. Mostrou-se que para o conjunto de teste, o
modelo TCM-kNN obteve uma acurácia maior do que 99%, acertando mais classificações que
os algoritmos SVM, Redes Neurais e kNN padrão, também analisados.
Cheng et al. (2009) criaram um modelo detector de intrusão que utiliza o kNN em
conjunto com o algoritmo Multivariate Adaptive Regression Splines (MARS). Utilizou-se o
MARS para selecionar a classe mais comum entre os k vizinhos selecionados pelo kNN. Os
conjuntos de dados de treinamento e teste também foram retirados do KDD 99. Mostrou-se que
para o conjunto de teste, o modelo kNN-MARS obteve uma acurácia na faixa de 98%, acertando
mais classificações que os algoritmos SVM e kNN padrão.
Os dois trabalhos citados acima foram avaliados em software. Foram apresentados
apenas resultados de acurácia de classificação, sem avaliação de taxa de transferência e consumo
energético. Utilizou-se o KDD 99 para modelagem dos classificadores, então a acurácia obtida
pode não ser a mesma no cenário de rede atual. Não foram encontrados trabalhos que utilizam
o kNN para detecção de intrusão de rede em hardware.
39
3
DESENVOLVIMENTO DO EXTRATOR DE CARACTERÍSTICAS
Neste capı́tulo será explicado o funcionamento do extrator de caracterı́sticas dos
pacotes de rede para detecção de probing existente e apresentado o desenvolvimento da
implementação correspondente em hardware. Serão apresentados, também, as plataformas e
métodos utilizados para avaliação e comparação das duas implementações.
3.1
IMPLEMENTAÇÃO EM SOFTWARE
Nesta seção será explicado o funcionamento do extrator de caracterı́sticas em software
que serviu de base para desenvolver a versão correspondente em hardware. O trabalho descrito
a seguir foi desenvolvido por Eduardo Kugler Viegas e pelo Prof. Dr. Altair Olivo Santin
(VIEGAS et al., 2013, 2014a, 2014b).
Os autores primeiramente montaram o banco de pacotes de rede, do qual os pacotes
são objetos de classificação. Para geração do tráfego criou-se o cenário com máquinas virtuais
mostrado esquematicamente na figura 12. O servidor é a máquina-alvo que recebe o tráfego e
deve classificá-lo como normal ou ataque.
O tráfego normal foi gerado com ferramentas de workload, a partir de requisições de
100 máquinas-cliente ao servidor: 54 gerando requisições HTTP, 33 gerando requisições SMTP,
7 gerando requisições SSH e 6 gerando requisições SNMP. O tráfego de probing foi gerado com
a ferramenta Nessus, programa usado para auditar uma rede à procura de possı́veis falhas. Com
o Nessus, selecionaram-se classes de ataques probing para inspeção e gerou-se o tráfego de
ataque contra o servidor.
Os tráfegos normal e de ataque foram gerados concomitantemente durante um perı́odo
de trinta minutos. Os pacotes foram armazenados num arquivo PCAP, o qual mantém o
histórico dos pacotes e pode ser utilizado como entrada para ferramentas de análise de rede. Ao
todo, foram gerados 9.431.075 pacotes, dos quais 9.416.113 são normais e 14.962 são ataques
probing. O software de extração de caracterı́sticas usa o arquivo PCAP como entrada.
40
Figura 12: Cenário para geração de tráfego normal e de ataque.
Fonte: Adaptado de Viegas et al. (2014a)
Com relação às caracterı́sticas, os autores seguiram a literatura e escolheram atributos
que podem ser extraı́dos: 1) diretamente do cabeçalho de cada pacote e 2) a partir dos pacotes
pertencentes a uma mesma comunicação entre hosts, considerando certa janela de tempo.
Os atributos escolhidos que podem ser extraı́dos diretamente do cabeçalho de cada
pacote são mostrados no quadro 2. Cada atributo, com exceção do payload length, possui um
prefixo (ip, udp, icmp, tcp) indicando a qual cabeçalho pertence. Os atributos do cabeçalho IP
são comuns a todos os pacotes, enquanto que os atributos dos cabeçalhos UDP, ICMP e TCP
estão presentes apenas nos pacotes de protocolo UDP, ICMP e TCP, respectivamente.
Os atributos dos cabeçalhos IP (para todos os pacotes) e UDP, ICMP e TCP (para
os pacotes com estes protocolos) estão em campos bem definidos nos pacotes. O atributo
payload length, que define o tamanho da carga útil, pode ser calculado a partir do tamanho
do pacote descontando-se o tamanho dos cabeçalhos.
Os atributos que podem ser extraı́dos a partir de uma mesma comunicação entre hosts
são mostrados no quadro 3. A maioria dos atributos são contadores e alguns são calculados a
partir do cabeçalho. Porém, nesse caso, considera-se cada conexão entre os hosts, dentro de
uma janela de 2 s. Em cada conexão, uma das máquinas é sempre o servidor e a outra máquina
pode ser um dos clientes que geram tráfego normal ou o cliente que gera ataques.
O extrator foi desenvolvido em C++. Foi utilizada a biblioteca Libpcap para ler os
pacotes do arquivo PCAP e acessar estruturas com os campos dos protocolos UDP, ICMP e TCP.
41
Número
Atributo
Descrição
Tamanho (bits)
1
ip type
Tipo de serviço
8
2
ip length
Tamanho do pacote IP
16
3
ip id
Número de identificação
16
4
ip offset
Offset do fragmento
13
5
ip RF
Flag reservada
1
6
ip DF
Flag “não fragmente”
1
7
ip MF
Flag “mais fragmentos”
1
8
ip proto
Protocolo (TCP, UDP ou ICMP)
8
9
ip checksum
Checksum do cabeçalho IP
16
10
udp sport
Porta de origem do cabeçalho UDP
16
11
udp dport
Porta de destino do cabeçalho UDP
16
12
udp length
Tamanho do datagrama
16
13
udp checksum
Checksum do datagrama
16
14
icmp type
Tipo da mensagem
8
15
icmp code
Código da mensagem
8
16
icmp checksum
Checksum da mensagem
16
17
tcp sport
Porta de origem do cabeçalho TCP
16
18
tcp dport
Porta de origem do cabeçalho TCP
16
19
tcp seq
Número de sequência
32
20
tcp ack
Número de confirmação
32
21
tcp ffin
Flag fin
1
22
tcp fsyn
Flag syn
1
23
tcp frst
Flag rst
1
24
tcp fpsh
Flag push
1
25
tcp fack
Flag ack
1
26
tcp furg
Flag urgent
1
27
payload length
Tamanho da carga útil
16
Quadro 2: Lista de atributos extraı́dos diretamente do cabeçalho de cada pacote para distinção
entre tráfego normal e de probing.
Fonte: Adaptado de Viegas et al. (2013).
Cada uma destas estruturas possui estruturas com os cabeçalhos Ethernet, IP e do protocolo
correspondente, além do timestamp e da carga útil do pacote. Variáveis int armazenam cada um
dos 50 atributos mostrados nos quadros 2 e 3.
Para extração das caracterı́sticas do quadro 2, as estruturas com os campos de cada
protocolo são acessadas. O quadro 4 explica como cada atributo é extraı́do dependendo do
protocolo do pacote. Quando o protocolo é TCP, os atributos relativos aos cabeçalhos UDP e
ICMP são igualados a zero. Um raciocı́nio semelhante pode ser aplicado aos protocolos UDP e
ICMP, com exceção para as flags do cabeçalho TCP. Para protocolos diferentes do TCP, as flags
são igualadas a dois, visto que zero (flag não setada) é um valor válido para o protocolo TCP.
42
Número
1
2
3
Atributo
conn status
count c2s
count s2c
4
count serv c2s
5
count serv s2c
6
num bytes c2s
7
num bytes s2c
8
num bytes serv c2s
9
num bytes serv s2c
10
num pushed c2s
11
num pushed s2c
12
num syn fin c2s
13
num syn fin s2c
14
num fin c2s
15
num fin s2c
16
num ack c2s
17
num ack s2c
18
num syn c2s
19
num syn s2c
20
num rst c2s
21
num rst s2c
22
first packet
23
first serv packet
Descrição
Estado da conexão TCP
No de pacotes enviados do cliente para o servidor
No de pacotes enviados do servidor para o cliente
No de pacotes enviados, para o mesmo
serviço, do cliente para o servidor
o
N de pacotes enviados, para o mesmo
serviço, do servidor para o cliente
No de bytes da carga útil enviados
do cliente para o servidor
o
N de bytes da carga útil enviados
do servidor para o cliente
o
N de bytes da carga útil, enviados para o
mesmo serviço, do cliente para o servidor
No de bytes da carga útil, enviados para o
mesmo serviço, do servidor para o cliente
No de pacotes com a flag PUSH setada
enviados do cliente para o servidor
o
N de pacotes com a flag PUSH setada
enviados do servidor para o cliente
No de pacotes com as flags SYN e FIN setadas
enviados do cliente para o servidor
o
N de pacotes com as flags SYN e FIN setadas
enviados do servidor para o cliente
No de pacotes com a flag FIN setada
enviados do cliente para o servidor
No de pacotes com a flag FIN setada
enviados do servidor para o cliente
No de pacotes com a flag ACK setada
enviados do cliente para o servidor
No de pacotes com a flag ACK setada
enviados do servidor para o cliente
No de pacotes com a flag SYN setada
enviados do cliente para o servidor
No de pacotes com a flag SYN setada
enviados do servidor para o cliente
No de pacotes com a flag RST setada
enviados do cliente para o servidor
No de pacotes com a flag RST setada
enviados do servidor para o cliente
Verdadeiro se é o primeiro pacote trocado pelos hosts
Verdadeiro se é o primeiro pacote
trocado pelos hosts para o mesmo serviço
Quadro 3: Lista de atributos extraı́dos a partir dos pacotes pertencentes a uma mesma
comunicação entre hosts, considerando um janela de tempo de 2 s, para distinção entre tráfego
normal e de probing.
Fonte: Adaptado de Viegas et al. (2013).
43
Atributos / Protocolo
Do cabeçalho IP
Do cabeçalho UDP
UDP
A partir da
estrutura IP
A partir da
estrutura UDP
Do cabeçalho ICMP
Do cabeçalho TCP
(portas, seq e ack)
Do cabeçalho TCP
(flags)
payload length
0
ICMP
A partir da
estrutura IP
TCP
A partir da
estrutura IP
0
0
A partir da
estrutura ICMP
0
A partir da
estrutura TCP
A partir da
2
2
estrutura TCP
Tamanho IP
Tamanho IP
Tamanho IP
menos tamanho menos tamanho menos tamanho
dos cabeçalhos dos cabeçalhos dos cabeçalhos
IP e UDP
IP e ICMP
IP e TCP
0
0
Quadro 4: Explicação de como cada atributo do cabeçalho dos pacotes é extraı́do.
Fonte: Adaptado de Viegas et al. (2014b).
Para a extração dos atributos do quadro 3, é necessário guardar algumas variáveis de
estado da comunicação entre hosts durante a janela de tempo de 2 segundos. Para esse fim, os
autores implementaram uma tabela de tamanho constante para armazenar os atributos.
A tabela tem 65536 (216 ) linhas e cada linha é acessada a partir da função hash FNV.
A chave da hash é um valor de 5 ou 7 bytes, formada a partir de dados da máquina cliente e da
caracterı́stica a ser extraı́da. Para os atributos com o infixo “ serv ”, no meio do nome, a chave
tem 7 bytes, composta dos 4 bytes do endereço IP do cliente, dos 2 bytes da porta do cliente
(iguais a 0 se o protocolo for ICMP no qual não há porta) e 1 byte que identifica o atributo a
ser extraı́do. Como esses atributos são definidos para o mesmo serviço (por isso o “ serv ”), a
porta do cliente, que identifica o serviço em questão, também é considerada.
Para os demais atributos,
que são definidos apenas de host para host,
independentemente do serviço requisitado, a chave da hash é composta por 5 bytes. Os dois
bytes da porta do cliente não são considerados nesse caso. A figura 13 mostra como a chave da
hash é montada e como uma determinada linha da tabela é acessada.
Do total de 23 atributos dependentes da comunicação, os atributos first packet e
first serv packet não precisam ser guardados na tabela, visto que podem ser extraı́dos a
partir dos contadores de pacotes (atributos com o prefixo count). Assim, cada comunicação
envolvendo dois hosts ocupa 21 linhas na tabela. Por exemplo, a comunicação entre cliente A
e servidor ocupa 21 linhas, a comunicação entre cliente B e servidor também ocupa 21 linhas e
44
Figura 13: Montagem da chave da hash que acessa as linhas da tabela de atributos dependentes
dos pacotes de uma mesma comunicação.
Fonte: Adaptado de Viegas et al. (2014b)
assim por diante. Cada linha armazena um atributo de determinada comunicação.
As linhas da tabela foram divididas em cinco células (de 0 a 4) com vida útil de 0,5
segundos. A soma das células totaliza 2,5 segundos, mas a cada extração uma das células é
desconsiderada, de forma que a janela de tempo para cada atributo é de 2 segundos. O processo
funciona da seguinte forma: se no tempo 0 s inicia-se uma extração, os atributos são atualizados
na célula 0, enquanto o conteúdo da célula 4 deve ser apagado. A célula 0 continua sendo
atualizada até o tempo de 0,5 s. A partir de 0,5 s, os atributos são atualizados na célula 4
(previamente apagada), enquanto o conteúdo da célula 3 deve ser apagado. E assim por diante,
de modo que as células são utilizadas em ordem decrescente.
A cada momento, para extrair-se uma caracterı́stica, devem ser somadas as células
desconsiderando-se a célula a ser apagada. A figura 14 mostra graficamente o funcionamento
temporal de cada célula e quais células devem ser somadas para se obter o valor do atributo.
Cada célula tem tamanho de 16 bits, de modo que uma linha possui 80 bits e a tabela
completa ocupa 5.242.880 bits.
O fluxograma do extrator é mostrado de forma resumida na figura 15. A primeira
operação é justamente criar a tabela de atributos dependentes da comunicação, com valor zero
em todas as células. Depois, configuram-se as células a ser atualizada e a ser apagada como 0 e
4, respectivamente, e o timestamp do extrator em zero.
45
Figura 14: Células das linhas da tabela a serem consideradas para se obter o valor dos atributos
dependentes da comunicação.
Fonte: Adaptado de Viegas et al. (2014b)
Na sequência, lê-se um pacote. Se o timestamp do pacote (lido do arquivo PCAP, no
qual armazena-se a diferença de tempo de chegada entre os pacotes a partir do tempo 0) for
maior que o timestamp da aplicação por 0,5 s (janela de tempo de cada célula) ou mais, três
operações são feitas antes do prosseguimento da extração. Primeiro, zeram-se os conteúdos de
todas as células a serem apagadas. Segundo, decrementam-se as células a ser atualizada e a ser
apagada. Terceiro, soma-se 0,5 s ao timestamp da aplicação e, então, o teste da diferença de
timestamps é repetido.
Quando nenhum zeramento é necessário, a extração continua. Testa-se, então, o
protocolo do pacote. Para cada um dos protocolos da aplicação, UDP, ICMP ou TCP, as
funções correspondentes de extração dos atributos do cabeçalho e dos atributos dependentes
da comunicação são chamadas. A seguir, se houver mais pacotes a serem extraı́dos, a aplicação
volta ao ponto de leitura de pacote. Caso contrário, a aplicação é encerrada.
A extração dos atributos que dependem da comunicação está mostrada
simplificadamente como função na figura 15. Nesta etapa, os 23 atributos são extraı́dos,
um após o outro. Cada extração compreende: montar a chave da hash, calcular o valor da hash,
46
Figura 15: Fluxograma simplificado do extrator de caracterı́sticas.
Fonte: Adaptado de Viegas et al. (2014b)
atualizar a célula da linha da tabela dada pela hash e calcular o valor do atributo a partir da
soma da células, excluindo-se a célula a ser apagada.
Quando o IP do servidor é o IP de origem do pacote, os atributos com sufixo
“ s2c” devem ser atualizados na tabela, enquanto que os atributos com sufixo “ c2s” não são
atualizados (embora sejam extraı́dos). Quando o IP do servidor é o IP de destino do pacote, a
lógica inverte-se. O quadro 5 mostra como cada atributo deve ser atualizado.
47
Tipo
Nome Genérico
Estado da conexão TCP
conn status
Contadores de pacotes
count x2x
Contadores de bytes
num bytes x2x
Contadores de flags
num flag x2x
Primeiro pacote
first packet
Atualização
Valor definido a partir de máquina
de estados dependente das flags
do TCP (POSTEL, 1981c). Para
protocolos ICMP e UDP tem valores
“icmp” e “udp”, respectivamente.
Incrementado de um em um a cada pacote.
Se a origem do pacote é o servidor,
incrementa-se os atributos do tipo s2c.
Se o destino do pacote é o servidor,
incrementa-se os atributos do tipo c2s.
Quando há o infixo serv (de serviço),
o incremento acontece apenas para
pacotes de mesmo serviço (mesmas portas).
Incrementado com o tamanho da carga útil.
Se a origem do pacote é o servidor,
incrementa-se os atributos do tipo s2c.
Se o destino do pacote é o servidor,
incrementa-se os atributos do tipo c2s.
Quando há o infixo serv (de serviço),
o incremento acontece apenas para
pacotes de mesmo serviço (mesmas portas).
Incrementado para pacotes TCP
quando a flag em questão está setada.
Se a origem do pacote é o servidor,
incrementa-se os atributos do tipo s2c.
Se o destino do pacote é o servidor,
incrementa-se os atributos do tipo c2s.
“1” se o pacote em questão é o
primeiro da comunicação entre cliente
e servidor; “0” caso contrário.
Esse tipo de atributo é extraı́do a
partir dos contadores de pacotes.
Quando há o infixo serv (de serviço),
considera-se os pacotes de mesmo serviço.
Quadro 5: Explicação de como cada atributo dependente da comunicação é atualizado.
Fonte: Adaptado de Viegas et al. (2014b).
O programa tem a funcionalidade de gerar um arquivo com os atributos extraı́dos dos
pacotes. O formato gerado é o ARFF, que armazena as instâncias com seus respectivos atributos
e classes (THE UNIVERSITY OF WAIKATO, 2014). Para o arquivo PCAP com a base de
pacotes, foi gerado um arquivo ARFF com as caracterı́sticas extraı́das e a classe (normal ou
ataque) dos 9.431.075 pacotes. Para saber se cada pacote era normal ou ataque, o extrator
verificou o endereço IP do cliente (para saber se este era o Nessus ou um dos workloads).
48
Dos total de vetores de caracterı́sticas, os autores formaram um conjunto de
treinamento com 7480 vetores (3740 vetores normais e 3740 vetores de ataque) e um conjunto
de teste também com 7480 vetores (3740 vetores normais e 3740 vetores de ataque).
3.2
AVALIAÇÃO EM SOFTWARE
Em posse do extrator fornecido pelos autores, este foi compilado e executado numa
placa-mãe DN2800MT com processador Atom, fabricada pela Intel. Os processadores da
linha Atom são de baixo consumo e voltados para aplicações em que a eficiência energética
é desejada. Os principais periféricos que compõem o ambiente, mostrado na figura 16, são
um processador N2800, uma memória RAM DDR3 de 4 GB e um disco rı́gido de 500 GB. O
sistema operacional utilizado foi o openSUSE 13.1.
Figura 16: Ambiente para avaliação dos algoritmos em software.
Fonte: Autoria Própria
Do arquivo com todos os pacotes, também fornecido, montou-se um novo arquivo
PCAP com 8.000.000 de pacotes através do programa Wireshark. O Wireshark é um analisador
de protocolos de rede de código aberto. Com esta ferramenta é possı́vel capturar o tráfego de
rede e analisá-lo em tempo real ou partir de um arquivo PCAP. Para o arquivo com 8.000.000
de pacotes, foram realizadas cem execuções da aplicação de extração de caracterı́sticas em
sequência, a fim de considerar a média de múltiplas execuções.
Para calcular a taxa de transferência e o consumo energético do extrator, foi necessário
obter o tempo de processamento e a potência consumida pela aplicação. Considera-se que o
consumo da aplicação é o incremento de consumo da placa-mãe durante o tempo de execução
49
da aplicação em relação ao consumo da placa-mãe no estado inativo (sem executar nenhuma
aplicação de usuário).
Para obter o tempo de processamento e o consumo referentes à aplicação, utilizouse a plataforma desenvolvida por Cemin (2015) e mostrada esquematicamente na figura 17.
Alimenta-se a placa-mãe com 15 VDC. Um resistor de 270 mΩ inserido entre a fonte e a placa
faz a função de sensor de corrente. Utiliza-se o DAQ USB-6008 da National Instruments,
operando a 5000 amostras/s com 12 bits de resolução, para amostrar o consumo da placa-mãe.
Figura 17: Plataforma usada para medição do tempo de processamento e do consumo energético
dos algoritmos em software.
Fonte: Adaptado de Cemin (2015)
A plataforma possui a habilidade de medir o consumo de uma aplicação especı́fica
sendo executada no processador, descontando outras tarefas que por acaso sejam escalonadas
pelo Sistema Operacional. Para isso, monitora-se um sinal de sincronismo enviado via porta
paralela ao DAQ, que fica em nı́vel alto enquanto a aplicação está sendo executada e nı́vel baixo
caso contrário. A geração desse sinal é possibilitada através do kernel do Linux instrumentado
para reconhecer o Thread Group ID (TGID) à qual pertence a aplicação.
Com as amostras válidas do DAQ (ou seja, as amostras feitas com o sinal de
sincronismo em nı́vel alto), o valor da tensão de alimentação da fonte e o valor da resistência,
pode-se calcular o consumo de potência da aplicação.
Através de registros de timestamps durante a execução, também é possı́vel calcular
isoladamente o tempo de processamento da aplicação especı́fica na placa-mãe, com uma
resolução de 1 µs.
50
Utilizou-se a plataforma descrita para avaliar a aplicação do extrator de caracterı́sticas.
O clock do processador foi travado na frequência máxima (1,86 GHz) e habilitaram-se apenas
um core e uma thread. Os tempos de processamento para a aplicação completa, que consiste na
leitura mais extração dos pacotes, e apenas para a leitura, foram obtidos isoladamente. A partir
do tempo de processamento da aplicação completa (tempol+e ), desconta-se o tempo de leitura
(tempol ) para obter o tempo de extração, visto que para leitura dos pacotes é necessário acessar
o disco rı́gido e esta operação não faz parte da extração. Assim, foi utilizada a equação (7) para
calcular a taxa de transferência do extrator, em pacotes por segundo.
Taxa de Trans f erência (pacotes/s) =
número de pacotes
tempol+e − tempol
(7)
Utilizou-se a equação (8) para calcular a energia consumida por cada extração,
em joules (J). A potência da placa para a aplicação completa e para a leitura (Pl+e e Pl ,
respectivamente) também foram obtidas separadamente. O termo Pinat corresponde à potência
da placa-mãe quando inativa, ou seja, sem executar aplicação de usuário.
Energia por extração (J) =
3.3
(Pl+e − Pinat ) · tempol+e − (Pl − Pinat ) · tempol
número de pacotes
(8)
IMPLEMENTAÇÃO EM HARDWARE
O extrator de caracterı́sticas foi implementado em hardware com a linguagem VHDL,
utilizando o ambiente de desenvolvimento Sigasi. A ferramenta facilita a codificação, pois
tem funcionalidades como auto-completar, navegação entre arquivos, correção de erros da
linguagem e muitas outras.
A figura 18 mostra o diagrama em blocos do extrator implementado. O circuito possui
como entradas um sinal de clock (std logic), um sinal de reset (std logic), um sinal de inı́cio de
extração (boolean) e o cabeçalho do pacote de rede (std logic vector de 432 bits). As portas
de saı́da são um sinal de fim de extração (boolean), um sinal de pronto para outra extração
(boolean) e os atributos extraı́dos (vetor com os 50 atributos, cada um unsigned de 32 bits).
O sinal do cabeçalho possui 432 bits pois este é o total de bits do maior cabeçalho
possı́vel na aplicação: 54 bytes, quando o protocolo é TCP. Para os protocolos ICMP ou UDP,
o cabeçalho do pacote possui 42 bytes e assim pode ser compreendido no sinal de 432 bits.
O vetor com os atributos extraı́dos é do tipo record, composto pelos 50 atributos. A
51
Figura 18: Diagrama em blocos do extrator de caracterı́sticas em hardware.
Fonte: Autoria Própria
partir do tipo record, cada atributo pode ser acessado através de seu nome. Todos os atributos
foram definidos com 32 bits, pois este é o tamanho dos maiores atributos (tcp seq e tcp ack).
O digrama mostra que o circuito do extrator é composto por vários módulos. Um
destes é o extrator de atributos do cabeçalho dos pacotes. A entrada do módulo é o próprio sinal
do cabeçalho e a saı́da é um vetor composto pelos 27 atributos dessa categoria. Os atributos
são calculados a partir do acesso aos diferentes campos do cabeçalho (offsets do sinal de 432
bits), conforme explicado no quadro 4 para o extrator em software. A extração dos atributos do
cabeçalho não depende dos demais módulos do circuito.
Para armazenar os atributos baseados na comunicação entre cliente e servidor,
projetou-se uma tabela em forma de memória RAM. O endereço desta memória é fornecido
pelo módulo de cálculo da hash. Este módulo tem como entradas o sinal de cabeçalho do
pacote e um sinal de identificação do atributo a ser extraı́do (natural, com variação de 0 a 49
correspondendo aos 50 atributos). A saı́da do módulo é o valor da hash (natural, com variação
de 0 a 65535).
52
Primeiramente, a chave da hash é montada a partir dos bytes do endereço IP e da
porta do cliente e de um número primo que representa o atributo dependente da comunicação
a ser extraı́do. Esse número primo é obtido consultando-se uma tabela a partir do número de
identificação do atributo. O número de identificação, uma das entradas do módulo, deve variar
de 27 a 49 nesse caso, visto que os atributos extraı́dos diretamente do cabeçalho de cada pacote
não são registrados na memória.
O fornecimento do número de identificação do atributo é função do módulo de
controle, que será explicado mais adiante. Por enquanto é suficiente saber que um número
é fornecido por vez. Assim, ao fim da extração de um atributo, incrementa-se o número de
identificação para extração do próximo atributo e assim por diante.
A partir do valor da hash, acessa-se a memória de atributos mostrada na figura 19.
De forma semelhante à implementação em software, há 65536 (216 ) linhas subdivididas em 5
células de 16 bits (unsigned). A memória tem como entradas o sinal de clock, um sinal de
endereço (natural, com variação de 0 a 65535), um sinal de habilitação de escrita (boolean) e
uma linha de entrada. A memória fornece uma linha de saı́da.
Figura 19: Memória RAM que armazena os atributos dependentes da comunicação.
Fonte: Autoria Própria
A cada ciclo de clock, a tabela fornece na saı́da a linha correspondente ao endereço
configurado. Ao habilitar-se a escrita, a linha da tabela dada pelo endereço é sobrescrita com a
linha de entrada e esta aparece na saı́da, em seguida. Cada linha de saı́da da tabela corresponde
a um único atributo de determinada comunicação.
A linha de saı́da da tabela é entrada para o módulo de atualização de linha, mostrado
na figura 20. Além da linha a ser atualizada, o módulo ainda possui como entradas o sinal de
clock, o sinal de reset, o sinal de cabeçalho do pacote, o número de identificação do atributo,
o ı́ndice da célula a ser atualizada e o ı́ndice da célula a ser apagada. O módulo fornece como
saı́das a linha após atualização e o atributo extraı́do.
53
Figura 20: Módulo de atualização das linhas da memória de atributos.
Fonte: Autoria Própria
Da linha da tabela, primeiramente um multiplexador seleciona a célula a ser atualizada.
Esta célula, juntamente com o cabeçalho do pacote e o número de identificação do atributo,
constituem a entrada do módulo de atualização de célula. Conforme o atributo em questão
e os campos do cabeçalho do pacote, atualiza-se a célula como explicado no quadro 5 da
implementação em software.
Na sequência, a célula atualizada é mesclada com as outras 4 células não atualizadas
para formar a linha de tabela atualizada. Internamente ao módulo de atualização da linha, a linha
atualizada ainda tem suas células somadas, desconsiderando a célula a apagar, para cálculo do
atributo. Externamente ao módulo de atualização da linha, a linha atualizada é encaminhada
para a memória de atributos, para sobrescrever a linha prévia.
No fim do módulo de atualização da linha calcula-se o valor do atributo. Para a maioria
dos atributos, o valor é simplesmente o resultado do somatório das células da linha atualizada.
Para os atributos first packet e first serv packet, que não são mantidos na tabela, os valores são
registrados quando o extrator trata os atributos contadores de pacotes. Assim, quando o número
de identificação é 48 ou 49, em vez do valor do somatório, o valor de atributo fornecido na saı́da
vem do registrador correspondente. A cada fim de cálculo de atributo, o valor é registrado no
shift-register atributos comunicação sreg, mostrado no diagrama do inı́cio da seção.
54
Ao fim de cada janela de tempo deve-se zerar as células a serem apagadas. Isto é feito
pelo módulo de apagamento de colunas. A cada 0,5 s, o extrator deve manter qualquer pacote
recebido em espera para proceder com a operação de apagamento. Assim, diferentemente da
implementação em software, que verificava o timestamp do pacote para inı́cio ou não de um
apagamento, em hardware, o inı́cio da operação de apagamento é determinı́stico. Cada célula a
ser apagada na tabela é zerada em dois ciclos de clock.
O módulo de apagamento, mostrado na figura 21, faz interface diretamente com a
memória e com o módulo de controle, que será explicado mais adiante. As entradas são o sinal
de clock, o sinal de reset, uma linha da tabela, o ı́ndice da célula a ser apagada e um sinal de
inı́cio de apagamento (boolean). As saı́das são o endereço da tabela no qual a linha com a
célula apagada será sobrescrita, a linha com a célula apagada, um sinal de habilitação de escrita
na memória (boolean) e um sinal de fim de apagamento (boolean). O funcionamento do módulo
é simples: cada linha da memória é recebida uma a uma, zera-se a célula a ser apagada de cada
linha e escreve-se a nova linha na memória a partir da habilitação de escrita.
Figura 21: Módulo de zeramento das células a serem apagadas da tabela de atributos.
Fonte: Autoria Própria
O processo de extração é controlado pelo módulo de controle, mostrado na figura 22.
As entradas são o sinal de clock, o sinal de reset, o sinal de inı́cio de extração e o sinal de fim de
apagamento. As saı́das são o ı́ndice da célula a ser atualizada, o ı́ndice da célula a ser apagada,
o sinal de identificação do atributo a ser extraı́do, o sinal de inı́cio de apagamento, um sinal de
registro de atributo (boolean), o sinal de fim de extração e o sinal de pronto para outra extração.
Uma das funções do controle é temporizar as janelas de tempo. A cada 0,5 s, o módulo
decrementa os ı́ndices das células a serem atualizada e apagada e sinaliza uma operação de
apagamento pendente. Outra função do módulo é controlar a máquina de estados do extrator,
mostrada na figura 23. São sete estados no total: inativo, calcula hash, fornece linha da tabela,
atualiza linha da tabela, registra atributo, fim de extração e apagamento de coluna.
O primeiro estado é o inativo. Quando a extração é iniciada, o extrator passar a operar
em modo normal, no qual a cada ciclo de clock a máquina de estados move-se entre os estados
55
Figura 22: Módulo de controle do extrator.
Fonte: Autoria Própria
Figura 23: Máquina de estados que controla o extrator de caracterı́sticas.
Fonte: Autoria Própria
de dois a cinco, cujos nomes descrevem exatamente as operações realizadas, já descritas. A
partir do quinto estado, “registra atributo”, há duas possibilidades. Se não foram extraı́dos todos
os atributos ainda, o número de identificação de atributo é incrementado e retorna-se ao estado
calcula hash. Caso contrário, a máquina vai para o estado de fim de extração. No estado de fim
de extração, se houver pendência de apagamento, a máquina irá para o estado de apagamento.
No fim de um apagamento a máquina retorna ao estado inicial.
Por simplicidade não foi mostrado na imagem, mas a condição “inicia extração” força
a máquina a sempre prosseguir para o estado calcula hash. No estado de fim de extração, porém,
a condição “apagamento pendente” tem prioridade sobre a condição “inicia extração”.
56
O módulo de controle sinaliza, ainda, que o extrator está pronto para outra extração
quando o estado da máquina é inativo ou fim de extração e não há apagamento pendente.
Ao fim da extração, os atributos do shift-register em conjunto com os atributos
extraı́dos diretamente de cada cabeçalho constituem os atributos de saı́da do circuito.
A extração de um pacote dura 93 ciclos de clock porque são necessários 1 ciclo para
inı́cio da operação mais 92 ciclos para cálculo do atributos dependentes da comunicação (23
atributos · 4 ciclos). A cada 0,5 s há uma operação de apagamento que dura 131.072 ciclos,
sempre realizada entre pacotes. Essa operação diminui a taxa de transferência do extrator e se
um pacote chegar durante o apagamento, este deve ser registrado. A mesma conclusão é válida
para o extrator em software.
Para validação da implementação do extrator em hardware, foi codificado um
testbench em VHDL que lê e extrai 1.000.000 de pacotes e compara os resultados com os
resultados obtidos pelo extrator em software. Os arquivos VHDL do extrator e do testbench
foram compilados e simulados no programa ModelSim. O ModelSim é uma ferramenta de
simulação lógica para verificação e depuração de circuitos digitais. A execução do teste com
sucesso indicou que os extratores em software e hardware são equivalentes.
3.4
AVALIAÇÃO EM HARDWARE
Para avaliação do extrator em hardware foi utilizado o kit de desenvolvimento com a
FPGA Cyclone IV GX da Altera (chip EP4CGX150N), mostrado na figura 24. A linha Cyclone
é desenvolvida para atender aplicações que necessitam de baixo consumo energético. Para
sı́ntese do circuito do extrator descrito em VHDL e posterior gravação na FPGA foi utilizado o
programa Quartus II, da Altera. A ferramenta possibilita o projeto de dispositivos programáveis,
permitindo a análise e a sı́ntese de circuitos a partir de linguagem de descrição de hardware.
O kit de desenvolvimento é instrumentado com conversores A/D que permitem a
medição do consumo da FPGA. Para este fim, utilizou-se a ferramenta Power Monitor da Altera
em um computador para ler, via USB, a potência consumida pelas oito trilhas que alimentam o
chip. Somando-se os valores de cada trilha obtém-se o consumo total da FPGA.
Utilizou-se a equação (9) para calcular a taxa de transferência do extrator em hardware,
em pacotes por segundo. O termo tempoapag refere-se ao tempo de apagamento das colunas da
tabela de atributos, enquanto o termo tempoext refere-se ao tempo de extração. A definição do
numerador da equação vem do fato de que há duas operações de apagamento no perı́odo de um
segundo.
57
Figura 24: Kit com FPGA Cyclone IV GX para avaliação dos algoritmos em hardware.
Fonte: Autoria Própria
Taxa de Trans f erência (pacotes/s) =
1 − 2 · tempoapag
tempoext
(9)
Para medição do consumo do extrator em funcionamento, foi projetado o circuito da
figura 25. O circuito possui como entradas um sinal de clock (std logic) e um sinal de reset
(std logic). A saı́da é um atributo. Apenas um atributo extraı́do é fornecido por vez, para o
Quartus II não mapear cada bit de saı́da em pinos de I/O. Considerando todos os atributos,
seriam necessários 1600 pinos, porém, a FPGA utilizada só possui 508 pinos de I/O.
Figura 25: Circuito para medição do consumo do extrator em hardware.
Fonte: Autoria Própria
A entrada de cabeçalho do extrator é fornecida por um circuito gerador de números
aleatórios. Esta opção foi utilizada porque a operação do extrator não depende de valores exatos
dos campos do cabeçalho. Há, ainda, um módulo de controle que simplesmente inicia uma nova
58
extração um ciclo de clock após o fim da extração anterior. O fim da extração também habilita
uma nova geração de números aleatórios.
Como o extrator ocupa mais de 99% da área, considerou-se que o consumo do circuito
de medição se deve ao extrator. Utilizou-se a equação (10) para calcular o consumo energético
por operação de extração, na qual o termo Pexec refere-se à potência da FPGA com o extrator
em funcionamento e o termo Pbase refere-se à potência base do chip. Esta última foi medida
para um simples buffer, gravado na FPGA, que recebe um bit de entrada e transfere-o para a
saı́da. Desconta-se a potência base (cujo valor medido foi de 165 mW) para saber o incremento
causado pelo extrator de caracterı́sticas. Considera-se, também, que o extrator trabalha na
taxa de transferência dada pela equação (9). Os resultados da avaliação do extrator serão
apresentados no capı́tulo 7.
Energia por extração (J) =
Pexec − Pbase
Taxa de Trans f erência
(10)
59
4
DESENVOLVIMENTO DA ÁRVORE DE DECISÃO
Neste capı́tulo serão apresentados os desenvolvimentos do classificador Árvore de
Decisão para detecção de probing, em software e hardware. Para cada implementação serão
apresentados, também, as plataformas e métodos utilizados para avaliação. A tarefa de seleção
de caracterı́sticas usadas pela Árvore de Decisão, explicada no inı́cio da seção 4.1, foi realizada
por Eduardo Kugler Viegas (VIEGAS et al., 2014a).
4.1
IMPLEMENTAÇÃO EM SOFTWARE
Em posse dos conjuntos de dados, também fornecidos pelos desenvolvedores do
extrator em software, foi possı́vel treinar o primeiro classificador para detecção dos ataques do
tipo probing: a Árvore de Decisão. Para modelagem do classificador, foi utilizado o algoritmo
J48 do programa Weka. O Weka é um ambiente de Aprendizagem de Máquina que possui
uma grande gama de classificadores. O J48 é uma implementação em Java do algoritmo C4.5
(comentado na subseção 2.2.2).
Antes da tarefa de aprendizagem, porém, foi executada uma seleção de caracterı́sticas
do tipo wrapper-based. Esta etapa é considerada pré-processamento e o objetivo é eliminar as
caracterı́sticas redundantes e/ou irrelevantes para a classificação. Para este fim, a seleção de
caracterı́sticas, que deve ser atrelada ao classificador em questão (neste caso, o J48), avalia
a acurácia de classificação para várias combinações de caracterı́sticas e seleciona o menor
conjunto de caracterı́sticas que fornece o melhor resultado.
No Weka, utilizou-se um algoritmo genético com 100 gerações e 100 populações para
busca dos atributos mais relevantes para classificação do conjunto de testes pela árvore. Do total
de 50 atributos, foram selecionados os 11 atributos mostrados no quadro 6.
Utilizando, então, as 11 caracterı́sticas selecionadas, o algoritmo J48 foi executado
com as configurações padrão sobre o conjunto de treinamento. A figura 26 mostra a Árvore
de Decisão resultante. A árvore possui 24 nós, que correspondem aos testes dos atributos e 28
60
Número
Atributo
1
ip DF
2
ip checksum
3
tcp sport
4
tcp dport
5
tcp frst
6
tcp fpush
7
tcp fack
8
count serv s2c
9
num ack c2s
10
num ack s2c
11
num syn c2s
Quadro 6: Atributos selecionados para detecção de probing pela Árvore de Decisão.
Fonte: Adaptado de Viegas et al. (2014a).
folhas, que correspondem às classificações das instâncias em normal ou ataque do tipo probing.
Figura 26: Árvore de Decisão para detecção de probing.
Fonte: Autoria Própria
O primeiro atributo testado é a flag “Don’t Fragment” do cabeçalho IP. Se o atributo
for 0, o algoritmo segue para o lado esquerdo da figura; se o atributo for 1, o algoritmo segue
para o lado direito. Se, por exemplo, um vetor tem ip DF igual a 0 e count serv s2c maior
que 6, este é classificado como normal. Para classificação de qualquer vetor basta percorrer a
árvore, testando os atributos em cada nó, até atingir uma folha com a respectiva classe.
O modelo da árvore foi implementado em software com a linguagem C++, utilizando
o ambiente de desenvolvimento NetBeans. Esta ferramenta é de código aberto e possibilita
61
o desenvolvimento de aplicações em Java, HTML, PHP, C/C++ e outras linguagens.
O
classificador recebe um vetor contendo todas as 50 caracterı́sticas e classifica-o a partir dos
testes ‘se-então’ realizados nas caracterı́sticas especı́ficas da árvore.
Para validação da implementação, as 7480 instâncias do conjunto de dados de teste
foram lidas do arquivo ARFF correspondente e classificadas pela aplicação. As classificações
da aplicação foram, então, comparadas com as classificações obtidas com o programa Weka.
Este teste foi realizado com o auxı́lio das bibliotecas da plataforma Google Test, passando as
classes retornadas pela aplicação como valores a serem verificados e as classes retornadas pelo
Weka como valores esperados. A execução do teste com sucesso indicou que o classificador
implementado é equivalente ao classificador do J48. Os resultados de acurácia de classificação
serão apresentados no capı́tulo 7.
4.2
AVALIAÇÃO EM SOFTWARE
Para avaliação do classificador Árvore de Decisão em software, foram utilizados o
mesmo ambiente de compilação e execução e a mesma plataforma de medição comentados na
seção 3.2. A Árvore de Decisão foi integrada ao extrator de caracterı́sticas, de modo que um
pacote de entrada é primeiramente lido, depois extraı́do e por fim, classificado pela aplicação.
Para o arquivo com 8.000.000 de pacotes, foram realizadas cem execuções da aplicação
em sequência, para considerar uma média. Utilizou-se a equação (11) para calcular a taxa de
transferência do classificador, em pacotes por segundo. O termo tempol+e+c refere-se ao tempo
de processamento da aplicação completa (leitura + extração + classificação), enquanto o termo
tempol+e refere-se ao tempo de processamento das operações de leitura e extração.
Taxa de Trans f erência (pacotes/s) =
número de pacotes
tempol+e+c − tempol+e
(11)
Utilizou-se a equação (12) para calcular a energia consumida por cada classificação,
em joules (J). O termo Pl+e+c corresponde à potência da placa-mãe durante a execução da
aplicação completa; o termo Pl+e corresponde à potência da placa-mãe durante a execução das
operações de leitura e extração; o termo Pinat corresponde à potência da placa-mãe quando
inativa.
Energia por classi f ic. (J) =
(Pl+e+c − Pinat ) · tempol+e+c − (Pl+e − Pinat ) · tempol+e
número de pacotes
(12)
62
4.3
IMPLEMENTAÇÃO EM HARDWARE
O modelo da Árvore de Decisão para detecção de probing da figura 26 foi
implementado em hardware a partir da transcrição direta do algoritmo em comparadores e
portas lógicas. Para isso, foram utilizados a linguagem VHDL e o ambiente Sigasi.
A figura 27 mostra aproximadamente 1/6 do circuito do classificador. A entrada do
circuito é o vetor com todas as caracterı́sticas em valores unsigned de 32 bits e a saı́da é a
classe: normal ou ataque. Vários comparadores verificam os intervalos de valores dos atributos
da árvore. Na sequência, as saı́das dos comparadores são combinadas numa soma de produtos
que é nı́vel alto quando o vetor é classificado como ataque e nı́vel baixo quando o vetor é
classificado como normal.
Figura 27: Implementação em hardware da Árvore de Decisão para detecção de probing
(aproximadamente 1/6 do circuito mostrado).
Fonte: Adaptado de França et al. (2015)
A arquitetura em VHDL do classificador foi descrita num processo, para que a
implementação em hardware também utilizasse as declarações do tipo ‘se-então’. O circuito,
porém, é inteiramente combinacional.
Para validação da implementação, foi codificado um testbench que lê e classifica as
7480 instâncias do conjunto de dados de teste e compara os resultados com os resultados obtidos
no Weka. Os arquivos VHDL do classificador e do testbench foram compilados e simulados no
programa ModelSim. A execução do teste com sucesso indicou que o classificador Árvore
de Decisão implementado em hardware é equivalente ao classificador Árvore de Decisão
implementado em software.
63
4.4
AVALIAÇÃO EM HARDWARE
Para avaliação do classificador Árvore de Decisão em hardware, foram utilizados os
mesmos kit com FPGA e ferramenta de medição de consumo comentados na seção 3.4.
Como será mostrado no capı́tulo 7, o circuito da árvore é pequeno e por isso o
classificador pode trabalhar com uma grande taxa de transferência. Em vez de verificada, essa
taxa foi, então, estimada. Para isso, foi projetado o circuito da figura 28. O circuito consiste
numa memória FIFO, para registrar um atributo por vez, e no módulo classificador.
Figura 28: Circuito para estimação da taxa de transferência dos classificadores.
Fonte: Autoria Própria
O circuito tem como entradas um sinal de clock (std logic), um sinal de reset
(std logic), um sinal de inı́cio de classificação (boolean), um atributo (valor unsigned de 32
bits) e um sinal de habilitação de registro do atributo (boolean). As portas de saı́da são um sinal
de fim de classificação (boolean) e a classe (normal ou ataque). O circuito tem, ainda, um sinal
genérico: o tipo do classificador, que pode ser escolhido antes da compilação.
Utilizou-se a equação (13) para calcular a taxa de transferência da Árvore de Decisão
(e dos demais classificadores em hardware a serem apresentados), em pacotes por segundo. O
termo tempoclass refere-se ao tempo de classificação. Para os classificadores combinacionais, o
tempo de classificação é o tempo de propagação entre a FIFO e a saı́da da classe, verificada com
a ferramenta TimeQuest Timing Analyzer, do Quartus II. Para os classificadores sequenciais,
o tempo de classificação é a divisão entre a quantidade de ciclos de clock necessários para
classificação pela frequência máxima (verificada no próprio Quartus II) de operação.
Taxa de Trans f erência (pacotes/s) =
1
tempoclass
(13)
64
Para avaliação do consumo do classificador foi desenvolvido o circuito mostrado na
figura 29. O circuito possui as seguintes caracterı́sticas:
• Número configurável de réplicas do classificador;
• Memória ROM com 2000 vetores de atributos (1000 vetores normais e 1000 vetores de
ataque, retirados do arquivo ARFF de teste) e respectivas classes esperadas;
• PLL para selecionar a frequência de operação;
• Memória FIFO para ler os vetores da ROM e aplicá-los nas entradas dos classificadores;
• Detector de erro de classificação, que sinaliza quando um vetor é incorretamente
classificado.
Figura 29: Circuito para medição do consumo dos classificadores em hardware.
Fonte: Adaptado de França et al. (2015)
O circuito de medição tem como entradas um sinal de clock (std logic), um sinal
de reset (std logic), um sinal de habilitação (boolean) do circuito de teste (composto pelas
memórias) e um sinal de habilitação dos classificadores (boolean). O sinal de reset e os dois
sinais de habilitação são selecionados, respectivamente, a partir de um botão e de duas chaves
do kit de desenvolvimento. A saı́da é o sinal de detecção de erro de classificação (boolean),
mostrado em um LED do kit.
O circuito possui, ainda, três sinais genéricos que devem ser escolhidos antes da
compilação: classificador (pois o circuito é usado para avaliação da árvore e dos demais
classificadores em hardware a serem apresentados nos capı́tulos 5 e 6), o número N de réplicas
65
do classificador e a frequência de operação (que seleciona o valor de saı́da do PLL, a partir de
um sinal interno de 50 MHz da FPGA).
Esse circuito é importante por dois motivos. Primeiro, é possı́vel observar se há
incremento linear no consumo conforme o número de réplicas e assim obter o consumo do
classificador a partir de regressão linear. Segundo, com o circuito de medição é possı́vel
aumentar a frequência de operação e monitorar a saı́da de erro de classificação. Como a classe
esperada da memória é comparada com a classe obtida em tempo real, um erro de classificação
significa que o classificador não consegue funcionar corretamente na frequência em questão.
A memória ROM tem como entradas o sinal de clock e o endereço (std logic vector
de 11 bits). A saı́da é um vetor de 1601 bits (std logic vector), composto pelos vetores de
teste (1600 bits) e a classe esperada (1 bit). O endereço de 11 bits implica em 2048 linhas de
memória, que são suficientes para armazenar os 2000 vetores de teste. Os vetores são lidos da
ROM continuamente.
A memória FIFO tem N linhas e é utilizada para evitar a simplificação do circuito, pelo
Quartus II, no momento da sı́ntese e assim manter as N réplicas do classificador.
Com o circuito em funcionamento, a cada ciclo de clock, um vetor da ROM é
armazenado na FIFO, que funciona como shift-register. Isso acontece até N vetores da ROM
serem armazenados na FIFO. A partir deste momento, os vetores na FIFO são deslocados um
a um de forma que o vetor N+1 da ROM é registrado no lugar do vetor 1 na FIFO. Esse
deslocamento dos vetores de teste acontece até os 2000 vetores da ROM serem classificados.
Na sequência o ciclo se repete a partir do vetor 1, de modo que a operação de classificação dos
2000 vetores acontece continuamente.
Quando o sinal de habilitação do circuito de teste está em nı́vel baixo, não há
incremento de endereço da ROM nem deslocamento na FIFO e assim as memórias permanecem
estáticas. Quando o sinal de habilitação dos classificadores está em nı́vel baixo, as entradas dos
classificadores recebem um vetor zerado em vez de receber o vetor de atributos da memória.
A partir desses sinais de habilitação é possı́vel medir o consumo dos classificadores em
funcionamento e em modo inativo.
O circuito de medição conta, ainda, com um módulo de detecção de erro de
classificação. Neste, as classes obtidas em tempo real são comparadas com as classes esperadas.
Se houver erro de classificação em qualquer uma das N réplicas do classificador, sinaliza-se um
erro de classificação no LED de saı́da. Neste caso, o LED permanece aceso até que o circuito
seja reiniciado, indicando que o classificador não consegue operar na frequência em questão.
66
A sequência de operações do circuito é controlada pelo módulo de controle. O módulo
coordena o inı́cio e o fim de cada classificação, de modo que a classificação de um novo vetor
só é iniciada após o fim da classificação do vetor anterior. O inı́cio de cada classificação, por
sua vez, está condicionado ao prévio carregamento do vetor da ROM para a FIFO. A figura 30
mostra a máquina de estados de controle. Uma vez no estado de erro detectado, o circuito de
medição só pode voltar ao modo de execução mediante o sinal de reset.
Figura 30: Máquina de estados que controla as operações do circuito de medição dos
classificadores.
Fonte: Autoria Própria
Após a finalização do circuito de medição, os seguintes procedimentos foram adotados
para cálculo do consumo do classificador: fixou-se um valor de frequência de operação e
compilou-se o circuito para várias réplicas da Árvore de Decisão; o consumo da FPGA foi
medido, então, com os classificadores habilitados. Percebeu-se que o consumo de potência
variou linearmente com o número de réplicas do classificador e assim essa foi obtida através de
regressão linear (coeficiente angular da regressão, que desconta o consumo base da FPGA). A
partir do valor de potência, Pclass , utilizou-se a equação (14) para calcular a energia consumida
por cada classificação, em joules (J).
Energia por classi f ic. (J) = Pclass · tempoclass
(14)
67
5
DESENVOLVIMENTO DO NAIVE BAYES
Neste capı́tulo serão apresentados os desenvolvimentos do classificador Naive Bayes
para detecção de probing, em software e hardware. A tarefa de seleção de caracterı́sticas usadas
pelo Naive Bayes, explicada no inı́cio da seção 5.1, foi realizada por Eduardo Kugler Viegas
(VIEGAS et al., 2014a).
5.1
IMPLEMENTAÇÃO EM SOFTWARE
Para modelagem do classificador Naive Bayes, foi utilizado o algoritmo Naive Bayes
do programa Weka. Primeiramente, porém, foram selecionadas as caracterı́sticas, no modo
wrapper-based, mais relevantes para o Naive Bayes através de um algoritmo genético com
100 gerações e 100 populações. Do total de 50 atributos, foram selecionados os 10 atributos
mostrados no quadro 7.
Número
Atributo
1
ip DF
2
udp sport
3
tcp sport
4
tcp ack
5
num bytes serv s2c
6
num fin c2s
7
num ack c2s
8
num syn s2c
9
num rst c2s
10
num rst s2c
Quadro 7: Atributos selecionados para detecção de probing pelo Naive Bayes.
Fonte: Adaptado de Viegas et al. (2014a).
Utilizando, então, as 10 caracterı́sticas selecionadas, o algoritmo Naive Bayes do
Weka foi executado sobre o conjunto de treinamento. Entre as configurações padrão, uma foi
alterada: utilizou-se a opção useSupervisedDiscretization, para converter atributos numéricos
68
contı́nuos em atributos discretos. Nesse caso, os atributos são discretizados a partir de algumas
divisões do intervalo de variação de seus valores. A discretização é necessária para o cálculo
das probabilidades, conforme mencionado na subseção 2.2.3. A figura 31 mostra o modelo
resultante do classificador.
Figura 31: Modelo Naive Bayes para detecção de probing.
Fonte: Autoria Própria
As informações de probabilidades estão implı́citas e precisam ser obtidas. A influência
69
de um atributo de valor v na probabilidade de um pacote ser normal é dada pela divisão entre
o número presente na intercessão da coluna “Class normal” com a linha com o valor de v e o
número presente na intercessão da coluna “Class normal” com a linha “[total]” do atributo. O
mesmo raciocı́nio pode ser aplicado para calcular a influência do atributo na probabilidade do
pacote ser ataque.
Como exemplo, pode-se observar o primeiro atributo: ip DF. Se um pacote possui
ip DF = 0, a parcela deste atributo na probabilidade do pacote ser normal é P(ip DF =
0|normal) = 2029/3742. Já a parcela desse atributo na probabilidade do pacote ser ataque
é P(ip DF = 0|ataque) = 18/3742. Seguindo a mesma lógica, tem-se que para ip DF = 1:
P(ip DF = 1|normal) = 1713/3742 e P(ip DF = 1|ataque) = 3724/3742. O ip DF é um
exemplo de atributo discreto, pois assume valor 0 ou 1.
Os atributos contı́nuos foram discretizados em intervalos pelo Weka. Este é o caso do
atributo num syn s2c, por exemplo, que foi divido em quatro intervalos: [−∞ até 1,5], [1,5 até
2,5], [2,5 até 92] e [92 até ∞]. Para cada pacote, deve ser verificado em qual intervalo recai o
valor desse atributo, pois cada intervalo tem sua própria influência nas probabilidades.
O denominador das divisões das probabilidades não é igual ao número de exemplos de
treinamento, pois o algoritmo de discretização cria exemplos “virtuais” para todos os valores
de atributos no intuito de evitar que algum atributo tenha um intervalo com zero exemplos
(o que forneceria um valor zero para a multiplicação das probabilidades). Por causa disso,
também, os numeradores das divisões não são necessariamente iguais aos números de exemplos
de treinamento de determinada classe para o valor de atributo considerado.
Da figura, também podem ser retiradas as probabilidades prévias de cada classe.
Observando-se o cabeçalho das tabelas, tem-se que P(normal) = 0, 5 e P(ataque) = 0, 5. A
probabilidade prévia de cada classe é 50% pois o conjunto de dados de treinamento tem um
número igual de exemplos de ataque e de exemplos normais: 3740. Como P(c) é igual para
as duas as classes, pode-se assumir que a equação (15) expressa a probabilidade de um pacote
ser normal enquanto que a equação (16) expressa a probabilidade de um pacote ser ataque. A
maior probabilidade indica a classe na qual o pacote será classificado.
P(normal|pacote) = P(ip DF|normal) · P(ud p sport|normal) · P(tcp sport|normal)·
P(tcp ack|normal) · P(num bytes serv s2c|normal) · P(num f in c2s|normal)·
P(num ack c2s|normal) · P(num syn s2c|normal) · P(num rst c2s|normal)·
P(num rst s2c|normal)
(15)
70
P(ataque|pacote) = P(ip DF|ataque) · P(ud p sport|ataque) · P(tcp sport|ataque)·
P(tcp ack|ataque) · P(num bytes serv s2c|ataque) · P(num f in c2s|ataque)·
(16)
P(num ack c2s|ataque) · P(num syn s2c|ataque) · P(num rst c2s|ataque)·
P(num rst s2c|ataque)
O modelo Naive Bayes foi implementado em software utilizando o ambiente NetBeans
e a linguagem C++. Foram declaradas tabelas para cada atributo, contendo as constantes de
probabilidades. Cada linha das tabelas é uma estrutura que contém 3 valores: limite superior,
probabilidade para pacote normal e probabilidade para pacote ataque.
O limite superior
foi declarado como inteiro de 32 bits e armazena o valor superior do limite (arredondado
para baixo) de cada intervalo de valores dos atributos, advindos do modelo do Weka. As
probabilidades para pacote normal e para pacote ataque foram declaradas como floats de 32
bits e armazenam os valores de probabilidades do modelo do Weka, conforme explicado alguns
parágrafos acima.
A tabela 1 apresenta o exemplo de como foi construı́da a tabela de constantes para o
atributo udp sport. O campo limite superior indica quais os valores de probabilidades devem
ser utilizadas no classificador. Se, por exemplo, um pacote tem udp sport = 50000, devem ser
selecionadas Pnormal = (72.0/3746.0) e Pataque = (2.0/3746.0) pois 50000 é maior que 48793
e menor que 51350 (ou seja, encaixa-se na condição de limite superior de valor 51350). Foram
criadas funções que retornam os valores de probabilidades normal e de ataque, considerando
em qual intervalo de limite superior o valor do atributo se encaixa. As tabelas para os demais
atributos foram construı́das da mesma forma.
Tabela 1: Probabilidades para os intervalos de valores do atributo udp sport na implementação em
software do Naive Bayes.
Limite superior: inteiro de 32 bits
26
48579
48793
51350
51930
4294967295
Pnormal : float de 32 bits
(2829.0 / 3746.0)
(700.0 / 3746.0)
(1.0 / 3746.0)
(72.0 / 3746.0)
(1.0 / 3746.0)
(143.0 / 3746.0)
Pataque : float de 32 bits
(3114.0 / 3746.0)
(5.0 / 3746.0)
(26.0 / 3746.0)
(2.0 / 3746.0)
(592.0 / 3746.0)
(7.0 / 3746.0)
Fonte: Autoria própria.
Para a classificação, o Naive Bayes obtém as probabilidades de um pacote ser normal
e de ser ataque a partir do vetor com todos os 50 atributos e assinala a classe de maior
71
probabilidade. A probabilidade do pacote ser normal é dada pelo produto das probabilidades
de cada atributo inferindo a classe normal. A probabilidade do pacote ser ataque é dada pelo
produto das probabilidades de cada atributo inferindo a classe ataque. A figura 32 mostra o
fluxograma do classificador, apresentando em detalhes os cálculos das probabilidades.
Figura 32: Fluxograma do classificador Naive Bayes para detecção de probing em software.
Fonte: Autoria Própria
Nas caixas que mostram os detalhes dos cálculos das probabilidades, estão presentes
as funções “pNormal” e “pAtaque”. Estas são as funções que verificam em qual limite superior
o valor do atributo se encaixa, para assim retornar os valores individuais das probabilidades.
Ambas as funções recebem dois parâmetros: a tabela e o valor do atributo correspondente.
Para validação da implementação, as 7480 instâncias do conjunto de dados de teste
foram lidas do arquivo ARFF correspondente e classificadas pela aplicação. As classificações
da aplicação foram, então, comparadas com as classificações obtidas com o programa Weka.
Este teste foi realizado com o auxı́lio das bibliotecas da plataforma Google Test, passando as
classes retornadas pela aplicação como valores a serem verificados e as classes retornadas pelo
Weka como valores esperados. A execução do teste com sucesso indicou que o classificador
implementado é equivalente ao classificador Naive Bayes do Weka.
72
5.2
AVALIAÇÃO EM SOFTWARE
A avaliação do classificador Naive Bayes em software foi realizada de forma
semelhante à avaliação da Árvore de Decisão em software, explicada na seção 4.2. A única
alteração foi a troca do classificador.
5.3
IMPLEMENTAÇÃO EM HARDWARE
Foram desenvolvidas duas versões do classificador Naive Bayes para detecção de
probing em hardware: uma versão combinacional e uma versão sequencial. A implementação
combinacional é praticamente uma tradução direta do classificador em software. Com isso, as
operações de consultas às tabelas de probabilidades e multiplicações ocorrem em paralelo para
cada atributo, fato que reduz o tempo de classificação. Em contrapartida, a implementação
sequencial faz uma operação por vez, utilizando menos recursos de hardware. Foram utilizados
a linguagem VHDL e o ambiente de desenvolvimento Sigasi para as implementações.
5.3.1
VERSÃO COMBINACIONAL
Na implementação combinacional, transcreveu-se diretamente o algoritmo da figura 32
em consultas à tabelas, multiplicadores e um comparador.
A figura 33 mostra parte do circuito do classificador. A entrada do circuito é o vetor
com todas as caracterı́sticas em valores unsigned de 32 bits e a saı́da é a classe: normal ou
ataque. Para cada valor de atributo do Naive Bayes, são realizadas consultas às tabelas de
probabilidade normal e de probabilidade de ataque. Há dois multiplicadores, cada um de dez
entradas: um multiplicador para o produto das probabilidades normais e um multiplicador para
o produto das probabilidades de ataque. Por fim, o comparador verifica qual o maior produto e
assinala a classe de maior probabilidade.
De forma semelhante à versão em C++, na versão em VHDL também há uma tabela
para cada atributo. Cada linha da tabela também é composta por uma estrutura com três valores:
limite superior, probabilidade normal e probabilidade de ataque. O limite superior é unsigned
de 32 bits e as probabilidades individuais são floats de 32 bits (no padrão IEEE 754: 1 bit para
sinal, 8 bits para expoente e 23 bits para mantissa).
As considerações feitas com relação às tabelas da implementação em software também
são válidas para a implementação combinacional em hardware. As tabelas foram declaradas
como constantes no código VHDL. O circuito é inteiramente combinacional.
73
Figura 33: Implementação combinacional do Naive Bayes em hardware para detecção de probing.
Fonte: Adaptado de França et al. (2015)
Para validação da implementação, foi codificado um testbench que lê e classifica as
7480 instâncias do conjunto de dados de teste e compara os resultados com os resultados obtidos
no Weka. Os arquivos VHDL do classificador e do testbench foram compilados e simulados
no programa ModelSim. A execução do teste com sucesso indicou que o classificador Naive
Bayes combinacional implementado em hardware é equivalente ao classificador Naive Bayes
implementado em software.
5.3.2
VERSÃO SEQUENCIAL
A implementação sequencial do classificador Naive Bayes consulta as tabelas de
probabilidades de forma serial. Assim, as probabilidades normal e de ataque de cada atributo
são multiplicadas por vez. O circuito, mostrado na figura 34, utiliza apenas dois multiplicadores
de duas entradas, mas precisa de 73 ciclos de clock para classificar um pacote. Uma memória
ROM armazena os valores de limite superior, probabilidade normal e probabilidade de ataque
para cada intervalo dos atributos.
O circuito tem como entradas um sinal de clock (std logic), um sinal de reset
(std logic), um sinal de inı́cio de classificação (boolean) e os atributos (valores unsigned de
32 bits). As portas de saı́da são um sinal de fim de classificação (boolean) e a classe (normal
ou ataque).
74
Figura 34: Implementação sequencial do Naive Bayes em hardware para detecção de probing.
Fonte: Adaptado de França et al. (2015)
A memória ROM tem como entradas o sinal de clock e o endereço (std logic vector de
7 bits). E tem como saı́da uma linha (std logic vector de 96 bits) composta pela concatenação
do limite superior (std logic vector de 32 bits) com as probabilidades normal e de ataque (ambas
std logic vector de 32 bits, a partir da conversão de valores float de 32 bits). O endereço de 7
bits implica em 128 linhas, que são suficientes para armazenar os valores para cada intervalo de
atributo, que totalizam 70 linhas.
A classificação começa quando os atributos selecionados para o Naive Bayes são
registrados no registrador “atributos reg”. Para cada atributo, são lidas as linhas (uma por
ciclo de clock) correspondentes da tabela. A consulta à tabela consiste em comparar o valor
do atributo com o limite superior. Enquanto o valor do atributo está dentro do limite superior,
os registradores das probabilidades normal e de ataque são sobrescritos com os valores advindos
da memória. Esses registradores armazenam valores float de 32 bits, então as probabilidades
individuais lidas da memória precisam ser convertidas em float novamente.
O último limite superior para cada atributo é um vetor com todos os bits iguais a ‘1’,
que representa o valor ∞ do modelo do Weka. Este vetor é utilizado para sinalizar, através do
75
buffer do circuito, o fim de um atributo na tabela. Neste momento, os valores de probabilidades
do atributo são multiplicados pelos valores de probabilidades acumuladas. Os registradores das
probabilidades acumuladas também armazenam valores floats de 32 bits. Como os valores de
probabilidade são menores do que 1, foi mantida a mesma precisão em bits para registrar os
resultados das multiplicações.
Ao término da multiplicação das probabilidades de todos os dez atributos, um
comparador classifica o pacote em normal ou ataque, a partir da verificação do maior valor
de probabilidade acumulada.
Todo esse fluxo da classificação é controlado por uma máquina de três estados. Antes
do inı́cio de classificação, o circuito fica no estado “inativo”. Após o pulso de inı́cio, o
circuito vai para o estado “calculando”, no qual permanece até a multiplicação de todas as
probabilidades. Após o fim de todos os atributos, o circuito vai para o estado “fim”, no qual
deixa o sinal de fim de classificação em nı́vel alto.
A classificação dura 73 ciclos de clock porque são necessários 70 ciclos para percorrer
as 70 linhas de valores da memória, mais 1 ciclo para inı́cio de classificação, mais 2 ciclos
iniciais para registro dos atributos e registro dos primeiros valores de probabilidades individuais.
No inı́cio de classificação todos os registradores de probabilidades são carregados com o valor
um, fator neutro na multiplicação.
Para validação da implementação, foi codificado um testbench que lê e classifica as
7480 instâncias do conjunto de dados de teste e compara os resultados com os resultados
obtidos no Weka. Os arquivos VHDL do classificador e do testbench foram compilados e
simulados no programa ModelSim. A execução do teste com sucesso indicou que o classificador
Naive Bayes sequencial implementado em hardware é equivalente ao classificador Naive Bayes
implementado em software.
5.4
AVALIAÇÃO EM HARDWARE
A avaliação dos classificadores Naive Bayes em hardware (versões combinacional e
sequencial) foi realizada de forma semelhante à avaliação da Árvore de Decisão em hardware,
explicada na seção 4.4. A única alteração foi a troca do classificador.
76
6
DESENVOLVIMENTO DO KNN
Neste capı́tulo serão apresentados os desenvolvimentos do classificador kNN para
detecção de probing, em software e hardware. As tarefas de clusterização da base de dados
de treinamento, de seleção do melhor parâmetro k e de seleção de caracterı́sticas usadas pelo
kNN, explicadas no inı́cio da seção 6.1, foram realizadas por Eduardo Kugler Viegas (VIEGAS
et al., 2014a).
6.1
IMPLEMENTAÇÃO EM SOFTWARE
Para avaliação do classificador kNN, foi utilizado o algoritmo IBk (o IB vem de
Instance-Based) do programa Weka. Como os atributos dos pacotes de rede têm diferentes
variações de valores, é importante normalizá-los, conforme mencionado na subseção 2.2.4. O
Weka utiliza a equação (17) para normalizar os atributos, em que max e min são os valores
máximo e mı́nimo do atributo, a ser normalizado, na base de treinamento. Para normalizar os
atributos entre -1 e +1, os valores de escala e translação devem ser 2 e -1, respectivamente.
Atributo − min
Atributonorm = escala ·
+ translação
max − min
(17)
A base de dados de treinamento possui mais de 7000 vetores. Se para a classificação
do kNN fossem calculadas as distâncias para todos esses vetores, o tempo necessário seria
demasiadamente grande. Para reduzir a quantidade de cálculos de distâncias, foi utilizado o
algoritmo k-Means do Weka para clusterização da base de treinamento. Este processo substitui
grandes grupos de vetores semelhantes (próximos uns dos outros) por um único vetor (cluster):
o centroide dos vetores.
Com o k-Means, foram selecionados 100, 200, 300, 400 e 500 clusters, já normalizados
entre -1 e +1, para cada classe. Um algoritmo genético de busca, do Weka, forneceu o melhor
resultado de classificação para o caso de 500 clusters de cada classe. Assim, gerou-se um novo
arquivo ARFF contendo 500 centroides normais e 500 centroides de ataque. Na sequência,
77
aplicou-se um algoritmo genético para busca do melhor parâmetro k para o classificador, entre
1 e 10. O melhor resultado foi obtido para k = 3.
Após definir o conjunto de clusters e o parâmetro k, foram selecionadas no modo
wrapper-based as caracterı́sticas mais relevantes para o kNN através de um algoritmo genético
com 100 gerações e 100 populações. Foram selecionados os 19 atributos mostrados no quadro 8.
Os valores máximo e mı́nimo de cada atributo na base de treinamento também são mostrados.
Número
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Atributo
ip len
ip id
ip MF
ip proto
udp dport
tcp sport
tcp ack
tcp frst
tcp fpush
tcp fack
fr length
conn status
count fr s2c
num bytes s2c
num bytes serv c2s
num bytes serv s2c
num syn fin s2c
num ack c2s
num syn s2c
Mı́nimo
Máximo
29
5844
0
65509
0
1
1
17
0
60960
0
65416
0
4294504880
0
2
0
2
0
2
0
5804
0
15
0
4205
0
114688
0
32664
0
114688
0
17173
0
2722
0
7949
Quadro 8: Atributos selecionados para detecção de probing pelo kNN e seus valores máximos e
mı́nimos na base de dados de treinamento.
Fonte: Adaptado de Viegas et al. (2014a).
O kNN foi implementado em software com o C++ utilizando o ambiente NetBeans.
Primeiramente foram criadas duas estruturas de dados. A primeira contém 19 variáveis do tipo
float de 32 bits, para armazenar os atributos normalizados, e uma classe (normal ou ataque). A
segunda estrutura de dados contém um valor de distância do tipo float de 32 bits e uma classe,
para armazenar o par distância/classe dos vizinhos. Foi criada, também, uma tabela constante
que armazena os 1000 vetores (centroides) de treinamento. Cada vetor é do formato da primeira
estrutura de dados, contendo os 19 atributos normalizados e a classe correspondente.
Após a definição das estruturas de dados e da tabela com os vetores de treinamento,
foram criadas duas funções auxiliares usadas durante a classificação. A primeira função
78
normaliza um vetor de entrada e a segunda função calcula o quadrado da distância Euclidiana
entre dois vetores. A raiz quadrada da distância Euclidiana foi descartada, pois é uma operação
custosa e não influencia na procura dos vizinhos mais próximos.
A figura 35 mostra o fluxograma do kNN para classificação de novos vetores.
Primeiramente os atributos do kNN do vetor de entrada são normalizados entre -1 e +1.
Na sequência são calculadas as distâncias desse vetor normalizado para cada um dos 1000
vetores de treinamento. Durante os cálculos das distâncias, os três vizinhos mais próximos são
mantidos. Ao final, a classe mais comum entre os vizinhos é selecionada.
Figura 35: Fluxograma do classificador kNN para detecção de probing em software.
Fonte: Autoria Própria
Para validação da implementação, as 7480 instâncias de teste foram lidas do
arquivo ARFF correspondente e classificadas pela aplicação. As classificações foram, então,
comparadas com as classificações obtidas com o Weka. Esse teste foi realizado com o auxı́lio
das bibliotecas do Google Test, passando as classes retornadas pela aplicação como valores
a serem verificados e as classes do Weka como valores esperados. A execução do teste com
sucesso indicou que o kNN implementado é equivalente ao classificador IBk do Weka.
79
6.2
AVALIAÇÃO EM SOFTWARE
A avaliação do classificador kNN em software foi realizada de forma semelhante à
avaliação da Árvore de Decisão em software, explicada na seção 4.2. A única alteração foi a
troca do classificador.
6.3
IMPLEMENTAÇÃO EM HARDWARE
O kNN foi implementado em hardware de forma sequencial e é composto por vários
módulos. Foram utilizados o ambiente de desenvolvimento Sigasi e a linguagem VHDL.
A figura 36 mostra o circuito do classificador em diagrama de blocos. São necessários
24.096 ciclos de clock para classificar um pacote. Uma memória ROM armazena os 1000
vetores de treinamento. As entradas são um sinal de clock (std logic), um sinal de reset
(std logic), um sinal de inı́cio de classificação (boolean) e os atributos (valores unsigned de
32 bits). As saı́das são um sinal de fim de classificação (boolean) e a classe (normal ou ataque).
Figura 36: Implementação do kNN em hardware para detecção de probing.
Fonte: Adaptado de França et al. (2015)
O primeiro módulo do classificador é o Normalizador, mostrado na figura 37, que tem
como entradas o sinal de clock, o sinal de reset, um sinal de inı́cio de normalização (boolean)
e os atributos. As saı́das são um sinal de fim de normalização (boolean) e um vetor com os 19
atributos do kNN normalizados entre -1 e +1 (floats de 32 bits).
A normalização começa quando o pulso de inı́cio é passado para nı́vel alto. Neste
80
Figura 37: Circuito do Normalizador do kNN.
Fonte: Autoria Própria
momento os atributos do kNN são registrados no shift register “atributos sreg”. Durante a
normalização, os atributos são deslocados no shift register, de modo que apenas um atributo
é normalizado por vez.
A operação de normalização consiste em multiplicar o atributo
pelo coeficiente angular correspondente na tabela de coeficientes e somar o resultado com o
coeficiente linear. Os coeficientes para cada atributo foram calculados a partir da equação (17),
modificada para o formato de reta.
A tabela de coeficientes foi implementada como constante e armazena os coeficientes
de normalização (floats de 32 bits) para cada atributo, também na forma de shift register.
Os coeficientes são deslocados no shift register, para a normalização do atributo em questão.
Assim, são necessários apenas um multiplicador e um somador. Foi utilizado um multiplicador
que fornece o resultado após 5 ciclos de clock, para aumentar a frequência máxima de operação
do módulo.
Após a operação de normalização, cada atributo é registrado e deslocado no
shift register “atributos normalizados sreg”. O vetor de saı́da é composto por todos os atributos
normalizados.
A normalização é controlada por uma máquina de três estados. Antes do inı́cio da
normalização, o circuito fica no estado “inativo”. Após o pulso de inı́cio, o circuito vai para
o estado “normalizando”, no qual permanece até a normalização de todos os 19 atributos. Em
seguida o circuito vai para o estado “fim”, no qual deixa o sinal de fim de normalização em nı́vel
alto. A operação completa dura 96 ciclos de clock: 95 ciclos para normalizar os 19 atributos,
mais 1 ciclo do pulso de inı́cio de normalização.
A memória ROM do classificador tem como entradas o sinal de clock e o endereço
81
(std logic vector de 10 bits). A saı́da é um vetor (std logic vector de 1601 bits) composto
da instância de treinamento com todos os atributos, mais um bit que corresponde à classe da
instância. Os vetores de treinamento, que possuem atributos normalizados entre -1 e +1, são
convertidos em std logic vector para serem armazenados. O endereço de 10 bits implica em
1024 linhas de memória, que são suficientes para armazenar os 1000 vetores de treinamento.
Na sequência implementou-se o módulo de cálculo de distância, mostrado na figura 38,
que tem como entradas o sinal de clock, o sinal de reset, um sinal de inı́cio de cálculo (boolean)
e os dois vetores (um de treinamento e um de teste; cada um com 19 floats de 32 bits,
correspondendo aos atributos normalizados do kNN) dos quais se quer calcular a distância
(quadrado da distância Euclidiana, conforme mencionado na seção 6.1). As saı́das são um
sinal de fim de cálculo (boolean) e o resultado da distância (float de 32 bits).
Figura 38: Circuito do Calculador de Distância do kNN.
Fonte: Autoria Própria
O cálculo de distância começa quando o pulso de inı́cio é passado para nı́vel alto. Neste
momento o vetor de treinamento (que vem da memória ROM) e o vetor de teste são registrados
nos shift registers “vetor treinamento sreg” e “vetor teste sreg”, respectivamente. A cada pulso
de clock, os atributos de ambos os vetores são deslocados nos shift registers.
A operação de cálculo de distância consiste em subtrair os atributos correspondentes
dos vetores, elevar o resultado ao quadrado e somar este quadrado com o valor de distância
acumulada, até todos os atributos serem considerados. Como cada atributo é considerado por
vez, são necessários apenas um subtrator, um multiplicador (usado para a operação de elevar
ao quadrado) e um somador. Todos os resultados são computados como floats de 32 bits. Há,
ainda, um registrador para a saı́da do subtrator e um registrador para a saı́da do multiplicador,
não mostrados na figura.
O fluxo de cálculo da distância é controlado por uma máquina de três estados. Antes
do inı́cio do cálculo, o circuito fica no estado “inativo”. Após o pulso de inı́cio, o circuito vai
82
para o estado “calculando”, no qual permanece até todos os atributos serem considerados no
cálculo. Em seguida o circuito vai para o estado “fim”, no qual deixa o sinal de fim do cálculo
de distância em nı́vel alto.
O cálculo de distância dura 22 ciclos de clock: 19 ciclos para calcular a distância
individual de cada um dos 19 atributos, mais 1 ciclo do pulso de inı́cio do cálculo, mas 2 ciclos
de registro dos valores iniciais de diferença e de multiplicação.
Em seguida implementou-se o módulo ordenador, que mantém os três pares
distância/classe dos vizinhos mais próximos e classifica o vetor de teste. O módulo tem como
entradas o sinal de clock, o sinal de reset, um sinal de clear (boolean), um sinal de habilitação
(boolean) e um par distância/classe (float de 32 bits/normal ou ataque). A saı́da é a classe do
vetor.
Quando habilitado, o ordenador ordena três pares distância/classe. A ordenação
mantém sempre os pares com as menores distâncias durante o processo de classificação do
kNN. A cada pulso de clock, o circuito verifica se o par de entrada tem distância menor do
que as distâncias dos pares já registrados. Em caso afirmativo, o novo par é armazenado no
ordenador. Caso contrário, o novo par é descartado.
O sinal de clear tem por objetivo reiniciar o ordenador, armazenando três pares com
o valor máximo permitido para o float de 32 bits e a classe ataque. A cada classificação, o
ordenador deve ser reiniciado, antes de serem procurados os vizinhos mais próximos.
Considerando os três pares armazenados, o ordenador seleciona a classe do vetor de
teste: ataque, caso haja dois ou três pares com o valor de classe ataque, ou normal, caso
contrário.
Por fim, implementou-se o módulo completo do kNN. O classificador instancia cada
um dos módulos descritos anteriormente, isto é, normalizador, memória ROM, calculador de
distância e ordenador. O módulo também é responsável por gerar os pulsos de inı́cio dos
módulos internos e os endereços de acesso à memória ROM com os vetores de treinamento.
O pulso de inı́cio de classificação é também o pulso de inı́cio de normalização. A
partir do pulso de fim de normalização, o kNN gera um pulso que ao mesmo tempo inicia o
primeiro cálculo de distância e reinicia o ordenador. A partir do fim do cálculo de distância,
o kNN gera dois pulsos: um pulso que ao mesmo tempo incrementa o endereço da ROM e
habilita o ordenador e outro pulso, atrasado em dois ciclos de clock, para iniciar o próximo
cálculo de distância. Esse atraso de dois ciclos de clock permite que o endereço da ROM seja
incrementado em um ciclo e um novo vetor de treinamento esteja disponı́vel no outro ciclo.
83
A classificação de um vetor dura 24.096 ciclos de clock porque são necessários 96
ciclos para a normalização, mais 1000·(22+2) ciclos para as demais operações. O cálculo
de distância, que dura 22 ciclos, é multiplicado por 1.000, pois existem 1000 vetores de
treinamento. O fator 2 que se soma aos ciclos do cálculo de distância é devido aos dois ciclos
de atraso entre um cálculo e outro, conforme explicado no parágrafo anterior.
Para validação da implementação, foi codificado um testbench que lê e classifica as
7480 instâncias do conjunto de dados de teste e compara os resultados com os resultados obtidos
no Weka. Os arquivos VHDL do classificador e do testbench foram compilados e simulados
no programa ModelSim. A execução do teste com sucesso indicou que o classificador kNN
implementado em hardware é equivalente ao classificador kNN implementado em software.
6.4
AVALIAÇÃO EM HARDWARE
A avaliação do classificador kNN hardware foi realizada de forma semelhante à
avaliação da Árvore de Decisão em hardware, explicada na seção 4.4. A única alteração foi
a troca do classificador.
84
7
RESULTADOS
Neste capı́tulo serão apresentados os resultados da dissertação. Na seção 7.1 serão
apresentados os resultados obtidos para o extrator de caracterı́sticas existente em software e para
a implementação correspondente desenvolvida em hardware. Na seção 7.2 serão apresentados
os resultados obtidos para os diferentes classificadores. Por fim, na seção 7.3 serão apresentadas
as publicações resultantes desta dissertação.
7.1
EXTRATOR DE CARACTERÍSTICAS
Nesta seção serão apresentados os resultados obtidos para as duas versões do extrator
de caracterı́sticas, com relação à área de circuito (para o extrator em hardware), taxa de
transferência e consumo de energia.
7.1.1
ÁREA DO CIRCUITO
A tabela 2 apresenta a área usada pelo extrator de caracterı́sticas em hardware, quanto
à células lógicas e bits de memória. Cada linha mostra os recursos utilizados pelos módulos
que compõem o circuito. O extrator completo ocupa 2.683 células lógicas e 5.242.880 bits de
memória. A totalidade dos bits de memória é usada pela tabela de atributos.
Tabela 2: Área utilizada pelo extrator de caracterı́sticas implementado em hardware.
Módulo
Células Lógicas Bits de Memória
apagamento coluna
33
0
controle
122
0
tabela atributos
600
5.242.880
hash
728
0
extrator atributos cabeçalho
60
0
atualiza linha
523
0
restante
617
0
extrator de caracterı́sticas
2.683
5.242.880
Fonte: Autoria própria.
85
7.1.2
TAXA DE TRANSFERÊNCIA
A tabela 3 apresenta a taxa de transferência das duas versões do extrator de
caracterı́sticas. O extrator em hardware funcionou corretamente para uma frequência de
operação de 50 MHz, o que resultou numa taxa de transferência de 534.815 pacotes/s. A taxa
de transferência do extrator em software é 295.615 pacotes/s, o que corresponde a 55% da taxa
em hardware.
Tabela 3: Taxa de transferência dos extratores em software e hardware (em 50 MHz).
Implementação
Pacotes/s
extrator em software 295.615
extrator em hardware 534.815
Fonte: Autoria própria.
Ambos os extratores atendem à taxa de transferência máxima teórica do link de Fast
Ethernet de 150.000 pacotes/s (CISCO, 2009).
7.1.3
CONSUMO DE ENERGIA
A tabela 4 apresenta o consumo de energia dos extratores. O extrator de caracterı́sticas
em software gasta 5,03 µJ para extrair um pacote, enquanto a implementação em hardware
gasta 1,15 µJ (em 50 MHz). O extrator de caracterı́sticas em hardware, então, consome 23%
da energia consumida pela implementação em software na operação de extração.
Tabela 4: Energia consumida na operação de extração em software e hardware (em 50 MHz).
Implementação
extrator em software
extrator em hardware
Energia por Extração (µJ)
5,03
1,15
Fonte: Autoria própria.
Adicionalmente, calculou-se também a energia consumida por extração em hardware
para as frequências de operação de 10, 20, 30 e 40 MHz. A figura 39, na qual o infixo “hw”
significa hardware, mostra que esses valores variam pouco em relação ao valor obtido para 50
MHz (no máximo 15 nJ). Conclui-se, então, que o consumo energético do extrator em hardware
depende minoritariamente da frequência. O consumo de potência e o tempo para extração mais
apagamento são, respectivamente, diretamente e inversamente proporcionais à frequência de
operação, e por isso o valor de energia se mantém quase constante.
86
Figura 39: Energia gasta para extrair um pacote em hardware para diferentes frequências de
operação.
Fonte: Autoria Própria
7.2
CLASSIFICADORES
Nesta seção serão apresentados os resultados obtidos para os classificadores, com
relação à acurácia de classificação, área de circuito (para os classificadores em hardware), taxa
de transferência e consumo de energia.
Os classificadores em hardware que utilizam ponto flutuante (Naive Bayes e kNN)
também foram avaliados com 10 e 16 bits, em adição às implementações originais, com 32 bits.
Nesses casos, todos os valores float dos classificadores têm o mesmo tamanho (32, 16 ou 10
bits), tanto para sinais e resultados internos quanto para os valores armazenados em memória.
Avaliou-se essa redução porque as operações com float em hardware são custosas.
A implementação do ponto flutuante de 16 bits no Naive Bayes e no kNN utilizou 1 bit
para sinal, 6 bits para expoente e 9 bits para a mantissa. Já a implementação de 10 bits, para os
dois classificadores, utilizou 1 bit para sinal, 6 bits para expoente e 3 bits para a mantissa. Esses
parâmetros forneceram o melhor resultado de acurácia. Além disso, no kNN, a normalização
do atributo tcp ack entre -1 e +1 requer ao menos 6 bits de expoente, devido ao grande valor
máximo do atributo.
Os resultados desta seção serão apresentados com as seguintes convenções:
87
• As implementações são nomeadas com os prefixos ad, nb e knn, denotando os
classificadores Árvore de Decisão, Naive Bayes e kNN, respectivamente;
• Os classificadores Naive Bayes incluem os infixos comb e seq, denotando as versões
combinacional e sequencial, respectivamente;
• Os classificadores que usam ponto flutuante incluem os sufixos 32, 16 e 10, indicando o
número de bits da representação em float.
7.2.1
ACURÁCIA DE CLASSIFICAÇÃO
Nesta subseção serão apresentados os resultados de acurácia de classificação dos
classificadores, considerando o conjunto de dados de teste (7480 instâncias: 3740 normais e
3740 ataques). Além da acurácia, serão mostradas as estimativas das taxas de falso-positivo e
falso-negativo, a partir do isolamento dos erros de classificação.
A tabela 5 mostra a matriz de confusão para o classificador Árvore de Decisão. Neste
tipo de apresentação de dados, os acertos do classificador são mostrados na diagonal principal
e os erros são mostrados na diagonal secundária. Dos 3740 vetores normais, 3736 foram
realmente classificados como normais e 4 foram classificados como ataques. Dos 3740 vetores
de ataque, 3734 foram realmente classificados como ataques e 6 foram classificados como
normais. Esses resultados foram obtidos tanto no programa Weka quanto nas implementações
em software e hardware do classificador. Os resultados implicam numa acurácia de 99,87%,
taxa de falso-positivo de 0,11% e taxa de falso-negativo de 0,16%, para o classificador Árvore
de Decisão.
Tabela 5: Matriz de confusão para o classificador Árvore de Decisão.
Normal
3736
6
Ataque ← classificado como
4
Normal
3734
Ataque
Fonte: Autoria própria.
A tabela 6 mostra a matriz de confusão para o classificador Naive Bayes. Dos 3740
vetores normais, 3727 foram realmente classificados como normais e 13 foram classificados
como ataques. Dos 3740 vetores de ataque, 3730 foram realmente classificados como ataques
e 10 foram classificados como normais. Esses resultados foram obtidos tanto no programa
Weka quanto nas implementações em software e hardware (para ponto flutuante de 32 bits)
do classificador. Os resultados implicam numa acurácia de 99,69%, taxa de falso-positivo de
0,35% e taxa de falso-negativo de 0,27%, para o classificafor Naive Bayes.
88
Tabela 6: Matriz de confusão para o classificador Naive Bayes.
Normal
3727
10
Ataque ← classificado como
13
Normal
3730
Ataque
Fonte: Autoria própria.
A tabela 7 mostra a matriz de confusão para o classificador kNN. Dos 3740 vetores
normais, 3656 foram realmente classificados como normais e 84 foram classificados como
ataques. Dos 3740 vetores de ataque, 3719 foram realmente classificados como ataques e
21 foram classificados como normais. Esses resultados foram obtidos tanto no programa
Weka quanto nas implementações em software e hardware (para ponto flutuante de 32 bits)
do classificador. Os resultados implicam numa acurácia de 98,60%, taxa de falso-positivo de
2,25% e taxa de falso-negativo de 0,56%, para o classificafor kNN.
Tabela 7: Matriz de confusão para o classificador kNN.
Normal
3656
21
Ataque ← classificado como
84
Normal
3719
Ataque
Fonte: Autoria própria.
A tabela 8 apresenta a acurácia de cada classificador, considerando também as
implementações em hardware com ponto flutuante de 16 e 10 bits. As versões em software
foram avaliadas apenas com 32 bits para os valores float.
Tabela 8: Acurácia dos classificadores sobre a base de testes.
Classificador
ad
nb comb 32
nb comb 16
nb comb 10
nb seq 32
nb seq 16
nb seq 10
knn 32
knn 16
knn 10
Acurácia (%)
99,87
99,69
99,69
99,68
99,69
99,69
99,68
98,60
98,57
97,09
Implementação
software e hardware
software e hardware
hardware
hardware
software e hardware
hardware
hardware
software e hardware
hardware
hardware
Fonte: Autoria própria.
O classificador que obteve a maior acurácia foi a Árvore de Decisão, acertando 99,87%
das classificações (em software e hardware). Na sequência vem o Naive Bayes com float de 32
bits, que acertou 99,69% das classificações (em software e hardware). As implementações
89
em hardware do Naive Bayes com 16 e 10 bits acertaram 99,69% e 99,68%, respectivamente.
Nestes casos, o circuito diminuiu, como será mostrado em breve, mas não houve redução de
acurácia para 16 bits e uma redução mı́nima para 10 bits. Percebe-se que as implementações
combinacional e sequencial do Naive Bayes são equivalentes do ponto de vista de acurácia.
Já o kNN de 32 bits acertou 98,60% das classificações (em software e hardware). As
implementações em hardware com 16 e 10 bits acertaram 98,57% e 97,09%, respectivamente.
Nestes casos, o circuito também diminuiu em detrimento da redução de acurácia.
7.2.2
ÁREA DOS CIRCUITOS
A tabela 9 apresenta a área usada pelos classificadores em hardware, quanto a células
lógicas, bits de memória e multiplicadores de 9 bits dedicados. A Árvore de Decisão é
o classificador mais compacto entre todos os classificadores, ocupando apenas 167 células
lógicas. A árvore não possui requisitos de memória e nem multiplicadores.
Tabela 9: Área utilizada pelos classificadores implementados em hardware.
Classificador
ad
nb comb 32
nb comb 16
nb comb 10
nb seq 32
nb seq 16
nb seq 10
knn 32
knn 16
knn 10
Células Lógicas Bits de Memória
167
0
8.420
0
3.085
0
2.115
0
1.380
10.112
743
6.528
633
4.992
6.300
465.920
3.090
228.352
2.024
128.000
Multiplicadores de 9 bits
0
126
36
0
14
4
0
14
4
2
Fonte: Autoria própria.
A versão combinacional do classificador Naive Bayes utiliza a maior área, com 8.420
células lógicas. Não foram utilizados bits de memória na sı́ntese porque o circuito armazena
os valores de probabilidades dos atributos em células lógicas. Até por isso a quantidade
de células é grande. Foram necessários 126 multiplicadores de 9 bits para a multiplicação
das probabilidades normal e de ataque dos atributos.
Ao reduzir-se os valores float do
classificador para 16 e 10 bits, foram obtidos 3.085 células lógicas, 36 multiplicadores e 2.115
células lógicas, 0 multiplicadores, respectivamente. Para 10 bits, o Quartus II sintetizou os
multiplicadores com células lógicas, em vez de usar multiplicadores dedicados.
A versão sequencial do classificador Naive Bayes utiliza 1.380 células lógicas. A
90
redução na quantidade de células foi possı́vel a partir do armazenamento dos valores de
probabilidades dos atributos na memória ROM. Foram utilizados 10.112 bits de memória para
esse armazenamento. Como o classificador compartilha os multiplicadores das probabilidades,
foram necessários apenas 14 multiplicadores de 9 bits. Ao reduzir-se os valores float do
classificador para 16 e 10 bits, foram obtidos 743 células lógicas, 6.528 bits de memória, 4
multiplicadores e 633 células lógicas, 4.992 bits de memória, 0 multiplicadores (nesse caso os
multiplicadores do classificador também foram sintetizados com células lógicas).
O classificador kNN requer a maior quantidade de bits de memória: 465.920, utilizados
para armazenar os vetores de treinamento do algoritmo. Foram necessários, ainda, 6.300
células lógicas e 14 multiplicadores de 9 bits. Esses últimos são utilizados nos módulos de
normalização e de cálculo de distância. Ao reduzir-se os valores float do classificador para 16
e 10 bits, foram obtidos 3.090 células lógicas, 228.352 bits de memória, 4 multiplicadores e
2.024 células lógicas, 128.000 bits de memória, 2 multiplicadores, respectivamente.
7.2.3
TAXA DE TRANSFERÊNCIA
A tabela 10 apresenta a taxa de transferência dos classificadores. Não há valores de
taxa de transferência em software para os classificadores com float de 10 e 16 bits, visto que em
software avaliaram-se apenas float de 32 bits.
Tabela 10: Taxa de transferência dos classificadores em software e hardware (em 50 MHz).
Classificador
ad
nb comb 32
nb comb 16
nb comb 10
nb seq 32
nb seq 16
nb seq 10
knn 32
knn 16
knn 10
Pacotes/s (hardware)
68.653.027
3.529.216
5.947.813
7.869.182
619.041
991.232
1.204.657
1.843
2.507
3.018
Acurácia Relativa (%)
100,00
100,00
100,00
99,99
100,00
100,00
99,99
100,00
99,97
98,47
Pacotes/s (software)
15.198.631
821.358
821.358
7.900
-
Fonte: Autoria própria.
A Árvore de Decisão em hardware tem a maior taxa de transferência entre todos os
classificadores, classificando mais de 68 milhões de pacotes por segundo. Esse valor é 4,5 vezes
a taxa de transferência da versão correspondente em software. A versão combinacional do Naive
Bayes em hardware com float de 32 bits também é mais rápida que a versão em software, por
um fator de 4,3. Em contrapartida, o Naive Bayes em software é mais rápido que a versão
91
sequencial do Naive Bayes em hardware com float de 32 bits por um fator de 1,3. O mesmo
acontece para o kNN, no qual a versão em software é mais rápida por um fator de 4,3. Isso
acontece, nos dois últimos casos, porque as implementações em hardware são inteiramente
sequenciais e os classificadores possuem frequência máxima de operação bem menor que a
frequência de clock do processador da placa-mãe.
A acurácia relativa indica a predição de cada classificador em hardware relativa à
versão em software. Para as versões com float de 32 bits, a acurácia relativa é 100% porque
hardware e software fornecem os mesmos resultados. Ao reduzir-se o número de bits em
hardware, a acurácia é reduzida (com exceção do Naive Bayes de 16 bits). A perda de acurácia
foi menor do que 2 pontos percentuais em todos os casos, mas a partir da redução do tamanho
do float de 32 para 10 bits em hardware, aumentaram-se as taxas de transferência em 123%,
95% e 64% para Naive Bayes combinacional, Naive Bayes sequencial e kNN, respectivamente.
Com exceção do kNN, todos os outros classificadores (tanto em software quanto em
hardware) são capazes de atender à taxa máxima da Fast Ethernet de 150.000 pacotes/s.
7.2.4
CONSUMO DE ENERGIA
O consumo dos classificadores em hardware foi medido para 50 MHz, porque não
houve erro de classificação em nenhum classificador nessa frequência de operação.
A figura 40 mostra o gráfico da potência do circuito de medição pelo número de
réplicas dos classificadores em hardware. O consumo varia linearmente com o número de
réplicas, então as potências consumidas pelos classificadores foram calculadas através de
regressão linear como o coeficiente angular da reta de tendência correspondente. Cada uma das
dez linhas, se projetadas, cruzam o eixo vertical em aproximadamente 200 mW (caso para 0
classificadores). Este valor é devido, majoritariamente, ao consumo base da FPGA e ao circuito
de medição e portanto não é considerado no cálculo de consumo dos classificadores.
É importante ressaltar que o coeficiente angular inclui, também, o consumo da parte
do circuito de medição que é proporcional ao número de réplicas dos classificadores. Assim, os
consumos reais dos classificadores em hardware são ainda menores do que os valores que serão
apresentados a seguir.
A tabela 11 resume o consumo de energia e a acurácia relativa dos classificadores
implementados. O termo Phab refere-se à potência média consumida por cada classificador em
hardware, enquanto habilitado, obtida por regressão linear, conforme comentado acima. O
termo Pdes refere-se à potência média consumida por cada classificador em hardware, enquanto
92
Figura 40: Potência do circuito de medição pelo no de classificadores em 50 MHz.
Fonte: Autoria Própria
desabilitado, também obtida por regressão linear. Essa potência, porém, não entrou no cálculo
de consumo, pois considera-se que cada classificador em hardware opera na sua taxa de
transferência, de forma que entre a chegada de pacotes o circuito sempre está ativo.
Tabela 11: Energia consumida pelos classificadores em software e hardware (em 50 MHz).
Classificador
ad
nb comb 32
nb comb 16
nb comb 10
nb seq 32
nb seq 16
nb seq 10
knn 32
knn 16
knn 10
Pdes
(mW)
1,37
3,58
3,36
3,09
3,90
2,73
2,53
84,30
28,71
15,47
Energia por op.
Acurácia
Energia por op.
Phab
(mW) em hardware (nJ) Relativa (%) em software (nJ)
2,76
0,055
100,00
53,54
714,45
42,87
100,00
635,25
85,55
5,13
100,00
35,91
2,15
99,99
14,72
21,49
100,00
635,25
5,62
8,20
100,00
4,51
6,58
99,99
105,12
50.659,43
100,00
58.387,93
33,39
16.089,38
99,97
17,26
8.319,38
98,47
Fonte: Autoria própria.
A Árvore de Decisão em hardware é o classificador mais eficiente energeticamente,
gastando 55 pJ por classificação; apenas 0,1% do consumo da versão em software. As versões
com float de 32 bits dos classificadores Naive Bayes combinacional e sequencial também são
mais eficientes que a versão em software. O primeiro consome 42,87 nJ por classificação,
93
6,7% do consumo em software, e o segundo consome 21,49 nJ, 3,4% do consumo em software.
Quanto ao kNN, mais uma vez a versão em hardware consome menos: 50,66 µJ, o que
corresponde a 86,8% do consumo da versão em software.
As economias de energia obtidas a partir da redução do tamanho do ponto flutuante
de 32 para 10 bits em hardware foram de 95%, 69% e 84% para Naive Bayes Combinacional,
Naive Bayes Sequencial e kNN, respectivamente.
A figura 41 mostra lado a lado a energia gasta por cada classificador para classificar um
pacote. As barras pretas correspondem aos classificadores em software (mostrados com o sufixo
“sw”), enquanto as barras cinzas correspondem aos classificadores em hardware (mostrados
com o sufixo “hw”). Através da imagem é possı́vel confirmar que a diferença de consumo
entre a implementação em hardware mais eficiente (Árvore de Decisão) e a implementação em
software mais eficiente (Árvore de Decisão) é de três ordens de magnitude.
Figura 41: Energia gasta para classificar um pacote em software e hardware (em 50 MHz).
Fonte: Autoria Própria
Adicionalmente, calculou-se também a energia consumida por classificação em
hardware para as frequências de operação de 10, 20, 30 e 40 MHz. A figura 42 mostra que esses
valores são próximos aos obtidos para 50 MHz. Conclui-se, então, que o consumo energético
dos classificadores em hardware depende minoritariamente da frequência.
O consumo
de potência e o tempo de classificação são, respectivamente, diretamente e inversamente
proporcionais à frequência de operação, e por isso o valor de energia se mantém quase constante.
94
Figura 42: Energia gasta para classificar um pacote em hardware em diferentes frequências.
Fonte: Autoria Própria
Como observação final, ressalta-se que caso um classificador em hardware não
operasse em sua taxa de transferência, a potência desse enquanto desabilitado entraria no
cálculo do consumo energético. Porém, para evitar essa situação, outra tática poderia ser
adotada: executar o circuito com uma frequência mais baixa de forma a preencher todo o tempo
de chegada entre pacotes com a classificação. O mesmo raciocı́nio é válido para o extrator.
7.3
PUBLICAÇÕES
O desenvolvimento deste trabalho proporcionou a publicação de dois artigos em
congressos internacionais do IEEE, conforme referências abaixo:
• FRANÇA, André L.; JASINSKI, Ricardo; PEDRONI, Volnei A.; SANTIN, Altair O.
Moving Network Protection from Software to Hardware: An Energy Efficiency Analysis.
In: Computer Society Annual Symposium on VLSI 2014 (ISVLSI 2014). Tampa, Estados
Unidos: IEEE, 2014. p. 456-461
• FRANÇA, André L.; JASINSKI, Ricardo; CEMIN, Paulo; PEDRONI, Volnei A.;
SANTIN, Altair O. The Energy Cost of Network Security: A Hardware vs. Software
Comparison. In: International Symposium on Circuits and Systems 2015 (ISCAS 2015).
Lisboa, Portugal: IEEE, 2015.
95
8
CONCLUSÃO
Neste trabalho foram desenvolvidos algoritmos necessários ao projeto de um Sistema
de Detecção de Intrusão de Rede baseado em anomalia. Os algoritmos contemplados foram
um extrator de caracterı́sticas dos pacotes da rede em hardware (versão correspondente a um
extrator existente em software) e três classificadores de Aprendizagem de Máquina (Árvore
de Decisão, Naive Bayes e k-Vizinhos mais Próximos, ou kNN), em software e hardware,
modelados para detecção de ataques do tipo probing.
Os algoritmos em software foram implementados em C++ e avaliados numa placa-mãe
Atom DN2800MT com o Sistema Operacional openSUSE 13.1. Os algoritmos em hardware
foram implementados em VHDL e avaliados na FPGA Cyclone IV GX, da Altera. Para as
duas versões do extrator de caracterı́sticas foram comparados consumo energético e taxa de
transferência. Para as versões em software e hardware dos classificadores, além do consumo
energético e taxa de transferência, comparou-se, ainda, a acurácia de classificação.
O extrator de caracterı́sticas em software, desenvolvido por Eduardo Kugler Viegas
e Altair Olivo Santin, obteve uma taxa de transferência de 295.615 pacotes/s. A versão
correspondente em hardware, em contrapartida, obteve uma taxa de transferência de 534.815
pacotes/s. Com relação ao consumo energético por operação de extração, os valores das versões
em software e hardware foram de 5,03 µJ e 1,15 µJ, respectivamente. O extrator em hardware,
então, opera numa velocidade quase duas vezes maior, gastando apenas 23% do valor de
energia da implementação em software. O extrator em hardware ocupa 2.683 células lógicas e
5.242.880 bits de memória da FPGA.
Quanto aos classificadores, a Árvore de Decisão obteve a melhor acurácia de
classificação na base de dados de testes: 99,87%, tanto em software quanto em hardware. Na
sequência vêm Naive Bayes e kNN, com acurácias de 99,69% e 98,60%, respectivamente, tanto
em software quanto em hardware (com float de 32 bits). Para Naive Bayes e kNN avaliou-se,
ainda, a redução do tamanho do ponto flutuante em hardware. As perdas de acurácia foram
menores do que 2 pontos percentuais na redução de 32 para 10 bits.
96
Os classificadores em hardware foram comparados, também, quanto à área.
A
Árvore de Decisão é o classificador mais compacto, ocupando 167 células lógicas.
A
versão combinacional do Naive Bayes ocupa a maior área, com 8.420 células lógicas e 126
multiplicadores de 9 bits. O kNN utiliza a maior quantidade de bits de memória, 465.920, além
de 6.300 células e 14 multiplicadores. A versão sequencial do Naive Bayes ocupa 1.380 células
lógicas, 10.112 bits de memória e 14 multiplicadores. Reduzindo-se o float de 32 para 10 bits,
as áreas de Naive Bayes combinacional e sequencial e kNN foram reduzidas em mais de 50%.
A Árvore de Decisão em hardware alcançou a maior taxa de transferência entre
todos os classificadores: 68.653.028 pacotes/s, ou 4,5 vezes a taxa da versão correspondente
em software (15.198.631 pacotes/s). A versão combinacional do Naive Bayes em hardware
(3.529.217 pacotes/s) também é mais rápida que a versão em software (821.358 pacotes/s), mas
o mesmo não acontece para a versão sequencial em hardware (619.041 pacotes/s). Para o kNN,
a versão em software (7.900 pacotes/s) também é mais rápida que a versão em hardware (1.843
pacotes/s). Nos últimos dois casos isso acontece porque os classificadores em hardware são
inteiramente sequenciais e operam numa frequência bem menor que a frequência de clock do
processador da placa-mãe. A partir da redução do tamanho do ponto flutuante de 32 para 10
bits em hardware, aumentaram-se as taxas de transferência em 123%, 95% e 64% para Naive
Bayes combinacional, Naive Bayes sequencial e kNN, respectivamente.
A Árvore de Decisão em hardware é o classificador mais eficiente energeticamente,
gastando 55 pJ para classificar um pacote, ou 0,1% da energia gasta pela versão correspondente
em software (53,54 nJ). As versões combinacional (42,87 nJ) e sequencial (21,49 nJ) do Naive
Bayes em hardware também são mais eficientes que a versão em software (635,25 nJ). Em
relação ao kNN, mais uma vez, embora por pouco, a versão em hardware (50,66 µJ) é mais
eficiente energeticamente que a versão em software (58,39 µJ). As economias de energia obtidas
a partir da redução do tamanho do ponto flutuante de 32 para 10 bits em hardware foram de 95%,
69% e 84% para Naive Bayes Combinacional, Naive Bayes Sequencial e kNN, respectivamente.
Os trabalhos futuros incluem: 1) otimização do classificador kNN em hardware, a
partir da realização de operações em paralelo e avaliação do cálculo de distância Manhattan
em vez da Euclidiana (MANOLAKOS; STAMOULIAS, 2010); 2) desenvolvimento dos
classificadores Máquina de Vetor de Suporte (SVM, do inglês Support Vector Machine) e
Análise de Discriminante Linear (LDA, do inglês Linear Discriminant Analysis) para detecção
de probing; 3) desenvolvimento dos classificadores Árvore de Decisão, Naive Bayes, kNN,
SVM e LDA para detecção de ataques do tipo DoS.
97
REFERÊNCIAS
BRUGGER, S. T. Data Mining Methods for Network Intrusion Detection. Davis: University
of California, Davis, 2004. 64 p.
CATANIA, Carlos A.; GARINO, Carlos G. Automatic network intrusion detection: Current
techniques and open issues. Computers & Electrical Engineering, v. 38, n. 5, p. 1062-1072,
set. 2012.
CEMIN, Paulo R. Plataforma de Medição de Consumo para Comparação entre Software
e Hardware em Projetos Energeticamente Eficientes. 2015. 99 f. Dissertação (Mestrado em
Engenharia Elétrica e Informática Industrial) – Programa de Pós-Graduação em Engenharia
Elétrica e Informática Industrial, Universidade Tecnológica Federal do Paraná, Curitiba, 2015.
CHEN, Hao; CHEN, Yu; SUMMERVILLE, Douglas H. A Survey on the Application of FPGAs
for Network Infrastructure Security. IEEE Communications Surveys & Tutorials, v. 13, n. 4,
p. 541-561, nov. 2011.
CHENG, Xiang et al. Intrusion Detection System Based on KNN-MARS. In: WRI World
Congress on Software Engineering 2009 (WCSE ’09). Xiamen, China: IEEE, 2009. p. 392396.
CISCO. Bandwidth, Packets Per Second, and Other Network Performance Metrics. San
Jose: Cisco, 2009. 3 p.
CISCO. Visual Networking Index: Forecast and Methodology, 2013–2018. San Jose: Cisco,
2014. 14 p.
CORONA, Igino; GIACINTO, Giorgio; ROLI, Fabio. Adversarial attacks against intrusion
detection systems: Taxonomy, solutions and open issues. Information Sciences, v. 239, p.
201-225, ago. 2013.
DAS, Abhishek et al. An FPGA-Based Network Intrusion Detection Architecture. IEEE
Transactions on Information Forensics and Security, v. 3, n. 1, p. 118-132, mar. 2008.
DAVIS, Jonathan J.; CLARK, Andrew J. Data preprocessing for anomaly based network
intrusion detection: A review. Computers & Security, v. 30, n. 6-7, p. 353-375, set.-out. 2011.
DUDA, Richard O.; HART, Peter E.; STORK, David G. Pattern Classification. 2. ed. [S.l.]:
Willey Interscience, 2002.
ESTEVEZ-TAPIADOR, Juan M.; GARCÍA-TEODORO, Pedro; DIAZ-VERDEJO, Jesus
E. Stochastic Protocol Modeling for Anomaly Based Network Intrusion Detection. In:
International Workshop on Information Assurance 2003 (IWIAS 2003). Darmstadt,
Alemanha: IEEE, 2003. p. 3-12.
EVANS, Dave. The Internet of Things: How the Next Evolution of the Internet Is Changing
Everything. San Jose: Cisco, 2011. 11 p.
98
FRANÇA, André L. et al. The Energy Cost of Network Security: A Hardware vs. Software
Comparison. In: International Symposium on Circuits and Systems 2015 (ISCAS 2015).
Lisboa, Portugal: IEEE, 2015.
GARCÍA-TEODORO, Pedro et al. Anomaly-based network intrusion detection: Techniques,
systems and challenges. Computers & Security, v. 28, n. 1-2, p. 18-28, fev.-mar. 2009.
GOGOI, Prasanta et al. Packet and Flow Based Network Intrusion Dataset. In: International
Conference on Contemporary Computing 2012 (IC3 2012). Noida, India: Springer, 2012. p.
322-334.
HARWAYNE-GIDANSKY, Jared; STEFAN, Deian; DALAL, Ishaan. FPGA-based SoC for
Real-Time Network Intrusion Detection using Counting Bloom Filters. In: Southeastcon 2009.
Atlanta, Estados Unidos: IEEE, 2009. p. 452-458.
IBRAHIM, Heba E.; BADR, Sherif M.; SHAHEEN, Mohamed A. Phases vs. Levels using
Decision Trees for Intrusion Detection Systems. International Journal of Computer Science
and Information Security (IJCSIS), v. 10, n. 8, p. 1-7, ago. 2012.
KATASHITA, Toshihiro et al. FPGA-Based Intrusion Detection System for 10 Gigabit Ethernet.
IEICE Transactions on Information and Systems, E90-D, n. 12, p. 1923-1931, dez. 2007.
KENDALL, Kristopher. A Database of Computer Attacks for the Evaluation of
Intrusion Detection Systems. 1999. 124 f. Dissertação (Mestrado em Electrical Engineering
and Computer Science) – Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, Cambridge, 1999.
KIZZA, Joseph M. Guide to Computer Network Security. 2nd. ed. [S.l.]: Springer, 2013.
KOSHAL, Jashan; BAG, Monark. Cascading of C4.5 Decision Tree and Support Vector
Machine for Rule Based Intrusion Detection System. International Journal of Computer
Network and Information Security (IJCNIS), v. 4, n. 8, p. 8-20, ago. 2012.
LE, Hoang; PRASANNA, Viktor K. A Memory-Efficient and Modular Approach for LargeScale String Pattern Matching. IEEE Transactions on Computers, v. 62, n. 5, p. 844-857,
mai. 2013.
LI, Wei; LI, QingXia. Using Naive Bayes with AdaBoost to Enhance Network Anomaly
Intrusion Detection. In: International Conference on Intelligent Networks and Intelligent
Systems 2010 (ICINIS 2010). Shenyang, China: IEEE, 2010. p. 486-489.
LI, Yang; GUO, Li. An active learning based TCM-KNN algorithm for supervised network
intrusion detection. Computers & Security, v. 26, n. 7-8, p. 459-467, dez. 2007.
MANOLAKOS, Elias S.; STAMOULIAS, Ioannis. Flexible IP cores for the k-NN classification
problem and their FPGA implementation. In: International Symposium on Parallel
Distributed Processing, Workshops and Phd Forum 2010 (IPDPSW 2010). Atlanta, Estados
Unidos: IEEE, 2010. p. 1-4.
MITCHELL, Tom M. Machine Learning. [S.l.]: McGraw-Hill, 1997.
99
MUKHERJEE, Saurabh; SHARMA, Neelam. Intrusion Detection using Naive Bayes Classifier
with Feature Reduction. In: International Conference on Computer, Communication,
Control and Information Technology 2012 (C3IT-2012). Hooghly, Índia: Elsevier, 2012.
p. 119-128.
MURALEEDHARAN, N.; PARMAR, Arun; KUMAR, Manish. A Flow based Anomaly
Detection System using Chi-square Technique. In: International Advance Computing
Conference 2010 (IACC 2010). Patiala, Índia: IEEE, 2010. p. 285-289.
PONTARELLI, Salvatore; BIANCHI, Giuseppe; TEOFILI, Simone. Traffic-Aware Design of a
High-Speed FPGA Network Intrusion Detection System. IEEE Transactions on Computers,
v. 62, n. 11, p. 2322-2334, nov. 2013.
POSTEL, Jon. RFC 768 - User Datagram Protocol. Marina del Rey: USC Information
Sciences Institute, 1980. 3 p.
POSTEL, Jon. RFC 791 - Internet Protocol. Marina del Rey: USC Information Sciences
Institute, 1981. 45 p.
POSTEL, Jon. RFC 792 - Internet Control Message Protocol. Marina del Rey: USC
Information Sciences Institute, 1981. 21 p.
POSTEL, Jon. RFC 793 - Transmission Control Protocol. Marina del Rey: USC Information
Sciences Institute, 1981. 85 p.
PUKKAWANNA, Sirikarn et al. Investigating the Utility of S-Transform for Detecting Denialof-Service and Probe Attacks. In: International Conference on Information Networking
2014 (ICOIN 2014). Phuket, Tailândia: IEEE, 2014. p. 282-287.
ROESCH, Martin. Snort - Lightweight Intrusion Detection for Networks. In: USENIX
Conference on System Administration 1999 (LISA ’99). Berkeley, Estados Unidos: USENIX
Association, 1999. p. 229-238.
SOMAVAT, Pavel; NAMBOODIRI, Vinod. Energy Consumption of Personal Computing
Including Portable Communication Devices. Journal of Green Engineering, p. 447-475, jul.
2011.
SONG, Haoyu; LOCKWOOD, John W. Efficient Packet Classification for Network Intrusion
Detection Using FPGA. In: International Symposium on Field-programmable Gate Arrays
2005 (FPGA ’05). Monterey, Estados Unidos: ACM, 2005. p. 238-245.
SOURCEFIRE. SNORT Users Manual. Disponı́vel em: <http://manual.snort.org/>. Acesso
em: 09 dez. 2014.
STANIFORD, Stuart; HOAGLAND, James A.; MCALERNEY, Joseph M. Practical Automated
Detection of Stealthy Portscans. Journal of Computer Security, v. 10, n. 1-2, p. 105-136,
2002.
THE UNIVERSITY OF WAIKATO. Attribute-Relation File Format (ARFF). Disponı́vel em:
<http://weka.wikispaces.com/ARFF>. Acesso em: 13 nov. 2013.
TSAI, Chih-Fong et al. Intrusion detection by machine learning: A review. Expert Systems
with Applications, v. 36, n. 10, p. 11994-12000, dez. 2009.
100
TUNCER, Taner; TATAR, Yetkin. FPGA Based Programmable Embedded Intrusion Detection
System. In: International Conference on Security of Information and Networks 2010 (SIN
’10). Taganrog, Rússia: ACM, 2010. p. 245-248.
UNIVERSITY OF CALIFORNIA, IRVINE. KDD Cup 1999 Data. Disponı́vel em:
<http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html>. Acesso em: 10 set. 2013.
UNIVERSITY OF NEW BRUNSWICK. The NSL-KDD Data Set. Disponı́vel em:
<http://nsl.cs.unb.ca/NSL-KDD/>. Acesso em: 10 set. 2013.
VIEGAS, Eduardo K. et al. EEIDS: Method and Energy-Efficient FPGA-based SoC
Implementation for Anomaly Detection System. PUCPR/UTFPR: Curitiba, 2013. n. 2.
VIEGAS, Eduardo K. et al. EEIDS: Method and Energy-Efficient FPGA-based SoC
Implementation for Anomaly Detection System. PUCPR/UTFPR: Curitiba, 2014. n. 3.
VIEGAS, Eduardo K. et al. EEIDS: Method and Energy-Efficient FPGA-based SoC
Implementation for Anomaly Detection System. PUCPR/UTFPR: Curitiba, 2014. n. 4.
VIJAYASARATHY, R.; RAGHAVAN, S.; RAVINDRAN, Balaraman. A System Approach to
Network Modeling for DDoS Detection using a Naive Bayesian Classifier. In: International
Conference on Communication Systems and Networks 2011 (COMSNETS 2011).
Bangalore, Índia: IEEE, 2011. p. 1-10.
WU, Shelly X.; BANZHAF, Wolfgang. The use of computational intelligence in intrusion
detection systems: A review. Applied Soft Computing, v. 10, n. 1, p. 1-35, jan. 2010.